第13讲-信源编码2

1、 东北石油大学电气信息工程学院东北石油大学电气信息工程学院 张玉波张玉波15.7 5.7 算术编码算术编码n 原理：原理： 算术编码是另一种常用的算术编码是另一种常用的变字长编码变字长编码，它也是利用信源概率分，它也是利用信源概率分布特性、能够趋近熵极限的编码方法。它与布特性、能够趋近熵极限的编码方法。它与 Huffman Huffman 一样，也是对一样，也是对出现出现概率大的符号赋予短码，对概率小的符号赋予长码概率大的符号赋予短码，对概率小的符号赋予长码。但它的编。但它的编码过程与码过程与 Huffman Huffman 编码却不相同，而且在信源概率分布比较均匀的编码却不相同，而且在信源概

2、率分布比较均匀的情况下其编码效率高于情况下其编码效率高于 Huffman Huffman 编码。它和编码。它和 Huffman Huffman 编码最大的编码最大的区别在于它不是使用整数码。区别在于它不是使用整数码。 Huffman Huffman 码是用整数长度的码字来编码的最佳方法，码是用整数长度的码字来编码的最佳方法，而算法编码是一种并不局限于整数长度码字的最佳编码而算法编码是一种并不局限于整数长度码字的最佳编码方法。方法。 算术编码是把各符号出现的概率算术编码是把各符号出现的概率表示在单位概率表示在单位概率 00，1 1 区间之中，区间的宽度代表概率值的大小区间之中，区间的宽度代表概率

3、值的大小。符号出现。符号出现的概率越大对应于区间愈宽，可用较短码字表示；符号的概率越大对应于区间愈宽，可用较短码字表示；符号出现概率越小对应于区间愈窄，需要较长码字表示。出现概率越小对应于区间愈窄，需要较长码字表示。 东北石油大学电气信息工程学院东北石油大学电气信息工程学院 张玉波张玉波2算术编码算术编码原理原理n 符号序列符号序列S S3 3S S3 3S S2 2S S4 4 为例为例S1S2S3S4S1S2S3S4S1S2S3S401/83/87/81.000.0010.0110.1111.00.0110.1110.0111 0.10010.1101在算术编码中通常采用二进制分数表在算术

4、编码中通常采用二进制分数表示概率，示概率，每个符号所对应的概率区间每个符号所对应的概率区间都是半开区间都是半开区间，即该区间包括左端点，即该区间包括左端点，而不包括右端点，如而不包括右端点，如 S S1 1对应对应 0, 0, 0.001)0.001)，S S2 2 对应对应 0.001, 0.01) 0.001, 0.01) 等。等。 东北石油大学电气信息工程学院东北石油大学电气信息工程学院 张玉波张玉波3算术编码算术编码原理原理n 符号序列符号序列 S S3 3S S3 3S S2 2S S4 4 的第一个符号的第一个符号 S S3 3 用指向第用指向第 3 3 个子区间的个子区间的指针来

5、代表，指针来代表，可以用这个区间内的任意一个小数来表示这个指针，可以用这个区间内的任意一个小数来表示这个指针，这里约定这个区间的左端点代表这个指针，因此得到第一个码这里约定这个区间的左端点代表这个指针，因此得到第一个码字字 .011.011。n 后续的编码将在前面编码指向的子区间内进行，将后续的编码将在前面编码指向的子区间内进行，将 .011, .111 .011, .111 区间再按概率大小划分为区间再按概率大小划分为 4 4 份，第二个符号份，第二个符号 S S3 3 指向指向 .1001 (S.1001 (S3 3 区间的左端），输出码字变为区间的左端），输出码字变为 .1001.100

6、1。n 然后，然后，S S3 3 对应的子区间又被划分为对应的子区间又被划分为 4 4 份，开始对第三个符号份，开始对第三个符号 S S2 2 进行编码，进行编码，. . n 算术编码产生的码字实际上是一个二进制数值的算术编码产生的码字实际上是一个二进制数值的指针，指向所编的符号对应的概率区间。指针，指向所编的符号对应的概率区间。 东北石油大学电气信息工程学院东北石油大学电气信息工程学院 张玉波张玉波4算术编码算术编码基本法则基本法则n 两个参量：两个参量：编码点（指针所指处）编码点（指针所指处）C C 和区间宽度和区间宽度 A A。 初始状态初始状态 编码点（指针所指处）编码点（指针所指处）

7、C = 0C = 0 区间宽度区间宽度 A = 1.0A = 1.0 新编码点新编码点 C = C = 原编码点原编码点 C C 原区间原区间 A AP Pi i 新区间新区间 A = A = 原区间原区间 A Ap pi i n 序列序列 S S3 3S S3 3S S2 2S S4 4 的编码过程：的编码过程： 第第1 1个符号个符号 (S(S3 3): ): C = 0 + 1C = 0 + 1.011 = .011.011 = .011 A = 1A = 1.1 = .1.1 = .1 第第2 2个符号个符号 (S(S3 3): ): C = .011 + .1C = .011 + .

8、1.011 = .1001.011 = .1001 A = .1A = .1.1 = .01.1 = .01 第第3 3个符号个符号 (S(S2 2): C = .1001 + .01): C = .1001 + .01.001 = .10011 .001 = .10011 A = .01 A = .01.01 = .0001.01 = .0001 第第4 4个符号个符号 (S(S4 4): C = .10011 + .0001): C = .10011 + .0001.111 = .1010011 .111 = .1010011 （输出（输出的码字）的码字） A = .0001A = .00

9、01.001 = .0000001.001 = .0000001符号符号 S Si i 对应对应的的累积概率累积概率符号符号 S Si i 对对应的应的概率概率 东北石油大学电气信息工程学院东北石油大学电气信息工程学院 张玉波张玉波5算术编码算术编码解码解码n 算法解码采取与编码过程相反的步骤算法解码采取与编码过程相反的步骤 把接收到的码字串指向其对应的子区间，得到此子区间对应的符号，即把接收到的码字串指向其对应的子区间，得到此子区间对应的符号，即为解码后的符号。为解码后的符号。 即从码字串中减去已解码符号的子区间的左端点的数值（即从码字串中减去已解码符号的子区间的左端点的数值（累积概率累积概

10、率），）， 并将差值除以该子区间的宽度（并将差值除以该子区间的宽度（概率值概率值），得到新的码字串。），得到新的码字串。n 上述例子上述例子 当收到字码串当收到字码串 (.1010011) (.1010011) 时，其指向子区间时，其指向子区间 .011, .111.011, .111，对应于，对应于 S S3 3，因此，得到第，因此，得到第 1 1 个符号为个符号为 S S3 3。 新码字串：（新码字串：（.1010011 - .011) .1010011 - .011) (.1) = 0.100011 (.1) = 0.100011 ，新码字串仍然，新码字串仍然指向子区间指向子区间 .01

11、1, .111.011, .111，因此，第，因此，第 2 2 个符号仍为个符号仍为 S S3 3。 其它符号依次类推其它符号依次类推n 注意：算术编码中的进位注意：算术编码中的进位 在在 Huffman Huffman 编码中，后续符号产生的码字只是简单地附加到先前的码字编码中，后续符号产生的码字只是简单地附加到先前的码字串之后，并不改变已有的码字串。串之后，并不改变已有的码字串。 在算术编码中，在算术编码中，由于新编码点由于新编码点 C C 表达式中相加运算而产生进位表达式中相加运算而产生进位，从而与，从而与 Huffman Huffman 不同。例如上述的第不同。例如上述的第 3 3 个

12、符号后码字串为个符号后码字串为 .10011.10011，但第，但第 4 4 个个符号后码字串变为符号后码字串变为 .1010011.1010011， 东北石油大学电气信息工程学院东北石油大学电气信息工程学院 张玉波张玉波6二进制算术编码二进制算术编码n 二进制算术编码的输入的二进制算术编码的输入的字符只有两种字符只有两种，如果信源字符集内，如果信源字符集内包含有多个字符，则先将这些字符经过一系列的二进判决，包含有多个字符，则先将这些字符经过一系列的二进判决，变成二进制字符串。变成二进制字符串。n 这两个符号构成的序列的编码与算术编码基本原理相同，仍这两个符号构成的序列的编码与算术编码基本原理

13、相同，仍是不断划分概率子区间的递归过程。是不断划分概率子区间的递归过程。n 在两个输入字符中，出现概率较大的为在两个输入字符中，出现概率较大的为 MPS (MPS (More Probable More Probable SymbolSymbol) )，MPS MPS 的概率为的概率为 P Pe e；出现概率较小的为；出现概率较小的为 LPS (LPS (Less Less Probable SymbolProbable Symbol) )，LPS LPS 的概率为的概率为 Q Qe e，P Pe e=1-Q=1-Qe e。n 编码初始化子区间为编码初始化子区间为 00，11，MPSMPS与与

14、 LPS LPS 分配如图所示：分配如图所示：QePeLPSMPS 东北石油大学电气信息工程学院东北石油大学电气信息工程学院 张玉波张玉波7n 编码时，设置两个专用寄存器（编码时，设置两个专用寄存器（C C，A A） C C 寄存器的值为编码点（指针所指处）寄存器的值为编码点（指针所指处） A A 寄存器的值为子区间的宽度寄存器的值为子区间的宽度 ( (该宽度恰好是已输入符号串的概率该宽度恰好是已输入符号串的概率) )n 初始化时：初始化时：C=0 A=1C=0 A=1n 随着被编码数据源输入，随着被编码数据源输入，C C 和和 A A 的内容按以下编码规则修正：的内容按以下编码规则修正： 当

15、低概率符号当低概率符号 LPS LPS 到来时：到来时：(LPS (LPS 的概率为的概率为 Q Qe e，累积概率为，累积概率为 0 )0 ) C=C A=AQ C=C A=AQe e 当高概率符号当高概率符号MPSMPS到来时：到来时：(LPS (LPS 的概率为的概率为 P Pe e，累积概率为，累积概率为 Q Qe e ) ) C=C + AQ C=C + AQe e A=Ap A=Ape e = A= A（1-Q1-Qe e）二进制算术编码二进制算术编码编码规则编码规则算术编码的基本法则：算术编码的基本法则： 新编码点新编码点 C = C = 原编码点原编码点 C C 原区间原区间

16、A AP Pi i 新区间新区间 A = A = 原区间原区间 A Ap pi i符号符号 S Si i 对应对应的累积概率的累积概率符号符号 S Si i 对对应的概率应的概率QePeLPSMPS 东北石油大学电气信息工程学院东北石油大学电气信息工程学院 张玉波张玉波8 第第 1 1 个符号个符号 1 1 为为 MPSMPS C = C + AQ C = C + AQe e = 0 + 1 = 0 + 1 0.001 = 0.0010.001 = 0.001 A = AP A = APe e = 1 = 1 0.1110.111 = 0.111 = 0.1110.0010.111二进制算术编

17、码二进制算术编码编码举例编码举例例例: : 信源符号序列信源符号序列 11011111 11011111 0 0 为为 LPS QLPS Qe e = 1/8 = = 1/8 =（0.0010.001）b b 1 1 为为 MPS PMPS Pe e = 7/8 = = 7/8 =（0.1110.111）b b初始状态：初始状态：C=0 (C=0 (子区间起始位置子区间起始位置) A=1 ) A=1 （子区间宽度）（子区间宽度） 第第 2 2 个符号个符号 1 1 仍为仍为 MPSMPS C=C+AQ C=C+AQe e = = 0.0010.001 + 0.111 + 0.111 0.001

18、=0.0011110.001=0.001111 A=AP A=APe e= 0.111 = 0.111 0.1110.111 =0.110001 =0.1100010.0011110.11000101 东北石油大学电气信息工程学院东北石油大学电气信息工程学院 张玉波张玉波9 第第 3 3 个符号个符号 0 0 为为 LPS LPS C=C= C=C=0.0011110.001111 A=A Qe A=A Qe =0.110001 =0.110001 0.0010.001 =0.000110001 =0.000110001 继续下去继续下去. . 最后得最后得 C= 0.010001111110

19、111100000001C= 0.010001111110111100000001 A= 0.000011001001000010111111 A= 0.000011001001000010111111 结果结果二进制算术编码二进制算术编码编码举例编码举例0.0011110.000110001头 CA尾头头 0.010001111110111100000001 （C）+ 0.000011001001000010111111 （A）尾尾 0.010101000111111111000000头头 0.0101尾尾传送码字为传送码字为 0101编码输出可以是最后一个编码区编码输出可以是最后一个编码区

20、间中的任意数值，但为了取得最间中的任意数值，但为了取得最好的编码效率，选择的小数应有好的编码效率，选择的小数应有最短的比特长度。最短的比特长度。 东北石油大学电气信息工程学院东北石油大学电气信息工程学院 张玉波张玉波100CA1CACACACACACACA尾尾头头事件事件序号序号判决判决符号符号C=C 符号符号“0“C=C+AQe 符号符号“1“A=AQe 符号符号“0“A=AQe 符号符号“1“子区间分段子区间分段（Pe-7/8；Qe=1/8）110.0010.111210.0011110.11001300.0011110.000110001410.0011111100010.0001010

21、10111510.0100000110111110.000100101100001610.0100010000010110010.000100000110100111710.0100011000100011011110.000011100101110001001810.0100011111101111000000010.000011001001000010111111符号串符号串“11011111” 处于范围：处于范围：头头 0.010001111110111100000001 + 0.000011001001000010111111 尾尾 0.010101000111111111000000

22、 头头 0.0101 尾尾 传送码字传送码字 0101二进制算术编码二进制算术编码编码举例编码举例上述算术编码过程上述算术编码过程 东北石油大学电气信息工程学院东北石油大学电气信息工程学院 张玉波张玉波11n 解码：解码：按按 Qe、Pe 分成两个子区间，判断被解码的码字落在哪个区分成两个子区间，判断被解码的码字落在哪个区间，并赋予对应符号。间，并赋予对应符号。p 设设 c =（0.0101) b 是被解码的值，初始值是被解码的值，初始值 A=1 Qe = 0.001二进制算术编码二进制算术编码解码解码当当 c 落在落在 QeAA 之间，之间，解码符号为解码符号为 D=1 C = C-Qe A

23、 A = A（1-Qe）当当 c 落在落在 0QeA 之间之间，解码符号为解码符号为 D=0 C = C A = Qe A c = 0.0101 落在落在 Qe A -A 之间，解码符号为之间，解码符号为 D = 1 c = c-QeA = 0.0101 - 0.001 = 0.0011 A = A（1-Qe）= 0.111 c= 0.0011 落在落在 Qe A -A 之间，解码符号为之间，解码符号为 D=1 c=c-QeA= 0.0011 -0.000111=0.000101 A=A（1-Qe）= 0.111 0.111=0.110001 c = 0.000101 落在落在 0-QeA 之间之间，解码符号为，解码符号为 D = 0 c = c = 0.0