无失真信源编码定理教材

5.4等长信源编码定理1

若一组码中所有码字的码长都相同，即li=l（i=1，2，…，q），则称为等长码。2定理证明的基本思路是：把离散无记忆的N次扩展信源划分成两个互补的集合G和G'。一个集合包含的都是经常出现的信源序列，这个集合出现的概率接近于1。另一个集合虽包含的元素较多，但都不是经常出现的信源序列，总的出现的概率极小，趋于零。对高概率集G中的信源序列进行编码，而将低概率集G'中的信源序列舍弃，不编码。这样，所需的平均码长可以减少，而所引起的错误概率去很小。34

它是编码后平均每个信源符号能载荷的最大信息量，称R'为编码后信息传输率。可见编码后信源的信息传输率大于信源的熵，才能实现几乎无失真编码，为了衡量各种实际等长编码方法的编码效果，引进称为编码效率5.5变长码5.5.1唯一可译变长码与即时码

5

本节讨论对信源进行边长编码的问题。变长码往往在N（信源序列长度）不很大时就可编出效率很高而且无失真的码。同样，变长码也必须是唯一可译码，才能实现无失真编码。对于变长码，要满足唯一可译性，不但码本身必须是非奇异的，而且其任意有限长N次扩展码也都必须是非奇异的。所以，唯一可译变长码的任意有限长N次扩展码都是非奇异码。信源符号符号出现概率码1码2码3码4S11/20011S21/411101001S31/80000100001S41/8110110000001

对于码1，显然它不是唯一可译的，因为信源符号S2和S4对应于同一个码字11，码1本身是一个奇异码。对于码2，虽然它本身是一个非奇异码，但是它仍然不是唯一可以码。

因为当接收到一串码符号序列时无法唯一地译出对应的信源符号。

表5.4675.5.2即时码的树图构造法即时码的一种简单构造方法是树图法。对于给定码字的全体集合C={W1，W2，...,Wq}，可用码树来描述它。所谓树，既有根、枝，又有节点。。1.图中最上端A点为根，从根出发向下伸出树枝，树枝的数目等于码符号的总数r。2.树枝的尽头为节点，从节点出发再伸出树枝，每次每个节点伸出r枝，依次下去构成一棵树88.4用码树表述表5.4中的码41.在左图中，当某一个节点被安排为码字后，就不再继续伸枝，此节点称为终端节点（用粗黑点表示）。2.其他节点称为中间节点，不安排为码字（用空心圈表示），给每个节点所伸出的树枝分别从左向右标上码符号0，1，…，r。9任一即时码都可用树图法来表示。当码字长度给定时，即时码不是唯一的。在每个节点上都有r个分枝的树称为整树（满树），否则称为非整树（非满树）。当元节的码树的所有树枝都被用上时，第阶节点共有个终端节点，正好对应于长度为的等长码，可见等长码也是即时码的一种。105.5.3克拉夫特（Kraft)不等式1112定理5.6若存在一个码长为L1,L2,...,Lq的唯一可译码，则一定存在一个具有相同码长的即时码

不满足克拉夫特不等式的码，一定不是唯一可译码。码长满足克拉夫特不等式的码，也不一定是唯一可译码。克拉夫特不等式只是说明唯一可译码是否存在，并不能作为一种码制是否是唯一可译码的判断依据。5.5.4唯一可译变长码的判断法

根据唯一可译码的定义可知，当且仅当有限长的码符号序列能译成两种不同的码字序列，此码一定不是唯一可译变长码。假设下图中情况发生，13图5.10有限长码符号序列译成两种不同的码字序列

唯一可译码的判断方法：将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，则可判断此码C为唯一可译码。如何构成集合F,可以按如下步骤进行。首先，观察码C中最短的码字是否是其它码字的前缀。若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又有可能是某些码字的前缀，再将这些尾随后缀产生的新的尾随后缀列出，然后再观察这些新的尾随后缀是否是某些码字的前缀，1415

再将产生的尾随后缀列出，依此下去，直到没有一个尾随后缀是码字的前缀为止。这样，首先获得了由最短的码字能引起的所有尾随后缀，接着，按照上述步骤将次短码字、…...所有码字可能产生的尾随后缀全部列出。由此得到由码C的所有可能的尾随后缀的集合F。

【例5.2】现设码C={0，10，1100，1110，1011，1101}，根据上述测试方法，判断是否是唯一可译码。解：先看最短的码字：“0”，它不是其他码字前缀，所以没有尾随后缀。再观察码字“10”，它是码字“1011”的前缀，因此有尾随后缀：16C={0，10，1100，1110，1011，1101}所以，集合F={11,00,10,01,0,1,100,110,011,101}，其中“10”为码字，故码C不是唯一可译码。5.6变长信源编码定理

由上一节讨论可知，对于已知信源S可用码符号X进行变长编码，而且对同一信源编成同一码符号的即时码或唯一可译码可有许多种。究竟哪一种最好呢？从高效率传输信息的观点来考虑，当然希望选择由短的码符号组成的码字，就是用码长作为选择准则，为此我们引入码的平均长度。17编码后的码字为对应的码长分布为因为对唯一可译码来说，信源符号与码字是一一对应的，所以有则这个码的平均长度为它是每个信源符号平均需用的码元数。设信源为18

当信源给定时，信源的熵就确定（为比特/信源符号），而编码后每个信源符号平均用个码元来变换。那么平均每个码元携带的信息量即编码后信道的信息传输率（码率）为（比特/码符号）若传输一个码符号平均需要t秒钟，则编码后信道每秒钟传输的信息量为（比特/秒）可见，越短，越大，信息传输效率就越高。19

对某一信源来说，若有一个唯一可译码，其平均长度小于所有其它的唯一可译码的平均长度，则该码称为紧致码，或称最佳码。无失真变长信源编码的基本问题就是要找最佳码。20

码字平均长度不能小于极限值，否则唯一可译码不存在。定理给出平均码长的上界，但并不是说大于上界不能构成唯一可译码，而是我们希望尽可能短。定理给出紧致码的最短平均码长，并指出这个最短的平均码长与信源熵是有关的。2122为了衡量各种编码，定义变长码的编码效率。对于平稳有记忆信源对于无记忆信源则有式中

23

一定是小于或等于1的数。对同一信源来说，若码的平均码长越短，越接近极限值，信道的信息传输率就越高，也越接近于1，所以用码的效率来衡量各种编码的优劣。为了衡量各种编码与最佳码的差距，定义码的剩余度为编码效率越高，码剩余度越接近零。24【例5.4】

有一离散无记忆信源其熵为（比特/信源符号）25

若用二元码符号(0，1)来构造一个即时码:s1→0，s2→1，这时平均码长为（二元码符号/信源符号）编码效率为输出的信息率为26

为提高传输效率，再对信源S的二次扩展信源进行编码，其即时码如下表所示：这个码的平均长度为（二元码符号/信源符号）27aiP(ai)即时码s1s29/160s1s23/1610s2s13/16110s2s21/16111信源S中每一单个符号的平均码长为

（二元码符号/信源符号）其编码效率为编码复杂了，但信息传输率和效率有了提高。28

同样可以求得信源序列长度增加到3和4时