第3章 無失真信源編碼--廖-2013-本科生

1、 第第3章章離散信源無失真編碼第第3章章 離散信源無失真編碼離散信源無失真編碼內(nèi)容提要用盡可能少的符號(hào)來傳輸信源消息，目的是提高傳輸效率，這是信源編碼應(yīng)考慮的問題，這章討論在不允許失真情況下的信源編碼。等長編碼定理給出了等長編碼條件下，其碼長的下限值，變長編碼定理（香農(nóng)第一定理）給出了信源無失真變長編碼時(shí)其碼長的上、下限值。本章還介紹了三種通用信源編碼方法：香農(nóng)編碼法、Fano編碼法和霍夫曼編碼法。z離散信源：消息集X為離散集合。即時(shí)間和幅度取值都離散的信源。31概述 為了實(shí)現(xiàn)高質(zhì)量、高效率的通信，引入了信源編碼和信道編碼。信源編碼和信道編碼主要需要解決以下兩個(gè)問題。提高傳輸效率增強(qiáng)通信的可靠

2、性信息論的研究對(duì)象信息論的研究對(duì)象-通信系統(tǒng)模型，信源，通信系統(tǒng)模型，信源，編碼器，編碼器，信道，信道，譯碼器，信宿。譯碼器，信宿。（1）提高傳輸效率，用盡可能少的信道傳輸符號(hào)來傳遞信源消息，目的是提高傳輸效率，這是信源編碼主要應(yīng)考慮的問題。這里又分兩種情況討論，即允許接收信號(hào)有一定的失真或不允許失真。 綜上所述，提高抗干擾能力往往是以降低信息傳輸效率為代價(jià)的，而為了提高傳輸效率又往往削弱了其抗干擾能力。這樣，設(shè)計(jì)者在取舍之間就要作均衡考慮。（2）增強(qiáng)通信的可靠性如何增加信號(hào)的抗干擾能力，提高傳輸?shù)目煽啃裕@是信道編碼主要考慮的問題。解決這一問題，一般是采用冗余編碼法，賦予信碼自身一定的糾錯(cuò)和

3、檢錯(cuò)能力，只要采取適當(dāng)?shù)男诺谰幋a和譯碼措施，就可使信道傳輸?shù)牟铄e(cuò)概率降到允許的范圍之內(nèi)。信源編碼包括兩個(gè)功能： （1）將信源符號(hào)變換成適合信道傳輸?shù)姆?hào)； （2）壓縮信源冗余度，提高傳輸效率。7由于信源符號(hào)之間存在分布由于信源符號(hào)之間存在分布不均勻和相關(guān)性不均勻和相關(guān)性，使得信源存在使得信源存在冗余度冗余度，信源編碼的主要任務(wù)，信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。就是減少冗余，提高編碼效率。 8信源編碼的基本途徑有兩個(gè)：信源編碼的基本途徑有兩個(gè)：z使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立，使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立，即解除相關(guān)性；即解除相關(guān)性；z使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相

4、使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等，即概率均勻化。等，即概率均勻化。 9信源編碼的基礎(chǔ)是信息論中的兩個(gè)編碼定理：信源編碼的基礎(chǔ)是信息論中的兩個(gè)編碼定理：z無失真編碼定理無失真編碼定理-香農(nóng)第一定律，給出了香農(nóng)第一定律，給出了信源無失真變長編碼時(shí)其碼長的上、下限值。信源無失真變長編碼時(shí)其碼長的上、下限值。z限失真編碼定理限失真編碼定理 無失真編碼無失真編碼只適用于離散信源只適用于離散信源 對(duì)于連續(xù)信源，只能在失真受限制的情況下進(jìn)行對(duì)于連續(xù)信源，只能在失真受限制的情況下進(jìn)行限失真編碼限失真編碼 無失真信源編碼：無失真信源編碼：能夠精確地復(fù)現(xiàn)信源的輸出，保證信源產(chǎn)生的全部信息無損地送給信宿，這時(shí)

5、的信源編碼就是無失真信源編碼。3.1.1信源編碼的相關(guān)概念編碼器3.1圖3.1信源編碼器3.1書上例子：3.1,3.2z 信源編碼有以下3種主要方法：z (1)匹配編碼匹配編碼根據(jù)信源符號(hào)的概率不同，編碼的碼長不同：概率大的信源符號(hào)，所編的代碼短；概率小的信源符號(hào)所編的代碼長，這樣使平均碼長最短。將要講述的香農(nóng)編碼、哈夫曼編碼、費(fèi)諾碼都是概率匹配編碼，都是無失真信源編碼。z (2)變換編碼變換編碼 先對(duì)信號(hào)進(jìn)行變換，從一種信號(hào)空間變換為另一種信號(hào)空間，然后針對(duì)變換后的信號(hào)進(jìn)行編碼。z (3)識(shí)別編碼識(shí)別編碼識(shí)別編碼主要用于印刷或打字機(jī)等有標(biāo)準(zhǔn)形狀的文字符號(hào)和數(shù)據(jù)的編碼，比如中文文字和語音的識(shí)別

6、。z 后兩種信源編碼均為有失真的信源編碼。z 無失真信源編碼主要針對(duì)離散信源，連續(xù)信源在量化編碼的過程中必然會(huì)有量化失真，所以對(duì)連續(xù)信源只能近似地再現(xiàn)信源的消息。 信源編碼可看成是從信源符號(hào)集到碼符號(hào)集的一種映射，即將信源符號(hào)集中的每個(gè)元素（可以是單符號(hào)，也可以是符號(hào)序列）映射成一個(gè)長度為n的碼字。對(duì)于同一個(gè)信源，編碼方法是多種的?！纠?.3】 用u1 ，u2 ，u3，u4表示信源的四個(gè)消息，碼符號(hào)集為0,1，表3-1列出了該信源的幾種不同編碼。表3-1同一信源的幾種不同編碼信源消息各消息概率碼1碼2碼3碼4u1q(u1)000001u2q(u2)1101110u3q(u3)10100010

7、0u4q(u4)11111110003.1.2碼的分類3.變長碼變長碼若碼字集合C中的所有碼字cm (m =1,2,M)，其碼長不都相同，碼碼中的碼字長短不一中的碼字長短不一，稱碼C為變長碼，表3-1中列出的碼3、碼4就是變長碼。2.等長碼等長碼在一組碼字集合C中的所有碼字cm (m =1,2,M)，其碼長都相同，碼中所有碼字的長度，都相同，碼中所有碼字的長度，都相同，則稱這組碼C為等長碼，表3-1中列出的碼1、碼2就碼長n=2等長碼。一般，可以將碼簡單的分成如下幾類：1.二元碼二元碼若碼符號(hào)集為0，1，則碼字就是二元序列，稱為二元碼,二元碼通過二進(jìn)制信道傳輸，這是數(shù)字通信和計(jì)算機(jī)通信中最常見

8、的一種碼，表3-1列出的4種碼都是二元碼。5.非奇異碼非奇異碼從信源消息到碼字的影射是一一對(duì)應(yīng)的，每一個(gè)不同的信源消息都用不同的碼字對(duì)其編碼，若一組碼中所有碼字都不相同，則稱為非奇異碼。例表3-1中的碼2、碼3和碼4都是非奇異碼。4.奇異碼奇異碼對(duì)奇異碼來說，從信源消息到碼字的影射不是一一對(duì)應(yīng)的。若一組碼中有相同的碼字，則稱為奇異碼。例表3-1中的碼1，信源消息u2和u4都用碼字11對(duì)其編碼，因此這種碼就是奇異碼，奇異碼不具備惟一可譯性。擴(kuò)展信源信源編碼器 信源符號(hào) a1,a2,aK 信道符號(hào)（碼符號(hào)）b1, b2,bD消息u1 uN =(u11u12 u1L) (uN1uN2 uNL)N次擴(kuò)

9、展碼字 c1 cN =(c11c12 c1n) (cN1cN2 cNn)圖3-2 N次擴(kuò)展信源編碼器模型原碼的N次擴(kuò)展碼是將信源作N次擴(kuò)展得到的新信源符號(hào)序列u（N）=u1 uN =(u11u12 u1L) (uN1uN2 uNL)，對(duì)應(yīng)碼符號(hào)序列c（N）=c1 cN =(c11c12 c1n) (cN1cN2 cNn)，記集合C (N)=c1(N),c2(N),，C (N)即原碼C的N次擴(kuò)展碼。6.原碼原碼C的的N次擴(kuò)展碼次擴(kuò)展碼原碼C的N次擴(kuò)展碼中的每個(gè)元素是N次擴(kuò)展信源中的序列所對(duì)應(yīng)的N個(gè)碼字組成的序列。草稿對(duì)于定長碼，若原碼是惟一可譯碼，則它的N次擴(kuò)展碼也是惟一可譯的，而對(duì)于變長碼則不

10、盡然，見表3-2。信源消息各消息概率碼1碼2碼3u1q(u1)011u2q(u2)11001u3q(u3)00100001u4q(u4)1110000001表3-2同一信源的幾種不同變長編碼表3-2同一信源的幾種不同變長編碼7.惟一可譯碼惟一可譯碼定義定義3.1 如果碼的任意如果碼的任意N次擴(kuò)展碼都是非奇異碼，則稱該碼為次擴(kuò)展碼都是非奇異碼，則稱該碼為惟一可譯碼。惟一可譯碼。NYYz對(duì)于碼1，由于它的每一個(gè)信源符號(hào)對(duì)應(yīng)不同的碼字，所以它本身是唯一可譯，但將它進(jìn)行二次擴(kuò)展后得到的二次擴(kuò)展碼就不唯一可譯，例如，二次擴(kuò)展碼中的u1u3和u3u1對(duì)應(yīng)同一個(gè)碼字000，u2u4和u4u2對(duì)應(yīng)同一個(gè)碼字1

11、11，因此碼1不是唯一可譯碼。z對(duì)于碼2，碼3不僅本身是唯一可譯碼，進(jìn)行N次擴(kuò)展后得到的N次擴(kuò)展碼也是唯一可譯的，按照定義3.1，碼2、碼3是唯一可譯碼。第三章：離散信源無失真編碼z編碼器碼的分類z1.二元碼：若碼符號(hào)集為0，1，則碼字就是二元序列，稱為二元碼；z2.等長碼：碼中所有碼字的長度，都相同；z3.變長碼：碼中的碼字長短不一；z4.奇異碼：若一組碼中有相同的碼字，則稱為奇異碼；z5.非奇異碼：若一組碼中所有碼字都不相同。z6.原碼C的N次擴(kuò)展碼z7.惟一可譯碼：如果碼的任意N次擴(kuò)展碼都是非奇異碼，則稱該碼為惟一可譯碼。8.即時(shí)碼即時(shí)碼對(duì)于變長碼，又有如下定義定義定義3.2 對(duì)于碼字對(duì)

12、于碼字c = c1 c2 cn, ,稱稱c、 = c1 c2 ci ( (i n) )為碼字為碼字c的字頭（前綴）的字頭（前綴）。定義定義3.3 若碼中任一碼字都不是另一碼字的字頭，稱該碼為異字頭碼（無前綴碼）。碼3是無前綴碼，碼1和2都不是無前綴碼表3-2中碼3，收到“1”后就知道一個(gè)碼字已經(jīng)完結(jié)，無須等待下一個(gè)符號(hào)抵達(dá)，所以無前綴碼能夠即時(shí)譯碼, 稱之為即時(shí)可譯碼，簡稱即時(shí)碼即時(shí)碼。 而對(duì)于碼2，收到“1”后，并不能立即做出判決，就是收到“10”也不能立即做出判決，則還要收到下面的碼元才能做出判決。所以非異字頭碼不能即時(shí)譯碼，稱為非即時(shí)非即時(shí)碼碼，由于非異字頭碼的其中一些碼字是另一些碼字的

13、延長，故也稱延長碼。顯然，即時(shí)碼是惟一可譯碼，而惟一可譯碼不一定是即時(shí)碼。因?yàn)橛行┓羌磿r(shí)碼(延長碼)具有唯一可譯性，但不滿足前綴條件，不能即時(shí)譯碼即時(shí)碼可用樹圖法來構(gòu)造。對(duì)給定碼字的全體集合來說，可以用碼樹來描述它，例子下面。所謂樹，既有根，枝，又有節(jié)點(diǎn)。樹中最頂部的節(jié)點(diǎn)稱為根節(jié)點(diǎn)根節(jié)點(diǎn)，從根出發(fā)向下伸出樹枝，樹枝的數(shù)目等于碼符號(hào)的總數(shù)r。沒有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為葉葉子節(jié)點(diǎn)子節(jié)點(diǎn)。所有根節(jié)點(diǎn)的子節(jié)點(diǎn)稱為一階節(jié)點(diǎn)一階節(jié)點(diǎn)，所有一階節(jié)點(diǎn)的子節(jié)點(diǎn)稱為二階二階節(jié)點(diǎn)節(jié)點(diǎn)，依此類推。n階節(jié)點(diǎn)最多有個(gè)。節(jié)點(diǎn)的階次又稱為節(jié)點(diǎn)的深度深度。當(dāng)某一節(jié)點(diǎn)被安排為碼字后，它就不再繼續(xù)伸枝，此節(jié)點(diǎn)稱為終端節(jié)點(diǎn)，用粗黑點(diǎn)表示。

14、圖3-3 用樹圖法編碼樹根編碼深度u1：1u2：01u3：001u4：000110u1u2u3u411100【例例3.4】 用樹圖法表示表3-2中的碼3，如圖3-3所示（D =2）。復(fù)習(xí)上次課的內(nèi)容：編碼器碼的分類復(fù)習(xí)上次課的內(nèi)容：碼的分類z 1.二元碼：若碼符號(hào)集為0，1，則碼字就是二元序列，稱為二元碼；z 2.等長碼：碼中所有碼字的長度，都相同；z 3.變長碼：碼中的碼字長短不一；z 4.奇異碼：若一組碼中有相同的碼字，則稱為奇異碼；z 5.非奇異碼：若一組碼中所有碼字都不相同。z 6.原碼C的N次擴(kuò)展碼z 7.惟一可譯碼：如果碼的任意N次擴(kuò)展碼都是非奇異碼，則稱該碼為惟一可譯碼。z 8.

15、即時(shí)碼即時(shí)碼:無需考慮后續(xù)的碼符號(hào)就可以從碼符號(hào)序列中譯出碼字，這樣的唯一可譯碼稱為即時(shí)碼即時(shí)碼。8.即時(shí)碼即時(shí)碼對(duì)于變長碼，又有如下定義定義定義3.2 對(duì)于碼字對(duì)于碼字c = c1 c2 cn, ,稱稱c、 = c1 c2 ci ( (i n) )為碼字為碼字c的字頭（前綴）的字頭（前綴）。定義定義3.3 若碼中任一碼字都不是另一碼字的字頭，稱該碼為異字頭碼（無前綴碼）。碼3是無前綴碼，碼1和2都不是無前綴碼表3-2中碼3，收到“1”后就知道一個(gè)碼字已經(jīng)完結(jié)，無須等待下一個(gè)符號(hào)抵達(dá)，所以無前綴碼能夠即時(shí)譯碼, 稱之為即時(shí)可譯碼，簡稱即時(shí)碼即時(shí)碼。 而對(duì)于碼2，收到“1”后，并不能立即做出判決

16、，就是收到“10”也不能立即做出判決，則還要收到下面的碼元才能做出判決。所以非異字頭碼不能即時(shí)譯碼，稱為非即時(shí)非即時(shí)碼碼，由于非異字頭碼的其中一些碼字是另一些碼字的延長，故也稱延長碼。顯然，即時(shí)碼是惟一可譯碼，而惟一可譯碼不一定是即時(shí)碼。因?yàn)橛行┓羌磿r(shí)碼(延長碼)具有唯一可譯性，但不滿足前綴條件，不能即時(shí)譯碼即時(shí)碼可用樹圖法來構(gòu)造。對(duì)給定碼字的全體集合來說，可以用碼樹來描述它，例子下面。所謂樹，既有根，枝，又有節(jié)點(diǎn)。樹中最頂部的節(jié)點(diǎn)稱為根節(jié)點(diǎn)根節(jié)點(diǎn)，從根出發(fā)向下伸出樹枝，樹枝的數(shù)目等于碼符號(hào)的總數(shù)r。沒有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為葉葉子節(jié)點(diǎn)子節(jié)點(diǎn)。所有根節(jié)點(diǎn)的子節(jié)點(diǎn)稱為一階節(jié)點(diǎn)一階節(jié)點(diǎn)，所有一階節(jié)點(diǎn)的子

17、節(jié)點(diǎn)稱為二階二階節(jié)點(diǎn)節(jié)點(diǎn)，依此類推。n階節(jié)點(diǎn)最多有個(gè)。節(jié)點(diǎn)的階次又稱為節(jié)點(diǎn)的深度深度。當(dāng)某一節(jié)點(diǎn)被安排為碼字后，它就不再繼續(xù)伸枝，此節(jié)點(diǎn)稱為終端節(jié)點(diǎn)，用粗黑點(diǎn)表示。圖3-3 用樹圖法編碼樹根編碼深度u1：1u2：01u3：001u4：000110u1u2u3u411100【例例3.4】 用樹圖法表示表3-2中的碼3，如圖3-3所示（D =2）。即時(shí)碼的樹圖構(gòu)造法我們可以用樹圖的形式構(gòu)造即時(shí)碼，如01001111010010001碼4的樹圖10110000101001000碼3的樹圖樹根碼字的起點(diǎn)樹枝數(shù)碼的數(shù)節(jié)點(diǎn)數(shù)碼字的一部分節(jié)數(shù)碼長端點(diǎn)碼字滿樹等長碼非滿樹變長碼書上例子3.59同價(jià)碼同價(jià)碼 同

18、價(jià)碼：同價(jià)碼：每個(gè)碼符號(hào)所占的傳輸時(shí)間都相同的碼。對(duì)同價(jià)碼來說，等長碼中每個(gè)碼字的傳輸時(shí)間相同。而變長碼中的每個(gè)碼字的傳輸時(shí)間不一定相同。電報(bào)中常用的莫爾斯碼是非同價(jià)碼，其碼符號(hào)點(diǎn)（）和劃（-）所占的傳輸時(shí)間不相同。最早的摩爾斯電碼是一些表示數(shù)字的點(diǎn)和劃。數(shù)字對(duì)應(yīng)單詞，需要查找一本代碼表才能知道每個(gè)詞對(duì)應(yīng)的數(shù)。用一個(gè)電鍵可以敲擊出點(diǎn)、劃以及中間的停頓。雖然摩爾斯發(fā)明了電報(bào)，但他缺乏相關(guān)的專門技術(shù)。他與艾爾菲德維爾簽定了一個(gè)協(xié)議，讓他幫自己制造更加實(shí)用的設(shè)備。艾爾菲德維爾構(gòu)思了一個(gè)方案，通過點(diǎn)、劃和中間的停頓，可以讓每個(gè)字元和標(biāo)點(diǎn)符號(hào)彼此獨(dú)立地發(fā)送出去。他們達(dá)成一致，同意把這種標(biāo)識(shí)不同符號(hào)的方案

19、放到摩爾斯的專利中。這就是現(xiàn)在我們所熟知的美式摩爾斯電碼。10.z分組碼和非分組碼分組碼和非分組碼z 定義定義 將信源符號(hào)集中的每個(gè)信源符號(hào) 固定地映射成一個(gè)碼字 Wi，這樣的碼稱為分組碼。分組碼。z 用分組碼對(duì)信源符號(hào)進(jìn)行編碼時(shí)，為了使接收端能夠迅速準(zhǔn)確地將碼譯出，分組碼必須具有一些直觀屬性。與分組碼對(duì)應(yīng)的是非分組碼非分組碼，又稱為樹碼樹碼、樹碼編碼器輸出的碼符號(hào)通常與編碼器的所有信源符號(hào)都有關(guān)。si圖3-5 碼的分類結(jié)構(gòu)圖圖3-5是碼的分類結(jié)構(gòu)圖由上面的結(jié)構(gòu)圖可看出，我們只討論非奇異碼。非奇異碼又分為惟一可譯碼和非惟一可譯碼兩大類，我們只討論惟一可譯碼。3.1.3 平均碼長的計(jì)算平均碼長的

20、計(jì)算對(duì)于變長碼變長碼，碼集C的平均碼長，用符號(hào) 表示，定義為碼C中每個(gè)碼字cm( m = 1,2,，M)其碼長的概率加權(quán)平均值為 (3-1)式中nm是碼字cm所對(duì)應(yīng)的碼字的長度，p (cm )是碼字cm出現(xiàn)的概率。 1()Mmmmnnpc cn對(duì)于等長碼等長碼，由于碼集C中的每個(gè)碼字的碼長都相同，平均碼長就等于每個(gè)碼字的碼長npnpnnmmmmm11)()(c cc c書上例子P54頁，計(jì)算平均碼長n1,n2,n3,n4N次次擴(kuò)展碼擴(kuò)展碼的平均碼長等于擴(kuò)展碼中碼字長度的概率加權(quán)平均值。對(duì)于2次擴(kuò)展碼，有：(3-2)設(shè)nm,ns分別是原信源消息um,us所對(duì)應(yīng)的碼長,cm,cs是um,us所對(duì)應(yīng)

21、的碼字，則式(3-2)中的nm + ns是擴(kuò)展后新的信源序列nmns所對(duì)應(yīng)的碼字cmcs的長度，q(um) q(us)是cmcs出現(xiàn)的概率。n smmssmuquqnnn書上的例子3.63.1.4 信息傳輸速率信息傳輸速率 信道的信息傳輸速率信息傳輸速率為信道單位時(shí)間內(nèi)所傳輸?shù)膶?shí)際信息量。若信息量以比特為單位，時(shí)間以秒為單位，則信息傳輸率定義為： (比特/秒) (3-3)nXtHtR若信息量以比特為單位，時(shí)間以碼元時(shí)間（傳輸一個(gè)碼符號(hào)的時(shí)間）為單位，則信息傳輸率記為 (比特/碼元時(shí)間) (3-4)nXHRDn為編碼后的平均碼長；H(X)為信源熵；式中：t為傳輸一個(gè)碼符號(hào)的時(shí)間?？梢钥闯觯叫?，

22、則越大，信息傳輸率就越高，因此我們感興趣的碼是使平均碼長最短的碼。書上例子。3.7【例例3.8】 給定信源 ，為提高傳輸效率，使平均碼長盡可能短，遵照概率大取碼長短，概率小取碼長長的原則對(duì)上述信源進(jìn)行二進(jìn)制不等長編碼，得到 ，求編碼后的信息傳輸率RD 。16116116116181814141)(76543210 xxxxxxxxXqX1111:101:1110:110:1001:01:1000:00:73625140 xxxxxxxx解：根據(jù)定義如果碼的任意如果碼的任意N次擴(kuò)展碼都是非奇異碼，則稱該碼為次擴(kuò)展碼都是非奇異碼，則稱該碼為惟一可譯碼。惟一可譯碼。(非奇異碼為碼中所有碼字都不相同非

23、奇異碼為碼中所有碼字都不相同)DS2S3:10110,S5S1:10110FS1S4:0110S6S1:0110信源S共有q=4個(gè)信源符號(hào)，s1,s2,s3,s4,現(xiàn)進(jìn)行二元等長編碼，其中碼符號(hào)個(gè)數(shù)r=2，則根據(jù)5.1式可知，存在唯一可譯等長碼的條件是碼長l必須不小于2如果N=1，則，則與前面的5.1式一樣。l/N是平均每個(gè)信源符號(hào)所需要的碼符號(hào)個(gè)數(shù)，表明對(duì)于等長唯一可譯碼，每個(gè)信源符號(hào)至少需要用個(gè)碼符號(hào)來變換,也就是說，每個(gè)信源符號(hào)所需最短的碼長為個(gè)。loglogqlrz當(dāng)r=2（二元碼）時(shí)，logr=1.則式5.2成為z這結(jié)果表明，對(duì)于二元等長唯一可譯碼，每個(gè)信源符號(hào)至少需要用 logq個(gè)

24、二元符號(hào)來變換，也表明對(duì)信源進(jìn)行二元等長不失真編碼時(shí)，每個(gè)信源符號(hào)所需碼長的極限值為logq個(gè)。loglqN定理定理3.1 等長編碼定理等長編碼定理 設(shè)離散無記憶信源S =x1 ，x2 ，xk的熵為H（X），S的L維擴(kuò)展信源為 ，對(duì)信源輸出的L長序列si ，i=1,2,KL 進(jìn)行等長編碼，碼字是長度為n的D進(jìn)制符號(hào)串，當(dāng)滿足條件 ，則L 時(shí)，可使譯碼差錯(cuò)pe n2，實(shí)際上由于要求碼長取整數(shù)，故只能取n1=n2=5。75. 42log27log1loglog1DKLn03. 42log03. 41log)(2DXHLnLnn為碼長-lK信源的符號(hào)個(gè)數(shù)-qD碼符號(hào)個(gè)數(shù)-rn為碼長-lL為信源序列長

25、度-N編碼效率編碼效率定理3.1要求 ，即 ，可看出比值 是一個(gè)小于1的無量綱純數(shù)，定義它為等長編碼的編碼效率，記為 （3-7） DXHLnlogDnXHLlog)(1DnXLHlog)(DnXLHlog)(定理3.1要求，是為了實(shí)現(xiàn)無差錯(cuò)編碼每個(gè)信源符號(hào)所需要的最少碼符號(hào)數(shù)，這是等長碼編碼時(shí)的理論極限。事實(shí)上這種幾乎無失真的代價(jià)是要求信源序列長L , L 大就意味著實(shí)現(xiàn)的復(fù)雜性及譯碼的時(shí)延加大。n為碼長-lL為信源序列長度-ND碼符號(hào)個(gè)數(shù)-rz例子3.9zP583.3 3.3 變長碼及變長編碼定理變長碼及變長編碼定理 3.3.1 變長碼變長碼 對(duì)變長碼的討論是在L足夠大的條件下得到的結(jié)論，當(dāng)

26、L為有限值時(shí)，則總會(huì)帶來一定程度的失真。對(duì)于變長碼，往往在L不是很大的情況下就可編出高效且無失真的碼。 變長碼也要求原碼的任意L次擴(kuò)展碼也是惟一可譯的。變長碼分為即時(shí)碼和延長碼，為保證即時(shí)譯碼，要求變長惟一可譯碼采用即時(shí)碼。 對(duì)于變長碼，要求整個(gè)碼集的平均碼長力求最小，此時(shí)編碼效率最高。對(duì)于給定信源，使平均碼長達(dá)到最小的編碼方法，稱為最最佳編碼佳編碼，得到的碼集稱為最佳碼最佳碼。3.3.2 克拉夫特不等式克拉夫特不等式 定理定理3.2 D進(jìn)制碼字集合C =c1, c2, cM ，碼集中每一cm（m =1,2,M）都是一個(gè)D進(jìn)制符號(hào)串，設(shè)c1, c2, cM 對(duì)應(yīng)的碼長分別是n1,n2, ,nM

27、，則存在唯一可譯碼的充要條件是 (3-10)MmnmD11式（3-10）也稱克拉夫特不等式克拉夫特不等式 定理3.2只是說是存在惟一可譯碼的充要條件，這里強(qiáng)調(diào)的是“存在”，但它并不是唯一可譯碼的充要條件，換言之，惟一可譯碼一定滿足克拉夫特不等式，反之，滿足克拉夫特不等式的碼不一定是惟一可譯碼。575.1 5.1 編碼的定義編碼的定義例例：設(shè)二進(jìn)制碼樹中設(shè)二進(jìn)制碼樹中X (a1， a2 ， a3 ， a4 )，l11，l22，l32，l43，應(yīng)用上述判斷，應(yīng)用上述判斷定理：定理：41223192222218ili因此不存在滿足這種因此不存在滿足這種li的唯一可譯碼的唯一可譯碼。585.1 5.1

28、 編碼的定義編碼的定義a1=1010101a2=01a3=001a4=0001，01，001，000 惟一可譯碼；惟一可譯碼；1，01，101，000 不是惟一可譯碼；不是惟一可譯碼；均滿足克勞夫特不等式均滿足克勞夫特不等式122222332141iKi595.1 5.1 編碼的定義編碼的定義克勞夫特不等式克勞夫特不等式只是用來說明唯一可譯碼是只是用來說明唯一可譯碼是否否存存在，并不能作為唯一可譯碼的判據(jù)。在，并不能作為唯一可譯碼的判據(jù)。 3.3.3 變長編碼定理變長編碼定理 定理定理3.3 給定熵為H（X）的離散無記憶信源，及有D個(gè)元素的碼符號(hào)集，則總可找到一種無失真編碼方法，構(gòu)成惟一可譯碼

29、，其平均碼長 滿足： （3-19）n DXHnDXHlog1log證明：(1)先證下界，即證。 DXHnlog 0logDnXH設(shè)離散無記憶信源含M個(gè)消息，信源熵為H（X），其統(tǒng)計(jì)模型為)()()()(2121MMxqxqxqxxxXqX DnXHlogMmMmmmmmnxqDxqxq11)(log)(1log)(MmMmnmmmmDxqxqxq11log)()(1log)(MmmnmxqDxqm1)(log)(MmmnmxqDxqm1)()(logMmnmD1log則：（利用克拉夫特不等式）log101)(mnxqDm mmnnmDDxq1 0log DnXH當(dāng)即時(shí)，上式中等號(hào)成立，有下界D

30、XHnlog這時(shí)得到的碼就是緊致碼，意味著信源消息概率分布q(xm)必須有(hm為整數(shù))的形式，直接取各消息碼字的碼長nm等于q(xm)所對(duì)應(yīng)的指數(shù)hm即可。這就是例3.8所例舉的情況，在例3.8中，信源分布可以表示為44443322765432102121212121212121)(xxxxxxxxXqX取信源各消息相應(yīng)的碼字的碼長等于其分布概率所對(duì)應(yīng)的指數(shù)，即n0=2n1=2n2=3n3=3n4=4n5=4n6=4n7=4得到的信源編碼就是緊致碼（最佳碼）。mhD 1DXHnlogn DXHlog1n DXHnlog1定理3.3說明，只有滿足否則惟一可譯碼不存在。但平均碼長應(yīng)該小于，這是按

31、應(yīng)盡可能短的要求，這時(shí)得到的碼是最佳碼，其實(shí)，也能找到惟一可譯碼。，才能構(gòu)成惟一可譯碼，332432143212121212181814121)(xxxxxxxxXqXmmmxqnn75. 13221)(814121 )/(75. 12log75. 18log8124log412log21)(log)(41符號(hào)比特iiixqxqXH1)(nXHRD【例例3.10】 信源 對(duì)信源進(jìn)行二進(jìn)制變長編碼，D=2，信源各消息概率恰好表示成D=2的整數(shù)次冪，取碼長等于其冪次，即取n1=1n2=2n3=3n4=3對(duì)信源各消息編碼，得到的碼就是緊致碼，下面計(jì)算RD。（碼元/符號(hào)）因?yàn)樾畔鬏斅蔙D的值小于等于

32、1，所以上述RD =1達(dá)到最大值，得到的碼集為緊致碼。（比特/碼元時(shí)間）2733. 2737. 1322. 3322. 25432154321212121212125. 015. 03 . 01 . 02 . 0)(xxxxxxxxxxXqX55. 2225. 0315. 023 . 041 . 032 . 0n 25. 0log25. 015. 0log15. 03 . 0log3 . 01 . 0log1 . 02 . 0log2 . 0XH 228. 22loglogXHDXH DXHnDXHlog1log【例例3.11】對(duì)下述信源進(jìn)行二進(jìn)制變長編碼， 根據(jù)式(3-20)，即碼長nm 應(yīng)

33、滿足tm nm tm+1 ，tm是消息xm（m=1，2，3，4，5）的2次冪概率所對(duì)應(yīng)的冪次，取x1,x2,x3,x4,x5所對(duì)應(yīng)的碼字的碼長分別為n1=3n2=4n3=2n4=3 n5=2，計(jì)算出平均碼長 熵 =2.228（比特/符號(hào)） 滿足式(3-19) 則有定理定理3.4 變長編碼定理變長編碼定理 ( (Shannon第一定理第一定理) ) 給定熵為H（X）的離散無記憶信源 ，其L次擴(kuò)展信源 的熵記為H（X），給定有D個(gè)元素的碼符號(hào)集，對(duì)擴(kuò)展信源進(jìn)行編碼，總可以找到一種惟一可譯碼，使碼長 滿足 (3-23)()()()(2121MMxqxqxqxxxXqX)()()()(2121LMMq

34、qqqx xx xx xx xx xx xX XX XLnLDXHLnDXHL1loglog定理3.3推廣到L次擴(kuò)展信源，就得到如下定理，即Shannon第一定理記 為信源每個(gè)符號(hào)所對(duì)應(yīng)的平均碼字?jǐn)?shù)，則式(3-23)為 （3-24）nLnL LDXHnDXH1loglogShannon第一定理的物理意義在于：對(duì)信源進(jìn)行編碼，使編碼后的碼集中各碼字盡可能等概分布，如果將這碼集看成為一個(gè)新的信源，這時(shí)新信源所含信息量最大。定義編碼效率編碼效率 (3-26)是一個(gè)無量綱的數(shù)，一般情況下1，在極限情況下=1。 DnXHnDXHloglog講書上例子3.12,3.13,P66 對(duì)于同一種信源，三種編碼法

35、中以香農(nóng)編碼法的編碼效率最低，費(fèi)諾編碼法也不是一種最佳編碼法，但用這種方法有時(shí)候也能找到緊致碼。一般情況下，霍夫曼編碼法得到的平均碼長 最短，即編碼效率 最高。DnXHlogn3.4 3.4 變長碼的編碼方法變長碼的編碼方法香農(nóng)（Shannon）編碼法費(fèi)諾(Fano)編碼法霍夫曼(Huffman)編碼法變長編碼法：705.2 5.2 無失真信源編碼無失真信源編碼最佳變長編碼最佳變長編碼 凡是能載荷一定的信息量，且碼字的平均長凡是能載荷一定的信息量，且碼字的平均長度最短，可分離的變長碼的碼字集合稱為度最短，可分離的變長碼的碼字集合稱為最最佳變長碼佳變長碼。 715.2 5.2 無失真信源編碼無失

36、真信源編碼能能獲得最佳碼的編碼方法主要有：獲得最佳碼的編碼方法主要有：z香農(nóng)（香農(nóng)（Shannon）z費(fèi)諾（費(fèi)諾（Fano）z哈夫曼（哈夫曼（Huffman）等）等725.2 5.2 無失真信源編碼無失真信源編碼香農(nóng)香農(nóng)（Shannon）編碼）編碼z 1. 將信源消息符號(hào)按其出現(xiàn)的概率大小將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列依次排列z 2. 確定滿足下列不等式的整數(shù)碼長確定滿足下列不等式的整數(shù)碼長Ki。nppp211loglog22iiipKp735.2 5.2 無失真信源編碼無失真信源編碼z 為了編成唯一可譯碼，計(jì)算第為了編成唯一可譯碼，計(jì)算第i個(gè)消息的個(gè)消息的累加概率累加概率z 將累加

37、概率將累加概率Pi變換成二進(jìn)制數(shù)。變換成二進(jìn)制數(shù)。z 取取Pi二進(jìn)數(shù)的小數(shù)點(diǎn)后二進(jìn)數(shù)的小數(shù)點(diǎn)后Ki位即為該消息符位即為該消息符號(hào)的二進(jìn)制碼字。號(hào)的二進(jìn)制碼字。 11ikkiapP745.2 5.2 無失真信源編碼無失真信源編碼例例 設(shè)信源共設(shè)信源共7個(gè)符號(hào)消息，其概率和累加概個(gè)符號(hào)消息，其概率和累加概率如下表所示。率如下表所示。-后面有題目后面有題目 【例例3.14】對(duì)給定信源 進(jìn)行D=2進(jìn)制香農(nóng)編碼。01. 010. 015. 017. 018. 019. 02 . 0)(7654321xxxxxxxXqX消息符號(hào)消息符號(hào)ai消息概率消息概率qi-log2qi碼長碼長ni累加概率累加概率碼字

38、碼字cia10.22.3430000a20.192.4130.2001a30.182.4830.39011a40.172.5630.57100a50.152.7430.74101a60.103.3440.891110a70.016.6670.991111110 表3-8香農(nóng)編碼765.2 5.2 無失真信源編碼無失真信源編碼信源消息信源消息符號(hào)符號(hào)ai符號(hào)概符號(hào)概率率(ai)累加概累加概率率Pi-log p(ai)碼字長碼字長度度Ki碼字碼字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.170.572.563100a50.150.7

39、42.743101a60.100.893.3241110a70.010.996.6471111110以消息x5為例，對(duì)其進(jìn)行編碼：計(jì)算出 -logq(x5)=-log0.15=2.74，取整數(shù)n5=3作為x5的碼字的碼長，計(jì)算出消息x1,x2,x3,x4累加概率將0.74變換成二進(jìn)制小數(shù) (0.74)10=(0.1011110)2，取小數(shù)點(diǎn)后面三位101作為 x5的代碼。151574. 017. 018. 019. 02 . 0)(mmxqp計(jì)算該編碼的編碼效率先算出信源熵 =2.61(比特/符號(hào))71)(log)()(mmmxqxqXH平均碼長 =3.14(比特/符號(hào)) 71)(mmmxqn

40、n則編碼效率 831. 0114. 361. 2logDnXH785.2 5.2 無失真信源編碼無失真信源編碼，即117. 017. 04lbklb以以i=4為例，為例，316.526.5244kk，4440.57,0.1001.3,100.pka其累加概率變換成二進(jìn)制：由于所 的編碼為復(fù)習(xí)上一次課的主要內(nèi)容z一、平均碼長的計(jì)算z二、等長編碼定理z三、變長編碼定理 (Shannon第一定理) 3.1.3 平均碼長的計(jì)算平均碼長的計(jì)算對(duì)于變長碼變長碼，碼集C的平均碼長，用符號(hào) 表示，定義為碼C中每個(gè)碼字cm( m = 1,2,，M)其碼長的概率加權(quán)平均值為 (3-1)式中nm是碼字cm所對(duì)應(yīng)的碼

41、字的長度，p (cm )是碼字cm出現(xiàn)的概率。 1()Mmmmnnpc cn對(duì)于等長碼等長碼，由于碼集C中的每個(gè)碼字的碼長都相同，平均碼長就等于每個(gè)碼字的碼長npnpnnmmmmm11)()(c cc c3.1.4 信息傳輸速率信息傳輸速率 信道的信息傳輸速率信息傳輸速率為信道單位時(shí)間內(nèi)所傳輸?shù)膶?shí)際信息量。若信息量以比特為單位，時(shí)間以秒為單位，則信息傳輸率定義為： (比特/秒) (3-3)nXtHtR若信息量以比特為單位，時(shí)間以碼元時(shí)間（傳輸一個(gè)碼符號(hào)的時(shí)間）為單位，則信息傳輸率記為 (比特/碼元時(shí)間) (3-4)nXHRDn為編碼后的平均碼長；H(X)為信源熵；式中：t為傳輸一個(gè)碼符號(hào)的時(shí)間

42、?？梢钥闯觯叫?，則越大，信息傳輸率就越高，因此我們感興趣的碼是使平均碼長最短的碼。信源S共有q=4個(gè)信源符號(hào)，s1,s2,s3,s4,現(xiàn)進(jìn)行二元等長編碼，其中碼符號(hào)個(gè)數(shù)r=2，則根據(jù)5.1式可知，存在唯一可譯等長碼的條件是碼長l必須不小于2如果N=1，則，則與前面的5.1式一樣。l/N是平均每個(gè)信源符號(hào)所需要的碼符號(hào)個(gè)數(shù)，表明對(duì)于等長唯一可譯碼，每個(gè)信源符號(hào)至少需要用個(gè)碼符號(hào)來變換,也就是說，每個(gè)信源符號(hào)所需最短的碼長為個(gè)。loglogqlrz當(dāng)r=2（二元碼）時(shí)，logr=1.則式5.2成為z這結(jié)果表明，對(duì)于二元等長唯一可譯碼，每個(gè)信源符號(hào)至少需要用 logq個(gè)二元符號(hào)來變換，也表明對(duì)信源

43、進(jìn)行二元等長不失真編碼時(shí)，每個(gè)信源符號(hào)所需碼長的極限值為logq個(gè)。loglqN定理定理3.1 等長編碼定理等長編碼定理 設(shè)離散無記憶信源S =x1 ，x2 ，xk的熵為H（X），S的L維擴(kuò)展信源為 ，對(duì)信源輸出的L長序列si ，i=1,2,KL 進(jìn)行等長編碼，碼字是長度為n的D進(jìn)制符號(hào)串，當(dāng)滿足條件 ，則L 時(shí)，可使譯碼差錯(cuò)pe (、為無窮小量)；反之，當(dāng) 時(shí)，則不可能實(shí)現(xiàn)無差錯(cuò)編碼。,21)(LkLSs ss ss s DXHLnlog DXHLnlog定理定理3.1等長編碼定理等長編碼定理編碼效率編碼效率定理3.1要求 ，即 ，可看出比值 是一個(gè)小于1的無量綱純數(shù)，定義它為等長編碼的編碼

44、效率，記為 （3-7） DXHLnlogDnXHLlog)(1DnXLHlog)(DnXLHlog)(定理3.1要求，是為了實(shí)現(xiàn)無差錯(cuò)編碼每個(gè)信源符號(hào)所需要的最少碼符號(hào)數(shù)，這是等長碼編碼時(shí)的理論極限。事實(shí)上這種幾乎無失真的代價(jià)是要求信源序列長L , L 大就意味著實(shí)現(xiàn)的復(fù)雜性及譯碼的時(shí)延加大。n為碼長-lL為信源序列長度-ND碼符號(hào)個(gè)數(shù)-r3.3 3.3 變長碼及變長編碼定理變長碼及變長編碼定理 3.3.1 變長碼變長碼 對(duì)變長碼的討論是在L足夠大的條件下得到的結(jié)論，當(dāng)L為有限值時(shí)，則總會(huì)帶來一定程度的失真。對(duì)于變長碼，往往在L不是很大的情況下就可編出高效且無失真的碼。 對(duì)于變長碼，要求整個(gè)碼

45、集的平均碼長力求最小，此時(shí)編碼效率最高。對(duì)于給定信源，使平均碼長達(dá)到最小的編碼方法，稱為最佳編碼最佳編碼，得到的碼集稱為最佳碼最佳碼。3.3.2 克拉夫特不等式克拉夫特不等式 定理定理3.2 D進(jìn)制碼字集合C =c1, c2, cM ，碼集中每一cm（m =1,2,M）都是一個(gè)D進(jìn)制符號(hào)串，設(shè)c1, c2, cM 對(duì)應(yīng)的碼長分別是n1,n2, ,nM，則存在唯一可譯碼的充要條件是 (3-10)MmnmD11式（3-10）也稱克拉夫特不等式克拉夫特不等式 定理3.2只是說是存在惟一可譯碼的充要條件，這里強(qiáng)調(diào)的是“存在”，但它并不是唯一可譯碼的充要條件，換言之，惟一可譯碼一定滿足克拉夫特不等式，反

46、之，滿足克拉夫特不等式的碼不一定是惟一可譯碼。3.3.3 變長編碼定理變長編碼定理 定理定理3.3 給定熵為H（X）的離散無記憶信源，及有D個(gè)元素的碼符號(hào)集，則總可找到一種無失真編碼方法，構(gòu)成惟一可譯碼，其平均碼長 滿足： （3-19）n DXHnDXHlog1logDXHnlogn DXHlog1n DXHnlog1定理3.3說明，只有滿足否則惟一可譯碼不存在。但平均碼長應(yīng)該小于，這是按應(yīng)盡可能短的要求，這時(shí)得到的碼是最佳碼，其實(shí)，也能找到惟一可譯碼。，才能構(gòu)成惟一可譯碼，定理定理3.4 變長編碼定理變長編碼定理 ( (Shannon第一定理第一定理) ) 給定熵為H（X）的離散無記憶信源

47、，其L次擴(kuò)展信源 的熵記為H（X），給定有D個(gè)元素的碼符號(hào)集，對(duì)擴(kuò)展信源進(jìn)行編碼，總可以找到一種惟一可譯碼，使碼長 滿足 (3-23)()()()(2121MMxqxqxqxxxXqX)()()()(2121LMMqqqqx xx xx xx xx xx xX XX XLnLDXHLnDXHL1loglog定理3.3推廣到L次擴(kuò)展信源，就得到如下定理，即Shannon第一定理記 為信源每個(gè)符號(hào)所對(duì)應(yīng)的平均碼字?jǐn)?shù)，則式(3-23)為 （3-24）nLnL LDXHnDXH1loglogShannon第一定理的物理意義在于：對(duì)信源進(jìn)行編碼，使編碼后的碼集中各碼字盡可能等概分布，如果將這碼集看成為一

48、個(gè)新的信源，這時(shí)新信源所含信息量最大。定義編碼效率編碼效率 (3-26)是一個(gè)無量綱的數(shù)，一般情況下1，在極限情況下=1。 DnXHnDXHloglog 對(duì)于同一種信源，三種編碼法中以香農(nóng)編碼法的編碼效率最低，費(fèi)諾編碼法也不是一種最佳編碼法，但用這種方法有時(shí)候也能找到緊致碼。一般情況下，霍夫曼編碼法得到的平均碼長 最短，即編碼效率 最高。DnXHlogn3.4 3.4 變長碼的編碼方法變長碼的編碼方法香農(nóng)（Shannon）編碼法費(fèi)諾(Fano)編碼法霍夫曼(Huffman)編碼法變長編碼法：945.2 5.2 無失真信源編碼無失真信源編碼香農(nóng)香農(nóng)（Shannon）編碼）編碼z 1. 將信源消息

49、符號(hào)按其出現(xiàn)的概率大小將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列依次排列z 2. 確定滿足下列不等式的整數(shù)碼長確定滿足下列不等式的整數(shù)碼長Ki。nppp211loglog22iiipKp955.2 5.2 無失真信源編碼無失真信源編碼z 計(jì)算第計(jì)算第i個(gè)消息的累加概率個(gè)消息的累加概率z 將累加概率將累加概率Pi變換成二進(jìn)制數(shù)。變換成二進(jìn)制數(shù)。z 取取Pi二進(jìn)數(shù)的小數(shù)點(diǎn)后二進(jìn)數(shù)的小數(shù)點(diǎn)后Ki位即為該消息符位即為該消息符號(hào)的二進(jìn)制碼字。號(hào)的二進(jìn)制碼字。 11ikkiapP 05. 015. 03 . 05 . 0 xxxx)X(PX4321n, 2 , 1j)x(p)x(p1j0iija 1k12l

50、b)x(lbp11 2k74. 21)x(lbp,74. 13 . 0lb)x(lbp222 取取3k74. 31)x(lbp,74. 215. 0lb)x(lbp333 取取5k32. 51)x(lbp,32. 405. 0lb)x(lbp444 取取05. 0lb05. 015. 0lb15. 03 . 0lb3 . 05 . 0lb5 . 0)x(lbp)x(p)X(H41iii )symbol/bit(648. 1 )symbol/bit( 8 . 1505. 0315. 023 . 015 . 0k )x (pK41iii %6 .91916. 08 . 1648. 1K)X(H 信

51、息傳輸率=1035.2 5.2 無失真信源編碼無失真信源編碼費(fèi)諾費(fèi)諾編碼方法編碼方法費(fèi)諾編碼屬于概率匹配編碼費(fèi)諾編碼屬于概率匹配編碼(1)將信源消息符號(hào)按其出現(xiàn)的概率大小依將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列：次排列： (2)將依次排列的信源符號(hào)按概率值分為兩將依次排列的信源符號(hào)按概率值分為兩大組，使兩個(gè)組的概率之和近于相同，大組，使兩個(gè)組的概率之和近于相同，并對(duì)各組賦予一個(gè)二進(jìn)制碼元并對(duì)各組賦予一個(gè)二進(jìn)制碼元“0”和和“1”。nppp211045.2 5.2 無失真信源編碼無失真信源編碼(3)將每一大組的信源符號(hào)進(jìn)一步再分成兩將每一大組的信源符號(hào)進(jìn)一步再分成兩組，使劃分后的兩個(gè)組的概率之

52、和近于組，使劃分后的兩個(gè)組的概率之和近于相同，并又賦予兩個(gè)組一個(gè)二進(jìn)制符號(hào)相同，并又賦予兩個(gè)組一個(gè)二進(jìn)制符號(hào)“0”和和“1”。(4)如此重復(fù)，直至每個(gè)組只剩下一個(gè)信源如此重復(fù)，直至每個(gè)組只剩下一個(gè)信源符號(hào)為止。符號(hào)為止。(5)信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾碼。信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾碼。1055.2 5.2 無失真信源編碼無失真信源編碼例例 對(duì)以下信源進(jìn)行費(fèi)諾編碼對(duì)以下信源進(jìn)行費(fèi)諾編碼。 消息符消息符號(hào)號(hào)ai各 個(gè) 消各 個(gè) 消息概率息概率 p(ai)第一次第一次分組分組第二次第二次分組分組第三次第三次分組分組第四次第四次分組分組二元二元碼字碼字碼長碼長Kia10.2000002a20.19

53、100103a30.1810113a40.1710102a50.15101103a60.101011104a70.011111141065.2 5.2 無失真信源編碼無失真信源編碼74. 2)(71iiiKapK953. 074. 261. 2)(KXHR碼元碼元/符號(hào)符號(hào)bit/符號(hào)符號(hào)1095.2 5.2 無失真信源編碼無失真信源編碼 哈夫曼哈夫曼編碼方法編碼方法(1)將信源消息符號(hào)按其出現(xiàn)的概率大小依次將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列，排列，(2)取兩個(gè)概率最小的字母分別配以取兩個(gè)概率最小的字母分別配以0和和1兩個(gè)兩個(gè)碼元，并將這兩個(gè)概率相加作為一個(gè)新字碼元，并將這兩個(gè)概率相加作

54、為一個(gè)新字母的概率，與未分配的二進(jìn)符號(hào)的字母重母的概率，與未分配的二進(jìn)符號(hào)的字母重新排隊(duì)。新排隊(duì)。nppp21Thesixthweek1105.2 5.2 無失真信源編碼無失真信源編碼(3)對(duì)重排后的兩個(gè)概率最小符號(hào)重復(fù)步驟對(duì)重排后的兩個(gè)概率最小符號(hào)重復(fù)步驟(2)的過程。的過程。(4)不斷繼續(xù)上述過程，直到最后兩個(gè)符號(hào)配不斷繼續(xù)上述過程，直到最后兩個(gè)符號(hào)配以以0和和1為止。為止。(5)從最后一級(jí)開始，向前返回得到各個(gè)信源從最后一級(jí)開始，向前返回得到各個(gè)信源符號(hào)所對(duì)應(yīng)的碼元序列，即相應(yīng)的碼字。符號(hào)所對(duì)應(yīng)的碼元序列，即相應(yīng)的碼字?！纠?.15.15】 對(duì)例3.14給出的 信源進(jìn)行費(fèi)諾編碼01.

55、010. 015. 017. 018. 019. 02 . 0)(7654321xxxxxxxXqX （1）將信源消息分成兩個(gè)子集 x1，x2，x3和 x4，x5，x6，x7，兩個(gè)子集的和概率分別為0.2+0.19+0.18=0.57與0.17+0.15+0.10+0.01=0.43，賦予第一個(gè)子集碼元“0”，賦予第二個(gè)子集碼元“1”；（2）又將子集分成和概率盡可能接近相等的兩個(gè)子集，分別賦予第一個(gè)子集碼元“0”，賦予第二個(gè)子集碼元“1”；（3）一直進(jìn)行下去，直到每個(gè)子集僅含一個(gè)消息為止。該編碼的編碼效率：例3.14中已算出信源熵 H（X）=2.61（比特/符號(hào)）平均碼長 =2.7471)(m

56、mmxqnn則編碼效率： 935. 0174. 261. 2logDnXH1125.2 5.2 無失真信源編碼無失真信源編碼例例 對(duì)以下信源進(jìn)行哈夫曼編碼對(duì)以下信源進(jìn)行哈夫曼編碼 信源符號(hào)信源符號(hào)ai概率概率p(ai) 碼字碼字Wi碼長碼長Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.01011141135.2 5.2 無失真信源編碼無失真信源編碼0.20 0.20 0.26 0.35 0.39 0.61 1.00.19 0.19 0.20 0.26 0.35 0.390.18 0.18 0.19 0.20 0

57、.260.17 0.17 0.18 0.190.15 0.15 0.170.10 0.110.010101010101011145.2 5.2 無失真信源編碼無失真信源編碼碼元碼元/符號(hào)符號(hào)bit/符號(hào)符號(hào)72. 2)(71iiiKapK96. 072. 261. 2)(KXHR1215.2 5.2 無失真信源編碼無失真信源編碼哈夫曼編碼方法得到的碼并哈夫曼編碼方法得到的碼并非唯一非唯一的的z每次對(duì)信源縮減時(shí)，賦予信源最后兩個(gè)概每次對(duì)信源縮減時(shí)，賦予信源最后兩個(gè)概率最小的符號(hào)，用率最小的符號(hào)，用0和和1是可以任意的，所是可以任意的，所以可以得到不同的哈夫曼碼，但不會(huì)影響以可以得到不同的哈夫曼碼

58、，但不會(huì)影響碼字的長度。碼字的長度。1225.2 5.2 無失真信源編碼無失真信源編碼z對(duì)信源進(jìn)行縮減時(shí)，兩個(gè)概率最小的符對(duì)信源進(jìn)行縮減時(shí)，兩個(gè)概率最小的符號(hào)合并后的概率與其它信源符號(hào)的概率號(hào)合并后的概率與其它信源符號(hào)的概率相同相同時(shí)，這兩者在縮減信源中進(jìn)行概率時(shí)，這兩者在縮減信源中進(jìn)行概率排序，其位置放置次序是可以任意的，排序，其位置放置次序是可以任意的，故會(huì)得到不同的哈夫曼碼。此時(shí)將影響故會(huì)得到不同的哈夫曼碼。此時(shí)將影響碼字的長度，一般將碼字的長度，一般將合并的概率放在上合并的概率放在上面面，這樣可獲得，這樣可獲得較小的碼方差較小的碼方差。1235.2 5.2 無失真信源編碼無失真信源編碼

59、例例 設(shè)有離散無記憶信源設(shè)有離散無記憶信源1 . 01 . 02 . 02 . 04 . 054321aaaaaPX1245.2 5.2 無失真信源編碼無失真信源編碼信源符號(hào)信源符號(hào)ai概率概率p(ai)碼字碼字Wi1碼長碼長Ki1碼字碼字Wi2碼長碼長Ki2a10.411002a20.2012102a30.20003112a40.1001040103a50.1001140113 其有兩種哈夫曼編碼方法：其有兩種哈夫曼編碼方法：1255.2 5.2 無失真信源編碼無失真信源編碼0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.2 0.10.

60、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.101010101010101011265.2 5.2 無失真信源編碼無失真信源編碼2 . 2)(71iiiKapK為：二者平均碼長相等，均 碼元碼元/符號(hào)符號(hào)965. 0)(KXH1275.2 5.2 無失真信源編碼無失真信源編碼qiiiilKkapKkE1222)(36. 121l16. 022l1285.2 5.2 無失真信源編碼無失真信源編碼 進(jìn)行哈夫曼編碼時(shí)，為得到進(jìn)行哈夫曼編碼時(shí)，為得到碼方差碼方差最小的碼，最小的碼，應(yīng)使合并的信源符號(hào)位于縮減信源序列應(yīng)使合并的信源符號(hào)位于縮減