信息论基础理论与应用6无失真信源编码

1、第四章无失真信源编码 1 冗余度的概念； 2 数据压缩的概念 3 数据压缩的基本途径 4 编码器 5 等长码及等长信源编码定理 6 变长码及变长信源编码定理 7 霍夫曼码和其他编码方法信息论面对通信系统回答了以下两个问题： 在不失真或者允许一定失真条件下，如何用尽可能少的符号来传送信源信息，以提高信息传输率-信源编码 在信道受干扰的情况下，如何增加信道的抗干扰能力，同时使信息传输率最大-信道编码冗余度的概念冗余度的概念冗余度的概念冗余度的概念冗余度的概念冗余度的概念4.1HHHHHHHHHNmin0max012冗余度的概念冗余度的概念冗余度的概念冗余度的概念冗余度的概念冗余度的概念冗余度计算机

2、文件表现为字符集合或者是二进制集合，当然二者最终存储形式都是“0”、“1”代码。有一类逻辑压缩方法，就是从分析数据入手，看那些数据可以省去，又如何以最少的符号来代替必不可少的数据。这实际上只是一种由数据自身特点及设计者技巧来决定的压缩表示法。本节讨论的是减少计算机文件内部冗余度的办法的统计编码方法。文件的冗余类型 字符分布 字符重复 位置冗余 高使用模式4.2 数据压缩的概念 信源编码信源编码：主要解决有效性问题。通过对信源的压缩、扰乱、加密等一系列处理，力求用最少的数码传递最大的信息量，使信号更适宜传输。 信道编码信道编码：主要解决可靠性问题。即尽量使处理过的信号在传输过程中不出错或少出错，

3、即使出了出了错也要能自动检错和尽量纠错。 因此，从信息论的角度看，信源编码的一个最主要的目的，就是要解决数据的压缩的问题，它构成了数据压缩的理论基础。 数据压缩，就是以最少的数码表示信源所发出的信号，减少容纳给定消息集合或数据采样集合的信号空间。数据压缩的概念所谓信号空间亦即被压缩的对象是指：v 物理空间：如存储器、磁盘、磁带、光盘等数据存储介质；时间区间：如传递给定信号所需要的时间；1. 电磁频谱区域：如为传递给定消息所要求的带宽。数据压缩的概念解决方法解决方法减小数据存储空间；提高传输速度时域压缩；提高频带利用率（在通信干线上开通更多的并行业务（电视、传真、电话、可视图文等）。数据压缩技术

4、分类数据压缩技术分类可逆压缩可逆压缩; ;1.1. 不可逆压缩不可逆压缩 可逆压缩可逆压缩可逆压缩：可逆压缩： 亦称无失真、无差错编码亦称无失真、无差错编码(Error Free (Error Free Coding)Coding)或（或（Noiseless CodingNoiseless Coding），不同专业），不同专业的文献作者还采用了另外些术语，如冗余度的文献作者还采用了另外些术语，如冗余度压缩（压缩（Redundancy ReductionRedundancy Reduction）, ,熵编码熵编码（Entropy CodingEntropy Coding）、数据紧缩）、数据紧缩(

5、Data (Data Compaction)Compaction)等等。等等。理论依据：理论依据： 香农在创立信息论时，提出把数据看作是信香农在创立信息论时，提出把数据看作是信息与冗余度的结合。息与冗余度的结合。可逆压缩可逆压缩【例【例4-14-1】在一个数据采集系统，如信号在一段在一个数据采集系统，如信号在一段长时间内不变，则许多连续采样值是重复不变长时间内不变，则许多连续采样值是重复不变的。的。 显而易见的方法就是计算两个不同采样值间显而易见的方法就是计算两个不同采样值间的重复采样数目的重复采样数目, ,然后将变化的采样值和重复数然后将变化的采样值和重复数目一起发送目一起发送, ,即压缩又

6、无失真即压缩又无失真( (compressioncompression）【例【例4-24-2】1212位位A/DA/D转换器采样数据。为了便于转换器采样数据。为了便于处理，常用一个处理，常用一个2 2个个8 8 位的寄存器来存一个样值，位的寄存器来存一个样值，这就使每一样值额外增加了这就使每一样值额外增加了4 4位冗余度位冗余度. 若改用若改用6 6个字（个字（48bit48bit）存）存4 4个数据，即可消除冗个数据，即可消除冗余度（余度（CompactionCompaction）不可逆压缩不可逆压缩不可逆压缩不可逆压缩 ： 有失真编码（有失真编码（LossyLossyCodingCodin

7、g），亦称），亦称熵压缩（熵压缩（Entropy CompressingEntropy Compressing）【例【例4-34-3】为了简单地实现熵编码，我们】为了简单地实现熵编码，我们在监督采样时设置某个门限；只有当采样在监督采样时设置某个门限；只有当采样值过该门限时才传数据。值过该门限时才传数据。丢失了信息。丢失了信息。数据压缩的类比 【例【例4-44-4】设想我们将菜叶（数据）倒入一个铁桶（存储设想我们将菜叶（数据）倒入一个铁桶（存储器）的情形，为了使铁桶装得尽可能多的茶叶。器）的情形，为了使铁桶装得尽可能多的茶叶。 有以下几种可行的途径：有以下几种可行的途径：将茶叶罐颠一颠、摇一摇，

8、使茶叶排列更紧密，挤掉外在的一些外在将茶叶罐颠一颠、摇一摇，使茶叶排列更紧密，挤掉外在的一些外在的的“冗余度（冗余度（ CompactionCompaction）”。无失真压缩。无失真压缩将茶叶烤干，去除茶叶的水分，减小自身体积将茶叶烤干，去除茶叶的水分，减小自身体积消除消除“内在的冗余内在的冗余度度”（compressioncompression）。无失真压缩）。无失真压缩将干菜叶压成末，此时装的最多（压缩最大），将干菜叶压成末，此时装的最多（压缩最大）， 但但“ “ 叶叶”已变已变“粉粉”，不可逆压缩。茶叶已无法复原。，不可逆压缩。茶叶已无法复原。 有失真信源编码。有失真信源编码。 由此我

9、们已建立了一个初步的概念，即：由此我们已建立了一个初步的概念，即：有冗余度就可以压缩（罐中有空气，茶叶中有水分）有冗余度就可以压缩（罐中有空气，茶叶中有水分）压缩只能在一定限度内可逆（菜叶倒出来仍然完整）压缩只能在一定限度内可逆（菜叶倒出来仍然完整）超过此限度（信息熵）必然带来失真（茶叶会破碎）超过此限度（信息熵）必然带来失真（茶叶会破碎）1. 允许的失真越大，压缩比也可以越大（茶叶压得余额碎，罐可装得越允许的失真越大，压缩比也可以越大（茶叶压得余额碎，罐可装得越多）多）3 数据压缩的基本途径数据压缩的基本途径 基本途径之一概率匹配 基本途径之二对独立分量进行编码 基本途径之三利用条件概率基本

10、途径之一概率匹配基本途径之一概率匹配基本途径之一概率匹配基本途径之一概率匹配%100/ )(143. 1/4log/75. 1381381241121)(41lXHlCRbitlapliii符号基本途径之二对独立分量进行编码不考虑相关性时信源熵为H(X)+H(Y)考虑相关性时信源熵为H(X)+H(Y)-I(X,Y)基本途径之三利用条件概率基本途径之三利用条件概率基本途径之三利用条件概率4 4、编码器、编码器 编码实质是对信源的原始符号按一定的数学规则进行的一种变换，如下图所示图4.1 无记忆信源编码器编码器编码器编码器编码器无失真信源编码 无失真编码概述 定长信源编码 变长信源编码 无失真信源

11、编码方法举例4.1无失真编码概述1离散、无失真、无记忆信源编码的一般模型：总码组合数：)(21NiiiSSSS),(21liiixxxC总组合数：Nqlr入出信源编码4.1无失真编码概述2 问题问题：能否进行无失真编码，怎样进行无失真编码若：不考虑信源统计特性： 应满足条件应满足条件： 相互矛盾！ lrqrqNN有效：无失真：lrqNlrqlNloglog由结论结论：当q=r时，lN不有效。当l=N时，rq，亦不满足有效性解决办法解决办法：引入信源统计特性。4.1无失真编码概述3考察无失真条件考察无失真条件： 分别表示等概条件下的消息熵 与码字熵 之比， 考虑信源的实际统计特性（非等概），实际

12、消息熵为： 代入无失真条件得： 此时：即使q=r,只要 就有可能实现N0,0，只要满足： (l/N)logrH(S)+ 则：当N足够大时，可使译码差错小于， 反之，当 (l/N)logrH(S)-2 时，译码一定出错。解释：定长编码定理给出了信源进行等长编码所需码长的理论极限值。 4.2定长编码定理2-进一步理解若要求变得的等长码是唯一可译的，则必须：若N1，则：结论结论：对于唯一可译码，每个信源符号至少需要用 个码符号来变换。当采用二元码编码时，r2，则：结论结论：对信源进行二元等长编码时，每个信源符号所需码长的极限值为 rqNlrqlNloglogrqloglogrqlloglog)(lo

13、glog21bitqlqNlN)(logbitq例1：英文电报有32个符号（266），即n=32， 若m=2，L1（即对信源的逐个符号进行二元编码）， 则：解释：每个英文电报符号至少需要用5位二元符号编码问题：在考虑符号出现的概率和符号间相关性前提下,每个英文符 号平均携带的信息量是1.4bit/符号（ ），5bit/符号， 等长编码效率极低，如何提高效率？如何体现有效性？532loglogqlBit/符号bitH4 . 1解决方法：考察：字母个数为q，字母出现非等概，且字母之间相关长度为N的英文信源，其可能的字母序列总数为 ；但其中大部分字母序列是无意义的字母组合，而且随着N的增加，这种无意

14、义序列的总数越来越大。方法：进行联合编码，即对字母序列编码，且只对哪些有意义的字母序列编码，即需编码的字母序列的总数 ,则平均每个信源符号所需的码符号个数可以大大减少，从而提高了传输效率。问题：会引入一定的误差，当N足够长后，误差可以任意小。NqNq4.2定长编码定理5（物理意义） 结论： 可推广至离散、非平稳无记忆信源和有记忆信源情况 只要编码信息率大于信源序列携带的信息量（熵)，总可以实现几乎无失真编码(l/N)log rH(S)+rSHNllog)(二元码时，r2：)()()()(SHSHNlRSHNlSHNll最佳等长码时：4.2定长编码定理6（实际应用问题） 编译码同步问题 问题：如

15、何使译码端知道码字起点 解决办法：1、每个码字加短同步前缀 2、每若干码字加较长同步前缀 分组长度与编译码复杂性、编译码延时等等关系 问题：要实现有效，源序列分组很长，使得编译码 复杂性和延时增加 解决办法：目前没有理想到解决办法 定长信源编码的理论意义远大于其实用价值4.2定长编码定理7（举例)例2：设有一简单离散信源：L=1,n=2对其进行近似于无失真的等长编码，若要求其编码效率为96%，差错率低于10-5，试求符号联合编码长度L=？解： 由编码效率：即： 再由:可见,需要4100万个信源符号联合编码,才能达到上述要求,这显然是不现实的.一般来说：当一般来说：当N有限时，高传输效率的等长码

16、往往要引入一定的失真和错误，有限时，高传输效率的等长码往往要引入一定的失真和错误，它不能象变长编码那样可以实现真正的无失真编码它不能象变长编码那样可以实现真正的无失真编码信源符号）/(811. 0log)(21bitppSHiii%96)()(SHSH034.096.096.0811.0811.075222221013. 410)034. 0(4715. 0PLLP4715. 0)(log221)(22SHppiii412431sspS4.5 变长码变长码 可见变长码的编码思想就是，用短码表示高概率的符号，用长码表示低概率符号，编码后使平均码长接近于信源的信息熵。 缺点是：解码远比等长码复杂，

17、并且还存在唯一可译性、译码实时性、均匀输入输出的缓存问题4.6变长信源编码-1 几个码类的概念 非奇异码（奇异码、单义码） 唯一可译码 前缀码（即时码、非延长码、异前置码） 最佳码（紧致码） Kraft定理 唯一可译码存在定理 变长编码定理（香农第一定理）4.6变长信源编码-2(几个码类的概念) 非奇异码： 每一个码字仅对应信源中的一个信源符号（序列）。 编码是单义的。 反之为奇异码或非单义码。4.6变长信源编码-3(几个码类的概念) 唯一可译码 编码单义、译码单义 对任何一个有限长度的信源字母序列，如果编码得到的码字母序列不与其他任何信源字母序列所对应的码字母序列相同。4.6变长信源编码-4

18、(几个码类的概念) 即时码 是一类唯一可译码 在一个变长码中，没有任何一个码字是其他码字的前缀。 译码时无需参考后续的码符号就能立即作出判断，进行无延时译码。 又称即时码、非延时码4.6变长信源编码-5(几个码类的概念) 最佳码 唯一可译码的一类 其平均码长小于其他唯一可译码的平均长度所有的码非奇异码唯一可译码即时码4.6变长信源编码-6（几种类型的信源编码 举例）例3：信源信源概率概率pi 编码编码编码编码编码编码编码编码编码编码S11/2000000S21/401011001S31/810100110011S41/81110111110111编码编码唯一可译等长编码编码奇异编码编码非奇异编

19、码编码即时编码编码唯一可译不等长定理定理4.4：对于码符号为X：x1,x2,xq的任意即时码，其码字为W1，W2, Wq符号，所对应码长分别为l1,l2,lq。则必定满足Kraft不等式，即：反之，若码长满足Kraft不等式，则一定存在这样码长的即时码qilir11定理定理4.5：对于码符号为X：x1,x2,xq的任一唯一可译码，其码字为W1，W2, Wq符号，所对应码长分别为l1,l2,lq。则必定满足Kraft不等式，即：反之，若码长满足Kraft不等式，则一定存在这样码长的唯一可译码qilir11定理定理4.6：若存在码长分别为l1,l2,lq的唯一可译码。则一定存在具有相同码长的即时码

20、码树变长码的树图表示将变长码与码树建立“一一对应”关系：树根码字起点树枝数码的进制数节点码字或码字的一部分终止节点码字节数码长非满树变长码满树等长码 变长码变长码变长码唯一可译变长码的判断法 将码C所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任意码字，则可判断此码C为唯一可译变长码 例4.2 现设码C=0,10,1100,1110,1011,1101, 判断码C是否为唯一可译码 F=11，00，10，01，0，1，100，110，011，101，而10，0都是C中的码字，所以码C不是唯一可译码 10101110110100010111100001110 例4.1 设码C=110,

21、11,100,00,10, 判断码C是否为唯一可译码 F=0，F集中没有元素是码C的码字，所以码C是唯一可译 01000114.6变长编码定理问题： 对于已知信源S可用码符号X进行变长编码，而且对同一信源编成同一码符号的前缀码或惟一可译码可有许多种。究竟哪一种最好呢?从高速度传输信息的观点来考虑，当然希望选择由短的码符号组成的码字，就是用码长作为选择准则。引入：码的平均长度。 离散无记忆平稳信源 信源熵率为 码字母表个数为M， 则即时码平均码长： ninipppsSsSsSPS11)(SH)(1iMiiapll4.6变长编码定理定理4.7 无失真变长信源编码定理(即香农第一定理) ： 离散无记

22、忆平稳信源S，其熵率为 ，并有码符号X=x1,xm。对信源S进行编码,总可以找到一种编码方法，构成惟一可译码，使信源S中每个信源符号所需的平均码长满足: )(SH1log)(log)(rSHrSHL 下界证明rSHLrsPrsPsPrsPrsPsPsPrlsPsPsPlsPrsPsPrLSHqililiqiqiiliqiliiqiiqiiiqiiqiiiiqiiiiiiilog)(01loglog)()(log)(log)(log)()(log)(log)()(log)()(log)(log)(log)(111111111 上界证明1log)()(log)(log)()(1log)(loglo

23、g)(log,log)(loglog)(log1i1i1irsHLsPrsPsPlsPrsPlrsPrsPlrsPlqiiqiqiiiiiiiii所以的最小整数是不小于令4.6变长编码定理 物理意义： 又称无噪信道编码定理 编码后的码符号信源尽可能为等概分布，使每个码符号平均所含的信息量达到最大 要做到无失真编码，变换每个信源符号平均所需最少的r元码元数就是信源的熵率（以r进制信息量单位测度） 信源的熵率是描述信源每个符号平均所需最少的比特数 定理说明： 是存在性定理具有理论指导意义 是构造性定理设计出多种具体编码方法4.6变长编码定理15编码效率 变长码编码效率：衡量各种编码方法的优略，判断

24、是否最佳码。 编码前平均每个信源符号携带的信息量为： 编码后平均每个信源符号携带的最大的信息量为： 定义变长码编码效率为： 另一种理解： 最佳码（极限时）每个信源符号的平均码长为： 某一方法得到的每个信源符号的平均码长为： 定义变长码编码效率为：rllogLSHrLSHr)(log)()(SH)(log)(SHlrrSHl)(lSHllr比较： 定长编码的编码效率： 变长编码的编码效率：NSlHrSHRSHrNl)(log)()(LSHrLSHr)(log)( 例4：p145例4.1一离散无记忆信源412431sspS其熵为：信源符号）比特/(811.0log4log)(344341SH用二元

25、符号（0，1；m=2）构造一个前缀码：1,021ss此时每个信源符号平均码长为：1l811.0)(lSH编码效率为：为提高编码效率，对S的2次扩展信源进行2维联合编码：构造一个扩展信源S2的前缀码：前缀码 s1s2 9/16 0 s1s23/16 10 s1s2 3/16110 s1s2 1/16111i)(iP此时平均码长为：16272l此时信源S中每个符号对应的平均码长为：322716272 l编码效率为：961.0)(2lSH同样可得：985.0)(3lSH991.0)(4lSH定长编码与变长编码效率比较：例4.4与例4.1相比： 同一个信源，当要求编码效率达到96时， 等长码需要410

26、0万个信源符号联合编码； 变长码只需2个符号（二次扩展信源）联合编码；结论：采用变长编码，N不需要很大就可以达到相当高的编码效率，而且可以实现无失真编码。且随着N的增大，编码效率越来越接近于1。无失真编码的实质 无失真编码的实质就是：对离散信源进行适当的变换，使变换后新的码符号信源尽可能的为等概率分布，以使新信源的每个码符号平均所含的信息量达到最大码符号码符号码符号/1381log3)(/1241log2)(/1121log1)(321bitaIbitaIbitaI信源编码 针对信源的编码，能更加有效地传输、存储信息。 编码后尽可能减少所需信息的损失，提高编码后携带信息的效率 本节介绍霍夫曼本

27、节介绍霍夫曼(Huffman)码、费诺码、费诺(Fano)码和码和香农香农 -费诺费诺-埃利斯埃利斯(Shannon-Fano-Elias)码。码。 香农第一定理指出了平均码长与信源熵之间的关香农第一定理指出了平均码长与信源熵之间的关系，同时也指出了通过编码可使平均码长达到极限系，同时也指出了通过编码可使平均码长达到极限值。值。 但如何编码呢？但如何编码呢？ 1952年，霍夫曼提出了一种构造最佳码年，霍夫曼提出了一种构造最佳码的方法。的方法。 这是一种最佳的逐个符号的编码这是一种最佳的逐个符号的编码方法。编码对象为离散信源：方法。编码对象为离散信源：,.,)(,.,2121qiqpppsPss

28、sS编码步骤（对二元系统）：编码步骤（对二元系统）： v将将q个信源符号按概率递减的方式排列起来；个信源符号按概率递减的方式排列起来； v用用“0”,“1”码符号分别表示概率最小的两个信源码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一符号，并将这两个概率最小的信源符号合并成一个符号，从而得到只包含个符号，从而得到只包含 q-1个符号的新信源，个符号的新信源，称之为称之为S信源的缩减信源信源的缩减信源S1； v将缩减信源将缩减信源S1的符号仍按概率大小以递减次序排的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个列，再将其最后两个概率最小的符号合

29、并成一个符号，并分别用符号，并分别用“0”，“1”码符号表示，这样又码符号表示，这样又形成了形成了q-2个符号的缩减信源个符号的缩减信源S2； v依次继续下去，直到信源最后只剩下两个符号为依次继续下去，直到信源最后只剩下两个符号为止，将这最后两个符号分别用止，将这最后两个符号分别用“0”，“1” 码符号码符号表示，然后从最后一级缩减信源开始，向前返回，表示，然后从最后一级缩减信源开始，向前返回，得出各信源符号所对应的码符号序列，即得出对得出各信源符号所对应的码符号序列，即得出对应的码字。应的码字。 按霍夫曼的编码方法，可知这种码有以下特点：它是一种分组码它是一种即时码它是一种唯一可译码解码：霍夫曼码串可通过从左到右检查各个符号进行解码。本例中00011011010011a3 a2 a5 a2 a6a511 l=2a210 l=2a6011 l=3a4010 l=3a1001 l=3a30001 l=4a70000 l=4（huffman编码）编码方法：例 ： =消息U 概率pi 编码C U1 1/2 0 0 1 0 U2 1/4 0 10 1/2 1 U3 1/8 0 110 1/4 1 U4 1/8 1 111pis8/18/14/12/14321ssss（huff