《信息论基础理论与应用第三版(傅祖芸)讲义(课堂PPT)》由会员分享，可在线阅读，更多相关《信息论基础理论与应用第三版(傅祖芸)讲义(课堂PPT)（57页珍藏版）》请在金锄头文库上搜索。
1、第5章无失真信源编码定理 5 1编码器 5 2等长码 5 6变长信源编码定理 5 4等长信源编码定理 5 5变长码 信息通过信道传输到信宿的过程 要做到既不失真又快速地通信 需要解决两个问题 信源编码 在不失真或允许一定失真条件下 提高信息传输率 信道编码 在信道受到干扰的情况下 增加信号的抗干扰能力 同时又使得信息传输率最大 最佳编码 一般来说 抗干扰能与信息传输率二者相互矛盾 而编码定理理论上证明 至少存在某种最佳的编码能够解决上述矛盾 做到既可靠又有效地传输信息 信源编码 信源虽然多种多样 但无论是哪种类型的信源 信源符号之间总存在相关性和分布的不均匀性 使得信源存在冗余度 信源编码的目
2、的就是要减少冗余 提高编码效率 引言 研究方法研究信源编码时 将信道编码与译码看成是信道的一部分 从而突出信源编码 研究信道编码时 将信源编码与译码看成是信源与信宿的一部分 从而突出信道编码 5 1编码器 编码器 对信源的符号按一定的数学规则进行的变换 它可以看作这样一个系统 它的输入端为原始信源S 其符号集为而信道所能传输的符号集为 编码器功能 用符号集X中的元素 将原始信源的符号变换为相应的码字符号 编码器输出符号集为 码或码书 称为码字 li为码字的码元个数 码字长度 码长 码字集合C称为码或码书 若要实现无失真编码 这种映射应是一一对应的可逆映射 编码的形式化描述 从信源符号到码符号的
3、一种映射 或 1 二元码与r元码2元码 码符号集X 0 1 如果将信源通过二元信道传输 必须将信源编成二元码 这是最常用的一种码 r元码 码符号集有r个符号的编码 2 等长码与变长码等长码 一组码中所有码字的长度都相同 变长码 一组码中所有码字的长度各不相同 码的分类及定义 3 非奇异码与奇异码非奇异码 一组码中所有码字都不相同 奇异码 一组码中有相同的码字 4 同价码同价码 码符号集中每个码符号所占的传输时间都相同 大多数情况 变长码中每个码字的传输时间就不一定相同 摩尔斯电报码 点 划所占传输时间不同 5 码的N次扩展若某码C 它把信源S中的符号一一变换成码C中的码字 则码C的N次扩展码是
4、所有N个码字组成的码字序列的集合B S 扩展 码C 码B 扩展信源 扩展码 N次扩展 N次扩展 例 设信源S的概率空间为 若通过 个二元信道进行传输 须把信源符号变换成0 1符号组成的码符号序列 二元序列 采用如下二元码 如下表所示 q 4 试求码的二次扩展码 信源S的二次扩展信源 则码的二次扩展码为 6 唯一可译码 单义可译码 由码构成的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列 否则 就为非惟一可译码或非单义可译码 例 对于二元码 当任意给定一串码字序列 例如 10001101 只可唯一地划分为1 00 01 1 01 因此是惟一可译码 而对另一个二元码 当码字序列为
5、01001 可划分为0 10 01或01 0 01 所以是非惟一可译的 唯一可译码的条件1 不同的信源符号变换成不同的码字 非奇异码 2 任意有限长的信源序列所对应的码元序列各不相同 即 码的任意有限长N次扩展码都是非奇异码 Or 码符号序列的反变换也唯一的 扩展码非奇异 原因 若要使某一码为惟一可译码 则对于任意有限长的码符号序列 必须只能被惟一地分割成一个个的码字 才能实现唯一的译码 无失真的编码的一般条件1 码字与信源符号之间一一对应 非奇异码 2 码符号序列的反变换也唯一的 扩展码非奇异 即 编码必须是唯一可译码 否则 就会引起译码的错误与失真 等长码是唯一可译码的条件若等长码是非奇异
6、码 则它的任意有限长N次扩展码一定也是非奇异码 因此 等长非奇异码字一定是唯一可译码 因为采用固定长度划分码字序列 5 2等长码 1 若对每个信源符号进行等长编码 则必须满足 其中 l是码长 r是码符号集的码元数 q信源符号数 2 若对信源的N次扩展信源进行编码 必须满足 表示平均每个信源符号所需的码符号个数 即 为了使等长码为非奇异码 唯一可译码 那么 例证 根据依赖关系 信源符号平均所需码符号数可减少 例设信源 而其依赖关系为 1 若不考虑符号间的依赖关系 可得每符号码长l 2 2 若考虑符号间的二元依赖关系 可作二次扩展信源进行分析 根据条件概率仅有4项的概率不为零 可得扩展信源的码长l
7、 2 而每个信源符号的平均码长为l N 1 5 4等长信源编码定理 给出了等长信源编码所需码长的极限值 定理等长信源编码定理一熵为H S 的离散无记忆信源 若对其N次扩展信源进行等长r元编码 码长为l 对于任意大于0 只要满足 当N足够大时 则可以实现几乎无失真编码 反之 若 则不可能实现无失真编码 当N趋向于无穷大时 译码错误率接近于1 分析 定理中的条件式可写成 左边 长为l的码符号 码字 所能载荷的最大信息量 右边 长为N的信源符号序列平均携带的信息量 因此 定理说明了 只要码字传输的最大信息量大于信源序列携带的信息量 则可以实现无失真编码 编码后信源的信息传输率 令 可见 只有编码后信
8、息传输率 才能实现无失真编码 编码后 平均每个信源符号承载的信息量 最佳编码效率 由定理知 编码效率 移项后 当信源符号自信息量的方差和确定时 只要N足够大 就可以实现允许错误概率 这时要求序列长度满足 任意一正数 信源序列长度N 一般情况下 在已知信源熵的情况下 信源序列长度N的选择 与最佳编码效率和允许错误概率有关 可以证明 若采用等长二元编码 要求编码效率 允许错误率 则 例 设离散无记忆信源 1 唯一可译变长码 5 5变长码 优势 容易实现效率很高的编码 变长码也必须是唯一可译码 才能实现无失真编码 码1是一个奇异码 故不是唯一可译码 码2也不是唯一可译码 因为收到一串序列 无法唯一译
9、出对应的原符号序列 如01000 即可译作s4s3s1 也可译作s4s1s3 s1s2s3或s1s2s1s1 码2本身不是奇异码 但从有限长的码符号序列是奇异码 如果把码2的2次扩展码写出 则会发现 S1S3的扩展码字为 000 S3S1的扩展码字也为 000所以 当出现000序列时候 不能唯一地确定信源符号 码3和码4都是唯一可译的 但码3和码4也不太一样 码4称作逗点码 只要收到1 就可以立即作出译码 而码3不同 当收到一个或几个码时 必须参考后面的码才能作出判断 100010010 即时码接收端收到一个完整的码字后 就能立即进行译码 无须参考后面的码字就可以作出唯一判断 译码 对于非即时
10、码 接收端收到一个完整的码字后 还需等后续码元接收后才能判断是否可以唯一译码 非延长码 前缀条件码 若码C中 没有任何完整的码字是其他码字的前缀 即设是码C中的任意码字 而它不是其他码字 j m 的前缀 则此码为非延长码 或前缀条件码 显然 即时码等价于前缀条件码 非延长码 码3 s1的码字是s2 s3 s4的码字的前缀 词头 s2的码字是s3 s4的码字的前缀 s3的码字是s4的码字的前缀 当译码时 接受到一个完整码字后 不能马上译码 还需考察后续码元的情况才能进行正确译码 如 100010010 可译码为 s4s3 因此 码3不是即时码 但确是唯一可译码 码4 码本中的任何一个码字都不是其
11、他码字的前缀 当译码时 接受到一个完整码字后 不需要等待后续码元的情况即可正确译码 如 100010010 可译码为 s1s4s3 因此 码4是即时码 也是唯一可译码 因此 对于码C 若其为唯一可译码 则必为非奇异码 若其为即时码 则必是唯一可译码 反之 作为唯一可译码 则不一定是即时码 所有的码 非奇异码 唯一可译码 即时码 非延长码 2 即时码 非延时码 的树图构造法 对于给定码字集合C 可用码树来描述 同时 树图法可构造即时码 在每个节点上都有r个分枝的树称为整树 满树 否则称为非整 满 树 等长码二元码树 整树 树根 码字的起点 树枝数 码符号数 终端节点 码字 阶数 码长 中间节点
12、012 012012012 012 012 三元码树 整树 满树 变长码 非即时码的树图中间节点安排为码字 1 树图中间节点不作为码字 2 一旦某节点作为码字 则不再继续进行分枝 这样可保证每个码字不同 且满足前缀条件码的条件 一般编码方法选择相应节点作为码字 不同的路径上的分支 对应了相应的码元符号 则可得到所编码字 构造即时码 编码举例 即时码 编码方式不同 都为即时码 但编码方式不唯一 编码举例 多元即时码 译码方法因为每一码元对应于一个的树图分枝路径 则即时码的树图可以用来译码 译码器系统对一串符号序列译码过程 1 首先从树根出发 根据接收的第一个码元符号来选择应走的第一条路径 2 若
13、沿着所选路径走到某中间节点 再根据接收的第二个码元符号来选择第二条路经 3 若又走到中间节点 再依次继续选择路径 直到终端节点为止 这时 可根据所经历的枝路 判断出所接收的码字 4 重新返回树根 再作下一个接收码字的判断 这样 便可将接收到的一串码符号序列译成信源符号序列 3 克拉夫特 Kraft 不等式 定理对于码符号为的任意r元即时码 若所对应的码长 则必定满足 反之 若码长满足上式 则一定存在这样的即时码 可以证明 对于唯一可译码也须满足Kraft不等式 这说明 其他唯一可译码并不比即时码占优 而即时码很容易用树图法构造 所以在讨论唯一可译码时 只需要讨论即时码就可以了 定理若存在一个码
14、长为的唯一可译码 则一定存在一个同样长度的即时码 例 设二进制码树中S s1 s2 s3 s4 L1 1 L2 2 L3 2 L4 3 应用Kraft不等式 得 不存在满足这种Li的唯一可译码 如果将各码字长度改成L1 1 L2 2 L3 3 L4 3 则 存在满足这种Li唯一可译码 码树 设信源 编码后的码字为 码长为 码的平均长度 平均码长 为 5 6变长信源编码定理 码符号 信源符号 码的平均长度 信息传输率 码率 平均每个码元携带的信息量 即编码后信道的信息传输率 比特 码符号 若信道传输一个码符号平均需要t秒钟 则编码后信道的每秒传输的信息量为 比特 秒 由此可见 平均码长越短 信息
15、传输效率越高 紧致码 最佳码 对于某一信源和某一个码符号集合 若有一个唯一可译码 它的平均码长小于其他唯一可译码的长度 无失真信源编码的基本问题就是寻找紧致码 定理若对一熵为H S 的离散无记忆信源S进行r元编码 则总是可以找到一种无失真编码方法构成唯一可译码 使其平均码长满足 说明 下界 平均码长不能小于极限H s logr 否则唯一可译码不存在 上界 给出了平均码长的上界 但并不是说大于这个上界就不能构成唯一可译码 而是说在上界范围内 可找到唯一可译码 证明 1 下界证明 詹森不等式 因总可找到一种唯一可译码 其码长满足Craft不等式 所以 则证得 由Craft不等式 此等式成立的充要条
16、件 即 可见 只有当能够选择每个码长满足上述等式时候 平均码长才能够达到这个下界值 由于li必须为正整数 所以也必须为正整数 那么 当该等式成立时 每个信源符号的概率分布必须呈现如下形式 如果这个条件满足 则只要选择 根据这些码长 按照树图法构造出一种唯一可译码 所得的码一定是紧致码 2 上界证明 只需证明存在一种唯一可译码满足 即可 令 则 选取每个码字的长度的原则是 显然知 即为Craft不等式 因此 用这样选择的码长满足Craft不等式 故可构造唯一可译码 但不一定是紧致码 两边对i求和 则有 由于 右边的不等式两边进行如下处理 平均码长 因此 平均码长小于上界的唯一可译码存在 两边乘以P si 后 求和 另外由于 无失真变长信源编码定理 香农第一定理 离散无记忆信源S的N次扩展信源 其熵为 且编码器码元符号集为 对信源进行编码 总可以找到一种编码方法 构成唯一可译码 使信源S中每个信源符号si所需要的平均码长满足 当则得 证明 设离散无记忆信源X的数学模型 N次扩展 由于无记忆性 有 由前述定理 有 定理含义 要做到无失真信源编码 变换每个信源符号平均所需最少的r元码元数是信源
