第4章_离散信源编码理论.

第1页2019/12/20第四章──────────────离散信源编码理论4.1信源编码的基本概念4.3信源无失真编码4.4信息率失真函数及性质4.5信息率失真函数与信道容量4.7香农第三定理第2页2019/12/204.1信源编码的基本概念4.1信源编码的基本概念1.为什么要进行信源编码信源的两个重要问题信源输出的信息量计算问题；如何更有效地表示信源输出的问题。信源编码就是为了提高通信效率，对信源所发送的消息进行变换的方法之一。为什么要进行信源编码人们都希望无失真传送，首先要对信源无差错编码；数字技术应用越来越多，模拟信源通过数字化变成数字信号传送。第3页2019/12/204.1信源编码的基本概念2.信源编码的概念信源编码定义：指定能够满足信道特性（适合于信道传输）的符号序列—码序列，来代表信源输出的消息。编码器：完成编码功能的器件。离散信源输出的码序列离散信源输出的消息是由一个个离散符号组成的随机序列信源编码就是把信源输出的随机符号序列变成码序列nilLlx,,x,,xxXXXXXX2121)(mjkKky,,y,,yyYYYYYY2121)(第4页2019/12/204.1信源编码的基本概念2.信源编码的概念研究信源编码时，将信道编码和译码看成是信道的一部分，而突出信源编码；研究信道编码时，将信源编码和译码看成是信源和信宿的一部分，而突出信道编码。信道信源译码信源1.3信息传输系统模型S信源编码信宿噪声源信道编码信道译码加密编码解密译码SUVCC’XYn第5页2019/12/204.1信源编码的基本概念2.信源编码的概念讨论无失真信源编码先不考虑抗干扰问题，它的数学模型比较简单，如下图。编码器图2.4.0无失真信源编码器X{x1,x2,…,xn}Y{y1,y2,…,yL}{y1,y2,…,ym}(yl是由ki个yj组成的序列)信源符号：编码器的输入是信源符号X={x1,x2,…,xi,…xn}。信源符号序列：码符号/码元：元素yj是适合信道传输的符号，Y={y1,y2,…,yj,…ym}称为码符号/码元。XxxxxlLiiiii),,,(21x第6页2019/12/204.1信源编码的基本概念码字（码符号序列）：码长（码字长度）：ki称为码字长度或简称码长。编码：从信源符号到码符号的一种映射。若要实现无失真编码，这种映射必须是一一对应的，可逆的。Yyyyylikiiiii),,,(21y2.信源编码的概念编码器功能：将信源符号集当中的符号xi（或者长为L的信源符号序列）变换成由yj(j=1,2,…,m)组成的长度为ki的序列。Yyyyynixlikiiiiii),,,(),,2,1(21y）（）（iiiiiiiiiiiklYyLlXxyyyxxxllikL,,2,1,,2,1),,,(),,,(2121yx第7页2019/12/204.1信源编码的基本概念二元码：码符号集为X={0,1}，所得码字都是一些二元序列。定长码（等长码）：一组码中所有码字的码长都相同，即：ki=K(i=1,2,…,n)。变长码：一组码字中所有码字的码长各不相同，即任意码字由不同长度的码符号序列组成。非奇异码：一组码字中所有码字都不相同，即所有信源符号影射到不同的码符号序列。奇异码：一组码中有相同的码字。惟一可译码：码的任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号。即时码：不需要考虑后续的码符号，可以根据当前的码符号序列正确译出相应的码字。第8页2019/12/204.1信源编码的基本概念码树图m元（m进制）码树图树根：最顶部画一个起始点。树枝：从根部引出m条线段，每条线段都称为树枝。一级节点：自根部起,通过一条树枝到达的节点。一级节点最多有m个.n级节点：通过n条树枝达到的节点。最多有mn。终节点/终端节点：下面不再有树枝的节点。中间节点：除了树根和终节点以外的节点。联枝：串联的树枝。满树：在码树图中，当每一个码字的串联枝数都相同时，就是定长码。此时的码树称为满树。第9页2019/12/204.1信源编码的基本概念[例]：码1：显然不是惟一可译码。x2和x4对应于同一码字“11”，码1是一个奇异码。码2：是非奇异码，不是惟一可译码。当收到一串码符号“01000”时，可将它译成“x4x3x1”，也可译为“x4x1x3”，“x1x2x3”或“x1x2x1x1”等，这种码从单个码字来看虽然不是奇异的，但从有限长的码序列来看，它仍然是一个奇异码。码3：虽然是惟一可译码，但它要等到下一个“1”收到后才能确定码字的结束，译码有延时。码4：既是惟一可译码，又没有译码延时。码字中的符号“1”起了逗点的作用，故称为逗点码。即时码/前缀条件码/异前置码/异字头码/逗点码/非延长码：如果一个码的任何一个码字都不是其它码字的前缀。信源消息出现概率码1码2码3码4x11/20011x21/411101001x31/80000100001x41/8110110000001第10页2019/12/203.克拉夫特不等式克拉夫特不等式：m元长度为ki，i=1,2,…,n的即时码存在的充要条件是证明：必要条件：设即时码第i个码字的长度为ki，i=1,2,…,n，造一个码树图，在第ki级总共有个节点。第i个码字占据了第ki级的，根据即时码的定义，其后的树枝不能再用。对于N级满树，其后不能用的枝数为，那么总共不用的枝数为。N级满树第N级上的总枝数已知为mN，所以必有两边除以mN，就得：。11nikimikm1ikm4.1信源编码的基本概念ikNmnikNim1NnikNmmi111nikim第11页2019/12/203.克拉夫特不等式克拉夫特不等式：m元长度为ki，i=1,2,…,n的即时码存在的充要条件是证明：充分条件：如果式成立，则必成立，总可以把第N级上的树枝分成n组；各组中从第N级开始删除(i=1,2,…n)个枝；相对于N级满树，等于删除了所有可能的ki级节点的在该组中以第ki级节点作为终节点，就构造好了第i个码字。对所有码字如法炮制，则总共删除了所有mN个节点中的。由于，于是构造了一个即时码。11nikimikNmiikkmm1NnikNmmi111nikim4.1信源编码的基本概念nikim111nikim第12页2019/12/204.3信源无失真编码码字与信息率的关系有时消息太多，不可能或者没必要给每个消息分配一个码字；给多少消息分配码字可以做到几乎无失真译码？传送码字需要一定的信息率，码字越多，所需的信息率越大。编多少码字的问题可以转化为对信息率大小的问题；信息率越小越好，最小能小到多少才能做到无失真译码呢？这些问题就是信源编码定理要研究的问题。第13页2019/12/204.3信源无失真编码信源编码有定长和变长两种方法。定长编码：码字长度K是固定的，相应的编码定理称为定长信源编码定理，是寻求最小K值的编码方法。变长编码：K是变值，相应的编码定理称为变长编码定理。这里的K值最小意味着数学期望最小。无失真信源编码就是要求信源符号与码字之间形成一一映射的关系，并且要求编码输出的码字序列对应的反变换是惟一的，即是惟一可译码的，否则会造成译码错误或者失真。第14页2019/12/201.定长编码定理(1)定长编码定理定长编码定理：一个熵为H(X)的离散无记忆信源X1X2…Xl…XL，若对信源长为L的符号序列进行定长编码，设码字是从m个字母的码符号集中，选取K个码元组成Y1Y2…Yk…YK。对于任意ε0，δ0，只要满足当L足够大时，必可使译码差错小于δ，即译码错误概率能为任意小；反之，若：则不可能实现无失真编码，而当L足够大时，译码错误概率近似等于1。)(log2XHmLK2)(log2XHmLK4.3信源无失真编码第15页2019/12/20(1)定长编码定理4.3信源无失真编码)(log2XHmLK定理中的公式改写成：Klog2mLH(X)Klog2m：表示长为K的码符号序列能载荷的最大信息量LH(X)：代表长为L的信源序列平均携带的信息量平均符号熵。：mLK2log定长编码定理说明：只要码字传输的信息量大于信源携带的信息量，总可实现几乎无失真编码。译码差错率：编码效率：)()(XHXH)(1XH第16页2019/12/20(1)定长编码定理信源熵H(X)就是一个界限（临界值）。当编码器输出的信息率超过这个临界值时，就能无失真译码，否则就不行。信源编码定理从理论上说明了编码效率接近于1，即：的理想编码器的存在性，代价是在实际编码时取无限长的信源符号(L→∞)进行统一编码。说明：定长编码定理是在平稳无记忆离散信源的条件下论证的，但它同样适用于平稳有记忆信源，只是要求有记忆信源的极限熵和极限方差存在即可。对于平稳有记忆信源，定理中的熵应改为极限熵。1log)(2mLKXH4.3信源无失真编码第17页2019/12/20定长编码定理的意义(1)对于给定的离散无记忆信源X和码元数m，如果对X的N次扩展信源进行无失真等长编码，那么当码长K满足条件时，一定存在一种编码方案，能够实现无失真编码；反之，不可能进行无失真编码。4.3信源无失真编码2log()KmHXL(2)对于给定的信源离散无记忆X，信源的熵H(X)是一定的，当码符号数量m选定时，可以增加信源序列的长度L，使得无失真编码产生的每个符号平均长度尽可能小，但是无论怎样增加序列长度L，信源每个符号的平均码长不可能小于，即码长的极限为。KKL2()logHXm2()logHXm第18页2019/12/20定长编码定理的意义4.3信源无失真编码(3)当序列长度L一定，译码错误概率PE为2E22[()]()(,)iDIaXPLLL其中，D［I(ai)］为自信息量方差，定义为221[()]()[log()]()riiiiDIapapaHX当信源给定时，自信息方差是一定的，序列长度L越大，错误概率越小，要实现无失真编码，序列长度就应当足够长，使PE能够满足一定要求。第19页2019/12/20(2)举例[例4.1]：设单符号信源模型为：其信息熵为：H(X)=2.55（比特／符号）若编码效率为η=90%，取L=1，则取：ε=0.28，若译码差错率为δ=10－6,在差错率和效率要求都不苛刻的情况下，就必须有1600多万个信源符号一起编码，技术实现非常困难。04.005.006.007.010.010.018.04.0)(87654321xxxxxxxxxpX90.0)()(XHXH722106875.1)(xL4.3信源无失真编码1.定长编码定理82221()()(log)()7.8246.5021.322iiiiXDIxppHX2.5590%2.83bit/sK2.832=7.11第20页2019/12/20(2)举例[例]：离散无记忆信源：其信息熵为：自信息的方差为：12,31(),44xxXpx（比特／信源符号）811.034log434log41)(22XH4715.0)811.0(41log4143log43)()(log)()(2222212222niiiiXHxpxpxID4.3信源无失真编码若对信源X采取等长二元编码时，要求η=0.96，δ=10－5信源序列长度需长达4130万以上，才能实现给定的要求，这在实际中很难实现。一般来说，当L有限时，高传输效率的等长码往往要引入一定的失真和错误，它不能像变长码那样可以实现无失真编码。752222221013.