第三章 无失真信源编码2

1、1信息与编码信息与编码 数学系数学系菏泽学院菏泽学院2主要内容主要内容第第1 1章章 绪论绪论 第第2 2章章 信源及信源熵信源及信源熵 第第3 3章章 无失真信源编码无失真信源编码 第第4 4章章 限失真信源编码限失真信源编码 第第5 5章章 信道编码信道编码 第第6 6章章 密码学密码学 3第第3 3章章 无失真信源编码无失真信源编码3.1 编码的定义编码的定义 3.2 定长编码定理定长编码定理 3.3 变长编码定理变长编码定理3.4 最佳编码最佳编码1.特点：用不同长度的码字序列实现信源符号的编码2.方法：根据信源符号的不同统计特性，用短码表示大概率符号，长码表示小概率符号，从而在保证信

2、息量的同时降低编码后平均每个信源符号所需要的输出符号数，提高编码效率。举例：英文字母“e”出现概率较大，约为0.105.对“fee”进行编码时，若用定长编码每个符号需要5比特，消息序列需用15比特。若用变长编码e只需3比特，消息序列远小于10比特。1.单个符号变长编码定理：若一离散无记忆信源的符号熵为H（X），每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式 1)-(3 1log)(log)(mXHKmXHL当当m m2 2时，单个符号变长编码定理为：时，单个符号变长编码定理为：此时码字平均符号信息量与信源熵相差在此时码字平均符号信息量与信源熵相差

3、在1 1比特内。比特内。 1)()(XHKXH定理给出了无失真信源编码的最短平均定理给出了无失真信源编码的最短平均码长，并指出这个最短的平均码长与信码长，并指出这个最短的平均码长与信源熵源熵H(X)H(X)有关。有关。码字的平均码长不能小于极限值码字的平均码长不能小于极限值H(X)/logmH(X)/logm，否则唯一可译，否则唯一可译码不存在。平均码长小于上界值时，唯一可译码肯定存在，码不存在。平均码长小于上界值时，唯一可译码肯定存在，但并不是说大于这个上界不能够成为唯一可译码，而是因但并不是说大于这个上界不能够成为唯一可译码，而是因为希望平均码长尽可能短。为希望平均码长尽可能短。2.离散平

4、稳无记忆序列变长编码定理 l对于平均符号熵为 的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率 满足不等式 K)()(XHKXHLL其中其中 为任意小正数。为任意小正数。 )(XHL（香农第一定理）（香农第一定理）要实现无失真的信源编码，采用要实现无失真的信源编码，采用m m元码进行编码时，元码进行编码时，每个信源符号的平均码长的极限值就是原始信源的每个信源符号的平均码长的极限值就是原始信源的熵值熵值。当编码的平均码长小于信源的熵值，则唯一。当编码的平均码长小于信源的熵值，则唯一可译码不存在，在译码时必然带来失真或差错。同可译码不存在，在译码时必然带来失真或差错。同时还表明通过对扩

5、展信源进行变长编码，当时还表明通过对扩展信源进行变长编码，当nn时，时，平均码长可以达到这个极限值。平均码长可以达到这个极限值。 l 证明: 设用m进制码元作变长编码，序列长度为L个信源符号，则可以得到平均码字长度 满足下列不等式 LK)()(XLHXHL1log)(log)(mXLHKmXLHLLLLmXHmLKKXHLLLlog)(log)(当当L L足够大时，可使足够大时，可使 ，这就得到了所需结论，这就得到了所需结论Lmlogl 说明: (1) 用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小得多。可得编码效率的下界： LmXHXHKXHLLLlog)()()(

6、2) 例 用二进制，m2，log2m=l，H（X）2.55比特符号，若要求 ，则 %90428. 0/1, 9 . 0/155. 255. 2LL(3) 码的剩余度 KXHL)(11认为编码效率趋于认为编码效率趋于1 1时的编码为理论最佳编码，码时的编码为理论最佳编码，码的剩余度用来衡量各种编码方法与最佳的剩余度用来衡量各种编码方法与最佳编编码的差码的差距距. . 例l 设离散无记忆信源的概率空间为 4/14/321xxPX解解: :其信源熵为其信源熵为 81. 034log434log41)(22XH比特/符号 求求: :编码效率编码效率? ?l (1)定长编码 若用二元定长编码（0，1）来

7、构造一个即时码： 这时平均码长为 =1 二元码符号/信源符号编码效率为(对于离散无记忆信源而言,有HL(X)=H(X) ) 1, 021xx81.0)(KXHLK序列序列序列概率序列概率即时码即时码 x1x1 9/16 00 00 x1x2 x2x1 x2x2 1/16 3/16 3/16 11 10 01对长度为对长度为2 2的信源序列进行定长编码的信源序列进行定长编码：l 这个码的码字平均长度 l 单个符号的平均码长 l 编码效率 信源序列二元码符号/22iiiiiiipKKpKEK信源序列二元码符号/122KK81.02KXHKXHLL=3,4L=3,4时，时，811. 043l (2)

8、变长编码 假定信源序列的长度为L=2,其即时码如表3-3所示。 序列序列序列概率序列概率即时码即时码 x1x1 9/16 0 x1x2 x2x1 x2x2 1/16 3/16 3/16 111 110 10l 这个码的码字平均长度 单个符号的平均码长 编码效率 信源序列二元码符号/162731613163216311692K961.027811.0322信源序列二元码符号/322722KK信源序列长度L定长编码变长编码20.8110.96130.8110.98540.8110.991如果对这一信源采用定长二元码编码，要求编码效率达到如果对这一信源采用定长二元码编码，要求编码效率达到9696时时

9、，允许译码错误概率，允许译码错误概率 。则根据。则根据(3-2-6)(3-2-6)式，式，自信息的方差自信息的方差 所需要的信源序列长度所需要的信源序列长度510212224715. 0)()(log)(iiiXHppX 7221013. 4XL 2.2.变长码变长码,L,L不需太长不需太长, ,则可达到相当高的编码则可达到相当高的编码 效率效率, ,且可以实现无失真编码且可以实现无失真编码, ,随着随着L L增加增加, 越接近越接近1,1,编码后的信息传输率编码后的信息传输率R R也越来越接近也越来越接近 无噪无损二元对称信道的容量无噪无损二元对称信道的容量, ,使信道得到充使信道得到充 分

10、的利用。分的利用。1.1.定长码需要信源序列长定长码需要信源序列长, ,且总存在译码差错。且总存在译码差错。结结 论：论：(1)最佳码定义是什么?凡是能载荷一定的信息量，且码字的平均长度最短，短，可分离的变长码的码字集合都可称为最佳码。(2)最佳编码思想是什么?将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。(3)最佳码的编码主要方法有哪些?香农(Shannon)、费诺(Fano)、哈夫曼(Huffman)编码等。 第四节第四节 最佳编码最佳编码香农编码方法又称最佳变长编码方法。香农编码方法又称最佳变长编码方法。最佳变长编码最佳变长编码: :能载荷一定信息量，且

11、码字的平均长度最短，可分离能载荷一定信息量，且码字的平均长度最短，可分离的变长码的码字集合。的变长码的码字集合。对于某一信源和某一码元集来说，如果有一个唯一可对于某一信源和某一码元集来说，如果有一个唯一可译码的平均码长不大于其他的唯一可译码的平均码长译码的平均码长不大于其他的唯一可译码的平均码长，则称此码为最佳码或称为紧致码。，则称此码为最佳码或称为紧致码。最佳码两个特点：最佳码两个特点：1 1. .概率大的符号对应于短码，概率小的对应于长码，概率大的符号对应于短码，概率小的对应于长码，充分利用了短码；充分利用了短码；2 2. .对于二元最佳码，所对应的缩减信源的两个最小概对于二元最佳码，所对

12、应的缩减信源的两个最小概率的信源符号所对应的码字具有相同的码长，且总率的信源符号所对应的码字具有相同的码长，且总是最后一位不同，保证是即时码。是最后一位不同，保证是即时码。 最佳变长编码的方法主要有：最佳变长编码的方法主要有： 香农（香农（ShannonShannon）、费诺（）、费诺（FanoFano）、）、 哈夫曼（哈夫曼（HuffmanHuffman）编码等。）编码等。1.1.香农第一定理香农第一定理( (无失真信源编码定理）：无失真信源编码定理）： 如果编码后的信源序列信息传输速率不小于信源的熵，则如果编码后的信源序列信息传输速率不小于信源的熵，则可实现无失真编码，反之不存在无失真编码

13、。可实现无失真编码，反之不存在无失真编码。1 1）第一定理指出了平均码长与信源熵之间的关系。）第一定理指出了平均码长与信源熵之间的关系。2 2）可以通过编码使平均码长达到极限值。）可以通过编码使平均码长达到极限值。1)()(iiixIKxI 香农编码方法 3 3）每个码字长度）每个码字长度iK4 4）相应的编码称为香农编码）相应的编码称为香农编码2.2.香农编码步骤香农编码步骤： （1 1）将信源消息符号按其出现的概率大小依次排列）将信源消息符号按其出现的概率大小依次排列 )(.)()(21nxpxpxp （2 2）确定满足下列不等式的整数码长）确定满足下列不等式的整数码长K Ki i 1)(

14、log)(log22 iiixpKxp（3 3）为了编成唯一可译码，计算第）为了编成唯一可译码，计算第i i个消息的累加概率个消息的累加概率 11)(ikkixpP（4 4）将累加概率）将累加概率P Pi i变成二进制数变成二进制数 （5 5）取）取P Pi i二进制数的小数点后二进制数的小数点后K Ki i位为该符号的二进制编码。位为该符号的二进制编码。 例 设信源共7个符号消息，其概率和累加概率如下表所示。信源消息符号xi符号概率p(xi)累加概率Pi-log p(xi)码字长度Ki码字x10.2002.323000 x20.190.22.393001x30.180.392.473011x

15、40.170.572.563100 x50.150.742.743101x60.100.893.3241110 x70.010.996.64711111101step2step2：以排序后：以排序后i=4i=4为例为例3,56. 356. 217. 0log17. 0log44242KKKstep3step3：计算累加概率：计算累加概率P4=0.57step4step4：将累加概率变成二进制数为：将累加概率变成二进制数为：0.1001step5step5：取小数后：取小数后 位位34K得到得到 的编码为的编码为1001004x说明: (1)该信源7个码字都不是延长码，它们都属于即时码。故是唯一

16、可译码。 (2)信源符号的平均码长 码元/符号 14. 3)(71iiiLKxpK码元比特/ 831. 014. 361. 2)(KXHR(3)(3) 平均信息传输率平均信息传输率 169. 0831. 011剩余度剩余度香农编码剩余度较大，实用性不强，但有重要的理论价值。香农编码剩余度较大，实用性不强，但有重要的理论价值。 费诺编码方法 （1 1）将信源消息符号按其出现的概率大小依次排列）将信源消息符号按其出现的概率大小依次排列 )(.)()(21nxpxpxp （2 2）将依次排列的信源符号按概率值分为两大组，使两个组）将依次排列的信源符号按概率值分为两大组，使两个组 的概率之和近于相同，

17、并对各组赋于码元的概率之和近于相同，并对各组赋于码元0 0，1 1。 （3 3）将每一大组的信源符号进一步再分成两组，重复第）将每一大组的信源符号进一步再分成两组，重复第 (2)(2)步步 。（4 4）如此重复，直到每个组只剩下一个信源符号为止。）如此重复，直到每个组只剩下一个信源符号为止。 （5 5）信源符号所对应的码字即为费诺码。）信源符号所对应的码字即为费诺码。 消息符号各个消息概率p(xi)第一次分组第二次分组第三次分组第四次分组二元码字码长Kix10.2000002x20.19100103x30.1810113x40.1710102x50.15101103x60.101011104x

18、70.01111114A01010101110000010011110101110 1111l 费诺码的平均码长 信息传输速率 码元比特/ 953. 074. 261. 2)(KXHR符号码元 / 74. 2)(71iiiKxpK047. 0953. 011剩余度剩余度费诺编码剩余度较小，编码效率较高费诺编码剩余度较小，编码效率较高哈夫曼编码哈夫曼编码编码方法编码方法19521952年，哈夫曼提出了一种构造最佳码的方法。所得年，哈夫曼提出了一种构造最佳码的方法。所得的码字是即时码，而且在所有唯一可译码中，它的平的码字是即时码，而且在所有唯一可译码中，它的平均码长最短，是一种最佳变长码。均码长最

19、短，是一种最佳变长码。 哈夫曼（Huffman）码 （1 1）将信源消息符号按其出现的概率大小依次排列）将信源消息符号按其出现的概率大小依次排列 )(.)()(21nxpxpxp （2 2）取两个概率最小的信源符号分别配以）取两个概率最小的信源符号分别配以0 0和和1 1两码元，将这两两码元，将这两个概率相加作为一个新信源的概率，与未分配的信源符号按概个概率相加作为一个新信源的概率，与未分配的信源符号按概率重新进行排队率重新进行排队 （3 3）对重新排队后的队伍重复步骤（）对重新排队后的队伍重复步骤（2 2） （4 4）不断重复（）不断重复（2 2）（）（3 3），直到最后两个信源符号配以），

20、直到最后两个信源符号配以0 0和和1 1 （5 5）从最后一级开始，）从最后一级开始，向前返回向前返回得到的各个信源符号所对得到的各个信源符号所对应的码元序列，就是相应的码字。应的码元序列，就是相应的码字。 信源符号xi概率p(xi)编码过程码字码长x10.20102x20.19112x30.180003x40.170013x50.150103x60.1001104x70.0101114 40.110.200.190.180.170.15010.260.200.190.180.17010.350.260.200.19010.390.350.26010.610.3901说明:哈夫曼码的平均码长为

21、 信息传输速率 符号码元 / 72. 2)(71iiiKxpK码元比特/ 9596. 072. 261. 2)(KXHR与香农、费诺编码相比，传输所需的平均码字长度更短，与香农、费诺编码相比，传输所需的平均码字长度更短，平均传输速率更高。平均传输速率更高。)(香农编码费诺编码哈夫曼编码平均码长（码元/符号）3.142.742.72平均信息传输速率（比特/码元）0.8310.9530.9596问题:为何哈夫曼编码方法得到的码并非是唯一的? (1)每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。问题:为何哈夫曼编码方法得到的

22、码并非是唯一的? (2)对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。例 设有离散无记忆信源1 . 01 . 02 . 02 . 04 . 054321aaaaaPX0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.2 0.10.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.20.101010101010

23、10101信源符号ai概率p(ai)码字Wi1码长Ki1码字Wi2码长Ki2a10.411002a20.2012102a30.20003112a40.1001040103a50.10011401132 . 2)(71iiiKapK 码元码元/符号符号 965. 0)(KXHqiiiilKkapKkE1222)(36. 121l16. 022l 码方差码方差：用于衡量码字长度相比于平均长度的波动情况，码：用于衡量码字长度相比于平均长度的波动情况，码方差小的码字需要较少的存储设备，质量好。方差小的码字需要较少的存储设备，质量好。第二种方差小些。第二种方差小些。即：将新合并的等概率消息排即：将新合并

24、的等概率消息排列到上支路，将有利于缩短码长的方差，即编出列到上支路，将有利于缩短码长的方差，即编出的码更接近于等长码。所以说第二种码的质量优的码更接近于等长码。所以说第二种码的质量优于第一种码的质量。于第一种码的质量。l哈夫曼码是用概率匹配方法进行信源编码。l哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；l缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。工程上注意的三个问题上面讨论了哈夫曼编码的方法和一些性质，在实际上面讨论了哈夫曼编码的方法和一些性质，在实际问题中真正应用哈夫曼编码方法时，还需进一步研问题中真正应用哈夫曼编码方法时

25、，还需进一步研究有关误差扩散，速率匹配和概率匹配等问题。究有关误差扩散，速率匹配和概率匹配等问题。哈夫曼码是一类无失真信源最佳变长码哈夫曼码是一类无失真信源最佳变长码, ,在研究这在研究这类无失真信源编码时认为信道传输是理想的类无失真信源编码时认为信道传输是理想的, ,是不是不产生误差的产生误差的, ,然而实际信道中总是存在噪声然而实际信道中总是存在噪声, ,噪声噪声引入必将要破坏变长码的结构引入必将要破坏变长码的结构, ,同时变长码是不加同时变长码是不加同步的码同步的码, ,无法自动清洗所产生的影响无法自动清洗所产生的影响, ,所以必然所以必然要产生误差的扩散要产生误差的扩散, ,就是说噪声

26、所影响的不仅是被就是说噪声所影响的不仅是被干扰的码元干扰的码元, ,而是一直扩散下去而是一直扩散下去, ,影响后面一系列影响后面一系列码元码元, ,以至在低信噪比下无法正常工作。以至在低信噪比下无法正常工作。1 1、误差扩散、误差扩散目前对这类误差扩散还没有特别有效的克服方法目前对这类误差扩散还没有特别有效的克服方法. .在工程上在工程上, ,一般哈夫曼码能适合于高信噪比的优一般哈夫曼码能适合于高信噪比的优质信道质信道, ,如误码率如误码率1010-6-6. .同时工程上还常常采用同时工程上还常常采用定期清洗方法定期清洗方法, ,比如在文件和报纸传真中采用按比如在文件和报纸传真中采用按行清洗的

27、方式行清洗的方式, ,以牺牲编码效率来达到限制误差以牺牲编码效率来达到限制误差扩散的目的扩散的目的. .另一种方法是加检错纠错码。另一种方法是加检错纠错码。由于绝大多数信源其消息是不等概率的，因而编成由于绝大多数信源其消息是不等概率的，因而编成的变长码长度也是不相等的的变长码长度也是不相等的, ,这必然导致信源输出这必然导致信源输出速率的变化速率的变化, ,而在实际信道中传送的信息率是固定而在实际信道中传送的信息率是固定不变的不变的, ,就是说信源给出的是变速的就是说信源给出的是变速的, ,而信道传送则而信道传送则是恒速的是恒速的, ,因而信源与信道之间必然存在一个速率因而信源与信道之间必然存

28、在一个速率匹配问题。匹配问题。2 2、速率匹配、速率匹配在工程上一般采用缓冲存储器方法，这个缓冲器在工程上一般采用缓冲存储器方法，这个缓冲器起到类似水库的作用，变速输入，恒速输出，缓起到类似水库的作用，变速输入，恒速输出，缓冲器容量的选择与信源统计特性，编码方法，输冲器容量的选择与信源统计特性，编码方法，输出速率相关，容量大浪费设备，小达不到效果。出速率相关，容量大浪费设备，小达不到效果。NC16. 6经概率运算得存储器容量经概率运算得存储器容量 N N表示在表示在T T秒内秒内N N个信源符号输出个信源符号输出, ,为单为单符号方差。符号方差。变长码本身就是与信源统计特性相匹配的无失真信变长

29、码本身就是与信源统计特性相匹配的无失真信源编码源编码, ,因此信源统计特性的变化对变长码影响很因此信源统计特性的变化对变长码影响很大大, ,主要体现在：主要体现在： 3 3、信源统计特性匹配、信源统计特性匹配(1)(1)与信源消息种类多少的关系与信源消息种类多少的关系; ;一般变长码更适合一般变长码更适合于大的消息集于大的消息集, ,而不适合小且概率分布相差很大的而不适合小且概率分布相差很大的集合。集合。（2 2）变长码是在信源概率特性已知的情况下实现统）变长码是在信源概率特性已知的情况下实现统计匹配的。计匹配的。三、三、D D进制进制Huffman Huffman 算法算法前面介绍的均为二进

30、制哈夫曼码前面介绍的均为二进制哈夫曼码, ,很容易推广到很容易推广到m m进进制的情况制的情况, ,只是编码过程中过程缩减信源时只是编码过程中过程缩减信源时, ,每次都每次都是将是将m m个概率最小的符号合并个概率最小的符号合并, ,并分别用、并分别用、1 1、m-1m-1码符号表示码符号表示, ,为了充分利用短码为了充分利用短码, ,使哈夫曼使哈夫曼的平均码长最短的平均码长最短, ,必须使最后一个缩减源有必须使最后一个缩减源有m m个信源个信源符号符号. .故对故对m m元哈夫曼编码信源符号个数元哈夫曼编码信源符号个数q q必须满足必须满足q=(m-q=(m-1)1)+m ,+m ,表示信源

31、缩减的次数表示信源缩减的次数, ,如如m m的二元码的二元码, ,信源的符号个数信源的符号个数q q必须满足必须满足 q=q=+2+2若不满足若不满足, ,用虚设方法用虚设方法, ,增补一些概率为信源符号满增补一些概率为信源符号满足上式足上式, ,这样得到的这样得到的m m元哈夫曼码一定是紧致码。元哈夫曼码一定是紧致码。设离散无记忆信源码符号集设离散无记忆信源码符号集 X=(0X=(0、1 1、2)2)【例例4.3-64.3-6】设无记忆信源设无记忆信源5 . 05 . 05 . 05 . 01 . 01 . 02 . 04 . 087654321ssssssssPS试构造一种三进制哈夫曼码信

32、源试构造一种三进制哈夫曼码信源, ,0S930110.05S830100.05S72220.05S62210.05S52200.1S42020.1S32000.2S2110.4S1KiWi编码过程编码过程P(si)信源符号信源符号0.20.10.10.10.050.050 120 120.40.20.20.10.10.40.40.20120121.0S9是增补是增补,令其概率为令其概率为0,0.4q=(m-1)+miqiikspK1)(7 . 12305. 02205. 021 . 021 . 022 . 014 . 0平均码长：平均码长：A012012012000100111200221 2

33、2码树码树: :注注: :编码效率、编码信息率、编码后信息传输率之间关系编码效率、编码信息率、编码后信息传输率之间关系编码信息率编码信息率(信源符号的平均码长信源符号的平均码长)：mLKKLlogmLKxHKxHLlog)()(LKLKLLxHmxHmKxHmmR)(log)(log)(loglog编码效率：编码效率：编码后信息传输率：编码后信息传输率：码字平均长码字平均长RKxHL)(二进制单个符号时二进制单个符号时L信源符号长度信源符号长度RmKxHLlog)(三进制单个符号时三进制单个符号时n哈夫曼树1）一种最优二叉树，它的编码也是一种最优编码。2）在哈夫曼树中，规定往左编码为0，往右编码为1，则得到叶子结点编码为从根结点到叶子结点中所有路径中0和1顺序排列。（右图分别为编码1、2的哈夫曼树） n最