信源编码的基本方法课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,4.5,信源编码的基本方法,信源编码的基本方法课件,一,.,信源编码的基本方法,1.,信源编码的目的：提高传输效率,（,1,）去除信息中的冗余度，使传输的符号尽可能都是独立的，没有多余的成分,(,如语音、图像信号压缩,),；,（,2,）使传输的符号所含的信息最大化例如，通过编码使符号以等概分布的形式出现，使每个符号可能携带的信息量达到最大；,（,3,）采用不等长编码，让出现概率大的符号用较短的码元序列表示，对概率小的符号用较长的码元序列；,(4),在允许一定失真的条件下，如何实现高效率的编码一.信源编码的基本方法,2.,离散无记忆信源,(DMS:Discrete Memoryless Source,）,离散无记忆信源的输出序列：,各个,符号间彼此独立,其中,反之，若输出的各符号间,有一定的相关性,，则其为一种,有记忆的信源,有记忆的信源，经过处理后，有可能变为一种无记忆的信,源如有记忆的信源，经过理想的、完全去除冗余的,压缩编码后产生的输出2.离散无记忆信源(DMS:Discrete Memor,若将信源输出的符号按每,J,个为一组进行编码，则任意的第,m,个分组可以表示为,编码输出,其中,为输出的码元集。

接收端的,译码输出,若将信源输出的符号按每J个为一组进行编码，则任意的第,待编码码组,编码,输出码组,(,码字,),信源编码的基本方法课件,定义,4.5.1,若对信源的每个不同的符号或不同的符号序列，编,码后产生的码字不同的，则称该码为,唯一可译码,若待编码的符号序列的不同组合个数为,码字集中不同的码字个数,唯一可译码的条件,信源编码的基本方法课件,定义,4.5.2,编码表示一个信源符号所需的平均信息量的定义为,编码速率,码字长度为常数的编码称为,等长编码,，发之称为,不等长编码,等长编码,的,编码速率,不等长编码,的,编码速率,其中 为不等长编码的,平均码长信源编码的基本方法课件,定义,4.5.3,信源的熵 与编码速率 的比值定义为编码效率,要保证编码没有信息丢失，要求,信源编码的基本方法课件,3.,霍夫曼,(Huffman),编码,霍夫曼编码是一种,异字头不等长编码,，其基本思想是：,对出现概率大的符号或符号组用位数较少的码字表示；,对出现概率小的符号或符号组用位数较多的码字表示由此可提高编码效率霍夫曼编码,：,定理,4.5.17,霍夫曼编码一种,最佳的不等长编码,霍夫曼编码的,应用条件,：,信源的分布,(,统计,),特性已知。

记 信源符号集为：,编码输出符号集为：,3.霍夫曼(Huffman)编码,霍夫曼编码的步骤,：,(1),将,L,个信源符号按概率大小，以递减次序，从上到下排成一列；,(2),对处于最下面的概率最小的,D,个信源符号，一一对应地分别赋予码字元素,Z,1,、,Z,2,、,、,Z,D,，把这,D,个概率最小的信源符号相应的概率相加，所得的值用一个虚拟的符号代表，与余下的,L-D,个符号组成含有,(L-D)+1=L-(D-1),个符号的第一次缩减信源,S,(1),；,(3),对缩减信源,S,(1),仍按其概率大小以递减次序从上到下排列，按照步骤,(2),的方法处理，得到一个含有,(L-D)+1-D+1=L-2(D-1),个符号的第二次缩减信源,S,(2),；,(4),按照上述的方法，依次继续下去，每次缩减所减少的符号数是,D-1,个；只要缩减后的信源,S,i,符号的个数大于,D,，缩减就继续进行；,(5),当进行第,k,次缩减后信源,S,(k),符号个数刚好等于,D,，即有,则对最后这,D,个符号分别赋予码字元素,Z,1,、,Z,2,、,、,Z,D,；,霍夫曼编码的步骤：,霍夫曼编码的步骤：,(6),从最后赋予的码符号开始，沿着每一信源符号在各次缩减过程中得到的码字元素进行路线前向返回，达至每一信源符号，按前后次序，把返回路途中所遇到的码元素排成序列，这个序列，就是相应信源符号对应的码字；,(7),若进行,k,次缩减后，当进行第,k,次缩减后信源,S,(k),符号个数不等于,D,，即有,则中止缩减，增加 个概率为,0,的虚假信源符号,重新编码，使在,k,次编码后一定有 。

信源编码的基本方法课件,示例,：已知信源符号集,编码输出的码字符号集为,解：已知：尝试,需要增加虚假符号数为,新构建的信源满足：,示例：已知信源符号集,改造后的符号概率场为,:,编码过程如下,改造后的符号概率场为:,平均码字长度：,示例,(,续,),：,如果不加入虚假符号，直接进行编码，则有,平均码字长度,信源编码的基本方法课件,码字长度的均匀性和方差,在同样的平均码字长度的情况下，码字长度越均匀，对传输越有利定义,4.5.16,码字长度的,方差,其中,编码过程的排序过程不同会影响码长的方差信源编码的基本方法课件,码字长度的均匀性和方差,示例：信源的符号空间为,编码输出码字集,编码方式,1,将局部概率和置于相同概率的最低位置,码字长度的均匀性和方差,示例：,编码方式,1,平均码长,：,方差,：,示例：编码方式1,编码方式,2,将局部概率和置于相同概率的最高位置,平均码长,：,方差,：,编码方式2 将局部概率和置于相同概率的最高位置,可见,虽然平均码长一样，但编码方法,2,使得输出的码长更为均匀在编码过程中，当对缩减信源概率重新排列时，应使合并,得到的局部概率和，尽量使其处于最高位置；使得合并元素重,复编码的次数减少，有利于降低码字长度的方差。

4.6,率失真理论,信源编码的基本方法课件,一,.,实际系统中的权衡问题,实际系统中通常需要考虑,性能,与,经济性,之间的权衡问题；,可采用以某些不可察觉或可察觉但不影响应用的信号失真代价，来换取所需的传输速率、存储空间、运算复杂度和系统实现成本的降低；,系统采样,8kHz,采样，,8,比特量化；,数字音响系统采样,44kHz,采样，,16,或,24,比特量化；,一.实际系统中的权衡问题,1.,失真的概念,失真,是指用某种尺度衡量的理想信源样值 与,“,变换,”,后的样,值 间的差异这里所谓的,“,变换,”,，可以是某种有损的编码，或者是经传输,后受到劣化的信号失真函数,：对由符号 变为符号 产生失真造成的影响，可,根据不同的情况定义一个非负函数 来描述，该函数,就称为失真函数失真函数的取值通常反映失真产生的代价1.失真的概念,失真函数的示例：,失真函数的示例：,2.,率失真理论研究的问题,率失真理论研究的是限定失真条件下信源的编码和信息传输问题的方法分析在允许一定失真的条件下，要重构信源的符号，至少应获得多少信源的信息量；,2.率失真理论研究的问题,(1),率失真理论在通信系统中应用时的参数,输入信号集：,输出信号集：,对离散无记忆信道，有,失真函数：,其中 为输入符号；为输出符号,(1)率失真理论在通信系统中应用时的参数,(2).,平均失真度,失真函数矩阵,与转移概率矩阵对应，可定义相应的失真度矩阵：,定义,4.6.1,平均失真度定义为,平均失真度是从统计意义上来说每个符号失真的平均值。

2).平均失真度,在通信系统中，失真通常在信道中产生，平均失真度与信道的关系可由转移概率的函数来描述给定信源的统计特性,和失真函数的定义,平均失真度由信道转移概率决定,在通信系统中，失真通常在信道中产生，平均失真度与信道的关,平均失真度与信道转移概率的关系,示例,已知信源统计特性,信道转移概率矩阵,当失真测度采用汉明失真函数时，平均失真度为,平均失真度与信道转移概率的关系,(3).,率失真函数,回顾平均互信息定义,定理,4.6.2,给定信源的统计特性,平均互信息量是信道转移概率,的,型凸函数定理成立的主要依据：,对数函数 的,型凸函数特性；,概率的基本关系式：,(3).率失真函数,定义,4.6.3,给定信源统计特性,给定失真度准则,率失真函数,定义为,其中,转移概率矩阵集,定理,4.6.2,保证了率失真函数的存在定义4.6.3 给定信源统计特性,(4).,率失真函数的物理意义,：,如果将符号通过信道传输看作某种变换过程，,为了以小于,等于,D,C,的失真度恢复信源的输出，,平均每个信源符号,需,要得到的,最小信息量,若将率失真函数看作,D,的函数，显然有如下的关系,(4).率失真函数的物理意义：,当没有失真时,():,当失真达到最大时,(),：,当没有失真时():,率失真函数的定义域,参见上页图，但并非所有 的取值都有意义。

一般地,使,的最小平均失真度,率失真函数的定义域,率失真函数 的主要性质：,(1)(,定理,4.6.3),率失真函数 是,D,的,型凸函数作为,D,的函数存在最小值2)(,定理,4.6.4),率失真函数 是,D,的单调递减函数允许的失真越大，所需的互信息量越小3)(,定理,4.6.5),是,D,的连续函数率失真函数 的主要性质：,示例,：已知等概分布的信源,信源的熵为：,采用汉明失真函数,汉明失真测度的失真矩阵为：,示例：已知等概分布的信源,示例,：若转移概率矩阵为,即有,示例：若转移概率矩阵为,则平均失真度为,:,随机变量,Y,的分布为,因为转移概率矩阵的元素非,0,即,1,，因此有,则平均失真度为:,平均互信息量为,:,即若允许平均互失真度为,可只发送信源的 前面,n,个符号，后面,的,n,个符号全部用 替代此时表示单位符号所需的比特数由,平均互信息量为:,4.,汉明失真与传输差错概率,设信源符号的分布特性为,汉明失真矩阵为,4.汉明失真与传输差错概率,设信道转移矩阵为,由汉明失真矩阵，得平均失真度为,而传输出错的概率,因此有 即,失真是由传输出错所致,。