離散信源無失真編碼

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

2、目的是提高傳輸效率，這是信源編碼主要應(yīng)考慮的問題。這里又分兩種情況討論，即允許接收信號(hào)有一定的失真或不允許失真。 綜上所述，提高抗干擾能力往往是以降低信息傳輸效率為代價(jià)的，而為了提高傳輸效率又往往削弱了其抗干擾能力。這樣，設(shè)計(jì)者在取舍之間就要作均衡考慮。（2）增強(qiáng)通信的可靠性如何增加信號(hào)的抗干擾能力，提高傳輸?shù)目煽啃?，這是信道編碼主要考慮的問題。解決這一問題，一般是采用冗余編碼法，賦予信碼自身一定的糾錯(cuò)和檢錯(cuò)能力，只要采取適當(dāng)?shù)男诺谰幋a和譯碼措施，就可使信道傳輸?shù)牟铄e(cuò)概率降到允許的范圍之內(nèi)。信源編碼包括兩個(gè)功能： （1）將信源符號(hào)變換成適合信道傳輸?shù)姆?hào)； （2）壓縮信源冗余度，提高傳輸效率。

3、a1, a2,aK為信源符號(hào)集，序列中每一個(gè)符號(hào)uml都取自信源符號(hào)集。b1 ，b2 ，bD是適合信道傳輸?shù)腄個(gè)符號(hào)，用作信源編碼器的編碼符號(hào)。編碼輸出碼字cm =cm1cm2 cmn， c mkb1 ，b2 ，bD k =1,2, ,n ，n表示碼字長(zhǎng)度，簡(jiǎn)稱碼長(zhǎng)碼長(zhǎng) 信源符號(hào) a1,a2,aK 信道符號(hào)（碼符號(hào)）b1, b2,bD圖3-1 信源編碼器模型信源信源 信源編碼器信源編碼器 一般來說，信源編碼可歸納為如圖3-1所示的模型。消息ui =ui1ui2 uiL 碼字ci =ci1ci2 cin 信源編碼可看成是從信源符號(hào)集到碼符號(hào)集的一種映射，即將信源符號(hào)集中的每個(gè)元素（可以是單符號(hào)，

4、也可以是符號(hào)序列）映射成一個(gè)長(zhǎng)度為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)101000100u4q(u4)11111110003.1.1碼的分類3.變長(zhǎng)碼變長(zhǎng)碼若碼字集合C中的所有碼字cm (m =1,2,M)，其碼長(zhǎng)不都相同，稱碼C為變長(zhǎng)碼，表3-1中列出的碼3、碼4就是變長(zhǎng)碼。2.等長(zhǎng)碼等長(zhǎng)碼在一組碼字集合C中的所有碼字cm (m =1,2

5、,M)，其碼長(zhǎng)都相同，則稱這組碼C為等長(zhǎng)碼，表3-1中列出的碼1、碼2就碼長(zhǎng)n=2等長(zhǎng)碼。一般，可以將碼簡(jiǎn)單的分成如下幾類：1.二元碼二元碼若碼符號(hào)集為0，1，則碼字就是二元序列，稱為二元碼,二元碼通過二進(jìn)制信道傳輸，這是數(shù)字通信和計(jì)算機(jī)通信中最常見的一種碼，表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ì)其編碼，因此這種碼就是奇異碼，奇異碼不具備惟

6、一可譯性。擴(kuò)展信源信源編碼器 信源符號(hào) a1,a2,aK 信道符號(hào)（碼符號(hào)）b1, b2,bD消息u1 uN =(u11u12 u1L) (uN1uN2 uNL)N次擴(kuò)展碼字 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ò)

7、展碼原碼C的N次擴(kuò)展碼中的每個(gè)元素是N次擴(kuò)展信源中的序列所對(duì)應(yīng)的N個(gè)碼字組成的序列。對(duì)于定長(zhǎng)碼，若原碼是惟一可譯碼，則它的N次擴(kuò)展碼也是惟一可譯的，而對(duì)于變長(zhǎng)碼則不盡然，見表3-2。信源消息各消息概率碼1碼2碼3u1q(u1)011u2q(u2)11001u3q(u3)00100001u4q(u4)1110000001表3-2同一信源的幾種不同變長(zhǎng)編碼表3-2同一信源的幾種不同變長(zhǎng)編碼7.惟一可譯碼惟一可譯碼定義定義3.1 如果碼的任意如果碼的任意N次擴(kuò)展碼都是非奇異碼，則稱該碼為次擴(kuò)展碼都是非奇異碼，則稱該碼為惟一可譯碼。惟一可譯碼。8.即時(shí)碼即時(shí)碼對(duì)于變長(zhǎng)碼，又有如下定義定義定義3.2 對(duì)

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

9、碼是惟一可譯碼，而惟一可譯碼不一定是即時(shí)碼。即時(shí)碼可用樹圖法來構(gòu)造。圖3-3 用樹圖法編碼樹根編碼深度u1：1u2：01u3：001u4：000110u1u2u3u411100【例例3.4】 用樹圖法表示表3-2中的碼3，如圖3-3所示（D =2）。碼奇異碼非奇異碼非惟一可譯碼惟一可譯碼變長(zhǎng)碼等長(zhǎng)碼即時(shí)碼延長(zhǎng)碼圖3-5 碼的分類結(jié)構(gòu)圖圖3-5是碼的分類結(jié)構(gòu)圖由上面的結(jié)構(gòu)圖可看出，將碼分為奇異碼和非奇異碼兩大類，我們只討論非奇異碼。非奇異碼又分為惟一可譯碼和非惟一可譯碼兩大類，我們只討論惟一可譯碼。3.1.2 平均碼長(zhǎng)的計(jì)算平均碼長(zhǎng)的計(jì)算對(duì)于變長(zhǎng)碼變長(zhǎng)碼，碼集C的平均碼長(zhǎng)，用符號(hào) 表示，定義為碼

10、C中每個(gè)碼字cm( m = 1,2,，M)其碼長(zhǎng)的概率加權(quán)平均值為 (3-1)式中nm是碼字cm所對(duì)應(yīng)的碼字的長(zhǎng)度，p (cm )是碼字cm出現(xiàn)的概率。 Mmmmpnn1)(c cn對(duì)于等長(zhǎng)碼等長(zhǎng)碼，由于碼集C中的每個(gè)碼字的碼長(zhǎng)都相同，平均碼長(zhǎng)就等于每個(gè)碼字的碼長(zhǎng)npnpnnmmmmm11)()(c cc cN次次擴(kuò)展碼擴(kuò)展碼的平均碼長(zhǎng)等于擴(kuò)展碼中碼字長(zhǎng)度的概率加權(quán)平均值。對(duì)于2次擴(kuò)展碼，有：(3-2)設(shè)nm,ns分別是原信源消息um,us所對(duì)應(yīng)的碼長(zhǎng),cm,cs是um,us所對(duì)應(yīng)的碼字，則式(3-2)中的nm + ns是擴(kuò)展后新的信源序列nmns所對(duì)應(yīng)的碼字cmcs的長(zhǎng)度，q(um) q(u

11、s)是cmcs出現(xiàn)的概率。n smmssmuquqnnn3.1.3 信息傳輸速率信息傳輸速率 信道的信息傳輸速率信息傳輸速率為信道單位時(shí)間內(nèi)所傳輸?shù)膶?shí)際信息量。若信息量以比特為單位，時(shí)間以秒為單位，則信息傳輸率定義為： (比特/秒) (3-3)nXtHtR若信息量以比特為單位，時(shí)間以碼元時(shí)間（傳輸一個(gè)碼符號(hào)的時(shí)間）為單位，則信息傳輸率記為 (比特/碼元時(shí)間) (3-4)nXHRDn為編碼后的平均碼長(zhǎng)；H(X)為信源熵；式中：t為傳輸一個(gè)碼符號(hào)的時(shí)間?！纠?.8】 給定信源 ，為提高傳輸效率，使平均碼長(zhǎng)盡可能短，遵照概率大取碼長(zhǎng)短，概率小取碼長(zhǎng)長(zhǎng)的原則對(duì)上述信源進(jìn)行二進(jìn)制不等長(zhǎng)編碼，得到 ，求

12、編碼后的信息傳輸率RD 。16116116116181814141)(76543210 xxxxxxxxXqX1111:101:1110:110:1001:01:1000:00:73625140 xxxxxxxx （比特/符號(hào)） （碼元/符號(hào)） (比特/碼元時(shí)間) 75. 22log75. 2161log161481log81241log412XH75. 21614481324122n 175. 275. 2nXHRD3.2 等長(zhǎng)碼及等長(zhǎng)編碼定理等長(zhǎng)碼及等長(zhǎng)編碼定理考慮對(duì)一簡(jiǎn)單信源S進(jìn)行等長(zhǎng)編碼，信源符號(hào)集有K個(gè)符號(hào)，碼符號(hào)集含D個(gè)符號(hào)，碼字長(zhǎng)度記為n。要得到惟一可譯碼，必須滿足下式K D n

13、對(duì)單符號(hào)信源S的L次擴(kuò)展信源S（L）進(jìn)行等長(zhǎng)編碼，要得到長(zhǎng)為n的惟一可譯碼，必須滿足K L D n （3-5）對(duì)式（3-5）兩邊取對(duì)數(shù)，得 （3-6）DKLnloglog 對(duì)于那些出現(xiàn)概率極小的字符序列不予編碼，這樣可以減小平均碼長(zhǎng)，當(dāng)然這樣會(huì)帶來一定的失真。下面的定理3.1 將證明，當(dāng)滿足一定的條件時(shí)，在L 時(shí)，失真pe 0定理定理3.1 等長(zhǎng)編碼定理等長(zhǎng)編碼定理 設(shè)離散無記憶信源S =x1 ，x2 ，xk的熵為H（X），S的L維擴(kuò)展信源為 ，對(duì)信源輸出的L長(zhǎng)序列si ，i=1,2,KL 進(jìn)行等長(zhǎng)編碼，碼字是長(zhǎng)度為n的D進(jìn)制符號(hào)串，當(dāng)滿足條件 ，則L 時(shí)，可使譯碼差錯(cuò)pe n2，實(shí)際上由于要

14、求碼長(zhǎng)取整數(shù)，故只能取n1=n2=5。75. 42log27log1loglog1DKLn03. 42log03. 41log)(2DXHLnLn編碼效率編碼效率定理3.1要求 ，即 ，可看出比值 是一個(gè)小于1的無量綱純數(shù)，定義它為等長(zhǎng)編碼的編碼效率，記為 （3-7） DXHLnlogDnXHLlog)(1DnXLHlog)(DnXLHlog)(定理3.1要求，是為了實(shí)現(xiàn)無差錯(cuò)編碼每個(gè)信源符號(hào)所需要的最少碼符號(hào)數(shù)，這是等長(zhǎng)碼編碼時(shí)的理論極限。事實(shí)上這種幾乎無失真的代價(jià)是要求信源序列長(zhǎng)L , L 大就意味著實(shí)現(xiàn)的復(fù)雜性及譯碼的時(shí)延加大。3.3 3.3 變長(zhǎng)碼及變長(zhǎng)編碼定理變長(zhǎng)碼及變長(zhǎng)編碼定理 3

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

16、進(jìn)制符號(hào)串，設(shè)c1, c2, cM 對(duì)應(yīng)的碼長(zhǎng)分別是n1,n2, ,nM，則存在唯一可譯碼的充要條件是 (3-10)MmnmD11式（3-10）也稱克拉夫特不等式克拉夫特不等式 定理3.2只是說是存在惟一可譯碼的充要條件，這里強(qiáng)調(diào)的是“存在”，但它并不是唯一可譯碼的充要條件，換言之，惟一可譯碼一定滿足克拉夫特不等式，反之，滿足克拉夫特不等式的碼不一定是惟一可譯碼。3.3.3 變長(zhǎng)編碼定理變長(zhǎng)編碼定理 定理定理3.3 給定熵為H（X）的離散無記憶信源，及有D個(gè)元素的碼符號(hào)集，則總可找到一種無失真編碼方法，構(gòu)成惟一可譯碼，其平均碼長(zhǎng) 滿足： （3-19）n DXHnDXHlog1log證明：(1)

17、先證下界，即證。 DXHnlog 0logDnXH設(shè)離散無記憶信源含M個(gè)消息，信源熵為H（X），其統(tǒng)計(jì)模型為)()()()(2121MMxqxqxqxxxXqX DnXHlogMmMmmmmmnxqDxqxq11)(log)(1log)(MmMmnmmmmDxqxqxq11log)()(1log)(MmmnmxqDxqm1)(log)(MmmnmxqDxqm1)()(logMmnmD1log則：（利用克拉夫特不等式）1)(mnxqDm mmnnmDDxq1 0log DnXH當(dāng)即時(shí)，上式中等號(hào)成立，有下界DXHnlog這時(shí)得到的碼就是緊致碼，意味著信源消息概率分布q(xm)必須有(hm為整數(shù))

18、的形式，直接取各消息碼字的碼長(zhǎng)nm等于q(xm)所對(duì)應(yīng)的指數(shù)hm即可。這就是例3.8所例舉的情況，在例3.8中，信源分布可以表示為44443322765432102121212121212121)(xxxxxxxxXqX取信源各消息相應(yīng)的碼字的碼長(zhǎng)等于其分布概率所對(duì)應(yīng)的指數(shù)，即n0=2n1=2n2=3n3=3n4=4n5=4n6=4n7=4得到的信源編碼就是緊致碼（最佳碼）。mhD 1DXHnlog1 DXHnlog1 mtmDxq1)(1mmmmmtnttn之間總有一整數(shù)不是整數(shù)，但在（為整數(shù)時(shí)) 1,mmmmtttt(2) 再證上界：采用構(gòu)造性證明：只要構(gòu)造一種惟一可譯碼，滿足先將概率q(

19、xm)寫成即可。的形式（tm不一定為整數(shù)）。構(gòu)造碼，使碼長(zhǎng)滿足：綜合兩種情況，碼長(zhǎng)nm滿足：tm nm tm+1(3-20)將式(3-21)代入(3-20)右邊的不等式nm tm+1，即有：將式(3-21)代入(3-20)右邊的不等式nm tm+1，即有：1log)(logDxqnmm對(duì)左式兩邊求統(tǒng)計(jì)平均值得：1log)(log)()(11DxqxqnxqmMmmmMmm DXHnlog1DXHnlogn DXHlog1n DXHnlog1定理3.3說明，只有滿足否則惟一可譯碼不存在。但平均碼長(zhǎng)應(yīng)該小于，這是按應(yīng)盡可能短的要求，這時(shí)得到的碼是最佳碼，其實(shí)，也能找到惟一可譯碼。，才能構(gòu)成惟一可譯

20、碼，332432143212121212181814121)(xxxxxxxxXqXmmmxqnn75. 13221)(814121 )/(75. 12log75. 18log8124log412log21)(log)(41符號(hào)比特iiixqxqXH1)(nXHRD【例例3.10】 信源 對(duì)信源進(jìn)行二進(jìn)制變長(zhǎng)編碼，D=2，信源各消息概率恰好表示成D=2的整數(shù)次冪，取碼長(zhǎng)等于其冪次，即取n1=1n2=2n3=3n4=3對(duì)信源各消息編碼，得到的碼就是緊致碼，下面計(jì)算RD。（碼元/符號(hào)）因?yàn)樾畔鬏斅蔙D的值小于等于1，所以上述RD =1達(dá)到最大值，得到的碼集為緊致碼。（比特/碼元時(shí)間）2733.

21、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)制變長(zhǎng)編碼， 根據(jù)式(3-20)，即碼長(zhǎng)nm 應(yīng)滿足tm nm tm+1 ，tm是消息xm（m=1，2，3，4，5）的2次冪概率所對(duì)

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

23、glog記 為信源每個(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 對(duì)于同一種信源，三種編碼法中以香農(nóng)編碼法的編碼效率最低，費(fèi)諾編碼法也不是一種最佳編碼法，但用這種方法有時(shí)候也能找到緊致碼。一般情況下，霍夫曼編碼法得到的平均碼長(zhǎng) 最短，即編碼效率 最高。DnXHlogn3.4 3.4

24、 變長(zhǎng)碼的編碼方法變長(zhǎng)碼的編碼方法香農(nóng)（Shannon）編碼法費(fèi)諾(Fano)編碼法霍夫曼(Huffman)編碼法變長(zhǎng)編碼法：3.4.1香農(nóng)編碼法二進(jìn)制香農(nóng)編碼法其碼長(zhǎng)的取值范圍: -logq(xm)nm-logq (xm)+1 （3-30）記離散信源 ，給定有D個(gè)元素的碼符號(hào)集，對(duì)信源進(jìn)行變長(zhǎng)編碼，將各消息概率q(xm) (m = 1, 2, , M) 寫成如下的形式： )()()()(2121MMxqxqxqxxxXqXmtmDxq1)(取碼長(zhǎng)nm(m=1,2,M) 滿足： tm nm tm+1 （3-28）香農(nóng)編碼法具體步驟如下， （4）計(jì)算出第m個(gè)消息的累加概率 ，再將pi變換成二進(jìn)制

25、小數(shù)，取小數(shù)點(diǎn)后面nm位作為第m個(gè)消息的代碼組11)(immixqp（3）根據(jù)式（3-31）：-logq(xm)nm-logq (xm)+1（-logq(xm)為整數(shù)時(shí)取等號(hào)），計(jì)算出每個(gè)消息的二進(jìn)制代碼的長(zhǎng)度nm。 （2）計(jì)算出各消息的 -logq(xm)值，m=1,2,M； （1）將信源發(fā)出的M個(gè)消息，按其概率遞減順序進(jìn)行排列【例例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碼長(zhǎng)碼長(zhǎng)ni累加概率累加概率碼字碼字cia10.22.

26、3430000a20.192.4130.2001a30.182.4830.39011a40.172.5630.57100a50.152.7430.74101a60.103.3440.891110a70.016.6670.991111110 表3-8香農(nóng)編碼以消息x5為例，對(duì)其進(jìn)行編碼：計(jì)算出 -logq(x5)=-log0.15=2.74，取整數(shù)n5=3作為x5的碼字的碼長(zhǎng)，計(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)(mmxq

27、p計(jì)算該編碼的編碼效率先算出信源熵 =2.61(比特/符號(hào))71)(log)()(mmmxqxqXH平均碼長(zhǎng) =3.14(比特/符號(hào)) 71)(mmmxqnn則編碼效率 831. 0114. 361. 2logDnXH3.4.2 費(fèi)諾費(fèi)諾編碼法編碼法 費(fèi)諾編碼法的具體步驟如下： （1）信源發(fā)出的M個(gè)消息，按其概率遞減順序進(jìn)行排列，把消息集 x1,x2,x3, , xM按其概率大小分解成兩個(gè)子集，使兩個(gè)子集的概率之和盡可能接近相等，把第一個(gè)子集編碼為“0”，第二個(gè)子集編碼為“1”，作為代碼組的第一個(gè)碼元； （2）對(duì)子集做第二次分解，同樣分解成兩個(gè)子集，并使兩個(gè)子集的概率盡可能接近相等，再把第一個(gè)

28、子集編碼為“0”，第二個(gè)子集編碼為“1”，作為代碼組的第二個(gè)碼元；（3）如此一直進(jìn)行下去，直到各子集僅含一個(gè)消息為止（4）將逐次分解過程當(dāng)中得到的碼元排列起來就是各消息的代碼。【例例3.15.15】 對(duì)例3.14給出的 信源進(jìn)行費(fèi)諾編碼01. 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）又將子集分成

29、和概率盡可能接近相等的兩個(gè)子集，分別賦予第一個(gè)子集碼元“0”，賦予第二個(gè)子集碼元“1”；（3）一直進(jìn)行下去，直到每個(gè)子集僅含一個(gè)消息為止。該編碼的編碼效率：例3.14中已算出信源熵 H（X）=2.61（比特/符號(hào)）平均碼長(zhǎng) =2.7471)(mmmxqnn則編碼效率： 935. 0174. 261. 2logDnXH消息符號(hào)xi消息概率q(xm)第一次分解所得碼元第二次分解所得碼元第三次分解所得碼元第四次分解所得碼元碼字cm碼長(zhǎng)nix10.200002x20.19100103x30.1810113x40.1710102x50.15101103 x60.101011104x70.01111114

30、表3-9費(fèi)諾編碼3.4.3 霍夫曼霍夫曼編碼法編碼法 設(shè)信源消息數(shù)M2，記概率分布為，存在D進(jìn)制惟一可譯碼C =c1,c2,cM，對(duì)應(yīng)的碼長(zhǎng)分別為n1,n2,nM ，不失一般性，設(shè)q(x1) q(x2 ) q(xM )，則C = c c1, c c2, ,c cM是最佳碼必須具備如下兩條性質(zhì)：1.1. n1n2 nM；2.2.最后（最長(zhǎng)）的D*個(gè)碼字，它們具有相同的前綴c，惟一的區(qū)別是最后一位碼符號(hào)不同，可將這D*個(gè)最長(zhǎng)的碼字分別表示為c0，c1，c（D*-1）其中 D*2，3，D（3-31）且 D*= M mod(D-1)（3-32）)()()()(2121MMxqxqxqxxxXqX定理定

31、理3.5假定C * =c1, c2, cM-D，c 為最佳碼，對(duì)應(yīng)概率Q*=q(x1), q(x2), q(xM-D*)，q* 其中q*可記為q*=q(x M-D*+1)+ q (xM-D*+2)+ +q(xM)且概率分布滿足q(x1) q(x2 ) q(x M-D*) q (xM-D*+1 ) q(xM )則對(duì)應(yīng)概率分布為 Q =q(x1 ) , q(x2 ) , , q(xM-D*), q(x M-D*+1),q(xM) 的最佳碼是C =c1 , c2 , c cM-D*, c c0, c c1, , c c( D*-1) （3）將上述概率之和作為一新消息的概率，與余下的消息一起組成一新的信源，再按概率遞減順序重新排列，如果概率之和與原信源的某個(gè)概率相等，則把概率之和排在上面，這樣可使合并消息重復(fù)編碼的次數(shù)減少，使短碼得到充分利用。 （4）如此一直進(jìn)行下去，直到兩個(gè)合并消息的概率之和為1； （5）從最后一步驟開始，沿編碼逆程取下各步驟得到的碼符號(hào)，如此構(gòu)成的碼符號(hào)序列即為對(duì)