第八章 无失真信源编码

第八章无失真的信源编码8.1霍夫曼(Huffman)码8.2费诺(Fano)码8.3香农—费诺—埃利斯码8.1霍夫曼(Huffman)码8.1.1二元霍夫曼码8.1.2r元霍夫曼码8.1.3Huffman码的最佳性香农编码：1、码长),,2,1()(1logqisPlii2、按照算出的码长、用树图法编出相应的即时码。一般香农编码的不是最短的，即不是最佳码。L例8.1用香农编码方法编成二元惟一可译码.000010111111.01.02.02.04.0)(54321isPsssssS3.33.33.23.232.1)(1logisP44332il1111111001101000编码)/(8.22.044.034.02信源符号码元L758.0)(122.2)(LSHSH1log)(log)(rSHLrSH8.1.1二元霍夫曼码1、二元Huffman码的编码步骤(1)将q个信源符号按概率分布由大到小的顺序排列起来：qpppp321(2)将码符号0,1分配给两个最小概率的信源符号，并将其概率值合并，成为一个信源符号，q个符号的信源缩减成q-1个信源。1SS(3)排序，分配0,1,重复步骤(2),得缩减信源2S1S(4)直至最后信源只含两个符号，分配码符号0,1.(5)从最后一级信源开始，向前返回，码符号顺序列出，得相应码字。例8.11.01.02.02.04.054321SSSSS010101012.02.02.04.02.04.04.04.06.0001100100000111SS2S3S)/(2.28.06.04.04.0信源符号码元L965.02.2122.2)(LSH1S000011113S2S5S4S00110010000011构造出码树原因：(1)最小概率分配0,1时可任意。各码长不变,不变,码形式不同.ilL(2)缩减合并后的符号概率与其它符号概率相同时,概率大小次序当上下移动时,不违反规定。编码后不同,码不同,但相同。ilLHuffman编码方法得到的码并不唯一。)/(2.22.0382符号码元L2、例8.1新合并概率放上面1.02.01.04.02.00.44.02.00.64.054321SSSSS01010101011010111000码长比较3,3,2,2,24,4,21３，，问题：码长相同，哪种编码好？2122)()(])[(LlsPLlEiqiii码长度方差小的码序列长度变化较小，从实现的角度更好。36.1)()(2121LlsPiqii16.0)()(2122LlsPiqii编码方法补充：在霍夫曼编码过程中，在缩减信源时，使合并得来的概率尽量处于最高的位置。3、霍夫曼码具有的三个特点(1)短码得到充分利用则jiPPjill(2)各次缩减信源中最小概率的两个符号有相同的码长。(3)各次缩减信源中最小概率的两个符号的码字只有最后一位码元不同。8.1.2r元霍夫曼码注意三点(2)每次合并r个最小概率成为新信源，减少个符号。1r(3)满足式才能充分利用短码.rrq)1(信源缩减次数若不满足,增加的概率项21,qqpp)1(10r，，，(1)将最小概率的r个符号分配码元例8.2四元Huffman码4,2328,2,8rq而时补二项0007.002.005.008.008.010.010.018.015.015.020.018.022.020.040.022.010987654321SSSSSSSSSS0132112300230330320310300201003216S4S1S2001113S2S02338S7S5S8.1.3Huffman码的最佳性1、定理8.1kjkjllpp则,(1)若对于给定分布的任何信源，存在一个最佳即时码，此码满足以下性质(2)两个最小概率的信源符号所对应的码字具有相同的码长。(3)两个最小概率的信源符号对应的码字，除最后一位码元不同外，前面各位码元都相同。2、定理8.2)'()(CLCLC是Huffman码。可以证明r元霍夫曼码一定是最佳码。而且信源的N次扩展也可以采用Huffman编码方法，当N增大时，快速二元Huffman码一定是最佳即时码。即)(SHLr(1)无失真编码效率高,,常用于文件传真,语音处理和图象处理的数据压缩.1(2)解决速率匹配问题，设备较复杂,信源与信道间需增加缓冲寄存器,变速入,恒速出。Huffman码的优点和缺点(3)克服误差扩散：限制霍夫曼码仅能应用于优质信道（=10-6）以限制扩散的可能性。(4)要求了解信源的统计分布。(5)算法复杂度随着信源符号串长度的增加而迅速增长。Fano码的编码步骤：(1)将信源符号以概率递减的次序排列.(2)划分成两大组，使每组的概率和近似相等，并分别赋予码符号“0”和“1”.(3)将每大组的信源符号再分成两大组，重复(2),直至每小组只剩一个信源符号.(4)信源符号所对应的码符号序列则为编得的码字。8.2费诺(Fano)码例8.404.008.016.018.022.032.0654321SSSSSS01352.2)(SH)/(4.2信源符号码元L98.0)(LSH1111111011010010000111100例8.11.01.02.02.04.054321SSSSS0111111110110100112.8同表1.8同表费诺码的编码方法实际上是构造码树的一种方法,是即时码,当概率和相差较远时,会使平均码长增加.一般不是最佳码.000111111101001001.01.02.02.04.054321SSSSS1100001它是采用信源符号的累积分布函数来分配码字.1、设信源符号集且所有定义累积分布函数},,,,{21qaaaAAaaPii,0)()(kaFAaaaPaFikkiik,)()(1定义修正的累积分布函数)(21)()(11kkiikaPaPaF8.3香农-费诺-埃利斯码054321i)(1aF)(2aF)(4aF)(3aF)(2aF)(3aF)(1ap)(4ap)(3ap)(2ap)(kaF0.1(1)是每台阶的上界值．)(kaF(2)处于对应台阶的中点．)(kaFka(3)每台阶的高度是该符号的概率)(iaP(4)当)()(jijiaFaFaa时可采用的数值作为符号的码字.)(kaFka.0)(kaF码字，取多长？)()(21)()(kkalalkkaFaF选取1)(1log)(kkaPal)(1)(1logkkalaP1)()(logkkalaP1)(12)(kalkaP)()()()(212)()()(kkalkkalkkkaFaFaPaFaF1)(21)(kalkaP用替代所带来的误差小于,其值仍在同台阶以内．不同的对应不同的台阶，即区域，没有重叠，是即时码。)()(kalkaF)(kaF2)(kaPia书中证明2)(1)(SHLSH)()(212)()()()(kkalkkkaFaFaPaFaFk例8.5求香农—费诺—埃利斯码125.0125.05.025.0)(4321ssssaPk)/(75.21175.0信源符号二元码L)/(75.1325.05.0225.0)(符号bitSH636.075.275.1)(LSH0.1875.075.025.0)(kaF9375.08125.05.0125.0)(kaF4423il1111.01101.010.0001.0)()(kalkaF1111110110001码字W125.011125.0125.01105.025.025.0105.05.004312SSSS10001175.1L1Shannon-Fano-Elias码虽然不是最佳码，但它发展成为算术码，其编码和译码可由计算获得，效率很高。