第五章信源编码.ppt

第1章 概述 第2章 信源熵 第3章 信道容量 第4章 信息率失真函数 第5章 信源编码 第6章 信道编码 第7章 密码体制的安全性测度 信源编码 信源编码是以提高通信的有效性为目的编码 通常通过压缩信源的冗余度来实现 采用的一般方法是压缩每个信源符号的平均比特数或信源的码率 同样多的信息用较少的码率来传送 使单位时间内传送的平均信息量增加 从而提高通信的有效性 信源编码的基本途径有两个 使序列中的各个符号尽可能地互相独立 即解除相关性 使编码中各个符号出现的概率尽可能地相等 即概率均匀化 信源编码的基础是信息论中的两个编码定理 无失真编码定理限失真编码定理无失真编码只适用于离散信源对于连续信源 只能在失真受限制的情况下进行限失真编码 下面介绍几种典型的离散信源编码方法 5 1离散信源编码 5 2连续信源编码 5 3相关信源编码 5 4变换编码 5 1 4赫夫曼编码 5 1 3费诺编码 5 1 5游程编码 5 1 6冗余位编码 5 1 1码字唯一可译的条件 5 1 2香农编码 如何分离码字 如果0 01都是码字 译码时如何分离 判断以下码字是否可分离 例2 4 1 对离散无记忆信源 消息长度为L 符号熵为H X 对信源进行m元变长编码 一定存在无失真的信源编码方法 5 1 4赫夫曼编码 5 1 3费诺编码 5 1 5游程编码 5 1 6冗余位编码 5 1 1码字唯一可译的条件 5 1 2香农编码 5 1 2香农编码 设有离散无记忆信源 1 2 3 4 香农编码方法的步骤 例 编码过程 1 5 1 4赫夫曼编码 5 1 3费诺编码 5 1 5游程编码 5 1 6冗余位编码 5 1 1码字唯一可译的条件 5 1 2香农编码 5 1 3费诺编码 对概率按m进行分组 使每组概率尽可能相等 给每个分组分配一个码元 对每个分组重复2 3步 直到不可分为止 1 2 3 4 例 编码过程 可以看出本例中费诺码有较高的编码效率 费诺码比较适合于每次分组概率都很接近的信源 5 1 4赫夫曼编码 5 1 3费诺编码 5 1 5游程编码 5 1 6冗余位编码 5 1 1码字唯一可译的条件 5 1 2香农编码 将信源符号按概率由大到小顺序排队 给两个概率最小的符号各分配一个码位 将其概率相加后合并作为一个新的符号 与剩下的符号一起 再重新排队 给缩减信源中概率最小的符号各分配一个码元 重复步骤2 3直至概率和为1 2 1 4 3 5 1 4赫夫曼编码 例 编码过程 说明 Huffman码的编码方法不是唯一的 首先 每次对缩减信源两个最小的符号分配 0 和 1 码元试任意的 所以可得到不同的码字 只要在各次缩减信源中保持码元分配的一致性 即能得到可分离码字 不同的码元分配 得到的具体码字不同 但码长 平均码长都不变 所以没有本质区别 其次 若合并后的新符号的概率与其他符号的概率相等 从编码的方法上来说 这几个符号的次序可任意排列 编出的码都是正确的 但得到的码字不同 不同的编法得到的码字长度也不尽相同 对信源进行缩减时 两个概率最小的符号合并后的概率与其它信源符号的概率相同时 这两者在缩减信源中进行概率排序 其位置放置次序是可以任意的 故会得到不同的哈夫曼码 此时将影响码字的长度 一般将合并的概率放在上面 这样可获得较小的码方差 如下面的例子 例设有离散无记忆信源 用两种不同的方法对其编二进制huffman码 方法一 方法二 两种不同的编码方法得到的码字和码长的对比 平均码长和编码效率 两种编码方法编出的码字的码长方差比较 可以看出第二种编码方法的码长方差要小许多 这意味着第二种编码方法的码长变化较小 比较接近平均码长 由此可以得到一个结论 怎样得到码方差较小的huffman编码 结论 进行赫夫曼编码时 为得到码方差最小的码 应使合并的信源符号位于缩减信源序列尽可能高的位置上 以减少再次合并的次数 充分利用短码 5 1 4赫夫曼编码 5 1 3费诺编码 5 1 5游程编码 5 1 6冗余位编码 5 1 1码字唯一可译的条件 5 1 2香农编码 5 1 5游程编码 前面的几种编码方法主要时针对无记忆信源 对有记忆信源 这些编码方法的效率并不高 特别是对二元相关信源 需要一些其它的方法 游程编码就是这样的方法 对相关信源的编码更有效 游程 指数字序列中连续出现相同符号的一段 在二元信源中 连续的一段 0 称为一个 0 游程 0 的个数称为此游程的长度 同样 也有 1 游程 游程序列 用交替出现的 0 游程 1 游程的长度 来表示任意二元序列而产生的一个新序列 它和二元序列是一个一一对应的变换 000101110010001 31132131 若已知二元序列以0起始 从游程序列很容易恢复成原来的二元序列游程序列是多元序列 各长度可按赫夫曼编码或其它方法处理以达到压缩码率的目的 多元序列也存在相应的游程序列多元序列变换成游程序列再进行压缩编码没有多大意义游游程编码只适用于二元序列 对于多元信源 一般不能直接利用游程编码 因为游程变换是一一对应的可逆变换 所以游程变换后 熵不变 组合编码可获得较高的编码效率 5 1 4赫夫曼编码 5 1 3费诺编码 5 1 5游程编码 5 1 6冗余位编码 5 1 1码字唯一可译的条件 5 1 2香农编码 多元信源序列 冗余位 上面二元1表示信息位 0表示冗余位 冗余位序列 游程编码 信息序列 赫夫曼编码 分帧传送冗余位序列的编码方法 N个符号为一帧 编成一个L D码字 每个码字含有两个数 Q和T Q 本帧内信息位的数目 T 信息位的位置信息 L D编码 例 001000000010000 N 15 编L D码 编码 编码位数 Q的位数 T的位数 1 00100101111 译码 T 47 适用 冗余位和信息位数目相差较大的情况 2 5 1离散信源编码 5 2连续信源编码 5 3相关信源编码 5 4变换编码 对于连续信源输出的消息 首先要在时间上进行采样 然后在取值上进行量化并进而编码 连续信源编码属于限失真编码 根据保真度准则下的信源编码定理 其编码效率受限于信息率失真函数 在符合采样定理的条件下 采样所带来的信息失真可以忽略不计 量化是用值域上有限个称为量化值中的一个来代替信号值 量化必然带来误差 如果量化后采用无失真编码 那么连续信源编码中的信息失真就都来自量化过程 5 2连续信源编码 量化有多种方法 一种是将各个采样时刻的信号值逐个进行量化 称为标量量化 另一种是将个采样时刻的信号值组成一组 将其看作一个维矢量 将这些维矢量逐个进行量化 称为矢量量化 脉冲编码调制 PCM pulsecodemodulation 是研究最早 使用最广的一种最佳标量量化编码 PCM的编码原理 5 2 1最佳标量量化 模拟信号经过采样 成为时间离散的信号序列 将各个采样时刻的信号值逐个量化 编码 得到与取值也是离散的信号量化值序列相对应的二进制编码序列 由于每个采样时刻的量化 编码过程相同 为方便 我们可去掉时标 将量化 编码的输入信号值记为 量化 编码中的信号量化值记为 量化 编码的编码输出记为 一 均匀量化 均匀量化是指在整个量化范围内的量化间隔都是相等的 均匀量化也称为线性量化 均匀量化的特性 其中 a 为中平量化 b 为中升量化 主要以有无零量化值来加以区别 a b 以中平量化为例讨论均匀量化 引入四舍五入原则的中平量化特性 由于均匀量化正反两个方向的对称性 可以将其分为极性判断和信号绝对值量化两个步骤 由于归一化信号绝对值满足 如果信号绝对值的量化数目为 取 则量化间隔 相应 当信号绝对值及时 将其量化为 当信号绝对值时 将其量化为 量化后 最常用的编码是定长折叠二进制码 其码元安排为 最高位为极性码 用以表示信号极性 当信号值时 极性码取1 时 极性码取0 次高位以下为量化码 用以表示的量化值 当的量化间隔为时 码长 在编码电路或编码程序中 一般编码过程是 1 对信号值进行极性判断 确定极性码 2 通过信号绝对值与量化码各位权值组合的逐次比较 确定量化码 3 将极性码和量化码组合起来 得到均匀量化编码 例5 2 1 已知某一采样时刻的归一化信号值 设量化间隔 求其均匀量化编码 确定码长 确定极性码 由于信号值 所以极性码 确定量化码 信号绝对值与量化码最高位权值比较 由于 所以 与量化码最高位和次高位权值之和比较 由于 所以 与量化码最高位和最低位权值之和比较 由于 所以 故量化码 将其组合 归一化信号值的均匀量化编码为 量化值与信号值之间由于四舍五入而产生的量化误差一般也称为量化噪声 量化噪声与信号值一样 也是随机变量 记为 例如 例6 2 1的量化噪声 均匀量化的量化噪声 如果我们采用平方误差失真函数 则量化噪声直接反映了信息失真的程度 根据限失真编码的要求就可以决定均匀量化的量化噪声水平 二 非均匀量化 只要在量化范围内的量化间隔不完全相等 就将其称为非均匀量化 非均匀量化也叫做非线性量化 采用压扩技术的非线性量化原理 在发送端 信号值首先通过一个电路或程序进行压缩 然后再进行均匀量化 编码 而在接收端 译码后也需通过一个电路或程序进行扩张 只要压缩和扩张特性相互补偿 压扩过程就不会引入新的信息失真 以语音信号为例 了解非线性量化的主要概念和方法 目前 在语音信号的非线性量化编码中 采用了两种压缩特性 一种称为律特性 另一种称为律特性 欧洲和中国大陆等地的数字电话通信中采用的律特性 式中 x为归一化信号值 当时函数取正 否则取负 一般取 为实现方便 大多采用13折线来逼近律特性 量化范围的13折线律特性 划分为8个不均匀的段落 其中第8段占量化范围的 除第1段外 其余各段的宽度均按倍率减小 即第7段占 第6段占 第2段占 第1段也占 每个段落再均匀地分为16份 每一份作为一个量化间隔 这样 量化范围内共划分出了个不均匀的量化间隔 如果将最小的量化间隔记为 则 相应最大的量化间隔为 13折线律非均匀量化编码也采用定长折叠二进制码 并将码长确定为8位 其8位码元安排如下 最高位为极性码 用以表示信号极性 其准则与均匀量化相同 以下三位为段落码 用以表示落在正方向的第几个段落 最后四位为段内码 用以表示在段内落在第几个量化间隔 在编码电路或编码程序中 13折线律非均匀量化编码过程是 1 对信号值进行极性判断 确定极性码 2 通过段落码起始量化值的中位搜索 确定段落码 3 信号绝对值与所确定段落起始量化值之差通过与段内码各位权值组合的逐次比较 确定段内码 4 组合起来即得到13折线律非线性量化编码 由于每个段落的宽度不同 每个段落内段内码各位的权值也不同 例5 2 2 已知某一采样时刻的归一化信号值求其13折线律非均匀量化编码 确定极性码 由于信号值 确定段落码 取第1段与第8段的中位第5段进行比较 由于 所以 取第5段与第8段的中位第7段进行比较 由于 所以 取第7段与第5段的中位第6段进行比较 由于 所以 故段落码即落在第6段 确定段内码 第6段的起始量化值为 量化间隔为 将其组合 归一化信号值的13折线律非线性量化编码为 与段内码最高位权值比较 由于 所以 与段内码次高位权值比较 由于 所以 与段内码第三位权值比较 由于 所以 与段内码第三位和最低位权值之和比较 由于 所以 故段内码 由于每个段落的量化间隔不同 13折线律非线性量化的量化噪声随着信号值落在不同段落而不同 例如 例6 2 2的量化码所代表的量化值为 相应的量化噪声 显然 信号绝对值越小 13折线律非线性量化的量化噪声也越小 当信号绝对值落在第1段或第2段时 虽然当信号绝对值落在其他段落时 量化噪声会大于 但由于语音信号小信号出现的概率远大于大信号出现的概率 所以13折线律非线性量化的量化噪声功率与码长为12的均匀量化的量化噪声功率相差并不太大 换句话说 对于语音信号而言 码长为8的13折线律非线性量化编码与码长为12的均匀量化编码的量化噪声水平基本相当 而编码效率却提高了 矢量量化是在图像 语音信号编码中研究得较多的量化编码方法 它的出现不仅仅是作为量化 更多的是作为压缩编码而提出的 在矢量量化中 将个采样时刻的信号值组成一组 将其看作一个维矢量 以这些维矢量为单位逐个进行量化编码 5 2 2矢量量化 以为例讨论矢量量化 对于时间离散的信号序列 如果将每2个采样时刻的信号值构成一个2维矢量 就形成个2维矢量 由于每个2维矢量的矢量量化过程相同 为方便 我们也去掉时标 将2维矢量记为 所有可能的2维矢量构成一个平面 矢量量化最重要的工作是将这个平面划分为块 相当于标量量化中的量化数目 记为 这些块可以是均匀的 也可以是非均匀的 相当于标量量化中均匀或非均匀的的量化间隔 一般将这些块称为胞腔 Cell 平面的划分 然后对于所划分的每一块给定一个量化矢量 相当于标量量化中的量化值 记为 通常将其取为所划分块的形心 在矢量量化中 一般将每个量化矢量称为码字或码矢 将所有个量化矢量构成的集合称为码书 因此 矢量量化中这项最重要的工作称为码书的建立 码书建立之后 矢量量化过程就成了在给定码书中搜索一个与信号矢量最接近的码字的过程 矢量量化原理 在发送端 信号矢量与码书中的每一个码字通过计算误差失真函数进行比较 搜索到失真最小的码字及其相应的序号 该码字在码书中的地址 在接收端 由于设置了一个与发送端相同的码书 故只需根据序号就可检索到与最接近的码字 当码书长度为时 传输码字序号所需的比特数为 由于矢量维数为 相当于每个信号值所对应的比特数仅为 可见其压缩比可以很高 要做到最佳矢量量化 怎样建立一个合理的码书 当码书较大时 如何快速有效地搜索到与信号矢量最接近的码字 这是矢量量化的两个关键问题 一 LBG算法 利用训练序列建立码书的LBG算法的流程是 1 给定码书长度 置 初始平均失真 给定初始码书 给定计算停止门限 2 用码书为已知形心 利用信号序列构成的维训练序列 根据最佳划分原则 划分出个胞腔 3 计算平均失真和相对失真 如 则停止计算 当前码书就是设计好的码书 否则 进行第 4 步 4 计算各胞腔的形心 置 返回第 2 步 该流程还有两个问题 第一是初始码书的选取 第二是空胞腔的处理 初始码书的选取常用的方法是随机选取法和分裂法 处理空胞腔常用的方法是去空胞腔分裂法 二 全搜索算法和树搜索算法 常用时间复杂度和空间复杂度来衡量矢量量化的特点 时间复杂度是指每量化一个信号矢量所需的计算量 它主要取决于搜索过程中乘法运算的次数 空间复杂度是指码书所需的存储容量 全搜索算法的特点是信号矢量与码书中的码字逐一进行比较 根据采用的误差失真函数找到失真最小的码字作为其量化矢量 采用全搜索算法的矢量量化也称为基本矢量量化 对于基本矢量量化而言 如其矢量维数为 码书长度为 采用平方误差失真函数 那么时间复杂度 次 信号矢量 空间复杂度 单元 采用树搜索算法的矢量量化称为树搜索矢量量化 在树搜索矢量量化的发送端 需要建立树型码书以方便进行树搜索 而在接收端 由于只需根据序号检索 可以仍然是数组型码书 以3层二叉树为例 其搜索步骤 1 信号矢量分别与第二层的中间节点通过计算误差失真函数进行比较 如 则走上子树 送0至信道 否则走下子树 送1至信道 2 如走的是上子树 信号矢量分别与第三层的中间节点通过计算误差失真函数进行比较 如 则走上上子树 送0至信道 否则走上下子树 送1至信道 结束搜索 如走的是下子树 信号矢量分别与第三层的中间节点通过计算误差失真函数进行比较 如 则走下上子树 送0至信道 否则走下下子树 送1至信道 结束搜索 在信道中传输的是树型码书中树叶的序号 因此 在接收端 其数组型码书只需包含树叶就可根据序号检索 对于二叉树矢量量化而言 如其矢量维数为 码书树叶数为 则树的层数 采用平方误差失真函数 那么时间复杂度 次 信号矢量 空间复杂度 单元 与基本矢量量化相比 二叉树矢量量化的特点就是以空间复杂度的提高来换取时间复杂度的降低 5 1离散信源编码 5 2连续信源编码 5 3相关信源编码 5 4变换编码 对于有记忆信源 采样后的信号序列存在时间相关性 仍然对各个采样时刻的信号值逐个进行量化 会造成码长的冗余 为提高编码效率 对于时间相关的信号序列 通常用两类方法进行编码 第一类方法是利用信号序列的时间相关性 通过预测以减少信息冗余后再进行编码 这类方法称为预测编码 另一类方法则是引入某种变换 将信号序列变换为另一个域上彼此独立或者相关程度较低的序列 同时将能量集中在部分样值上 再对这个新序列进行编码 这类方法称为变换编码 5 3相关信源编码 现在讨论预测编码 为方便 将第个时刻的信号值记为 相应第个时刻的信号值记为 对于时间相关的信号序列 由于与相关 故只要知道 就可对进行预测 设预测值为 则 称为预测误差 5 3 1预测编码 通过预测 我们将所携带的信息量分成了两部分 一部分为所携带的信息量 它实际上是所携带的信息量 另一部分是所携带的信息量 它才是所携带信息量的新增加部分 只要预测足够准确 就足够小 因此 如果是对进行量化 编码而不是对进行量化 编码 就会减少信息冗余 从而提高编码效率 由于预测编码是对进行量化 编码 接收端译码后也只能得到 接收端必须重建 而 因此接收端也同样需要进行预测 线性预测是最常用的预测方法 其表达为 式中 称为预测阶数 为加权系数 预测阶数应该取多大 加权系数又应该怎样选取 才能在性能和简单上得到合理的折中 为此 人们提出了许多方案 最常用的是增量调制 或DM DifferentialModulation 差分脉冲编码调制 DPCM DifferentialPulseCodeModulation 和自适应差分脉冲编码调制 ADPCM AdaptiveDifferentialPulseCodeModulation 这类方案通常也称为差值编码 一 增量调制 增量调制是预测编码中最简单的一种 增量调制原理如下 其中 a 为发送端 b 为接收端 a b 5 3 2差值编码 在发送端 将信号值与量化预测值之差进行1比特量化 所谓1比特量化 就是只对差值的符号而不是大小进行量化 即当时 否则 同时 在的基础上加减一个量化增量 以形成下一个采样时刻的量化预测值 备下一个采样时刻求差值之用 编码则当时 时 其码长为1 在接收端 通过译码将还原为量化增量后 将量化增量与量化预测值相加即可得到量化值 同时 在的基础上加上一个量化值 以形成下一个采样时刻的量化预测值 备下一个采样时刻相加之用 例5 3 1 已知某归一化信号序列 设初始量化 量化增量 求其增量调制编码和量化值 的编码 的量化值 在增量调制中 量化噪声分为一般量化噪声和过载量化噪声 一般量化噪声 即1比特量化的量化噪声 其幅度不会超过量化增量 过载量化噪声则是由信号斜率过大而产生的 因为在增量调制中 每个采样间隔只允许一个量化增量的变化 所以当信号斜率比这个固定斜率大时 就会产生过载量化噪声 过载量化噪声 由于的最大斜率是 因此 为了避免产生过载量化噪声 最大信号斜率必须满足 对于正弦信号 避免产生过载量化噪声的条件是 即 通常取 所以为了避免产生过载量化噪声 增量调制的采样频率要远远大于奈奎斯特采样定理的要求 二 差分脉冲编码调制 差分脉冲编码调制原理如下 其中 a 为发送端 b 为接收端 a b 在发送端 将信号值与量化预测值之差进行量化 量化可以采用均匀量化 也可以采用非均匀量化 由于差值的动态范围一般比较小 通常用均匀量化且量化码的长度取3就可以了 因此量化间隔 编码一般也与均匀量化相同 在量化码基础上增加一位极性码 故码长为4 同时 在的基础上加减一个量化值 以形成下一个采样时刻的量化预测值 备下一个采样时刻求差值之用 在接收端 通过译码将还原为量化值后 将量化值与量化预测值相加即可得到量化信号值 同时 在的基础上加上一个量化信号值 以形成下一个采样时刻的量化预测值 备下一个采样时刻相加之用 例5 3 2 已知某归一化信号序列 设初始值 采用码长为4的均匀量化 量化间隔 求其差分脉冲编码调制的编码和量化信号值 DPCM的编码 DPCM的量化信号值 在差分脉冲编码调制中 量化噪声 即均匀量化的量化噪声 其幅度不会超过量化间隔的一半 5 1离散信源编码 5 2连续信源编码 5 3相关信源编码 5 4变换编码 5 4变换编码 所谓变换编码 就是引入某种变换 通常是正交变换 将时间相关的信号序列变换为另一个域上彼此独立或者相关程度较低的序列 同时将能量集中在部分样值上 再对这个新序列进行编码 给能量较大的分量分配较多的比特 给能量较小的分量分配较少的比特 从而提高编码整体效率的方法 变换编码的关键是找到一种合适的变换 使时间相关的信号序列成为变换域上彼此独立或者相关程度较低的序列 同时将能量集中在部分样值上 满足这样条件的变换有傅立叶变换 余弦变换 哈达玛变换 变换 小波变换等 子带编码首先将信号分割成若干个不同的频带分量 一般称其为子带信号 然后再分别对子带信号进行时间采样和量化编码 可见 子带编码既与频域有关 也与时域有关 是一种基于时频分析的变换编码 子带编码原理如下 其中 a 为发送端 b 为接收端 a 在发送端 用一组带通滤波将信号分割成若干个不同的频带分量 将这些子带信号通过频率搬移为基带 再对其分别采样 采样频率应满足奈奎斯特定理 如果将各子带带宽记为 则采样频率可取 采样后的各信号序列分别进行量化编码形成子带码 将其合并成一个总码通过信道传送到接收端 在接收端 将总码分路为子带码 分别通过译码重建信号序列 经变换重建基带 再通过将频率搬移重建子带信号 经带通滤波 最后得到重建信号 在子带编码中 如果各子带的带宽 相同 称为等带宽子带编码 否则 称为变带宽子带编码 以语音信号为例 信号的分割通常采用二叉树结构 首先根据整个音频信号的带宽将信号分割成两个相等带宽的子带 高频子带和低频子带 然后将这两个子带或其中一个子带用同样的方法分割成4个或3个子带 这个过程可按需要重复下去 形成个子带 为分割次数 如果分割是满树 所形成的是等带宽子带 如果分割是非满树 所形成的是变带宽子带 例如 带宽为的音频信号 当时 可以形成8个相等带宽的子带 每个子带的带宽为 也可以形成5个不等带宽的子带 分别为 子带编码的好处是 1 即使采用均匀量化 也可以利用人耳或人眼对不同频率信号感知灵敏度不同的特性 对人听觉或视觉不敏感的频带分量分配较少的比特数 以达到数据压缩的目的 2 各子带的量化噪声都束缚在本子带内 从而避免幅值较小的子带信号被其它子带的量化噪声所掩盖