第八章 无失真信源编码

第八章无失真的信源编码8.1霍夫曼(Huffman)码8.2费诺(Fano)码8.3香农—费诺—埃利斯码8.1霍夫曼(Huffman)码8.1.1二元霍夫曼码8.1.2r元霍夫曼码8.1.3Huffman码的最佳性香农编码：1、码长2、按照算出的码长、用树图法编出相应的即时码。一般香农编码的不是最短的，即不是最佳码。例8.1

用香农编码方法编成二元惟一可译码.编码

8.1.1二元霍夫曼码1、二元Huffman码的编码步骤将q个信源符号按概率分布由大到小的顺序排列起来：(2)将码符号0,1分配给两个最小概率的信源符号，并将其概率值合并，成为一个信源符号，q个符号的信源缩减成q-1

个信源。(3)排序，分配0,1,重复步骤(2),得缩减信源(4)直至最后信源只含两个符号，分配码符号0,1.(5)从最后一级信源开始，向前返回，码符号顺序列出，得相应码字。例8.1构造出码树原因：(1)最小概率分配0,1时可任意。各码长不变,不变,码形式不同.(2)缩减合并后的符号概率与其它符号概率相同时,概率大小次序当上下移动时,不违反规定。编码后不同,码不同,但相同。Huffman编码方法得到的码并不唯一。2、例8.1新合并概率放上面码长比较问题：码长相同，哪种编码好？码长度方差小的码序列长度变化较小，从实现的角度更好。编码方法补充：在霍夫曼编码过程中，在缩减信源时，使合并得来的概率尽量处于最高的位置。3、霍夫曼码具有的三个特点(1)短码得到充分利用则(2)各次缩减信源中最小概率的两个符号有相同的码长。(3)各次缩减信源中最小概率的两个符号的码字只有最后一位码元不同。8.1.2r元霍夫曼码注意三点(2)每次合并r个最小概率成为新信源，减少个符号。(3)满足式才能充分利用短码.信源缩减次数若不满足,增加的概率项(1)将最小概率的r个符号分配码元例8.2

四元Huffman码补二项8.1.3Huffman码的最佳性1、定理8.1(1)若对于给定分布的任何信源，存在一个最佳即时码，此码满足以下性质(2)两个最小概率的信源符号所对应的码字具有相同的码长。(3)两个最小概率的信源符号对应的码字，除最后一位码元不同外，前面各位码元都相同。2、定理8.2C是Huffman码。可以证明r

元霍夫曼码一定是最佳码。而且信源的N次扩展也可以采用Huffman编码方法，当N增大时，快速二元Huffman码一定是最佳即时码。即(1)无失真编码效率高,,常用于文件传真,语音处理和图象处理的数据压缩.(2)解决速率匹配问题，设备较复杂,信源与信道间需增加缓冲寄存器,

变速入,恒速出。Huffman码的优点和缺点(3)克服误差扩散：限制霍夫曼码仅能应用于优质信道（<=10-6）以限制扩散的可能性。(4)要求了解信源的统计分布。(5)算法复杂度随着信源符号串长度的增加而迅速增长。Fano

码的编码步骤：(1)将信源符号以概率递减的次序排列.(2)划分成两大组，使每组的概率和近似相等，并分别赋予码符号“0”和“1”.(3)将每大组的信源符号再分成两大组，重复(2),直至每小组只剩一个信源符号.(4)信源符号所对应的码符号序列则为编得的码字。8.2费诺(Fano)码例8.4例8.1费诺码的编码方法实际上是构造码树的一种方法,是即时码,当概率和相差较远时,会使平均码长增加.一般不是最佳码.它是采用信源符号的累积分布函数来分配码字.1、设信源符号集且所有定义累积分布函数定义修正的累积分布函数8.3香农-费诺-埃利斯码(1)是每台阶的上界值．(2)处于对应台阶的中点．(3)每台阶的高度是该符号的概率(4)当可采用的数值作为符号的码字.码字，取多长？选取用替代所带来的误差小于,其值仍在同台阶以内．不同的对应不同的台阶，即区域，没有重叠，是即时码。书中证明例8.5

求香农—费诺—埃利斯码Shannon-Fano-Elias码虽然不是最佳码，但它发展成为算术码，其编码和译码可由计算获得，效率很高。作业：(香农码、Huffman码、Fano码)1.画出任一种编码的实现流程图。2.使用Matlab或C++语言编程，完成编码。要求：已知：信源符号个数q,符号概率;输入：信源符号个数和概率，在程序运行时从键盘输入；输出：编码3.自己举例,给出编码的程序执行结果。4.作业提交Word文档——（1）作业题目；（2）算法流程图；（3）程序验证例子；（