1、信息论与编码技术第4章 无失真信源编码定理,苗付友2016年9月,本章介绍对离散信源进行无失真信源编码的要求、方法及理论极限，并引出香农第一定理。进一步加深对熵的物理意义的理解,信道编码,信道译码,信源译码,信源,信宿,信 道,干扰,5.1 编码器5.2 几个概念5.3 等长码5.4 渐进等分割性和典型序列5.5 等长信源编码定理5.6 变长码5.7 变长信源编码定理,主要内容,编码的实质 是对信源的原始符号按一定的数学规则进行的一种变换， 以码字代替原始信源符号，使变换后得到的码符号接近等概率分布，从而提高信息的传输有效性,5.1 编码器,信源,信宿,5.1 编码器,信源编码：从信源符号到码
2、符号的一种映射。,信源编码器：,定义：,S的元素si，i=1，2q叫做信号单元或消息（共有q个信源符号）。,信源,信宿,5.1 编码器,将信源符号集中的符号sj，i=1，2q（或者长为N的信源符号序列）变换成由基本符号xj,j=1,2r组成的长度为Li的一一对应的输出符号序列,即 C=W1,W2，Wq，,Wi 称为码字，li称为码字长度或简称码长,所有这些码字的集合C称为码.可见编码就是从信源符号到码符号的一种映射,若要实现无失真编码, 这种映射必须是一一对应的,可逆的。,信源,信宿,5.1 编码器,例：二元信道基本符号集为0,1,将信源符号s变换成由0和1符号组成的码符号序列(码元),即编码
3、。,5.1 编码器,例：下表为信源编码所使用的码表，信源输出序列的长度为L=1，信源共有4个符号，对应的概率空间为,5.1 编码器,以码1为例，将信源输出的符号按照固定的规则进行变换，即信源编码器输出共有4个码字，分别为00，01，10和11，码字的长度都为2，即li=2，（i=1，2，3，4）每个码字都是由取值于码符号集合0，1的两位二元码组成。也就是说，该码表将信源输出的每个符号映射成二元码。,各种码的定义,5.1 编码器,1.二元(代)码: 码符号集为X=0,1,所得码字都是一些二元序列,则为二元码.它是数字通信和计算机系统中最常用的一种码。,2.同价(代)码: 若码符号集X:x1,x2
4、,xr中每个码符号x所占的传输时间相同,则所得的码C为同价码.一般二元码是同价码.电报中常用的摩尔斯码是非同价码，其码符号()和划()所占的传输时间不同.,3. 等长码(固定长度码或定长码): 若一组码中所有(码字的)码长都相等,(即Li=L(i=1,2,q),则称为等长码。如下表中的码1。,4.变长码: 码中的码字长短不一， 如上图中的码2。,5.非奇异码：一组码中所有的码字都不相同。即,6.奇异码：一组码中有相同的码字，即,码1奇异，码2非奇异。,7.码的N次扩展码 码C把信源S中的符号si一一变换成码C中的码字Wi,则码C的N次扩展码是所有N个码字组成的码字序列的集合。 若码 其中,则N
5、次扩展码为,每个码字Bi 与N此扩展信源SN中每个信源符号序列,一一对应。,例子：信源S的概率空间为，二元信道传输，si0或1,可以求得信源S的任意N次扩展码。码1的二次扩展码: 1)信源S的二次扩展信源 S2=1=s1s1,2=s1s2,3=s1s3,16=s4s4，共qN=42=16个符号2）S的二次扩展码,注: 奇异码不是唯一可译码;非奇异码有唯一可译码,又有非唯一可译码。,唯一可译码又分为非即时译码和即时码.,非即时译码: 接收端收到一个完整的码字后,不能立即译码,而等下一码字开始接收后才判断是否可以译码.,8.唯一可译码 若码的任意一串有限长的码符号序列,只能被唯一的译成所对应的信源
6、符号序列,则称为唯一可译码。,码1:如码符号序列为码符号序列为0010 s1 s3 唯一可译码,s 1 s 2 s1,s3 s1,是非唯一可译码,码2. 0010 可能译为,注: 奇异码不是唯一可译码;非奇异码有 唯一可译码,又有非唯一可译码。,唯一可译码又分为非即时译码和即时码.,非即时译码: 接收端收到一个完整的码字后,不能立即译码,而等下一码字开始接收后才判断是否可以码.,表中码3是非即时码,码4是即时码.只要收到1就表示码意完整。,即时码(非延长码或非续长码): 任意一个码子都不是其它码字的前缀部分. 在延长码中有的是唯一可译,有的不是.如码3是唯一可译码。,综上所述，码的分类有：,（
7、非延时码）,表5-2 不同的码字,1是奇异码，码2是非奇异码。,码3是唯一可译码，码2不是唯一可译码,码3是非即时码。码4中只要收到符号1就表示该码字已完整，可以立即译码，所以码4是即时码,又称为非延长码，任意一个码字都不是其他码字的前缀部分构.,码树平均码长信息传输率编码效率克劳夫特不等式,5.2 几个基本概念,1.码树通常情况下可以用码树来表示各个码字的构成，如果码字序列符号为m进制的，可以用m个符号的码树来构造码字，每个码树有一个树根A,树根有m个树枝，树枝的尽头称为叶节点,中间每个节点生出的树枝的数量等于码符号的数量m，从而形成m进制的码树。,5.2.1 几个基本概念-码树,图4-3（
8、a）二进制码树,图4-3（b）图是三进制码树,b图为非满树，是一个三进码树，有三个支，码是不定长的。码树一定是即时码，反之，任何即时码都是用码树来表示。即时码的码树可以用来译码,A为根分为两个支，有n=3级节点，其终端结点为23=8个表示信源符号，a图为满树.,5.2.1 几个基本概念-码树,【例5.2-1】某地二月份天气的概率分布统计如下：雨天的概率是1/8，雪天的概率也是1/8，阴天的概率是1/4，晴天的概率是1/2。设x1表示雨天，x2表示雪天，x3表示阴天，x4表示晴天，则其离散无记忆信源的概率空间为,5.2.1 几个基本概念-码树,表5-3 两种信源编码方案,采用两种信源编码方案编成
9、的码字如下表所示。绘出方案一和方案二的码树，试比较方案1和方案2的码字哪个有效性更好一些？,5.2.1 几个基本概念-码树,表5-3 两种信源编码方案,5.2.2 几个基本概念-平均码长,编码后的每个信源符号平均所需的码元（码符号）个数。 单位为“码元/信源符号”。 对单个信源符号进行编码，设信源为,2、平均码长,若每个码字对应的码长为Ki（i1，2q）则该码的平均码长为,（码元/信源符号）,5.2.1几个基本概念-平均码长,方案1的平均码长,方案2的平均码长,（码元/信源符号）,（码元/信源符号）,编码后信息传输率R 又称为码率，是指编码后每个码元载荷的信息量。单位为“比特/码元”或“比特/
10、码符号”。,5.2.3 几个基本概念-信息传输率,【例4.2-1】中信源熵H(x)1.75比特/符号，方案1编码后每个码元载荷的平均信息量：,方案2编码后每个码元载荷的平均信息量：,（比特/码元）,（比特/码元）,由于每个二进制码元所能携带的最大信息量为1比特，所以方案2是一种最佳编码。,编码效率：表示编码后每个码元的实际信息量和能承载的最大信息量的比值。 假设码元为m进制，即可取m种可能值，则每个码元所能承载的最大信息量为log m 比特/码元：,5.2.3 几个基本概念-编码效率,二元编码效率,33,方案2编码后每个码元载荷的平均信息量：,（比特/码元）,（比特/码元）,方案1编码后每个码
11、元载荷的平均信息量：,从编码效率看，方案1的编码效率为0.875，方案2的编码效率为1。所以方案2比方案1的有效性要更好一些 。,5.2.4 几个基本概念-信息传输率,5.2.5 几个基本概念-Kraft不等式,5、克劳夫特不等式 用码树的概念可以推导出唯一可译码存在的充要条件，即各码字的长度ki 应符合不等式,m是进制数，n是信源符号数 ki -码字Ci的长度,称之为克劳夫特(Kraft)不等式,5.2.5 几个基本概念-Kraft不等式,该不等式指出了即时码的码长必须满足的条件。 麦克米伦证明惟一可译码也满足此不等式； 在码长选择的条件上，即时码与唯一码是一致的。 克劳夫特不等式给出了m元
12、码中，信源序列中的消息数n与码字的各个码长之间的关系。说明，若三者满足上式，至少能构成一种这样码长的即时码或惟一可译码，否则无法构造即时码或惟一可译码。,5.2.5 几个基本概念-Kraft不等式,【例5.2-2】设二元码树中,不存在满足这种Ki的唯一可译码。如码字为0，10，11，110。试将码字长度改为 则此时,这样的码就存在唯一可译码， 如码字为0，10，110，111。,0,10,110,11,码字为,不是唯一可译码,要实现上述码必须在中间放置码字,1,111,可以用码树进行检查,这样就产生了非延长码0，10，110，111 .,码字0，10，010，111虽然也满足克劳夫特不等式，却
13、它并不是唯一可译码。这是因为，克劳夫特不等式并不能作为判别一种码是否为即时码或唯一可译码的依据。例如，码组中有长度相等的两个码字，则这两个码字无论是否相同，都有可能使不等式成立，然而，当这两个码字相同时，它们一定不是唯一可译码。因此，唯一可译码一定满足克拉夫特不等式，反之，满足克拉夫特不等式的码不一定是唯一可译码。,5.2.5 几个基本概念-Kraft不等式,特点：一组码中所有(码字的)码长都相等无失真信源编码条件：信源符号si（i=1,2,q）与码符号序列Wi一一对应。（唯一可译码）信源的任意N次扩展码也应该是唯一可译码。例：某信源X有8种等概率符号，求二元等长码长度。信源序列熵达到最大值，
14、由最大熵定理H(X)log m ，可以用3个二进制码元对该信源进行无失真编码.即码长为K=3 码元/符号,5.3 等长码,5.3 等长码,而取 2.55码元/符号,只有22.55 =5.856种可能码字,还有部分符号没有对应的码字,一旦这些符号传到接收端将引起译码错误。,但是，若信源输出概率不相等，如p(x)=0.4，0.18，0.1，0.1，0.07，0.06，0.05，0.04,则 比特/符号,s1s2s3s4s5s6s7s8,w1w2w3w4w5w6,X,因此，非等概率信源不能依据信源熵提供的长度值对信源进行编码。,依据最大信源熵提供的长度值对信源进行编码。,任何概率不为0的信源符号都需
15、要一一对应一个不同的码字。,5.3 等长码,例：如果有四个信源符号s1，s2，s3，s4，采用二元编码(码元为0,1；个数为2)，KL=2，则可以编成s1=00，s2=01，s3=10，s4=11。,若对信源进行等长编码，则必须满足其中，KL是码长，m是码符号集中的码元数，q 信源符号个数。,B1=w1w1w1B2=w1w1w2B =wqwqwq,1=s1s1s12=s1s1s2 =sqsqsq,L个信源符号,L个1次码字,例：2次扩展信源二元编码,5.3 等长码,例：对英文电报的32个符号进行二元编码，根据上述关系：,继续讨论上面的例子，我们已经知道英文的极限熵是1.4bit,远小于5bit
16、。也就是说，5个二元码符号只携带1.4bit的信息量，实际上，5个二元符号最多可以携带5bit信息量。,如何做到让平均码长缩短，提高信息传输率？,5.3 等长码,例：设信源,而其依赖关系为：,注：估计信源编码长度KL时，并没有考虑不同信源符号出现的 概率以及依赖关系；,5.3 等长码,若不考虑符号间的依赖关系，对此信源作二次扩展若考虑符号间的依赖关系，则,可见，由于符号间依赖关系的存在，扩展后许多符号出现的概率为0。可以将此信源看做包含s1s2, s2s1, s3s4, s4s3 共4个符号的新信源，KL=logq/logm=log4/log2=2 可得码长 ， 但平均每个信源符号所需码符号个
17、数为,即共24=16个码字,我们仍以英文电报为例，在考虑了英文字母间的相关性之后，我们对信源作L次扩展，在扩展后形成的新信源（也就是句子）中，有些句子是有意义的，而有些句子是没有意义的，我们可以只对有意义的句子编码，而对那些没有意义的句子不进行编码，这样就可以缩短每个信源符号所需的码长。第5.5中的等长信源编码定理给出了进行等长信源编码所需码长的极限值。,5.3 等长码,大数定律：对应独立等分布的随机变量X1 X2 Xn,当n足够大时， 接近于其数学期望值E(X).S1 S2 SN统计独立等同分布的随机变量，联合概率为P(S1 S2 SN),N足够大时， (-log P(S1 S2 SN)/N
18、接近于信源熵H(S), P(S1 S2 Sn)接近于2-NH(S).,5.4 渐进等分割性（AEP）和典型序列,定理5.1(渐进等分割性AEP)若随机序列S1 S2 SN中Si (i=1,2,N)相互统计独立并且服从同一概率分布P(s)， 又 则 以概率收敛于H(S).,5.4渐进等分割性（AEP）和典型序列,定义（典型序列 ）N长的序列 对于任意小的正数，满足 即 则称N长的序列 为典型序列 。反之，满足的N长的序列 为非典型序列。,5.4 渐进等分割性（AEP）和典型序列,GN : N长典型序列 集 : N长非典型序列 集,5.4 渐进等分割性（AEP）和典型序列,5.4 渐进等分割性（A
19、EP）和典型序列,52,5.5 等长信源编码定理,等长信源编码定理 一个熵为H(S)的离散无记忆信源，若对其N次扩展信源进行等长r元编码，码长为l，对于任意 0 ，只要满足,则可以实现几乎无失真编码，反之，若：,则不可能实现无失真编码,5.5 等长信源编码定理,定理的条件式可写成：,左边表示长为 l 的码符号所能载荷的最大信息量，而右边代表长为N的序列平均携带的信息量。因此，只要码字传输的信息量大于信源序列携带的信息量，总可以实现无失真编码 。,定理的条件式也可写成：,编码效率,5.5 等长信源编码定理,等长码最佳编码效率,码字长度 ，在定长编码中是定值， 是码源符号个数，当编码器容许的输出信
20、息率,即每个信源符号必须输出的码长是 时，只要 ，且所取的符号数 足够大，此时这种编码器一定可以做到几乎无失真，即收端的译码差错概率接近于零。,例:设离散无记忆信源求信源符号序列长 解：,自信息方差,=3/4(log3/4)2+1/4(log1/4)2-(0.811)2,=0.4715,则 ：,允许错误概率pe10-5,若对信源X采取等长二元编码,要求编码效率=0.96,编码效率定义,最佳编码效率,信源序列长度需长达4130万以上，才能实现给定的要求，这在实际中很难实现。,变长编码，编码后码长K是变化的。 如果概率大的符号用短码，概率小的符号用较长的码，则大量信源符号编成码后，平均每个信源符号
21、所需的输出符号数就可以降低，就可以提高编码效率。,5.6 变长码,单个符号变长编码定理 : 若一离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度 满足下列不等式即,码字的平均码长不能小于极限值H(X)/log m，否则唯一可译码不存在。平均码长小于上界值时，唯一可译码肯定存在，但并不是说大于这个上界不能够成为唯一可译码，而是因为希望平均码长尽可能短。,用变长编码可以达到相当高的编码效率,一般所要求的符号长度可以比定长编码小得多,由前式得编码效率的下界：,如上次的例子: m=2,logm=1,H(x)=0.811比特/符号 要求编
22、码效率=0.96,定长编码符号序列长为： L=4.13107,编码效率总是小于1,用此衡量各种编码方法的优劣,为了衡量各种编码方法与最佳码的差距,定义码的剩余度为:,例 设离散无记忆信源的概率空间为,求:用二元码符号(0,1)来构成一个即时码时的信息传输率。,解：,=0.81比特/信源符号,平均码长：,码元/信源符号,码的平均长度：,信源中每一个单个符号的平均码长：,信息传输率:,编码效率：,由此可见编码越复杂,传输率越高. 若用定长,当编码效率=96% ,编码错误概率105,则信源序列长度 L4.13107,用同样的方法进行三次，四次信源扩展,即 L=3 ，L=4 ，,得 3=0.985=R
23、3 4=0.991=R4,1=0.81=R1 2=0.961,2.变长码,L不需太长,则可达到相当高的编码效率,且可以实现无失真编码,随着L增加,越接近1,编码后的信息传输率R也越来越接近无噪无损二元对称信道的容量,使信道得到充分的利用。,1.定长码需要信源序列长,且总存在译码差错。,结 论,设信源编码后码字：W1,W2, Wq ;码长分别为： l1,l2, lq唯一可译码: p(Wi)=p(si) i=1,2,q平均码长: （码元/信源符号）信息传输率（码率）-平均每个码元携带的信息量： R=H(S)/ 比特/码元,某一信源和码符号集若有一个唯一可译码，其平均长度 小于所有其他唯一可译码的平
24、均长度，则称该码为紧致码或最佳码。无失真信源编码的基本问题寻找紧致码定理5.7 若一个离散无记忆信源S具有熵为H(S),并有r个码元的码符号集 X=x1,xr, 则总可以找到一种无失真编码方法，构成唯一可译码，其平均长度满足 （下界） （非上界）,下界证明： 即因为是紧致码, 所以注意：等式成立的条件 ，即 li= - logr p(si) 时，平均码长才能达到这个下界。或者说 p(si)= (1/r)li （li为整数）,定理5.8 无失真变长信源编码定理(香农第一定理)离散无记忆信源S的N次扩展信源 SN=a1,a2,aqN, 其熵为H(SN)，并有码符号X=x1,x2,xr.对信源SN进行编码，总可以找到一种编码方法，构成唯一可译码，使得信源S中每个信源符号所需的平均码长满足,Hr(S) :r进制信源S的熵,定理5.8 推广到平稳有记忆信源:,编码后每个信源符号承载的信息量，即变长信源编码后信源的信息传输率。 与等长信源编码一致。即等长与非等长信源编码编码后信源的信息传输率理论极限是一致的，均为H(S)。香农第一定理也可表述为： 若RH(S),就存在唯一可译变长编码；若RH(S),唯一可译变长码不存在，不能实现无失真信源编码。,无失真信源编码的实质,5.2, 5.3, 5.5, 5.10,Assignments,
