信息论基础理论与应用第三版(傅祖芸)第5章讲义.

第5章无失真信源编码定理5.1编码器5.2等长码5.6变长信源编码定理5.4等长信源编码定理5.5变长码信息通过信道传输到信宿的过程。要做到既不失真又快速地通信，需要解决两个问题：信源编码:在不失真或允许一定失真条件下，提高信息传输率.信道编码:在信道受到干扰的情况下，增加信号的抗干扰能力，同时又使得信息传输率最大.最佳编码：一般来说，抗干扰能与信息传输率二者相互矛盾。而编码定理理论上证明，至少存在某种最佳的编码能够解决上述矛盾，做到既可靠又有效地传输信息。信源编码：信源虽然多种多样，但无论是哪种类型的信源，信源符号之间总存在相关性和分布的不均匀性，使得信源存在冗余度。信源编码的目的就是要减少冗余，提高编码效率。引言研究方法研究信源编码时，将信道编码与译码看成是信道的一部分，从而突出信源编码；研究信道编码时，将信源编码与译码看成是信源与信宿的一部分，从而突出信道编码。12{,,...,}qSSSS5.1编码器编码器：对信源的符号按一定的数学规则进行的变换。它可以看作这样一个系统，它的输入端为原始信源S，其符号集为而信道所能传输的符号集为12{,,...,}rXxxx编码器功能：用符号集X中的元素，将原始信源的符号变换为相应的码字符号，编码器输出符号集为(码或码书)称为码字，li为码字的码元个数（码字长度，码长）。码字集合C称为码或码书。12:{,,...,}qC),...2,1(,),...(),...,2,1(iiiiiiilkXxxxxWqiskil21),...2,1();,...2,1(,),...()...(2121iiiixiiiiiilkXxNkSsxxxWssskkilN若要实现无失真编码，这种映射应是一一对应的可逆映射。编码的形式化描述：从信源符号到码符号的一种映射或：1、二元码与r元码2元码:码符号集X={0,1}.如果将信源通过二元信道传输，必须将信源编成二元码，这是最常用的一种码。r元码:码符号集有r个符号的编码。2、等长码与变长码等长码:一组码中所有码字的长度都相同。变长码:一组码中所有码字的长度各不相同。码的分类及定义信源符号si符号出现概率p(si)编码1编码2s1p(s1)000s2p(s2)0101s3p(s3)10001s4p(s4)111013、非奇异码与奇异码非奇异码:一组码中所有码字都不相同。奇异码:一组码中有相同的码字。CWWSssWWssjijijiji,,;CWWSssWWssjijijiji,,;信源符号编码1编码21/20001/40101/81011/811101a2a3a4a()ipa4、同价码同价码:码符号集中每个码符号所占的传输时间都相同(大多数情况)。变长码中每个码字的传输时间就不一定相同。（摩尔斯电报码，点-划所占传输时间不同）5、码的N次扩展若某码C，它把信源S中的符号一一变换成码C中的码字，则码C的N次扩展码是所有N个码字组成的码字序列的集合B:12:{,,...,}qC{(...)}iiiiNBBiw12{,,...,}rXxxxisS扩展),...,2,1()...()...()...(212121Niiiiiiiiiiiiiqi码C码B扩展信源扩展码N次扩展12{,,,}qC12(,,,),,NlNiiiiiiiBN次扩展[例]设信源S的概率空间为：若通过—个二元信道进行传输，须把信源符号变换成0，1符号组成的码符号序列(二元序列)。采用如下二元码，如下表所示（q=4）：)()()()()(321321qqsPsPsPsPsssssPS1)(1qiisp信源符号si符号出现概率P(si)码s1P(s1)0s2P(s2)01s3P(s3)001s4P(s4)111试求码的二次扩展码。信源S的二次扩展信源：则码的二次扩展码为：],...,,,[44163132121112ssssssssS信源符号码字信源符号码字信源符号码字α100:W1W1=B1α5010:W2W1=B5：：α2001:W1W2=B2：：：：α30001:W1W3=B3：：：：α40111:W1W4=B4：：α16111111:W4W4=B166、唯一可译码(单义可译码）由码构成的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列。否则,就为非惟一可译码或非单义可译码。例：对于二元码，当任意给定一串码字序列，例如…10001101…只可唯一地划分为1,00,01,1,01，因此是惟一可译码；而对另一个二元码，当码字序列为…01001…可划分为0,10,01或01,0,01，所以是非惟一可译的。1{1,01,00}C2{0,10,01}C唯一可译码的条件1）不同的信源符号变换成不同的码字(非奇异码)；2）任意有限长的信源序列所对应的码元序列各不相同.即:码的任意有限长N次扩展码都是非奇异码。Or:码符号序列的反变换也唯一的（扩展码非奇异）原因：若要使某一码为惟一可译码，则对于任意有限长的码符号序列，必须只能被惟一地分割成一个个的码字，才能实现唯一的译码。无失真的编码的一般条件1）码字与信源符号之间一一对应（非奇异码）；2）码符号序列的反变换也唯一的（扩展码非奇异）。即：编码必须是唯一可译码。否则，就会引起译码的错误与失真。等长码是唯一可译码的条件若等长码是非奇异码，则它的任意有限长N次扩展码一定也是非奇异码。因此，等长非奇异码字一定是唯一可译码,因为采用固定长度划分码字序列.5.2等长码1）若对每个信源符号进行等长编码，则必须满足:其中:l是码长，r是码符号集的码元数，q信源符号数。lqr2）若对信源的N次扩展信源进行编码，必须满足:NlqrlogloglqNr表示平均每个信源符号所需的码符号个数。lN即为了使等长码为非奇异码（唯一可译码），那么:例证：根据依赖关系，信源符号平均所需码符号数可减少。例设信源31241234()()()()()ssssSPsPsPsPsPs41()1iiPs而其依赖关系为：0)|(,1)|()|()|()|(43342112ijssPssPssPssPssP其余1）若不考虑符号间的依赖关系，可得每符号码长l＝2；2）若考虑符号间的二元依赖关系，可作二次扩展信源进行分析。根据条件概率仅有4项的概率不为零，可得扩展信源的码长l’=2，而每个信源符号的平均码长为l’/N=1。234431221212213443()()()()()ssssssssSPssPssPssPssPs()1ijijPss)|()()(ijijissPsPssP5.4等长信源编码定理给出了等长信源编码所需码长的极限值。定理等长信源编码定理一熵为H(S)的离散无记忆信源，若对其N次扩展信源进行等长r元编码，码长为l，对于任意大于0，只要满足()loglHSNr当N足够大时，则可以实现几乎无失真编码，反之，若：()2loglHSNr则不可能实现无失真编码，当N趋向于无穷大时，译码错误率接近于1。•分析：定理中的条件式可写成log()lrNHS左边:长为l的码符号（码字）所能载荷的最大信息量；右边:长为N的信源符号序列平均携带的信息量。因此，定理说明了：只要码字传输的最大信息量大于信源序列携带的信息量，则可以实现无失真编码。编码后信源的信息传输率log()lrHSN令：'loglRrN可见，只有编码后信息传输率，才能实现无失真编码。)('SHR(编码后，平均每个信源符号承载的信息量))('SHR最佳编码效率：由定理知，'()()()HSHSRHS1()HS'()()logHSHSlRrN编码效率移项后，)0(1log()lrHSN当信源符号自信息量的方差和确定时，只要N足够大，就可以实现允许错误概率：2222)1()()]([)]([SHsIDsIDNiiEP0)]([isID0这时要求序列长度满足：（任意一正数）信源序列长度N一般情况下，在已知信源熵的情况下，信源序列长度N的选择，与最佳编码效率和允许错误概率有关。可以证明：1()HS134()log4log0.811443HS2222221134[()](log)[()](log4)(log)0.8110.4715443iiiiDIsppHS若采用等长二元编码，要求编码效率，允许错误率0.96510则：74.1310N例：设离散无记忆信源：1231()44ssSPs811.0)()(log'SHNlSHrNlR1、唯一可译变长码信源符号出现概率码1码2码3码4s1s2s3s41/21/41/81/801100110100001110100100010100100015.5变长码优势：容易实现效率很高的编码。变长码也必须是唯一可译码，才能实现无失真编码。码1是一个奇异码，故不是唯一可译码；码2也不是唯一可译码，因为收到一串序列，无法唯一译出对应的原符号序列，如01000，即可译作s4s3s1,也可译作s4s1s3,s1s2s3或s1s2s1s1；码2本身不是奇异码，但从有限长的码符号序列是奇异码。如果把码2的2次扩展码写出，则会发现：S1S3的扩展码字为：000；S3S1的扩展码字也为：000所以，当出现000序列时候，不能唯一地确定信源符号。码3和码4都是唯一可译的，但码3和码4也不太一样。码4称作逗点码，只要收到1，就可以立即作出译码；而码3不同，当收到一个或几个码时，必须参考后面的码才能作出判断。100010010…即时码接收端收到一个完整的码字后，就能立即进行译码，无须参考后面的码字就可以作出唯一判断（译码）。对于非即时码，接收端收到一个完整的码字后，还需等后续码元接收后才能判断是否可以唯一译码。非延长码（前缀条件码）若码C中，没有任何完整的码字是其他码字的前缀，即设是码C中的任意码字，而它不是其他码字（jm）的前缀，则此码为非延长码（或前缀条件码）。)...(21imiiixxxW)......(21kjkmkkkxxxxW！！显然：即时码等价于前缀条件码（非延长码）。码3：s1的码字是s2,s3,s4的码字的前缀（词头）；s2的码字是s3,s4的码字的前缀；s3的码字是s4的码字的前缀；当译码时，接受到一个完整码字后，不能马上译码，还需考察后续码元的情况才能进行正确译码；如：100010010…可译码为：s4s3？…因此，码3不是即时码；但确是唯一可译码。信源符号码3s1s2s3s41101001000信源符号码4s1s2s3s41010010001码4：码本中的任何一个码字都不是其他码字的前缀。当译码时，接受到一个完整码字后，不需要等待后续码元的情况即可正确译码；如：100010010…可译码为：s1s4s3…因此，码4是即时码，也是唯一可译码。因此，对于码C：若其为唯一可译码，则必为非奇异码；若其为即时码，则必是唯一可译码；反之，作为唯一可译码，则不一定是即时码。所有的码非奇异码唯一可译码即时码（非延长码）信源符号码4s1s2s3s410100100012、即时码（非延时码）的树图构造法对于给定码字集合C，可用码树来描述。同时，树图法可构造即时码。01001111010010001码4的树图描述在每个节点上都有r个分枝的树称为整树（满树），否则称为非整（满）树。010101010101010101010101010101等长码二元码树（整树）树根——码字的起点树枝数—码符号数终端节点—码字阶数—码长中间节点012012012012012012三元码树（整树）