信息论基础理论与应用第三版傅祖芸第5章讲义课件

信息论基础理论与应用第三版傅祖芸第5章讲义信息论基础理论与应用第三版傅祖芸第5章讲义 信息通过信道传输到信宿的过程。要做到既不失真又信息通过信道传输到信宿的过程。要做到既不失真又快速地通信，需要解决两个问题：快速地通信，需要解决两个问题：n信源编码信源编码:在不失真或允许一定失真条件下，提高在不失真或允许一定失真条件下，提高信息传输率信息传输率.n信道编码信道编码:在信道受到干扰的情况下，增加信号的在信道受到干扰的情况下，增加信号的抗干扰能力抗干扰能力，同时，同时又使得信息传输率最大又使得信息传输率最大.n最佳编码：最佳编码：一般来说，一般来说，抗干扰能抗干扰能与与信息传输率信息传输率二者相互矛盾。二者相互矛盾。而编码定理理论上证明，至少存在某种而编码定理理论上证明，至少存在某种最佳最佳的编码能够解决上的编码能够解决上述矛盾，做到述矛盾，做到既可靠又有效既可靠又有效地传输信息。地传输信息。n信源编码：信源编码：信源虽然多种多样，但无论是哪种类型的信源，信信源虽然多种多样，但无论是哪种类型的信源，信源符号之间总存在相关性和分布的不均匀性，使得信源存在冗源符号之间总存在相关性和分布的不均匀性，使得信源存在冗余度。余度。信源编码的目的就是要减少冗余，提高编码效率。信源编码的目的就是要减少冗余，提高编码效率。引引 言言 信息通过信道传输到信宿的过程。要做到既n研究方法研究方法研究研究信源编码信源编码时，将信道编码与译码看成是时，将信道编码与译码看成是信道信道的一部分，的一部分，从而突出信源编码；从而突出信源编码；研究研究信道编码信道编码时，将信源编码与译码看成是时，将信源编码与译码看成是信源与信宿信源与信宿的的一部分，从而突出信道编码。一部分，从而突出信道编码。5.1 5.1 编码器编码器n编码器：编码器：对信源的符号按一定的数学规则进行的变换。对信源的符号按一定的数学规则进行的变换。它可以看作这样一个系统，它的输入端为原始信源它可以看作这样一个系统，它的输入端为原始信源S S，其，其符号集为符号集为 而信道所能传输的符号集为而信道所能传输的符号集为 研究方法5.1 编码器编码器：编码器功能：编码器功能：用符号集用符号集X X中的元素，将原始信源中的元素，将原始信源的符号的符号 变换为相应的码字符号变换为相应的码字符号 ，编码器输出符，编码器输出符号集为号集为 (码或码书码或码书)称为称为码字码字，l li i 为码字为码字 的码元个数（码字的码元个数（码字长度，长度，码长码长）。码字集合）。码字集合C C称为称为码码或或码书码书。信息论基础理论与应用第三版傅祖芸第5章讲义课件 若要实现无失真编码，这种映射应是若要实现无失真编码，这种映射应是一一对应的可一一对应的可逆映射。逆映射。n编码的形式化描述：编码的形式化描述：从从信源符号信源符号到到码符号码符号的一种映射的一种映射或：或：若要实现无失真编码，这种映射应是一一对应的可逆映1 1、二元码与二元码与r r元码元码 2 2元码元码:码符号集码符号集X=0,1.X=0,1.如果将信源通过二元信道传如果将信源通过二元信道传输，必须将信源编成二元码，这是最常用的一种码。输，必须将信源编成二元码，这是最常用的一种码。r r元码元码:码符号集有码符号集有r r个符号的编码。个符号的编码。2 2、等长码与变长码等长码与变长码 等长码等长码:一组码中所有码字的长度都相同。一组码中所有码字的长度都相同。变长码变长码:一组码中所有码字的长度各不相同。一组码中所有码字的长度各不相同。n 码的分类及定义码的分类及定义信源符号信源符号sisi符号出现概率符号出现概率p p(si)(si)编码编码1 1编码编码2 2s1s1p p(s1)(s1)00000 0s2s2p p(s2)(s2)01010101s3s3p p(s3)(s3)1010001001s4s4p p(s4)(s4)11111011011、二元码与r元码 码的分类及定义信源符号si符号出现概率p3 3、非奇异码与奇异码非奇异码与奇异码 非奇异码非奇异码:一组码中所有码字都不相同。一组码中所有码字都不相同。奇异码奇异码:一组码中有相同的码字。一组码中有相同的码字。信源符号信源符号 编码编码1 1编码编码2 21/21/200000 01/41/401010 01/81/810101 11/81/8111110103、非奇异码与奇异码信源符号 编码1编码21/20001/44 4、同价码同价码 同价码同价码:码符号集码符号集 中每个码符号所占的中每个码符号所占的传输时间传输时间都相同都相同(大多数情况大多数情况)。变长码中每个码字的传输时间就不一定相同。变长码中每个码字的传输时间就不一定相同。（摩尔斯电报码，（摩尔斯电报码，点点-划划 所占传输时间不同）所占传输时间不同）5 5、码的码的N N次扩展次扩展 若某码若某码 C C，它把信源，它把信源S S中的符号中的符号 一一变换成码一一变换成码C C中中的码字的码字 ，则，则码码C C的的N N次扩展码次扩展码是所有是所有N N个码字组成的码个码字组成的码字序列的集合字序列的集合B:B:S扩展扩展4、同价码S扩展码码C C码码B B扩展信源扩展信源扩展码扩展码N N次扩展次扩展N N次扩展次扩展码C码B扩展信源扩展码N次扩展N次扩展 例例 设信源设信源S S的概率空间为：的概率空间为：若通过若通过个二元信道进行传输，须把信源符号变换成个二元信道进行传输，须把信源符号变换成 0 0，1 1 符号组成的码符号序列符号组成的码符号序列(二元序列二元序列)。采用如下二元码，。采用如下二元码，如下如下表所示（表所示（q=4q=4）：）：信源符号信源符号s si i符号出现概率符号出现概率P(sP(si i)码码s s1 1P(sP(s1 1)0 0s s2 2P(sP(s2 2)0101s s3 3P(sP(s3 3)001001s s4 4P(sP(s4 4)111111试求码的二次扩展码。试求码的二次扩展码。例 设信源S的概率空间为：若通过个二信信源源S S的的二次扩展信源二次扩展信源：则则码码的的二次扩展码二次扩展码为：为：信源信源符号符号码字码字信源信源符号符号码字码字信源信源符号符号码字码字1 100:W00:W1 1W W1 1=B=B1 15 5010:W010:W2 2W W1 1=B=B5 5：2 2001:W001:W1 1W W2 2=B=B2 2：3 30001:W0001:W1 1W W3 3=B=B3 3：4 40111:W0111:W1 1W W4 4=B=B4 4：1616111111:W111111:W4 4W W4 4=B=B1616信源S的二次扩展信源：则码的二次扩展码为：信源符号码字信源符6 6、唯一可译码、唯一可译码(单义可译码单义可译码）由码构成的任意一串有限长的由码构成的任意一串有限长的码符号序列码符号序列只能被唯只能被唯一的译成所对应的一的译成所对应的信源符号序列信源符号序列。否则否则,就为非惟一可译码或非单义可译码。就为非惟一可译码或非单义可译码。n例例：对于二元码：对于二元码 ，当，当任意给定一串任意给定一串码字序列码字序列，例如，例如1000110110001101只可唯一地划分为只可唯一地划分为1,00,01,1,011,00,01,1,01，因此是，因此是惟一可译码惟一可译码；n而对另一个二元码而对另一个二元码 ，当码字序列为当码字序列为0100101001可划分为可划分为0,10,010,10,01或或01,0,0101,0,01，所以是，所以是非惟一可译的非惟一可译的。6、唯一可译码(单义可译码）例：对于二元码 n唯一可译码的条件唯一可译码的条件 1 1）不同的信源符号变换成不同的码字）不同的信源符号变换成不同的码字(非奇异码非奇异码)；2 2）任意有限长任意有限长的的信源序列信源序列所对应的所对应的码元序列码元序列各不相同各不相同.即即:码的任意有限长码的任意有限长N N次扩展码次扩展码都是都是非奇异码非奇异码。Or:码符号序列码符号序列的的反变换反变换也唯一的（也唯一的（扩展码非奇异扩展码非奇异）原因：原因：若要使某一码为惟一可译码，则对于任意有限若要使某一码为惟一可译码，则对于任意有限长的长的码符号序列码符号序列，必须只能被，必须只能被惟一地分割惟一地分割成一个个的码字，成一个个的码字，才能实现唯一的译码。才能实现唯一的译码。唯一可译码的条件n无失真的编码的一般条件无失真的编码的一般条件 1 1）码字与信源符号之间一一对应（）码字与信源符号之间一一对应（非奇异码非奇异码）；）；2 2）码符号序列码符号序列的的反变换反变换也唯一的（也唯一的（扩展码非奇异扩展码非奇异）。）。即即：编码必须是：编码必须是唯一可译码唯一可译码。否则，就会引起译码的错。否则，就会引起译码的错误与失真。误与失真。等长码是唯一可译码的条件等长码是唯一可译码的条件 若等长码是若等长码是非奇异码非奇异码，则它的任意有限长，则它的任意有限长N N次次扩展码扩展码一定也是非奇异码。一定也是非奇异码。因此，因此，等长非奇异码字等长非奇异码字一定是一定是唯一可译码唯一可译码,因为因为采用固定长度划分码字序列采用固定长度划分码字序列.5.2 5.2 等长码等长码无失真的编码的一般条件5.2 等长码 1 1）若对）若对每个信源符号每个信源符号进行等长编码，则必须满进行等长编码，则必须满足足:其中其中:l:l是码长，是码长，r r是码符号集的码元数，是码符号集的码元数，q q信源符号数。信源符号数。2 2）若对）若对信源的信源的N N次扩展信源次扩展信源进行编码，必须满进行编码，必须满足足:表示平均表示平均每个信源符号每个信源符号所需的所需的码符号个数。码符号个数。即即 为了使等长码为非奇异码（唯一可译码），那为了使等长码为非奇异码（唯一可译码），那么么:1）若对每个信源符号进行等长编码，则必须满足:例证：根据依赖关系，信源符号平均所需码符号数可减少。例证：根据依赖关系，信源符号平均所需码符号数可减少。例例 设信源设信源而其依赖关系为：而其依赖关系为：1 1）若不考虑符号间的依赖关系，可得每符号码长）若不考虑符号间的依赖关系，可得每符号码长l l2 2；2 2）若考虑符号间的）若考虑符号间的二元依赖关系二元依赖关系，可作二次扩展信源进行，可作二次扩展信源进行分析。根据条件概率仅有分析。根据条件概率仅有4 4项的概率不为零，可得扩展信源项的概率不为零，可得扩展信源的码长的码长 l=2l=2，而每个信源符号的，而每个信源符号的平均码长平均码长为为 l/N=1l/N=1 。例证：根据依赖关系，信源符号平均所需码符号数可减少。而其依赖5.4 5.4 等长信源编码定理等长信源编码定理给出了等长信源编码所需给出了等长信源编码所需码长的极限值码长的极限值。定理定理 等长信源编码定理等长信源编码定理 一熵为一熵为H(S)H(S)的的离散无记忆信源离散无记忆信源，若对其，若对其N N次扩展信次扩展信源源进行等长进行等长 r r 元编码，码长为元编码，码长为l l，对于任意，对于任意 大于大于0 0，只要满足只要满足当当N N足够大时，则可以实现几乎无失真编码，反之，若：足够大时，则可以实现几乎无失真编码，反之，若：则不可能实现无失真编码，当则不可能实现无失真编码，当N N趋向于无穷大时，译码错误趋向于无穷大时，译码错误率接近于率接近于1 1。5.4 等长信源编码定理给出了等长信源编码所需码长的极限值分析分析：定理中的条件式可写成：定理中的条件式可写成 左边左边:长为长为 l l 的的码符号（码字）码符号（码字）所能载荷的所能载荷的最大信最大信息量息量；右边右边:长为长为N N的的信源符号序列信源符号序列平均携带的信息量。平均携带的信息量。因此，定理说明了：只要因此，定理说明了：只要码字传输的最大信息量码字传输的最大信息量大于大于信信源序列携带的信息量源序列携带的信息量，则可以实现无失真编码，则可以实现无失真编码 。n编码后信源的信息传输率编码后信源的信息传输率 令：令：可见，只有可见，只有编码后信息传输率编码后信息传输率 ，才能实现无才能实现无失真编码。失真编码。(编码后，平均每个信源编码后，平均每个信源符号承载的信息量符号承载的信息量)分析：定理中的条件式可写成 左边:长为 l 最佳编码效率：最佳编码效率：由定理知，由定理知，n编码效率编码效率移项后，移项后，最佳编码效率：编码效率移项后，当信源符号自信息量的方差当信源符号自信息量的方差 和和 确定时，只要确定时，只要N N足够大，就可以实现允许错误概率：足够大，就可以实现允许错误概率：这时要求序列长度满足：这时要求序列长度满足：（任意一正数）（任意一正数）n信源序列长度信源序列长度N N 一般情况下，在已知信源熵的情况下，信源序列一般情况下，在已知信源熵的情况下，信源序列长度长度N N的选择，与的选择，与最佳编码效率最佳编码效率和和允许错误概率允许错误概率有关。可以有关。可以证明：证明：当信源符号自信息量的方差 和 若采用若采用等长二元编码等长二元编码，要求编码效率，要求编码效率 ，允许错误率，允许错误率则：则：例例：设离散无记忆信源：设离散无记忆信源：若采用等长二元编码，要求编码效率 1 1、唯一可译变长码、唯一可译变长码信源符号信源符号出现概率出现概率码码1 1码码2 2码码3 3码码4 4s1s1s2s2s3s3s4s41/21/21/41/41/81/81/81/80 01111000011110 01010000001011 11010100100100010001 10101001001000100015.5 5.5 变长码变长码优势优势：容易实现效率很高的编码。：容易实现效率很高的编码。变长码也必须是变长码也必须是唯一可译码唯一可译码，才能实现，才能实现无失真编码无失真编码。码码1 1是一个是一个奇异码奇异码，故不是唯一可译码；，故不是唯一可译码；码码2 2也不是唯一可译码，因为收到一串序列，无法唯一译出对应的也不是唯一可译码，因为收到一串序列，无法唯一译出对应的原符号序列，如原符号序列，如0100001000，即可译作，即可译作s4s3s1,s4s3s1,也可译作也可译作s4s1s3,s1s2s3s4s1s3,s1s2s3或或s1s2s1s1s1s2s1s1；1、唯一可译变长码信源符号出现概率码1码2码3码4s11/2码码2 2本身不是奇异码，但从有限长的码符号序列是奇异码。本身不是奇异码，但从有限长的码符号序列是奇异码。如果把码如果把码2 2的的2 2次扩展码写出，则会发现：次扩展码写出，则会发现：S1S3 S1S3的的扩展码字扩展码字为：为：000 000 ；S3S1 S3S1的的扩展码字扩展码字也为：也为：000000 所以，当出现所以，当出现000000序列时候，不能唯一地确定信源符序列时候，不能唯一地确定信源符号。号。码码3 3和和码码4 4都是唯一可译的，但码都是唯一可译的，但码3 3和码和码4 4也不太一样。也不太一样。码码4 4称作称作逗点码逗点码，只要收到，只要收到1 1，就可以立即作出，就可以立即作出译码译码；而而码码3 3不同，当收到一个或几个码时，必须参考后不同，当收到一个或几个码时，必须参考后面的码才能作出判断。面的码才能作出判断。1 10000001 100001010 码2本身不是奇异码，但从有限长的码符号序列是奇异码。码3和码n即时码即时码 接收端收到一个完整的码字后，就能接收端收到一个完整的码字后，就能立即进行译立即进行译码码，无须参考后面的码字无须参考后面的码字就可以作出唯一判断就可以作出唯一判断（译码）（译码）。n对于对于非即时码，非即时码，接收端收到一个完整的码字后，还接收端收到一个完整的码字后，还需等后续码元接收后才能判断是否可以唯一译码。需等后续码元接收后才能判断是否可以唯一译码。n非延长码（前缀条件码）非延长码（前缀条件码）若码若码C C中，没有任何完整的码字是其他码字的前中，没有任何完整的码字是其他码字的前缀，即设缀，即设 是码是码C C中的任意中的任意码字，而它不是其他码字码字，而它不是其他码字 （jmjm）的前缀，则此码为的前缀，则此码为非延长码非延长码（或（或前缀条件码前缀条件码）。）。！显然：即时码！显然：即时码等价于等价于前缀条件码（非延长码）前缀条件码（非延长码）。即时码对于非即时码，接收端收到一个完整的码字后，还需等后续码码码3 3：s1s1的码字是的码字是s2,s3,s4s2,s3,s4的码字的的码字的前缀前缀（词头）；（词头）；s2s2的码字是的码字是s3,s4s3,s4的码字的前缀；的码字的前缀；s3s3的码字是的码字是s4s4的码字的前缀；的码字的前缀；当译码时，接受到一个完整码字后，当译码时，接受到一个完整码字后，不能马上译码不能马上译码，还需考察，还需考察后续码元后续码元的情况才能进行正确译码；的情况才能进行正确译码；如：如：1 10000001 100001010 可译码为：可译码为：s4s3 s4s3？因此，码因此，码3 3不是即时码；但确是唯一不是即时码；但确是唯一可译码。可译码。信源符号信源符号码码3 3s1s1s2s2s3s3s4s41 1101010010010001000信源符号信源符号码码4 4s1s1s2s2s3s3s4s41 1010100100100010001码码4 4：码本中的任何一个码字：码本中的任何一个码字都不是其他码字的前缀。都不是其他码字的前缀。当译码时，接受到一个完整码当译码时，接受到一个完整码字后，不需要等待后续码元的字后，不需要等待后续码元的情况即可正确译码；情况即可正确译码；如：如：1 1000100010010010 0 可译码为：可译码为：s1 s4 s3 s1 s4 s3 因此，码因此，码4 4 是即时码，也是唯是即时码，也是唯一可译码。一可译码。码3：s1的码字是s2,s3,s4的码字的前缀（词头）；信源因此，对于码因此，对于码C C：若其为唯一可译码，则必为若其为唯一可译码，则必为非奇异码非奇异码；若其为即时码，则必是若其为即时码，则必是唯一可译码唯一可译码；反之，作为唯一可；反之，作为唯一可译码，则不一定是译码，则不一定是即时码即时码。所有的码所有的码非奇异码非奇异码唯一可译码唯一可译码即时码（非延长码）即时码（非延长码）因此，对于码C：所有的码非奇异码唯一可译码即时码（非延长码）信源符号信源符号码码4 4s1s1s2s2s3s3s4s41 10101001001000100012 2、即时码（非延时码）的树图构造法、即时码（非延时码）的树图构造法 对于给定码字集合对于给定码字集合C C，可用，可用码树码树来描述。来描述。同时，树图法可构造同时，树图法可构造即时码。即时码。01001111010010001码码4 4的树图描述的树图描述信源符号码4s112、即时码（非延时码）的树图构造法 在每个节点上都有在每个节点上都有r r个分枝的树称为个分枝的树称为整树（满树）整树（满树），否则称为否则称为非整（满）树。非整（满）树。0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 10 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1等长码二元码树（等长码二元码树（整树整树）树根树根码字的起点码字的起点树枝数树枝数码符号数码符号数终端节点终端节点码字码字阶数阶数码长码长中间节点中间节点 在每个节点上都有r个分枝的树称为整树（满树），0 1 0 1 2 2 0 1 2 0 1 0 1 2 0 1 2 0 1 22 0 1 20 1 20 1 20 1 20 1 2三元码树三元码树（整树）（整树）满树满树变长码变长码01001111010010001非满树非满树 0 非即时码非即时码的树图的树图中间节点安排为码字中间节点安排为码字1.1.树图树图中间节点中间节点不作为码字；不作为码字；2.2.一旦某节点作为码字，则一旦某节点作为码字，则不再继续进行分枝不再继续进行分枝。这样可保证每个码字不这样可保证每个码字不同，且满足同，且满足前缀条件码前缀条件码的条件。的条件。一般编码方法一般编码方法 选择相应节点作为码字：选择相应节点作为码字：不同的路径上的分支，对应不同的路径上的分支，对应了相应的码元符号，则可得到所编码字。了相应的码元符号，则可得到所编码字。10001101001000构造构造即时码即时码非即时码的树图1.树图中间节点不作为码字；一般编码方法100编码举例编码举例（即时码，编码方式不同）（即时码，编码方式不同）都为即时码，但编码方式不唯一都为即时码，但编码方式不唯一编码举例都为即时码，但编码方式不唯一编码举例（多元即时码）编码举例（多元即时码）编码举例（多元即时码）译码方法译码方法 因为每一码元对应于一个的树图分枝路径，则因为每一码元对应于一个的树图分枝路径，则即时即时码的树图码的树图可以用来可以用来译码译码。译码器系统对一串符号序列译码过。译码器系统对一串符号序列译码过程：程：1 1）首先从）首先从树根树根出发，根据接收的出发，根据接收的第一个码元符号第一个码元符号来选择应走来选择应走的第一条路径；的第一条路径；2 2）若沿着所选路径走到）若沿着所选路径走到某中间节点某中间节点，再根据接收的，再根据接收的第二个码第二个码元符号元符号来选择第二条路经；来选择第二条路经；3 3）若又走到中间节点，再依次继续选择路径，直到）若又走到中间节点，再依次继续选择路径，直到终端节点终端节点为止。这时，可根据所经历的为止。这时，可根据所经历的枝路枝路，判断出所接收的码字。，判断出所接收的码字。4 4）重新）重新返回树根，返回树根，再作下一个接收码字的判断。再作下一个接收码字的判断。这样，便可将接收到的一串码符号序列译成信源符号序列。这样，便可将接收到的一串码符号序列译成信源符号序列。译码方法 3 3、克拉夫特（、克拉夫特（KraftKraft）不等式）不等式定理定理 对于码符号为对于码符号为 的任的任意意r r元元即时码即时码 ，若所对，若所对应的码长应的码长 ，则必定满足：则必定满足：反之，若码长满足上式，则一定存在这样的反之，若码长满足上式，则一定存在这样的即时码即时码 。*可以证明，对于可以证明，对于唯一可译码唯一可译码也须满足也须满足KraftKraft不等式。不等式。这说明，其他唯一可译码并不比即时码占优。这说明，其他唯一可译码并不比即时码占优。而即时码很容易用而即时码很容易用树图法构造树图法构造，所以在讨论唯一可，所以在讨论唯一可译码时，译码时，只需要讨论即时码就可以了。只需要讨论即时码就可以了。定理定理 若存在一个码长为若存在一个码长为 的的唯一可唯一可译码译码，则一定存在一个同样长度的，则一定存在一个同样长度的即时码即时码。3、克拉夫特（Kraft）不等式定理 对于码符号为 n例例：设二进制码树中设二进制码树中S=(sS=(s1 1,s,s2 2,s,s3 3,s s4 4),L),L1 1=1,L=1,L2 2=2,L=2,L3 3=2,L=2,L4 4=3,=3,应用应用KraftKraft不不等式等式,得：得：不存在满足这种不存在满足这种L Li i的唯一可译码的唯一可译码 n如果将各码字长度改成如果将各码字长度改成L L1 1=1,L=1,L2 2=2,L=2,L3 3=3,L=3,L4 4=3,=3,则则存在满足这种存在满足这种L Li i唯一可译码唯一可译码 000110 010101101101111码树码树111111000110 01010110110例：设二进制码树中S=(s1,s2,s3,s4)设信源设信源编码后的码字为：编码后的码字为：码长为：码长为：码的码的平均长度（平均码长）平均长度（平均码长）为：为：5.6 5.6 变长信源编码定理变长信源编码定理（码符号（码符号/信源符号）信源符号）n码的平均长度码的平均长度n信息传输率（码率）：信息传输率（码率）：平均每个平均每个码元携带的信息量码元携带的信息量，即，即编码后信道的信息编码后信道的信息传输率传输率：（比特（比特/码符号）码符号）设信源编码后的码字为：码长为：码的平均长度（平均码长）为：5 若信道传输一个码符号平均需要若信道传输一个码符号平均需要t t秒钟，则编码后信秒钟，则编码后信道的每秒传输的信息量为：道的每秒传输的信息量为：（比特（比特/秒）秒）由此可见：由此可见：平均码长越短，信息传输效率越高。平均码长越短，信息传输效率越高。n紧致码（最佳码）紧致码（最佳码）对于某一信源和某一个码符号集合，若有一个对于某一信源和某一个码符号集合，若有一个唯一唯一可译码，可译码，它的平均码长小于其他唯一可译码的长度。它的平均码长小于其他唯一可译码的长度。无失真信源编码的无失真信源编码的基本问题基本问题就是寻找就是寻找紧致码紧致码。若信道传输一个码符号平均需要t秒钟，则编码后信定理定理 若对一熵为若对一熵为H(S)H(S)的离散无记忆信源的离散无记忆信源 S S 进行进行r r 元编码，元编码，则总是可以找到一种无失真编码方法构成则总是可以找到一种无失真编码方法构成唯一可译码唯一可译码，使其，使其平均码长平均码长满足：满足：说明：说明：下界下界：平均码长不能小于极限：平均码长不能小于极限H(s)/logr,H(s)/logr,否则唯一可译码不存在。否则唯一可译码不存在。上界上界：给出了平均码长的上界。但并不是说大于这个上界就不能：给出了平均码长的上界。但并不是说大于这个上界就不能构成唯一可译码。而是说构成唯一可译码。而是说在上界范围内，可找到唯一可译码在上界范围内，可找到唯一可译码。定理 若对一熵为H(S)的离散无记忆信源 S 进行r 元证明：证明：1.1.下界证明：下界证明：詹森不等式詹森不等式证明：詹森不等式因总可找到一种唯一可译码，其码长因总可找到一种唯一可译码，其码长满足满足CraftCraft不等式不等式，所，所以以则证得：则证得：由由CraftCraft不等式，此等式成立的充要条件：不等式，此等式成立的充要条件：即：即：可见，只有当能够选择每个码长满足上述等式时候，平均码可见，只有当能够选择每个码长满足上述等式时候，平均码长才能够长才能够达到达到这个下界值。这个下界值。因总可找到一种唯一可译码，其码长满足Craft不等式，所以则 由于由于l li i 必须为正整数，所以必须为正整数，所以 也必须为也必须为正整数正整数。那么，当该等式成立时，每个那么，当该等式成立时，每个信源符号的概率分信源符号的概率分布布必须呈现如下形式：必须呈现如下形式：如果这个条件满足，则只要选择：如果这个条件满足，则只要选择：根据这些码长，按照根据这些码长，按照树图法树图法构造出一种构造出一种唯一可译码唯一可译码，所得，所得的码一定是的码一定是紧致码紧致码。由于li 必须为正整数，所以 2.2.上界证明：上界证明：只需证明存在只需证明存在一种唯一可译码满足一种唯一可译码满足即可。令即可。令则，选取每个码字的长度的原则是：则，选取每个码字的长度的原则是：显然知显然知2.上界证明：只需证明存在一种唯一可译码满足即可。令则，选取即为即为CraftCraft不等式；因此，不等式；因此，用这样选择的码长用这样选择的码长满足满足CraftCraft不等不等式式，故，故可构造唯一可译码可构造唯一可译码。但不一定是紧致码。但不一定是紧致码。两边对两边对i i求和，则有：求和，则有：由于由于即为Craft不等式；因此，用这样选择的码长满足Craft不右边的不等式两边进行如下处理：右边的不等式两边进行如下处理：平均码长平均码长因此，平均码长因此，平均码长小于上界小于上界的的唯一可译码存在唯一可译码存在。两边乘以两边乘以P(P(s si i)后，求和。后，求和。另外由于另外由于右边的不等式两边进行如下处理：平均码长因此，平均码长小于上界无失真变长信源编码定理（香农第一定理）无失真变长信源编码定理（香农第一定理）离散无记忆信源离散无记忆信源S S的的N N次扩展信源次扩展信源 ，其熵为，其熵为 ，且编码器码元符号集为，且编码器码元符号集为 .对信源对信源 进行编码，总可以找到一种编码方法，构成唯一进行编码，总可以找到一种编码方法，构成唯一可译码，使信源可译码，使信源S S中每个信源符号中每个信源符号s si i所需要的平均码长所需要的平均码长 满足满足 当当 则则得：得：无失真变长信源编码定理（香农第一定理）当 证明证明：设离散无记忆信源：设离散无记忆信源X X的数学模型的数学模型N N次扩展次扩展由于无记忆性，有：由于无记忆性，有：证明：设离散无记忆信源X的数学模型N次扩展由于无记忆性，有：由前述定理，有：由前述定理，有：由前述定理，有：定理含义：定理含义：要做到无失真信源编码，变换每个信源符号平要做到无失真信源编码，变换每个信源符号平均所需最少的均所需最少的r r元码元数是信源的熵值。元码元数是信源的熵值。若编码的平均码长小于信源的熵，则唯一可译若编码的平均码长小于信源的熵，则唯一可译码不存在，在译码时必然带来失真或差错。码不存在，在译码时必然带来失真或差错。同时，通过对扩展信源进行变长编码，当扩展长同时，通过对扩展信源进行变长编码，当扩展长度度N N足够大时，平均码长可达到此极限值。足够大时，平均码长可达到此极限值。信源的熵是无失真信源压缩的极限值。信源的熵是无失真信源压缩的极限值。定理含义：要做到无失真信源编定理推广：定理推广：可以推广到可以推广到平稳有记忆信源平稳有记忆信源和和马尔科夫信源马尔科夫信源：定理推广：可以推广到平稳有记忆信源和马尔科夫 如果将定理中的下式改写：如果将定理中的下式改写：为编码后平均每个信源符号所能承载的最大信息量，即变长为编码后平均每个信源符号所能承载的最大信息量，即变长编码编码后信源后信源的的信息传输率（编码信息率）信息传输率（编码信息率）。这样，香农第一定理也可表述为：这样，香农第一定理也可表述为：若若R=H(S),R=H(S),就存在唯一可译变长编码；若就存在唯一可译变长编码；若R H(S),R H(S),唯一可译边长码不存在，不能实现无失真德信源编码。唯一可译边长码不存在，不能实现无失真德信源编码。则定义：则定义：等长编码等长编码 如果将定理中的下式改写：为编码后平均每个信源符号 从从信道角度信道角度看，编码后看，编码后信道的信息传输率信道的信息传输率：由此可见，此时信道的信息传输率等于由此可见，此时信道的信息传输率等于无噪无损信道无噪无损信道的信的信道容量道容量C C，信息传输率最高。，信息传输率最高。因此，无失真信源编码的实质是：因此，无失真信源编码的实质是：对离散信源进行适当编对离散信源进行适当编码，使变换后新的码符号信源（信道的输入信源）尽可能等概率分码，使变换后新的码符号信源（信道的输入信源）尽可能等概率分布，以使新信源的每个码符号平均所含的信息量达到最大，从而使布，以使新信源的每个码符号平均所含的信息量达到最大，从而使信道的信息传输率信道的信息传输率R R达到信道容量达到信道容量C C，实现信源与信道的统计匹配。，实现信源与信道的统计匹配。所以，无失真信源编码实质上就是所以，无失真信源编码实质上就是无噪信道编码问题。无噪信道编码问题。而而 则：则：即：当平均码长为极限值即：当平均码长为极限值H(S)/logrH(S)/logr时，则时，则 R=logr.R=logr.（香农第一定理）（香农第一定理）从信道角度看，编码后信道的信息传输率：无噪信道编码定理无噪信道编码定理 若若信道的信息传输率信道的信息传输率RR无噪无损信道无噪无损信道容量容量 C=logrC=logr，总能对信源的输出进行适当的编码，使得在，总能对信源的输出进行适当的编码，使得在无噪无损信道无噪无损信道上能无差错地、以最大信息传输率上能无差错地、以最大信息传输率C C传输信息；反之，若传输信息；反之，若R R大大C C，则无差错传输是不可能的。，则无差错传输是不可能的。因此，因此，信道容量信道容量C C是无噪信道的无差错传输的最大信是无噪信道的无差错传输的最大信息传输率。息传输率。编码效率编码效率衡量各种编码距极限压缩值得情况：衡量各种编码距极限压缩值得情况：无噪信道编码定理 编码效率衡量各种编码距极限压缩值码的剩余度码的剩余度：特别地，在二元无噪无损信道中，编码效率为：特别地，在二元无噪无损信道中，编码效率为：所以，在二元无噪无损信道中信息传输率：所以，在二元无噪无损信道中信息传输率：即：在二元信道中，可直接用编码的效率来衡量编码后信道的信即：在二元信道中，可直接用编码的效率来衡量编码后信道的信息传输率是否提高了。息传输率是否提高了。码的剩余度：特别地，在二元无噪无损信道中，编码效率为：所以，例：例：离散无记忆信源离散无记忆信源其熵为：其熵为：H(S)=0.811 H(S)=0.811 比特比特/信源符号信源符号用二元码符号（用二元码符号（0 0，1 1）来构造一个即时码：）来构造一个即时码：S1=S1=0 0，s2=s2=1 1。这时平均码长这时平均码长 ，编码的效率编码的效率为为信道信息传速率信道信息传速率 R=0.811 R=0.811 比特比特/码元符号。码元符号。例：离散无记忆信源其熵为：H(S)=0.811 比特/信源为了提高传输效率，可以对无记忆离散信源为了提高传输效率，可以对无记忆离散信源S S的扩展信源进行的扩展信源进行扩展，再进行编码：扩展，再进行编码：即时码即时码s1s1s1s19/169/160 0s1s2s1s23/163/161010s2s1s2s13/163/16110110s2s2s2s21/161/16111111平均码长：平均码长：则则S S中每个符号的中每个符号的平均码长平均码长：编码效率：编码效率：可见，编码复杂了一些，但信息传输率有了提高。可见，编码复杂了一些，但信息传输率有了提高。随着信源扩展次数增大，编码效率趋近于随着信源扩展次数增大，编码效率趋近于1 1；信息传输率；信息传输率R R也趋也趋近于无损无噪信道的信道容量近于无损无噪信道的信道容量C C，达到信源与信道的匹配。，达到信源与信道的匹配。，R R2 2=0.961=0.961 比特比特/码元符号码元符号为了提高传输效率，可以对无记忆离散信源S的扩展信源进行扩展，香农第一定理（无失真信源编码定理）指出香农第一定理（无失真信源编码定理）指出了了信源无损压缩信源无损压缩与信源与信源信息熵信息熵之间的关系：之间的关系：信息熵是无损压缩编码所需平均码长的极限值，信息熵是无损压缩编码所需平均码长的极限值，可以通过编码使平均码长达到极限值。可以通过编码使平均码长达到极限值。物理意义：物理意义：由于信息熵表达了事物所含的信息量，因此，由于信息熵表达了事物所含的信息量，因此，不可能用少于信息熵的比特数来确切地表达这一事物。不可能用少于信息熵的比特数来确切地表达这一事物。香农第一定理（无失真信源编码定理）指出了信源