信源编码

信源编码自动化与电子工程学院黄翼虎([e-mail])一、编码的意义1、信源编码的目的；2、编码的实质；3、信源编码的基本思想；信源编码的目的提高信息传输的有效性；将模拟信号转换为数字信号；编码的实质对信源的原始符号按一定的数学规则进行的一种可逆变换；编码器信源码字M={m1,m2,…,mn}C={C1,C2,…,Cn}符号集A={a1,a2,…,ar}编码器输入：信源符号M={m1,m2,…,mn}；码符号（码元）：符号集A={a1,a2,…,ar}，一般元素ai是适合信道传输的；编码器：将信源符号mi变换成由aj(j=1,2,…,r)组成的长度为li的一一对应的序列，即：mi(i=1,2,…,m)=Ci=(aj1,aj2,…,ajli)这种码符号序列Ci称为码字，其长度li称为码字长度（码长），所有这些码字的集合C称为码。信源编码的基本思想信源编码提高信息传输有效性的基本思想，就是针对信源输出符号序列的统计特性，通过概率匹配的编码方法，将出现概率大的信源符号尽可能编为短码，从而使信源输出的符号序列变换为最短的码字序列。二、编码定义1、非奇异码和奇异码2、等长码和变长码3、单义码和非单义码4、非续长码5、码树6、码字平均长度7、编码效率非奇异码和奇异码如果码中所有的码字都不相同，称为非奇异码，反之，则为奇异码；等长码和变长码码中各个码字都是由同样多个码元构成的，称为等长码，反之，称为变长码；单义码和非单义码如果由码C的一组码字构成的任意长码序列，只能有唯一的方式分割成若干前后连接的码字，叫单义码，反之，为非单义码；例:C1=(1,01,00)是单义码，如码字序列10001101只可唯一划分为1、00、01、1、01;C2=(0,10,01)为非单义码，如序列01001可划分为0、10、01或01、0、01。非续长码设Ci={xi1,xi2,…,xim}是码C中的任一码字，而其他码字Ck={xk1,xk2,…,xkj}(jm)都不是码字Ci的前缀，则称此码为非续长码，也称为即时码。非续长码一定是单义码；反之，单义码不一定都是非续长码。例：对某个信源符号集合按照下面两种方式编码，试分析其异同。信源符号码1码2S111S21001S3100001S410000001非续长码例子相同点：码1、码2都是单义码；不同点：码2中，每个码字都以“1”为终端，这样在接收过程中，只要一出现“1”时，就知道这是一个码字已经终结，新的码字就要开始，因此当出现“1”后，就可以立即将收到的码元序列译成对应的信源符号；码1中，当收到一个或几个码元符号后，不能即时判断码字是否已经终结，必须等待下一个或几个码元符号收到后，才能作出判断。例：码1组成的序列：1000100101码2组成的序列：0001011001结论：码1是续长码，码2是非续长码。这两种码的结构有重要区别。非续长码的性能要好于续长码。码树对给定的码字的全体集合C={C1,C2,…,Cn}来说，可以用树来描述它。码树的构造：对一棵树，给每个节点所伸出的枝分别标上码元符号0、1、…、r-1，这样，叶节点所对应的码字就是从根出发到叶节点经过的路径所对应的码元符号组成。按树图法构成的码一定满足非续长码的充要条件，因为从根到叶所走的路径各不相同，而且中间节点不安排为码字，所以一定满足对前缀的限制。码树的例子该树的5个叶节点S1,S2,S3,S4,S5分别表示5个二进制码字0，100，111，1010，1011；100001111S3S1S2S4S5码字平均长度码字平均长度:设N个码字中的第I个码字的码长为ni，它所代表的编码对象xi的出现的概率为p(xi)，则码字的平均长度为iNiinxpL1)(编码效率编码效率用最小平均码字长度Lmin和实际的编码平均长度L之比来表示；当编码对象的平均信息量为H(X),编码所用的符号数目为D时，有DXHLlog)(min因此，编码效率为：DLXHLLlog)(min剩余度为：1R例子已知信源符号集合的概率分布为}81,81,41,21{)(},,,{4321XPxxxxX则H(X)=1.75bits/符号如采用2bit等长编码(如x1—00,x2—01,x3—10,x4—11)，则L=2,η=1.75/(2*log2)=0.875；如按照概率匹配原则编成如下非续长码：x1—0,x2—10,x3—110,x4—111，则L=(1/2)*1+(1/4)*2+(1/8)*3+(1/8)*3=1.75,η=1.75/(1.75*log2)=1；三、非续长码存在定理存在N个长度为n1,n2,…,nN的非续长码字的充要条件为其中D为编码符号的数目，N为码字的数目，n1,n2,…,nN为码字C1,C2,…CN分别对应的码长。定理证明；该定理给出了非续长码的存在性，但并未指出如何构造；不等式　　KraftDNini11例子14522222222141ini1161522222432141ini在码长n1=1,n2=n3=n4=2的条件下，一定不能构成非续长码，因为对于码长n1=1,n2=2,n3=3,n4=4的码可以有很多种，但可能构成的许多种码中至少可以找到一种是非续长的，因为信源符号码1码2S111S21001S300001S4010001例：四、平均编码长度设X表示离散信源，其消息Xi(i=1,2,…,N)的出现概率为p(xi)，如将它用符号集{a1,a2,…,aD}编成单义码，则码字平均长度L满足不等式：此外，存在D元唯一可译码，其平均编码长度L满足：该定理给出了无失真编码的性能的极限。编码符号的传信能力信源熵NiiiDXHnxpL1log)()(1log)()(1NiiiDXHnxpL五、最佳编码方法1、最佳编码定义2、仙农-范诺编码方法3、霍夫曼编码方法最佳码对于某一个信源和某一码符号集来说，若有唯一可译码，其平均编码长度小于所有其他唯一可译码的平均编码长度，则该码为最佳码。仙农-范诺编码方法编码对象：离散信源概率集合编码方法（对二元系统）按概率递减的方式将消息及其概率排列起来；将消息分成概率尽可能相同的两个子集，两个子集分别冠以码元符号“1”和“0”。将每个子集再划分为概率尽可能相等的两个子集，并分别冠以10，11和00，01，依此类推，直到子集只包括一个消息为止。},...,,{)(},...,,{2121nnpppXPxxxX例子将下列消息按二元先农-范诺方法编码（如下页）编码后可以计算得到：}0625.0,0625.0,125.0,25.0,0625.0,0625.0,25.0,125.0{)(},,,,,,,{87654321XPxxxxxxxxX1log75.2)(/75.2)(log)(8181DLHnxpLxpxpHiiiiii消息比特X2x5x1x6x3x4x7x80.250.250.1250.1250.06250.06250.06250.06250100011011110111100101110011011110111100011001011100110111101111消息概率编码码字主要问题当消息数目很多，而其概率又各不相同时，如何把一个消息集逐次划分为概率尽可能相同的两个或多个子集。该方法不能保证概率大的消息一定比概率小的消息能用较短的码字。霍夫曼编码方法编码对象：离散信源概率集合},...,,{)(},...,,{2121nnpppXPxxxX编码方法（对二元系统）将N个信源符号按概率递减的方式排列起来；用“0”，“1”码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个符号，从而得到只包含N-1个符号的新信源，称为S信源的缩减信源S1；将缩减信源S1的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别用0，1码符号表示，这样又形成了N-2个符号的缩减信源S2；依次继续下去，直到信源最后只剩下两个符号为止，将这最后两个符号分别用0，1码符号表示，然后从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即得出对应的码字。例子将下列消息按二元霍夫曼方法编码编码后可以计算得到：}01.0,1.0,15.0,17.0,18.0,19.0,2.0{)(},,,,,,{7654321XPxxxxxxxX96.0log72.2)(/61.2)(log)(7171DLHnxpLxpxpHiiiiii消息比特X10.20x20.19x30.18x40.17x50.15x60.10x70.01SS1100.11100.26S2100.35100.39100.61101.00S3S4S5111001101000100010000码方差码方差定义δ2=E[(ni-L)2]=∑p(xi)(ni-L)2对信源进行缩减时，若两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置次序可以是任意的，这种情况将影响码字的长度；在进行编码时，为了得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码；码方差例子设离散无记忆信源如下，分别按如下两种方式编码，分析哪种编码更好。1.01.02.02.04.054321xxxxxPXHuffman编码1x1x2x3x4x50.20.20.20.40.40.40.20.60.410101010110100000100011信源符号码字Huffman编码2x1x2x3x4x5101001011010011信源符号码字0.20.20.2010.40.20.4100.40.60.401编码1、2的分析比较这两种编码的平均码长和编码效率相同，分别为：L=2.2;η=0.965但它们的码方差不同。对于方法1，δ2=1.36,对于方法2，δ2=0.16可见方法2的码方差小，因此编码质量好霍夫曼编码方法编码的特点霍夫曼编码方法得到的编码不是唯一的每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1可以是任意的。但这不会影响码字的长度；对信源进行缩减时，若两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置次序可以是任意的；霍夫曼编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；霍夫曼编码方法缩减信源的最后两个码字总是最后一位不同，从而保证了编码结果是非续长码；六、仙农第一基本定理设S为无记忆离散信源，其熵为H(X)，经过一容量为C比特/符号的无干扰信道传送。总有可能将信源输出编成码字，使它在信道中的传信率任意地接近于信道容量C。