《信源编码》PPT课件

第5章信源编码,5.1编码的定义,5.2无失真信源编码,5.3限失真信源编码定理,5.4常用信源编码方法简介,编码,通信的实质是传输信息，通信系统的性能指标主,要有有效性、可靠性、安全性等，这些指标正是信息,论研究的对象。编码的目的是为了优化通信系统，就,是使这些指标达到最佳。,按不同的编码目的，编码分为三类：,信源编码,信道编码,安全编码/密码,信源编码,信源编码是以提高通信的有效性为目的编码。,通常通过压缩信源的冗余度来实现。,采用的一般方法是压缩每个信源符号的平均比特,数或信源的码率。同样多的信息用较少的码率来,传送，使单位时间内传送的平均信息量增加，从,而提高通信的有效性。,在不失真或允许失真的条件下，用,尽可能少的符号传送信源信息。,信道编码：,是以提高信息传输的可靠性为目的的编码。,通常通过增加信源的冗余度来实现。采用的,一般方法是增大码率/带宽。,在信道受干扰的情况下增加信号的抗干,扰能力，同时又使得信息传输率最大。,密码：,是以提高通信系统的安全性为目的的编码。,通常通过加密和解密来实现。,无失真编码,无失真信源编码定理,信源编码,限失真编码,限失真信源编码定理,无失真(冗余度压缩编码)：仅对信源的冗余度进行,压缩，不改变信源的熵。无失真编码是可逆的，即当,信源符号变换成代码后，可从代码无失真地恢复出原,信源符号。只适用于离散信源。,限失真(熵压缩编码)：在失真受限的情况下进行限,失真编码。在连续信源的情况下，由于信源的信息量,趋于无限，显然不能用离散符号序列来完成无失真编,码，而只能进行限失真编码。,离散信源,无失真信源编码定理称为第一极限定理,离散和连续信道,信道编码定理称为第二极限定理,限失真信源编码定理称为第三极限定理,连续信源,信源编码的主要任务,符号变换：使信源输出符号与信道输入符号匹配。,减少冗余，提高编码效率。,针对信源输出符号序列的统计特性，寻找一定的方,法把信源输出符号序列变换为最短的码字序列。,信源编码的基本途径,使序列中的各个符号尽可能地互相独立，即解,除相关性，去冗余；,使编码中各个符号出现的概率尽可能地相等，,即概率均匀化。,本章讨论离散信源编码。首先从无失真编码定理,出发，重点讨论以香农码、费诺码和霍夫曼码为,代表的最佳无失真码。,5.1编码的定义,信源编码：信源输出符号经信源编码器编码后,转换成另外的压缩符号,无失真信源编码：可精确无失真地复制信源输,出的消息,编码器的作用,将信源符号集X中的符号变换成由码,符号集y中的码元组成的长度为Ki的一,一对应的码字。,码字集合叫做代码组Y；码字所含码元的个数称,为该码字的码长，记为Ki。,分组码,将信源消息分成若干组，即符号序列，每个符号,序列依照固定码表映射成一个码字，这样的码称,为分组码，有时也叫块码。只有分组码才有对应,的码表，而非分组码中则不存在码表。,例：,若将信源X通过二元信道传输，就必须把信源符,号ai变换成由0、1符号组成的码符号序列，这个,过程就是信源编码。,定长码,固定长度的码，码中所,有码字的长度都相同。,变长码,可变长度码，码中的码字长短不一。,定长码变长码,若0、01都是码字，译码时如何分离？,分组码/块码将信源符号集中的每个符号映射成一个固,定的码字。分组码必须具有某些属性，才能保证在接,收端能够迅速可靠地译码。,码的不同属性,码表,信源符号,信源,出现概率p(ai),符号ai,码1,码2,码3,码4,a1,1/2,0,0,1,1,a2,1/4,11,10,10,01,a3,1/8,00,00,100,001,a4,1/8,11,01,1000,0001,奇异码,奇异码和非奇异码,1,若信源符号和码字是一一对应的，则该码为非奇异,码。反之为奇异码。,唯一可译码,2,任意有限长的码元序列，只能,被唯一地分割成一个个码字。,例：0,10,11是一种唯一可译码。,任意一串有限长码序列，如100111000，只能被分割,成10、0、11、10、0、0。任何其他分割法都会产生,一些非定义的码字。,奇异码不是唯一可译码,非唯一可译码,码2，可译成a1a1或a3,非奇异码,唯一可译码,码3，但译码有延时,非即时码,唯一可译码,即时码,非即时码,接收端收到一个完整的码字后，不能立即译码，还需,等下一个码字开始接收后才能判断是否可以译码。码3,即时码(非延长码)(异前缀码),在译码时无需参考后续的码符号就能立即作出判断，,译成对应的信源符号。,码4,任意一个码字都不是其它码字的前缀部分,码1,码2,码3,码4,ai,a1,0,0,1,1,a2,11,10,10,01,a3,00,00,100,001,a4,11,01,1000,0001,即时码,奇异码,非唯一可译码,非即时码,用码树来构造码字,码树从树根开始向下长出m个树枝，成为m进制,码树，树枝代表码元，树枝与树枝的交点叫做节点。,经过r个树枝才能到达的节点称为r阶节点。向下不长,出树枝的节点称为终端节点或端点。m进制码树各节,点(包括树根)向下长出的树枝不会超过m，若等于m称,为满树(整树)，否则称为非满树(非整树)。,码树上任一节点都对应一个码字，组成该码字的,码元就是从树根开始到该节点所经过的树枝(码元)。,若一个码所有码字均处于终端节点，则该码为即时码。,满树等长码,节数码长,非满树变长码,树码：若有n个信源符号，那么在码树上就要选择n,个终端节点，用相应的m元基本符号表示这些码字。,任一即时码都可用树图法来表示。,当码字长度给定，即时码不是唯一的。,该码树从根到终端节点所经路径上，,每一个中间节点皆为码字，因此码3,不是即时码，但它是唯一可译码。,唯一可译码存在的充分和必要条件,各码字的长度Ki应符合克劳夫特(Kraft)不等式：,m：码元进制数,n：信源符号数,Ki：各个码字的长度,例：设二进制码树中X(a1,a2,a3,a4)，,K1=1，K2=2，K3=2，K4=3。,应用Kraft不等式，得：,不存在满足这种Ki的唯一可译码,要形成满足上述长度的码字，必须在中间节点放置码字。,中间节点,如果将各码字长度改成：,存在唯一可译码,K1=1，K2=2，K3=2，K4=3。,K1=1,K2=2,K3=3,K4=3。,注意,Kraft不等式只是用来说明唯一可译码是,否存在，并不能作为唯一可译码的判据。,如码字0，10，010，111虽然满足Kraft不等式，,但它不是唯一可译码。,K1=1,K2=2,K3=3,K4=3。,5.2无失真信源编码,要求能够无失真或无差错地译码，同时希望所,得编码的平均码长最小。,对信源的L长符号序列进行m进制编码，码长KL,只要可用的码字数不少于扩展信源的符号数：,就可做到唯一译码,编码输出码,字的个数,KL/L是平均每个信源符号所需要的码元符号个数,编码后平均每个信源符号能载荷的最大信息量为：,5.2.1定长编码定理,在定长编码中，K=KL是定值，且为唯一可译码。,编码的目的是寻找最小K值,若对信源进行定长编码，必须满足:,对于定长唯一可译码，每个信源符号至少需用,（logn/logm）个码符号来变换。,例:英文电报符号，n=27，L=1，m=2(二元编码),log2n,K,=log2275,每个英文电报符号至少,log2m,要用5位二元符号编码,实际英文电报符号信源，平均每个英文电报符号所,提供的信息量约等于1.4比特，大大小于5比特。,定长编码后每个码字(5个二元符号)只携带约1.4比特,信息量。定长编码的信息传输效率极低,当考虑信源符号出现的概率及符号间的依赖关系后,（考虑信源的冗余度），在定长编码中每个信源符,号平均所需的码长可以减少。,定长编码定理给出了信源进行定长编码所需码,长的理论极限值。,定长编码定理,编码器的平均输出信息率,对于二进制编码，每个信源符号必须,输出的码长,定长编码定理说明：,只要码字所能携带的信息量大于信源序列输出的,信息量，则可以使传输几乎无失真，当然条件是,L足够大。,当时，不可能构成无失真的编码，也,就是不可能做一种编码器，能使收端译码时差,错概率趋于零。,当时，则为临界状态，可能无失真，,也可能有失真。,差错概率,设差错概率用Pe表示，则有：,为一正数,为信源序列的自信息方差,当均为定值时，只要L足够大，Pe可以小,于任一正数。即：,当信源序列长度L满足,能达到差错率要求：,编码效率,编码效率总,定义编码效率为：,是小于1,信源的平均符号熵为HL(X)，采用平均符号码长,为K来编码后所得的效率。,最佳编码效率：,编码定理从理论上阐明了编码效率接近1的理想编码,器的存在性，它使输出符号的信息率与信源熵之比接,近于1，即：,若要实现，取无限长L的,信源符号进行统一编码。,例：设离散无记忆信源概率空间为,信源熵：H(X)=-p(xi)logp(xi)=2.55bit/符号,i=1,对信源符号采用定长二元编码,要求编码效率为90,若取L1，则,即每个符号用2.83bit进行定长编码，共有22.83=7.11种,可能，按7种可能性计算，信源符号中就有一种符号,没有对应的码字，取概率最小的a8，则Pe=0.04,太大,信源序列的自信息方差：,若要求译码错误概率10-6,L应满足：,对于定长编码，即使在编码效率和译码错误概率的要,求并不十分苛刻的情况下，就需要108个信源符号一,起进行编码。这显然是很难实现的。,5.2.2变长编码定理,在变长编码中，码长KL是变化的。,根据信源各个符号的统计特性，如概率大的符号用,短码，概率小的用较长的码，使得编码后平均码长,降低，从而提高编码效率。（统计匹配）,编码后码字Y1,Y2,Yn码长分别为K1,K2,Kn,码的平均长度为：,编码后的信息传输率为：,对于某一信源和某一码符号集，若有一个唯一可译,码，其平均长度小于所有其他唯一可译码的平均长,度，则称该码为最佳码（紧致码）。,单个符号变长编码定理,若离散无记忆信源的符号熵为H(X)，每个信源符号,用m进制码元进行变长编码，一定存在一种无失真,编码方法，其码字平均长度K满足下列不等式：,H(X),H(X),K,+1,logm,logm,离散平稳无记忆序列变长编码定理,对于平均符号熵为HL(X)的离散平稳无记忆信,源，必存在一种无失真编码方法，使平均信息率R,满足不等式：,其中为任意小正数。,无失真变长信源编码定理（香农第一定理）,对于平均符号熵为HL(X)的离散平稳无记忆信源（离散,无记忆信源X的L次扩展信源,对其进行m元编码，必存在一种无失真编码方法，构,成唯一可译码，使信源X中每个信源符号所需的平均码,长满足：,用变长编码可达到相当高的编码效率，一般所要求,的符号长度L可以比定长编码小得多。,编码效率的下界,为了衡量各种编码方法与最佳码的差距，定义码的,剩余度为：,同前例：,设离散无记忆信源概率空间为,信源熵：H(X)=2.55bit/符号,要求编码效率为90,用二进制变长编码，m2,例：设离散无记忆信源概率空间为,信源熵：H(X)=1/4log4+3/4log3/4=0.811bit/信源符号,若用二元定长编码(0,1)来构造一个即时码：,平均码长：二元码符号/信源符号,编码效率：,输出的信息传输率：,再对长度L为2的信源序列进行,变长编码，其即时码如表：,码字平均长度：,单个符号的平均码长,编码效率,输出的信息传输率：R20.961bit/二元码符号,信源序列的长度增加:,编码复杂一些，但信息传输率有了提高,变长编码：L2，2=0.961,定长编码：,要求编码效率达到96时，允许译码错误概率105,说明,(1)定长码需要的信源序列长，使码表很大，且总存,在译码差错。而用变长码编码时，L不需要很大就可,达到相当高的编码效率，而且可实现无失真编码。,(2)随着信源序列长度的增加，编码的效率越来越接,近于1。编码后的传输率R也越来越接近于无噪无损,二元对称信道的信道容量(1bit/二元码符号)，达到信,源与信道的匹配。,最佳变长编码,5.2.3,凡是能载荷一定的信息量，且码字的平均长度最,短，可分离的变长码的码字集合称为最佳变长码。,编码主要方法有：香农编码、费诺编码、哈夫曼,编码等。,仅哈夫曼编码是真正意义下的最佳编码,哈夫曼编码效率最高，费诺编码效率次之，香农,编码效率最低，甚至低于定长编码的效率。因此，香,农编码的实用价值不大，但却有深远的理论意义，因,为按香农的方法对信源序列编码，当序列长度趋于无,穷时，平均码长会趋于信源的熵。,香农（Shannon）编码方法,1,香农第一定理指出了平均码长与信源之间的关系，同,时也指出了可以通过编码使平均码长达到极限值。,香农第一定理指出，选择每个码字的长度Ki满足下,式，就可以得到香农码：,二进制香农码的编码步骤,按信源符号的概率从大到小的顺序排队，不妨设：,1,确定满足下列不等式的整数码长Ki：,2,令p(a0)=0，计算第i个消息的累加概率Pi：,3,将累加概率Pi变换成二进制数，并取小数点后Ki位,4,作为符号ai的编码。,例：有一单符号离散无记忆信源,对该信源编二,进制香农码。,香农码的平均码长,信源熵,编码效率,为提高编码效率，可把x4x5换成前面的节,点，可减小平均码长。,不应先规定码长，而是由码树来规定码,字，可得更好的结果。,例：设信源共7个符号消息，其概率如表所示：,费诺（Fano）编码方法,概率匹配,2,按信源符号的概率从大到小的顺序排队，不妨设：,p(a1)p(a2)p(an),按编码进制数将概率分组，使每组概率尽可能接,近或相等。如编二进制码就分成两组，编m进制,码就分成m组。,给每一组分配一位码元。,将每一分组再按同样原则划分，重复步骤2和3，,直至概率不再可分为止。,信源符号对应的码字即为费诺码。,例：对前例信源进行二进制费诺编码。,费诺编码的基本特点:,1)费诺编码在构造码树时，是从树根开始到终端节,点结束；,2)由于赋码元时的任意性，因此编出的码字不唯一；,3)费诺编码虽属于概率匹配范畴，但并未严格遵守,匹配规则，有时出现概率小的码长反而小。因此,平均码长一般不会最小。,费诺码比较适合于每次分组概率都很接近的信源，特,别是对每次分组概率都相等的信源进行编码时，可达,到理想的编码效率。,例：,对该信源进行二,进制费诺编码。,平均码长：,编码效率：,例：,二进制费诺编码,信源符号,概率,编码,码字,码长,x1,0.25,0,0,00,2,x2,0.25,1,01,2,x3,0.125,0,100,3,0,x4,0.125,1,101,3,x5,0.0625,0,1100,4,1,0,x6,0.0625,1,1101,4,1,x7,0.0625,0,1110,4,1,x8,0.0625,1,1111,4,平均码长,K=2.75码元/符号,每次所分两组的,信源熵,H(X)=2.75bit/符号,概率恰好相等。,H(X),编码效率=,=1,Klog2,树图：,哈夫曼（Huffman）编码方法,3,将信源符号按概率由大到小顺序排队,1,给两个概率最小的符号各分配一个码元，将其概率,2,相加后合并作为一个新的符号，与剩下的符号一,起，再重新排队,给缩减信源中概率最小的两个符号各分配一个码元,3,4重复步骤2、3直至概率和为1,从最后一级开始，向前返回得到各个信源符号所对,5,应的码元序列，即相应的码字。,例：,试对该信源编二进制哈夫曼码。,读取码字的时候，要从后向前读，此,时编出来的码字是可分离的即时码。,平均码长,信源熵,H(X)=H(0.2,0.19,0.18,0.17,0.15,0.1,0.01)=2.61bit/符号,编码效率,哈夫曼编码的基本特点,1)哈夫曼编码在构造码树时，是从端点开始直到树,根结束；,2)哈夫曼编码采用概率匹配方法来决定各码字长度，,概率大的符号对应于短码，概率小的符号对应与长,码，充分利用了短码，从而使平均码长最小；,3)哈夫曼编码时，缩减信源的最后二个码字总是最,后一位不同，从而保证了哈夫曼码是即时码。,费诺码是从树根开始，把各节点分给某子集，若子,集已是单点集，它就是一片树叶而作为码字。,哈夫曼编码是先给每一符号一片树叶，逐步合并成,节点直到树根。,哈夫曼的编法并不惟一。,说明,每次对概率最小的符号分配“0”和“1”码元是任意,的，所以可得到不同的码字。只要在各次缩减信源,中保持码元分配的一致性，即能得到可分离码字。,不同的码元分配，得到的具体码字不同，但码长Ki,不变，平均码长也不变，所以没有本质区别。,缩减信源时，若合并后的新符号概率与其他符号概,率相等，从编码方法上来说，这几个符号的次序可,任意排列，编出的码都是正确的，但得到的码字不,相同，不同的编法得到的码字长度Ki也不尽相同。,在哈夫曼编码过程中，对缩减信源符号按概率由大,到小的顺序重新排列时，应使合并后的新符号尽可,能排在靠前的位置，这样可使合并后的新符号重复,编码次数减少，使短码得到充分利用。,m进制哈夫曼编码,在编m进制哈夫曼码时，为了使短码得到充分利用，,使平均码长最短，必须使最后一步的缩减信源有m个,信源符号。,缩减次数,每次缩减所减少,的信源符号个数,信源符号数n应满足：,不满足时：设q个概率为0的信源符号，使q+n满足要求,第一次对最小概率符号分配码元时只取(m-q)个，分别,配以0,1,m-q-1，把这些符号的概率相加作为一个新,符号的概率，与其它符号一起重新排列。以后每次取,m个符号，分别配以0,1,m-1；如此下去，直至所有,概率相加得1为止，即得到各符号的m进制码字。,单符号离散无记忆信源，,例,试对该信源编三进制哈夫曼码。,m=3，n=8,无法满足n=s(m-1)+m,s=3，q=1,q+n=s(m-1)+m,第一次取m-q=2个符号进行编码,平均码长,信息传输率,编码效率,香农码、费诺码、哈夫曼码都考虑了信源的统计特,性，使经常出现的信源符号对应较短的码字，使平,均码长缩短，从而实现了对信源的压缩；,香农码有系统的、惟一的编码方法，费诺码和哈夫,曼码的编码方法都不惟一；,费诺码比较适合于对