中北大学信息论与编码第5章(10)

《中北大学信息论与编码第5章(10)》由会员分享，可在线阅读，更多相关《中北大学信息论与编码第5章(10)（103页珍藏版）》请在金锄头文库上搜索。

1、1 1 1 信息论与编码 中北大学信息与通信工程学院 杨光 Tel：13994203068 E-mail: yangguang 2 第5章 信源编码 编码分为信源编码和信道编码，其中 信源编码又分为无失真和限失真。 一般称 u第一极限定理：无失真信源编码定理 u第二极限定理：信道编码定理 u第三极限定理：限失真信源编码定理 3 v信源存在冗余度 v原因是信源符号之间存在概率分布不均匀和 相关性 v信源编码的主要任务就是减少冗余，提高编 码效率。 第5章 信源编码 4 第5章 信源编码 信源编码的基本途径有两个： v使序列中的各个符号尽可能地互相独立，即 解除相关性； v使编码中各个符号出现的概

2、率尽可能地相等 ，即概率均匀化。 5 信源编码的作用可归纳为： (1) 符号变换：使信源的输出符号与信道的 输入符号相匹配； (2) 冗余度压缩：使编码效率等于或接近 100。 第5章 信源编码 6 第5章 信源编码 信源编码的基础是信息论中的两个编码定理： v无失真编码定理 v限失真编码定理 无失真编码可精确复制信源输出的消息，只适用于 离散信源 对于连续信源，只能在失真受限制的情况下进行限 失真编码 7 第5章 信源编码 本章讨论离散信源编码，首先从无失真编码定 理出发，重点讨论以香农码、费诺码和霍夫曼 码为代表的最佳无失真码。然后介绍了限失真 编码定理。最后简单介绍了一些其它常用的信 源

3、编码方法。 8 5.1 编码的定义 信源编码器信道 码表 图5-1 信源编码器示意图 9 5.1 编码的定义 将信源消息分成若干组，即符号序列xi， xi(xi1xi2xilxiL)， xilA=a1，a2，ai，an 每个符号序列xi依照固定码表映射成一个码字yi， yi(yi1yi2yilyiL)， yilB=b1，b2，bi，bm 这样的码称为分组码，有时也叫块码。只有分组码才有对 应的码表，而非分组码中则不存在码表。 10 5.1 编码的定义 如图5-1所示，如果信源输出符号序列长度L1， 信源符号集A(a1，a2，an) 信源概率空间为 若将信源X通过二元信道传输，就必须把信源符 号

4、ai变换成由0，1符号组成的码符号序列，这个 过程就是信源编码 11 5.1 编码的定义 码可分为两类： 一、固定长度的码，码中所有码字的长度 都 相同，如表5-1中的码1就是定长码 二、可变长度码，码中的码字长短不一，如表 中码2就是变长码。 12 5.1 编码的定义 不同的码符号序列，如表5-1所示。 表5-1 变长码与定长码 信源 符号ai 信源符号出 现概率p(ai) 码表 码1码2 a1p(a1)000 a2p(a2)0101 a3p(a3)10001 a4p(a4)11111 13 5.1 编码的定义 （1）奇异码和非奇异码 若信源符号和码字是一一对应的，则该码为 非奇异码。反之为

5、奇异码。 如表5-2中的码1是奇异码，码2是非奇异码 。 14 5.1 编码的定义 表5-2 码的不同属性 信源符号 ai 符号出现现概率 p(ai) 码码1码码2码码3码码4 a11/20011 a21/411101001 a31/80000100001 a41/8110110000001 15 5.1 编码的定义 （2）唯一可译码 任意有限长的码元序列，只能被唯一地分割 成一个个的码字，便称为唯一可译码 16 5.1 编码的定义 唯一可译码中又分为非即时码和即时码：如果 接收端收到一个完整的码字后，不能立即译码 ，还需等下一个码字开始接收后才能判断是否 可以译码，这样的码叫做非即时码。 1

6、7 5.1 编码的定义 即时码：只要收到符号就表示该码字已完整， 可以立即译码。 即时码又称为非延长码，任意一个码字都不是 其它码字的前缀部分，有时叫做异前缀码。 18 5.1 编码的定义 码 奇异码 非分组码 分组码 非奇异码 非唯一可译码 非即时码 即时码(非延长码) 唯一可译码 19 5.1 编码的定义 通常可用码树来表示各码字的构成 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 二进制码树 20 5.1 编码的定义 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 三进制码树 21 码树与码

7、字对应关系图 树根 树枝数 节点 终端节点 节数 非满树 满树 码字的起点 码的进制数 码字或码字的一部分 码字 码长 变长码 等长码 22 5.1 编码的定义 唯一可译码存在的充分和必要条件 各码字的长度Ki 应符合克劳夫特不等式： 23 5.1 编码的定义 例：设二进制码树中X (a1， a2 ， a3 ， a4 )， K11，K22，K32，K43，应用上述判 断定理： 因此不存在满足这种Ki的唯一可译码。 24 5.1 编码的定义 a1=0 1 0 1 0 1 0 a2=10 a3=110a4=111 0，10，110，111 惟一可译码； 0，10，010，111 不是惟一可译码；

8、均满足克劳夫特不等式 K11，K22，K33，K43 25 5.1 编码的定义 克劳夫特不等式只是用来说明唯一可译码是否 存在，并不能作为唯一可译码的判据。 26 X(X1X2XlXL) Xla1,a2,ai,an nL种 v用Y表示L长的信源序列X，则送出一个信源符号所 需要的信息率平均为 编码目的：使 最小 信源编码器 Ykb1,b2,bj,bm M=mKL种 KL log m 5.2 无失真信源编码 27 5.2 无失真信源编码 无失真信源编码定理研究的内容: v最小信息率为多少时，才能得到无失真的 译码？ v若小于这个信息率是否还能无失真地译码? 28 5.2 无失真信源编码 无失真的

9、信源编码定理 v定长编码定理 v变长编码定理 29 5.2 无失真信源编码 定长编码定理： 无记忆平稳信源平均符号熵为HL(X)， 只要 则当L足够大时，必可使译码差错足够小； 反之，当 时，译码差 错一定是有限值，而L足够大时，译码几乎必定 出错。 30 5.2 无失真信源编码 定长编码定理说明， 码字所能携带的信息量大于信源序列输出 的信息量，则可以使传输几乎无失真，当 然条件是L足够大。 31 5.2 无失真信源编码 反之，当 时，不可能构成无失真的 编码，也就是不可能做一种编码器，能使收端 译码时差错概率趋于零。 时，则为临界状态，可能无失真，也 可能有失真。 32 5.2 无失真信源

10、编码 例：信源输出8种符号， vL=1，等概率时，H1(X)log2 83比特/符号， 可用3比特的信息率进行无失真的编码。 vp(ai)0.4，0.18，0.1，0.1，0.07，0.06，0.05， 0.04，则此时H1(X)2.55比特/符号，22.555.856 v当L足够大，没有对应码字的符号序列发生的概 率变得很小，使得差错概率达到足够小。 33 5.2 无失真信源编码 式中 为自信息方差 为一正数。当 和 均为定值时，只要L足 够大，Pe可以小于任一正数。即， 34 5.2 无失真信源编码 当信源序列长度L满足 时， 能达到差错率要求 35 5.2 无失真信源编码 在连续信源的情

11、况下，由于信源的信息量趋于 无限，显然不能用离散符号序列Y来完成无失 真编码，而只能进行限失真编码。 36 5.2 无失真信源编码 定义 为编码效率，即信源的平均符号熵为H(X) ，采用平均符号码长为 来编码，所得的 效率。 编码效率总是小于1，且最佳编码效率为 37 5.2 无失真信源编码 编码定理从理论上阐明了编码效率接近1的理 想编码器的存在性，它使输出符号的信息率与 信源熵之比接近于1，即 L取无限长 38 5.2 无失真信源编码 例设离散无记忆信源概率空间为 比特/符号 39 5.2 无失真信源编码 对信源符号采用定长二元编码，要求编码效率 为 90，若取L1，则可算出 2.55 9

12、0%=2.8比特/符号 Pe0.04 太大 40 5.2 无失真信源编码 若要求译码错误概率 41 5.2 无失真信源编码 变长编码定理： v平均码长： v根据信源各个符号的统计特性，如概率大 的符号用短码，概率小的用较长的码，使得 编码后平均码长降低，从而提高编码效率。 （统计匹配） 42 5.2 无失真信源编码 单个符号变长编码定理：若离散无记忆信源的 符号熵为H(X)，每个信源符号用m进制码元进 行变长编码，一定存在一种无失真编码方法， 其码字平均长度满足下列不等式 43 5.2 无失真信源编码 离散平稳无记忆序列变长编码定理：对于平均 符号熵为HL(X)的离散平稳无记忆信源，必存在 一

13、种无失真编码方法，使平均信息率满足不等 式 其中为任意小正数。 44 5.2 无失真信源编码 用变长编码来达到相当高的编码效率，一般所 要求的符号长度L可以比定长编码小得多。 45 5.2 无失真信源编码 编码效率总是小于1，可以用它来衡量各种编码 方法的优劣。 为了衡量各种编码方法与最佳码的差距，定义 码的剩余度为 46 5.2 无失真信源编码 例设离散无记忆信源的概率空间为 47 5.2 无失真信源编码 若用二元定长编码(0，1)来构造一个即 时码： 。 平均码长 1二元码符号/信源符号 48 5.2 无失真信源编码 编码效率为 输出的信息效率为 R0.811比特/二元码符号 49 5.2

14、 无失真信源编码 长度为2的信源序列进行变长编码（编码方 法后面介绍），其即时码如下表 序列概率即时码 a1a19/160 a1a23/1610 a2a13/16110 a2a21/16111 50 5.2 无失真信源编码 二元码符号/信源序列 二元码符号/信源符号 51 5.2 无失真信源编码 编码效率 信息效率 R20.961比特/二元码符号 52 5.2 无失真信源编码 L3 R30.985比特/二元码符号 L4 R40.991比特/二元码符号 53 5.2 无失真信源编码 定长二元码编码，要求编码效率达到96 时，允许译码错误概率 54 5.2 无失真信源编码 最佳变长编码 凡是能载荷一定的信息量，且码字的平均长度 最短，可分离的变长码的码字集合称为最佳变 长码。 55 5.2 无失真信源编码 能获得最佳码的编码方法主要有： v香农（Shannon） v费诺（Fano） v哈夫曼（Huffman）等