信息论第八章

信息论第八章第1页，共25页，2023年，2月20日，星期日8.1霍夫曼(Huffman)码8.1.1二元霍夫曼码8.1.2r元霍夫曼码8.1.3Huffman码的最佳性第2页，共25页，2023年，2月20日，星期日香农编码：1、码长2、按照算出的码长、用树图法编出相应的即时码。一般香农编码的不是最短的，即不是最佳码。第3页，共25页，2023年，2月20日，星期日例8.1

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

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

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

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

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

变速入,恒速出。Huffman码的优点和缺点(3)克服误差扩散：限制霍夫曼码仅能应用于优质信道（<=10-6）以限制扩散的可能性。(4)要求了解信源的统计分布。(5)算法复杂度随着信源符号串长度的增加而迅速增长。第16页，共25页，2023年，2月20日，星期日Fano码的编码步骤：(1)将信源符号以概率递减的次序排列.(2)划分成两大组，使每组的概率和近似相等，并分别赋予码符号“0”和“1”.(3)将每大组的信源符号再分成两大组，重复(2),直至每小组只剩一个信源符号.(4)信源符号所对应的码符号序列则为编得的码字。8.2费诺(Fano)码第17页，共25页，2023年，2月20日，星期日例8.4第18页，共25页，2023年，2月20日，星期日例8.1费诺码的编码方法实际上是构造码树的一种方法,是即时码,当概率和相差较远时,会使平均码长增加.一般不是最佳码.第19页，共25页，2023年，2月20日，星期日它是采用信源符号的累积分布函数来分配码字.1、设信源符号集且所有定义累积分布函数定义修正的累积分布函数8.3香农-费诺-埃利斯码第20页，共25页，2023年，2月20日，星期日(1)是每台阶的上界值．(2)处于对应台阶的中点．(3)每台阶的高度是该符号的概率(4)当第21页，共25页，2023年，2月20日，星期日可采用的数值作为符号的码字.码字，取多长？选取第22页，共25页，2023年，2月20日，星期日用替代所带来的误差小于,其值仍在同台阶以内．不同的对应不同的台阶，即区域，没有重叠，是即时码。书中证明第23页，共25页，2023年，2