中南大学信息论与编码课件Inf_T_C_64N

1、信息论与编码张祖平/Zhang Zuping电子信息工程系School of Information Science and Engineering,Central South University ,InformationTheory & Coding2013 秋季 信息11Inf Theory & Coding-张祖平2本章主要内容 (Main Content )6.1 单义可译码6.2 非延长码6.3 单义可译定理6.4 平均码长与有效性6.5 平均码长的界限定理6.8 霍夫曼（Huffman）编码6.0 编码概述6.6 香农码6.7 费诺码2013 秋季 信息11Inf Theory

2、& Coding-张祖平3 信源信源编码信道编码信道译码信源译码信宿信道6.0 编码概述编码概述2013 秋季 信息11Inf Theory & Coding-张祖平44生活中编码实例? 学号、身份证号码、一卡通、汉语等编码。编码实质：信息的组织方式。对信源的原始符号按一定的数学规则进行变换。结论: 信息无处不在 ，编码无处不在。6.0 编码概述编码概述2013 秋季 信息11Inf Theory & Coding-张祖平5通信的基本问题：通信的基本问题： 通信的基本问题：如何高速、高质地传送信息。 高速和高质有效性和可靠性。通信的还需要解决的问题：通信的还需要解决的问题： 1：解决信源发出的

3、消息不适合信道的传输，信源编码 2：希望信道可以尽快的传输信息，信源编码的编码效率 3：信道中有噪声，进入信道以前需要加入抗干扰能力，信道编码总结得到：总结得到： 信息质量一定时，如何提高信息传输速度（提高编码效率或压缩比）-信源编码信源编码（本章讨论问题），提高信息传输的有效性。 信道传输速度一定时，如何提高信息传输质量（抗干扰能力） ， -信道编码信道编码（下一章讨论），提高信息传输的可靠性。56.0 编码概述编码概述2013 秋季 信息11Inf Theory & Coding-张祖平6信源编码定义信源编码定义 将信源输出的消息符号进行有效变换，使其成为适合信道传输的符号序列，且使该序列

4、组成的新信源的冗余度尽可能地减少。信源编码目的信源编码目的 符号变换：使信源输出符号与信道的输入符号相匹配。 减少冗余：提高通信的有效性，就是针对信源输出符号序列的统计特性，寻找一定的把信源输出符号序列变换为最短码字序列的方法。信源编码基本方法信源编码基本方法 （1） 解除相关性：使序列中的各个符号尽可能地互相独立。比如：一个英文单词视为系列符号从而消除单词内部字母之间的相关性 。 （2） 概率均匀化：使编码中各个符号出现的概率尽可能地相等，尽可能缩短出现概率大的信源符号的码字，压缩每个信源符号的平均比特数。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性

5、。 66.0 编码概述编码概述2013 秋季 信息11Inf Theory & Coding-张祖平7信源编码的两大定理信源编码的两大定理 信源编码理论是信息论的一个重要分支，其理论基础是两个定理。 无失真信源编码定理无失真信源编码定理：是离散信源/数字信号编码的基础；无失真编码是可逆的，即当信源符号变换成代码以后，可以从代码无失真地恢复出原信源符号。 限失真信源编码定理限失真信源编码定理：是连续信源/模拟信号编码的基础，如语音、图像等信号。在连续信源的情况下，由于信源的信息量趋于无限，显然不能用离散符号序列来完成无失真编码，而只能进行限失真编码。香农信息论三大定理香农信息论三大定理 无失真信

6、源编码定理为第一极限定理； 信道编码定理（离散和连续信道）称为第二极限定理； 限失真信源编码定理称为第三极限定理。76.0 编码概述编码概述2013 秋季 信息11Inf Theory & Coding-张祖平8编码器的数学模型编码器的数学模型8 编码器可以看作这样一个系统，它的输入端为原始信源编码器可以看作这样一个系统，它的输入端为原始信源S S，其符号集为，其符号集为 ；而；而信道所能传输的符号集信道所能传输的符号集为为 。编码器的功能是用符号集。编码器的功能是用符号集X X中的元素，中的元素，将原始信源的符号将原始信源的符号 变换为相应的码字符号变换为相应的码字符号 ，所以编码，所以编码

7、器输出端的符号集为器输出端的符号集为 称为称为码字码字， 为码字为码字 的码元个数，称为码字的码元个数，称为码字 的码的码字长度，简称字长度，简称码长码长。码字的集合。码字的集合C C 称为称为码书码书。 称为称为码元。码元。12,.,qSS SS12 ,.,rXx xx12 ,.,qSs ss12 ,.,rXx xx编码器编码器12:,.,qCW WW12:,.,qCwwwiSiwiwiLiwiwix6.0 编码概述编码概述2013 秋季 信息11Inf Theory & Coding-张祖平9单义可译码单义可译码 若码的任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列，则此码

8、称为惟一可译码（单义可译码） 否则就称为非惟一可译码或非单义可译码。比如：比如： 信源S的符号集是英文字母和标点 而信道只能传输0,1序列，即信道要求的信源其符号集只能包含0和1我们需要用我们需要用0和和1组成的组成的码字码字来表示来表示S中的英文字母和标点中的英文字母和标点 要求1：码字要与S中的每种字符一一对应 要求2：码字序列要与S的N个符号组成的序列一一对应6.1 单义可译码单义可译码2013 秋季 信息11Inf Theory & Coding-张祖平1010码码1：W(1)码码2：W(2)码码3：W(3)码码4：W(4)码码5：W(5)00011100110010010100001

9、011110000001二元码二元码：若码符号集X0，1，即：码元只有2种取值可能、所有码字都是二元序列，则称为二元码。二元码是数字通信和计算机中最常用的一种码。二元信道二元信道：一种最简单的逻辑信道（信源编码器），信道的基本符号集为0，1，输入、输出符号都只有这两种取值。二元信源二元信源：信源输出符号只有这两种取值。6.1 单义可译码单义可译码2013 秋季 信息11Inf Theory & Coding-张祖平1111码码1：W(1)码码2：W(2)码码3：W(3)码码4：W(4)码码5：W(5)00011100110010010100001011110000001奇异码非奇异码：非奇异码

10、：若一组码中所有码字都不相同(即所有信源符号映射到不同的码符号序列，不同信源符号可分辨)，则称为非奇异码。奇异码：奇异码：反之，若码组中含有相同的码字则为奇异码。6.1 单义可译码单义可译码2013 秋季 信息11Inf Theory & Coding-张祖平1212码码1：W(1)码码2：W(2)码码3：W(3)码码4：W(4)码码5：W(5)000111001100100101000010111100000016.1 单义可译码单义可译码2013 秋季 信息11Inf Theory & Coding-张祖平1313码码1：W(1)码码2：W(2)码码3：W(3)码码4：W(4)码码5：W(

11、5)00011100110010010100001011110000001定长码（等长码）：若一组码中所有码字的码长都相同，则称为定长码。因为长度相同，相当于每个码字后有一个无形的逗号(点),又叫逗号(点)码。变长码：若一组码中所有码字的码长各不相同，则称为变长码。非奇异的等长码一定是单义可译码6.1 单义可译码单义可译码2013 秋季 信息11Inf Theory & Coding-张祖平1414码码1：W(1)码码2：W(2)码码3：W(3)码码4：W(4)码码5：W(5)00011100110010010100001011110000001奇异码非奇异的等长码一定是单义可译码都是非奇异的

12、且都是单义可译码6.1 单义可译码单义可译码2013 秋季 信息11Inf Theory & Coding-张祖平1515码码4：W(4)码码5：W(5)11100110000110000001W4，W5 都是非奇异的且都是单义可译码非即时码：如果接收端收到一个完整的码字后不能立即译码，必须结合后续的码元序列才能进行译码，称为非即时码。如码4，收到10无法判断结束。即时码：在译码时，如果当前已经接收到一个完整的码元序列之后，无需参考后续的码元符号、立即能够确定对应的码字，这种码制称为即时码。如码5，每个码字最后符号都是1，收到1好像逗(点)号，又叫逗号(点)码。6.2 非延长码非延长码2013

13、 秋季 信息11Inf Theory & Coding-张祖平1616码码4：W(4)码码5：W(5)11100110000110000001异前缀码异前缀码/ /非延长码非延长码：即时码要求任何一个码字都不是其他码字的前缀部分，所以也叫做异前缀码/非延长码，反之就叫延长码。即时码（异前缀码）一定可以单义可译码即时码（异前缀码）一定可以单义可译码。因为，如果没有一个码字是其他码字的前缀，则在译码过程中，当收到一个完整码字的码符号序列时，无需考虑下一个符号，就能直接把它译成对应的码字或信源符号。所有码所有码非奇异码非奇异码单义可译码单义可译码即时码即时码6.2 非延长码非延长码2013 秋季 信

14、息11Inf Theory & Coding-张祖平1717怎样构建非延长码？ 可用“树图法/码树”来构建非延长码6.2 非延长码非延长码2013 秋季 信息11Inf Theory & Coding-张祖平18 q=4, r=2, n1=1, n2=2, n3=3, n4=401得到一阶节点标记每条树枝树枝数为rW1可以二选一186.2 非延长码非延长码2013 秋季 信息11Inf Theory & Coding-张祖平19 q=4, r=2, n1=1, n2=2, n3=3, n4=4010011该选哪个节点？196.2 非延长码非延长码2013 秋季 信息11Inf Theory &

15、 Coding-张祖平20 q=4, r=2, n1=1, n2=2, n3=3, n4=4010011该选哪个节点？206.2 非延长码非延长码2013 秋季 信息11Inf Theory & Coding-张祖平21 q=4, r=2, n1=1, n2=2, n3=3, n4=4010011011216.2 非延长码非延长码2013 秋季 信息11Inf Theory & Coding-张祖平22 q=4, r=2, n1=1, n2=2, n3=3, n4=4010011011w1=1w2=01w3=001w4=0001未用尽226.2 非延长码非延长码2013 秋季 信息11Inf

16、Theory & Coding-张祖平23 q=4, r=2, n1=1, n2=2, n3=3, n4=40101011w1=1w2=01w3=001w4=0001未用尽236.2 非延长码非延长码2013 秋季 信息11Inf Theory & Coding-张祖平2424根：树的最上端树枝的个数为r，r=2为二元码树01001111010010001码5的树图ABCD中间节点（空心）节点：树枝的终端，从节点生出树枝，每个节点伸出r个枝终端节点（实心）码字：从根到终端节点对应的码符号，又称树叶 q=4, r=2, n1=1, n2=2, n3=3, n4=4w1=1w2=01w3=001w

17、4=00016.2 非延长码非延长码2013 秋季 信息11Inf Theory & Coding-张祖平2525该树的5个终端节点W1,W2,W3,W4,W5分别表示5个二进制码字0，100，111，1010，1011码树的性质：任一即时码都可用树图表示。即时码不是惟一的。单义可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀，按树图法构成的码一定满足即时码的充要条件，因为从根到叶所走的路径各不相同，而且中间节点不安排为码字，所以一定满足对前缀的限制。6.2 非延长码非延长码2013 秋季 信息11Inf Theory & Coding-张祖平2626满树满树 每个码字的联枝数

18、均相同时每个码字的联枝数均相同时( (定长码定长码) )非满树非满树 当码字的联枝数不同时当码字的联枝数不同时( (变长码变长码) ) 全树全树 每个中间节点的后续分支数均为每个中间节点的后续分支数均为m 非全树非全树 有些中间节点的后续分支数不足有些中间节点的后续分支数不足m满树满树非全树非全树树根树根终节点终节点中间节点中间节点非满树，全树非满树，全树6.2 非延长码非延长码2013 秋季 信息11Inf Theory & Coding-张祖平2727 0 1 2 0 1 2 0 1 2 0 1 20 1 20 1 2三进制码树三进制码树6.2 非延长码非延长码2013 秋季 信息11In

19、f Theory & Coding-张祖平2828S：s1，s2，s9，A=0，1，2，q=36.2 非延长码非延长码2013 秋季 信息11Inf Theory & Coding-张祖平2929 设原始信源符号集为S:S1,S2,Sq，码元符号集为x:x1,x2,xr，码字集合为W:W1,W2,Wq，其码长分别为L1,L2,Lq；则单义可译码存在的充要条件为码长组合满足 Kraft 不等式，即： 11qilirr是码元进制数q是信源符号数l为码字长度。 例：设二进制码树中X (a1， a2 ， a3 ， a4 )，码长 L11，L22，L32，L43，应用上述判断定理： 4122319222

20、2218iLi不存在满足这种不存在满足这种 Li的单义可译码的单义可译码6.3 单义可译定理单义可译定理2013 秋季 信息11Inf Theory & Coding-张祖平3030例：设二进制码树中X (a1， a2)，码长 L11，L22，L33，L43，应用上述判断定理： 412331222221iLia1=1 0 1 0 1 0 1a2=01a3=001a4=000这种Li的单义可译码是存在的用树的方式尝试构造，叶节点如1，01，001，000 单义可译码；但不能作为单义可译码的判据，如1，01，101，000 不是单义可译码；6.3 单义可译定理单义可译定理2013 秋季 信息11I

21、nf Theory & Coding-张祖平31关于关于Kraft不等式不等式 满足Kraft不等式的码长组合一定能构成至少一种单义可译码。 单义码的码长组合一定满足Kraft不等式，否则无法构成单义可译码。 有些码字的码长组合虽满足Kraft不等式，但不是单义可译码。 Kraft不等式不能用来判断是否是单义可译码，但不满足该不等式的一定不是单义可译码。316.3 单义可译定理单义可译定理2013 秋季 信息11Inf Theory & Coding-张祖平32321C这些码中哪些是单义可译码？哪些码是非延长码？6.3 单义可译定理单义可译定理2013 秋季 信息11Inf Theory &

22、Coding-张祖平33333112345623:6 2163:22222216463:164CCC1244135236:224 21:25 21:25 21CCC C2不是即时码C5不是唯一可译码，C5是奇异码又根据码树构造码字的方法 C1， C3， C6的码字均处于终端节点 他们是即时码C4不全是终端节点6.3 单义可译定理单义可译定理2013 秋季 信息11Inf Theory & Coding-张祖平34通信的有效性通信的有效性 单义可译码、非延长码解决了编码的一一对应和即时译码问题。 人们还要求提高通信的效率，希望通信中每个码能携带更多信息量。 对于已知信源 S 可用码符号 X 进行

23、变长编码，而且对同一信源可有多种非延长码或单义可译码。选择哪一种最好呢？ 因此我们结合信源空间、信源熵引出了平均码长。341212,( ),(),()( )qqsssSP sP sP sP s() ()( ) ( )( )log( )iiiiiiH XE I Xp x I xp xp x 信源空间信源熵6.4 平均码长与有效性平均码长与有效性2013 秋季 信息11Inf Theory & Coding-张祖平3535见书上例题。概率大的信源符号要用码长小的码字，概率小的信源符号要用码长大的码字6.4 平均码长与有效性平均码长与有效性2013 秋季 信息11Inf Theory & Codin

24、g-张祖平3636平均码长3.14比特/符号，信息传输率0.8309平均码长2.74比特/符号，信息传输率0.9522计算平均码长和信息传输率6.4 平均码长与有效性平均码长与有效性2013 秋季 信息11Inf Theory & Coding-张祖平37紧致码（最佳码）紧致码（最佳码） 对于某一信源和某一码符号集来说，若有一个单义可译码，其平均长度小于所有其他单义可译码的平均长度，称为紧致码（最佳码） 。 无失真信源编码的基本问题转化为找出紧致码（最佳码） 。 最佳码也就是紧致码的平均长度不是可以无限制缩小的，在理论上是有它的极限值的（在无失真信源编码的条件下）376.5 平均码长界限定理平

25、均码长界限定理2013 秋季 信息11Inf Theory & Coding-张祖平3838上界下界证明与例题见书6.5 平均码长界限定理平均码长界限定理2013 秋季 信息11Inf Theory & Coding-张祖平3939表明码符号数为r的码符号集合编出的非延长码的平均码长下界值，在数值上等于r进制信息单位的信源熵值。也就是说平均码长下限值在数值上取决于给定的信源的信息熵。信源给定，这个信源的的平均码长下限值就确定了，改进编码方法无法进一步提高有效性，只能对编码对象，即信源做文章6.5 平均码长界限定理平均码长界限定理2013 秋季 信息11Inf Theory & Coding-张

26、祖平40406.5 平均码长界限定理平均码长界限定理2013 秋季 信息11Inf Theory & Coding-张祖平41416.6 香农码香农码2013 秋季 信息11Inf Theory & Coding-张祖平42421. 将信源符号按概率排序：将信源符号按概率排序：p(a1)p(a2)p(an)；2. 计算第计算第i个码字个码字( (之前之前) )的累加概率的累加概率pa(xj)3. 确定第确定第i个码字的码长个码字的码长ni( (整数整数) )：- -log2p(xi) ni 1-log2p(xi)4.4.将累加概率将累加概率pa(xj)变为二进制数，并取小数点后变为二进制数，并

27、取小数点后ni位，即为位，即为ai的编的编码码 说明说明 j j=1=1时，时， pa(a1) = p(a0) =0j j=2=2时，时， pa(a2) = p(a1) + p(a0) = p(a1) ) j j=3=3时，时， pa(a3) = p(a2) + p(a1) + p(a0) 因而因而pa(aj)表示：表示：aj之前之前( (不含不含aj) )的各概率之和的各概率之和100()( ),1,., ,()0jajiip ap ajnp a6.6 香农码香农码2013 秋季 信息11Inf Theory & Coding-张祖平43第四步举例第四步举例 累加概率Pi=0.57，变成二进

28、制数，为0.1001。 转换的方法是：用Pi乘以2，如果整数部分有进位，则小数点后第一位为1，否则为0，将其小数部分再做同样的处理，得到小数点后的第二位，依此类推，直到得到了满足要求的位数，或者没有小数部分了为止。 对应结果：现在Pi=0.57，乘以2为1.14，整数部分有进位，所以小数点后第一位为1，将小数部分即0.14再乘以2，得0.28，没有整数进位，所以小数点后第二位为0，依此类推，可得到其对应的二进制数为0.1001。436.6 香农码香农码2013 秋季 信息11Inf Theory & Coding-张祖平4444123456,()05

29、XxxxxxxP X例例: : 有一单符号离散无记忆信源，编二进制香农码有一单符号离散无记忆信源，编二进制香农码6.6 香农码香农码2013 秋季 信息11Inf Theory & Coding-张祖平45450001100101110111110可以看出，编码所得的码字，没有相同的，所以是非奇异码也没有一个码字是其它码字的前缀，所以是即时码（非延长码），也是单义可译码。用树图构造出来可以看出符合非延长码特点。0.2522(0.20.15)30.1040.0552.7n 621()()log()2.42325iiiH Xp ap a ()2.420.89622.7H XRn平均信息传输率 平均

30、码长与信息熵香农码编码效香农码编码效率并不是很高，率并不是很高，不是最佳码，不是最佳码，为什么？为什么？图上可以看出图上可以看出来吗？来吗？码符号/信源符号6.6 香农码香农码2013 秋季 信息11Inf Theory & Coding-张祖平4646信源共有7个符号组成，其概率如表所示，求二进制香农码，平均码长和信息传输率。信源消息符号信源消息符号xi符号概率符号概率p(xi)x1 0.20 x2 0.19x3 0.18x4 0.17x5 0.15x6 0.10 x7 0.016.6 香农码香农码2013 秋季 信息11Inf Theory & Coding-张祖平4747xip(xi)累

31、加累加Pi-log2 p(xi)码字长度码字长度Ki 码码 字字x10.2002.343000 x13001x30.180.392.483011x40.170.572.563100 x50.150.742.743101x60.100.893.3441110 x70.010.996.667111111071( )3.14iiiKp x K()2.610.8313.14H XRK6.6 香农码香农码2013 秋季 信息11Inf Theory & Coding-张祖平4848费诺编码也是一种常见的信源编码方法。费诺编码也是一种常见的信源编码方法。编码步骤如下：编码步骤如下：(

32、1)(1)将概率按从大到小的顺序排列，令将概率按从大到小的顺序排列，令 p(a1) p(a2) p(an)(2)(2)按编码进制数将概率分组，使每组概率尽可能接近或相按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编等。如编二进制码就分成两组，编m m进制码就分成进制码就分成m m组。组。(3)(3)给每一组分配一位码元。给每一组分配一位码元。(4)(4)将每一分组再按同样原则划分，重复步骤将每一分组再按同样原则划分，重复步骤2 2和和3 3，直至概，直至概率不再可分为止。率不再可分为止。6.7 费诺码费诺码2013 秋季 信息11Inf Theory & Codi

33、ng-张祖平4949例例 设有一单符号离散信源设有一单符号离散信源, ,对该信源编二进制费诺码。对该信源编二进制费诺码。123456,()05XaaaaaaP X二进制费诺编码 信源符号 概率 编码 码字 码长 x1 0.25 0 00 2 x2 0.25 0 1 01 2 x3 0.20 0 10 2 x4 0.15 0 110 3 x5 0.10 0 1110 4 x6 0.05 1 1 1 1 1111 4 大概率用短码大概率用短码6.7 费诺码费诺码2013 秋季 信息11Inf Theory & Coding-张祖平5050该信源的熵为该信

34、源的熵为平均码长为平均码长为编码效率为编码效率为 本例中费诺编码有较高的编码效率。费诺码比较适合于本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近每次分组概率都很接近的信源。特别是对每次的信源。特别是对每次分组概率都相分组概率都相等等的信源进行编码时，可达到理想的编码效率。的信源进行编码时，可达到理想的编码效率。621()( )log( )2.45(/)iiiH Xp ap a 比特 符号61( )2.4(/)iiiLp a k比特 符号()2.423350.98912.45H XRK6.7 费诺码费诺码2013 秋季 信息11Inf Theory & Coding-张祖平

35、5151题中码字还可用码树来表示，如图所示。题中码字还可用码树来表示，如图所示。6.7 费诺码费诺码2013 秋季 信息11Inf Theory & Coding-张祖平5252信源共有7个符号组成，其概率如表所示，求二进制费诺码，平均码长和信息传输率。信源消息符号信源消息符号xi符号概率符号概率p(xi)x1 0.20 x2 0.19x3 0.18x4 0.17x5 0.15x6 0.10 x7 0.016.7 费诺码费诺码2013 秋季 信息11Inf Theory & Coding-张祖平5353消 息 符消 息 符号号ai各 个 消各 个 消息概率息概率 p(ai)第一次第一次分组分组

36、第二次第二次分组分组第三次第三次分组分组第四次第四次分组分组二元二元码字码字码长码长Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.0111111474. 2)(71iiiKapK953. 074. 261. 2)(KXHR6.7 费诺码费诺码2013 秋季 信息11Inf Theory & Coding-张祖平5454信源共有8个符号组成，其概率如表所示，求二进制费诺码，平均码长和信息传输率。1234567811111111()448816161616aaaaaaaaXP X6.7 费诺码

37、费诺码2013 秋季 信息11Inf Theory & Coding-张祖平5555平均码长平均码长 81( )0.25 2 2 0.125 2 3 0.0625 4 42.75iiiLp a k 编码效率编码效率()1H XRK信源熵信源熵 H(X)=2.75 bit/sign 每次两分组的概率正好相等每次两分组的概率正好相等，效率最高，效率最高6.7 费诺码费诺码2013 秋季 信息11Inf Theory & Coding-张祖平56香农码与费诺码总结香农码与费诺码总结 香农第一编码定理给出了码字的平均长度的下界和上界。 但并不是说大于这上界不能构成单义可译码，而是因为我们总是希望尽可能

38、短。 也就是说，定理给出的是最佳码（比其他单义可译码平均码长都小的编码）的最短平均码长的下界和上界，并指出这个最短的平均码长与信源熵是有关的。 无失真信源编码的基本问题转化为找出紧致码（最佳码） 。 最佳编码基本思想： 将概率大的信息符号编以短的码字，概率小的符号编以长的码字。 最佳码的编码主要方法： 香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码等。 香农码：编码唯一，但通常效率不高，学术意义大于实际意义； 费诺码：由于赋码元时的任意性，因此编出的码字不是唯一的；构造码树时自顶向下；编码效率高于香农码，适合于对分组概率相等或接近的信源编码； 香农码和费诺码都不是真正意

39、义上的最佳码，哈夫曼编码实现了最佳编码。566.7 费诺码费诺码2013 秋季 信息11Inf Theory & Coding-张祖平5757哈夫曼哈夫曼1953年于年于MIT获得科学博士学位获得科学博士学位哈夫曼编码是哈夫曼编码是1951年，他在研究生阶段课程（信年，他在研究生阶段课程（信息论与编码）的课程大作业中提出的，哈夫曼使息论与编码）的课程大作业中提出的，哈夫曼使用自底向上的方法构建二叉树，避免了次优算法用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端编码的最大弊端自顶向下构自顶向下构建树，该算法广泛应用于数据压缩和计算机安全建树，该算法广泛应用于数据

40、压缩和计算机安全领域。领域。离开离开MIT后，哈夫曼来到加利福尼亚大学的计算后，哈夫曼来到加利福尼亚大学的计算机系任教。机系任教。哈夫曼从未为此算法申请过专利或其它相关能够哈夫曼从未为此算法申请过专利或其它相关能够为他带来经济利益的东西，他将他全部的精力放为他带来经济利益的东西，他将他全部的精力放在教学上，以他自己的话来说，在教学上，以他自己的话来说，“我所要带来的我所要带来的就是我的学生。就是我的学生。”David A. Huffman(1925-1999)6.8 Huffman编码编码2013 秋季 信息11Inf Theory & Coding-张祖平58还记得数据结构中的哈夫曼码吗？还

41、记得数据结构中的哈夫曼码吗？哈夫曼编码是最佳码（即平均码长最小）哈夫曼编码是最佳码（即平均码长最小） 怎么证明这一点？哈夫曼在1952年的原始论文中并没有给出证明 后人给出了不同的证明方法特点：特点： 自底向上构造码树 把码长小的码字分配给出现频率高的信源字符 在编码过程中需要构造虚拟节点 每次缩减信源的最长两个码字有相同的码长。586.8 Huffman编码编码2013 秋季 信息11Inf Theory & Coding-张祖平59(1) (1) 将信源符号按概率从大到小的顺序排列，令将信源符号按概率从大到小的顺序排列，令 p(a1) p(a2) p(an)(2) (2) 给两个概率最小的

42、信源符号给两个概率最小的信源符号p( (an-1) )和和p( (an) )各分配一个码位各分配一个码位“0 0”和和“1 1”，将这两个信源符号合并成一个新符号，并用这两，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含个最小的概率之和作为新符号的概率，结果得到一个只包含( (q1) )个信源符号的新信源。称为个信源符号的新信源。称为信源的第一次缩减信源信源的第一次缩减信源，用，用S1表示。表示。(3)(3)将缩减信源将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤的符号仍按概率从大到小顺序排列，重复步骤2 2，得到只含，得到只含( (q2

43、) )个符号的缩减信源个符号的缩减信源S2。(4)(4)重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为两个符号的概率之和必为1 1。然后从最后一级缩减信源开始，依。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。编码路径向前返回，就得到各信源符号所对应的码字。596.8 Huffman编码编码2013 秋季 信息11Inf Theory & Coding-张祖平60601 . 01 . 02 . 02 . 04 . 054321aaaaaPX0.4 0.4 0.4 1.0 0.2 0.

44、2 0.40.2 0.2 0.20.1 0.110101010aip(ai)码字码字Wi1a10.40a20.210a30.2111a40.11101a50.111006.8 Huffman编码编码2013 秋季 信息11Inf Theory & Coding-张祖平61611 . 01 . 02 . 02 . 04 . 054321aaaaaPX2 . 2)(71iiiKapK 码元码元/符号符号 ()0.965H XRK平均码长、编码效率平均码长、编码效率aip(ai)码字码字Wi1a10.40a20.210a30.2111a40.11101a50.111006.8 Huffman编码编码

45、2013 秋季 信息11Inf Theory & Coding-张祖平62621 . 01 . 02 . 02 . 04 . 054321aaaaaPX0.4 0.4 0.4 1.0 0.2 0.2 0.40.2 0.2 0.20.1 0.101010101aip(ai)码字码字Wi2a10.41a20.201a30.2000a40.10010a50.1001101106.8 Huffman编码编码2013 秋季 信息11Inf Theory & Coding-张祖平63631 . 01 . 02 . 02 . 04 . 054321aaaaaPXaip(ai)码字码字Wi2a10.41a20

46、.201a30.2000a40.10010a50.100112 . 2)(71iiiKapK 码元码元/符号符号 ()0.965H XRK平均码长、编码效率平均码长、编码效率6.8 Huffman编码编码2013 秋季 信息11Inf Theory & Coding-张祖平64641 . 01 . 02 . 02 . 04 . 054321aaaaaPXaip(ai)码字码字Wi3a10.400a20.210a30.211a40.1010a50.10110.4 0.4 1.0 0.2 0.4 0.40.2 0.2 0.20.1 0.20.1010101016.8 Huffman编码编码2013

47、 秋季 信息11Inf Theory & Coding-张祖平65651 . 01 . 02 . 02 . 04 . 054321aaaaaPX2 . 2)(71iiiKapK 码元码元/符号符号 ()0.965H XRK平均码长、编码效率平均码长、编码效率aip(ai)码字码字Wi3a10.400a20.210a30.211a40.1010a50.10116.8 Huffman编码编码2013 秋季 信息11Inf Theory & Coding-张祖平66哈夫曼编码形式不是唯一的，用方差选择较好的编码哈夫曼编码形式不是唯一的，用方差选择较好的编码 由于0，1顺序可以不同，导致不一样 由于出

48、现合并后等概率情况，排序位置不同，导致不一样aip(ai)码字码字Wi1码字码字Wi2码字码字Wi3a10.40100a20.2100110a30.211100011a40.111010010010a50.111000011011W2和和w3编码的方差不同编码的方差不同，进行哈夫进行哈夫曼编码时，为得到曼编码时，为得到码方差码方差最小的码，最小的码，应使合并的信源符号位于缩减信源序应使合并的信源符号位于缩减信源序列列尽可能高的位置尽可能高的位置上，以减少再次合上，以减少再次合并的次数，充分利用短码。并的次数，充分利用短码。 qiiiilKkapKkE1222)(221.36l230.16l方差

49、越小，说明各个码的长度方差越小，说明各个码的长度都比较接近平均长度，这样编都比较接近平均长度，这样编码器和解码器就可以比较简单码器和解码器就可以比较简单6.8 Huffman编码编码2013 秋季 信息11Inf Theory & Coding-张祖平67信源共有7个符号组成，其概率如表所示，求二进制哈夫曼编码，平均码长和信息传输率。信源消息符号信源消息符号xi符号概率符号概率p(xi)x1 0.20 x2 0.19x3 0.18x4 0.17x5 0.15x6 0.10 x7 0.016.8 Huffman编码编码2013 秋季 信息11Inf Theory & Coding-张祖平6868

50、0.20 0.20 0.26 0.35 0.39 0.61 1.00.19 0.19 0.20 0.26 0.35 0.390.18 0.18 0.19 0.20 0.260.17 0.17 0.18 0.190.15 0.15 0.170.10 0.110.010101010101016.8 Huffman编码编码2013 秋季 信息11Inf Theory & Coding-张祖平6969信源信源符号符号符号符号概率概率 编编 码码 过过 程程码字码字码码长长0.201020.191120.1800030.1700130.1501030.10011040.0101114010.200.19

51、50.110.280.1701010.260.350.200.19010.350.260.39010.390.61011x2x3x4x5x6x7x6.8 Huffman编码编码2013 秋季 信息11Inf Theory & Coding-张祖平70700.050.250.69 1011001011001符号码元/72. 2)(71iiiKxpK码元/9596. 072. 261. 2)(bitKXHR采用码树形式进行哈夫曼编码的过程中，由于代表信源符号的节点都是终端节点，因此

52、其编码不可能是其它终端节点对应的编码的前缀。哈夫曼编码总是把概率大的符号安排在离根节点近的终端节点，所以平均码长短。6.8 Huffman编码编码2013 秋季 信息11Inf Theory & Coding-张祖平71平均码长=2*0.24+2*0.2+2*0.18+2*0.16+2*0.14+2*0.08=2码符号/信源符号定长编码？这样编码效率高吗？为什么？6.8 Huffman编码编码2013 秋季 信息11Inf Theory & Coding-张祖平7272 0 1 2 0 1 2 0 1 2 0 1 2w1w2w3w4w5w6？很明显可以使用“0”这个短码来作为概率最大的S1的编

53、码，为什么编码结果却没有用到呢？因为最后一次缩减，没有把码符号集中所有符号都用上，最后一次缩减是针对大概率信源符号的，是短码，短码没有充分利用，反而优先把小概率的信源符号，是长码，用上了所有码符号集中的符号。6.8 Huffman编码编码2013 秋季 信息11Inf Theory & Coding-张祖平7373 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2非全树非全树全树全树m进制的全树的终端叶节点数进制的全树的终端叶节点数( (码码个数个数) ) m + k(m-1), k = 0,1,2,.( (每从一个节点分出每从一个节点分出m枝枝, , 就增加就增加m-1-1个终端个终端) )当信源符号数当信源符号数 n，n m+k(m-1)时，时，令令 s = m+k(m-1)-n, , s m-1-1，为，为构成全树所缺少的码字构成全树所缺少的码字( (分支分支) )数，数，必须在信源符号集合中补上概率必须在信源符号集合中补上概率为为0 0的的s个虚假符号个虚假符号w1w2w3w4w5w66.8 Huffman编