06-信源编码概述

2020/2/121/17电信学院朱山第五章信源编码的概述2020/2/122/17电信学院朱山本章节教学内容、基本要求、重点与难点1.教学内容：信源编码的概念。无失真信源编码定理。2.教学基本要求：了解信源编码的概念。掌握等长编码定理和变长编码定理。3.重点与难点：等长编码定理。变长编码定理。2020/2/123/17电信学院朱山为什么要进行信源编码信源的两个重要问题信源输出的信息量计算问题；如何更有效地表示信源输出的问题。为什么要进行信源编码无失真传送，首先要对信源无差错编码；对离散平稳信源，理论上只要有传送H∞的手段，就能把信源包含的信息全部发送出去。但实际上确定H∞非常困难，只好用实际信源熵Hm来近似。而HmH∞，所以在传输手段上必然存在冗余，即造成一定的浪费，这种浪费是由信源符号的相关性引起的。信源编码正是通过减少或消除信源的冗余度来提高通信效率。2020/2/124/17电信学院朱山研究信源编码时，将信道编码和译码看成是信道的一部分，而突出信源编码；研究信道编码时，将信源编码和译码看成是信源和信宿的一部分，而突出信道编码。2020/2/125/17电信学院朱山信源编码的概念信源编码定义：指定能够满足信道特性/适合于信道传输的符号序列/码序列，来代表信源输出的消息。完成编码功能的器件称为编码器。离散信源输出的码序列离散信源输出的消息是由一个个离散符号组成的随机序列X=(X1X2…Xl…XL)Xl∈{x1,x2,…,xi,…xn}信源编码就是把信源输出的随机符号序列变成码序列Y=(Y1Y2…Yk…YK)Yk∈{y1,y2,…,yj,…ym}2020/2/126/17电信学院朱山讨论无失真信源编码可以先不考虑抗干扰问题，所以它的数学模型比较简单，如图。P(yj/xi)无失真信源编码器X{X1,X2,…,XL}Y{Y1,Y2,…,Yki}{y1,y2,…,ym}(Yk是由ki个yj组成的序列)2020/2/127/17电信学院朱山编码器功能：将信源符号集内的符号（或者长为L的信源符号序列）变换成由Yj(j=1,2,…,m)组成的长度为ki的序列。码符号/码元：编码器的输入是信源符号{X1,X2,…,Xi,…Xn}，输出符号{Y1,Y2,…,Yj,…Ym}，一般元素Yj是适合信道传输的,称为码符号/码元。码字：码符号序列Y=(Y1Y2…Yk…Yki)称为码字。码长/码字长度：ki称为码字长度或简称码长。编码就是从信源符号到码符号的一种映射。若要实现无失真编码，这种映射必须是一一对应的，可逆的。见P132例5.1.12020/2/128/17电信学院朱山一些码的定义二元码：符号集为X={0,1}，所得码字Y都是一些二元序列。定长码/等长码：一组码中所有码字的码长都相同，即ki=K(i=1,2,…,n)。变长码：一组码字中至少有两个码字的码长不相同。非奇异码：一组码字中所有码字都不相同，即所有信源符号影射到不同的码符号序列。奇异码：一组码中有相同的码字。惟一可译码：码的任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号。2020/2/129/17电信学院朱山有时消息太多，不可能或者没必要给每个消息都分配一个码字；给多少消息分配码字可以做到几乎无失真译码？传送码字需要一定的信息率，码字越多，所需的信息率越大。编多少码字的问题可以转化为对信息率大小要求的问题；信息率R的定义：平均传输一个信源符号所需要的码字的最大信息量的大小。R=(Klog2m)/L(重要！)信息率越小越好，最小能小到多少才能做到无失真译码呢？这些问题就是信源编码定理要研究的问题。码字与信息率的关系2020/2/1210/17电信学院朱山信源编码的方法信源编码有定长和变长两种方法。定长编码：码字长度K是固定的，相应的编码定理称为定长信源编码定理，是寻求最小K值的编码方法。变长编码：K是变值，相应的编码定理称为变长编码定理。这里的K值最小意味着数学期望最小。2020/2/1211/17电信学院朱山定长编码定理定长编码定理：一个熵为H(X)的离散无记忆信源X1X2…Xl…XL，若对信源长为L的符号序列进行定长编码，设码字是从m个信源符号集内，选取K个码元组成Y1Y2…Yk…YK。对于任意ε0，δ0只要满足(K/L)log2m≥H(X)+ε则当L足够大时，必可使译码差错小于δ，即译码错误概率能为任意小。反之，若(K/L)log2m≤H(X)-2ε则不可能实现无失真编码，而当L足够大时，译码错误概率近似等于1。因为(K/L)log2m=R就是信息率，因此可以理解为只要R≥H(X)则可以实现无失真编码。反之亦然。2020/2/1212/17电信学院朱山定理中的公式改写成Klog2mLH(X)不等式左边表示长为K的码符号序列能载荷的最大信息量，右边代表长为L的信源序列携带的信息量。所以定长编码定理告诉我们：只要码字传输的信息量大于信源携带的信息量，总可实现几乎无失真编码。信源熵H(X)是一个界限/临界值。当编码器输出的信息率R超过这个临界值时，就能无失真译码，否则就不行。信源编码定理从理论上说明了编码效率接近于1，即的理想编码器的存在性，代价是在实际编码时取无限长的信源符号(L→∞)进行统一编码。12log)(mXHLK2020/2/1213/17电信学院朱山变长编码：不等长编码允许把等长的消息变换成不等长的码序列。通常把经常出现的消息编成短码，不常出现的消息编成长码。这样可使平均码长最短，从而提高通信效率，代价是增加了编译码设备的复杂度。例如，在不等长码字组成的序列中要正确识别每个长度不同的码字的起点就比等长码复杂得多。译码延时/译码同步：接收到一个不等长码序列后，有时不能马上断定码字是否真正结束，因而不能立即译出该码，要等到后面的符号收到后才能正确译出。变长编码定理2020/2/1214/17电信学院朱山码树图P132m元码树图树根：树枝：一级节点：n级节点：终节点：中间节点：联枝：串联的树枝。满树：每一个码字的串联枝数都相同，满树构造的就是定长码。例如：码长为K的满树的终节点个数为mK，即可表示mK个码字。非满树：有些树枝未用时的码树。非满树构造的就是变长码。2020/2/1215/17电信学院朱山变长编码定理平均码长：变长编码定理：若单符号离散无记忆信源的平均符号熵为H(X)，对信源符号进行m元变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式KmXHmXHK22log)(log)(1niiikxpK1)(2020/2/1216/17电信学院朱山多符号情况对于平稳无记忆信源来说，当信源输出的是长度为L的消息序列时，定理中式子可改进为这时的代表平均码序列长度。信息率R定义：编码后平均每个信源符号能载荷的最大信息量mXLHmXLHK22log)(log)(1LmLmLKLXHRXHmR22loglog2)()(log足够大时，可使当故有K2020/2/1217/17电信学院朱山对信源进行变长编码一般所要求的信源符号长度L比定长编码小的多。例:设单符号信源模型为其信息熵为H(X)=2.55(比特/符号),这里m=2，log2m=1要求η90%，则与定长编码相比，对同一信源，要求编码效率都达到90%时，变长编码只需L=4进行编码，即L不需要很大就可以达到相当高的编码效率而且可实现无失真编码。04.005.006.007.010.010.018.04.0)(87654321xxxxxxxxXPX49.028.0155.255.21LLLmXHXHRXHXHRXH2log)()()()()(的下界得编码效率由