无失真信源编码方法

1、第第3章章 无失真信源编码方法无失真信源编码方法 3.1 霍夫曼编码及其他编码方法霍夫曼编码及其他编码方法要求掌握的主要内容n熟练掌握霍夫曼(Huffman)编码方法n熟练掌握计算平均码长与编码效率的方法n深刻理解霍夫曼编码的适用条件，并掌握用N次扩展信源实现霍夫曼编码的方法n无失真的信源编码定理，既是存在性定理也是构造性定理，即它给出了构造信源编码的原理性方法，这样构造出的码的平均码长与信源统计特性相匹配。为此，香农、费诺、霍夫曼都各自按上述思路设计出不同的具体编码方法，其中霍夫曼给出的方法最好n 霍夫曼码是一种构造最佳信源编码的方法，它是一种逐个符号的编码方法。所得的码字是异前缀码的变长码

2、，其平均码长最短，是最佳变长码。n二元霍夫曼码编码方法 (1)将n个信源U的各个符号ui按概率分布p（ui）以递减次序排列起来。 (2)将两个概率最小的信源符号合并成一个新符号，新符号的值概率值为两个信源符号概率值的和，从而得到只包含n1个符号的缩减信源 3.1.1 霍夫曼编码(3)把缩减信源U1的符号仍按概率以递减次序排列，然后将其中两个概率最小的符号合并成一个符号，这样又形成了 n2个符号的缩减信源U2。(4)重复(2)(3)两步骤，直至信源最后只剩下个符号为止。(5)将每次合并的两个信源符号分别用0和1码符号表示(6)从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，

3、即得各信源符号对应的码字。 3.1.1 霍夫曼编码12340.50.250.1250.125UuuuuP对应的霍夫曼编码如图所示 例例3.1 离散无记忆信源离散无记忆信源符 号概 率缩减后符号概率码 字u1u2u3u40.50.250.1250.1250.50.25010.25010.50.5011.0010110111码 长1233 3.1.1 霍夫曼编码信源熵: ( )( )( )1.75( )1.75( )100%iiiiiiH Up u Ibp ubitLp u lbitH UL 平均码长： 编码效率： 3.1.1 霍夫曼编码123450.40.20.20.1 0.1UuuuuuP用两

4、种方法进行霍夫曼编码。法a： 符 号概 率码 字u1u2u3u40.40.20.20.1u50.1100.40.20.20.20.40.40.210100.60.4101.0001011010011码 长22233(a)缩减后符号概率例3.2 离散无记忆信源 3.1.1 霍夫曼编码n例3.2 离散无记忆信源 123450.40.20.20.1 0.1UuuuuuP用两种方法进行霍夫曼编码。法b： 概 率码 字u1u2u3u40.40.20.20.1u50.1100.40.20.20.20.40.40.210100.60.4101.010100000100011码 长12344(b)符 号 3.

5、1.1 霍夫曼编码 例3.2 对应的码树 u11(a)(b)00101u4u501u2u310u110u210u310u4u5 3.1.1 霍夫曼编码 这两种霍夫曼编码的平均码长和编码效率是相同的：5151( )2.2( )( )( )2.12( )96.3%iiiiiiLp u lbitH Up u Ibp ubitH UL 信源熵为： 编码效率为： 平均码长为： 3.1.1 霍夫曼编码n两种码的均方差2分别为5221152221( )()0.16( )()1.36iiiiiip ulLp ulL(方法(a)方差)(方法(b)方差)方法（a）要优于方法（b）原因在于编码原则不同： (a）：把

6、合并后的概率总是放在其他相同概率的信源符号之上（b）：把合并后的概率放在其他相同概率的信源符号之下 3.1.1 霍夫曼编码n霍夫曼编码得到的码字不唯一，但这些码字只是具体结构不同，其码长和平均码长是相同的n对等概率消息编码时，将新合并的消息排列到上支路较好编出的码方差小，更接近等长码可使合并的元素重复编码次数减少，使短码得到充分利用。 3.1.1 霍夫曼编码练习练习1 对以下信源进行哈夫曼编码对以下信源进行哈夫曼编码 信源符号信源符号ai概率概率p(ai)码字码字Wi码长码长Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.100110

7、4a70.01011140.200.190.180.170.150.100.0101a1 10a2 11a3 000a4 001a7 0111a5 010a6 01100.200.190.180.170.150.110.260.200.190.180.170.350.260.200.190.390.350.260.610.3901010101011.0 码元码元/符号符号 bit/符号符号 71()2.72iiiLp a l()2.610.962.72H XL二元霍夫曼码的编码方法可以推广到m元编码中。不同的只是每次把概率最小的m个符号合并成一个新的信源符号，并分别用0，1，（m1）等码元表示

8、。为了使短码得到充分利用，使平均码长最短，必须使最后一步的缩减信源有m个信源符号。因此对于m元编码，信源U符号个数n必须满足：n n（m1）Qm 3.1.2 m元霍夫曼编码式中：式中： n信源符号个数；信源符号个数； m进制数（码元数）；进制数（码元数）； Q缩减次数。缩减次数。对于二元码，总能找到一个Q，满足上式。但对于m元码，n为任意正整数时不一定能找到一个Q满足上式，此时，可以人为地增加一些概率为零的符号，以满足式子。然后取概率最小的m个符号合并成一个新符号（结点），并把这些符号的概率相加作为该结点的概率，重新按概率由大到小顺序排队，再取概率最小的m个符号（结点）合并；如此下去直至树根。

9、n编码步骤： (1) 验证所给n是否满足式子：n（m1）Qm，若不满足，人为增加一些概率为零的符号，使最后一步有m个信源符号 (2) 取概率最小的m个符号合并成一个新结点，并分别用0，1，（m）给各分支赋值,把这些符号的概率相加作为该新结点的概率； (3) 将新结点和剩下结点重新排队，重复（2），如此下去直至树根 (4) 取树根到叶子（信源符号对应结点）的各树枝上的赋值，得到各符号码字 3.1.2 m元霍夫曼编码n例3.3 已知离散无记忆信源（1）分别求信源输出进行其三元和四元霍夫曼码编码（2）分别求出两种编码的平均码长和编码效率123450.40.30.20.05 0.05UuuuuuP 3

10、.1.2 m元霍夫曼编码符 号概 率码 字u1u2u3u40.40.30.20.0501012021u50.0520.40.30.301222码 长11222（1）三元霍夫曼编码： 3.1.2 m元霍夫曼编码（1）四元霍夫曼编码：符 号概 率码 字u1u2u3u40.400.300.200.050101230u50.0520.400.300.2001231码 长11122u6u70.000.0030.103323322 3.1.2 m元霍夫曼编码( )( )( )1.95iiiH Up u Ib ubit 两种编码的平均码长分别为 34( )(0.40.3) 12(0.20.050.05)1.

11、3( )(0.30.20.4) 12(0.20.050.05)1.1iiiiiiLp u lbitLp u lbit （2）：34( )1.59(3)94.7%31.3 1.58( )1.95(4)88.6%41.1 2H ULIbH ULIb 两种编码的编码效率分别为 信息熵： 3.1.2 m元霍夫曼编码我们看到，从二元码到三元码、四元码，编码效率越来越低。如果编制五元码，则编码过程不过是换一套表示符号，不起任何压缩作用，等于没有编码。结论：霍夫曼编码只适用于信源符号数目霍夫曼编码只适用于信源符号数目N比码比码元符号元符号m 数目大很多的情况数目大很多的情况。 3.1.2 m元霍夫曼编码n霍

12、夫曼编码是最佳码，它的平均码长最短，n霍夫曼编码的特点之一是高频先见。从而保证了概率大的符号对应于短码，概率小的符号对应于长码。n是现代编码的基础，是汉字编码的简码设计原则，也是动态高频优选的原则。n是即时码，符号集中的任一字符都不是其他码字的前缀，可直接用于译码。，所以霍夫曼码是即时码。 3.1.2 m元霍夫曼编码n编码步骤：(1)将信源消息（符号）按其出现的概率由大到小依次排列；(2)将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组分别赋予一个二进制码元“0”和“1”。(3)将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又分别赋予一

13、个二进制符号“0”和“1”。(4)如此重复，直至每个组只剩下一个信源符号为止(5)信源符号所对应的码字即为费诺码。 3.1.3 费诺码n例3.4 离散无记忆信源12340.50.250.1250.125UuuuuP求出它的费诺编码并计算其平均码长和编码效率解： 符 号概 率码 字u1u2u3u40.50.250.1250.125010110111码 长1233010101 3.1.3 费诺码编码效率： ( )100%H UL( )( )( )1.75( )1.75iiiiiiH Up u Ibp ubitLp u lbit 平均码长： 信源熵： 3.1.3 费诺码 费诺编码图 符 号概 率码

14、字u1u3u4u50.320.220.180.16000110110u60.081110码 长22234u20.041111400110101011234560.320.040.220.180.160.08UuuuuuuP例3.5 求的费诺编码 ( )( )( )2.35( )2.4( )98%iiiiiiH Up u Ibp ubitLp u lbitH UL 信源熵： 平均码长： 编码效率： 3.1.3 费诺码n 例3.6 求 的费诺编码123450.40.30.20.050.05UuuuuuP符 号概 率码 字u1u2u3u40.40.30.20.0500101101110u50.051

15、111码 长1234401010101 3.1.3 费诺码n费诺码考虑了信源的统计特性，使经常出现的信源符号能对应码长短的码字，是一种相当好的编码方法n不是最佳码，原因在于当信源符号较多，并有一些符号概率分布很接近时，分两大组的组合方法就很多，可能某种分配结果，会出现后面小组的“概率和”相差较远，因而使平均码长增加，所以费诺码不一定是最佳码。 n编码方法实际上是构造码树的一种方法，所以是即时码 3.1.3 费诺码3.1.4 二元霍夫编码的扩展n既然m=r=2时霍夫曼编码不起任何压缩作用，那么二元信源如何编成二元码字呢？n可以采用N维扩展信源来进行编码。所谓N维扩展信源指以把N个二元符号的符号串

16、当作一个“符号”看待的信源，即合并信源nN维扩展信源中共有2N个不同的“符号”，由于2N r，霍夫曼编码就能发挥威力,大大提高编码效率。 例例66二元无记忆信源发出二元无记忆信源发出a、b两个符号，概率分别两个符号，概率分别为为0.7和和0.3，试对二次、试对二次、三次扩展信源三次扩展信源进行编码。进行编码。解：根据解：根据 p(x1x2x3)=p(x1)p(x2)p(x3) 不难求出不难求出三次扩三次扩展信源的概率空间为：展信源的概率空间为： 按按8 8个符号的概率排队，进行霍夫曼编码个符号的概率排队，进行霍夫曼编码: : 027. 0063. 0063. 0063. 0147. 0147.

17、 0147. 0343. 0)(33bbbbbabababbbaaabaaabaaaXpX3.1.4 二元霍夫编码的扩展 bbb 0.0270.027 bba 0.0630.063 bab 0.0630.063 abb 0.0630.063 (0.09)(0.09)(0.126)(0.126) baa 0.1470.147 aba 0.1470.147 aab 0.1470.147 (0.216)(0.216)(0.294)(0.294)aaa 0.3430.343 (0.363)(0.363) ( (0.637)0.637) root 1 1 0 0 1 1 0 0 1 1 0 0 1 1

18、0 0 1 1 0 0 1 1 0 0 1 1 0 0 1011 1011 1010 1010 1001 1001 1000 1000 011 011 010 010 11 11 00 00 码字码字 4 4 4 4 4 4 4 4 3 3 3 3 2 2 2 2码长码长符号符号 bbb bba bab abb baa aba aab aaa概率概率 0.027 0.063 0.063 0.063 0.147 0.147 0.147 0.343 码字码字 00 11 010 011 1000 1001 1010 101100 11 010 011 1000 1001 1010 1011 码长码

19、长 2 2 3 3 4 4 4 42 2 3 3 4 4 4 4 码字平均长度：码字平均长度：L LN N=2.726=2.726； 信源符号平均编码长度：信源符号平均编码长度：2.726/3=0.9092.726/3=0.909编码效率：编码效率：=0.881/0.909=96.9=0.881/0.909=96.9%信息熵：信息熵：H(X)=-0.3=-0.3log0.3-0.70.3-0.7log0.7=0.8810.7=0.881027. 0063. 0063. 0063. 0147. 0147. 0147. 0343. 0)(33bbbbbabababbbaaabaaabaaaXpX3

20、.1.4 二元霍夫编码的扩展练习n未扩展信源编码的编码( )( )( )0.70.70.30.30.881( )0.7 10.3 11iiiiiiH Up u Ibp uIbIbbitLp u lbit 平均码长: ( )0.88188.1%1H UL编码效率: 平均码长： 1( )21(0.49 10.21 20.21 30.093)20.91iiLp u lbit 编码效率: ( )0.8896.2%0.91H UL练习二次扩展编码小结小结v 霍夫曼编码方法霍夫曼编码方法 v 计算平均码长和编码效率：计算平均码长和编码效率：v霍夫曼编码的扩展霍夫曼编码的扩展 多元码的霍夫曼编码多元码的霍夫

21、曼编码 扩展信源的二元编码扩展信源的二元编码课后复习题n作业题： 教材P63 习题3-1，3-2 和3-4n实践题： 试编程实现英文字母的霍夫曼编码 3.2 算术编码和游程编码第第3 3章章 无失真信源编码无失真信源编码n深刻理解算术编码原理n熟练掌握作图与公式相结合计算积累概率的方法n熟练掌握算术编码方法n深刻理解游程编码原理和意义要求掌握的内容霍夫曼编码的原理方法霍夫曼编码的适用条件信息熵的计算公式：温旧引新平均码长的计算公式：1()( )log ( )miiiH Xp xp x 1mi iilpln用霍夫曼编码方法对小消息信源进行编码，要实现统计匹配，提高编码效率，必须扩展信源，即由一维

22、扩展至多维进行霍夫曼编码时，才能使平均码长接近信源的熵,合并的信源符号越多，编码效率越高，但扩展阶次越高，系统延时越长、存储量越大、设备也越复杂，合并的符号数达到一定值时，再增加符号数所提高的效率将不显著，所以工程上只能在效率与经济性之间作合理的选择。 二元序列用二元码编码,等于没有编码,也无压缩而言,且编码效率也不高.主要内容n积累概率的递推公式n算术编码原理n算术编码方法n游程编码3.2 算术编码算术编码 n从结构上分，编码有两种方式：（1）分组编码 (块码)：将信源消息序列分成长度为N的字符组，按组进行编码的方式。（2）序列编码 (流码)：直接为整个信源消息序列寻找编码序列的方式。n等长

23、码和变长码的编码，都是“块码”，本节讨论的算术编码和游程编码属于“流码”，直接把信源发出的非等概序列变换成等概序列。n由于等概序列单位码元信息荷载量大，携带同样多的信息需要的代码少，编码后序列长度就会变短。 1212()()()nnuuuUp up up uP定义信源符号的积累概率： 1111()( ), ,kkiikniF up uu uu uu 设信源： 3.2.1 积累概率的递推公式积累概率的递推公式 可得：F(uk)0,1) F(u1) =0， F(u2) p(u1)， F(u3) p(u1)+ p(u2)， 且 p(ui) = F(ui+1)- F(ui)1111()( ), ,kk

24、iikniF up uu uu uu（311） 3.2.1 积累概率的递推公式积累概率的递推公式 1.信源符号的积累概率信源符号的积累概率nF(ui)和 F(ui+1) 都是小于1的正数，可用0，1）区间的两个点来表示，p(ui)就是这两点间小区间的长度n不同的符号对应不同的小区间，这些小区间互不重叠，小区间内的任意的一个点可作为该符号的码字3.2.1 积累概率的递推公式积累概率的递推公式 1.信源符号的积累概率信源符号的积累概率 则信源序列的积累概率的递推公式： F(Sur)=F(S)+p(S)F(ur) p(Sur)=p(S)p(ur)3.2.1 积累概率的递推公式积累概率的递推公式 2.

25、信源序列的积累概率的递推公式信源序列的积累概率的递推公式设独立信源序列S=s1s2sksnu1,u2,um， k1,2，n(3-12)F(Sur)新序列Sur的积累概率；P(S)信源序列S 的概率；F(ur)信源符号ur的积累概率；P(Sur)新序列Sur的概率P(ur)信源符号ur的概率n信源序列的积累概率F(S)与信源符号的积累概率一样，可用0，1）区间内的一个点来表示 积累概率F(S)将区间0，1）分成许多不同的小区间，它们互不重叠，序列S的概率p(S)就是两点间小区间的长度。小区间内的一个点可用来表示序列的概率. 以上就是算术编码的基本思想 3.2.1 积累概率的递推公式积累概率的递推

26、公式 2.信源序列的积累概率的递推公式信源序列的积累概率的递推公式3.2.2算术编码原理算术编码原理n算术编码原理：把信源序列的积累概率映射到0，1)区间上，使每个序列对应该区间内的一点，这些点把区间0，1)分成许多不同的小区间，这些小区间的长度等于对应序列的概率，在小区间内取一个浮点小数，使其长度与该序列的概率相匹配，因而达到高效编码的目的。 n算术编码的关键：计算信源序列对应的小区间n小区间划分的递推公式： 小区间左、右端点的递推公式： low(Sur)=low(S)+range(S)low(ur) (3-13) high(Sur)=low(S)+range(S)high(ur) low-

27、小区间左端点 high-右端点的值 range-小区间的长度3.2.2算术编码原理算术编码原理3.2.2算术编码原理算术编码原理 计算小区间端点值的步骤： (1) 给出信源符号对应的区间； (2) 初始时设S （ 代表空集），low( )0，high( )1，range( )1； (3) 输入信源序列的一个符号ur，根据公式（313）计算序列Sur的左右端点值。依次下去，直至全部信源序列对应的区间被确定为止。 n例1 设信源0.50.250.1250.125UabcdP求信源序列S=abda对应的小区间。 解： 各个信源符号对应的小区间如下表所示。 3.2.2算术编码原理算术编码原理 信源序列

28、S=abda对应的小区间的左、右端点的值 的计算过程如下：n设low( )0，high( )1，range( )1n输入信源序列的第1个符号a： low( a)low( )range( )low(a) 0100.000 high( a)low( )range( )high(a) 010.50.5003.2.2算术编码原理算术编码原理输入信源序列的第2个符号b： low(ab)low(a)range(a)low(b) 0.000.50.50.250 high(ab)low(a)range(a)high(b) 0.000.50.750.375输入信源序列的第3个符号d： low（abd）low(a

29、b)range(ab)low(d) 0.250.8750.1250.359375 high（abd）low(ab)range(ab)high(d) 0.250.12510.3753.2.2算术编码原理算术编码原理n输入信源序列的第4个符号a： low（abda）low（abd）range（abd）low（a） 0.359375 high（abda）low（abd）range（abd）high（a) =0.36718753.2.2算术编码原理算术编码原理例1 信源序列对应区间的划分abcd10.8750.750.500aaabacad0.50.3750.250abaabbabcabd0.3750

30、.250.359 375abdaabdbabdcabdd0.3750.359 3750.367 187 5取小区间内的一个点作为对应序列的编码，可取0.359375作为信源序列S=abda的编码n算术编码的译码步骤：(1) 判断码字落在哪个符号区间，翻译出1个符号 (2) 将码字减去刚翻译出的符号的左端点值；(3) 用刚翻译出的符号对应的区间的长度去除步骤2 的结果，判断此值落在哪个符号区间，翻译出一个新符号；(4) 重复步骤(2)、(3)直至全部信源序列被翻译完为止。3.2.2算术编码原理算术编码原理n 码字0.359375的译码过程：(1) 码字0.359375在0，0.5）之间,则第1个

31、符号为a；(2) 用符号a对应区间的长度0.5去除码字与符号a的左端点值的差得0.71875,它 0.5,0.75,则第2个符号为b；(3) 用符号b对应区间的长度0.25去除码字0.71875与符号b的左端点值的差得0.875,于是翻译出第3个符号为d；(4) 用符号d对应区间的长度0.125去除码字0.875与符号d的左端点值的差得0,落在0，0.5）之间,第4个符号为a, 所以码字0.359375对应的序列为abda,译码正确。 3.2.2算术编码原理算术编码原理n例2 信源0.10.10.30.10.10.3UabcdefP求信源序列S=efbfcafdcc对应的区间端点值。解：3.2

32、.2算术编码原理算术编码原理信源符号区间划分如下表：信源序列对应的区间端点值如下表： 3.2.2算术编码原理算术编码原理n不同的信源系列对应不同的小区间，可取小区间内的一点作为该序列的码字n码字长度选取的原则主要是与该序列的概率匹配，可根据下式来选择：n取信源序列码字的前L位，若后面有尾数就进位到第L位,这样得到的数就是序列的编码C。例如：p（S）3/16，序列S左端点的值0.011011,则L3,得序列S的码字C100。21log( )Lp S 可以证明：当信源序列S的符号序列很长时，算术编码的平均码长接近信源的熵值。因此算术编码是熵编码,这样构成的码字，当序列很长时，编码效率是很高的，且已

33、达到概率匹配。 3.2.2算术编码原理算术编码原理3.2.3算术编码方法算术编码方法用序列积累概率的递推公式进行算术编码的步骤用序列积累概率的递推公式进行算术编码的步骤：(1)根据式(3-11)计算信源符号的积累概率；(2)初始时设S ，F（ ）0，p（ ）1 ；(3)根据式(3-12)计算序列的积累概率F(Sui)和序列的概率p(Sui)；(4)根据式(3-14)计算码长L；(5)将F(S)写成二进制数的形式,取其前L位作为序列S的码字，若后面有尾数就进位到第L位。 1log( )aLp Sn例3 设二元独立信源 010.250.75UP求信源序列S=1010的算术编码。 3.2.3算术编码

34、方法算术编码方法数据的计算： F ( )0,p( )1 输入信源序列的第1个符号1： F( 1)F( )p( )F(1)010.250.01 p( 1)p( )p(1)0.11输入信源序列的第2个符号0： F(10)F(1)p(1)F(0)0.010.750.01 p(10)p(1)p(0)0.450.250.1875=（0.0011)2注：分数如何化成二进制数？（小数部分乘2取整，从上往下写出）3.2.3算术编码方法算术编码方法信源序列1010算术编码的相关数据如下表所示。 3.2.3算术编码方法算术编码方法 信源序列1010的算术编码图解 F(0)F(1)p(0)p(1)00.010.11

35、F(10)F(11)p(10)p(11)0.010.0111F(100)F(101)p(100)p(101)0.010 011F(1010)F(1011)p(1010)p(1011)0.010 0110.010 100.01110.01110.010.0113.2.3算术编码方法算术编码方法n例4 已知信源 0.50.250.1250.125UabcdP求信源序列S=abda的算术编码。 解：信源符号的积累概率表为：3.2.3算术编码方法算术编码方法信源序列S=abda的算术编码为： 3.2.3算术编码方法算术编码方法 信源序列abda算术编码图解 p(abdd)p(abdc)p(abc)p(

36、abd)p(a)p(b)0.100.0110.0100.0110.010.0101110.0110.0101110.0101111F(a)F(b)F(c)F(d)p(c)p(d)F(aa)p(aa)p(ab)p(ac)p(ad)F(ab)F(ac)F(ad)F(aba)p(aba)F(abb)p(abb)F(abc)F(abd)10.1F(abda)F(abdb)F(abdc)F(abdd)p(abda)p(abdb)n算术编码的编、译码方法有许多优点，尤其它的渐近最佳性。n存在的问题： 1.大量乘法的存在造成运算量大，难以做到实时编译码，特别是积累概率转换成二进制数要求精度高时 2. 计算精度问题：随着递推运算的延续，F(S)和p(S)的小数位数也将逐步增加，若不能随时输出和加以截断，运算器将难于容纳,但有截断必然降低精度,而精度不够会影响编、译码的正确性。3.2.3算术编码方法算术编码方法n信源序列积累概率的递推公式为 F (Sur)F(S)p(S)F(ur) p(Sur)p(S)p(ur)n则二元信源序列积累概率的递推公式为 F(S0) F(S) p(S)F(0) F(S) F(S1) F(S) p(S)F(1) p(S1)p(S)p(1) p(S0)p(S)p(