信息论与编码第5章(2)

1、信源编码1无失真信源编码无失真信源编码实现实现无失真无失真的信源编码的信源编码,要求要求: 信源符号信源符号X1 X2Xl XL是一一对应的是一一对应的 码字码字Y1 Y2Yk YKKLLlog M1Llog m _K 能够无失真或能够无失真或无差错地从无差错地从Y恢复恢复X,也就是能正确地进行反也就是能正确地进行反变换或译码变换或译码 ; 传送传送Y时所需要的时所需要的信息率最小信息率最小信息率最小信息率最小就是找到一种编码方式使就是找到一种编码方式使最小最小信源编码器信源编码器码表码表信源信源信道信道XYL长序列长序列K长码字长码字2定长编码定理定长编码定理定长编码定理定长编码定理： 由由

2、L个符号组成的、每个符号的熵为个符号组成的、每个符号的熵为HL(X)的无记忆的无记忆平稳信源符号序列平稳信源符号序列X1XlXL,可用可用 KL个符号个符号Y1YkYKL(每个符号有每个符号有m种可能值种可能值)进行定长编码。进行定长编码。则当则当L足够大时足够大时,必可使译码差错小于必可使译码差错小于;反之反之,当当时时,译码差错一定是有限值译码差错一定是有限值,而当而当L足够大时足够大时,译码几乎译码几乎必定出错必定出错)(logXLLHmLK2)(logXLLHmLK3定长编码定理定长编码定理当编码器容许的输出信息率当编码器容许的输出信息率,也就是当每个信源符号所必须也就是当每个信源符号

3、所必须输出的码长是输出的码长是 时时,只要只要 K HL(X) ,这种编码器一定可以做到几乎这种编码器一定可以做到几乎无失真无失真,也就是收端的译码差错概率接近于零也就是收端的译码差错概率接近于零,条件是所取的符号数条件是所取的符号数L足够大足够大。将定理的条件改写成将定理的条件改写成KL logm LHL(X) H(X)其中：其中：左边：左边：KL长码字所能携带的最大信息，长码字所能携带的最大信息，右边：右边：L长信源序列携带的信息量。长信源序列携带的信息量。4 (X) 定长编码定理定长编码定理, 0 HL(X)HL(X) 对定长编码对定长编码,若要实现几乎无失真编码若要实现几乎无失真编码,

4、则信源长度则信源长度必须满足必须满足:22L 2(X) EI(xi) H(X)2 信源序列的自信息方差信源序列的自信息方差为了衡量编码效果为了衡量编码效果,定义定义编码效率编码效率：最佳编码效率最佳编码效率：5H L(X) 变长编码定理变长编码定理 1H(X)log m K 离散平稳无记忆序列变长编码定理离散平稳无记忆序列变长编码定理 对于平均符号熵为对于平均符号熵为HL(X)的离散平稳无记忆信源的离散平稳无记忆信源,必存在一种必存在一种 无失真编码方法无失真编码方法,使平均信息率使平均信息率 K 满足不等满足不等式式HL(X) K HL(X) 单个符号变长编码定理单个符号变长编码定理： 若一

5、离散无记忆信源的符号熵为若一离散无记忆信源的符号熵为H(X),每个信源符号用每个信源符号用m进进制码元进行变长编码制码元进行变长编码,一定存在一种无失真编码方法一定存在一种无失真编码方法,其码其码字平均长度满足下列不等式字平均长度满足下列不等式: H(X)log m H L(X)log mL编码效率的下界编码效率的下界： H L(X) K65.2.3最佳变长编码最佳变长编码最佳码最佳码：对于某一信源和某一码符号集来说对于某一信源和某一码符号集来说,若有一唯一可若有一唯一可译码译码,其其平均码长平均码长小于所有其他唯一可译码的平均小于所有其他唯一可译码的平均长度。长度。 方法：方法：将概率大的信

6、源符号编以短的码字。概率小将概率大的信源符号编以短的码字。概率小的符号编以长的码字，这样使得平均码字长度最短。的符号编以长的码字，这样使得平均码字长度最短。 主要有：主要有： 香农香农（Shannon） 费诺费诺（Fano） 哈夫曼哈夫曼（Huffma ）7香农编码香农编码香农第一定理指出了香农第一定理指出了平均码长平均码长与与信源信源之间的关系之间的关系,同同时也指出了可以通过编码使平均码长达到时也指出了可以通过编码使平均码长达到极限值极限值,这这是一个很重要的极限定理。是一个很重要的极限定理。 香农第一定理指出香农第一定理指出,选择每个码字的长度选择每个码字的长度Ki满足下式：满足下式：或

7、或: log2 p(xi) Ki log2 p(xi)+1 就可以得到这种码。就可以得到这种码。 这种编码方法称为这种编码方法称为香农编码香农编码8二进制香农码的二进制香农码的编码步骤编码步骤如下：如下：香农编码香农编码将信源符号按概率从大到小的顺序排列将信源符号按概率从大到小的顺序排列, p1 p2 pn确定满足下列不等式的整数确定满足下列不等式的整数Ki,log2 pi Ki log2 pi+1计算第计算第i个码字的累加概率，个码字的累加概率，将将Pi用二进制表示用二进制表示,并取并取小数点后小数点后Ki位位作为符号作为符号ai的的编编码码。9信源消息信源消息符号符号ai符号概率符号概率P

8、(ai)累加概率累加概率Pi logP(ai)码字长码字长度度Ki码字码字a10.2002.343000a20.190.202.413001a30.180.392.483011a40.170.572.563100a50.150.742.743101a60.100.893.3441110a70.010.996.6671111110例例 有一个信源共有有一个信源共有7个符号，其概率及其累加和如下表所示：个符号，其概率及其累加和如下表所示：香农编码香农编码10()2.610.831/3.14H XRK比特 码元 由上表可以看出，一共有由上表可以看出，一共有5个三位的代码组，各代个三位的代码组，各代码

9、组之间至少有一位数字不相同，故是唯一可译码。码组之间至少有一位数字不相同，故是唯一可译码。还可以判断出，这还可以判断出，这7个代码组都属于即时码。个代码组都属于即时码。 平均码长平均码长 平均信息传输速率平均信息传输速率香农编码香农编码1( )3.14niiiKp x k 码元/符号11 香农编码方法特点香农编码方法特点：由于由于ki总是进一取整，香农编码方法不一定是最佳的；总是进一取整，香农编码方法不一定是最佳的；由于第一个消息符号的累加概率总是为由于第一个消息符号的累加概率总是为0，故它对应，故它对应的码字总是的码字总是0、00、000、00的式样；的式样；码字集合是唯一的，且为即时码；码

10、字集合是唯一的，且为即时码；先有码长再有码字；先有码长再有码字；对于一些信源，编码效率不高，冗余度稍大，因此对于一些信源，编码效率不高，冗余度稍大，因此其实用性受到较大限制。其实用性受到较大限制。结论结论12费诺编码费诺编码费诺编码属于费诺编码属于概率匹配概率匹配编码编码 。 编码步骤如下：编码步骤如下： 将概率按从大到小的顺序排列将概率按从大到小的顺序排列,令令p(x1) p(x2) p(xn) 按编码进制数将概率分组按编码进制数将概率分组,使使每组概率尽可能接近每组概率尽可能接近或或相等相等。如编二进制码就分成两组。如编二进制码就分成两组,编编m进制码就分成进制码就分成m组。组。 给每一组

11、分配一位码元。给每一组分配一位码元。 将每一分组再按同样原则划分将每一分组再按同样原则划分,重复步骤重复步骤2和和3,直至概直至概率不再可分为止。率不再可分为止。13xi符号概符号概率率编码编码码字码字码长码长x10.3200002x20.221012x30.1810102x40.16101103x50.081011104x60.04111114费诺编码费诺编码14 费诺编码特点费诺编码特点：概率大，则分解的次数小；概率小概率大，则分解的次数小；概率小, 则分解的次数多。则分解的次数多。这符合最佳编码原则。这符合最佳编码原则。码字集合是唯一的。码字集合是唯一的。分解完了，码字出来了，码长也有了

12、。分解完了，码字出来了，码长也有了。因此，费诺编码方法又称为子集分解法。因此，费诺编码方法又称为子集分解法。费诺编码方法比较适合于每次分组概率都很接近的信费诺编码方法比较适合于每次分组概率都很接近的信结论结论源，特别是对每次分组概率都相等的信源进行编码时，源，特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。可达到理想的编码效率。 r 元费诺码元费诺码: 前面讨论的费诺码是二元费诺码，对前面讨论的费诺码是二元费诺码，对r元费诺码，元费诺码，与二元费诺码编码方法相同，只是每次分组时应将符号分成概与二元费诺码编码方法相同，只是每次分组时应将符号分成概率分布接近的率分布接近的r个组。

13、个组。15哈夫曼编码哈夫曼编码哈夫曼编码也是用码树来分配各符号的码字。哈夫曼编码也是用码树来分配各符号的码字。哈夫曼哈夫曼(Huffman)编码是一种效率比较高的编码是一种效率比较高的变长无失变长无失真信源编码真信源编码方法。方法。霍夫曼编码及其变种，在压缩编码领域中应用的非常广泛霍夫曼编码及其变种，在压缩编码领域中应用的非常广泛数字图像：数字图像：JPEGJPEG运动图像：运动图像：MPEG2MPEG2、H.261H.261、H.263 H.263 16哈夫曼哈夫曼编码的编码的步骤步骤如下：如下： 将信源消息符号按其出现的概率大小依次排列将信源消息符号按其出现的概率大小依次排列 p(x1)p

14、(x2) p(xn)取两个取两个概率最小概率最小的字母分别配以的字母分别配以0和和1两码元两码元,并将这并将这两个两个概率相加概率相加作为一个作为一个新字母新字母的概率的概率,与未分配的二与未分配的二进符号的字母进符号的字母重新排队重新排队。 对重排后的两个概率最小符号重复步骤的过程。对重排后的两个概率最小符号重复步骤的过程。不断继续上述过程不断继续上述过程,直到最后两个符号直到最后两个符号配以配以0和和1为止。为止。 从最后一级开始从最后一级开始,向前返回向前返回得到各个信源符号所对应得到各个信源符号所对应的码元序列的码元序列,即相应的码字。即相应的码字。哈夫曼编码哈夫曼编码17信源符信源符

15、 符号概符号概号号xi 率率p(xi)编码过程编码过程x1x2x3x4x5x60.200.190.180.170.150.10 x70.01010.20 0.260.19 0.200.18 0.190.17 0.180.15 0 0.170.11 10.35 0.390.26 0.35 00.20 0 0.26 10 0.19 110.61 00.39 1码字码字101100000101001100111例例5-7 设单符号离散无记忆信源如下设单符号离散无记忆信源如下, ,要求对信源要求对信源编编二进制二进制哈夫曼码。编码过程如下表哈夫曼码。编码过程如下表哈夫曼编码哈夫曼编码18熵熵H(X)

16、0.2log0.20.19log0.190.18log0.180.17log0.170.15log0.150.10log0.100.01log0.01 2.61 平均码长为平均码长为0.220.1920.1830.1730.1530.1040.0142.72编码效率编码效率哈夫曼编码哈夫曼编码71()iiiKp a K19哈夫曼的哈夫曼的编法并不编法并不唯一唯一。 每次对缩减信源两个概率最小的符号每次对缩减信源两个概率最小的符号分配分配“0”和和“1”码元是码元是任意任意的的,所以可得到不同的码字。所以可得到不同的码字。 不同的码元分配不同的码元分配,得到的具体码字不同得到的具体码字不同,但码

17、长但码长Ki不变不变,平均码长也不变平均码长也不变,所以没有本质区别；所以没有本质区别； 缩减信源时缩减信源时,若合并后的新符号概率与其他符号概率若合并后的新符号概率与其他符号概率相等相等,从编码方法上来说从编码方法上来说,这几个符号的这几个符号的次序可任意排次序可任意排列列,编出的码都是正确的编出的码都是正确的,但得到的但得到的码字不相同码字不相同。 不同的编法得到的码字长度不同的编法得到的码字长度Ki也不尽相同。也不尽相同。哈夫曼编码哈夫曼编码20哈夫曼编码哈夫曼编码信源符号信源符号ai概率概率p(ai)码字码字Wi1码长码长Ki1码字码字Wi2码长码长Ki2a10.411002a20.2

18、012102a30.20003112a40.1001040103a50.100114011321哈夫曼编码哈夫曼编码22K1 p(xi)Ki 0.4 1 0.2 2 0.2 3 0.1 4 2 2.2K2 p(xi)Ki 0.4 2 0.2 2 2 0.1 3 2 2.2单符号信源编二进制哈夫曼码单符号信源编二进制哈夫曼码, ,编码效率主要决定编码效率主要决定于信源熵和平均码长之比于信源熵和平均码长之比。 对相同的信源编码对相同的信源编码, ,其熵是一样的其熵是一样的, ,采用不同的编法采用不同的编法, ,得到的平均码长可能不同。得到的平均码长可能不同。 平均码长越短平均码长越短, ,编码效率

19、就越高。编码效率就越高。编法一的平均码长为编法一的平均码长为5i 1编法二的平均码长为编法二的平均码长为5i 1两种编法的平均码长相同两种编法的平均码长相同, ,所以编码效率相同。所以编码效率相同。哈夫曼编码哈夫曼编码23讨论：哪种方法更好？讨论：哪种方法更好？ 定义码字长度的方差定义码字长度的方差2 2：第二种编码方法的码长方差要小许多。第二种编码方法的码长方差要小许多。 第二种编码方法的码长变化较小第二种编码方法的码长变化较小, ,比较接近于平均码比较接近于平均码长。长。哈夫曼编码哈夫曼编码24哈夫曼编码哈夫曼编码第一种方法编出的第一种方法编出的5个码字有个码字有4种不同的码长；种不同的码

20、长； 第二种方法编出的码长只有两种不同的码长；第二种方法编出的码长只有两种不同的码长； 第二种编码方法更简单、更容易实现第二种编码方法更简单、更容易实现,所以更好。所以更好。 结论：结论： 在哈夫曼编码过程中在哈夫曼编码过程中,对缩减信源符号按概率由大到小的顺序对缩减信源符号按概率由大到小的顺序重新排列时重新排列时,应使合并后的应使合并后的新符号尽可能排在靠前新符号尽可能排在靠前的位置的位置,这样这样可使合并后的新符号重复编码次数减少可使合并后的新符号重复编码次数减少,使短码得到充分利用。使短码得到充分利用。 特征特征:是是一种分组码一种分组码：各个信源符号都被映射成一组固定次序的码：各个信源

21、符号都被映射成一组固定次序的码符号符号. .是是一种一种唯唯一可解码一可解码：任何码符号序列只能以一种方式译码：任何码符号序列只能以一种方式译码. .是是一种即时码一种即时码：由于代表信源符号的节点都是终端节点，因：由于代表信源符号的节点都是终端节点，因此其编码不可能是其它终端节点对应的编码的前缀，哈夫曼编此其编码不可能是其它终端节点对应的编码的前缀，哈夫曼编码所得的码字一定是即时码。码所得的码字一定是即时码。25由于哈夫曼码是一类无失真信源最佳变长码，就是说在由于哈夫曼码是一类无失真信源最佳变长码，就是说在研究这类无失真信源编码时认为信道传输是理想的，是研究这类无失真信源编码时认为信道传输是

22、理想的，是不产生差错的，然而实际信道中总是存在噪声的，不产生差错的，然而实际信道中总是存在噪声的，噪声噪声引入后必然要破坏变长码的结构引入后必然要破坏变长码的结构。同时由于变长码是不。同时由于变长码是不加同步的码，无法自动清洗所产生的影响，所以必然要加同步的码，无法自动清洗所产生的影响，所以必然要产生误差的扩散，即产生误差的扩散，即噪声所影响的不仅是被干扰的码元，噪声所影响的不仅是被干扰的码元，而是一直要扩散下去影响后面一系列码元而是一直要扩散下去影响后面一系列码元。以至于在低以至于在低信噪比下无法工作。信噪比下无法工作。目前对这类误差扩散还没有特别有效的克服方法，在工目前对这类误差扩散还没有

23、特别有效的克服方法，在工程上一般哈夫曼码只能程上一般哈夫曼码只能适合于高信噪比的优质信道适合于高信噪比的优质信道，以，以减小误差扩散带来的影响。同时工程上还常常采用减小误差扩散带来的影响。同时工程上还常常采用定期定期清洗清洗，以牺牲编码效率来达到限制误差扩散的目的。另，以牺牲编码效率来达到限制误差扩散的目的。另一种方法是一种方法是加检错纠错码加检错纠错码。误差扩散问题误差扩散问题26由于绝大多数信源其消息是不等概率的，因而编成的变由于绝大多数信源其消息是不等概率的，因而编成的变长码长度也是不相等的，这必然导致信源输出速率是变长码长度也是不相等的，这必然导致信源输出速率是变化的，然而在实际信道中

24、传送的信息率是固定不变化的。化的，然而在实际信道中传送的信息率是固定不变化的。因而因而信源与信道之间必然存在一个速率匹配信源与信道之间必然存在一个速率匹配问题。问题。解决该问题的办法，在工程上一般解决该问题的办法，在工程上一般采用缓冲存储器的方采用缓冲存储器的方法以达到变速输入，恒速输出法以达到变速输入，恒速输出。但是这个缓存器的容量。但是这个缓存器的容量选取显然与输入变速特性即信源统计特性和编码方法，选取显然与输入变速特性即信源统计特性和编码方法，以及输出速率密切相关。这是一个需要在实际的工程设以及输出速率密切相关。这是一个需要在实际的工程设计中进一步深入探讨的问题。计中进一步深入探讨的问题

25、。速率匹配问题速率匹配问题27香农码、费诺码、哈夫曼码香农码、费诺码、哈夫曼码都考虑了信源的都考虑了信源的统计特性统计特性,使使经常出现的信源符号对应较短的码字经常出现的信源符号对应较短的码字,使信源的平均码长使信源的平均码长缩短缩短,从而实现了对信源的压缩；从而实现了对信源的压缩；香农码香农码有系统的、有系统的、唯唯一一的编码方法的编码方法,但在很多情况下编码但在很多情况下编码效率不是很高；效率不是很高；费诺费诺码和码和哈夫曼哈夫曼码的编码方法都码的编码方法都不不唯唯一一；费诺码比较适合于对分组概率相等或接近的信源编码费诺码比较适合于对分组概率相等或接近的信源编码,费费诺码也可以编诺码也可以

26、编m进制码进制码,但但m越大越大,信源的符号数越多信源的符号数越多,可能可能的编码方案就越多的编码方案就越多,编码过程就越复杂编码过程就越复杂,有时短码未必能得有时短码未必能得到充分利用；到充分利用；哈夫曼码哈夫曼码对信源的统计特性没有特殊要求对信源的统计特性没有特殊要求,编码效率比较编码效率比较高高,对编码设备的要求也比较简单对编码设备的要求也比较简单,因此因此综合性能优于综合性能优于香农香农码和费诺码。码和费诺码。总结总结28信源符号信源符号X有有8种消息，概率为种消息，概率为(1/2,1/4,1/8, 1/16, 1/32,1/64,1/128,1/128)(1)用香农编码编成二进变长码

27、，计算其编码效率。用香农编码编成二进变长码，计算其编码效率。(2)用费诺编码编成二进变长码，计算其编码效率。用费诺编码编成二进变长码，计算其编码效率。(3)用哈夫曼编码编成二进变长码，计算其编码效率。用哈夫曼编码编成二进变长码，计算其编码效率。举例举例29解解: 二进制香农编码二进制香农编码xix1x2x3x4x5x6x7x8p(xi)0.500.250.1250.06250.031250.0156250.00781250.0078125pa(xj)0.000. 500.750.8750. 93750. 968750. 9843750. 9921875ki12345677码字码字0(0.000

28、)210(0.100)2110(0.110)21110(0.1110)211110(0.11110)2111110(0.111110)21111110(0.111110)21111111(0.1111111)2举例举例30 xiP(xi)S1S2S3S4S5S6S7码字x11/200 x21/41010 x31/810110 x41/16101110 x51/321011110 x61/6410111110 x71/12810111110 x81/1281111111费诺编码费诺编码举例举例31码字码字字长（1/2）（1/4）（1/8）（1/16）（1/32）（1/64）哈夫曼编码哈夫曼编码举

29、例举例32习题习题5-12作业作业335.3限失真信源编码定理限失真信源编码定理在很多实际信源中在很多实际信源中,特别在模拟的连续信源中特别在模拟的连续信源中,无无失真要求是完全没有必要的失真要求是完全没有必要的,而且也是达不到的。而且也是达不到的。在实际中限失真信源在实际中限失真信源编码编码是具有现实意义的是具有现实意义的。信息率失真函数给出了失真小于信息率失真函数给出了失真小于D时所必须具有的最时所必须具有的最小信息率小信息率R(D)；只要信息率大于；只要信息率大于R(D)，一定可以找，一定可以找到一种编码，使译码后的失真小于到一种编码，使译码后的失真小于D。 34限失真信源编码定理限失真

30、信源编码定理限失真信源编码定理：限失真信源编码定理： 设离散无记忆信源设离散无记忆信源X的信息率失真函数为的信息率失真函数为R(D) , 当信息率当信息率 RR(D)时时,只要信源序列长度只要信源序列长度 L 足够长足够长,一定存在一种编码方法一定存在一种编码方法,其译码失真小于或等于其译码失真小于或等于D+,为任意小的正数；为任意小的正数； 反之反之,若若RR(D) ,则无论采用什么样的编码方法则无论采用什么样的编码方法,其其译码失真必大于译码失真必大于D。 如是二元信源如是二元信源,则对于任意小的则对于任意小的0,每一个信源符号每一个信源符号的平均码长满足如下公式：的平均码长满足如下公式：

31、R(D) K R(D) 35限失真信源编码定理限失真信源编码定理限失真信源编码定理限失真信源编码定理只能说明只能说明最佳编码最佳编码是存在的，是存在的，而具体构造编码方法却一无所知。因而就不能象无而具体构造编码方法却一无所知。因而就不能象无损编码那样从证明过程中引出概率匹配的编码方法。损编码那样从证明过程中引出概率匹配的编码方法。一般只能从优化的思路去求最佳编码。实际上迄今一般只能从优化的思路去求最佳编码。实际上迄今尚无合适的可实现的编码方法可接近尚无合适的可实现的编码方法可接近R(D)这个界。这个界。 36对信源编码定理的统一理解对信源编码定理的统一理解 定长信源无失真编码定理：定长信源无失

32、真编码定理： 变长信源无失真编码定理（香农第一定理）：变长信源无失真编码定理（香农第一定理）： 保真度准则下的信源编码定理（香农第三定理）：保真度准则下的信源编码定理（香农第三定理）： 从编码信息率的角度，当从编码信息率的角度，当时，则信源编码无失真或失真可控。时，则信源编码无失真或失真可控。()loglog()KRKH XLHmmXL lo()l(gg)oLLKRKHmHLXLmX()RR D ()()RH XRR D或37常用信源编码常用信源编码香农编码、费诺编码、哈夫曼编码主要是针对香农编码、费诺编码、哈夫曼编码主要是针对无记无记忆忆信源，属于信源，属于无失真信源编码无失真信源编码； 当信源有记忆时上述编码效率不高；当信源有记忆时上述编码效率不高； 游程编码游程编码 算术编码算术编码预测编码预测编码变换编码变换编码385.4.1 游程编码游程编码游程游程： 数字序列中连续出现相同符号的一段。数字序列中连续出现相同符号的一段。二元序列的游程：只有二元序列的游程：只有“0”和和“1”