第5(8)章无失真信源编码定理(OK).ppt

第5章无失真信源编码定理 5 1信源编码概论 5 2码的唯一可译性 5 3等长编码定理和等长编码方法 5 5变长编码方法 5 4变长编码定理 香农第一定理 5 1信源编码概论 基本概念 传输之前的两次变换 信源编码 信道编码 传输之后的两次反变换 变换与反变换是成对出现的 讨论无失真信源编码可以先不考虑抗干扰问题 因此 图中虚框部分可近似地视为一个等效的无噪信道 这一点是我们讨论信源编码的前提 1 基本概念 信源编码分类 无失真编码 有失真编码 无失真编码 只对信源的冗余度进行压缩 不会改变信源的熵 又称冗余度压缩编码 它能保证码元序列经译码后能无失真地恢复成信源符号序列 有失真编码 又称熵压缩编码 将在第7章讨论 无失真信源编码的作用 1 符号变换 使信源的输出符号与信道的输入符号相匹配 2 冗余度压缩 使编码之后的新信源概率分布均匀化 信息含量效率等于或接近于100 5 1信源编码概论 基本概念 5 1信源编码概论 编码器模型 信源编码 一一对应的变换 基本概念 码长li 等长码 变长码 平均码长 码长li 码字wi所含码元的个数 单位 码元 符号 r进制单位 符号 等长码 FLC FixedLengthcode 码中所有码字均有相同的码长l 否则称为变长码 VLC VariableLengthcode 平均码长 码元 符号 定长码 平均码长是衡量码的性能的重要参数 平均码长小 说明平均一个码元所携带的信息量大 信息的冗余就小 5 1信源编码概论 编码器模型 码元 符号 变长码 例 编码 设一信源的概率空间为 对其单个符号进行二进制编码 码元 符号 码元 符号 编码策略 经常出现 概率大 的符号采用较短的码字 不经常出现 概率小 的符号采用较长的码字 编码策略 采用等长的码字 3 编码器的输出 f是一一对应的映射 新信源X 编码后的信道的信息传输率R 平均每个码元携带的信息量 平均码长越小 每个码元携带的信息量就越多 传输一个码元就传输了较多的信息 5 1信源编码概论 4 编码效率 为了衡量编码效果 定义编码效率 编码后的实际信息率与编码后的最大信息率之比 注 编码效率实际上也是新信源X的信息含量效率或熵的相对率 新信源的冗余度也是码的冗余度 5 1信源编码概论 5 2码的唯一可译性 f为一一对应的变换只是无失真编码的必要条件 并不充分 要保证将码元序列无失真地恢复成信源符号序列 还要求编出的码自身具有独特的结构 有实用价值的码应该具有唯一可译性 即能从码字序列 也是码元序列 唯一地恢复成信源符号序列 1 唯一可译码 UDC UniquelyDecodableCode 唯一可译码 UDC 该码的码字组成的任意有限长码字序列都能恢复成唯一的信源序列 否则称为非唯一可译码 码是唯一可译码的充分必要条件是 由码中的码字组成的任意有限长的码字序列 也是码元序列 都能唯一划分成一个个的码字 且任一码字只与唯一一个信源符号对应 奇异码 含相同码字的码称奇异码 否则称为非奇异码 5 2码的唯一可译性 即时码 在惟一可译变长码中 有一类码 它在译码时无需参考后续的码符号就能立即做出判断 译成对应的信源符号 则这类码称为即时码 前缀条件码 码中任一完整码字都不是另一码字的前缀 该码也称异前置码或非延长码 此码为即时码 例题 5 2码的唯一可译性 W3 变长非奇异码 但不是UDC W5 变长码 非奇异码 延长码 是UDC W4 变长码 非奇异码 是UDC 例题 W1 等长非奇异码 是UDC W2 等长奇异码 不是UDC 等长非奇异码一定是惟一可译码 5 2码的唯一可译性 惟一可译码的判断方法 P182 将码中所有码字可能的尾随后缀组成一个集合F 当且仅当集合F中没有包含任一码字 则可判断此码为惟一可译码 5 2码的唯一可译性 2 码树 W1 00 01 10 11 W4 0 10 110 111 W5 0 01 011 111 5 2码的唯一可译性 码树从树根开始向上长出树枝 树枝代表码元 树枝与树枝的交点叫做节点 r进制码树 码元个数为r 各节点 含树根 向上长出的树枝数不大于r l阶节点 经过l根树枝才能到达的节点 终端节点或端点 向上不长出树枝的节点 码字 与码树上的节点对应 组成该码字的码元就是从树根开始到该节点所经过的树枝 或码元 非延长码 所有码字均处于终端节点 即端点上 整树 r进制码树各节点 包括树根 向上长出的树枝数均等于r 5 2码的唯一可译性 不满足Kraft不等式的码肯定不是非延长码 满足Kraft不等式的码也不一定是非延长码 根据满足Kraft不等式的码长集合可构造出一个非延长码 上述定理对唯一可译码仍然成立 即时码存在性定理 对于任一进制即时码 各码字的码长为则必定满足Kraft不等式 反过来 若上式成立 就一定能构造一个进制即时码 5 2码的唯一可译性 Kraft不等式 5 3等长编码定理和等长编码方法 1 对信源输出的符号序列进行编码 对信源U的单个符号进行编码 对信源U的N长符号串进行编码 对扩展信源UN的单个符号进行编码 2 等长编码定理 r进制定长编码 码长为lN 可用的码字数目 唯一可译 5 3等长编码定理和等长编码方法 等长无失真编码定理 用r元符号对离散无记忆信源U的N长符号序列进行定长编码 N长符号序列对应的码长为lN 若对于任意小的正数 有不等式就几乎能做到无失真编码 且随着序列长度N的增大 译码差错率趋于0 反过来 若就不可能做到无失真编码 且随着N的增大 译码差错率趋于1 5 3等长编码定理和等长编码方法 3 等长编码方法 例 对U的单个符号进行2进制编码 码元集 X 0 1 取l 3 bit 符号 码元 符号 提高编码效率的方法 对符号串进行编码 同时引入一定的失真 5 4变长编码定理 香农第一定理 5 5变长编码方法 变长编码采用非延长码 力求平均码长最小 此时编码效率最高 信源的冗余得到最大程度的压缩 对给定的信源 使平均码长达到最小的编码方法称为最佳编码 编出的码称为最佳码 三种变长编码方法 霍夫曼编码 费诺编码以及香农编码 霍夫曼编码是真正意义下的最佳编码 1 霍夫曼编码 二进制霍夫曼编码过程如下 1 将信源符号按概率大小排序 2 对概率最小的两个符号求其概率之和 同时给两符号分别赋予码元 0 和 1 3 将 概率之和 当作一个新符号的概率 与剩下符号的概率一起 形成一个缩减信源 再重复上述步骤 直到 概率之和 为1为止 4 按上述步骤实际上构造了一个码树 从树根到端点经过的树技即为码字 5 5变长编码方法 2进制霍夫曼编码 码元集 X 0 1 非延长码 平均码长最小 码字不唯一 霍夫曼编码的基本特点 编出的码是非延长码 霍夫曼编码实际上构造了一个码树 码树从最上层的端点开始构造 直到树根结束 最后得到一个横放的码树 平均码长最小 霍夫曼编码采用概率匹配方法来决定各码字的码长 概率大的符号对应于短码 概率小的符号对应于长码 码字不唯一 每次对概率最小的两个符号求概率之和形成缩减信源时 就构造出两个树枝 由于给两个树枝赋码元时是任意的 码字不唯一 等长编码与变长编码冗余压缩效果比较 等长编码 变长编码 码元 符号 码元 符号 bit 符号 bit 符号 bit 符号 2进制霍夫曼编码 码元集 X 0 1 bit 符号 r进制霍夫曼编码 每次求缩减信源时 求r个最小概率之和 即将个概率最小的r符号缩减为一个新符号 直到概率之和为1终止 新问题 缩减到最后时剩下不到r个符号了 为保证平均码长最小 希望缩减到最后刚好还剩下r个符号 为达到此目的 可给信源添加几个无用的符号 概率为0的符号 使得信源符号数q满足 q r 1 r 信源缩减的次数 3进制霍夫曼编码 码元集 X 0 1 2 bit 符号 符号串的霍夫曼编码 例 对如下DMS进行2进制霍夫曼编码 分别对单个符号和二元符号串进行编码 bit 符号 码元 符号 对单个符号进行编码 码元 符号 对二元符号串进行编码 2 费诺 Fano 编码 费诺 Fano 编码也是构造一个码树 因此 编出的码是非续长码 但不一定是最佳码 费诺编码步骤 以二进制编码为例 1 将信源符号按概率从大到小的排序 2 将信源符号分成2组 使2组信源符号的概率之和近似相等 并给2组信源符号分别赋码元 0 和 1 3 接下来再把各小组的信源符号细分为2组并赋码元 方法与第一次分组相同 4 如此一直进行下去 直到每一小组只含一个信源符号为止 5 由此即可构造一个码树 所有终端节点上的码字组成费诺码 2进制费诺编码 码元集 X 0 1 码元 符号 bit 符号 概率大 则分解的次数少 概率小 则分解的次数多 这符合最佳编码原则 码字集合是唯一的 分解完了 码字出来了 码长也有了 因此 费诺编码方法又称为子集分解法 费诺编码方法比较适合于每次分组概率都很接近的信源 特别是对每次分组概率都相等的信源进行编码时 可达到理想的编码效率 费诺编码特点 3 香农编码 设离散无记忆信源二进制香农码的编码步骤如下 将信源符号按概率从大到小的顺序排列 为方便起见 令p x1 p x2 p xn 令p x0 0 用pa xj j i 1表示第i个码字的累加概率 则 3 香农编码 确定满足下列不等式的整数ki 并令ki为第i个码字的长度 log2p xi ki 1 log2p xi 将pa xj 用二进制表示 并取小数点后ki位作为符号xi的编码 1 某信源具有7个消息符号 其概率分别为 0 20 0 19 0 18 0 17 0 15 0 10 0 01 欲对其进行香农方法的二进制编码 求其二进制代码组及其编码效率 解 先计算每一个码字的码长 分别为 3 3 3 3 3 4 7 再计算累加概率 例如 P4 p1 p2 p3 0 20 0 19 0 18 0 57 变换成二进制数为 0 1001 因为b4 3 故对于概率为0 17的消息符号x4 其编码为100 依此类推 与本题有关的数据和编码结果列于下表 例题 例题 可以求出其平均码长和信源熵分别为3 14码元 符号和2 16比特 符号 故其信息传输速率为同样 本题也是二进制信道 信道容量C 1比特 码元时间 故其编码效率在数值上等于信息传输速率 即 83 1 上述两个例子可见 香农编码方法对有的信源能够达到最佳编码而有的则不能 因此还不能说它是最佳编码 例题 香农编码方法特点 由于bi总是进一取整 香农编码方法不一定是最佳的 由于第一个消息符号的累加概率总是为0 故它对应的码字总是0 00 000 0 0的式样 码字集合是唯一的 且为即时码 先有码长再有码字 对于一些信源 编码效率不高 冗余度稍大 因此其实用性受到较大限制 3 香农编码 游程 指的是字符序列中各个字符连续重复出现而形成字符串的长度 又称游程长度或游长 编码方法 首先测定 0 游程长度和 1 游程长度的概率分布 即以游程长度为元素 构造一个新的信源 对新的信源 游程序列 进行哈夫曼编码 4 二元游程编码 其中为 0 游程长度的霍夫曼编码效率 为 1 游程长度的霍夫曼编码效率 4 二元游程编码 游程长度概率 二元序列的编码效率 游程变换减弱了原序列符号间的相关性 游程变换将二元序列变换成了多元序列 这样就适合于用其他方法 如哈夫曼编码 进一步压缩信源 提高通信效率 多元序列也可以变换成游程序列 如m元序列可有m种游程 但是变换成游程序列时 需要增加标志位才能区分游程序列中的 长度 是m种游程中的哪一个的长度 否则 变换就不可逆 这样 增加的标志位可能会抵消压缩编码得到的好处 所以 对多元序列进行游程变换的意义不大 4 二元游程编码 1 一个信源包含6个符号消息 它们的出现概率分别为0 3 0 2 0 15 0 15 0 1 0 1 信道基本符号为二进制码元 试用哈夫曼编码方法对该信源的6个符号进行信源编码 并求出代码组的平均长度和信息传输速率 解根据哈夫曼编码的步骤 可得其编码过程和编码结果 如下图所示 习题1 习题1 由编码结果 求得平均码长为 2 5码元 符号信源熵为信息传输速率为由此可得其编码效率为98 8 接近于最佳编码 习题1 习题2 2 信源符号X有8种消息 概率为 1 2 1 4 1 8 1 16 1 32 1 64 1 128 1 128 1 求符号熵H X 2 用香农编码编成二进变长码 计算其编码效率 3 用费诺编码编成二进变长码 计算其编码效率 4 用费诺编码编成三进变长码 计算其编码效率 5 用哈夫曼编码编成二进变长码 计算其编码效率 6 用哈夫曼编码编成三进变长码 计