第三章无失真离散信源编码.ppt

第三章无失真离散信源编码 1 3 1基本概念 信源编码器 信道基本符号 0 1 N个消息集合X a b c z 空格 N个代码组集合C c1 c2 cN 例1 2 3 1基本概念 一 信源编码的定义 信源编码是以提高通信的有效性为目的编码 信源编码 适合信道传输 减少冗余度 3 3 1基本概念 编码器模型 由于信源编码可以不考虑抗干扰问题 所以它的数学模型比较简单 4 3 1基本概念 编码器模型 输入是信源符号集 x为编码器所用的编码符号集 包含r个元素 称为码符号 码元 由码符号组成的输出序列称为码字 其长度称为码字长度或码长 全体码字的集合C称为码或码书 编码器将信源符号集中的信源符号 或长为N的信源符号序列 变成由码符号组成的长为的与信源符号一一对应的输出序列 即 若要实现无失真编码 必须这种映射是一一对应的 可逆的 5 3 1基本概念 二 信源编码的分类 1 二元码和r元码若码符号集 编码所得码字为一些适合在二元信道中传输的二元序列 则称二元码 二元码是数字通信与计算机系统中最常用的一种码 若码符号集共有r个元素 则所得之码称为r元码 6 3 1基本概念 二 信源编码的分类 2 基本源编码和N次扩展源编码 3 无失真编码和有失真编码数学上称为非奇异码和奇异码 若信源符号和码字是一一对应的 则该码为非奇异码 反之为奇异码 4 惟一可译码和非惟一可译码若任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列 则此码称为惟一可译码 或称单义可译码 否则就称为非惟一可译码或非单义可译码 若要使某一码为惟一可译码 则对于任意给定的有限长的码符号序列 只能被惟一地分割成一个个的码字 7 3 1基本概念 二 信源编码的分类 例如 对于二元码 当任意给定一串码字序列 例如 10001101 只可唯一地划分为1 00 01 1 01 因此是惟一可译码 而对另一个二元码 当码字序列为 01001 时 可划分为0 10 01或01 0 01 所以是非惟一可译的 8 3 1基本概念 二 信源编码的分类 5 定长码和变长码 若一组码中所有码字的长度都相同 即 则称为等长码 9 二 信源编码的分类 例2 设信源符号集为 a b c d 采用6种分组编码如下表 分析每一个码的唯一可译性 非奇异唯一可译 10 ba c 等长 10 3 2离散无失真信源编码定理 一 香农理论对数据压缩的指导意义 1 数据压缩的途径途径一 使序列中的各个符号尽可能地互相独立 即解除相关性 去冗余 途径二 使编码中各个符号出现的概率尽可能地相等 即概率均匀化 2 数据压缩的理论极限 11 3 2离散无失真信源编码定理 二 编码的指标 1 平均码长设信源有N个单符号消息x1 x2 xN 变长码编码器输出的代码组长度对应为l1 l2 lN 其出现概率分别为P s1 P s2 P sN 则该变长码的平均长度为 Code sign 12 3 2离散无失真信源编码定理 二 编码的指标 2 编码后的信息传输率 1 等长码的信息传输速率 对单符号离散信源 设其信源熵为H X 对其进行等长编码 每码字l个码元 故其信息传输速率为R H X l 2 变长码的信息传输速率 对单符号离散信源 设其信源熵为H X 对其进行等长编码 每码字l个码元 故其信息传输速率为 bit code bit code 13 3 2离散无失真信源编码定理 二 编码的指标 3 编码效率 信源编码器输出代码组的信息传输速率与信道容量之比 称为信源编码器的编码效率 即 14 3 2离散无失真信源编码定理 三 如何引出定长编码定理和不定长编码定理 例1 设离散无记忆信源概率空间为 信源熵 H X 1 4log4 3 4log3 4 0 811bit 信源符号 若用二元定长编码 0 1 来构造一个即时码 平均码长 二元码符号 信源符号 编码效率 输出的信息传输率 bit code 15 3 2离散无失真信源编码定理 三 如何引出定长编码定理和不定长编码定理 再对长度L为2的信源序列进行 变长编码 其即时码如表 码字平均长度 单个符号的平均码长 编码效率 输出的信息传输率 R2 0 961bit 二元码符号 16 3 2离散无失真信源编码定理 三 如何引出定长编码定理和不定长编码定理 编码复杂一些 但信息传输率有了提高 定长编码 要求编码效率达到96 时 允许译码错误概率 10 5 17 3 2离散无失真信源编码定理 18 3 2 1定长编码定理 19 3 2 1定长编码定理 定理中的公式改写成不等式左边表示长为L的码符号序列能载荷的最大信息量 右边代表长为N的信源序列平均携带的信息量 所以定长编码定理告诉我们 只要码字传输的信息量大于信源携带的信息量 总可实现几乎无失真编码 20 例题 结论 定长编码简单 但要达到一定的差错率不易实现 且编码效率低 21 对离散无记忆信源 消息长度为N 符号熵为H S 对信源进行r元变长编码 一定存在无失真的信源编码方法 变长编码定理 2 码字平均长度不能小于极限值 否则唯一可译码不存在 定理给出平均码长的上界 但并不是说大于上界不能构成唯一可译码 而是我们希望尽可能短 定理给出紧致码的最短平均码长 并指出这个最短的平均码长与信源熵是有关的 22 23 如何分离码字 变长编码出现的问题 要求 码是唯一可译 24 3 2 3码字唯一可译条件 25 判断以下码字是否可分离 例3 2 2 26 3 2 3码字唯一可译条件 即时码的一种简单构造方法是树图法 对于给定码字的全体集合C 可用码树来描述它 所谓树 既有根 枝 又有节点 图中最上端A点为根 从根出发向下伸出树枝 树枝的数目等于码符号的总数r 树枝的尽头为节点 从节点出发再伸出树枝 每次每个节点伸出r枝 依次下去构成一棵树 27 3 2 3码字唯一可译条件 在下图中 当某一个节点被安排为码字后 就不再继续伸枝 此节点称为终端节点 用粗黑点表示 其他节点称为中间节点 不安排为码字 用空心圈表示 给每个节点所伸出的树枝分别从左向右标上码符号0 1 r 28 3 2 3码字唯一可译条件 任一即时码都可用树图法来表示 当码字长度给定时 即时码不是唯一的 在每个节点上都有r个分枝的树称为整树 满树 否则称为非整树 非满树 当元节的码树的所有树枝都被用上时 第阶节点共有个终端节点 正好对应于长度为的等长码 可见等长码也是即时码的一种 29 即时码的树图结构 树与编码的关系树根 码的起点树枝 码的进制数节点 码字或其部分终结点 码字节数 码长满树 等长码非满树 变长码 3 2 3码字唯一可译条件 30 克拉夫特不等式 r元长度为li的异前置码存在的充要条件是 3 2 3码字唯一可译条件 31 3 2 3码字唯一可译条件 Kraft不等式是惟一可译码存在的充要条件 必要性表现在如果码是惟一可译码 则必定满足Kraft不等式 充分性表现在如果满足Kraft不等式 则这种码长的惟一可译码一定存在 但并不表示所有满足Kraft不等式的码一定是惟一可译码 因此 克拉夫特不等式是惟一可译码存在的充要条件 而不是惟一可译码的充要条件 32 3 2 3码字唯一可译条件 例 设二进制码树中X 对应的 由上述定理 可得因此不存在满足这种码长的唯一可译码 33 3 2 3码字唯一可译条件 1 01 001 000 惟一可译码 1 01 101 000 不是惟一可译码 均满足克劳夫特不等式 34 3 2 3码字唯一可译条件 注意 不满足克拉夫特不等式的码 一定不是唯一可译码 码长满足克拉夫特不等式的码 也不一定是唯一可译码 克拉夫特不等式只是说明唯一可译码是否存在 并不能作为一种码制是否是唯一可译码的判断依据 35 3 3香农编码 设有离散无记忆信源 36 1 2 3 4 香农编码方法的步骤 按信源符号的概率从大到小的顺序排队 计算各信源符号的自信息量 编码码长应该大于自信息量 5 累加概论二进制化 取给定码长 得到编码码字 37 38 香农编码 例 有一单符号离散无记忆信源 39 香农码的平均码长 信源熵 编码效率 为提高编码效率 可把x4x5换成前面的节 点 可减小平均码长 不应先规定码长 而是由码树来规定码 字 可得更好的结果 L 书例3 3 1 3 3香农编码 40 编码过程 1 码字 41 3 3香农编码 42 3 4费诺编码 对概率按r进行分组 使每组概率尽可能相等 给每个分组分配一个码元 对每个分组重复2 3步 直到不可分为止 1 2 3 4 43 概率匹配 44 3 4费诺编码 L 45 3 4费诺编码特点 1 费诺编码在构造码树时 是从树根开始到终端节 点结束 2 由于赋码元时的任意性 因此编出的码字不唯一 3 费诺编码虽属于概率匹配范畴 但并未严格遵守 匹配规则 有时出现概率小的码长反而小 因此 平均码长一般不会最小 费诺码比较适合于每次分组概率都很接近的信源 特 别是对每次分组概率都相等的信源进行编码时 可达 到理想的编码效率 46 例 对该信源进行二 进制费诺编码 平均码长 编码效率 设有一单符号离散无记忆信源 试对该信源编二进制费诺码 书例3 4 1 3 4费诺编码 47 编码过程 48 可以看出本例中费诺码有较高的编码效率 费诺码比较适合于每次分组概率都很接近的信源 3 4费诺编码 49 树图 50 将信源符号按概率由大到小顺序排队 给两个概率最小的符号各分配一个码位 将其概率相加后合并作为一个新的符号 与剩下的符号一起 再重新排队 给缩减信源中概率最小的符号各分配一个码元 重复步骤2 3直至概率和为1 2 1 4 3 3 5赫夫曼编码 51 从最后一级开始 向前返回得到各个信源符号所对应的码元序列 即相应的码字 5 52 例 试对该信源编二进制哈夫曼码 读取码字的时候 要从后向前读 此 时编出来的码字是可分离的即时码 53 平均码长 信源熵 H X H 0 2 0 19 0 18 0 17 0 15 0 1 0 01 2 61bit 符号 编码效率 L 54 1 哈夫曼编码在构造码树时 是从端点开始直到树 根结束 2 哈夫曼编码采用概率匹配方法来决定各码字长度 概率大的符号对应于短码 概率小的符号对应与长 码 充分利用了短码 从而使平均码长最小 3 哈夫曼编码时 缩减信源的最后二个码字总是最 后一位不同 从而保证了哈夫曼码是即时码 3 5赫夫曼编码特点 设有一单符号离散无记忆信源 试对该信源编二进制哈夫曼码 书例3 5 1 55 编码过程 56 57 58 Huffman码的编码方法不是唯一的首先 每次对缩减信源两个最小的符号分配 0 和 1 码元试任意的 其次 若合并后的新符号的概率与其他符号的概率相等 这几个符号的次序可任意排列 一般将合并的概率放在上面 这样可获得较小的码方差 说明 59 例设有离散无记忆信源 用两种不同的方法对其编二进制huffman码 60 方法一 方法二 61 两种不同的编码方法得到的码字和码长的对比 62 平均码长和编码效率 63 码字的码长方差比较 64 可以看出第二种编码方法的码长方差要小许多 码长变化较小 比较接近平均码长 要求 Huffman编码时应使合并的信源符号位于缩减信源序列尽可能高的位置上 码长变化较小 比较接近平均码长 易于实现 结论 65 66 3 5赫夫曼编码 m进制哈夫曼编码 在编m进制哈夫曼码时 为了使短码得到充分利用 使平均码长最短 必须使最后一步的缩减信源有m个 信源符号 缩减次数 每次缩减所减少 的信源符号个数 信源符号数n应满足 不满足时 设q个概率为0的信源符号 使q n满足要求 第一次对最小概率符号分配码元时只取 m q 个 分别 配以0 1 m q 1 把这些符号的概率相加作为一个新 符号的概率 与其它符号一起重新排列 以后每次取 m个符号 分别配以0 1 m 1 如此下去 直至所有 概率相加得1为止 即得到各符号的m进制码字 67 3 5赫夫曼编码 m进制哈夫曼编码 例 试对该信源编三进制哈夫曼码 m 3 n 8 无法满足n s m 1 m s 3 q 1 q n s m 1 m 第一次取m q 2个符号进行编码 68 3 5赫夫曼编码 m进制哈夫曼编码 69 3 5赫夫曼编码 m进制哈夫曼编码 平均码长 编码效率 L 70 简单讨论 空格 0 2E 0 105T 0 072O 0 0654A 0 063N 0 059I 0 055R 0 054S 0 052H 0 047D 0 035L 0 029C 0 023F U 0 025M 0 021P 0 175Y W 0 012G 0 011B 0 0105V 0 008K 0 003X 0 002J Q 0 001Z 0 001 英文各个字符的统计概率如下 71 简单讨论 1 编码效率 Shannon码 码长 3 11 平均码长 4 602bit sym 效率 0 895Fano码 码长 3 11 平均码长 4 168bit sym 效率 0 989Huffman码 码长 3 10 平均码长 4 156bit sym 效率 0 992 2 编码思路 Shannon码 自信息Fano码 等概划分Huffuman码 从概率最小的符号开始 三种编码的比较 Huffman 不唯一 但对信源没有特殊要求 且编码效率较高 设备要求简单 综合性能优于另外两种 相同点 三种编码都考虑了信源的统计特性 使经常出现的信源符号对应较短的码字 使平均码长缩短 实现了信源压缩 不同点 shannon 有唯一的编码 但编码效率不是很高 Fan