等长码与等长信源编码定理
一般说来,若要实现无失真的编码,不但要求信源符号si (i=1,2,…,q)与码字Wi (i=1,2,…,q )是一一对应的,而且要求码符号序列的反变换也是惟一的。也就是说,所编的码必须是惟一可译码。如果所编的码不具有惟一可译码性,就会引起译码错误与失真。
对于等长码来说,若等长码是非奇异码,则它的任意有限长N次扩展码一定也是非奇异码。因此等长非奇异码一定是惟一可译码。
如果对信源S的N次扩展信源进行等长编码。设信源S={s0,s1,…,sq},有q个符号,那么它的N次扩展信源共有qN个符号。又设码符号集为X=[x0,x1,…,xr]。现在需要把这些长为N的信源符号序列ai(i=1,2, ..., qN)变换成长度为l的码符号序列Wi。
若要求编得的等长码是惟一可译码必须满足. 即消息数要少于或等于码字数。
等价地,l/N>=logq/logr.l/N是平均每个信源符号所需要的码符号数。
对于等长惟一可译码,每个信源符号至少需要用logq/logr个码符号来变换,即每个信源符号所需最短码长为logq/logr个。
当r=2(二元码)时,log r=1,对于二元等长惟一可译码,每个信源符号至少需要用logq个二元符号来变换。这也表明,对信源进行二元等长不失真编码时,每个信源符号所需码长的极限值为logq个。
例如,英文电报有32个符号(26个英文字母加上6个字符),即q=32。若r=2,N=1(即对信源S的逐个符号进行二元编码),
l≥logq/logr=log32=5
这就是说,每个英文电报符号至少要用5位二元符号编码。
在前面的讨论中没有考虑符号出现的概率,以及符号之间的依赖关系。当考虑了信源符号的概率关系后,在等长编码中每个信源符号平均所需的码长就可以减少。当考虑符号之间的依赖关系后,有些信源符号序列不会出现,这样信源符号序列个数会减少,再进行编码时,所需平均码长就可以缩短。
仍以英文电报为例,在考虑了英文字母之间的依赖关系后,每个英文电报所需的二元码符号可以少于5。因为英文字母之间有很强的关联性,当用字母组合成不同的英文字母序列时,并不是所有的字母组合都是有意义的单字,若再把单字组合成更长的字母序列,也不是任意的单字组合都是有意义的句子。因此,考虑了这种关联性后,在N为足够长的英文字母序列中,就有许多是无用和无意义的序列,也就是说,这些信源序列出现的概率等于零或任意小。那么,当对长为N的英文字母序列进行编码时,对于那些无用的字母组合,无意义的句子都可以不编码。也就是相当于在N次扩展信源中去掉一些字母序列(这些字母序列出现的概率等于零或任意小),使扩展信源中的符号总数小于qN,这样使编码所需的码字个数大大减少,因此平均每个信源符号所需的码符号个数就可以大大减少,从而使传输效率提高。当然,这就会引入一定的误差。但是,当N足够长时,这种误差概率可以任意小,即可做到几乎无失真地编码。
等长信源编码定理:等长编码定理给出了信源进行等长编码所需码长的理论极限值。
一个熵为H(S)的离散无记忆信源,若对信源长为N的符号序列进行等长编码,设码字是从r个字母的码符号集中,选取l个码元组成。对于任意e>0,只要满足
则当N足够大时,可实现几乎无失真编码,即译码错误概率能为任意小。反之,若
则不可能实现无失真编码,而当N足够大时,译码错误概率近似等于1。
但是,等长信源编码要实现无失真编码是非常困难的,在实际中往往很难实现。因此,一般来说,当N有限时,高传输效率的等长码往往要引入一定的失真和错误,它不能像变长码那样可以实现无失真编码。
实质上,定长编码方法提高信息载荷能力的关键是利用了渐近等分性,通过选择足够大的M,把本来各个符号概率不等的信源输出符号序列变换为概率均匀的典型序列,而码字的唯一可译性则由码字的定长性来解决。
变长编码
若有一个唯一可译码,它的平均码长小于其他唯一可译码的长度,则称此码为紧致码或最佳码,无失真信源编码的基本问题就是寻找紧致码。
唯一可译码在码长方面并不比即时码占优。所以在讨论唯一可译码时,只需要讨论即时码就可以了。
离散无记忆信源的变长编码定理(仙农第一定理)
具体实现唯一可译变长编码的方法很多,但比较经典的方法还是仙农编码法、费诺编码法和霍夫曼编码法。其他方法都是这些经典方法的变形和发展。所有这些经典编码方法,都是通过以短码来表示常出现的符号这个原则来实现概率的均匀化,从而得到高的信息载荷效率;同时,通过遵守克拉夫特不等式关系来实现码字的唯一可译。
这个定理是香农信息论中非常重要的一个定理,它指出,要做到无失真的信源编码,信源每个符号所需要的平均码元数就是信源的熵值,如果小于这个值,则唯一可译码不存在,可见,熵是无失真信源编码的极限值。定理还指出,通过对扩展信源进行编码,当N趋向于无穷时,平均码长可以趋进该极限值。
还可以证明,如果我们不确切知道信源的概率分布,我们用估计的概率分布去进行编码时,平均码长会加长,但是如果估计的偏差不大的话,平均码长也不会增加太大。
无噪信道编码定理
若信道的信息传输率R不大于信道容量C,总能对信源的输出进行适当的编码,使的在无噪无损信道上能无差错的以最大信息传输率C传输信息,若R小于C,则无差错传输是不可能的。