信源编码等长码

1、主讲：肖 竹 第三章 离散信源无失真编码无失真编码 第三章第三章 Part I1. 编码的基本概念编码的基本概念2. 唯一可译码唯一可译码3. 等长码与等长信源编码原理等长码与等长信源编码原理 编码实质上是对编码实质上是对信源的原始符号按一定的数学规信源的原始符号按一定的数学规则进行一种变换则进行一种变换。由于无失真信源编码可以不考虑抗。由于无失真信源编码可以不考虑抗干扰问题，所以它的数学描述比较简单。如干扰问题，所以它的数学描述比较简单。如图所图所示示, 就是一个就是一个编码器编码器。编编 码码 器器S(消息、信源符号集消息、信源符号集)S1,S2,SqW(码字符号集码字符号集)w1,w2,

2、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的序列，称为的序列，称为码字码字。即

3、即 Si(i=1,q) Wi=(xi1xi2xiLi) , xi1X(k=1,Li) Si= Si1,Si2,SiN Wi=(xi1xi2xiLi) , SiKS (k=1,Li)长度长度Li称为码字长度或简称称为码字长度或简称码长码长。所有这些码字的所有这些码字的集合集合C称为称为码码。映射：映射：一一对应，一一对应， 无压缩编码无压缩编码多对一，压缩编码多对一，压缩编码举例举例待发消息：待发消息： 阴阴 晴晴 雨雨 雪雪信源符号集：信源符号集： a1, a2, a3, a4用二进制信道：用二进制信道： 0,1，4个消息转化为个消息转化为4个二进制代码：个二进制代码：a1: 00, a2:

4、01 , a3: 10 , a4: 11, 码长为码长为2汉字电报：汉字电报：10000个常用字个常用字 10000个个4位十位十进进制制数数 每每个个十十进进制制数数字字 5位二位二进进制等重代制等重代码组码组u1 0000 01101 01101 01101 01101u2 0001 01101 01101 01101 01011 u10000 9999 10011 10011 10011 10011 信源消息信源符号集：0,1,2，,9码符号集： 0，1码序列 1. 二元码二元码 若码符号集为若码符号集为X=0,1,所得码字都是一些二元序列所得码字都是一些二元序列,则称为则称为二元码二元

5、码。 二元码是数字通信和计算机系统中最常用的一种码。二元码是数字通信和计算机系统中最常用的一种码。 2.等长码等长码(或称固定长度码或称固定长度码) 若一组码中所有码字的码长都相同若一组码中所有码字的码长都相同,即即 Li=L(i=1,2,q), 则称为则称为等长码等长码。 3.变长码变长码 若一组码中所有码字的码长各不相同若一组码中所有码字的码长各不相同,即任意码字由不同长即任意码字由不同长度度Li码符号序列组成码符号序列组成,则称为则称为变长码变长码。 4.非奇异码非奇异码 若一组码中所有码字都不相同若一组码中所有码字都不相同,即所有信源符号映射到不同即所有信源符号映射到不同的码符号序列，

6、的码符号序列，5.奇异码奇异码 若一组码中有相同的码字若一组码中有相同的码字, 信源消息到码字的映射信源消息到码字的映射不是不是一一对应一一对应则称码则称码C为为奇异码奇异码。-不具备唯一可译性不具备唯一可译性 6.同价码同价码 若码符号集若码符号集X:x1,x2,xr中每个码符号中每个码符号xi所占的传输时间所占的传输时间相同相同,则所得的码则所得的码C为为同价码同价码。 一般二元码是同价码。对同价码来说，等长码中每个码一般二元码是同价码。对同价码来说，等长码中每个码字的传输时间都相同；而字的传输时间都相同；而变长码中每个码字的传输时间就不变长码中每个码字的传输时间就不一定相同一定相同。电报

7、中常用的。电报中常用的莫尔斯码是非同价码莫尔斯码是非同价码，其码符号点，其码符号点()和划和划()所占的传输时间不相同。所占的传输时间不相同。 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,s

8、iN一一对应。一一对应。 举例，设信源举例，设信源S的概率空间为的概率空间为若把它通过一个二元信道进行传输，为使信源适合信若把它通过一个二元信道进行传输，为使信源适合信道传输，就必须把信源符号道传输，就必须把信源符号Si变换成变换成0,1符号组成的码符号组成的码符号序列符号序列(二元序列二元序列)。我们可采用不同的二元序列其。我们可采用不同的二元序列其与信源符号与信源符号Si一一对应，这样就可得到不同的二元码，一一对应，这样就可得到不同的二元码，如如表表3.1所示。所示。表表3.1等长非等长非奇异码奇异码变长非变长非奇异码奇异码 求码的求码的N次扩展码：次扩展码： 求码求码2的二次扩展码的二次

9、扩展码 :s1=0；s2=01；s3=001;s4=111信源信源S的二次扩展信源的二次扩展信源 S2=a1=s1s1,a2=s1s2,a3=s1s3,a16=s4s4所以码所以码2的二次扩展码为的二次扩展码为 8. 唯一可译码唯一可译码 若码的任意一串有限长的码符号序列若码的任意一串有限长的码符号序列只能被唯一只能被唯一地译成所对应的信源符号序列地译成所对应的信源符号序列,则此码称为则此码称为唯一可译唯一可译码码,或单义可译码或单义可译码。否则，就称为。否则，就称为非唯一可译码非唯一可译码或或非非单义可译码。单义可译码。 例如例如,表表3.1中中码码1是唯一可译码是唯一可译码,而码而码2是非

10、唯一可是非唯一可译码。译码。因为对于码因为对于码2，其有限长的码符号序列能译成，其有限长的码符号序列能译成不同的信源符号序列。如码符号序列为不同的信源符号序列。如码符号序列为0010，可译，可译成成s1s2s1或或s3s1，就不唯一了。，就不唯一了。表表3.1唯一可译码唯一可译码非唯一非唯一可译码可译码唯一可译码唯一可译码若若W中任一有限长的码字序列中任一有限长的码字序列 （即有限长的一（即有限长的一串串W），可以被唯一地分割成一个一个码字，就称为是单义），可以被唯一地分割成一个一个码字，就称为是单义可译或唯一可译的，可译或唯一可译的，从扩展性定义：码的任意从扩展性定义：码的任意N次扩展码都是

11、非奇异码，则唯一可译次扩展码都是非奇异码，则唯一可译信源字母信源字母概率概率码码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是一一对应的（

12、非奇异码一一对应的（非奇异码），但由它所构成的序列不能被唯一分割。比如码字序列01110，可以分割成0,1,1,1,0;也可分割成0,1,11,0；0,11,1,0；或0,111,0等,因而也不是唯一可译的。但它与码码A还有不同之处还有不同之处：只要在码字之间留有空隙（例如像莫尔斯电报那样）或者加个“逗号”，就可以正确译码。 码码D: 0 01 011 0111 3、码D正是在码B各码字（除了w1）之前加了起一个逗加了起一个逗号作用的码元号作用的码元“0”，从而成为唯一可译的，但这就使平均码长增加了0.5bit； 码码B: 0 1 11 111 码码C: 0 10 110 111 4、码C是唯

13、一可译的,因为任一串有限长的码字w, 如 1 0 0 1 1 1 0 1 1 0 1 0 只能被分割成 10，0，111，0，110，10 任何其他分割方法都会产生一些不属于代码W的 码字（如1，001，11，011，010）； 码码E: 0 01 011 111 a1 a2 a3 a45、比较微妙的是码E：当收端收到“0”时，仍不能仍不能及时判决为及时判决为a1，必须等到第二个码元来时，也许才可做出判断。例如，当第二个码元为“0”时，就可判断前一个“0”对应于a1；但若第二个码元仍为“1”，则还无法做出判断，因为是a2或a3的可能性都还存在。所以它的译码就要等待一段时间。特别是若遇到如下的码

14、字序列： 0 1 1 1 1 1 1 1 11 1 1 1 1 其中只有第一个码元为其中只有第一个码元为“0”，其余均为，其余均为“1”，收端，收端在开始几步就无法加以判决。因为将开头几个码元在开始几步就无法加以判决。因为将开头几个码元“01111”判决成判决成“a1 1111”固然可以，但判决成固然可以，但判决成“a2 111”或或“a3 11”也未尝不行。也未尝不行。因而最好的办法就是待收到全部序列因而最好的办法就是待收到全部序列(如无第二个如无第二个“0”出出现现)后，再从尾开始进行判决，才能正确地决定第一个消息后，再从尾开始进行判决，才能正确地决定第一个消息是什么。是什么。这样一来，这

15、样一来，就产生了时间上的延迟和存储容量的增加就产生了时间上的延迟和存储容量的增加。甚。甚至可以说，也许要有无限大的存储容量才够用至可以说，也许要有无限大的存储容量才够用. 5、对于码、对于码F，即使从尾开始判断，也不是，即使从尾开始判断，也不是唯一可译的，如对码序列唯一可译的，如对码序列 1 0 1 1 1 1 0 1 0 既可译成既可译成“a2，a4，a2，a2”，也可判决，也可判决为为“a3，a4，a1，a2”。码码F: 0 10 101 111 a1， a2， a3， a4 即时码：即时码： 对于对于变长码变长码的定义：的定义： 字头（前缀）字头（前缀）： c=c1c2cn； c1c2c

16、i（in）是字头）是字头 异字头码（无前缀码）：异字头码（无前缀码）：任一码字都不是另一码字的字任一码字都不是另一码字的字头，可以即时译码，头，可以即时译码，即时码即时码 非异字头码非异字头码不能即时译码，称为不能即时译码，称为非即时码非即时码 即时码唯一可译，而即时码唯一可译，而唯一可译码不一定是即时码唯一可译码不一定是即时码信源符号信源符号码码C码码D码码E码码Fa1a2a3a40101101110010110111001011111010101111即时码唯一可译非即时码唯一可译非即时码可译非即时码非唯一可译 树图举例树图举例 =0,10,110,111. 对于D进制码，从树根开始，每次

17、引出D个分支，某一节点确定为码字之后，不再引出分支 010110111根111000码字是从树根节点出发到达终节点所对应的码符号序列即时码可以通过即时码可以通过树图树图来构造：根节点到终结点对应来构造：根节点到终结点对应的码符号序列的码符号序列 码的分类结构图码的分类结构图 平均码长平均码长 等长码：平均码长等长码：平均码长 = 每个码字码长每个码字码长1()Mmmmnn P C码字长度码字Cm出现概率码长的概率加权平均 变长码平均码长变长码平均码长 码：码：0, 1, 00, 11； 1, 10, 100, 1000， 假定各消息概率：（假定各消息概率：（0.4, 0.2, 0.2, 0.2

18、）1()Mmmmnn P C411421()1 0.4 1 0.22 0.22 0.21.4()1 0.42 0.23 0.24 0.22.2mmmmmmnn P Cnn P C N次扩展码平均码长次扩展码平均码长 问题：问题： 怎么使得平均码长尽量短？怎么使得平均码长尽量短？ 概率大概率大 码长小码长小 概率小概率小 码长大码长大1() ()Mmsmsmnnn P uP u原信源消息码字长度 信息传输速率信息传输速率 -信道单位时间内所传输的实际信息量信道单位时间内所传输的实际信息量 非压缩（无失真编码）非压缩（无失真编码） -信源的熵率（时间熵）信源的熵率（时间熵） 信息传输率定义：信息传

19、输率定义： (/)tH XRtn比特 秒信源熵平均码长码符号时间 若以码元时间为单位：若以码元时间为单位： D(/)H XRn比特 码元时间 举例举例 为提高传输效率使得平均码长尽可能短，进行为提高传输效率使得平均码长尽可能短，进行二进制不等长编码二进制不等长编码： 求信息传输速率。求信息传输速率。01234567,X1 1111111p(),4 488 16 16 16 16xxxxxxxxX 信源特殊分布，每个消息 的 概 率2(-h)紧致码。二进制符号最大信息量为1bit 01234567,00, 01, 110, 101, 1000, 1001, 1110, 1111xxxxxxxx

20、7iii=0D=-p(x )log(p(x )2.75log22.75(/)1112 22 32 42.7548162.75=1(/)2.75H XnH XRn 比特 符号（码元/符号）比特 码元时间 简单信源简单信源S: 信源符号集包含信源符号集包含K个符号个符号，码符号集包，码符号集包含含D个符号个符号，码字长度为，码字长度为n，码字个数为，码字个数为nD 对对S进行进行 等长无差错编码，得到码集等长无差错编码，得到码集C是唯一可译，必是唯一可译，必须满足：须满足： nKD信源消息信源消息概率概率码码1码码2u1u2u3u41/21/41/81/80011101100011011唯一可译不

21、是唯一可译必要非充分 码码1，码，码2 K=4，D=2，n=2 简单信源简单信源S的的L次扩展信源次扩展信源 进行等长编码，进行等长编码，扩展信源扩展信源 包含包含 个消息，得到长为个消息，得到长为n的唯一的唯一可译码，需满足：可译码，需满足： 这里这里K是信源符号集是信源符号集 的元素个数，的元素个数，D是码符号集是码符号集 ，n是码长。是码长。 对上式两边取对数并整理：对上式两边取对数并整理： LSLnKD信源序列中平均每个信源符号至少所需要的码符号数 LSLK12,Kaaa12,Dbbb（3-5）loglognKLD（3-6） 例例英文英文27个英文字符个英文字符(字母字母+空格空格)进

22、行等长二进制编进行等长二进制编码，即码，即K=27，L=1，D=2，根据（，根据（3-6），为得到唯一），为得到唯一可译码，应满足码长：可译码，应满足码长：实际码长取整数5logloglog2714.75logloglog2nKKnLLDD 每个英文字符需要每个英文字符需要5位二进制码，最大信息量位二进制码，最大信息量5bit（等概条件）。（等概条件）。 实际中，英文字符出现概率不同，再考虑字符间关联实际中，英文字符出现概率不同，再考虑字符间关联性（性（T+h,r，in+g）,已知东西多，得到信息少已知东西多，得到信息少。 收到收到5位二进制数的信息量远小于位二进制数的信息量远小于5bit，传

23、输效率低，传输效率低 若对极少出现的字符不进行编码，可以降低平均码长，若对极少出现的字符不进行编码，可以降低平均码长，进而提高传输率：进而提高传输率： 会引起失真。会引起失真。 但当满足一定条件，可以使失真趋于零但当满足一定条件，可以使失真趋于零 D(/)H XRn比特 码元时间0,PeL 定理定理3.1 等长编码定理：等长编码定理： 设离散无记忆信源设离散无记忆信源 的熵为的熵为H(X), S的的 L维扩展信源为维扩展信源为 ， 对信源输出的对信源输出的L长序列长序列 进行等长编码，码字是长度为进行等长编码，码字是长度为n的的D进制字符串，若满足：进制字符串，若满足：12,KSxxx 12,

24、LLKSsxs,1,2,.,LisiK logH XnLD则当则当L 可使译码差错可使译码差错Pe无穷小量反之，若反之，若 logH XnLD不可能实现无差错编码 比较定理比较定理3.1 和（和（3-6）的下界）的下界 log,loglogH XnnKLDLDH(X)是单符号信源是单符号信源 的熵的熵, 根据极大离散根据极大离散熵定理，信源等概分布时熵值最大，最大值为熵定理，信源等概分布时熵值最大，最大值为logK，即，即H(X)logK. 因此定理因此定理3.1给出了更紧的下界给出了更紧的下界对对n/L的要求更低。的要求更低。12,KSxxx 例例英文英文27个英文字符个英文字符(字母字母+

25、空格空格)进行等长二进制编进行等长二进制编码，即码，即K=27，L=1，D=2，根据（，根据（3-6），为得到唯一），为得到唯一可译码，应满足码长：可译码，应满足码长：logloglog2714.75logloglog2nKKnLLDD 若根据定理若根据定理3.1： 4.0314.03loglog2H XnLD 编 码 效率不同 编码效率：编码效率： 由定理由定理3.1 1loglogL H XH XnLDnD logL H XnD是小于是小于1的无量纲数，可以定义为等长的无量纲数，可以定义为等长编码的编码的编码效率编码效率 logLH XnD在编码环节，编码效率是衡量编码质量的重要指在编码环

26、节，编码效率是衡量编码质量的重要指标之一，对信源编码应当尽量提高编码效率标之一，对信源编码应当尽量提高编码效率 例例离散离散 无记忆信源无记忆信源012,Xp()0.1, 0.7, 0.2xxxX1logloglog3,11.585logloglog2nKKnLLDD 根据根据定理定理3.1，先计算熵：，先计算熵： 0.1log0.1 0.7log0.7 0.2log0.21.156(/)H X 比特符号 21.1561 1.116loglog2H XnLD 定理定理3.1要求的码长要求的码长下界比（下界比（3-6）要求）要求的码长下界的码长下界更紧致更紧致，但码长为整数，因但码长为整数，因此

27、码长都取此码长都取2对该信源进行二进制等长编码，先确定码长，因为信源消息对该信源进行二进制等长编码，先确定码长，因为信源消息数数K=3，信源序列长，信源序列长L=1，码符号数，码符号数D=2，根据（根据（3-6） 121 1.1550.587log2log2LH XnD 对原信源进行对原信源进行L=2维扩展，维扩展， 进行二进制等长编码进行二进制等长编码012,Xp()0.1, 0.7, 0.2xxxX编码效率取码长取码长为为42000 102101 112202 1222,X0.01,0.07, 0.02,p()x xx xx xx xx xx xx xx xx xX3logloglog3,23.170logloglog2nKKLnLLDD根据根据（3-6）确定码长）确定码长，扩展信源：，扩展信源：K=3，L=2，D=2000102101 1