信息论与编码_第4章无失真信源编码.ppt

第4章 无失真信源编码 王永容 机械与电气工程学院 wangyr416@126.com 信源编码 信源编码是以提高通信的有效性为目的编码。 通常通过压缩信源的冗余度来实现。 采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。同样多的信息用较少的码率来传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。 第4章 无失真信源编码 4.1 无失真信源编码的概念 4.2 等长编码 4.3 变长编码 4.4 常用的变长编码算法 4.1 无失真信源编码的概念 信源符号(字母)集：S＝{s1, s2,…,sq}. 码符号(字母、元)集：A＝{a1, a2,…,am}. 编码函数f: 将有限个信源符号变换成有限个码符号的函数 用AN表示全体长度为N的信源符号序列构成的集合 4.1 无失真信源编码的概念 N=1时 4.1 无失真信源编码的概念 4.1 无失真信源编码的概念 4.1 无失真信源编码的概念 4.1 无失真信源编码的概念 即时码: 如果收到一个码字后, 就能及时译出，则称为即时码,也称为非延长码，或异前缀码. 即没有任何完整的码字是其它码字的前缀。 否则，就称为非即时码. 例：码5是即时码, 码4是非即时码. 4.1 无失真信源编码的概念 关系 即时码一定是唯一可译码 唯一可译码一定是非奇异码 定长的非奇异码一定是唯一可译码 非定长的非奇异码不一定是唯一可译码 第4章 无失真信源编码 4.1 无失真信源编码的概念 4.2 等长编码 4.3 变长编码 4.4 常用的变长编码算法 4.2 等长编码 4.2 等长编码 4.2 等长编码 4.2 等长编码 4.2 等长编码 等长信源编码定理 定理4-1(Shannon信源编码定理) 4.2 等长编码 等长信源编码定理 最佳等长编码: 4.2 等长编码 第4章 无失真信源编码 4.1 无失真信源编码的概念 4.2 等长编码 4.3 变长编码 4.4 常用的变长编码算法 4.3 变长编码 4.3 变长编码 4.3 变长编码 4.3 变长编码 4.3 变长编码 4.3 变长编码 4.3 变长编码 4.3 变长编码 4.3 变长编码 第4章 无失真信源编码 4.1 无失真信源编码的概念 4.2 等长编码 4.3 变长编码 4.4 常用的变长编码算法 4.4.1 香农编码 §4.1.2 费诺编码 4.4 常用的变长编码算法 4.4 常用的变长编码算法 4.4 常用的变长编码算法 4.4 常用的变长编码算法 4.4 常用的变长编码算法 4.4 常用的变长编码算法 4.4 常用的变长编码算法 4.4 常用的变长编码算法 4.4 常用的变长编码算法 4.4 常用的变长编码算法 4.4 常用的变长编码算法 4.4 常用的变长编码算法 101 100 11 0 码字 0 1 2 3/16 4/16 9/16 0 1 1 7/16 9/16 0 1 3 1 9/16 a0 a0 2 3/16 a0 a1 3 3/16 a1 a0 3 1/16 a1 a1 码长 概率分布 符号序列 例4.10 设二元离散无记忆信源X的符号集为{a0, a1}, 概率分布为：p0=0.75, p1=0.25, 则 H(X)= ?0.75log0.75 ?0.25log0.25=0.811. 对两个信源符号X2进行编码, 则有 设离散信源X的熵为H(X), 则其任意一个m元唯一可译码满足： 同时存在m元唯一可译码，其平均长度满足： 单个符号不等长信源编码定理 设离散信源X的熵为H(X), 其N次扩张信源为XN，将信源XN编为m元码，总存在唯一可译码f，使得信源X的每个符号所需的平均码长满足： 离散平稳无记忆序列变长编码定理 香农第一编码定理 设有离散无记忆信源 1 2 3 4 香农编码方法的步骤 按信源符号的概率从大到小的顺序排队 不妨设 例 设有一单符号离散无记忆信源 试对该信源编二进制香农码。 编码过程 （1） 对概率按m进行分组，使每组概 率尽可能相等 给每个分组分配一个码元 对每个分组重复2、3步，直到不可分为止 1 2 3 4 按信源符号的概率从大到小的顺序排队 不妨设 设有一单符号离散无记忆信源 试对该信源编二进制费诺码。 例 编码过程 可以看出本例中费诺码有较高的编码效率。 费诺码比较适合于每次分组概率都很接近的信源。 将信源符号按概率由大到小顺序排队 给两个概率最小的符号各分配一个码位，将其概率相加后合并作为一个新的符号，与剩下的符号一起，再重新排队 给缩减信源