信息论与编码第五章.ppt

第5章无失真信源编码 5 1编码的定义 5 2定长编码定理 5 3编码器变长码定理 5 4最佳编码 将信源信息通过信道传送给信宿 怎样才能做到尽可能不失真而又快速呢 这就需要解决两个问题 第一 在不失真或允许一定失真的条件下 如何用尽可能少的符号来传送信源信息 第二 在信道受干扰的情况下 如何增加信号的抗干扰能力 同时又使得信息传输率最大 为了解决这两个问题 就要引入信源编码和信道编码 信源编码 在不失真或允许一定失真条件下 如何用尽可能少的符号来传送信源信息 以便提高信息传输率 在通信中要求精确的复现信源的输出 就要保证信源产生的全部信息无损的传送给信宿 这时的信源编码就是无失真信源编码 5 1编码的定义 5 1 1信源编码的定义 编码实质上是对信源的原始符号按一定的数学规则进行的一种变换 说明 1 输出的码符号序列称为码字 2 长度l称为码字长度或简称码长 3 编码就是从信源符号到码符号的一种映射 4 若要实现无失真编码 则这种映射必须是一一对应的 并且是可逆的 二元信道的基本符号集为 0 1 若将信源通过一个二元信道传输 就必须把信源符号变换成由0 1符号组成的码符号序列 即编码 可用不同的码符号序列 如表 若把N次无记忆扩展信源的概念加以引申 便可得到N次扩展码 5 1 2信源变码的分类 等长码 码中所有码字的长度都相同 变长码 码中的码字长短不一 定义5 1将信源符号集中的每个信源符号映射成一个固定的码字 这样的码称为分组码 采用分组编码方法 需要分组码具有某些属性 以保证在接受端能够迅速准确地将码译出 下面首先讨论分组码的一些直观属性 1 奇异码和非奇异码 若信源符号和码字是一一对应的 则该码为非奇异码 反之为奇异码 2 唯一可译码 若码的任意一串有限长的码符号序列只能唯一地被译成所对应的信源符号序列 则此码称为唯一可译码 否则就称为非唯一可译码 唯一可译码 码 码 即时码 无须考虑后续的码符号即可从码符号序列中译出码字 这样的唯一可译码称为即时码 设为一个码字 对于任意的 码符号序列的前j个元素为码字Wi的前缀 一个唯一可译码成为即时码的充分必要条件是其中任何一个码字都不是其他码字的前缀 码树 表示各码字的构成 A 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 二进制码树 2 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 三进制码树 树根 码字的起点 分成r个树枝 码的进制数 终端节点 码字1101 中间节点 码字的一部分 节数 码长 满树 每个节点上都有r个分枝的树 等长码非满树 变长码用树的概念可导出唯一可译码存在的充分和必要条件 综上所述 可将码作如下分类 定理5 1对于码符号为X x1 x2 xr 的任意唯一可译码 其码字为W1 W2 Wq 所对应的码长为l1 l2 lq 则必定满足克拉夫特不等式 注意 克拉夫特不等式只是说明唯一可译码是否存在 并不能作为唯一可译码的判据 例5 1 设二进制码树中X x1 x2 x3 x4 对应的l1 1 l2 2 l3 2 l4 3 由上述定理 可得 因此不存在满足这种码长的唯一可译码 5 1 3唯一可译码的判断法 变长 1 观察码C中最短的码字是否是其它码字的前缀 若是 将其所有可能的尾随后缀排列出 而这些尾随后缀又有可能是某些码字的前缀 再将这些尾随后缀产生的新的尾随后缀列出 2 再观察这些新的尾随后缀是否是某些码字的前缀 再将产生的尾随后缀列出 依此下去 直到没有一个尾随后缀是码字的前缀为止 3 这样 首先获得了由最短的码字能引起的所有尾随后缀 接着 按照上述步骤将次短码字 等等所有码字可能产生的尾随后缀全部列出 由此得到由码C的所有可能的尾随后缀的集合F 当且仅当集合F中没有包含任一码字 则可判断此码C为唯一可译码 5 2定长码编码定理 编码的目的 就是要是信源的信息率最小 也就是说 要用最少的符号来代表信源 在定长编码中 对每一个简单信源 码字的长度都是定值 要实现无失真的信源编码要求 信源符号s1s2 sq是一一对应码字W1W2 Wq 能够无失真或无差错地从W恢复 也就是能正确地进行反变换或译码 传送Y时所需要的信息率最小 如果对一个简单信源S进行定长编码 那么信源S存在惟一可译码的条件是 q是信源S的符号个数 r是信道基本码符号数 l是定长码的码长 如果对信源S的N次扩展信源SN进行定长编码 若要编得的定长码是惟一可译码 则须满足 对上式两边取对数 有 表示SN中平均每个原始信源符号所需要的码符号个数 对于定长唯一可译码 平均每个原始信源符号至少用个码符号来变换 例如英文电报有32个符号 即 采用二元编码时 则 对信源每个符号进行二元编码 则 也就是说 每个英文电报符号至少要用5位二元符号进行编码才能得到唯一可译码 定理5 2设离散无记忆信源 的熵为H S 其N次扩展信源为 次扩展信源熵 现在用码符号集X x1 x2 xr 对N次扩展信源SN进行长度为l的定长编码 对于 只要满足则当N足够大时 必可使译码差错小于 反之 若则当N足够大时 译码错误概率趋于1 定义5 2设熵为H S 离散无记忆信源 若对信源的长为N的符号序列进行定长编码 设码字是从r个码符号集中选取l个码元构成 定义R为编码速率 单位 bit 符号 即 此时若则可以实现无失真传输 定义5 3 2称为编码效率 则有 设差错概率为 当和均为定值时 只要N足够大 均为定值时 只要N足够大 即 例5 1 设离散无记忆信源概率空间为 信源熵为 自信息方差为 对信源符号采用定长二元编码 要求编码效率 无记忆信源有 因此 可以得到 如果要求译码错误概率 因此 一般说来 当N有限时 高传输效率的定长码往往要引入一定的失真和译码错误 解决的办法是可以采用变长编码 5 3变长码定理 5 3 1码平均长度 定义5 4 1设有信源 编码后的码字为W1 W2 Wq 其码字相应的码长分别为l1 l2 lq 因是惟一可译码 信源符号si和码字Wi一一对应 则这个码的平均长度为 表示每个信源符号编码对平均需用的码符号个数 单位 码符号 信源符号 当信源S给定 信源的熵为H S 则每个信道码元所携带的平均信息量可以表示为 传输一个码符号平均需要t秒时间 则编码后信道每秒传输的信息量 单位 bit s 定义5 5对应一给定的信源和一给定的码符号集 若有一种惟一可译码 其平均码长小于所有其他唯一可译码 则称这种码为紧致码 或最佳码 定理5 3设离散无记忆信源 若该离散无记忆离散信源的符号熵为H S 每个信源符号的用具r进制码元进行定长编码 一定存在一种无失真编码方法 其码字平均码长满足 5 3 2离散平稳无记忆序列变长编码定理 香农第一定理 定理5 4设离散无记忆信源 的熵为H S 其N次扩展信源为 现在用码符号集X x1 x2 xr 对N次扩展信源SN进行编码 总可以找到一种编码方法 构成惟一可译码 使信源S中的每个信源符号所需的码字平均长度满足 或且当N 时 则 号si所对应的平均码长 定义5 7编码效率定义为 表示离散无记忆信源S中的每个信源符 定义5 6变长编码的编码速率定义为 它表示编码后平均每个信源符号能载荷的最大信息量 于是 定理5 4又可表述为 其中 L为平均码长 此处L 故编码效率一定小于或等于1的数 定义5 4 3对于变长码 定义码的剩余度为 例5 4 设离散无记忆信源的概率空间为 其信源熵为 比特 符号 若用二元定长编码 0 1 来构造一个即时码 这时平均码长 二元码符号 信源符号 编码效率为 输出的信息率为 比特 二元码符号 再对长度为2的信源序列进行变长编码 其即时码如下表所示 这个码得码字平均长度 二元码符号 信源符号 每一单个符号的平均码长 二元码符号 信源符号 其编码效率 用同样的方法可进一步将信源序列的长度增加 L 3或L 4 对这些信源序列X进行编码 并求出其编码效率为 这时信息传输率分别为 如果对这一信源采用定长二元码编码 要求编码效率达到96 时 允许译码错误概率自信息的方差 10 5 2 0 4715 所需要的信源序列长度 4 13 107 5 4最佳编码 紧致码 香农 费诺 霍夫曼 香农码 费诺码 霍夫曼码都考虑了信源的统计特性 使经常出现的信源符号对应较短的码字 使信源的平均码长缩短 从而实现了对信源的压缩 香农码有系统的 惟一的编码方法 但在很多情况下编码效率不是很高 费诺码和霍夫曼码的编码方法都不惟一 费诺码比较适合于对分组概率相等或接近的信源编码 费诺码也可以编m进制码 但m越大 信源的符号数越多 可能的编码方案就越多 编码过程就越复杂 有时短码未必能得到充分利用 霍夫曼码对信源的统计特性没有特殊要求 编码效率比较高 对编码设备的要求也比较简单 因此综合性能优于香农码和费诺码 1 香农 Shannon 编码 1 将信源消息符号按其出现的概率大小依次排列 2 确定满足下列不等式的整数码长Ki 3 为了编成唯一可译码 计算第i个消息的累加概率 4 将累加概率Pi变换成二进制数 5 取Pi二进数的小数点后Ki位即为该消息符号的二进制码字 例5 4设信源共7个符号消息 a1 a2 a3 a4 a5 a6 a7 概率分别为0 20 0 19 0 18 0 17 0 15 0 10 0 01 求香农编码 信源熵 信源符号的平均码长为 编码效率为 香农编码方法特点 由于ki总是进一取整 香农编码方法不一定是最佳的 码字集合是惟一的 且为即时码 先有码字的长度再有码字 对于一些信源 编码效率不高 多余度稍大 因此其实用性受到较大限制 2 费诺编码方法费诺编码属于概率匹配编码 1 将信源消息符号按其出现的概率大小依次排列 2 将依次排列的信源符号按概率值分为两大组 使两个组的概率之和近于相同 并对各组赋予一个二进制码元 0 和 1 3 将每一大组的信源符号进一步再分成两组 使划分后的两个组的概率之和近于相同 并又赋予两个组一个二进制符号 0 和 1 4 如此重复 直至每个组只剩下一个信源符号为止 5 信源符号所对应的码字即为费诺码 例5 5设信源共7个符号消息 a1 a2 a3 a4 a5 a6 a7 概率分别为0 20 0 19 0 18 0 17 0 15 0 10 0 01 求费诺编码 信源符号的平均码长为 编码效率为 例5 6有一单符号离散无记忆信源对该信源用费诺编码方法 求其二进制代码组及其编码效率 该信源熵为 平均码长 编码效率 费诺编码特点 概率大 则分解的次数小 概率小 则分解的次数多 这符合最佳编码原则 码字集合是惟一可译码 且为即时码 分解完了 同时可以得到码字和码长 3 哈夫曼编码方法 1 将信源消息符号按其出现的概率大小依次排列 2 取两个概率最小的字母分别配以0和1两个码元 并将这两个概率相加作为一个新字母的概率 与未分配的二进符号的字母重新排队 3 对重排后的两个概率最小符号重复步骤 2 的过程 4 不断继续上述过程 直到最后两个符号配以0和1为止 5 从最后一级开始 向前返回得到各个信源符号所对应的码元序列 即相应的码字 例5 7设信源共7个符号消息 a1 a2 a3 a4 a5 a6 a7 概率分别为0 20 0 19 0 18 0 17 0 15 0 10 0 01 求哈夫曼编码 5 2无失真信源编码 0 200 190 180 170 150 100 01 0 200 190 180 170 150 11 0 260 200 190 180 17 0 350 260 200 19 0 390 350 26 0 610 39 1 0 信源符号的平均码长为 编码效率为 哈夫曼编码方法得到的码并非唯一的 每次对信源缩减时 赋予信源最后两个概率最小的符号 用0和1是可以任意的 所以可以得到不同的哈夫曼码 但不会影响码字的长度 对信源进行缩减时 两个概率最小的符号合并后的概率与其它信源符号的概率相同时 这两者在缩减信源中进行概率排序 其位置放置次序是可以任意的 故会得到不同的哈夫曼码 此时将影响码字的长度 例5 8设有离散无记忆信源求哈夫曼编码 解法一 1 0 0 40 20 20 2 0 40 40 2 0 60 4 0 40 20 20 10 1 解法二 1 0 0 40 20 20 2 0 40 40 2 0 60 4 0 40 20 20 10 1 信源符号的平均码长为 编码效率为 在实际应用中 选择那种编码方法 我们定义码字长度的方差为ki与平均码长之差的平方的数学期望 记为 2 即 计算上例中两种码的方差分别得 21 1 36 22 0 16可见第二种编码方法的码长方差要小许多 这意味着第二种编码方法的码长变化较小 比较接近平均码长 进行哈夫曼编码时 为得到码方差最小的码 应使合并的信源符号位于缩减信源序列尽可能高的位置上 以减少再次合并的次数 充分利用短码 哈夫曼码是用概率匹配方法进行信源编码 哈夫曼码的编码方法保证了概率大的符号对应于短码 概率小的符号对应于长码 充分利用了短码 缩减信源的最后二个码字总是最后一位不同 从而保证了哈夫曼码是即时码 把二进制的编码方法推广到m进制哈夫曼码 所不同的只是每次把m个概率最小的符号分别用0 1 m 1等码元来表示 然后再合并成一个新的信源符号 其余步骤与二进制编码相同 在编m进制哈夫曼码时 为了使平均码长最短 必须使最后一步缩减信源有m个信源符号 这样 第一步给概率最小的符号分配码元时 所取的符号数就不一定是m个 所谓全树 就是码树图中每个中间节点后续的枝数必为m 若有些节点的后续枝数不足m 就称为非全树 必须用非全树时 第一次分配码元就不能取m个符号 对于m进制编码 若所有码字构成全树 可分离的码字数必为 m k m 1 式中k为非负整数 因为从根节点开始 必须伸出m个树枝才能构成全树 以后每次从一个节点分出m枝 码字数就增加m 1个 即去掉原来的一个码字 加上m个码字 所以总码字数必为m k m 1 个才能构成全树 若信源所含的符号数n不能构成m进制的全树 就必须增加s个不用的码字来形成全树 显然s m 1 当有s个码字不用时 第一次对最小概率符号分配码元时就只取m s个 分别配以0 1 m s 1 把这些符号的概率相加作为一个新的符号概率 与其他符号一起重新排列 以后每次就可以取m个符号 分别配以0 1 m 1 如此下去 例5 9设单符号离散无记忆信源如下 对信源编三进制哈夫曼码 m 3 n 8令k 3 m k m 1 9则不用的码字数为s 9 n 1 所以第一次取m s 2个符号进行编码 概率 编码过程 0 22 0 38 0 09 1 0 三进制代码组 ki 消息 平均码长相应的信息率编码效率