信息论与编码民大05-最佳信源编码.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二层,第三层,第四层,第五层,*,*,/34,最佳,信源编码,5/24/2026,1,引言,香农编码定理虽然指出了理想编码器的存在性,但是并没有给出实用码的结构及构造方法；,编码理论正是为了解决这一问题而发展起来的科学理论；,编码的目的是为了,优化通信系统,，使通信系统的性能指标,有效性,、,可靠性,、,安全性,和,经济性,达到最佳；,按不同的编码目的，编码分为三类：,信源编码,、,信道编码,和,安全编码,（,加密编码）,。,5/24/2026,2,信源编码：,提高通信有效性,。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的传输率（码率）。即同样多的信息用较少的信息率来传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。,信道编码：,提高信息传输的可靠性,。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率,/,带宽。与信源编码正好相反。,加密编码：,提高通信系统的安全性,。通常通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。,5/24/2026,3,信源编码定理：对于给定的失真率,D,，,总可以找到一种信源编码方法，只要信源速率,R,大于,R(D),，,就可以在平均失真任意接近,D,的条件下实现波形重建。,说明1：,R(D),称为率失真函数，它是单调非增函数，速率越高，平均失真越小。,说明,2,：为了保证在一定速率下的失真，必需采用信源编码，因而会引入编码延时。,信道编码定理：如果信源速率,R,小于信道容量,C,，,总可以找到一种信道编码方法，使得信源信息可以,在有噪声信道上进行无差错传输，即：,R,C,，,无差错传输条件,说明1：信道容量,C,可,根据香农定理得到,C,W,log,2,(1+S/N),说明,2,：为了保证无差错传输，必需采用信道编码，因而会引入编码延时。,编码理论,5/24/2026,4,信息传输定理：,将信源编码定理和信道编码定理综合，就得到信息传输定理。,即：为保证无差错传输及失真度,的要求,，必需满足：,C,R,R(D),说明1：,在一般数字通信系统中，信源编码和信道编码可以分开考虑。信道编码定理给出无差错的速率上限，信源编码定理给出无失真或限失真的速率下限。,说明,2,：为了实现理想性能，都要付出延时的代价。,5/24/2026,5,速率：高速率、中速率、低速率,压缩比,质量：客观评价,主观评价,延时：质量和延时的关系,不同业务对延时的要求,复杂性：算法的复杂性及软硬件实现的复杂性,信源编码的性能指标,5/24/2026,6,波形编码：将波形直接变换成数字码流。,特点：比特率较高、解码后质量较高、延时较小。可以分为：时域波形编码，如,PCM,、,ADPCM,、,M,等；频域波形编码，如：子带编码,(SBC),、,自适应变换编码,(ATC),等。,参数编码：从信源信号的某个域中提取特征参数，并变换成数字码流。,特点：比特率较低、解码后质量较低、延时较大。如：各种声码器。,混合编码：,将以上二种方法混合，,特点：以较低的比特率获得较高的质量，延时适中，复杂。如：,GSM,的语音编码，,IS-95,的语音编码等。,信源编码的实现方法,5/24/2026,7,香农编码,设离散无记忆信源,二进制香农码的编码步骤如下,(4,步,),：,将信源符号按概率从大到小的顺序排列,p,(,x,1,),p,(,x,2,),p,(,x,n,),令,p,(,x,0,)=0,，用,p,a,(,x,j,),，,j,=,i,+1,表示第,i,个码字的累加概率,确定满足下列不等式的整数,k,i,，,并令,k,i,为第,i,个码字的长度,log,2,p,(,x,n,),k,i,1,log,2,p,(,x,n,),将,p,a,(,x,j,),用二进制表示，并取小数点后,k,i,位作为符号,x,i,的编码。,5/24/2026,8,例,有一单符号离散无记忆信源,对该信源编二进制香农码。其编码过程如表所示。,5/24/2026,9,香农码的平均码长,若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用,3,个比特表示。相比较，香农编码对信源的等长编码而言有,0.3,比特,/,符号的压缩。,由离散无记忆信源熵定义，可计算出：,对上述信源采用香农编码的信息率为,编码效率为信源熵和信息率之比。则,可以看出，编码效率并不是很高。,5/24/2026,10,费诺编码,费诺编码也是一种常见的信源编码方法。编码步骤如下：,将概率按从大到小的顺序排列，令,p,(,x,1,),p,(,x,2,),p,(,x,n,),按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编,m,进制码就分成,m,组。,给每一组分配一位码元。,将每一分组再按同样原则划分，重复步骤,2,和,3,，直至概率不再可分为止,。,5/24/2026,11,例,与,香农编码,一样的单符号离散信源,对该信源编二进制费诺码。编码过程如表。,5/24/2026,12,上述码字还可用码树来表示，如图所示。,5/24/2026,13,该信源的熵为,平均码长为,编码效率为,费诺编码有较高的编码效率。费诺码比较适合于,每次分组概率都很接近,的信源。特别是对每次,分组概率都相等,的信源进行编码时，可达到理想的编码效率。,5/24/2026,14,例,有一单符号离散无记忆信源,对该信源编二进制费诺码，编码过程如表。,5/24/2026,15,码树图如图,信源熵为,H,(,X,)=2.75(,比特,/,符号,),平均码长为,信息率,编码效率为,=100%,。,因为每次所分两组的概率恰好相等。,5/24/2026,16,5.4.1,编码步骤,哈夫曼,(,Huffman,),编码是一种效率比较高的变长无失真信源编码方法。,将信源符号按概率从大到小的顺序排列，令,p,(,x,1,),p,(,x,2,),p,(,x,n,),给两个概率最小的信源符号,p,(,x,n,-1,),和,p,(,x,n,),各分配一个码位“,0”,和“,1”,，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含,(,n,1),个信源符号的新信源。称为,信源的第一次缩减信源,，用,S,1,表示。,将缩减信源,S,1,的符号仍按概率从大到小顺序排列，重复步骤,2,，得到只含,(,n,2),个符号的缩减信源,S,2,。,重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为,1,。然后从最后一级缩减信源开始，依编码路径,向前返回,，就得到各信源符号所对应的码字。,哈夫曼编码,5/24/2026,17,例,设单符号离散无记忆信源如下，要求对信源编二进制哈夫曼码。,5/24/2026,18,将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树，如图所示。,5/24/2026,19,信源熵为,平均码长为,编码效率为,若采用定长编码，码长,K=3,，,则编码效率,可见哈夫曼的编码效率提高了,12.7%,。,5/24/2026,20,注意,：哈夫曼的编码并不惟一。,每次对缩减信源两个概率最小的符号分配“,0”,和“,1”,码元是任意的，所以可得到不同的码字。只要,在各次缩减信源中保持码元分配的一致性,，即能得到可分离码字。,不同的码元分配，得到的具体码字不同，但码长,k,i,不变，平均码长,也不变，所以没有本质区别；,缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，,这几个符号的次序可任意排列，编出的码都是正确的，但得到的,码字不相同,。,不同的编法得到的,码字长度,k,i,也不尽相同,。,5/24/2026,21,举例说明上述问题,例,:,单符号离散无记忆信源,方法一,：合并后的新符号排在其它相同概率符号的后面。,5/24/2026,22,5/24/2026,23,方法二,：合并后的新符号排在其它相同概率符号的前面。,5/24/2026,24,5/24/2026,25,单符号信源编二进制哈夫曼码，编码效率主要决定于信源熵和平均码长之比。对相同的信源编码，其熵是一样的，采用不同的编法，得到的平均码长可能不同。平均码长越短，编码效率就越高。,编法一的平均码长为,编法二的平均码长为,可见 ，本例两种编法的平均码长相同，所以编码效率相同。,5/24/2026,26,讨论：哪种方法更好？,定义码字长度的方差,2,：,长度,k,i,与平均码长 之差的平方的数学期望，即,编法一码字长度方差：,编法二码字长度方差：,可见：编法二的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。,编法一,的,5,个码字有,4,种不同的码长；而,编法二,的码字只有,2,种不同的码长；显然，,编法二的方法更简单、更容易实现，所以更好,。,结论,：,在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应,使合并后的新符号尽可能排在靠前的位置,，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。,5/24/2026,27,“全树”概念,定义：码树图中每个中间节点后续的枝数为,m,时称为,全树,；若有些节点的后续枝数不足,m,，,就称为,非全树,。,二进制码不存在非全树的情况，因为后续枝数是一时，这个枝就可以去掉使码字长度缩短。,对,m,进制编码：若所有码字构成全树，可分离的码字数（信源个数）必为,m,+,k,(,m,1),。,k,为正整数。,若信源所含的符号数,n,不能构成,m,进制全树，必须增加,s,个不用的码字形成全树。显然,s,m,1,，若,s,=,m,1,，,意味着某个中间节点之后只有一个分枝，为了节约码长，这一分枝可以省略。,m,进制哈夫曼编码,5/24/2026,28,例：对前面的单符号离散无记忆信源编三进制哈夫曼码。,这里：,m,=3,，,n,=8,令,k,=3,，,m,+,k,(,m,1)=9,，,则,s,=9,n,=9,8=1,所以第一次取,m,s,=2,个符号进行编码。,5/24/2026,29,5/24/2026,30,平均码长为,信息率为,编码效率为,可见：哈夫曼的编码效率相当高，对编码器的要求也简单得多。,5/24/2026,31,香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩；,香农码效率不是很高；,费诺码比较适合于对分组概率相等或接近的信源编码，,哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码,。,小结,5/24/2026,32,