信息论与编码-第5章

1、第第5章信源编码章信源编码 编码(Coding)分为信源编码(Source Coding)和信道编码(Channel Coding)，其中信源编码又分为无失真信源编码和限失真信源编码一般称u无失真信源编码定理为Shannon第一极限定理；u信道编码定理（包括离散和连续信道）称为Shannon第 二极限定理；u限失真信源编码定理称为Shannon第三极限定理 第第5章信源编码章信源编码l信源编码的主要任务：由于信源符号之间存在分布不均 匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率l信源编码的基本途径：n 使序列中的各个符号尽可能地互相独立，即解除相关性；n 使编码

2、中各个符号出现的概率尽可能地相等，即概率均 匀化第第5章信源编码章信源编码信源编码的理论基础是信息论中的两个编码定理：n无失真编码定理n限失真编码定理 无失真编码只适用于离散信源 对于连续信源，只能在失真受限制的情况下进行限失真编码 第第5章信源编码章信源编码本章主意讨论离散信源编码首先从无失真编码定理出发，重点讨论以香农(Shannon)码、费诺(Fano)码和霍夫曼(Huffman)码为代表的几种无失真信源码然后介绍限失真编码定理最后简单介绍了一些常用的信源编码方法5.1 编码的定义编码的定义信源编码器信道码符号(元)图5-1 信源编码器示意图XYX信源符号(Source Symbol)序

3、列Y码字(Codeword)序列信源编码是指信源输出的信源符号经信源编码器编码后转换成另外的压缩符号(码字Codeword)无失真信源编码：可精确无失真地复制信源输出的消息5.1 编码的定义编码的定义将信源消息分成若干组，即符号序列 xi， xi(xi1xi2xilxiL)， xilA=a1，a2，ai，an每个符号序列xi依照固定码表映射成一个码字yi， yi(yi1yi2yilyiL)， yilB=b1，b2，bi，bm这样的码称为分组码(Block Codes)，也叫块码只有分组码才有对应的码表，而非分组码中则不存在码表 5.1 编码的定义编码的定义如果信源输出符号序列长度L1，信源符号

4、集 A(a1，a2，an)信源概率空间为 )()()(2121nnapapapaaaPX若将信源X通过二元信道传输，就必须把信源符号ai变换成由0,1符号组成的码符号序列，这个过程就是信源编码 5.1 编码的定义编码的定义码可分为两类：1、固定长度的码，码中所有码字的长度（码元个数）都相同，如表5-1中的码1就是定长码(Fixed Length Codes)2、可变长度码，码中的码字长短不一，如表中码2就是变长码(Variable Length Codes) 表5-1 变长码与定长码信源符号ai信源符号出现概率p(ai)码表码1码2a1p(a1)000a2p(a2)0101a3p(a3)100

5、01a4p(a4)111115.1 编码的定义编码的定义码的属性及分类(1) 奇异码(Singular Codes)和非奇异码 (Nonsingular Codes) 若信源符号和码字是一一对应的，则该码为非奇异码, 反之为奇异码 表5-2中的码1是奇异码，码2是非奇异码信源符号ai符号出现概率p(ai)码1码2码3码4a11/20011a21/411101001a31/80000100001a41/8110110000001表5-2 码的不同属性5.1 编码的定义编码的定义(2) 唯一可译码 (Uniquely Decodable Codes) 任意有限长的码元序列，只能被唯一地分割成一个个

6、的码字，便称为唯一可译码( 3 ) 唯 一 可 译 码 中 又 分 为 非 即 时 码 和 即 时 码(Instantaneous Codes)： 如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码5.1 编码的定义编码的定义即时码：只要收到符号就表示该码字已完整，可以立即译码即时码又称为非延长码(Undelayed Codes)，任意一个码字都不是其它码字的前缀部分，有时叫做异前缀码(Prefix Codes)码码奇异码非分组码分组码非奇异码非唯一可译码非即时码即时码(非延长码)唯一可译码5.1 编码的定义编码的定义分组码非奇异

7、码唯一可译码即时码紧致码（最佳码）码5.1 编码的定义编码的定义通常可用码树来表示各码字的构成 树根root树枝 orders节点 notes终端节点 terminal nodes 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二进制码树015.1 编码的定义编码的定义 0 1 2 0 1 2 0 1 2 0 1 20 1 20 1 2三进制码树5.1 编码的定义编码的定义唯一可译码存在的充分和必要条件是各码字的长度Ki （码元个数）应符合克劳夫特不等式(Kraft Inequality)： 11niKim其中m为进制数，n为信源

8、符号数，Ki为各码字的长度（码元个数）必要性体现在如果是唯一可译码，则一定满足该不等式充分性体现在如果满足该不等式，则这种码长的唯一可译码一定存在，但并不表示所有满足Kraft不等式的码一定是唯一可译码所以说，该不等式是唯一可译码存在的充要条件5.1 编码的定义编码的定义例5.1 (p.88) 设二进制码中ai (a1, a2 ,a3 , a4)，K11，K22，K32，K43，应用Kraft定理判断是否可能是唯一可译码 412iKi因此不存在满足这种Ki的唯一可译码。 12239222218解：5.1 编码的定义编码的定义a1=1 0 1 0 1 0 1a2=01a3=011a4=0001，

9、01，001，000 惟一可译码；1，01，101，010 不是惟一可译码；均满足克劳夫特不等式122222332141iKi克劳夫特不等式只是用来说明唯一可译码是否存在是否存在，并不能作为唯一可译码的判据。5.2 无失真信源编码无失真信源编码信源输出符号序列为 X(X1X2XlXL)，其中 Xla1,a2,ai,an编码输出的码序列(码字)为 Y=(Y1Y2 Yk YKL) 其中 Ykb1,b2,bj,bm要求能够无失真或无差错地译码，同时传送Y 时所需要的信息率最小 由于Yk平均每个符号的最大信息量为 logm KL长码字的最大信息量为 KLlogm则传送每一个信源符号所需要的信息率平均为

10、 MLmLKKLlog1log其中LKmM Y所能编成的码字的个数5.2 无失真信源编码无失真信源编码所谓信息率最小，就是找到一种编码方式使 最小。无失真信源编码定理研究的内容:最小信息率为多少时，才能得到无失真的译码？若小于这个信息率是否还能无失真地译码？这就是无失真信源编码定理所要研究的内容n定长编码定理n变长编码定理K5.2 无失真信源编码无失真信源编码n5.2.1 定长编码定理K是定值 且惟一可译码由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1X2XlXL，可用KL=K个符号Y1，Y2，Yk，YKL，（每个符号有m种可能值）进行定长编码。对任意 0， 0，只要则

11、当L足够大时，必可使译码差错小于；反之，当 时，译码差错一定是有限值，而L足够大时，译码几乎必定出错log()LLKmHLXlog()2LLKmHLX5.2 无失真信源编码无失真信源编码定长编码定理含义：log()()LLKmLHHXX码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，当然条件是L足够大 反之，当 时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零()LKHX而当 时，则为临界状态，可能无失真，也可能有失真()LKHX5.2 无失真信源编码无失真信源编码编码效率定义编码效率总是小于1，且最佳编码效率为编码定理从理论上阐明了编码

12、效率接近1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1()LHKX即信源的平均符号熵为HL(X)，采用平均符号码长为 来编码，所得的效率K(),0()LLHHXX()1logLLHKmLX即 只要L足够大5.2 无失真信源编码无失真信源编码5.2.2 变长编码定理在变长编码中，码长K是变化的根据信源各个符号的统计特性，如概率大的符号用短码，概率小的用较长的码，使得编码后平均码长降低，从而提高编码效率。（统计匹配）5.2 无失真信源编码无失真信源编码单个符号变长编码定理：若离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字

13、平均长度满足下列不等式1log)(log)(mXHKmXH5.2 无失真信源编码无失真信源编码 离散平稳无记忆序列变长编码定理： 对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式其中为任意小正数由此式可推导出平均码字长度应满足的不等式用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小得多()()LLHKHXX1loglogLLLLHLHKmmXX5.2 无失真信源编码无失真信源编码编码效率总是小于1，可以用它来衡量各种编码方法的优劣为了衡量各种编码方法与最佳码的差距，定义码的剩余度为 ()()111logLLLHHKKmL

14、XX其中 为平均信息率logLKKmL5.2 无失真信源编码无失真信源编码例5.2 (p.93) 设离散无记忆信源的概率空间为其信源熵为若用二元定长编码(0,1)来构造一个即时码：414321aaPX134()log4log0.811 bit/sym443H X 1,021aa平均码长 1 二元码符号/信源符号K5.2 无失真信源编码无失真信源编码编码效率为811. 0)(KXH输出的信息率为 R0.811 比特/二元码符号长度为2的信源序列进行变长编码（编码方法后面讨论），其即时码如下表 aip(ai)即时码a1a19/160a1a23/1610a2a13/16110a2a21/161115

15、.2 无失真信源编码无失真信源编码293312712331.68751616161616K 二元码符号/信源序列322722KK二元码符号/信源符号码字平均长度为每个符号的平均码长为编码效率961. 027811. 0322信息效率 R20.961 比特/二元码符号5.2 无失真信源编码无失真信源编码L3 R30.985 比特/二元码符号 L4 R40.991 比特/二元码符号 30.98540.9915.2 无失真信源编码无失真信源编码5.2.3 最佳变长编码 凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码为此，将概率大的信源符号编以短码字，将概率小的信

16、源符号编以长码字能获得最佳码的编码方法主要有：n香农（Shannon）编码n费诺（Fano）编码n哈夫曼（Huffman）编码等5.2 无失真信源编码无失真信源编码香农（Shannon）码(1) 将信源消息符号按其出现的概率大小依次排列(2) 确定满足下列不等式的整数码长Ki(3) 为了编成唯一可译码，计算第i个消息的累加概率(4) 将累加概率Pi变换成二进制数(5) 取Pi二进数的小数点后Ki位即为该消息符号的二进制码字nppp211loglog22iiipKp11ikkiapP5.2 无失真信源编码无失真信源编码例5.3 (p.95) 设信源共7个符号，其概率和累加概率如下表所示 信源符号

17、 ai 符号概率(ai)累加概率 Pi -log p(ai)码字长度 Ki 码 字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.170.572.563100a50.150.742.743101a60.100.893.3241110a70.010.996.64711111105.2 无失真信源编码无失真信源编码指数分数十进制二进制2-11/21.5.12-21/22.25.012-31/23.125.0012-41/24.0625.000 12-51/25.03125.000 012-61/26.015625.000 001例如：0.

18、2=.125+.0625+ .001+.0001+=.0011 0.57=.5+.0625+ .1+.0001+=.1001 0.99=.5+.25+.125+.0625+.03125+.015625+ .75 .875 .9375 .96875 .984375 0.1+0.01+0.001+0.0001+0.00001+0.000001+=0.11111105.2 无失真信源编码无失真信源编码14. 3)(71iiiKapK码元/符号831. 014. 361. 2)(KXHR比特/码元 信源熵平均码长信息效率71log2.61iiiH Xp ap a 比特/符号5.2 无失真信源编码无失真

19、信源编码费诺（Fano）编码方法（属于概率匹配编码）(1) 将信源消息符号按其出现的概率大小依次排列：(2) 将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”；(3) 将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。(4) 如此重复，直至每个组只剩下一个信源符号为止。(5) 信源符号所对应的码字即为费诺码。nppp215.2 无失真信源编码无失真信源编码例5.4 (p.96) 对例5.3中的信源进行费诺编码。消息符号ai各 个 消息概率 p(ai)第一次分组第二次分

20、组第三次分组第四次分组二元码字码长Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.011111145.2 无失真信源编码无失真信源编码74. 2)(71iiiKapK 码元/符号 953. 074. 261. 2)(KXHRbit/符号 平均码长信息效率5.2 无失真信源编码无失真信源编码 哈夫曼（Huffman）码(1) 将信源消息符号按其出现的概率大小依次排列，(2) 取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。(

21、3) 对重排后的两个概率最小符号重复步骤(2)的过程。(4) 不断继续上述过程，直到最后两个符号配以0和1为止。(5) 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。nppp21015.2 无失真信源编码无失真信源编码01例5.5 (p.96) 对例5.3中的信源进行哈夫曼编码 0.610.390.200.190.180.170.150.110.260.200.190.180.170.350.260.200.190.390.350.261.00.200.190.180.170.150.100.01a1a2a3a4a5a6a701010101信源ai概率p(ai)码字W

22、i码长Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.0101114平均码长 码元/符号 72. 2)(71iiiKapK信息效率bit/符号96. 072. 261. 2)(KXHR5.2 无失真信源编码无失真信源编码可见，Huffman码的平均码长最小，R最大、编码效率最高值得注意：哈夫曼编码方法得到的码并非唯一的n每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度n对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时

23、，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差5.2 无失真信源编码无失真信源编码例5.6 (p.97) 设有离散无记忆信源1 . 01 . 02 . 02 . 04 . 054321aaaaaPX信源符号ai概率p(ai)码字Wi1码长Ki1码字Wi2码长Ki2a10.411002a20.2012102a30.20003112a40.1001040103a50.10011401135.2 无失真信源编码无失真信源编码0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.

24、40.2 0.2 0.20.1 0.2 0.10.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.20.10101010101010101两种方法给出的Huffman码的平均码长是相同的所以编码效率也是相同的5.2 无失真信源编码无失真信源编码2 . 2)(71iiiKapK 码元/符号 965. 0)(KXH但两种码的质量是不相同的，用码方差描述qiiiilKkapKkE1222)(第一种方法的码方差为36. 121l第二种方法的码方差为16. 022l可见，第二种方法的码方差比第一种方法的码方差小许多，也就是说第二种方法的Huffman码

25、的质量要好5.2 无失真信源编码无失真信源编码 进行哈夫曼编码时，为得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码哈夫曼码是用概率匹配方法进行信源编码n哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；n缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。n前一节讨论的无失真信源编码是属于保熵编码n本节将要讨论的限失真信源编码属于熵压缩编码n其中心任务是：在允许的失真范围内把编码后的信息率压缩到最小n引入有失真的熵压缩编码的原因：(1)保熵编码并非总是必需的；(2)保熵编码并非总是

26、可能的；(3)降低信息率有利于信息的传输和处理，因此有必要进行熵压缩编码，尤其是对于连续信源，熵压缩编码就是必需的了5.3 限失真信源编码定理限失真信源编码定理5.3 限失真信源编码定理限失真信源编码定理信息率失真函数给出了失真小于D时所必须具有的最小信息率R(D)只要信息率大于R(D)，一定可以找到一种编码，使译码后的失真小于D限失真信源编码定理：设离散无记忆信源X的信息率失真函数R(D)，则当信息率RR(D)，只要信源序列长度L足够长，一定存在一种编码方法，其译码失真小于或等于D，为任意小的正数。反之，若RR(D)，则无论采用什么样的编码方法，其译码失真必大于D 如果是二元信源，对于任意小

27、的，每一个信源符号的平均码长满足如下公式)()(DRKDR5.3 限失真信源编码定理限失真信源编码定理限失真定理的意义：在失真限度内使信息率任意接近R(D)的编码方法存在。然而，要使信息率小于R(D)，平均失真一定会超过失真限度D。对于连续平稳无记忆信源，无法进行无失真编码，在限失真情况下，有与上述定理一样的编码定理。限失真信源编码定理只能说明最佳编码是存在的，而具体构造编码方法却一无所知。因而就不能象无失真编码那样从证明过程中引出概率匹配的编码方法。一般只能从优化的思路去求最佳编码。实际上迄今尚无合适的可实现的编码方法可接近R(D)这个界。n实用化技术不同于单纯理论探讨；实用技术不是只追求理

28、论上的性能（如：压缩比），还要考虑工程上的可实现性n为了与复杂的实际信源统计匹配，实际的信源编码方法往往都不是单一的方法，而是多种方法的组合应用n本节简单介绍几种常用的信源编码方法5.4 常用信源编码方法简介常用信源编码方法简介5.4 常用信源编码方法简介常用信源编码方法简介5.4.1 游程编码 在二元序列中，连0段称为0游程 连1段称为1游程二元码序列： 000101110010001 可变换成下列游程序列： 31132131 若已知二元序列以0起始，从游程序列很容易恢复成原来的二元序列 游程序列是多元序列，各长度可按霍夫曼编码或其它方法处理以达到压缩码率的目的5.4 常用信源编码方法简介常

29、用信源编码方法简介n多元序列也存在相应的游程序列，但与二元序列变换所得到的游程序列不同，每个 r 游程的前后均可以是 r 以外的任何符号的游程序列，因此需要插入一个标志来说明后面游程的类别 n多元序列变换成游程序列再进行压缩编码没有多大意义 n游程编码只适用于二元序列，对于多元信源，一般不直接利用游程编码 5.4 常用信源编码方法简介常用信源编码方法简介n冗余位编码，游程编码在多元信源的应用n有许多信源序列中，常存在不少的符号不携带信息，因此处理这些符号的数目和时长外，可以不传n如电话通信和视频通信n这些符号称为冗余位，若能删除，可提高压缩比如下多元序列 x1,x2,xm1,y,y,y,xm1

30、+1,xm1+2,xm2,y,y, 其中x是信息代码，称为信息位，y是冗余位可以用下面序列表示 111，100，000111，111000 x1，x2，xm1，x m1+1，x m1+2x 2， 1表示信息位，0表示冗余位5.4 常用信源编码方法简介常用信源编码方法简介后一个序列是去除了冗余位的信息位序列此变换是一一对应的，可逆此变换将一个含有（大量）冗余位的多元序列变换成了一个二元序列和一个缩短了的多元序列这样，这两个序列就可能用不同的方法来编码，以获得更高的压缩码率比如二元码序列再采用游程编码然后根据信源概率分布在利益Huffman编码5.4 常用信源编码方法简介常用信源编码方法简介5.4

31、.2 算术编码 非分组码的编码方法之一算术码分组码的缺点：不考虑信源符号间的相关性，使得信源编码的匹配原则不能充分满足算术编码的基本思路：从全序列出发，考虑符号之间的依赖关系，将各信源序列的概率映射到0,1 区间上，使每个序列对应这个区间内的一点，也就是一个二进制的小数。这些点把0,1区间分成许多小段，每段的长度等于某一序列的概率。再在段内取一个二进制小数，其长度可与该序列的概率匹配，达到高效率编码的目的算术编码方法与Shannon编码有点类似，只是算术码中的信源序列长度要长的多5.4 常用信源编码方法简介常用信源编码方法简介信源符号集为A=a1,a2,an，概率分布为P(A)=p1,p2,p

32、n信源符号序列 xi(xi1xi2xilxiL)，共有nL种可能序列定义各符号的累积概率（累积分布函数）：显然，P1=0, P2=p1, P3=p1+p2=P2+p2, , Pr+1=Pr+pr, 即 pr =Pr+1-Pr由于Pr+1和Pr都为小于1的正数，可分别对应0,1区间内的两个点，所以pr 就是Pr+1和Pr这两点间的长度11rriiPp a 0(P1) P2 P3 P4 P5 1 p1 p2 p3 p4 5.4 常用信源编码方法简介常用信源编码方法简介不同的符号有不同的小区间，而且彼此互不重叠，因此可以把小区间的任意一点的二进制小数作为该符号的代码（码字）若信源已经发出一个序列S，

33、即信源输出为S状态，后面接着发一个符号r，则符号概率与积累概率的递推关系采用累积概率P(S)表示码字C(S)，符号概率p(S)表示状态区间A(S) ( , )( )( )( , )( )rrC S rC SA S PA S rA S p( , )( )( ), 0,1rP S rP Sp S Pr5.4 常用信源编码方法简介常用信源编码方法简介P(S)把区间0,1)分割成许多小区间，每个小区间的长度等于各序列的概率p(S)，小区间内的任一点可用来代表这序列 0(P1) P2 P3 P4 P5 1 p1 p2 p3 p4 代表大于或等于x的最小整数。把积累概率P(S)写成二进位的小数，取其前L位

34、;如果有尾数，就进位到第L位，这样得到一个数C x )(1logSpL令5.4 常用信源编码方法简介常用信源编码方法简介例如:P(S)0.10110001，p(S)=1/17，则L5， 得C0.10111这个C就可作为S的码字 编码效率很高，当序列很长时，可达到概率匹配。平均代码长度接近S的熵值。可以唯一地译码 5.4 常用信源编码方法简介常用信源编码方法简介符号符号概率pi符号累积概率Pja0.100(1/2)0.000b0.010(1/4)0.100c0.001(1/8)0.110d0.001(1/8)0.111例5.7 (p.105)有四个符号a,b,c,d构成简单序列Sabda，各符号

35、及其对应概率如下表，算术编解码过程如下：5.4 常用信源编码方法简介常用信源编码方法简介设起始状态为空序列，则 A()1，C()0递推得1 . 01 . 01)()(0010)()()(aapAaAPACaC001. 001. 01 . 0)()(01. 01 . 01 . 00)()()(bbpaAabAPaAaCabC5.4 常用信源编码方法简介常用信源编码方法简介000001. 0001. 0001. 0)()(010111. 0111. 0001. 001. 0)()()(ddpabAabdAPabAabCabdC0000001. 01 . 0000001. 0)()(010111. 0