《无失真信源编码》PPT课件.ppt

5.4.1 香农码,香农第一定理指出，可选择每个码字的长度满足关系式： 或： x 表示不小于 x 的整数。按不等式选择的码长所构成的码称香农码。香农码满足克拉夫特不等式，所以一定存在对应码字的长度的惟一可译码。,香农码满足克拉夫特不等式，所以一定存在对应码字的长度的唯一可译码。 也就是说按照这个码长用树图法就可以构造一组即时码。 一般情况下，按照香农编码方法编出来的码，其平均码长不是最短的，也即香农编码不一定是紧致码(最佳码)。,5.4.1 香农码,概率,5.4.1 香农码,例5.6:,累加概率,香农编码是一种概率匹配编码。即概率大的信源符号所编的代码短；概率小的信源符号所编的代码长，这样使平均码长最短,例5.6: 码的性能分析： 通过计算可得此信源的熵: (比特符号) 而码的平均长度: (码符号信源符号) 编码效率：,5.4.1 香农码,5.4.5 费诺码,费诺编码属于概率匹配编码，但它一般也不是最佳的编码方法，只有当信源的概率分布呈现 分布形式的条件下，才能达到最佳码的性能。,费诺码的编码步骤如下： 1）信源符号以概率递减的次序排列起来； 2）将排列好的信源符号按概率值划分成两大组，使每组的概率之和接近于相等，并对每组各赋予一个二元码符号“0”和“1”； 3）将每一大组的信源符号再分成两组，使划分后的两个组的概率之和接近于相等，再分别赋予一个二元码符号； 4）依次下去，直至每个小组只剩一个信源符号为止； 5）信源符号所对应的码字即为费诺码。,例5.9,费诺编码是一种概率匹配编码。即概率大的信源符号所编的代码短；概率小的信源符号所编的代码长，这样使平均码长最短,例5.9: 码的性能分析： 通过计算可得此信源的熵: (比特符号) 而码的平均长度: (码符号信源符号) 编码效率：,5.4.5 费诺码,费诺码具有如下的性质： 费诺码的编码方法实际上是一种构造码树的方法，所以费诺码是即时码。 费诺码考虑了信源的统计特性，使概率大的信源符号能对应码长较短的码字，从而有效地提高了编码效率。 费诺码不一定是最佳码。因为费诺码编码方法不一定能使短码得到充分利用:当信源符号较多时，若有一些符号概率分布很接近时，分两大组的组合方法就会很多。可能某种分大组的结果，会使后面小组的“概率和”相差较远，从而使平均码长增加。,5.4.2 霍夫曼码,1952年，霍夫曼（Huffman）提出了一种构造最佳码的方法，这是一种最佳的逐个符号的编码方法，一般就称作霍夫曼码。 设信源 ，其对应的概率分布为 ，则对二元霍夫曼码而言，其编码步骤如下：,1）将q个信源符号按概率递减的方式排列起来； 2）用“0”、“1”码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新的符号，从而得到只包含q-1个符号的新信源，称之为S信源的S1缩减信源； 3）将缩减信源中的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别用“0”、“1”码符号表示，这样又形成了由q-2个符号构成的缩减信源S2； 4）依次继续下去，直到缩减信源只剩下两个符号为止，将这最后两个符号分别用“0”、“1”码符号表示； 5）从最后一级缩减信源开始，向前返回，沿信源缩减方向的反方向取出所编的码元，得出各信源符号所对应的码符号序列，即为对应信源符号的码字。,5.4.2 霍夫曼码,例5.7霍夫曼码,例5.7: 码的性能分析： 通过计算可得此信源的熵: (比特符号) 而码的平均长度: (码符号信源符号) 编码效率：,5.4.2 霍夫曼码,表5.15 三种编码方法的比较,说明：霍夫曼编码方法得到的一定是紧致码。,说明：霍夫曼码是一种即时码，可用码树形式来表示。 例设有离散无记忆信源,5.4.2 霍夫曼码,5.4.2 霍夫曼码,哈夫曼编码方法得到的码并非是唯一的。造成非唯一的原因如下： 每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。 对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差,5.4.2 霍夫曼码,例设有离散无记忆信源,5.4.2 霍夫曼码,例设有离散无记忆信源,5.4.2 霍夫曼码,哈夫曼码的平均码长相等, 编码效率也相等 但是两种码的质量不完全相同， 可用码方差来表示：,可见，第二种哈夫曼编码方法得到的码方差要比第一种哈夫曼编码方法得到的码方差小许多。故第二种哈夫曼码的质量要好。,哈夫曼码是用概率匹配方法进行信源编码。它有两个明显特点： 一是哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码。因此它也属于匹配编码； 二是缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码,限失真信源编码,由实际生活经验我们知道，一般人们并不要求完全无失真地恢复消息。对人的心理视觉研究表明，人们在观察图像时主要是寻找某些比较明显的目标特征，而不是定量地分析图像中每个像素的亮度，或者至少不是对每个像素都等同地分析。例如观看一段视频或观察一幅图像，人们可能会关注其主要情节，对视频或图像中的细节并不是那么注意，此时便允许视频或图像有一定程度的失真。,由香农第一定理知，无论哪种信道，只要信息传输率R小于信道容量C，总能找到一种编码方法，使得在信道上能以任意小的错误概率，以任意接近的传输率来传送信息。 实际信道中，信源输出的信息传输率R一般都会超过信道容量，因此也就不可能实现完全无失真地传输信源的信息。 由香农第三定理知，在允许一定失真度D的情况下，信源输出的信息传输率可压缩到R(D)值，只要信息传输率R大于R(D)，一定能找到一种编码方法，使得译码后的失真小于D。香农第三定理从理论上给出了信息传输率与允许失真之间的关系，奠定了信息率失真理论的基础。信息率失真理论是进行量化、数模转换、频带压缩和数据压缩的理论基础。,5.5 实用信源编码方法,无失真和限失真信源编码定理，说明了最佳码的存在性，但没有给出具体构造码的方法，实用的编码方法需要根据信源的具体特点来决定。 霍夫曼码在实际中已得到应用，但它仍存在一些分组码所具有的缺点，例如概率特性必须精确地测定，如果信源概率特性稍有变化，就必须更换码表；对于二元信源，常需多个符号合起来编码，才能取得较好的效果，但是如果合并的符号数目不大时，编码效率提高得不多，特别是对于相关信源，霍夫曼编码不能给出令人满意的结果。因此在实用中常需作一些改进，同时也就有必要研究非分组码。 在编码理论的指导下，先后出现了许多性能优良的编码方法，本节介绍一些实用的编码方法 .,5.5.1 游程编码,游程（Run-Length，简记RL）是指符号序列中各个符号连续重复出现而形成符号串的长度，又称游程长度或游长。 游程编码（Run-Length Coding，简记RLC）就是将这种符号序列映射成游程长度和对应符号序列的位置的标志序列。如果知道了游程长度和对应符号序列的位置的标志序列，就可以完全恢复出原来的符号序列。,游程编码特别适用于对相关信源的编码。对二元相关信源，其输出序列往往会出现多个连续的“0”或连续的“1”。在信源输出的二元序列中，连续出现的“0”符号称为“0游程”，连续出现的“1”符号称为“1游程”，对应连续同一符号的个数分别称为“0”游程长度和“1游程”长度，因为游程长度是随机的，其取值可以是1，2，3，。 对二元序列，“0”游程和“1游程”总是交替出现的，如果规定二元序列是以“0”开始的，那么第一个游程是“0”游程，第二个游程必为“1”游程，第三个游程又是“0”游程等等。将任何二元序列变换成游程长度序列，这种变换是一一对应的，因此是可逆的、无失真的。 因为游程长度是随机的、多值的，所以游程序列本身是多元序列，对游程序列可以按霍夫曼编码或其他编码方法进行处理以达到压缩码率的目的。,在算术编码中，信源符号和码字间的一一对应关系并不存在，它是一种从整个符号序列出发，采用递推形式进行编码的方法 如果信源符号集为 ，信源序列 ，则总共有 种可能的序列。由于考虑的是整个符号序列，因而整页纸上的信息也许就是一个序列，所以序列长度L一般都很大。在实际中很难得到对应信源序列的概率，一般我们从已知的信源符号概率 递推得到。,5.5.2 算术编码,算术编码的基本思路是：从整个符号序列出发，将各信源序列的概率映射到0，1）区间上，使每个符号序列对应于区间内的一点，也就是一个二进制的小数。这些点把0，1）区间分成许多小段，每段的长度等于某一信源序列的概率。再在段内取一个二进制小数，其长度可与该序列的概率匹配，达到高效率编码的目的。这种方法与香农编码法有些类似，只是它们考虑的信源对象有所不同，在香农编码中考虑的是单个信源符号，而在算术码中考虑的是信源符号序列。,5.5.2 算术编码,从性能上来看，算术编码具有许多优点，它所需的参数较少、编码效率高、编译码简单，不象霍夫曼码那样需要一个很大的码表，在实际实现时，常用自适应算术编码对输入的信源序列自适应地估计其概率分布。算术编码在图像数据压缩标准（如JPEG）中得到广泛的应用。,实用限失真信源编码：预测编码,预测编码是数据压缩三大经典技术（统计编码、预测编码、变换编码）之一，它是建立在信源数据相关性之上的。由信息理论可知，对于相关性很强的信源，条件熵可远小于无条件熵，因此人们常采用尽量解除相关性的办法，使信源输出转化为独立序列，以利于进一步压缩码率。 常用的解除相关性的措施是预测和变换，其实质都是进行序列的一种映射。一般来说，预测编码有可能完全解除序列的相关性，但必需确知序列的概率特性；变换编码一般只解除矢量内部的相关性，但它可有许多可供选择的变换方法，以适应不同的信源特性。下面介绍预测编码的一般理论与方法。,实用限失真信源编码：变换编码,由前节已经看到，对于有记忆信源，由于信源前后符号之间具有较强相关性，要提高信息传输的效率首先需要解除信源符号之间的相关性，解除相关性可以在时域上进行（如前面介绍的预测编码方法），也可以在变换域上进行，这就是本节要介绍的变换编码方法。对于图像信源等相关性更强的信源，常采用基于正交变换的变换编码方法进行数据压缩。 变换编码的基本原理是将原来在空间（时间）域上描述的信号，通过一种数学变换（例如傅里叶变换等），将信号变到变换域（例如频域等）中进行描述，在变换域中，变换系数之间的相关性常常显著下降，并常有能量集中于低频或低序系数区域的特点，这样就容易实现码率的压缩，并还可大大降低数据压缩的难度。,最早将正交变换思想用于数据压缩是在20世纪60年代末期，由于快速傅里叶变换的出现，人们开始将离散傅里叶变换用于图像压缩；之后在1969年哈达玛变换用于图像压缩；1971年KL变换用于图像压缩，得到了最佳的性能，故KL变换又称为最优变换；1974年出现了综合性能较好的离散余弦变换（DCT），并很快得到广泛的应用；20世纪80年代后期，国际电信联盟(ITU)制订的图像压缩标准H.261选定DCT作为核心的压缩模块；随后国际标准化组织(ISO)制定的活动图像压缩标准MPEG-1也以DCT作为视频压缩的基本手段；更新的视频压缩国际标准中也有用到DCT。 下面我们首先介绍变换编码的基本原理，然后介绍变换编码中常用的几种变换。,近年来，由于DCT的信息集中能力和计算复杂性综合得比较好，而得到了较多的应用，DCT已被设计在单个集成块上。另外，近年来得到广泛研究和应用的一些编码方法（例如子带编码、小波变换编码、分形编码等）也直接或间接地与变换编码相关，在实际应用中，需要根据信源特性来选择变换方法以达到解除相关性、压缩码率的目的。另外还可以根据一些参数来比较各种变换方法间的性能优劣，如反映编码效率的编码增益、反映编码质量的块效应系数等。当信源的统计特性很难确知时，可用各种变换分别对信源进行变换编码，然后用实验或计算机仿真来计算这些参数，从而选择合适的编码。,总复习,第一章 绪论 信息的定义 通信系统模型,总复习,第二章 信息的度量 自信息 定义： 物理含义 单位：比特 计算（单位换算） 自信息是非负的,总复习,第二章 信息的度量 互信息 定义： 物理含义：已知事件yj后所消除的关于事件xi的不确定性 单位：比特 性质： 可正可负 互易性,总复习,第二章 信息的度量 平均自信息（信息熵、信源熵） 定义： 物理含义：对信源平均不确定性的描述 单位：比特/符号 性质： 对称性 确定性 非负性 极值性：最大离散熵定理,总复习,第二章 信息的度量 联合熵和条件熵 定义： 物理含义：H(Y|X)表示给定随机变量X后，随机变量Y仍然存在的平均不确定性 H(Y|X)：噪声熵 H(X|Y)：损失熵，信道疑义度 单位：比特/符号,总复习,第二章 信息的度量 平均互信息 定义： 物理含义：表示收到Y前后关于X的不确定度减少的量，亦即从Y获得的关于X的平均信息量 I(X;Y)：信息传输率 单位：比特/符号 性质：全部需要熟练掌握、灵活运用,总复习,第二章 信息的度量 各类熵之间的关系 要求熟练掌握，灵活运用 注意几个不等式关系,总复习,第三章 信源及信源熵 信源的分类（各类型的定义） 离散信源、连续信源、波形信源 平稳信源、非平稳信源 有记忆信源、无记忆信源 马尔科夫信源是一种离散有记忆且记忆长度有限的信源 单符号离散信源 数学模型 信息熵,总复习,第三章 信源及信源熵 离散平稳无记忆信源 数学模型：单符号信源的N次扩展 熵率： 离散平稳有记忆信源 定理3.1：平均符号熵HN(X)随N的增加是递减的,总复习,第三章 信源及信源熵 信源的相关性和剩余度 信源的剩余度定义 信源的剩余度来自哪两个方面，如何消除,总复习,第四