无失真信源编码定理

1、1 若一组码中所有码字的码长都相同，即li=l（i=1，2，q），则称为等长码。234rNLRlog)()(logl/)(/ )(rnSHRSH?称为 5 本节讨论对信源进行边长编码的问题。变长码往往在N（信源序列长度）不很大时就可编出效率很高而且无失真的码。 同样，变长码也必须是唯一可译码，才能实现无失真编码。对于变长码，要满足唯一可译性，不但码本身必须是非奇异的，而且其任意有限长N次扩展码也都必须是非奇异的。所以，唯一可译变长码的任意有限长N次扩展码都是非奇异码。信源符号信源符号符号出现概率符号出现概率码码1码码2码码3码码4S11/20011S21/411101001S31/800001

2、00001S41/8110110000001 对于码对于码1，显然它不是唯一可译的，因为信源符，显然它不是唯一可译的，因为信源符号号S2和和S4对应于同一个码字对应于同一个码字11，码，码1本身是一个奇本身是一个奇异码。异码。 对于码对于码2，虽然它本身是一个非奇异码，但是它，虽然它本身是一个非奇异码，但是它仍然不是唯一可以码。仍然不是唯一可以码。 因为当接收到一串码符号序因为当接收到一串码符号序列时无法唯一地译出对应的信源符号。列时无法唯一地译出对应的信源符号。 表表5.4671.图中最上端图中最上端A点为根，从点为根，从根出发向根出发向 下伸出树枝，树下伸出树枝，树枝的数目等于码符号的总数

3、枝的数目等于码符号的总数r。2.树枝的尽头为节点，从节树枝的尽头为节点，从节点出发再伸出树枝，每次每点出发再伸出树枝，每次每个节点伸出个节点伸出r枝，依次下去枝，依次下去构成一棵树构成一棵树9当当 元元 节的码树的所有树枝都被用上时，第节的码树的所有树枝都被用上时，第 阶节阶节点共有点共有 个终端节点，正好对应于长度为个终端节点，正好对应于长度为 的等长码，的等长码，可见等长码也是即时码的一种。可见等长码也是即时码的一种。rllllr101112 不满足克拉夫特不等式的码，一定不是唯一可不满足克拉夫特不等式的码，一定不是唯一可译码。码长满足克拉夫特不等式的码，也不一定是译码。码长满足克拉夫特不

4、等式的码，也不一定是唯一可译码。唯一可译码。 克拉夫特不等式只是说明唯一可译码是否存在，克拉夫特不等式只是说明唯一可译码是否存在，并不能作为一种码制是否是唯一可译码的判断依据。并不能作为一种码制是否是唯一可译码的判断依据。 根据唯一可译码的定义可知，当且仅当有限长的根据唯一可译码的定义可知，当且仅当有限长的码符号序列能译成两种不同的码字序列，此码一定码符号序列能译成两种不同的码字序列，此码一定不是唯一可译变长码。假设下图中情况发生，不是唯一可译变长码。假设下图中情况发生，131415 再将产生的尾随后缀列出，依此下去，直到没有再将产生的尾随后缀列出，依此下去，直到没有一个尾随后缀是码字的前缀为

5、止。这样，首先获一个尾随后缀是码字的前缀为止。这样，首先获得了由最短的码字能引起的所有尾随后缀，接着，得了由最短的码字能引起的所有尾随后缀，接着，按照上述步骤将次短码字、按照上述步骤将次短码字、.所有码字可能产生所有码字可能产生的尾随后缀全部列出。由此得到由码的尾随后缀全部列出。由此得到由码C的所有可能的所有可能的尾随后缀的集合的尾随后缀的集合F。16所以，集合所以，集合F=11,00,10,01,0,1,100,110,011,101，其中，其中“10”为码字，故码为码字，故码C不是唯一可译码。不是唯一可译码。17qWWW,.,21qiiilspL1)()(,),(,),(,2211qqsp

6、sspsspsPSqlll,.,21),.,2 , 1()()(qispWpii设信源为设信源为18LL)(SHLSHXHR)()(LtSHRt)(tR1920 码字平均长度码字平均长度 不能小于极限值不能小于极限值 ，否则唯一，否则唯一可译码不存在。定理给出平均码长的上界，但并不是可译码不存在。定理给出平均码长的上界，但并不是说大于上界不能构成唯一可译码，而是我们希望说大于上界不能构成唯一可译码，而是我们希望 尽尽可能短。定理给出紧致码的最短平均码长，并指出这可能短。定理给出紧致码的最短平均码长，并指出这个最短的平均码长与信源熵是有关的。个最短的平均码长与信源熵是有关的。LrSHlog)(L21222324811. 034log434log41)(22SH414321ssPS251L811. 0)(LSH符号/811. 0bitR 26?162731613163216311692L27aiP(ai)即时码即时码s1s29/160s1s23/1610s2s13/16110s2s21/16111?322722LL961. 027811. 0322二元码符号/961. 02bitR 28985. 03991. 04二元码符号/985. 03bitR