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

信 源 编 码 器 信 源 发 出 的 消 息 符 号 集 输 出 的 码 字 集 合 C（ 代 码 组 ） qSSSS ,., 21 qWWWC ,., 21 信 道 的 基 本 符 号 集 合 qxxxX ,., 21 ix 信 源 符 号 Si 码 1 码 2 码 3 码 4 S1 00 0 0 0 S2 01 01 11 10 S3 10 001 00 00 S4 11 111 11 10 )()()()( 4321 4321 spspspsp ssssPS NN CS CS 码信源)11,01(),( 21 CSSS一 个 分 组 码 若 对 任 意 有 限 的 整 数 N,其 N次 扩 展 码 均 为 非 奇 异 码 ，则 称 为 唯 一 可 译 码 。 或 每 个 信 源 符 号 序 列 映 射 成 一 个 固 定 的 码 字 ， 并 且 代 码 组 中 每个 码 字 只 能 唯 一 地 被 译 成 所 对 应 的 信 源 符 号 序 列 。 )1111,1101,0111,0101(),( 221221112 CSSSSSSSSS 无 需 考 虑 后 续 的 码 符 号 即 可 从 码 符 号 序 列 中 译 出 码 字 ， 这 样的 唯 一 可 译 码 称 为 即 时 码 ， 又 称 非 延 时 码 。 树 根 一 阶 节 点 二 阶 节 点 三 阶 节 点(终 端 节 点 )A000 1 10 1 0 11 10 0 1000 111110101100011010001 为码字的长度lqr Nl , rqNlqr Nl log/log rqNL loglog由 5 2log/32log log/log rqNlqr Nl )()()( 21 21 qqN pppPS 进 行 长 度 为 的 定 长 编 码 ， rxxxX , 21 NS对用 码 元 集设 离 散 无 记 忆 信 源 )()()( 21 21 qqSpSpSp SSSPS 的 熵 为 H(S)， 其 N次 扩 展对 于 ,0,0 只 要 满 足 )(log SHrNl (正 定 理 )则 当 N足 够 大 时 ， 几 乎 可 实 现 无 失 真 信 源 编 码 ， 此 时 译 码 差 错小 于 。反 之 ， 若 2)(log SHrNl则 当 N足 够 大 时 ， 译 码 错 误 概 率 趋 于 1(编 码 误 差 任 意 大 )（ 逆 定 理 ） l信 源 为 symbolbitXH /5)( symbolbitXH /4.1)( 1log )( 次扩展代码组的熵次扩展信源的熵lNrl SNH )(log,1)( )( SHrNlSH SH此时最佳编码时， 2 iSIDN 222 1 SH SIDN i iSID 为 自 信 息 的 方 差如 果 为 最 佳 编 码 ， 则 4143 21 SSPS 96.0510 求 信 源 序 列 的 长 度 。允 许 错 误 概 率 722221 22 222 22 22 222 1013.4)1()( )( 4715.0)()(log )(2)()( )()(2)()( )()(2)()( )()(2)()()()()( /811.0)( NSH SIDN SHpp SHSHSIE SIESHSHSIE SHSIESHSIE SHSISHSIESHSIESID SH ii ii i ii ii iiii 则根据符号比特解： 第 三 节 离 散 无 记 忆 信 源 的 变 长 编 码 设 信 源 符 号 集 为 ),( 21 qSSSS 不等式）kraftrqi l i (11 其 分 别 对 应 码 长 为 l1,l2,lq， 则 即 时 码 存 在 的 充 要 条 件 是 ：),( 21 qwwwW 对 信 源 进 行 编 码 ， 相 应 的 码 字 集 为),( 21 rxxxX 码 符 号 集 为不等式）McMillanrqi l i (11 在 满 足 kraft不 等 式 的 条 件 下 ， 唯 一 可 译 码 存 在 的 充 要 条件 是 ： 设 S0为 原 始 码 字 的 集 合 。 再 构 造 一 系 列 集 合 S1,S2,Sn。构 造 S1,S2, Sn的 方 法 ： 1、 首 先 考 察 S0中 所 有 的 码 字 。 若 码 字 Wj是 码 字 Wi的 前 缀 ，即 Wi = WjA， 则 将 后 缀 A列 为 S1中 的 元 素 ， S1就 是 由 所 有 具 有这 种 性 质 的 A构 成 的 集 合 。 2、 当 n1， 则 将 S0于 Sn-1比 较 ， 看 是 否 S0中 的 码 字 是 Sn-1的 前缀 ， 如 果 是 ， 则 取 后 缀 为 Sn中 元 素 ， 且 看 Sn-1中 码 字 是 否 为 S0中 码 字 的 前 缀 ， 如 果 是 ， 则 取 后 缀 为 S n中 元 素 ， 如 此 构 成 集合 Sn。 S0 S1 S2 S3 S4 S5 S6 S7 S8 a d eb de b ad d eb 0 c bb cde bcde ad abb bad deb bbcde , 7654321 aaaaaaa , bbcdedebbadabbadca 信源符号码元/)(1 qi ii lspl 平 均 每 个 码 元 载 荷 的 信 息 量 = 信 道 的 信 息 传 输 率 R码符号比特/)(lSHR秒比特信道的信息传输速率/)(tl SHRt = 信 道 中 平 均 每 个 符 号 所 能 传 送 的 信 息 量 l 对 于 某 一 信 源 和 某 一 码 元 集 ， 若 有 一 种 唯 一 可 译 码 ， 其 平均 长 度 小 于 所 有 其 他 的 唯 一 可 译 码 ， 则 称 此 码 为 最 佳 码 (紧 致码 )。 NrSHNLrSH N 1log )(log )( 则 总 可 以 找 到 一 种 编 码 方 法 构 成 唯 一 可 译 码 ， 使 信 源 S中 的 每个 信 源 符 号 所 需 的 码 字 与 平 均 长 度 满 足 有 一 离 散 无 记 忆 信 源 S=Si(i=1,2,q)， 输 出 符 号 为 q个 ， 其熵 为 H(S)， 它 的 N次 扩 展 信 源 ),.,2,1( NiN qiS )()( SNHSH N NS其 熵 ,若 用 r个 码 元 对 信 源 进 行 编 码其 中 ， 为 中 每 个 信 源 符 号 序 列 编 码 所 对 应 的 码 字 的 平均 码 长 。NL NS i Nqi iiiiN pL 1 ,)(所对应的码字的长度为所对应的平均码长中每个信源符号离散无记忆信源iN SSNL : NLN )(log )( SHrSH r变 长 编 码 定 理 说 明 ： 若 编 码 的 平 均 码 长 小 于 信 源 的 熵则 唯 一 可 译 码 不 存 在 。 同 时 指 出 ： 要 做 到 无 失 真 的 信 源 编 码 ， 变 换 每 个 信 源 符号 平 均 所 需 要 最 少 的 r进 制 码 符 号 数 ， 就 是 原 始 信 源 的 熵 值 （ 以 r为 底 的 ） ； 如果 编 码 的 平 均 码 长 小 于 原 始 信 源 的 熵 值 ， 则 唯 一 可 译 码 不 存 在 ， 此 时 ， 译 码 必然 带 来 失 真 。 )(SHr rR log当 平 均 码 长 为 时 ， 编 码 后 的 信 道 的 信 息 传 输 率此 时 有 ： 比 特 /符 号信 道 的 信 息 传 输 率 R=无 损 信 道 的 信 道 容 量 C 可 知 此 时 ： R达 到 最 大 值 ， 实 现 信 源 与 信 道 的 统 计 匹 配 。 变 长 编 码 定 理 还 表 明：在 无 失 真 信 源 编 码 中 ， 采 用 扩 展 信 源 的 手 段 ， 虽 然可 以 减 少 每 一 个 信 源 符 号 所 需 要 的 平 均 码 符 号 数 ， 使 编 码 的 有 效 性 提 高 ， 但 无论 如 何 扩 展 ， 其 有 效 性 是 有 限 度 的 ， 其 极 限 值 即 是 信 源 的 熵 值 。 rl SHl SHr log )()( 码 的 剩 余 度 =1- 有 一 离 散 无 记 忆 信 源 , 4143 21 SSPS symbolbitSH /811.0)( 1,0 21 SS 21 /1)(i ii llSpl信源符号码元则811.0)()( 2 l SHl SHr编码效率码元信道信息传输率/811.0)( bitlSHR 解 :(1) 161163163169 221221112 SSSSSSSSPS 111110100用树图构造即时码为信源序列码元/3321 16271611631631692 l信源符号码元/32/272/ 2 ll 961.0811.0)( 3227 l SHr编码效率码元信道信息传输率/961.0)( bitlSHR 为 了 编 成 唯 一 可 译 码 ， 首 先 计 算 第 i个 消 息 的 累 加 概 率 11 )(iK Ki Spp 1)(log)(log iii SplSp S1 0.40 1.32 2 0 00 S2 0.30 1.74 2 0.40 01 S3 0.20 2.32 3 0.70 101 S4 0.10 3.32 4 0.90 1110 11100.090.01011.070.0 0110.040.0000.00 43 21 pp pp信源符号码符号编码的平均码长/40.2)(41 i ii lSpl码符号比特信道的信息传输率/796.0)( lSHR 796.0log )( rl SH编码效率 用 0， 1码 符 号 分 别 代 表 概 率 最 小 的 两 个 信 源 符 号 ， 并 将 这 两个 概 率 最 小 的 信 源 符 号 合 并 成 一 个 ， 从 而 得 到 只 包 含 q-1个 符号 的 新 信 源 S1,称 为 缩 减 信 号 源 。 编码对其进行二元HuffmanSSSSSPS 1.01.02.02.04.0 54321信 源 符 号 Si 概 率 p(Si) 编 码 过 程 码 字 Wi 码 长 li S1 S2 S3 S1 0.4 S2 0.2 S3 0.2 S4 0.1 S5 0.1 0.40.2 0.40.60.2 10 10 10 01 51 /2.2)(i ii lSpl信源符号码元则平均码长 0 A0 100 1 1 1010000010 0011 信源符号比特/123.2)(log)()( 51 i ii SpSpSH码符号比特信道的信息传输率/965.0)( lSHR 965.0)( l SHr编码效率 码 字 Wi 码 长 l i S1 0.4 0.4 0.4 0.6 00 2 S2 0.2 0.2 0.4 0.4 10 2 S3 0.2 0.2 0.2 11 2 S4 0.1 0.2 010 3 S 5 0.1 011 301 01 01 01 A00 1 1 1000 10 110 1010 011965.0 /2.2编码效率信源符号码元平均码长l 比第一种好。由此可见，第二种质量差现在讲的哈夫曼码的方差先前讲的哈夫曼码的方16.036.1 )()( 22211 222 LLqi iiL llSplliE 结 论 ：同，用码方差表示：而他们的质量不完全相和编码效率码长两种编码有相同的平均l r元 哈 夫 曼 码 可 由 二 元 哈 夫 曼 码 的 编 码 方 法 推 广 得 到 。 只是 编 码 过 程 中 构 成 缩 减 信 源 时 ， 每 次 将 r个 概 率 最 小 的 符 号 合并 ， 并 分 别 用 0， 1， ， r-1码 元 表 示 。 为 了 充 分 利 用 短 码 ， 使 哈 夫 曼 码 的 平 均 码 长 最 短 ， 必 须是 最 后 一 个 缩 减 信 源 有 r个 信 源 符 号 。 因 此 ， 对 于 r元 哈 夫 曼 码 ，信 源 S的 符 号 个 数 q必 须 满 足为非负整数表示信源缩减的次数，其中 rrq )1( 如 果 信 源 S的 符 号 个 数 q不 满 足 上 式 ， 则 增 补 一 些 概 率为 0的 信 源 符 号 。 ： 有 一 离 散 无 记 忆 信 源 025.0025.005.02.03.04.0 654321 SSSSSSPS码 元 集 X=(0,1,2)， 对 S进 行 3元 哈 夫 曼 编 码 。 0)(72 323 )1( 77 SpSq qr rrq则增补 信 源 符 号 概 率 编 码 过 程 码 字 Wi 码 长 li Si p(Si) S1 S2 Wi li S1 0.4 0.4 0.4 0 1 S2 0.3 0.3 0.3 2 1 S3 0.2 0.2 0.3 10 2 S4 0.05 0.05 12 2 S 5 0.025 0.05 110 3 S6 0.025 111 3 S7 0 112 3210 210 210 61 /35.1)(i ii lSpl信源符号码元其平均码长 霍 夫 曼 编 码 的 特 点 ： 1） 由 于 霍 夫 曼 编 码 总 是 以 最 小 概 率 相 加 的 方 法 来 缩 减 参 与 皮 埃 对 的 概 率 个数 ， 因 此 概 率 越 小 ， 对 缩 减 的 贡 献 越 大 ， 其 对 应 消 息 的 码 字 也 越 长 。2） 最 小 概 率 相 加 的 方 法 使 得 编 码 不 具 有 唯 一 性 ， 尤 其 是 碰 到 存 在 几 个 消 息符 号 有 着 相 同 概 率 的 情 况 ， 将 会 有 多 种 路 径 选 择 ， 即 既 具 有 多 种 可 能 的 代 码组 集 合 。3） 尽 管 对 同 一 信 源 存 在 着 多 种 结 果 的 霍 夫 曼 编 码 ， 但 它 们 的 平 均 码 长 几 乎都 是 相 等 的 ， 因 为 每 一 种 路 径 选 择 都 是 使 用 最 小 概 率 相 加 的 方 法 ， 其 实 质 都是 遵 循 最 佳 编 码 的 原 则 ， 因 此 霍 夫 曼 编 码 是 最 佳 编 码 。 霍 夫 曼 编 码 存 在 的 问 题 ： 1） 霍 夫 曼 编 码 要 求 信 源 消 息 概 率 已 知 或 可 估 计 。 由 于 初 始 信 源 不 可 能 总 是 统 计好 了 概 率 ， 为 此 编 码 之 前 必 须 先 估 算 信 源 的 统 计 特 性 。 在 信 源 具 有 记 忆 性 能 并用 霍 夫 曼 编 码 来 表 示 信 源 的 扩 展 输 出 时 ， 概 率 的 估 计 很 耗 费 时 间 。 2） 霍 夫 曼 编 码 是 建 立 在 编 码 器 和 译 码 器 都 知 道 码 树 结 构 的 基 础 上 的 ， 如 果 信 源消 息 数 目 变 大 ， 则 树 型 结 构 的 大 小 和 算 法 的 复 杂 性 会 呈 指 数 规 律 增 加 。 例 5-10：待 编 码 的 字 符 序 列 为 ： abaaaabaabaaabbbbbbbabbbbbaababaababa.,试用 Lemple-Ziv方 法 给 出 编 码 结 果 。 编 码 结 果 0a 0b 1a 3b 4a 4b 2b 7b 1b 8b 5b 11b 地 址 1 2 3 4 5 6 7 8 9 10 11 12 码 段 内 容 a b aa aab aaba aabb bb bbb ab bbbb aabab aababa 由 此 可 知 ： Lemple-Ziv编 码 利 用 了 已 编 码 信 息 进 行 当 前 的 编 码 ， 编 码 结 果 是等 长 码 ， 编 码 过 程 就 是 建 立 码 地 址 和 将 待 编 码 消 息 序 列 分 段 的 过 程 ， 所 有 的码 段 内 容 都 是 不 同 的 。 ： 若 有 一 信 源 ：每 秒 钟 发 出 2.66个 信 源 符 号 ， 将 此 信 源 的 输 出 符 号 送 入 某 一 个 二元 信 道 中 进 行 传 输 （ 假 设 信 道 是 无 噪 无 损 的 ） ， 而 信 道 每 秒 钟 只传 递 2个 二 元 符 号 。 2.08.0)( 21 sssps 04.016.016.064.0)( 2212211122 sssssssssps信源符号二元符号符号序列二元符号/78.0 /56.1 2ll 008.0032.0032.0032.0128.0128.0128.0512.0)( 22212221211222112121111133 sssssssssssssssssssssssssps1 000 001 010 01100 01101 01110 01111信源符号二元符号符号序列二元符号/728.0 /184.23ll 一 .游 程 编 码1.游 程 编 码 的 基 本 原 理 游 程 编 码 是 哈 夫 曼 编 码 的 一 种 改 进 和 应 用 ， 主 要 用 于 黑 白 二值 文 件 的 传 真 。 表 示 背 景 （ 白 色 ） 时 像 素 为 码 元 “ 0” ， 表 示 内 容 （ 黑 字 ）像 素 为 码 元 “ 1” 。 对 大 量 出 现 的 连 “ 0” 或 连 “ 1” （ 黑 或 白 ） 像 素 序 列 在传 输 时 ， 可 通 过 像 素 类 别 （ 黑 、 白 像 素 ） 加 重 复 次 数 的 方 式 来加 以 表 示 ， 由 此 思 路 构 成 的 一 种 编 码 方 式 即 是 。重 复 出 现 的 同 类 像 素 的 长 度 称 为 。规 定 第 一 个 游 程 为 白 游 程 。 第 五 节 实 用 的 信 源 编 码 方 法 MH码 是 国 际 电 话 电 报 咨 询 委 员 会 提 出 的 文 件 、 传 真 类 一 维 数 据 压 缩编 码 的 国 际 标 准 ， 是 由 游 程 编 码 和 哈 夫 曼 编 码 相 结 合 而 成 的 一 种 改 进 型哈 夫 曼 码 .其 具 体 编 码 规 则 为 ： 游 程 长 度 在 0 63之 间 时 ， 码 字 直 接 由 相 应 的 终 止 码 表 示 。 游 程 长 度 在 64 1728之 间 时 ， 码 字 由 一 个 形 成 （ 组 合 )码 加 上 一 个 终 止 码构 成 。 每 行 必 须 以 白 游 程 开 始 ， 以 一 个 同 步 码 EOL结 束 ， 且 每 页 文 件 也 必 须 以 同步 码 EOL开 始 （ 用 以 清 洗 系 统 ， 防 止 误 差 扩 散 ） 。 每 行 游 程 总 和 必 须 为 1728个 像 素 ， 否 则 该 行 出 现 错 误 。 为 了 达 成 同 步 操 作 ， 每 行 编 码 的 传 输 时 间 最 短 为 20ms， 最 长 为 5s； 不 足20ms的 行 ， 需 EOL码 之 前 填 入 足 够 的 “ 0” 码 元 。 连 续 6个 EOL表 示 文 件 页 传 输 的 结 束 。 按 编 码 规 则 ， 一 页 文 件 传 真 编 码 的 最 终 格 式 如 图 所 示 。 页首填充码页尾tT tTTT EOL EOL EOL EOL 6个EOL数据数据数据数据数据其 中 ， EOL是 行 同 步 码 ， 其 码 字 为 0000000000001， 在 正 常 的游 程 编 码 数 据 中 不 可 能 出 现 连 11个 0， 故 EOL能 够 在 出 现 突 发差 错 时 ， 重 新 建 立 行 同 步 ， 控 制 差 错 不 扩 散 到 下 一 行 ， 同 时每 一 页 结 束 时 ， 转 回 控 制 （ RTC） 由 6个 EOL组 成 。 若 传 真 文 件 某 行 的 扫 描 像 素 序 列 如 表 所 示 ， 现 用 码进 行 编 码 。白 游 程 黑 游程 白 游 程 黑 游 程 白 游 程 黑 游 程 码 是 一 种 改 进 码 ， 与 前 面 介 绍 的 哈 夫 曼 码 存 在 的 两 点 差异 ： 码 的 编 码 表 是 由 各 类 文 件 的 平 均 统 计 特 性 指 标 得 到 的 ，并 且 固 定 不 变 ， 因 而 多 数 情 况 下 ， 码 并 非 紧 致 码 （ 最 佳 码 ） 。 游 程 的 码 字 由 形 成 码 和 终 止 码 组 成 ， 可 使 码 字 大 大 缩 短 。 具 体 编 码 过 程 如 下 ： 从 信 源 符 号 全 序 列 出 发 ， 将 各 信 源 序 列 依 累 积 概 率 分 布函 数 的 大 小 映 射 到 , 区 间 ,将 , 区 间 分 成 许 多互 不 重 叠 的 小 区 间 。 此 时 每 个 符 号 序 列 均 有 一 个 小 区 间 与 之对 应 ， 因 而 可 在 小 区 间 内 取 点 来 代 表 该 符 号 序 列 。 )(1log pl il il )(sPs )()(),( spsPsP s sr )(srp )(srPs )(sP)()()( )()()()( rpspsrp rPspsPsrP )(sP )(sC )(sp )(sA )()()( )()()()( rpsAsrA rPsAsCsrC 0)(,1)( CA)(sC )()( rpsA 1.0)(,1.0)(,2.0)(,6.0)(, 43214321 apapapapaaaaS 431 aaa 0)( 1 aP 6.0)( 2 aP 8.0)( 3 aP 9.0)( 4 aP算 术 编 解 码 过 程 如 下 ： 0)(,1)( CA 6.06.01)()()( 0010)()()()( 11 11 apAaA aPACaC 06.01.06.0)()()( 48.08.06.00)()()()( 3131 31131 apaAaaA aPaAaCaaC 006.01.006.0)()()( 534.09.006.048.0)()()()( 431431 43131431 apaaAaaaA aPaaAaaCaaaC 431 aaa 8006.0log)(1log pl 0.534 )( 431 aaaP 210431 .)100010001.0(0.534)( )( aaaP：431 aaa 4a 3a1a 0 10 10.60 0.60.540.480 0.54 0.534)(C )( 1aC )(A)( 1aA )( 31aaC )( 31aaA )( 431 aaaA)( 431 aaaC 编 码 的 基 本 原 理基 本 思 路 :查 字 典 很 相 似 ， 即 在 组 成 并 拥 有 词 典 的 情 况 下 ，通 过 “ 单 词 ” 简 短 的 位 置 信 息 ， 间 接 的 表 达 “ 单 词 ” 的 内 容 。 ： 习题：1.设有一页传真文件其中某一扫描行的像素点如下所示：83白9黑12白5黑1619白求：（1）该扫描行的MH码；（2）编码后该行总比特数；（3）本行编码压缩比（原码元总数/编码后码元总数.实验3：试编制算术编码算法实现程序。实验4：编码实验唯一可译码判断过程。