信息论基础第七周.ppt

信息论基础 杜春娟ducj QQ 22282998Tel 31889581 第三章数据压缩和信源编码 编码的定义定长编码定理变长编码定理香农码费诺码哈夫曼码 问题的提出 1 为什么要进行信源编码 2 信源编码的概念 3 一些码的定义 4 信源编码的方法 人们都希望无失真传送 首先要对信源无差错编码 数字技术应用越来越多 模拟信源通过数字化变成数字信号传送 信源编码的概念 信源编码定义 指定能够满足信道特性 适合于信道传输的符号序列 码序列 来代表信源输出的消息 完成编码功能的器件称为编码器 离散信源输出的码序列离散信源输出的消息是由一个个离散符号组成的随机序列X X1X2 Xl XL Xl x1 x2 xi xn 信源编码就是把信源输出的随机符号序列变成码序列Y Y1Y2 Yk YK Yk y1 y2 yj ym 码符号 码元 编码器的输入是信源符号 x1 x2 xi xn 同时存在另一符号 y1 y2 yj ym 一般元素yj是适合信道传输的 称为码符号 码元 编码器功能 将信源符号集中的符号 或者长为L的信源符号序列 变换成由yj j 1 2 m 组成的长度为ki的序列 码字 码符号序列Y Y1Y2 Yk Yki 称为码字 码长 码字长度 ki称为码字长度或简称码长 编码就是从信源符号到码符号的一种映射 若要实现无失真编码 这种映射必须是一一对应的 可逆的 编码的定义分类 每个符号序列xi按照固定的码表映射成一个码子yi 这样的码称为分组码 非分组码没有码表 编码的定义 二元码 码符号集为X 0 1 所得码字都是一些二元序列 定长码 等长码和可变长度码 固定长度的码 码中所有码字的长度都相同 是定长码 即ki K i 1 2 n 变长码为一组码字中所有码字的码长各不相同 即任意码字由不同长度的码符号序列组成 奇异码和非奇异码 若信源符号和码字是一一对应的 则该码为非奇异码 即一组码字中所有码字都不相同 即所有信源符号映射到不同的码符号序列 反之为奇异码 即一组码中有相同的码字 唯一可译码 任意有限长的码元序列 只能被唯一地分割成一个个的码字 便称为唯一可译码 或者说码的任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号 非即时码和即时码 如果接收端收到一个完整的码字后 不能立即译码 还需等下一个码开始接收后才能判断是否可以译码 这样的码叫做非即时码 举例 奇异码 惟一可译码 非即时码 是即时码 非奇异码 非惟一可译码 例 码1 显然不是惟一可译码 x2和x4对应于同一码字 11 码1本身是一个奇异码 码2 是非奇异码 不是惟一可译码 当收到一串码符号 01000 时 可将它译成 x4x3x1 也可译为 x4x1x3 x1x2x3 或 x1x2x1x1 等 这种码从单个码字来看虽然不是奇异的 单从有限长的码序列来看 它仍然是一个奇异码 码3 虽然是惟一可译码 但它要等到下一个 1 收到后才能确定码字的结束 译码有延时 码4 既是惟一可译码 又没有译码延时 码字中的符号 1 起了逗点的作用 故称为逗点码 前缀条件码 异前置码 异字头码 逗点码 即时码 非延长码 如果一个码的任何一个码字都不是其它码字的前缀 码4是即时码 信源编码的方法 信源编码有定长和变长两种方法 定长编码 码字长度K是固定的 相应的编码定理称为定长信源编码定理 是寻求最小K值的编码方法 变长编码 K是变值 相应的编码定理称为变长编码定理 这里的K值最小意味着数学期望最小 定长编码定理 定长编码定理 一个熵为H X 的离散无记忆信源X1X2 Xl XL 若对信源长为L的符号序列进行定长编码 设码字是从m个字母的码符号集中 选取K个码元组成Y1Y2 Yk YK 对于任意 0 0只要满足 K L log2m H X 则当L足够大时 必可使译码差错小于 即译码错误概率能为任意小 反之 若 K L log2m H X 2 则不可能实现无失真编码 而当L足够大时 译码错误概率近似等于1 定理中的公式改写成Klog2m LH X 不等式左边表示长为K的码符号序列能载荷的最大信息量 右边代表长为L的信源序列平均携带的信息量 所以定长编码定理告诉我们 只要码字传输的信息量大于信源携带的信息量 总可实现几乎无失真编码 定理的一般性证明是通过计算信源符号自信息的均值与方差 把信源消息分成两个互补集合 一个有编码 一个无编码 再利用契比雪夫不等式 求出有编码集合中码字个数的上下限 分别用上限证明正定理部分 用下限证明逆定理部分 能达到差错率要求 可以证明源序列长度L需满足 信源熵就H X 是一个界限 临界值 当编码器输出的信息率超过这个临界值时 就能无失真译码 否则就不行 信源编码定理从理论上说明了编码效率接近于1 即的理想编码器的存在性 代价是在实际编码时取无限长的信源符号 L 进行统一编码 给定 和 用上式规定的L计算所有可能信源消息的概率 按由小到大的次序排列 选用概率较大的消息进行编码 有编码的消息构成一个集合A 直到该集合的概率p A 1 意味着译码差错概率必小于 即完成了编码过程 只要 足够小 就可实现几乎无失真译码 若 足够小 编码效率就接近于1 说明 定长编码定理是在平稳无记忆离散信源的条件下论证的 但它同样适用于平稳有记忆信源 只是要求有记忆信源的极限熵和极限方差存在即可 对于平稳有记忆信源 定理中的熵应改为极限熵 编码效率定义 最佳编码效率 举例 例 设单符号信源模型为其信息熵为H X 2 55 比特 符号 2 x 1 323若要求编码效率为90 即译码差错率为 10 6 则由此可见 在差错率和效率要求都不苛刻的情况下 就必须有1600多万个信源符号一起编码技术实现非常困难 变长编码定理 1 基本概念 2 码树图 3 克拉夫特不等式 4 变长编码定理 1 基本概念 变长编码 不等长编码允许把等长的消息变换成不等长的码序列 通常把经常出现的消息编成短码 不常出现的消息编成长码 这样可使平均码长最短 从而提高通信效率 代价是增加了编译码设备的复杂度 例如 在不等长码字组成的序列中要正确识别每个长度不同的码字的起点就比等长码复杂得多 译码延时 译码同步 接收到一个不等长码序列后 有时不能马上断定码字是否真正结束 因而不能立即译出该码 要等到后面的符号收到后才能正确译出 2 码树图 m元 m进制树图树根 最顶部画一个起始点 树枝 从根部引出m条线段 每条线段都称为树枝 一级节点 自根部起 通过一条树枝到达的节点 一级节点最多有m个 n级节点 通过n条树枝达到的节点 最多有mn 终节点 终端节点 下面不再有树枝的节点 中间节点 除了树根和终节点以外的节点 联枝 串联的树枝 满树 在码数图中 当每一个码字的串联枝数都相同时 就是定长码 此时的码树称为满树 例如 码长为N的满树的终节点个数为mN 即可表示mN个码字 非满树 有些树枝未用时的码树 非满树构造的就是变长码 如果每一个码字都被安排在终节点上 这种码就是异前置码 三元码树图 树图的特征与编码的对应关系树根码字的起点树枝数码的进制数节点码字或码字的一部分终节点 终端节点码字节数码长满树等长码非满树变长码 3 克拉夫特不等式 克拉夫特不等式 m元长度为ki i 1 2 n的异前置码存在的充要条件是证明 必要条件 设异前置码第i个码字的长度为ki i 1 2 n 构造一个码树图 若某个长度为ki的树枝被选用作码字 则该枝自第ki个节点以后的树枝不能再被选用作码字 这样自ki以后有个码枝不能被选用 而某个ki 是从中任选的一个 那么就整个码树而言 总共不用的枝数为 它一定小于码树的总树枝数 N级满树第N级上的总枝数已知为mN 所以必有 两边除以mN 就得 充分条件如果式成立 总可以把第N级上的树枝分成n组 各组中从第N级开始删除 i 1 2 n 个枝 相对于N级满树 等于删除了所有可能的ki级节点的 在该组中以第ki级节点作为终节点 就构造好了第i个码字 对所有码字如法炮制 则总共删除了所有mN个节点中的 由于 于是构造了一个异前置码 充分性设码字长度满足Kraft不定式 不失一般性 假设取k1级节点中任何一个作为终节点 以C1表示 代表消息a1的码字 由于删去了从C1发出的通向更高层节点的任何分枝 从而相对于N层满树来说删除了所有可能的N层节点的 类似地可以指定一个ki级节点作为ai的码字 将删去满树N层节点的 由于所以这种方式可以一直进行下去 直到选出kn级节点作为的an码字 从而构成了一个异前置码 充分性如果式成立 相当于成立 则总可以把第N级上的树枝分成n组 各组中有个枝 各组分别以第ki节点为终止节点 这样就组成了n个长度分别为ki的码字 由于这n个码字自ki节点后不再被采用 显然它构成了一个异前置码 上面证明了异前置码存在的充分 必要条件 实际上这个充要条件可以进一步推广到比异前置码更大的集合 唯一克译码集合 这里就不再深入讨论 例3 1 1设二进制码树中X x1 x2 x3 x4 K1 1 K2 2 K3 2 K4 3 应用上述判断定理 可得 因此 不存在满足这种Ki的唯一可译码 用树码进行检查如图 树码 所谓信息率最小 就是找到一种编码方式使最小 4 变长编码定理 变长编码定理 举例 变长编码定理 平均码长 变长编码定理 若一离散无记忆信源的平均符号熵为H X 对信源符号进行m元变长编码 一定存在一种无失真编码方法 其码字平均长度满足下列不等式其平均信息率满足不等式H X R H X 式中 为任意正数 证明 设信源符号X x1 x2 xi xn 概率p xi i 1 2 n 对xi用一个长度为ki的码字 使只要规定为正整数时 上式取等号 非整数时 ki取比它大一些的最接近的整数 则满足上式的整数必存在 将上式分别乘以p xi 再对i求和 得 对ki取数学期望就是平均值 故由上面式子可得kilog2m log2p xi 或 对两边求和得码字长度满足克拉夫特不等式 因而是异前置码 多符号情况对于平稳无记忆信源来说 当信源输出的是长度为L的消息序列时 容易证明定理中式子可改进为这时的代表平均码序列长度 已知编码后平均每个信源符号能载荷的最大信息量为 不等长信源编码信源平均输出信息率 证毕 对信源进行变长编码一般所要求的信源符号长度L比定长编码小的多 码的剩余度 编码效率的下界 举例 例 设单符号信源模型为其信息熵为H X 2 55 比特 符号 这里m 2 log2m 1要求 90 则 与定长编码相比 对同一信源 要求编码效率都达到90 时 变长编码只需L 4进行编码 而等长码则要求L大于1 6875 107 用变长编码时 L不需要很大就可以达到相当高的编码效率而且可实现无失真编码 变长编码定理 例1设离散无记忆信源的概率空间为其信源熵为若用二元定长编码 0 1 来构造一个即时码 x1 0 x2 1 这时平均码长编码效率为输出的信息率为R 0 811比特 二元码符号 唯一可译码的判断法首先观察是否是非奇异码 若是奇异码 肯定不是唯一可译码 其次 计算是否满足Kraft不等式 若不满足一定不是唯一可译码 然后将码画成一棵树图 观察是否满足异前置码的树图的构造 若满足则是唯一可译码 或用Sardinas和Patterson设计的判断法 计算分组码中所有可能的尾随后缀集合F 观察F中有没有包含任一码字 若无则为唯一可译码 若有则一定不是唯一可译码 集合F的构造 首先观察码C中最短的码字是否是其它码字的前缀 若是 将其所有可能的尾随后缀排列出 而这些尾随后缀又可能是某些码字的前缀 再将由这些尾随后缀产生的新的尾随后缀列出 然后再观察这些新的尾随后缀是否是某些码字的前缀 再将产生的尾随后缀列出 这样 首先获得由最短的码字能引起的所有尾随后缀 接着 按照上述将次短的码字 等等 所有码字可能产生的尾随后缀全部列出 由此得到码C的所有可能的尾随后缀组成的集合F 练习 有一信源 它有六个可能的输出 其概率分布如下表所示 表中给出了对应的码A B C D E和F 求这些码中哪些是唯一可译码 求哪些码是即时码 对所有唯一可译码求出其平均码长 几种编码方法 1 香农编码2 费诺编码3 哈夫曼编码 1 最佳编码 最佳码 定义 能载荷一定的信息量 且码字的平均长度最短 可分离的变长码的码字集合 1 香农编码方法香农第一定理指出 选择每个码字的长度 K i 满足下式I xi Ki I xi 1 就可以得到这种码 这种编码方法称为香农编码 编码方法如下 1 将信源消息符号按其出现的概率大小依次排列 p x1 p x2 p xn 2 确定满足下列不等式的整数码长Ki 3 为了编成唯一可译码 计算第 i 个消息的累加概率 4 将累加概率 Pi 变换成二进制数 5 取 Pi 二进数的小数点后 Ki 位即为该消息符号的二进制码字 2 费诺编码方法 编码过程如下 1 将信源消息符号按其出现的概率大小依次排列 p x 1 p x 2 p x n 2 将依次排列的信源符号按概率值分为两大组 使两个组的概率之和近于相同 并对各组赋予一个二进制码元 0 和 1 3 将每一大组的信源符号进一步再分成两组 使划分后的两个组的概率之和近于相同 并又赋予两个组一个二进制符号 0 和 1 4 如此重复 直至每个组只剩下一个信源符号为止 5 信源符号所对应的码字即为费诺码 3 哈夫曼编码方法 编码过程如下 1 将 n 个信源消息符号按其出现的概率大小依次排列 p x1 p x2 p xn JZ 2 取两个概率最小的字母分别配以0和1两码元 并将这两个概率相加作为一个新字母的概率