信息论与编码Inf-T-C-6.5

信息论与编码张祖平/ZhangZuping电子信息工程系SchoolofInformationScienceandEngineering,CentralSouthUniversity,[e-mail]&Coding2013秋季信息11InfTheory&Coding-张祖平2本章主要内容(MainContent)6.1单义可译码6.2非延长码6.3单义可译定理6.4平均码长与有效性6.5平均码长的界限定理6.8霍夫曼（Huffman）编码6.0编码概述6.6香农码6.7费诺码2013秋季信息11InfTheory&Coding-张祖平3信源信源编码信道编码信道译码信源译码信宿信道6.0编码概述2013秋季信息11InfTheory&Coding-张祖平44•生活中编码实例?学号、身份证号码、一卡通、汉语等编码。•编码实质：信息的组织方式。对信源的原始符号按一定的数学规则进行变换。•结论:信息无处不在，编码无处不在。6.0编码概述2013秋季信息11InfTheory&Coding-张祖平5•通信的基本问题：–通信的基本问题：如何高速、高质地传送信息。–高速和高质＝有效性和可靠性。•通信的还需要解决的问题：–1：解决信源发出的消息不适合信道的传输，信源编码–2：希望信道可以尽快的传输信息，信源编码的编码效率–3：信道中有噪声，进入信道以前需要加入抗干扰能力，信道编码•总结得到：–信息质量一定时，如何提高信息传输速度（提高编码效率或压缩比）----信源编码（本章讨论问题），提高信息传输的有效性。–信道传输速度一定时，如何提高信息传输质量（抗干扰能力），----信道编码（下一章讨论），提高信息传输的可靠性。56.0编码概述2013秋季信息11InfTheory&Coding-张祖平6•信源编码定义–将信源输出的消息符号进行有效变换，使其成为适合信道传输的符号序列，且使该序列组成的新信源的冗余度尽可能地减少。•信源编码目的–符号变换：使信源输出符号与信道的输入符号相匹配。–减少冗余：提高通信的有效性，就是针对信源输出符号序列的统计特性，寻找一定的把信源输出符号序列变换为最短码字序列的方法。•信源编码基本方法–（1）解除相关性：使序列中的各个符号尽可能地互相独立。比如：一个英文单词视为系列符号从而消除单词内部字母之间的相关性。–（2）概率均匀化：使编码中各个符号出现的概率尽可能地相等，尽可能缩短出现概率大的信源符号的码字，压缩每个信源符号的平均比特数。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。66.0编码概述2013秋季信息11InfTheory&Coding-张祖平7•信源编码的两大定理–信源编码理论是信息论的一个重要分支，其理论基础是两个定理。–无失真信源编码定理：是离散信源/数字信号编码的基础；无失真编码是可逆的，即当信源符号变换成代码以后，可以从代码无失真地恢复出原信源符号。–限失真信源编码定理：是连续信源/模拟信号编码的基础，如语音、图像等信号。在连续信源的情况下，由于信源的信息量趋于无限，显然不能用离散符号序列来完成无失真编码，而只能进行限失真编码。•香农信息论三大定理–无失真信源编码定理为第一极限定理；–信道编码定理（离散和连续信道）称为第二极限定理；–限失真信源编码定理称为第三极限定理。76.0编码概述2013秋季信息11InfTheory&Coding-张祖平8•编码器的数学模型8编码器可以看作这样一个系统，它的输入端为原始信源S，其符号集为；而信道所能传输的符号集为。编码器的功能是用符号集X中的元素，将原始信源的符号变换为相应的码字符号，所以编码器输出端的符号集为称为码字，为码字的码元个数，称为码字的码字长度，简称码长。码字的集合C称为码书。称为码元。12{,,...,}qSSSS12{,,...,}rXxxx12{,,...,}qSsss12{,,...,}rXxxx编码器12:{,,...,}qC{,,...,}qC张祖平9•单义可译码–若码的任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列，则此码称为惟一可译码（单义可译码）–否则就称为非惟一可译码或非单义可译码。•比如：–信源S的符号集是英文字母和标点–而信道只能传输0,1序列，即信道要求的信源其符号集只能包含0和1•我们需要用0和1组成的码字来表示S中的英文字母和标点–要求1：码字要与S中的每种字符一一对应–要求2：码字序列要与S的N个符号组成的序列一一对应6.1单义可译码2013秋季信息11InfTheory&Coding-张祖平1010码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秋季信息11InfTheory&Coding-张祖平1111码1：W(1)码2：W(2)码3：W(3)码4：W(4)码5：W(5)00011100110010010100001011110000001奇异码非奇异码：若一组码中所有码字都不相同(即所有信源符号映射到不同的码符号序列，不同信源符号可分辨)，则称为非奇异码。奇异码：反之，若码组中含有相同的码字则为奇异码。6.1单义可译码2013秋季信息11InfTheory&Coding-张祖平1212码1：W(1)码2：W(2)码3：W(3)码4：W(4)码5：W(5)000111001100100101000010111100000016.1单义可译码2013秋季信息11InfTheory&Coding-张祖平1313码1：W(1)码2：W(2)码3：W(3)码4：W(4)码5：W(5)00011100110010010100001011110000001定长码（等长码）：若一组码中所有码字的码长都相同，则称为定长码。因为长度相同，相当于每个码字后有一个无形的逗号(点),又叫逗号(点)码。变长码：若一组码中所有码字的码长各不相同，则称为变长码。非奇异的等长码一定是单义可译码6.1单义可译码2013秋季信息11InfTheory&Coding-张祖平1414码1：W(1)码2：W(2)码3：W(3)码4：W(4)码5：W(5)00011100110010010100001011110000001奇异码非奇异的等长码一定是单义可译码都是非奇异的且都是单义可译码6.1单义可译码2013秋季信息11InfTheory&Coding-张祖平1515码4：W(4)码5：W(5)11100110000110000001W4，W5都是非奇异的且都是单义可译码非即时码：如果接收端收到一个完整的码字后不能立即译码，必须结合后续的码元序列才能进行译码，称为非即时码。如码4，收到10无法判断结束。即时码：在译码时，如果当前已经接收到一个完整的码元序列之后，无需参考后续的码元符号、立即能够确定对应的码字，这种码制称为即时码。如码5，每个码字最后符号都是1，收到1好像逗(点)号，又叫逗号(点)码。6.2非延长码2013秋季信息11InfTheory&Coding-张祖平1616码4：W(4)码5：W(5)11100110000110000001异前缀码/非延长码：即时码要求任何一个码字都不是其他码字的前缀部分，所以也叫做异前缀码/非延长码，反之就叫延长码。即时码（异前缀码）一定可以单义可译码。因为，如果没有一个码字是其他码字的前缀，则在译码过程中，当收到一个完整码字的码符号序列时，无需考虑下一个符号，就能直接把它译成对应的码字或信源符号。所有码非奇异码单义可译码即时码6.2非延长码2013秋季信息11InfTheory&Coding-张祖平1717怎样构建非延长码？可用“树图法/码树”来构建非延长码6.2非延长码2013秋季信息11InfTheory&Coding-张祖平18•q=4,r=2,n1=1,n2=2,n3=3,n4=401得到一阶节点标记每条树枝树枝数为rW1可以二选一186.2非延长码2013秋季信息11InfTheory&Coding-张祖平19•q=4,r=2,n1=1,n2=2,n3=3,n4=4010011该选哪个节点？196.2非延长码2013秋季信息11InfTheory&Coding-张祖平20•q=4,r=2,n1=1,n2=2,n3=3,n4=4010011该选哪个节点？206.2非延长码2013秋季信息11InfTheory&Coding-张祖平21•q=4,r=2,n1=1,n2=2,n3=3,n4=4010011011216.2非延长码2013秋季信息11InfTheory&Coding-张祖平22•q=4,r=2,n1=1,n2=2,n3=3,n4=4010011011w1=1w2=01w3=001w4=0001未用尽226.2非延长码2013秋季信息11InfTheory&Coding-张祖平23•q=4,r=2,n1=1,n2=2,n3=3,n4=40101011w1=1w2=01w3=001w4=0001未用尽236.2非延长码2013秋季信息11InfTheory&Coding-张祖平2424根：树的最上端树枝的个数为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秋季信息11InfTheory&Coding-张祖平2525该树的5个终端节点W1,W2,W3,W4,W5分别表示5个二进制码字0，100，111，1010，1011码树的性质：任一即时码都可用树图表示。即时码不是惟一的。单义可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀，按树图法构成的码一定满足即时码的充要条件，因为从根到叶所走的路径各不相同，而且中间节点不安排为码字，所以一定满足对前缀的限制。6.2非延长码2013秋季信息11InfTheory&Coding-张祖平2626满树——每个码字的联枝数均相同时(定长码)非满树——当码字的联枝数不同时(变长码)全树——每个中间节点的后续分支数均为m非全树——有些中间节点的后续分支数不足m满树非全树树根终节点中间节点非满树，全树6.2非延长码2013秋季信息11InfTheory&Coding-张祖平2727012012012012012012三进制码树6.2非延长码2013秋季信息11InfTheory&Coding-张祖平28练习28S：｛s1，s2，…，s9｝，A=｛0，1，2｝，q=36.2非延长码2013秋季信息11InfTheory&Coding-张祖平2929•设原始信源符号集为S:{S1,S2,…Sq}，码元符号集为x:{x1,x2,…,xr}，码字集合为W:{W1,W2,…Wq}，其码长分别为L1,L2,…,Lq；则单义可译码存在的充要条件为码长组合满足Kraft不等式，即：11qilirr是码元进制数q是信源符号数l为码字长度。例：设二进制码树中X(a1，a2，a3，a4)，码长L1＝1，L2＝2，L3＝2，L4＝3，应用上述判断定理：41223192222218iLi不存在满足这种Li的单义可译码6.3单义可译定理201