中南大学信息论与编码课件Inf-T-C-64N

信息论与编码张祖平/ZhangZuping电子信息工程系SchoolofInformationScienceandEngineering,CentralSouthUniversity,zpzhang@InformationTheory&Coding第六章无失真信源编码2013秋季信息111InfTheory&Coding-张祖平本章主要内容

(MainContent)6.1单义可译码6.2非延长码6.3单义可译定理6.4平均码长与有效性6.5平均码长的界限定理6.8霍夫曼（Huffman）编码6.0编码概述6.6香农码6.7费诺码2013秋季信息112InfTheory&Coding-张祖平

信源信源编码信道编码信道译码信源译码信宿信道6.0编码概述2013秋季信息113InfTheory&Coding-张祖平4生活中编码实例?

学号、身份证号码、一卡通、汉语等编码。编码实质：信息的组织方式。对信源的原始符号按一定的数学规则进行变换。结论:信息无处不在，编码无处不在。6.0编码概述2013秋季信息114InfTheory&Coding-张祖平通信的基本问题：通信的基本问题：如何高速、高质地传送信息。高速和高质＝有效性和可靠性。通信的还需要解决的问题：1：解决信源发出的消息不适合信道的传输，信源编码2：希望信道可以尽快的传输信息，信源编码的编码效率3：信道中有噪声，进入信道以前需要加入抗干扰能力，信道编码总结得到：信息质量一定时，如何提高信息传输速度（提高编码效率或压缩比）----信源编码（本章讨论问题），提高信息传输的有效性。信道传输速度一定时，如何提高信息传输质量（抗干扰能力），----信道编码（下一章讨论），提高信息传输的可靠性。56.0编码概述2013秋季信息115InfTheory&Coding-张祖平信源编码定义将信源输出的消息符号进行有效变换，使其成为适合信道传输的符号序列，且使该序列组成的新信源的冗余度尽可能地减少。信源编码目的符号变换：使信源输出符号与信道的输入符号相匹配。减少冗余：提高通信的有效性，就是针对信源输出符号序列的统计特性，寻找一定的把信源输出符号序列变换为最短码字序列的方法。信源编码基本方法（1）解除相关性：使序列中的各个符号尽可能地互相独立。比如：一个英文单词视为系列符号从而消除单词内部字母之间的相关性。（2）概率均匀化：使编码中各个符号出现的概率尽可能地相等，尽可能缩短出现概率大的信源符号的码字，压缩每个信源符号的平均比特数。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。66.0编码概述2013秋季信息116InfTheory&Coding-张祖平信源编码的两大定理信源编码理论是信息论的一个重要分支，其理论基础是两个定理。无失真信源编码定理：是离散信源/数字信号编码的基础；无失真编码是可逆的，即当信源符号变换成代码以后，可以从代码无失真地恢复出原信源符号。限失真信源编码定理：是连续信源/模拟信号编码的基础，如语音、图像等信号。在连续信源的情况下，由于信源的信息量趋于无限，显然不能用离散符号序列来完成无失真编码，而只能进行限失真编码。香农信息论三大定理无失真信源编码定理为第一极限定理；信道编码定理（离散和连续信道）称为第二极限定理；限失真信源编码定理称为第三极限定理。76.0编码概述2013秋季信息117InfTheory&Coding-张祖平编码器的数学模型8编码器可以看作这样一个系统，它的输入端为原始信源S，其符号集为；而信道所能传输的符号集为。编码器的功能是用符号集X中的元素，将原始信源的符号变换为相应的码字符号，所以编码器输出端的符号集为

称为码字，为码字的码元个数，称为码字的码字长度，简称码长。码字的集合C称为码书。

称为码元。编码器6.0编码概述2013秋季信息118InfTheory&Coding-张祖平单义可译码若码的任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列，则此码称为惟一可译码（单义可译码）否则就称为非惟一可译码或非单义可译码。比如：信源S的符号集是英文字母和标点而信道只能传输0,1序列，即信道要求的信源其符号集只能包含0和1我们需要用0和1组成的码字来表示S中的英文字母和标点要求1：码字要与S中的每种字符一一对应要求2：码字序列要与S的N个符号组成的序列一一对应6.1单义可译码2013秋季信息119InfTheory&Coding-张祖平10码1：W(1)码2：W(2)码3：W(3)码4：W(4)码5：W(5)00011100110010010100001011110000001二元码：若码符号集X＝{0，1}，即：码元只有2种取值可能、所有码字都是二元序列，则称为二元码。二元码是数字通信和计算机中最常用的一种码。二元信道：一种最简单的逻辑信道（信源编码器），信道的基本符号集为{0，1}，输入、输出符号都只有这两种取值。二元信源：信源输出符号只有这两种取值。6.1单义可译码2013秋季信息1110InfTheory&Coding-张祖平11码1：W(1)码2：W(2)码3：W(3)码4：W(4)码5：W(5)00011100110010010100001011110000001奇异码非奇异码：若一组码中所有码字都不相同(即所有信源符号映射到不同的码符号序列，不同信源符号可分辨)，则称为非奇异码。奇异码：反之，若码组中含有相同的码字则为奇异码。6.1单义可译码2013秋季信息1111InfTheory&Coding-张祖平12码1：W(1)码2：W(2)码3：W(3)码4：W(4)码5：W(5)000111001100100101000010111100000016.1单义可译码

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

非奇异的等长码一定是单义可译码都是非奇异的且都是单义可译码6.1单义可译码2013秋季信息1114InfTheory&Coding-张祖平15码4：W(4)码5：W(5)11100110000110000001W4，W5都是非奇异的且都是单义可译码非即时码：如果接收端收到一个完整的码字后不能立即译码，必须结合后续的码元序列才能进行译码，称为非即时码。如码4，收到10无法判断结束。即时码：在译码时，如果当前已经接收到一个完整的码元序列之后，无需参考后续的码元符号、立即能够确定对应的码字，这种码制称为即时码。如码5，每个码字最后符号都是1，收到1好像逗(点)号，又叫逗号(点)码。6.2非延长码2013秋季信息1115InfTheory&Coding-张祖平16码4：W(4)码5：W(5)11100110000110000001异前缀码/非延长码：即时码要求任何一个码字都不是其他码字的前缀部分，所以也叫做异前缀码/非延长码，反之就叫延长码。即时码（异前缀码）一定可以单义可译码。因为，如果没有一个码字是其他码字的前缀，则在译码过程中，当收到一个完整码字的码符号序列时，无需考虑下一个符号，就能直接把它译成对应的码字或信源符号。所有码非奇异码单义可译码即时码6.2非延长码2013秋季信息1116InfTheory&Coding-张祖平17怎样构建非延长码？可用“树图法/码树”来构建非延长码

6.2非延长码2013秋季信息1117InfTheory&Coding-张祖平q=4,r=2,n1=1,n2=2,n3=3,n4=401得到一阶节点标记每条树枝树枝数为rW1可以二选一186.2非延长码2013秋季信息1118InfTheory&Coding-张祖平q=4,r=2,n1=1,n2=2,n3=3,n4=4010011该选哪个节点？196.2非延长码2013秋季信息1119InfTheory&Coding-张祖平q=4,r=2,n1=1,n2=2,n3=3,n4=4010011该选哪个节点？206.2非延长码2013秋季信息1120InfTheory&Coding-张祖平q=4,r=2,n1=1,n2=2,n3=3,n4=4010011011216.2非延长码2013秋季信息1121InfTheory&Coding-张祖平q=4,r=2,n1=1,n2=2,n3=3,n4=4010011011w1=1w2=01w3=001w4=0001未用尽226.2非延长码2013秋季信息1122InfTheory&Coding-张祖平q=4,r=2,n1=1,n2=2,n3=3,n4=40101011w1=1w2=01w3=001w4=0001未用尽236.2非延长码2013秋季信息1123InfTheory&Coding-张祖平24根：树的最上端树枝的个数为r，r=2为二元码树01001111010010001码5的树图ABCD中间节点（空心）节点：树枝的终端，从节点生出树枝，每个节点伸出r个枝终端节点（实心）码字：从根到终端节点对应的码符号，又称树叶q=4,r=2,n1=1,n2=2,n3=3,n4=4w1=1w2=01w3=001w4=00016.2非延长码2013秋季信息1124InfTheory&Coding-张祖平25该树的5个终端节点W1,W2,W3,W4,W5分别表示5个二进制码字0，100，111，1010，1011码树的性质：任一即时码都可用树图表示。即时码不是惟一的。单义可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀，按树图法构成的码一定满足即时码的充要条件，因为从根到叶所走的路径各不相同，而且中间节点不安排为码字，所以一定满足对前缀的限制。6.2非延长码2013秋季信息1125InfTheory&Coding-张祖平26满树——

每个码字的联枝数均相同时(定长码)非满树——

当码字的联枝数不同时(变长码)全树——

每个中间节点的后续分支数均为m

非全树——

有些中间节点的后续分支数不足m满树非全树树根终节点中间节点非满树，全树6.2非延长码2013秋季信息1126InfTheory&Coding-张祖平27012012012012012012三进制码树6.2非延长码2013秋季信息1127InfTheory&Coding-张祖平练习28S：｛s1，s2，…，s9｝，A=｛0，1，2｝，q=36.2非延长码2013秋季信息1128InfTheory&Coding-张祖平29设原始信源符号集为S:{S1,S2,…Sq}，码元符号集为x:{x1,x2,…,xr}，码字集合为W:{W1,W2,…Wq}，其码长分别为L1,L2,…,Lq；则单义可译码存在的充要条件为码长组合满足Kraft不等式，即：

r是码元进制数q是信源符号数l为码字长度。

例：设二进制码树中X(a1，a2，a3，a4)，码长L1＝1，L2＝2，L3＝2，L4＝3，应用上述判断定理：不存在满足这种Li的单义可译码6.3单义可译定理2013秋季信息1129InfTheory&Coding-张祖平30例：设二进制码树中X(a1，a2)，码长L1＝1，L2＝2，L3＝3，L4＝3，应用上述判断定理：a1=1

01

01

01a2=01a3=001a4=000这种Li的单义可译码是存在的用树的方式尝试构造，叶节点如{1，01，001，000}

单义可译码；但不能作为单义可译码的判据，如{1，01，101，000}不是单义可译码；6.3单义可译定理2013秋季信息1130InfTheory&Coding-张祖平关于Kraft不等式满足Kraft不等式的码长组合一定能构成至少一种单义可译码。单义码的码长组合一定满足Kraft不等式，否则无法构成单义可译码。有些码字的码长组合虽满足Kraft不等式，但不是单义可译码。Kraft不等式不能用来判断是否是单义可译码，但不满足该不等式的一定不是单义可译码。316.3单义可译定理2013秋季信息1131InfTheory&Coding-张祖平练习32这些码中哪些是单义可译码？哪些码是非延长码？6.3单义可译定理2013秋季信息1132InfTheory&Coding-张祖平练习33C2不是即时码C5不是唯一可译码，C5是奇异码又根据码树构造码字的方法

C1，C3，C6的码字均处于终端节点他们是即时码C4不全是终端节点6.3单义可译定理2013秋季信息1133InfTheory&Coding-张祖平通信的有效性单义可译码、非延长码解决了编码的一一对应和即时译码问题。人们还要求提高通信的效率，希望通信中每个码能携带更多信息量。对于已知信源S可用码符号X进行变长编码，而且对同一信源可有多种非延长码或单义可译码。选择哪一种最好呢？因此我们结合信源空间、信源熵引出了平均码长。34信源空间信源熵6.4平均码长与有效性2013秋季信息1134InfTheory&Coding-张祖平35

见书上例题。概率大的信源符号要用码长小的码字，概率小的信源符号要用码长大的码字6.4平均码长与有效性2013秋季信息1135InfTheory&Coding-张祖平练习36平均码长3.14比特/符号，信息传输率0.8309平均码长2.74比特/符号，信息传输率0.9522计算平均码长和信息传输率6.4平均码长与有效性2013秋季信息1136InfTheory&Coding-张祖平紧致码（最佳码）对于某一信源和某一码符号集来说，若有一个单义可译码，其平均长度小于所有其他单义可译码的平均长度，称为紧致码（最佳码）。无失真信源编码的基本问题转化为找出紧致码（最佳码）。最佳码也就是紧致码的平均长度不是可以无限制缩小的，在理论上是有它的极限值的（在无失真信源编码的条件下）37

6.5平均码长界限定理2013秋季信息1137InfTheory&Coding-张祖平38

上界下界证明与例题见书6.5平均码长界限定理2013秋季信息1138InfTheory&Coding-张祖平39

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

6.5平均码长界限定理2013秋季信息1140InfTheory&Coding-张祖平41

6.6香农码2013秋季信息1141InfTheory&Coding-张祖平421.将信源符号按概率排序：p(a1)≥p(a2)≥…≥p(an)；2.计算第i个码字(之前)的累加概率pa(xj)3.确定第i个码字的码长ni(整数)：-log2p(xi)≤

ni

＜1-log2p(xi)4.将累加概率pa(xj)变为二进制数，并取小数点后ni位，即为ai的编码[说明]j=1时，pa(a1)=p(a0)=0 j=2时，pa(a2)=p(a1)+p(a0)=p(a1) j=3时，pa(a3)=p(a2)+p(a1)+p(a0)

因而pa(aj)表示：aj之前(不含aj)的各概率之和6.6香农码2013秋季信息1142InfTheory&Coding-张祖平第四步举例累加概率Pi=0.57，变成二进制数，为0.1001…。转换的方法是：用Pi乘以2，如果整数部分有进位，则小数点后第一位为1，否则为0，将其小数部分再做同样的处理，得到小数点后的第二位，依此类推，直到得到了满足要求的位数，或者没有小数部分了为止。对应结果：现在Pi=0.57，乘以2为1.14，整数部分有进位，所以小数点后第一位为1，将小数部分即0.14再乘以2，得0.28，没有整数进位，所以小数点后第二位为0，依此类推，可得到其对应的二进制数为0.1001…。436.6香农码2013秋季信息1143InfTheory&Coding-张祖平44例:有一单符号离散无记忆信源，编二进制香农码6.6香农码2013秋季信息1144InfTheory&Coding-张祖平450001100101110111110可以看出，编码所得的码字，没有相同的，所以是非奇异码也没有一个码字是其它码字的前缀，所以是即时码（非延长码），也是单义可译码。用树图构造出来可以看出符合非延长码特点。平均信息传输率平均码长与信息熵香农码编码效率并不是很高，不是最佳码，为什么？图上可以看出来吗？码符号/信源符号

6.6香农码2013秋季信息1145InfTheory&Coding-张祖平练习46信源共有7个符号组成，其概率如表所示，求二进制香农码，平均码长和信息传输率。信源消息符号xi符号概率p(xi)x1

0.20x2

0.19x3

0.18x4

0.17x5

0.15x6

0.10x7

0.016.6香农码2013秋季信息1146InfTheory&Coding-张祖平47xip(xi)累加Pi-log2

p(xi)码字长度Ki码字x10.2002.343000x20.190.22.413001x30.180.392.483011x40.170.572.563100x50.150.742.743101x60.100.893.3441110x70.010.996.66711111106.6香农码2013秋季信息1147InfTheory&Coding-张祖平48费诺编码也是一种常见的信源编码方法。编码步骤如下：(1)将概率按从大到小的顺序排列，令

p(a1)≥p(a2)≥…≥p(an)(2)按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编m进制码就分成m组。(3)给每一组分配一位码元。(4)将每一分组再按同样原则划分，重复步骤2和3，直至概率不再可分为止。6.7费诺码2013秋季信息1148InfTheory&Coding-张祖平49例设有一单符号离散信源,对该信源编二进制费诺码。二进制费诺编码

信源符号

概率

编码

码字

码长

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秋季信息1149InfTheory&Coding-张祖平50该信源的熵为平均码长为编码效率为本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。6.7费诺码2013秋季信息1150InfTheory&Coding-张祖平51题中码字还可用码树来表示，如图所示。6.7费诺码2013秋季信息1151InfTheory&Coding-张祖平练习52信源共有7个符号组成，其概率如表所示，求二进制费诺码，平均码长和信息传输率。信源消息符号xi符号概率p(xi)x1

0.20x2

0.19x3

0.18x4

0.17x5

0.15x6

0.10x7

0.016.7费诺码2013秋季信息1152InfTheory&Coding-张祖平练习53消息符号ai各个消息概率p(ai)第一次分组第二次分组第三次分组第四次分组二元码字码长Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.011111146.7费诺码2013秋季信息1153InfTheory&Coding-张祖平练习54信源共有8个符号组成，其概率如表所示，求二进制费诺码，平均码长和信息传输率。6.7费诺码2013秋季信息1154InfTheory&Coding-张祖平练习55平均码长

编码效率信源熵H(X)=2.75bit/sign每次两分组的概率正好相等，效率最高6.7费诺码2013秋季信息1155InfTheory&Coding-张祖平香农码与费诺码总结香农第一编码定理给出了码字的平均长度的下界和上界。但并不是说大于这上界不能构成单义可译码，而是因为我们总是希望尽可能短。也就是说，定理给出的是最佳码（比其他单义可译码平均码长都小的编码）的最短平均码长的下界和上界，并指出这个最短的平均码长与信源熵是有关的。无失真信源编码的基本问题转化为找出紧致码（最佳码）。最佳编码基本思想：将概率大的信息符号编以短的码字，概率小的符号编以长的码字。最佳码的编码主要方法：香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码等。香农码：编码唯一，但通常效率不高，学术意义大于实际意义；费诺码：由于赋码元时的任意性，因此编出的码字不是唯一的；构造码树时自顶向下；编码效率高于香农码，适合于对分组概率相等或接近的信源编码；香农码和费诺码都不是真正意义上的最佳码，哈夫曼编码实现了最佳编码。566.7费诺码2013秋季信息1156InfTheory&Coding-张祖平57哈夫曼1953年于MIT获得科学博士学位哈夫曼编码是1951年，他在研究生阶段课程（信息论与编码）的课程大作业中提出的，哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树，该算法广泛应用于数据压缩和计算机安全领域。离开MIT后，哈夫曼来到加利福尼亚大学的计算机系任教。哈夫曼从未为此算法申请过专利或其它相关能够为他带来经济利益的东西，他将他全部的精力放在教学上，以他自己的话来说，“我所要带来的就是我的学生。”DavidA.Huffman(1925-1999)6.8Huffman编码2013秋季信息1157InfTheory&Coding-张祖平还记得数据结构中的哈夫曼码吗？？哈夫曼编码是最佳码（即平均码长最小）怎么证明这一点？哈夫曼在1952年的原始论文中并没有给出证明后人给出了不同的证明方法特点：自底向上构造码树把码长小的码字分配给出现频率高的信源字符在编码过程中需要构造虚拟节点每次缩减信源的最长两个码字有相同的码长。586.8Huffman编码2013秋季信息1158InfTheory&Coding-张祖平(1)将信源符号按概率从大到小的顺序排列，令

p(a1)≥p(a2)≥…≥p(an)(2)给两个概率最小的信源符号p(an-1)和p(an)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(q－1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。(3)将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(q－2)个符号的缩减信源S2。(4)重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。596.8Huffman编码2013秋季信息1159InfTheory&Coding-张祖平600.40.4

0.4

0.61.00.20.2

0.4

0.40.20.2

0.20.10.2

0.110101010aip(ai)码字Wi1a10.40a20.210a30.2111a40.11101a50.111006.8Huffman编码2013秋季信息1160InfTheory&Coding-张祖平61

码元/符号

平均码长、编码效率aip(ai)码字Wi1a10.40a20.210a30.2111a40.11101a50.111006.8Huffman编码2013秋季信息1161InfTheory&Coding-张祖平620.40.4

0.4

0.61.00.20.2

0.4

0.40.20.2

0.20.10.2

0.101010101aip(ai)码字Wi2a10.41a20.201a30.2000a40.10010a50.1001101106.8Huffman编码2013秋季信息1162InfTheory&Coding-张祖平63aip(ai)码字Wi2a10.41a20.201a30.2000a40.10010a50.10011

码元/符号

平均码长、编码效率6.8Huffman编码2013秋季信息1163InfTheory&Coding-张祖平64aip(ai)码字Wi3a10.400a20.210a30.211a40.1010a50.10110.40.4

0.4

0.61.00.20.20.40.40.20.2

0.20.10.20.1010101016.8Huffman编码2013秋季信息1164InfTheory&Coding-张祖平65

码元/符号

平均码长、编码效率aip(ai)码字Wi3a10.400a20.210a30.211a40.1010a50.10116.8Huffman编码2013秋季信息1165InfTheory&Coding-张祖平哈夫曼编码形式不是唯一的，用方差选择较好的编码由于0，1顺序可以不同，导致不一样由于出现合并后等概率情况，排序位置不同，导致不一样aip(ai)码字Wi1码字Wi2码字Wi3a10.40100a20.2100110a30.211100011a40.111010010010a50.111000011011W2和w3编码的方差不同，进行哈夫曼编码时，为得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。

方差越小，说明各个码的长度都比较接近平均长度，这样编码器和解码器就可以比较简单6.8Huffman编码2013秋季信息1166InfTheory&Coding-张祖平练习信源共有7个符号组成，其概率如表所示，求二进制哈夫曼编码，平均码长和信息传输率。信源消息符号xi符号概率p(xi)x1

0.20x2

0.19x3

0.18x4

0.17x5

0.15x6

0.10x7

0.016.8Huffman编码2013秋季信息1167InfTheory&Coding-张祖平练习680.20 0.200.260.350.390.611.00.190.190.200.260.350.390.180.180.190.200.260.170.170.180.190.150.150.170.100.110.010101010101016.8Huffman编码2013秋季信息1168InfTheory&Coding-张祖平练习69信源符号符号概率编码过程码字码长0.201020.191120.1800030.1700130.1501030.10011040.0101114010.200.190.180.170.150.110.260.200.190.180.1701010.260.350.200.19010.350.260.39010.390.61016.8Huffman编码2013秋季信息1169InfTheory&Coding-张祖平练习700.010.100.110.150.260.170.180.350.610.190.200.39

1011001011001采用码树形式进行哈夫曼编码的过程中，由于代表信源符号的节点都是终端节点，因此其编码不可能是其它终端节点对应的编码的前缀。哈夫曼编码一定是非延长码。哈夫曼编码总是把概率大的符号安排在离根节点近的终端节点，所以平均码长短。6.8Huffman编码2013秋季信息1170InfTheory&Coding-张祖平多元Huffman编码平均码长=2*0.24+2*0.2+2*0.18+2*0.16+2*0.14+2*0.08=2码符号/信源符号定长编码？这样编码效率高吗？为什么？6.8Huffman编码2013秋季信息1171InfTheory&Coding-张祖平72012012012012w1w2w3w4w5w6？很明显可以使用“0”这个短码来作为概率最大的S1的编码，为什么编码结果却没有用到呢？因为最后一次缩减，没有把码符号集中所有符号都用上，最后一次缩减是针对大概率信源符号的，是短码，短码没有充分利用，反而优先把小概率的信源符号，是长码，用上了所有码符号集中的符号。多元Huffman编码6.8Huffman编码2013秋季信息1172InfTheory&Coding-张祖平7312012012012012012非全树全树m进制的全树的终端叶节点数(码个数)m+k(m-1),k=0,1,2,….(每从一个节点分出m枝,就增加m-1个终端)当信源符号数n，n<m+k(m-1)时，令s=[m+k(m-1)]-n,s<m-1，为构成全树所缺少的码字(分支)数，必须在信源符号集合中补上概率为0的s个虚假符号w1w2w3w4w5w6多元Huffman编码6.8Huffman编码2013秋季信息1173InfTheory&Coding-张祖平74m