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

第三章 信源编码-离散信源无失真编码 童 胜 ts_xd@163.com 2012年5月 通信系统的两个基本问题 问题一：数据压缩的理论极限是什么。 问题二：通信传输速率的理论极限是什么。 通信系统模型 主题 问题一（理论）：如何度量信源产生信息的速率？信源编码定理。 问题二（实际）：如何将信源的输出有效地进行表示？即信源压缩的具体实现技术。 信源编码-离散信源无失真编码 3.1 信源及其分类 3.2 离散无记忆信源的等长编码 3.3 离散无记忆信源的不等长编码 3.4 最佳不等长编码 3.5 平稳源编码* 3.6 马尔科夫源* 信源编码 信源编码：对信源输出符号/序列按一定的规则映射成码字的过程。 信源编码的目的和分类 1. 为什么要进行信源编码呢？ 2. 无失真编码和有失真编码 ：感觉无失真编码应该优于有失真编码，那么为什么还要引入有失真编码呢？ 信源码的分类 等长码：码中所有码字的码长都相同 接收端只要能正确识别出一个码字的起始位就能正确译码。 变长码：不同码字，其长度可以不一样 唯一可译性?唯一可译码，文言文断句 译码实时性?即时码 为了和匀速输出的信源匹配，需要考虑缓存 第1节 信源及其分类 信源 信源：产生消息的地方；信源的输出称为消息；信息承载在消息上。 在某一特定时刻，信源的输出可以是多种多样的消息。我们可以将消息建模为一个随机变量。 在某一段时间内，信源的输出可以是各种各样关于时间的函数。我们可以将其建模为随机过程。 信源的分类 输出在幅度和时间上的连续与否：离散信源、连续信源（波形信源）、时间离散连续信源等。 时间离散信源： 按各个时刻输出是否统计独立：有记忆信源和无记忆信源； 几个概念：简单信源、平稳信源、各态历经信源、马尔科夫信源。 离散无记忆平稳信源-简单信源 离散信源可以用随机变量序列来建模为 …U-2, U-1, U0, U1, U2, …。 如果Uk之间统计独立，相应的信源称为无记忆信源。 如果Uk彼此独立且服从同一概率分布，则称该信源为简单信源。 简单信源 简单信源可以建模为一个随机变量。 随机变量的取值空间---信源字母表 第2节离散无记忆信源的等长编码 等长编码 编码速率 编码速率： 物理含义：表示每个信源符号平均需要的比特数目（信息量）。 无失真等长编码 例3.2.1 中文电报的汉字编码就是一种等长编码。这里N = 4, D = 10，即每个汉字用4位十进制数表示。例如，“西安”编码后就成为4687 1618。此外，0, 1, 2, …, 9这10个数字采用如右边的编码方法。 问题：右边的表格中的码字有什么特点？ 等长编码能实现信源压缩吗？ 例子：考虑离散无记忆信源 一个具有启发意义的例子 例子：考虑一个简单信源U = {A, B}且Pr{A} = 0.2, Pr{B} = 0.8。对于下面两个长度为20的信源输出序列，哪个序列出现的概率更高？ 序列1：BBBBABBBABBBBBBABBBA 序列2：BBBBBBBBBBBBBBBBBBBB 序列出现概率的分布情况 A频率在[0.19,0.21] 的序列的概率和 A频率在[0.19,0.21] 序列的比例 结论 某些特定的信源序列的出现概率可能高于某个特定“常见”序列的出现概率； 随着序列长度的增加，“常见”序列构成的集合的总体概率趋于1。（弱大数定律） 想法 – 渐近无失真编码 如果这些“常见”序列的概率之和接近于1，并且它们的数目相对2L小得多，那么我们就可以只对这些“常见”序列进行编码。其他序列不做考虑。 随着L的增加，其它序列几乎不发生。这样，这种编码方法也就几乎没有失真了。 渐近无失真编码 如何用数学工具来描述“常见”序列？ 弱典型序列 定义：记离散无记忆信源U的熵为H(U)。对于正数ε，满足下面条件的序列构成的集合称为典型序列集(typical set)。 渐近等分性（asymptotic equipartition property） 定理：如果U1, U2, …是独立同分布的，且Ui ~ p(u)，那么有 弱典型序列的特性 定理1：当L? ∞时， 或者说，任给ε 0，存在正整数L0，使得LL0时， 弱典型序列的特性 定理2：如果序列 ，则有 弱典型序列的特性 定理3： 典型序列特性的总结 典型序列的出现概率渐近为1； 所有典型序列的出现概率几乎相同； 典型序列的总数约为2nH。 利用典型序列集进行编码就可以达到渐近无失真编码。 等长信源编码定理 考虑一个离散无记忆平稳(简单)信源，记其熵为H(U)。对长为L的信源序列进行等长编码。码字长度为N，且码字的N个符号取自同一个大小为D字母表。记编码