信源编码等长码

主讲：肖竹第三章

离散信源无失真编码第三章

PartI编码的基本概念唯一可译码等长码与等长信源编码原理编码实质上是对信源的原始符号按一定的数学规则进行一种变换。由于无失真信源编码可以不考虑抗干扰问题，所以它的数学描述比较简单。如图所示,就是一个编码器。编码器S(消息、信源符号集){S1,S2,…,Sq}W(码字符号集){w1,w2,…,wq}码/信道符号集{X1,X2,…,Xr}图3.1无失真信源编码器3.1编码的基本概念适合信道传输输入信源符号S={S1,S2,…,Sq}。同时存在另一符号X={x1,x2,…,xr}，一般元素xj是适合信道传输的，称为码符号(或者码元)。编码器是将信源符号集中的符号Si(或者长为N的信源符号序列)变换成由xj(j=1,2,…,r)组成的长度为Li的一一对应的码符号序列Wi的序列，称为码字。即Si(i=1,…,q)↔Wi=(xi1xi2…xiLi),xi1∈X(k=1,…,Li)Si={Si1,Si2,…,SiN}↔Wi=(xi1xi2…xiLi),SiK∈S(k=1,…,Li)长度Li称为码字长度或简称码长。所有这些码字的集合C称为码。映射：一一对应，无压缩编码多对一，压缩编码[举例]待发消息：阴晴雨雪信源符号集：{a1,a2,a3,a4}用二进制信道：{0,1}，4个消息转化为4个二进制代码：{a1:00,a2:01,a3:10,a4:11},码长为2汉字电报：10000个常用字↔10000个4位十进制数

每个十进制数字↔5位二进制等重代码组u1

↔0000↔01101011010110101101u2

↔0001↔01101011010110101011…u10000

↔9999↔10011100111001110011信源消息信源符号集：0,1,2，…,9码符号集：0，1码序列

码的定义

1.二元码

若码符号集为X={0,1},所得码字都是一些二元序列,则称为二元码。二元码是数字通信和计算机系统中最常用的一种码。

2.等长码(或称固定长度码)若一组码中所有码字的码长都相同,即

Li=L(i=1,2,…,q),则称为等长码。

3.变长码若一组码中所有码字的码长各不相同,即任意码字由不同长度Li码符号序列组成,则称为变长码。

4.非奇异码若一组码中所有码字都不相同,即所有信源符号映射到不同的码符号序列，5.奇异码

若一组码中有相同的码字,信源消息到码字的映射不是一一对应则称码C为奇异码。---不具备唯一可译性6.同价码若码符号集X:{x1,x2,…,xr}中每个码符号xi所占的传输时间相同,则所得的码C为同价码。一般二元码是同价码。对同价码来说，等长码中每个码字的传输时间都相同；而变长码中每个码字的传输时间就不一定相同。电报中常用的莫尔斯码是非同价码，其码符号点(•)和划(—)所占的传输时间不相同。

7.码的N次扩展码假设某码C,它把信源S中的符号Si一一变换成码C中的码字Wi,则码C的N次扩展码是所有N个码字组成的码字序列的集合。若码C={W1,W2,…,Wq}其中则N次扩展码可见,N次扩展B中,每个码字Bi(i=1,…,qN)与N次扩展信源SN中每个信源符号序列Si={si1,si2,…,siN}一一对应。举例，设信源S的概率空间为若把它通过一个二元信道进行传输，为使信源适合信道传输，就必须把信源符号Si变换成0,1符号组成的码符号序列(二元序列)。我们可采用不同的二元序列其与信源符号Si一一对应，这样就可得到不同的二元码，如表3.1所示。表3.1等长非奇异码变长非奇异码求码的N次扩展码：

求码2的二次扩展码:[s1=0；s2=01；s3=001;s4=111]信源S的二次扩展信源

S2=[a1=s1s1,a2=s1s2,a3=s1s3,…,a16=s4s4]所以码2的二次扩展码为

8.唯一可译码若码的任意一串有限长的码符号序列只能被唯一地译成所对应的信源符号序列,则此码称为唯一可译码,或单义可译码。否则，就称为非唯一可译码或非单义可译码。

例如,表3.1中码1是唯一可译码,而码2是非唯一可译码。因为对于码2，其有限长的码符号序列能译成不同的信源符号序列。如码符号序列为0010，可译成s1s2s1或s3s1，就不唯一了。表3.1唯一可译码非唯一可译码唯一可译码[定义]若W中任一有限长的码字序列（即有限长的一串W），可以被唯一地分割成一个一个码字，就称为是单义可译或唯一可译的，W也叫做单义代码。从扩展性定义：码的任意N次扩展码都是非奇异码，则唯一可译[例]考虑以下几种变长码：

信源字母概率码A码B码C码D码E码Fa1a2a3a41/21/41/81/80011001111110101101110010110111001011111010101111[例]考虑以下几种变长码：

信源字母概率码A码B码C码D码E码Fa1a2a3a41/21/41/81/800110011111101011011100101101110010111110101011111、码A不是一一对应的（码字0同时对应a1与a2），奇异码，故不是唯一可译的（虽然它具有最小的码长L）；2、码B是一一对应的（非奇异码），但由它所构成的序列不能被唯一分割。比如码字序列01110，可以分割成0,1,1,1,0;也可分割成0,1,11,0；0,11,1,0；或0,111,0等,因而也不是唯一可译的。但它与码A还有不同之处：只要在码字之间留有空隙（例如像莫尔斯电报那样）或者加个“逗号”，就可以正确译码。

码D:0010110111

3、码D正是在码B各码字（除了w1）之前加了起一个逗号作用的码元“0”，从而成为唯一可译的，但这就使平均码长增加了0.5bit；

码B:0111111

码C:010110111

4、码C是唯一可译的,因为任一串有限长的码字w,如100111011010只能被分割成10，0，111，0，110，10任何其他分割方法都会产生一些不属于代码W的码字（如1，001，11，011，010）；

码E:001011111

a1a2a3a45、比较微妙的是码E：当收端收到“0”时，仍不能及时判决为a1，必须等到第二个码元来时，也许才可做出判断。例如，当第二个码元为“0”时，就可判断前一个“0”对应于a1；但若第二个码元仍为“1”，则还无法做出判断，因为是a2或a3的可能性都还存在。所以它的译码就要等待一段时间。特别是若遇到如下的码字序列：011111111…11111其中只有第一个码元为“0”，其余均为“1”，收端在开始几步就无法加以判决。因为将开头几个码元“01111”判决成“a11111”固然可以，但判决成“a2111”或“a311”也未尝不行。因而最好的办法就是待收到全部序列(如无第二个“0”出现)后，再从尾开始进行判决，才能正确地决定第一个消息是什么。这样一来，就产生了时间上的延迟和存储容量的增加。甚至可以说，也许要有无限大的存储容量才够用.

5、对于码F，即使从尾开始判断，也不是唯一可译的，如对码序列101111010既可译成“a2，a4，a2，a2”，也可判决为“a3，a4，a1，a2”。码F:010101111

a1，a2，a3，a4即时码：对于变长码的定义：字头（前缀）：c=c1c2…cn；c1c2…ci（i<n）是字头异字头码（无前缀码）：任一码字都不是另一码字的字头，可以即时译码，即时码非异字头码不能即时译码，称为非即时码即时码唯一可译，而唯一可译码不一定是即时码信源符号码C码D码E码Fa1a2a3a40101101110010110111001011111010101111即时码唯一可译非即时码唯一可译非即时码可译非即时码非唯一可译[树图举例]={0,10,110,111}.对于D进制码，从树根开始，每次引出D个分支，某一节点确定为码字之后，不再引出分支●●●ºººº010110111根111000码字是从树根节点出发到达终节点所对应的码符号序列即时码可以通过树图来构造：根节点到终结点对应的码符号序列码的分类结构图奇异码非奇异码唯一可译码非唯一可译码等长码非等长码即时码延时码平均码长等长码：平均码长=每个码字码长码字长度码字Cm出现概率码长的概率加权平均变长码平均码长码：{0,1,00,11}；{1,10,100,1000}，假定各消息概率：（0.4,0.2,0.2,0.2）N次扩展码平均码长问题：怎么使得平均码长尽量短？概率大码长小概率小码长大原信源消息码字长度信息传输速率-----信道单位时间内所传输的实际信息量非压缩（无失真编码）-----信源的熵率（时间熵）信息传输率定义：信源熵平均码长码符号时间若以码元时间为单位：[举例]为提高传输效率使得平均码长尽可能短，进行二进制不等长编码：求信息传输速率。信源特殊分布，每个消息的概率2^(-h)紧致码。二进制符号最大信息量为1bit

3.2等长码及等长编码定理

简单信源S:信源符号集包含K个符号，码符号集包含D个符号，码字长度为n，码字个数为对S进行

等长无差错编码，得到码集C是唯一可译，必须满足：

信源消息概率码1码2u1u2u3u41/21/41/81/80011101100011011唯一可译不是唯一可译必要非充分码1，码2K=4，D=2，n=2简单信源S的L次扩展信源进行等长编码，扩展信源包含个消息，得到长为n的唯一可译码，需满足：这里K是信源符号集的元素个数，D是码符号集，n是码长。对上式两边取对数并整理：信源序列中平均每个信源符号至少所需要的码符号数（3-5）（3-6）[例]英文27个英文字符(字母+空格)进行等长二进制编码，即K=27，L=1，D=2，根据（3-6），为得到唯一可译码，应满足码长：实际码长取整数5每个英文字符需要5位二进制码，最大信息量5bit（等概条件）。实际中，英文字符出现概率不同，再考虑字符间关联性（T+h,r，in+g）,已知东西多，得到信息少。收到5位二进制数的信息量远小于5bit，传输效率低若对极少出现的字符不进行编码，可以降低平均码长，进而提高传输率：会引起失真。但当满足一定条件，可以使失真趋于零定理3.1等长编码定理：设离散无记忆信源的熵为H(X),S的L维扩展信源为，

对信源输出的L长序列进行等长编码，码字是长度为n的D进制字符串，若满足：则当可使译码差错无穷小量反之，若不可能实现无差错编码比较定理3.1和（3-6）的下界H(X)是单符号信源的熵,根据极大离散熵定理，信源等概分布时熵值最大，最大值为logK，即H(X)≤logK.因此定理3.1给出了更紧的下界对n/L的要求更低。[例]英文27个英文字符(字母+空格)进行等长二进制编码，即K=27，L=1，D=2，根据（3-6），为得到唯一可译码，应满足码长：若根据定理3.1：编