第五章_信源编码.ppt

第五章信源编码 5 1 1码字唯一可译的条件5 1 2香农编码5 1 3费诺编码5 1 4赫夫曼编码5 1 5游程编码5 1 6冗余位编码 2 信源编码概述 编码是为了优化通信系统 一般的通信系统的主要性能指标 有效性 可靠性和安全性信源编码的目的 提高通信系统的有效性 通常通过压缩信源的冗余度来实现 即压缩每个信源符号的信息量 使得同样多的信息用较少的信息传输率来传送信源编码的思路 根据信源输出符号序列的统计特性 寻找一定的把信源输出符号序列变换为最短码字序列的方法信源编码的基本途径 使编码后的符号序列中的各个符号尽可能地相互独立 即解除相关性 使编码后各个符号出现的概率尽可能的相等 即概率均匀化 信源编码的基础 无失真编码定理和限失真编码定理 3 5 1离散信源5 1 1码字唯一可译的条件 码的分类 按码长分类 定长码 码中所有码字的码长都相等奇异码 码中存在有相同的码字 对应不同的信源符号 唯一可译码 由码的码字组成任意有限长的码字序列只能被唯一地译为对应的信源符号序列即时码 译码器收到一个完整的唯一可译码字以后 无需参考后续的码字 码元 就能立即译码 4 5 1 1码字唯一可译的条件 码A 奇异码 定长码 非唯一可译码码B 非奇异码 定长码 唯一可译码码C 非奇异码 非唯一可译码码D 唯一可译码码E 非即时码码F 即时码 即时码中任何一个码字均不是其它码字的前缀 5 定义 如果一个码组中的任一个码字都不是另一个码字的延长或者找不到任何一个码字是另一个码字的前缀 或者说 任何一个码字后加上若干码元后都不是码组中另一个码字 则称为即时码或非延长码 也叫前缀条件码 异前置码 异字头码 逗点码 所有的码 非奇异码 唯一可译码 即时码 5 1 1码字唯一可译的条件 6 5 1 1码字唯一可译的条件 用树图法可以方便地构造即时码 从树根开始 树中每个中间节点都伸出1至r个树枝 不同的树枝标记不同的码元 将所有的码字都安排在终端节点上就可以得到即时码每个中间节点都正好有r个分枝的树称为整树 满树 所有终端节点的阶数都相等的树为完全树 对应于定长码 7 5 1 1码字唯一可译的条件 二元满树 二元非满树 三元非满树 三元满树 8 唯一可译定长码存在的条件 对于定长码 非奇异码一定是唯一可译码 注意 上述条件是唯一可译定长码存在的必要条件 而非充分条件 平均每个单信源符号所需要码元的个数 9 克拉夫特 Kraft 不等式 10 唯一可译码判别准则 11 唯一可译码判别准则 举例 设信源消息集合 x1 x2 x3 x4 x5 x6 x7 它们分别被编码为 a c ad abb bad deb bbcde 可构造出下表所示的吗符号集序列 当n 7时 sn是空集 而s5都包含s0中的元素 因此不是唯一可译码 12 5 1 2香农编码 香农编码是采用信源符号的累计概率分布函数来分配码字的 设某离散无记忆信源2进制香农编码步骤 将信源符号以概率递减的次序排列起来 为方便起见 令 按下式求xi对应码字的码长li 按下式逐步求信源符号xi的概率累加和Pi 将所有的累加和概率Pi变换成2进制数 取小数点后Pi位作为信源符号xi的2进制码字 13 编码所得的码字 没有相同的 所以是非奇异码 也没有一个码字是其它码字的前缀 所以是即时码 香农码的效率不高 其冗余度较大 不是最佳码 实用性受到较大限制 14 例 有一单符号离散无记忆信源 练习 对该信源编二进制香农码 其编码过程如下表所示 15 5 1 3费诺编码 费诺编码又称为子集分解法 通过将信源符号的概率分组 对每个组分配相应的码元来实现编码 其编码步骤如下 将信源符号以概率递减的次序排列起来 为方便起见 令 将依次排列的信源符号按概率分成r组 使每个组的信源符号的概率和尽可能接近或相等 然后赋予每组一个r元码符号 例如编2进制费诺码 则每次分组均分成两组 每个组分别赋予一个2元码符号 0 或 1 将每一大组的信源符号按概率和递减的次序再分成r组 使同一大组细分的r个小组的信源符号的概率和尽可能接近或相等 并分别赋予每小组一个r元码符号 重复上述的分组 分配r元码符号的过程 直至最个分得的每个小组只剩一个信源符号为止 最后每个信源符号所对应的码元序列就是相应的码字 16 17 费诺编码的码树图 实质上是一种构造码树的方法 所以费诺码是即时码概率大 则分解的次数小 概率小 则分解的次数多码字集合是唯一的分解完后 码字与码长便确定了 费诺码考虑了信源的统计特性 使经常出现的信源符号对应短码字 但是不一定能使短码得到充分利用 尤其当信源符号较多时 若有一些符号概率分布很接近时 分两大组的组合方法就会很多 可能某种分大组的结果 会使后面小组的 概率和 相差较远 从而使平均码长增加 费诺编码特点 18 费诺码适合于每次分组概率都很接近的信源 特别是对每次分组概率都相等的信源进行编码时 可达到理想的编码效率 费诺码考虑了信源的统计特性 使概率大的信源符号能对应码长短的码字 从而有效地提高了编码效率 一般而言 费诺编码不是最佳编码 它的编码效率 优于香农码 要比赫夫曼编码效率稍低 19 例 设有一单符号离散信源对该信源编二进制费诺码 练习 20 5 1 4赫夫曼编码 赫夫曼编码是一种最佳的逐个符号的编码方法 所得的码是即时码 其平均码长最短 因而是最佳编码2进制赫夫曼编码的步骤如下 将信源符号以概率递减的次序排列起来 为方便起见 令 将两个概率最小的信源符号xn 1 xn各分配一个码元 0 和 1 并将这两个符号合并成一个新符号 合并后新符号概率为原来两个符号概率之和 从而得到包含n 1个符号的缩减信源S1 把缩减信源S1的符号仍按概率递减次序排列 重复步骤2得到只含有n 2个信源符号的缩减信源S2 重复上述步骤 直至缩减信源只剩1个信源符号为止 然后从最后一级缩减信源开始 依编码路径向前返回 就得到各信源符号所对应的码元序列 即对应的码字 21 22 赫夫曼编码的码树 赫夫曼编码的特点概率大的符号安排在离根节点较近的终端节点保证了概率大的符号对应于短码 概率小的符号对应于长码每次缩减信源的最长两个码字具有相同码长每次缩减信源的最后两个码字总是最后一位码元不同 前面各位码元相同 2元码情况 编码不具有惟一性 赫夫曼编码是最佳码 23 方差越小 各码字长度就越接近平均码长 设计的编码器也就越简单 赫夫曼编码的非唯一性 每次对缩减信源两个概率最小的符号分配 0 或 1 码元是任意的 所以可得到不同的码字 只要在各次缩减信源中保持码元分配的一致性 即能得到可分离码字不同的码元分配 得到的具体码字不同 但码长li不变 平均码长也不变 所以没有本质区别缩减信源时 若合并后新符号的概率与其它符号概率相等 从编码方法上来说 这几个符号的次序可任意排列 编出的码都是正确的 但得到的码字不相同 不同的编法得到的码字长度li也不尽相同 但平均码长仍不变对同一信源的多种赫夫曼编码 除了用平均码长来衡量外 当平均码长相同时 可以码长li偏离平均码长的方差来判断 24 方案一 25 方案二 26 赫夫曼编码的非唯一性 续 方案一较好 其码长变化较小 在赫夫曼编码过程中 当缩减信源符号按概率大小 以递减次序自上而下重新排列时 应把合并后的新符号尽量置于缩减信源中具有相同概率的其它符号之上 减少合并后的新符号被重复赋予码元的次数 进而减小码字长度相对于平均码长的摆动上述方法不会引起平均码长的变化 可以使短码得到充分利用 27 r进制赫夫曼编码 r进制赫夫曼编码是2进制编码的推广 求缩减信源时需要求r个信源符号使其概率和最小 并对r个信源符号分别分配码元0 1 r 1 然后将它们缩减为一个新符号 重复上述缩减和分配码元的步骤直至缩减信源中只剩下一个符号为止r进制霍夫曼编码 如果从一始就每r个符号缩减为一个新符号 则缩减到最后时剩下的信源符号可能不到r个 为了使平均码长最短 必须使最后一步缩减信源有r个信源符号 码树图中至少有一个中间节点的后续枝数不足r 码树图中每个中间节点后续枝数为r 2进制码不存在非全树的情况 因为后续枝数是1时 这个枝就可以去掉使码字长度缩短 28 r进制赫夫曼编码 续 对r进制编码 若所有码字构成全树 可分离的码字数必为 k为信源缩减次数 1 若信源所含的符号数n不能构成r进制全树 必须增加s个不用的码字形成全树 且s r 1 若s r 1 意味着某个中间节点之后只有一个分枝 为了节约码长 这一分枝可以省略 为了使平均码长最短 当码树为非全树时 有s个码字不用 第一次对最小概率和的符号分配码元时只取r s个 分别赋予码元0 1 r s 1 把这些符号的概率相加作为一个新符号的概率 与其它符号一起重新排列以后每次就可以取r个符号 分别赋予码元0 1 r 1 如此下去直至缩减至1个信源符号 得到各符号的r进制码字 29 可见 要发挥赫夫曼编码的优势 一般情况下 信源符号集的符号数应远大于码元数 30 练习 设单符号离散无记忆信源如下 要求对信源编二进制霍夫曼码 在图中读取码字的时候 一定要从后向前读 此时编出来的码字才是可分离的异前置码 若从前向后读取码字 则码字不可分离 31 香农码 费诺码和赫夫曼码总结 香农码 费诺码 赫夫曼码都考虑了信源的统计特性 使经常出现的信源符号对应较短的码字 使信源的平均码长缩短 从而实现了对信源的压缩 香农码编码结果唯一 但在很多情况下编码效率不是很高费诺码和赫夫曼码的编码方法都不唯一费诺码比较适合于对分组概率相等或接近的信源编码赫夫曼码对信源的统计特性没有特殊要求 编码效率比较高 对编码设备的要求也比较简单 因此综合性能优于香农码和费诺码赫夫曼码通常适用于多元信源 对于二元信源 必须采用合并符号的方法 才能得到较高的编码效率 32 5 1 5游程编码概述 香农码 费诺码 赫夫曼码主要是针对无记忆信源 当信源有记忆时上述编码的效率不高游程编码是一种对相关信源较为有效的扩展符号集的编码方法 是赫夫曼编码的改进和应用 主要用于只有黑 白二值灰度的文件传真 如文件 报纸 表格 手写体字 图纸等文件传真是把一页文件扫描为n m个像素 由于黑 白二值文件只有两个灰度值 因此采用2进制编码 如果每一个像素用一位二进制码 0 白色 1 黑色 表示 显然一页文件的码元数就等于该页文件的像素数例如 参照国际标准 一张A4幅面 210mm 297mm 的二值文件扫描的辨率为 1728像素 行 4行 mm即一幅A4页面共可分为1188行 每行1728像素 整幅共有2 05M个像素 若用4800bit s的信息传输率进行传输约需7 2分钟 直接传真将需耗费大量的通信时间 33 游程编码概述 续 统计表明 此类传真文件黑白两个灰度值出现的概率为 显然一个像素用一位二进制编码 会有很大冗余度 要提高传真效率 必须去除冗余对于二值灰度的文件 每一扫描行均是由若干个连白 0 像素序列及若干个连黑 1 像素序列组合而成 且同类像素连续出现的概率很大 因此可通过像素类别 黑或白 加重复次数来表示 由此思想构成的编码称为游程编码重复出现的同类像素的长度称为游程长度 白 0 像素序列称为白 0 游程 黑 1 像素序列称为黑 1 游程 34 游程编码概述 续 游程编码的基本结构是编码单元 像素序列 白白黑黑黑黑白白白白白白黑黑黑游程编码 白 2黑 4白 6黑 3 实际上 每一扫描行的白像素序列和黑像素序列是交替出现的 若规定第一游程为白游程 若第一游程为黑游程 则在黑游程前插入一个游程长度为0的白游程 则可将编码中的 符号码 和 标识码 均省略 这样就可把像素序列变换为游程长度序列 且二者是可逆的 例如 像素类别 白 0 黑 1 符号码和游程长度之间的分割符 游程长度序列 45287613321 黑白像素序列 000011111001111111100000001111110111000110 游程长度是随机的 取值为1 2 直至无穷 35 游程 数字序列中连续出现相同符号的一段二元序列的游程 只有 0 和 1 两种符号连 0 这一段称为 0 游程 游程长度 L 0 连 1 这一段称为 1 游程 游程长度 L 1 在二元序列中 0 游程和 1 游程总是交替出现的游程变换将二元序列变换成了多元序列 减弱了原序列符号间的相关性 这样就适合于用其它方法 如赫夫曼编码 进一步压缩信源 提高通信效率r元序列同样也可以变换游程长度序列 但是r元序列 总共有r种游程 为能保证一一对应的可逆变换性 必须再加一些分隔标志符号 才能区分游程长度序列中的某一个长度是r种游程中的哪一个长度 增加分隔标志符号可能会抵消压缩编码得到的好处 故一般不对多元序列进行游程编码游程编码的方法 首先测定 0 游程长度和 1 游程长度的概率分布 即以游程长度为元素 构造一个新的信源对新的信源 游程长度序列 进行赫夫曼编码 游程编码 一般规定二元序列总是从 0 开始 36 二元独立序列的游程长度序列 注 在计算p L 0 时第一个信源符号必然是 0 否则就不是 0 游程 若下一个符号是 1 则游程长度为1 其概率是p1 1 p0 若下一个符号为 0 再下一个符号为 1 则游程长度为2 其概率为p0p1 依此类推 同理可得 若二元独立序列的概率特性已知 由于二元独立序列与游程长度序列的一一对应性 可计算出游程长度序列的概率特性设二元独立序列中符号 0 和 1 出现的概率分别为p0和p1 则 0 游程长度L 0 的概率为 37 0 游程长度序列的熵 1 游程长度序列的熵 同理可得 38 0 游程的平均长度 1 游程的平均长度 同理可得 二元独立序列的熵 0 游程长度序列的熵与 1 游程长度序列的熵之和除以它们的平均游程长度之和 即为对应的原二元独立序列的熵H X 游程变换后符号熵保持不变 因为游程变换是一一对应的可逆变换 39 游程编码的编码效率 根据编码效率的定义和前述分析可得二元序列的编码效率 假设h0 h1 易知 h0 h h1 当 0 游程和 1 游程的编码效率都很高时 采用游程编码的整体编码效率也很高 至少不会低于较小的那个游程的编码效率要想游程的整体编码效率尽可能高 应尽可能提高熵值较大的游程的编码效率 假设 0 游程长度和 1 游程长度的赫夫曼编码效率分别为h1 h2 即 40 游程编码的截断处理 尽管游程长度可以从1一直到无穷长 但建立游程长度与赫夫曼码字之间的一一对应码表将是非常困难 游程越长 其出现的概率就越小 所以 由赫夫曼码的编码规则 概率越小 码字越长 但小概率对应的长码字对平均码长影响很小 故对较长的二元序列 游程编码一般需采用截断处理 以下为一种截断处理方法 选取适当的n值 将游程长度分别为的游程进行赫夫曼编码 得到相应的码表 所有游程长度大于等于的游程 将其编码为多个固定的码字C串接游程长度减去所得余数的二进制表示 具体为 游程长度 则游程编码为CA 其中A为游程长度减去所得余数补足为n位的二进制表示 41 游程编码的截断处理 续 例如 如选择n 8 则可用255个码字构成的赫夫曼码表对应于游程长度不超过255的游程 如用C表示所有游程长度超过255的游程对应的码字的前半部分 则 0 游程和 1 游程当分别编码 建立各自的码表两个码表中的码字可以有重复 但C码必须不同 即分别用C0 C1编码 0 游程和 1 游程译码器要根据后面的码字来判断当前游程的长度 继续考察更后面的码字 42 MH码 MH码是黑白二值文件 传真类数据压缩编码国际标准 是由游程编码和赫夫曼编码综合而成的改进型赫夫曼编码对于A4幅面的文件 一页应有1188或2376条扫描线 每一行扫描线有1728个像素 一页A4纸张约2 05M或4 1M像素 从节省传送时间和存储空间来说 必须进行数据压缩这些像素可能是全黑 全白或黑 白相间隔 黑游程和白游程长度均为0 1728之间 共有2 1728种可能的游程 但不需要对所有这些可能的游程制定编码表将码表划分成两大类 结尾码 其长度为0 63位 分别按游程特性制定对应的赫夫曼编码表 组合基干码 其长度为64的整数倍 按游程特性制定对应的霍夫曼编码表 43 MH编码规则 黑 白游程长度在0 63之间时 直接用结尾码表编码黑 白游程长度在64 1728时 采用组合基干加结尾码进行联合编码每行以白游程开始 以同步码EOL结束 且每页文件以同步码EOL开始每行游程总和为1728个像素每行传输时间范围20ms 5s不足20ms的行 需在EOL码前填入足够的 0 每页文件以6个EOL结束 组合基干码码表 结尾码码表 44 文件页传真MH编码格式 根据MH码表编码 有 22 白 对应编码为00000116 黑 对应编码为001053 白 对应编码为0010010066 黑 因66 64 2 对应编码为0000001111 111559 白 因1559 1536 23 对应编码为010011001 000010022 黑 对应编码为00000110111 例如 幅面A4的传真文件某行的扫描像素序列如下 编码前总码长1728 编码后总码长58 压缩比非常高 MH码的编码表是由各类文件的平均统计特性指标得到的 固定不变 因而多数情况下 MH码不是最佳码游程的码字由构造码和结尾码组成 使码字大大缩短 45 5 1 6冗余位编码概述 在许多信源序列中 常有不少符号不携带信息 除了它的数目或所占时长外 完全可以不传送在电话通信中 讲话时常有间隙 如字句间的停顿 听对方讲话而静默 一般可以不传送图像信源中 背景基本上不变 并在图像中占相当大一部分 而其值为常量 相当于平均亮度 一般也可以不传送在数据信源序列中 数据包间的间歇或某种固定模式 也属于冗余性质上述这些符号可称为冗余位