1、信息论基础理论与应用第三版傅祖芸第5章讲义 信息通过信道传输到信宿的过程。要做到既不失真又快速信息通过信道传输到信宿的过程。要做到既不失真又快速地通信，需要解决两个问题：地通信，需要解决两个问题：n信源编码信源编码:在不失真或允许一定失真条件下，提高在不失真或允许一定失真条件下，提高信息传输率信息传输率.n信道编码信道编码:在信道受到干扰的情况下，增加信号的在信道受到干扰的情况下，增加信号的抗干扰能力抗干扰能力，同时又，同时又使得信息传输率最大使得信息传输率最大.n最佳编码：最佳编码：一般来说，一般来说，抗干扰能抗干扰能与与信息传输率信息传输率二者相互矛盾。而编码二者相互矛盾。而编码定理理论上
2、证明，至少存在某种定理理论上证明，至少存在某种最佳最佳的编码能够解决上述矛盾，的编码能够解决上述矛盾，做到做到既可靠又有效既可靠又有效地传输信息。地传输信息。n信源编码：信源编码：信源虽然多种多样，但无论是哪种类型的信源，信源符号信源虽然多种多样，但无论是哪种类型的信源，信源符号之间总存在相关性和分布的不均匀性，使得信源存在冗余度。之间总存在相关性和分布的不均匀性，使得信源存在冗余度。信源编码的目的就是要减少冗余，提高编码效率。信源编码的目的就是要减少冗余，提高编码效率。引引 言言n研究方法研究方法研究研究信源编码信源编码时，将信道编码与译码看成是时，将信道编码与译码看成是信道信道的一部分，的
3、一部分，从而突出信源编码；从而突出信源编码；研究研究信道编码信道编码时，将信源编码与译码看成是时，将信源编码与译码看成是信源与信宿信源与信宿的的一部分，从而突出信道编码。一部分，从而突出信道编码。12,.,qSS SS5.1 5.1 编码器编码器n编码器：编码器：对信源的符号按一定的数学规则进行的变换。对信源的符号按一定的数学规则进行的变换。它可以看作这样一个系统，它的输入端为原始信源它可以看作这样一个系统，它的输入端为原始信源S S，其符，其符号集为号集为 而信道所能传输的符号集为而信道所能传输的符号集为 12,.,rXx xx 编码器功能：编码器功能：用符号集用符号集X X中的元素，将原始
4、信源的符中的元素，将原始信源的符号号 变换为相应的码字符号变换为相应的码字符号 ，编码器输出符号集为，编码器输出符号集为 (码或码书码或码书)称为称为码字码字，l li i 为码字为码字 的码元个数（码字长度，的码元个数（码字长度，码码长长）。码字集合）。码字集合C C称为称为码码或或码书码书。12:,.,qCW WWiwiwiwis),.2,1(,),.(),.,2,1(iiiiiiilkXxxxxWqiskil21 ),.2,1();,.2,1(,),.().(2121iiiixiiiiiilkXxNkSsxxxWssskkilN 若要实现无失真编码，这种映射应是若要实现无失真编码，这种映
5、射应是一一对应的可逆一一对应的可逆映射。映射。n编码的形式化描述：编码的形式化描述：从从信源符号信源符号到到码符号码符号的一种映射的一种映射或：或：1 1、二元码与二元码与r r元码元码 2 2元码元码:码符号集码符号集X=0,1.X=0,1.如果将信源通过二元信道传输，必如果将信源通过二元信道传输，必须将信源编成二元码，这是最常用的一种码。须将信源编成二元码，这是最常用的一种码。r r元码元码:码符号集有码符号集有r r个符号的编码。个符号的编码。2 2、等长码与变长码等长码与变长码 等长码等长码:一组码中所有码字的长度都相同。一组码中所有码字的长度都相同。变长码变长码:一组码中所有码字的长
6、度各不相同。一组码中所有码字的长度各不相同。n 码的分类及定义码的分类及定义信源符号信源符号si si符号出现概率符号出现概率p p(si)(si)编码编码1 1编码编码2 2s1s1p p(s1)(s1)00000 0s2s2p p(s2)(s2)01010101s3s3p p(s3)(s3)1010001001s4s4p p(s4)(s4)11111011013 3、非奇异码与奇异码非奇异码与奇异码 非奇异码非奇异码:一组码中所有码字都不相同。一组码中所有码字都不相同。奇异码奇异码:一组码中有相同的码字。一组码中有相同的码字。CWWSssWWssjijijiji,;CWWSssWWssji
7、jijiji,;信源符号信源符号 编码编码1 1编码编码2 21/21/200000 01/41/401010 01/81/810101 11/81/8111110101a2a3a4a()ip a4 4、同价码同价码 同价码同价码:码符号集码符号集 中每个码符号所占的中每个码符号所占的传输时间传输时间都相同都相同(大多数情况大多数情况)。变长码中每个码字的传输时间就不一定相同。变长码中每个码字的传输时间就不一定相同。（摩尔斯电报码，（摩尔斯电报码，点点-划划 所占传输时间不同）所占传输时间不同）5 5、码的码的N N次扩展次扩展 若某码若某码 C C，它把信源，它把信源S S中的符号中的符号
8、一一变换成码一一变换成码C C中的码中的码字字 ，则，则码码C C的的N N次扩展码次扩展码是所有是所有N N个码字组成的码字序列个码字组成的码字序列的集合的集合B:B:12:,.,qCW WW12:(.)iiiiNB BWWWiw12,.,rXx xxisS扩展扩展),.,2,1().().().(212121NiiiiiiiiiiiiiqiWWWBsssxxxWsNNil码码C C码码B B扩展信源扩展信源扩展码扩展码N N次扩展次扩展12,qCW WW 12(,),NlNiiiiiiiBW WWSWC N N次扩展次扩展 例例 设信源设信源S S的概率空间为：的概率空间为：若通过若通过个
9、二元信道进行传输，须把信源符号变换成个二元信道进行传输，须把信源符号变换成 0 0，1 1 符符号组成的码符号序列号组成的码符号序列(二元序列二元序列)。采用如下二元码，。采用如下二元码，如下表所示如下表所示（q=4q=4）：）：)()()()()(321321qqsPsPsPsPsssssPS1)(1qiisp信源符号信源符号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试求码的二次扩展码。试求码的二次扩展码。信信
10、源源S S的的二次扩展信源二次扩展信源：则则码码的的二次扩展码二次扩展码为：为：,.,44163132121112ssssssssS信源信源符号符号码字码字信源信源符号符号码字码字信源信源符号符号码字码字 1 100:W00:W1 1WW1 1=B=B1 1 5 5010:W010:W2 2WW1 1=B=B5 5：2 2001:W001:W1 1WW2 2=B=B2 2：3 30001:W0001:W1 1WW3 3=B=B3 3：4 40111:W0111:W1 1WW4 4=B=B4 4：1616111111:W111111:W4 4WW4 4=B=B16166 6、唯一可译码、唯一可译
11、码(单义可译码单义可译码）由码构成的任意一串有限长的由码构成的任意一串有限长的码符号序列码符号序列只能被唯一的只能被唯一的译成所对应的译成所对应的信源符号序列信源符号序列。否则否则,就为非惟一可译码或非单义可译码。就为非惟一可译码或非单义可译码。n例例：对于二元码：对于二元码 ，当任意给定一串，当任意给定一串码字码字序列序列，例如，例如1000110110001101只可唯一地划分为只可唯一地划分为1,00,01,1,011,00,01,1,01，因此是，因此是惟一可译码惟一可译码；n而对另一个二元码而对另一个二元码 ，当码字序列为，当码字序列为0100101001可划分为可划分为0,10,0
12、10,10,01或或01,0,0101,0,01，所以是，所以是非惟一可译的非惟一可译的。11,01,00C 20,10,01C n唯一可译码的条件唯一可译码的条件 1 1）不同的信源符号变换成不同的码字）不同的信源符号变换成不同的码字(非奇异码非奇异码)；2 2）任意有限长任意有限长的的信源序列信源序列所对应的所对应的码元序列码元序列各不相同各不相同.即即:码的任意有限长码的任意有限长N N次扩展码次扩展码都是都是非奇异码非奇异码。Or:码符号序列码符号序列的的反变换反变换也唯一的（也唯一的（扩展码非奇异扩展码非奇异）原因：原因：若要使某一码为惟一可译码，则对于任意有限长的若要使某一码为惟一
13、可译码，则对于任意有限长的码码符号序列符号序列，必须只能被，必须只能被惟一地分割惟一地分割成一个个的码字，才成一个个的码字，才能实现唯一的译码。能实现唯一的译码。n无失真的编码的一般条件无失真的编码的一般条件 1 1）码字与信源符号之间一一对应（）码字与信源符号之间一一对应（非奇异码非奇异码）；）；2 2）码符号序列码符号序列的的反变换反变换也唯一的（也唯一的（扩展码非奇异扩展码非奇异）。）。即即：编码必须是：编码必须是唯一可译码唯一可译码。否则，就会引起译码的错。否则，就会引起译码的错误与失真。误与失真。等长码是唯一可译码的条件等长码是唯一可译码的条件 若等长码是若等长码是非奇异码非奇异码，
14、则它的任意有限长，则它的任意有限长N N次扩展次扩展码码一定也是非奇异码。一定也是非奇异码。因此，因此，等长非奇异码字等长非奇异码字一定是一定是唯一可译码唯一可译码,因为采用因为采用固定长度划分码字序列固定长度划分码字序列.5.2 5.2 等长码等长码 1 1）若对）若对每个信源符号每个信源符号进行等长编码，则必须满足进行等长编码，则必须满足:其中其中:l:l是码长，是码长，r r是码符号集的码元数，是码符号集的码元数，q q信源符号数。信源符号数。lqr 2 2）若对）若对信源的信源的N N次扩展信源次扩展信源进行编码，必须满足进行编码，必须满足:NlqrlogloglqNr表示平均表示平均
15、每个信源符号每个信源符号所需的所需的码符号个数。码符号个数。lN即即 为了使等长码为非奇异码（唯一可译码），那么为了使等长码为非奇异码（唯一可译码），那么:例证：根据依赖关系，信源符号平均所需码符号数可减少。例证：根据依赖关系，信源符号平均所需码符号数可减少。例例 设信源设信源31241234()()()()()ssssSP sP sP sP sP s41()1iiP s而其依赖关系为：而其依赖关系为：0)|(,1)|()|()|()|(43342112ijssPssPssPssPssP 其余其余1 1）若不考虑符号间的依赖关系，可得每符号码长）若不考虑符号间的依赖关系，可得每符号码长l l2
16、 2；2 2）若考虑符号间的）若考虑符号间的二元依赖关系二元依赖关系，可作二次扩展信源进行，可作二次扩展信源进行分析。根据条件概率仅有分析。根据条件概率仅有4 4项的概率不为零，可得扩展信源项的概率不为零，可得扩展信源的码长的码长 l=2l=2，而每个信源符号的，而每个信源符号的平均码长平均码长为为 l/N=1l/N=1 。23 44 31 22 121 22 13 44 3()()()()()s ss ss ss sSP s sP s sP s sP s sP s()1ijijP s s)|()()(ijijissPsPssP5.4 5.4 等长信源编码定理等长信源编码定理给出了等长信源编码
17、所需给出了等长信源编码所需码长的极限值码长的极限值。定理定理 等长信源编码定理等长信源编码定理 一熵为一熵为H(S)H(S)的的离散无记忆信源离散无记忆信源，若对其，若对其N N次扩展信源次扩展信源进行等长进行等长 r r 元编码，码长为元编码，码长为l l，对于任意，对于任意 大于大于0 0，只要满，只要满足足()loglH SNr当当N N足够大时，则可以实现几乎无失真编码，反之，若：足够大时，则可以实现几乎无失真编码，反之，若：()2loglH SNr则不可能实现无失真编码，当则不可能实现无失真编码，当N N趋向于无穷大时，译码错误趋向于无穷大时，译码错误率接近于率接近于1 1。分析分析
18、：定理中的条件式可写成：定理中的条件式可写成log()lrNH S 左边左边:长为长为 l l 的的码符号（码字）码符号（码字）所能载荷的所能载荷的最大信息量最大信息量；右边右边:长为长为N N的的信源符号序列信源符号序列平均携带的信息量。平均携带的信息量。因此，定理说明了：只要因此，定理说明了：只要码字传输的最大信息量码字传输的最大信息量大于大于信源序信源序列携带的信息量列携带的信息量，则可以实现无失真编码，则可以实现无失真编码 。n编码后信源的信息传输率编码后信源的信息传输率 log()lrH SN令：令：loglRrN可见，只有可见，只有编码后信息传输率编码后信息传输率 ，才能实现无失真
19、编码。才能实现无失真编码。)(SHR(编码后，平均每个信源编码后，平均每个信源符号承载的信息量符号承载的信息量)(SHR 最佳编码效率：最佳编码效率：由定理知，由定理知，()()()H SH SRH S1()H S()()logH SH SlRrNn编码效率编码效率移项后，移项后，)0(1 log()lrH SN当信源符号自信息量的方差当信源符号自信息量的方差 和和 确定时，只确定时，只要要N N足够大，就可以实现允许错误概率：足够大，就可以实现允许错误概率：2222)1()()()(SHsIDsIDNiiEP0)(isID0这时要求序列长度满足：这时要求序列长度满足：（任意一正数）（任意一正
20、数）n信源序列长度信源序列长度N N 一般情况下，在已知信源熵的情况下，信源序列长度一般情况下，在已知信源熵的情况下，信源序列长度N N的选择，与的选择，与最佳编码效率最佳编码效率和和允许错误概率允许错误概率有关。可以证明：有关。可以证明：1()H S134()log 4log0.811443HS2222221134()(log)()(log4)(log)0.8110.4715443iiiiDI sppH S若采用若采用等长二元编码等长二元编码，要求编码效率，要求编码效率 ，允许，允许错误率错误率0.96510则：则：74.1310N 例例：设离散无记忆信源：设离散无记忆信源：1231()44
21、ssSP s811.0)()(logSHNlSHrNlR1 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是一个是一个奇异码奇异
22、码，故不是唯一可译码；，故不是唯一可译码；码码2 2也不是唯一可译码，因为收到一串序列，无法唯一译出对应的也不是唯一可译码，因为收到一串序列，无法唯一译出对应的原符号序列，如原符号序列，如0100001000，即可译作，即可译作s4s3s1,s4s3s1,也可译作也可译作s4s1s3,s1s2s3s4s1s3,s1s2s3或或s1s2s1s1s1s2s1s1；码码2 2本身不是奇异码，但从有限长的码符号序列是奇异码。本身不是奇异码，但从有限长的码符号序列是奇异码。如果把码如果把码2 2的的2 2次扩展码写出，则会发现：次扩展码写出，则会发现：S1S3 S1S3的的扩展码字扩展码字为：为：000
23、 000 ；S3S1 S3S1的的扩展码字扩展码字也为：也为：000000 所以，当出现所以，当出现000000序列时候，不能唯一地确定信源符号。序列时候，不能唯一地确定信源符号。码码3 3和和码码4 4都是唯一可译的，但码都是唯一可译的，但码3 3和码和码4 4也不太一样。也不太一样。码码4 4称作称作逗点码逗点码，只要收到，只要收到1 1，就可以立即作出，就可以立即作出译码译码；而而码码3 3不同，当收到一个或几个码时，必须参考后面的不同，当收到一个或几个码时，必须参考后面的码才能作出判断。码才能作出判断。1 10000001 100001010 n即时码即时码 接收端收到一个完整的码字后
24、，就能接收端收到一个完整的码字后，就能立即进行译码立即进行译码，无须参考后面的码字无须参考后面的码字就可以作出唯一判断就可以作出唯一判断（译码）（译码）。n对于对于非即时码，非即时码，接收端收到一个完整的码字后，还接收端收到一个完整的码字后，还需等后续码元接收后才能判断是否可以唯一译码。需等后续码元接收后才能判断是否可以唯一译码。n非延长码（前缀条件码）非延长码（前缀条件码）若码若码C C中，没有任何完整的码字是其他码字的前缀，中，没有任何完整的码字是其他码字的前缀，即设即设 是码是码C C中的任意码字，而它不是其他中的任意码字，而它不是其他码字码字 （jmjm）的前缀，则此码为的前缀，则此码
25、为非延长码非延长码（或（或前缀条件码前缀条件码）。）。).(21imiiixxxW).(21kjkmkkkxxxxW！显然：即时码！显然：即时码等价于等价于前缀条件码（非延长码）前缀条件码（非延长码）。码码3 3：s1s1的码字是的码字是s2,s3,s4s2,s3,s4的码字的的码字的前前缀缀（词头）；（词头）；s2s2的码字是的码字是s3,s4s3,s4的码字的前缀；的码字的前缀；s3s3的码字是的码字是s4s4的码字的前缀；的码字的前缀；当译码时，接受到一个完整码字后，当译码时，接受到一个完整码字后，不能马上译码不能马上译码，还需考察，还需考察后续码元后续码元的情况才能进行正确译码；的情况
26、才能进行正确译码；如：如：1 10000001 100001010 可译码为：可译码为：s4s3 s4s3？因此，码因此，码3 3不是即时码；但确是唯一不是即时码；但确是唯一可译码。可译码。信源符号信源符号码码3 3s1s1s2s2s3s3s4s41 1101010010010001000信源符号信源符号码码4 4s1s1s2s2s3s3s4s41 1010100100100010001码码4 4：码本中的任何一个码字：码本中的任何一个码字都不是其他码字的前缀。都不是其他码字的前缀。当译码时，接受到一个完整当译码时，接受到一个完整码字后，不需要等待后续码码字后，不需要等待后续码元的情况即可正确
27、译码；元的情况即可正确译码；如：如：1 1000100010010010 0 可译码为：可译码为：s1 s4 s3 s1 s4 s3 因此，码因此，码4 4 是即时码，也是唯是即时码，也是唯一可译码。一可译码。因此，对于码因此，对于码C C：若其为唯一可译码，则必为若其为唯一可译码，则必为非奇异码非奇异码；若其为即时码，则必是若其为即时码，则必是唯一可译码唯一可译码；反之，作为唯一可；反之，作为唯一可译码，则不一定是译码，则不一定是即时码即时码。所有的码所有的码非奇异码非奇异码唯一可译码唯一可译码即时码（非延长码）即时码（非延长码）信源符号信源符号码码4 4s1s1s2s2s3s3s4s41
28、10101001001000100012 2、即时码（非延时码）的树图构造法、即时码（非延时码）的树图构造法 对于给定码字集合对于给定码字集合C C，可用，可用码树码树来描述。来描述。同时，树图法可构造同时，树图法可构造即时码。即时码。01001111010010001码码4 4的树图描述的树图描述 在每个节点上都有在每个节点上都有r r个分枝的树称为个分枝的树称为整树（满树），整树（满树），否则称为否则称为非整（满）树。非整（满）树。0 10 1 0 10 1 0 10 1 0 1 0 1 0 1 0 10 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
29、0 10 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1等长码二元码树（等长码二元码树（整树整树）树根树根码字的起点码字的起点树枝数树枝数码符号数码符号数终端节点终端节点码字码字阶数阶数码长码长中间节点中间节点 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 20 1 20 1 20 1 20 1 2三元码树三元码树（整树）（整树）满树满树变长码变长码01001111010010001非满树非满树非即时码非即时码的树图的树图中间节点安排为码字中间节点安排为码字1.1.树图树图中间节点中间节点不作为码字；不作为码字；2.2.一旦某节点作为码
30、字，则一旦某节点作为码字，则不再继续进行分枝不再继续进行分枝。这样可保证每个码字不同，这样可保证每个码字不同，且满足且满足前缀条件码前缀条件码的条件。的条件。一般编码方法一般编码方法 选择相应节点作为码字：选择相应节点作为码字：不同的路径上的分支，对应了不同的路径上的分支，对应了相应的码元符号，则可得到所编码字。相应的码元符号，则可得到所编码字。10001101001000构造构造即时码即时码编码举例编码举例（即时码，编码方式不同）（即时码，编码方式不同）都为即时码，但编码方式不唯一都为即时码，但编码方式不唯一编码举例（多元即时码）编码举例（多元即时码）译码方法译码方法 因为每一码元对应于一个
31、的树图分枝路径，则因为每一码元对应于一个的树图分枝路径，则即时码的即时码的树图树图可以用来可以用来译码译码。译码器系统对一串符号序列译码过程：。译码器系统对一串符号序列译码过程：1 1）首先从）首先从树根树根出发，根据接收的出发，根据接收的第一个码元符号第一个码元符号来选择应走来选择应走的第一条路径；的第一条路径；2 2）若沿着所选路径走到）若沿着所选路径走到某中间节点某中间节点，再根据接收的，再根据接收的第二个码第二个码元符号元符号来选择第二条路经；来选择第二条路经；3 3）若又走到中间节点，再依次继续选择路径，直到）若又走到中间节点，再依次继续选择路径，直到终端节点终端节点为止。这时，可根
32、据所经历的为止。这时，可根据所经历的枝路枝路，判断出所接收的码字。，判断出所接收的码字。4 4）重新）重新返回树根，返回树根，再作下一个接收码字的判断。再作下一个接收码字的判断。这样，便可将接收到的一串码符号序列译成信源符号序列。这样，便可将接收到的一串码符号序列译成信源符号序列。3 3、克拉夫特（、克拉夫特（KraftKraft）不等式）不等式定理定理 对于码符号为对于码符号为 的任意的任意r r元元即时即时码码 ，若所对应的码长，若所对应的码长 ，则必定满足：则必定满足：反之，若码长满足上式，则一定存在这样的反之，若码长满足上式，则一定存在这样的即时码即时码 。12,.,ql ll11iq
33、lir *可以证明，对于可以证明，对于唯一可译码唯一可译码也须满足也须满足KraftKraft不等式。不等式。12:,.,qCW WW12,.,rXx xx 这说明，其他唯一可译码并不比即时码占优。这说明，其他唯一可译码并不比即时码占优。而即时码很容易用而即时码很容易用树图法构造树图法构造，所以在讨论唯一可译码，所以在讨论唯一可译码时，时，只需要讨论即时码就可以了。只需要讨论即时码就可以了。定理定理 若存在一个码长为若存在一个码长为 的的唯一可译码唯一可译码，则一，则一定存在一个同样长度的定存在一个同样长度的即时码即时码。12,qllln例例：设二进制码树中设二进制码树中S=(sS=(s1 1
34、,s,s2 2,s,s3 3,s,s4 4),L),L1 1=1,=1,L 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,则则18922222322141 iKi122222332141iKi存在满足这种存在满足这种L Li i唯一可译码唯一可译码 000110 010101101101111码树码树111111000110 010
35、10110110设信源设信源编码后的码字为：编码后的码字为：12,.,qW WW码长为：码长为：12,.,ql ll码的码的平均长度（平均码长）平均长度（平均码长）为：为：1()qiiiLP S l5.6 5.6 变长信源编码定理变长信源编码定理（码符号（码符号/信源符号）信源符号）)(.)()()(.)(321321qqsPsPsPsPssssxPXn码的平均长度码的平均长度n信息传输率（码率）：信息传输率（码率）：平均每个平均每个码元携带的信息量码元携带的信息量，即，即编码后信道的信息传输编码后信道的信息传输率率：（比特（比特/码符号）码符号）LSHR)(若信道传输一个码符号平均需要若信道
36、传输一个码符号平均需要t t秒钟，则编码后信道的秒钟，则编码后信道的每秒传输的信息量为：每秒传输的信息量为：（比特（比特/秒）秒）LtSHtRRt)(/由此可见：由此可见：平均码长越短，信息传输效率越高。平均码长越短，信息传输效率越高。n紧致码（最佳码）紧致码（最佳码）对于某一信源和某一个码符号集合，若有一个对于某一信源和某一个码符号集合，若有一个唯一可译唯一可译码，码，它的平均码长小于其他唯一可译码的长度。它的平均码长小于其他唯一可译码的长度。无失真信源编码的无失真信源编码的基本问题基本问题就是寻找就是寻找紧致码紧致码。定理定理 若对一熵为若对一熵为H(S)H(S)的离散无记忆信源的离散无记
37、忆信源 S S 进行进行r r 元编码，则元编码，则总是可以找到一种无失真编码方法构成总是可以找到一种无失真编码方法构成唯一可译码唯一可译码，使其，使其平平均码长均码长满足：满足：)(1)(,log)(1log)(SHLSHrSHLrSHrr即说明：说明：下界下界：平均码长不能小于极限：平均码长不能小于极限H(s)/logr,H(s)/logr,否则唯一可译码不存在。否则唯一可译码不存在。上界上界：给出了平均码长的上界。但并不是说大于这个上界就不能：给出了平均码长的上界。但并不是说大于这个上界就不能构成唯一可译码。而是说构成唯一可译码。而是说在上界范围内，可找到唯一可译码在上界范围内，可找到唯
38、一可译码。证明：证明：1.1.下界证明：下界证明：LrSHlog)(0log)(rLSH詹森不等式詹森不等式)(,)(,log)log(iiiliiiiiiisPpsPrxxpxpi令因总可找到一种唯一可译码，其码长因总可找到一种唯一可译码，其码长满足满足CraftCraft不等式不等式，所以，所以则证得：则证得：由由CraftCraft不等式，此等式成立的充要条件：不等式，此等式成立的充要条件：即：即：),.,2,1()(loglog)(logqisPrsPlirii可见，只有当能够选择每个码长满足上述等式时候，平均码可见，只有当能够选择每个码长满足上述等式时候，平均码长才能够长才能够达到达
39、到这个下界值。这个下界值。由于由于l li i 必须为正整数，所以必须为正整数，所以 也必须也必须为为正整数正整数。那么，当该等式成立时，每个那么，当该等式成立时，每个信源符号的概率分布信源符号的概率分布必必须呈现如下形式：须呈现如下形式：)(logirisPl)(/1)(为正整数iiirsP如果这个条件满足，则只要选择：如果这个条件满足，则只要选择：）（qilii,.,2,1根据这些码长，按照根据这些码长，按照树图法树图法构造出一种构造出一种唯一可译码唯一可译码，所得，所得的码一定是的码一定是紧致码紧致码。2.2.上界证明：上界证明：只需证明存在只需证明存在一种唯一可译码满足一种唯一可译码满
40、足rSHLlog)(1即可。令即可。令),.,2,1()(logqisPiri则，选取每个码字的长度的原则是：则，选取每个码字的长度的原则是：),.,2,1(,)(logqisPliiriii不为正整数为正整数；，1iiil 的最小整数代表不小于为天花板函数，xx显然知显然知),.,2,1(,)(log)(logqirsPlrsPliliiiiii即即即即，即为即为CraftCraft不等式；因此，不等式；因此，用这样选择的码长用这样选择的码长满足满足CraftCraft不等式不等式，故故可构造唯一可译码可构造唯一可译码。但不一定是紧致码。但不一定是紧致码。两边对两边对i i求和，则有：求和，
41、则有：11iqlir由于由于右边的不等式两边进行如下处理：右边的不等式两边进行如下处理：1iil1)(logirisPl1log)(log)()(11rsPsPlsPiqiiiqii1)(1log)(SHrSHLr平均码长平均码长因此，平均码长因此，平均码长小于上界小于上界的的唯一可译码存在唯一可译码存在。两边乘以两边乘以P(P(s si i)后，求和。后，求和。另外由于另外由于无失真变长信源编码定理（香农第一定理）无失真变长信源编码定理（香农第一定理）离散无记忆信源离散无记忆信源S S的的N N次扩展信源次扩展信源 ，其熵，其熵为为 ，且编码器码元符号集为，且编码器码元符号集为 .对信源对信
42、源 进进行编码，总可以找到一种编码方法，构成唯一可译码，使信源行编码，总可以找到一种编码方法，构成唯一可译码，使信源S S中中每个信源符号每个信源符号s si i所需要的平均码长所需要的平均码长 满足满足 ()NH SNS当当 则得：则得：N NqNS,.,21rxxxX,.,21)(1)(,log)(1log)(SHNNLSHrSHNNLrSHrNrN即对应的码字长度。对应的码字长度。为符号为符号的平均码长；的平均码长；为扩展信源中每个符号为扩展信源中每个符号，其中，其中，iiiiqiiNrNNNPLSHNL.)()(lim1NLLN/证明证明：设离散无记忆信源：设离散无记忆信源X X的数学
43、模型的数学模型1.)(12121qiiqqppppsssspS).(,)(.)()(.)(212121NNNiiiiqqiNsssppppS1()1NqiiP),.2,1(,)().()()(21qisPsPsPPNiiiiN N次扩展次扩展由于无记忆性，有：由于无记忆性，有：)()(而,1)()(SNHSHSHLSHrNrNrNNrNSHNLSHSNHLSNHrNrrNr/1)()(1)()(即：rSHSHNLrNNlog)()(lim 显然：由前述定理，有：由前述定理，有：定理含义：定理含义：要做到无失真信源编码，变换每个信源符号平均所要做到无失真信源编码，变换每个信源符号平均所需最少的需
44、最少的r r元码元数是信源的熵值。元码元数是信源的熵值。若编码的平均码长小于信源的熵，则唯一可译码不若编码的平均码长小于信源的熵，则唯一可译码不存在，在译码时必然带来失真或差错。存在，在译码时必然带来失真或差错。同时，通过对扩展信源进行变长编码，当扩展长度同时，通过对扩展信源进行变长编码，当扩展长度N N足够大时，平均码长可达到此极限值。足够大时，平均码长可达到此极限值。信源的熵是无失真信源压缩的极限值。信源的熵是无失真信源压缩的极限值。rHHSSSHNNLNrNSSSHNLrNSSSHSSSHLSSSHrNNNNNNNNrNNrlog)()().(1limlim 且：/1log).(log)
45、.(则：1).().(2121212121定理推广：定理推广：可以推广到可以推广到平稳有记忆信源平稳有记忆信源和和马尔科夫信源马尔科夫信源：如果将定理中的下式改写：如果将定理中的下式改写：rSHNNLrSHNlog)(1log)()()(loglog)(SHSHNrrNLSHNrNLRNlog为编码后平均每个信源符号所能承载的最大信息量，即变长为编码后平均每个信源符号所能承载的最大信息量，即变长编码编码后信源后信源的的信息传输率（编码信息率）信息传输率（编码信息率）。这样，香农第一定理也可表述为：这样，香农第一定理也可表述为：若若R=H(S),R=H(S),就存在唯一可译变长编码；若就存在唯一
46、可译变长编码；若R H(S),R H(S),唯一唯一可译边长码不存在，不能实现无失真德信源编码。可译边长码不存在，不能实现无失真德信源编码。loglRrN则定义：则定义：等长编码等长编码 从从信道角度信道角度看，编码后看，编码后信道的信息传输率信道的信息传输率：)/(/)(码符号比特LSHR 由此可见，此时信道的信息传输率等于由此可见，此时信道的信息传输率等于无噪无损信道无噪无损信道的信道容的信道容量量C C，信息传输率最高。，信息传输率最高。因此，无失真信源编码的实质是：因此，无失真信源编码的实质是：对离散信源进行适当编码，对离散信源进行适当编码，使变换后新的码符号信源（信道的输入信源）尽可
47、能等概率分布，使变换后新的码符号信源（信道的输入信源）尽可能等概率分布，以使新信源的每个码符号平均所含的信息量达到最大，从而使信道以使新信源的每个码符号平均所含的信息量达到最大，从而使信道的信息传输率的信息传输率R R达到信道容量达到信道容量C C，实现信源与信道的统计匹配。，实现信源与信道的统计匹配。所以，无失真信源编码实质上就是所以，无失真信源编码实质上就是无噪信道编码问题。无噪信道编码问题。rSHNLLNlog/)(/而而rLSHRlog/)(则：则：即：当平均码长为极限值即：当平均码长为极限值H(S)/logrH(S)/logr时，则时，则 R=logr.R=logr.（香农第一定理）
48、（香农第一定理）无噪信道编码定理无噪信道编码定理 若若信道的信息传输率信道的信息传输率RR无噪无损信道无噪无损信道容量容量 C=logrC=logr，总，总能对信源的输出进行适当的编码，使得在能对信源的输出进行适当的编码，使得在无噪无损信道无噪无损信道上能上能无差错地、以最大信息传输率无差错地、以最大信息传输率C C传输信息；反之，若传输信息；反之，若R R大大C C，则无差错传输是不可能的。则无差错传输是不可能的。因此，因此，信道容量信道容量C C是无噪信道的无差错传输的最大信息是无噪信道的无差错传输的最大信息传输率。传输率。编码效率编码效率衡量各种编码距极限压缩值得情况：衡量各种编码距极限
49、压缩值得情况：)(loglog/夫信源一般平稳信源、马尔科rLHLrH./)(log)()(NLLrLSHLSHNr式中，无记忆信源实际平均码长极限平均码长码的剩余度码的剩余度：1特别地，在二元无噪无损信道中，编码效率为：特别地，在二元无噪无损信道中，编码效率为：所以，在二元无噪无损信道中信息传输率：所以，在二元无噪无损信道中信息传输率：()H sRL即：在二元信道中，可直接用编码的效率来衡量编码后信道的信即：在二元信道中，可直接用编码的效率来衡量编码后信道的信息传输率是否提高了。息传输率是否提高了。LSHLSH)(2log)(例：例：离散无记忆信源离散无记忆信源12()3/41/4ssSP
50、S其熵为：其熵为：H(S)=0.811 H(S)=0.811 比特比特/信源符号信源符号用二元码符号（用二元码符号（0 0，1 1）来构造一个即时码：）来构造一个即时码：S1=S1=0 0，s2=s2=1 1。这时平均码长这时平均码长 ，编码的效率编码的效率为为1L 0.811信道信息传速率信道信息传速率 R=0.811 R=0.811 比特比特/码元符号。码元符号。为了提高传输效率，可以对无记忆离散信源为了提高传输效率，可以对无记忆离散信源S S的扩展信源进行的扩展信源进行扩展，再进行编码：扩展，再进行编码：即时码即时码s1s1s1s19/169/160 0s1s2s1s23/163/161
