【数字编码表】求多媒体数字编码方法使用算数编码对二进制消息序列...

【数字编码表】求多媒体数字编码方法使用算数编码对二进制消息序列...

【答案】 算术编码在图像数据压缩标准(如JPEG,JBIG)中扮演了重要的角色.在算术编码中,消息用0到1之间的实数进行编码,算术编码用到两个基本的参数：符号的概率和它的编码间隔.信源符号的概率决定压缩编码的效率,也决定编码过程中信源符号的间隔,而这些间隔包含在0到1之间.编码过程中的间隔决定了符号压缩后的输出.算术编码器的编
　　码过程可用下面的例子加以解释.
　　[例4.2] 假设信源符号为{00, 01, 10, 11},这些符号的概率分别为{ 0.1, 0.4, 0.2, 0.3 },根据这些概率可把间隔[0, 1)分成4个子间隔：[0, 0.1), [0.1, 0.5), [0.5, 0.7), [0.7, 1),其中表示半开放间隔,即包含不包含.上面的信息可综合在表4-04中
　　.
　　表4-04 信源符号,概率和初始编码间隔
　　符号
　　00
　　01
　　10
　　11
　　概率
　　0.1
　　0.4
　　0.2
　　0.3
　　初始编码间隔
　　初始编码间隔
　　[0, 0.1)
　　[0.1, 0.5)
　　[0.5, 0.7)
　　[0.7, 1)
　　如果二进制消息序列的输入为：10 00 11 00 10 11 01.编码时首先输入的符号是10,
　　找到它的编码范围是[0.5, 0.7).由于消息中第二个符号00的编码范围是[0, 0.1),因
　　此它的间隔就取[0.5, 0.7)的第一个十分之一作为新间隔[0.5, 0.52).依此类推,编码
　　第3个符号11时取新间隔为[0.514, 0.52),编码第4个符号00时,取新间隔为[0.514, 0
　　.5146),… .消息的编码输出可以是最后一个间隔中的任意数.整个编码过程如图4-0
　　3所示.
　　图4-03 算术编码过程举例
　　这个例子的编码和译码的全过程分别表示在表4-05和表4-06中.根据上面所举的例子,
　　可把计算过程总结如下.
　　考虑一个有M个符号的字符表集,假设概率,而.输入符号用表示,第个子间隔的范围用
　　表示.其中,和,表示间隔左边界的值, 表示间隔右边界的值,表示间隔长度.编码步
　　骤如下：
　　步骤1：首先在1和0之间给每个符号分配一个初始子间隔,子间隔的长度等于它的概率,
　　初始子间隔的范围用[,)表示.令,和.
　　步骤2：L和R的二进制表达式分别表示为：
　　和
　　其中和等于“1”或者“0”.
　　比较和：①如果,不发送任何数据,转到步骤3；②如果,就发送二进制符号.
　　比较和：①如果,不发送任何数据,转到步骤3；②如果,就发送二进制符号.
　　…
　　这种比较一直进行到两个符号不相同为止,然后进入步骤3,
　　步骤3：加1,读下一个符号.假设第个输入符号为,按照以前的步骤把这个间隔分成如
　　下所示的子间隔：
　　令,和,然后转到步骤2.
　　表4-05 编码过程
　　步骤
　　输入
　　符号
　　编码间隔
　　编码判决
　　1
　　10
　　[0.5, 0.7)
　　符号的间隔范围[0.5, 0.7)
　　2
　　00
　　[0.5, 0.52)
　　[0.5, 0.7)间隔的第一个1/10
　　3
　　11
　　11
　　[0.514, 0.52)
　　[0.5, 0.52)间隔的最后一个1/10
　　4
　　00
　　[0.514, 0.5146)
　　[0.514, 0.52)间隔的第一个1/10
　　5
　　10
　　[0.5143, 0.51442)
　　[0.514, 0.5146)间隔的第五个1/10开始,二个1/10
　　6
　　11
　　[0.514384, 0.51442)
　　[0.5143, 0.51442)间隔的最后3个1/10
　　7
　　01
　　[0.5143836, 0.514402)
　　[0.514384, 0.51442)间隔的4个1/10,从第1个1/10开始
　　8
　　从[0.5143876, 0.514402中选择一个数作为输出：0.5143876
　　表4-06 译码过程
　　步骤
　　步骤
　　间隔
　　译码符号
　　译码判决
　　1
　　[0.5, 0.7)
　　10
　　0.51439在间隔 [0.5, 0.7)
　　2
　　[0.5, 0.52)
　　00
　　0.51439在间隔 [0.5, 0.7)的第1个1/10
　　3
　　[0.514, 0.52)
　　11
　　0.51439在间隔[0.5, 0.52)的第7个1/10
　　4
　　[0.514, 0.5146)
　　00
　　0.51439在间隔[0.514, 0.52)的第1个1/10
　　5
　　[0.5143, 0.51442)
　　10
　　10
　　0.51439在间隔[0.514, 0.5146)的第5个1/10
　　6
　　[0.514384, 0.51442)
　　11
　　0.51439在间隔[0.5143, 0.51442)的第7个1/10
　　7
　　[0.51439, 0.5143948)
　　01
　　0.51439在间隔[0.51439, 0.5143948)的第1个1/10
　　7
　　译码的消息：10 00 11 00 10 11 01
　　[例3] 假设有4个符号的信源,它门的概率如表4-07所示：
　　表4-07 符号概率
　　信源符号ai
　　概率
　　初始编码间隔
　　[0, 0.5)
　　[0.5, 0.75)
　　[0.75, 0.875)
　　[0.875, 1)
　　输入序列为.它的编码过程如图4-04所示,现说明如下.
　　输入第1个符号是,可知,定义初始间隔[,)＝[0.5, 0.75),由此可知,左右边界的二
　　进制数分别表示为：L＝0.5=0.1(B),R＝0.7＝0.11… (B) .按照步骤2,发送1.因
　　,因此转到步骤3.
　　输入第2个字符,它的子间隔, )＝[0.5, 0.625),由此可得=0.125.左右边界的二进
　　制数分别表示为：L＝0.5=0.100 … (B),R＝0.101… (B).按照步骤2,发送0,而和
　　不相同,因此在发送0之后就转到步骤3.
　　输入第3个字符, 它的子间隔[, )＝[0.59375, 0.609375),由此可得=0.015625.左
　　右边界的二进制数分别表示为：＝0.59375=0.10011 (B),＝0.609375=0.100111 (B).
　　按照步骤2,但和不相同,因此在发送011之后转到步骤3.
　　…
　　发送的符号是：10011….被编码的最后的符号是结束符号.
　　图4-04 算术编码概念
　　就这个例子而言,算术编码器接受的第1位是“1”,它的间隔范围就限制在[0.5, 1),
　　但在这个范围里有3种可能的码符, 和,因此第1位没有包含足够的译码信息.在接受第
　　2位之后就变成“10”,它落在[0.5, 0.75)的间隔里,由于这两位表示的符号都指向开
　　始的间隔,因此就可断定第一个符号是.在接受每位信息之后的译码情况如下表4-08所
　　示.
　　表4-08 译码过程表
　　接受的数字
　　间隔
　　译码输出
　　1
　　[0.5, 1)
　　[0.5, 1)
　　-
　　0
　　[0.5, 0.75)
　　0
　　[0.5, 0.609375)
　　1
　　[0.5625, 0.609375)
　　-
　　1
　　[0.59375, 0.609375)
　　…
　　…
　　…
　　在上面的例子中,我们假定编码器和译码器都知道消息的长度,因此译码器的译码过程
　　不会无限制地运行下去.实际上在译码器中需要添加一个专门的终止符,当译码器看到
　　终止符时就停止译码.
　　在算术编码中需要注意的几个问题：
　　由于实际的计算机的精度不可能无限长,运算中出现溢出是一个明显的问题,但多数机
　　器都有16位、32位或者64位的精度,因此这个问题可使用比例缩放方法解决.
　　算术编码器对整个消息只产生一个码字,这个码字是在间隔[0, 1)中的一个实数,因此
　　译码器在接受到表示这个实数的所有位之前不能进行译码.
　　算术编码也是一种对错误很敏感的编码方法,如果有一位发生错误就会导致整个消息译
　　错.
　　算术编码可以是静态的或者自适应的.在静态算术编码中,信源符号的概率是固定的.
　　在自适应算术编码中,信源符号的概率根据编码时符号出现的频繁程度动态地进行修改
　　,在编码期间估算信源符号概率的过程叫做建模.需要开发动态算术编码的原因是因为
　　事先知道精确的信源概率是很难的,而且是不切实际的.当压缩消息时,我们不能期待
　　一个算术编码器获得最大的效率,所能做的最有效的方法是在编码过程中估算概率.因
　　此动态建模就成为确定编码器压缩效率的关键.

谢谢了