信息论第八章

1、信息论第八章第1页，共25页，2022年，5月20日，1点22分，星期一8.1 霍夫曼(Huffman)码8.1.1 二元霍夫曼码 8.1.2 r元霍夫曼码 8.1.3 Huffman码的最佳性 第2页，共25页，2022年，5月20日，1点22分，星期一香农编码：1、码长2、按照算出的码长、用树图法编出相应的即时码。一般香农编码的 不是最短的，即不是最佳码。第3页，共25页，2022年，5月20日，1点22分，星期一例8.1 用香农编码方法编成二元惟一可译码. 编码 第4页，共25页，2022年，5月20日，1点22分，星期一8.1.1 二元霍夫曼码1、二元Huffman码的编码步骤将q个信

2、源符号按概率分布由大到小的 顺序排列起来：(2)将码符号0,1分配给两个最小概率的信 源符号，并将其概率值合并，成为一个 信源符号，q个符号的 信源缩减成q-1 个 信源。(3)排序 ，分配0,1, 重复步骤(2), 得缩减 信源 第5页，共25页，2022年，5月20日，1点22分，星期一(4)直至最后信源只含两个符号，分配码 符号0,1.(5) 从最后一级信源开始，向前返回，码 符号顺序列出，得相应码字。例8.1第6页，共25页，2022年，5月20日，1点22分，星期一构造出码树第7页，共25页，2022年，5月20日，1点22分，星期一原因：(1) 最小概率分配0,1时可任意。各 码长

3、 不变, 不变, 码形式不同.(2) 缩减合并后的符号概率与其它符号概 率相同时, 概率大小次序当上下移动 时, 不违反规定。编码后 不同, 码不 同, 但 相同。Huffman编码方法得到的码并不唯一。第8页，共25页，2022年，5月20日，1点22分，星期一2、例8.1 新合并概率放上面码长比较第9页，共25页，2022年，5月20日，1点22分，星期一问题：码长相同，哪种编码好？码长度方差小的码序列长度变化较小，从实现的角度更好。第10页，共25页，2022年，5月20日，1点22分，星期一编码方法补充： 在霍夫曼编码过程中，在缩减信源时，使合并得来的概率尽量处于最高的位置。3、霍夫曼

4、码具有的三个特点(1) 短码得到充分利用 则(2) 各次缩减信源中最小概率的两个符号 有相同的码长。(3) 各次缩减信源中最小概率的两个符号 的码字只有最后一位码元不同。第11页，共25页，2022年，5月20日，1点22分，星期一8.1.2 r元霍夫曼码注意三点(2) 每次合并r个最小概率成为新信源，减 少 个符号。(3) 满足式 才能充分利用短码.信源缩减次数若不满足, 增加 的概率项(1) 将最小概率的r个符号分配码元第12页，共25页，2022年，5月20日，1点22分，星期一例8.2 四元Huffman码补二项第13页，共25页，2022年，5月20日，1点22分，星期一8.1.3

5、Huffman码的最佳性1、定理8.1(1) 若对于给定分布的任何信源，存在一个最佳即时码，此码满足以下性质(2) 两个最小概率的信源符号所对应的 码字具有相同的码长。(3) 两个最小概率的信源符号对应的码 字，除最后一位码元不同外，前面 各位码元都相同。第14页，共25页，2022年，5月20日，1点22分，星期一2、定理 8.2 C是 Huffman 码。 可以证明 r 元霍夫曼码一定是最佳码。而且信源的N次扩展也可以采用Huffman 编码方法，当N增大时，快速 二元 Huffman 码一定是最佳即时码。即第15页，共25页，2022年，5月20日，1点22分，星期一(1) 无失真编码效

6、率高, , 常用于文件传 真, 语音处理和图象处理的数据压缩.(2) 解决速率匹配问题，设备较复杂, 信源与信 道间需增加缓冲寄存器, 变速入, 恒速出。Huffman 码的优点和缺点(3) 克服误差扩散：限制霍夫曼码仅能应用于 优质信道（=10-6）以限制扩散的可能性。(4) 要求了解信源的统计分布。(5) 算法复杂度随着信源符号串长度的增加而 迅速增长。第16页，共25页，2022年，5月20日，1点22分，星期一Fano 码的编码步骤：(1) 将信源符号以概率递减的次序排列. (2) 划分成两大组，使每组的概率和近似 相等，并分别赋予码符号“0”和“1”.(3) 将每大组的信源符号再分成

7、两大组， 重复(2), 直至每小组只剩一个信源符号.(4) 信源符号所对应的码符号序列则为 编得的码字。8.2 费诺(Fano)码第17页，共25页，2022年，5月20日，1点22分，星期一例8.4 第18页，共25页，2022年，5月20日，1点22分，星期一例8.1费诺码的编码方法实际上是构造码树的一种方法,是即时码,当概率和相差较远时,会使平均码长增加.一般不是最佳码.第19页，共25页，2022年，5月20日，1点22分，星期一它是采用信源符号的累积分布函数来分配码字.1、设信源符号集且所有定义累积分布函数定义修正的累积分布函数8.3 香农-费诺-埃利斯码第20页，共25页，2022年，5月20日，1点22分，星期一(1) 是每台阶的上界值(2) 处于对应台阶的中点(3) 每台阶的高度是该符号的概率(4) 当第21页，共25页，2022年，5月20日，1点22分，星期一可采用 的数值作为符号的码字.码字，取多长？选取第22页，共25页，2022年，5月20日，1点22分，星期一 用替代 所带来的误差小于 , 其值仍在同台阶以内不同的对应不同的台阶，即区域，没有重叠，是即时码。书中证明第23页，共25页，2022年，5月20日，1点22分，星期一例8.5 求香农费