無失真信源編碼及其定理

第四章無失真信源編碼4.1編碼器及碼的分類4.2等長(zhǎng)碼4.4等長(zhǎng)信源編碼定理4.5變長(zhǎng)碼4.6變長(zhǎng)信源編碼定理4.7霍夫曼碼和其它編碼方法4.8幾種實(shí)用的無失真信源編碼小結(jié)第四章無失真信源編碼本章的重、難點(diǎn)內(nèi)容1、理解等長(zhǎng)碼和等長(zhǎng)信源編碼定理2、理解和掌握變長(zhǎng)碼及變長(zhǎng)碼編碼定理3、理解Huffman編碼、費(fèi)諾碼、香農(nóng)碼4、了解幾種實(shí)用的無失真信源編碼方法，包括（MH編碼、算術(shù)編碼、LZ碼）第四章無失真信源編碼編碼的意義：通信的基本問題：如何高速、高質(zhì)地傳送信息。高速和高質(zhì)＝魚和熊掌。編碼討論的問題：（1）質(zhì)量一定，如何提高信息傳輸速度（提高編碼效率或壓縮比）----信源編碼（本章討論問題）（2）信道傳輸速度一定，如何提高信息傳輸質(zhì)量（抗干擾能力）----信道編碼（下一章討論）引言信源編碼：以提高通信有效性為目的的編碼。通常通過壓縮信源的冗余度來實(shí)現(xiàn)。采用的一般方法是壓縮每個(gè)信源符號(hào)的平均比特?cái)?shù)或信源的碼率。即同樣多的信息用較少的碼率傳送，使單位時(shí)間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。引言信道編碼：是以提高信息傳輸?shù)目煽啃詾槟康牡木幋a。通常通過增加信源的冗余度來實(shí)現(xiàn)。采用的一般方法是增大碼率/帶寬。與信源編碼正好相反。密碼：是以提高通信系統(tǒng)的安全性為目的的編碼。通常通過加密和解密來實(shí)現(xiàn)。從信息論的觀點(diǎn)出發(fā)，“加密”可視為增熵的過程，“解密”可視為減熵的過程。引言信源編碼理論是信息論的一個(gè)重要分支，其理論基礎(chǔ)是信源編碼的兩個(gè)定理。無失真信源編碼定理：是離散信源/數(shù)字信號(hào)編碼的基礎(chǔ)；限失真信源編碼定理：是連續(xù)信源/模擬信號(hào)編碼的基礎(chǔ)。引言信源編碼的分類：離散信源編碼、連續(xù)信源編碼和相關(guān)信源編碼三類。離散信源編碼：獨(dú)立信源編碼，可做到無失真編碼；連續(xù)信源編碼：獨(dú)立信源編碼，只能做到限失真信源編碼；相關(guān)信源編碼：非獨(dú)立信源編碼。4.1編碼器及碼的分類編碼：信息的組織方式編碼的實(shí)質(zhì)：對(duì)信源的原始符號(hào)按一定的數(shù)學(xué)規(guī)則進(jìn)行變換。編碼的目的：信源編碼：提高信息傳輸?shù)挠行孕诺谰幋a：提高信息傳輸?shù)目煽啃?/p>

本章不考慮干擾問題4.1編碼器及碼的分類無失真編碼器結(jié)構(gòu)框圖幾個(gè)術(shù)語：信源符號(hào)：信源輸入碼符號(hào)(碼元)：編碼器信源碼字符號(hào)集4.1編碼器及碼的分類碼字Wi：由xj(j=1,2,…,r)組成的長(zhǎng)度為li

的序列，Wi與si一一對(duì)應(yīng)。碼字長(zhǎng)度(碼長(zhǎng))：

Wi的長(zhǎng)度li編碼器：將信源符號(hào)si變換成Wi的設(shè)備信源編碼信源編碼：把信源符號(hào)si映射為碼字Wi的過程。無失真編碼：映射是一一對(duì)應(yīng)、可逆的。信源編碼基本思想：盡可能縮短出現(xiàn)概率大的信源符號(hào)的碼字4.1編碼器及碼的分類碼的分類二元碼：若碼符號(hào)集X＝{0，1}，所得碼字為一些二元序列，則稱二元碼。[在二元信道中傳輸]等長(zhǎng)碼（固定長(zhǎng)度碼）：若一組碼中所有碼字的長(zhǎng)度都相同(即li=l,i=1,…,q)，則稱為等長(zhǎng)碼。變長(zhǎng)碼：不滿足等長(zhǎng)碼條件的碼組稱為變長(zhǎng)碼。4.1編碼器及碼的分類非奇異碼：若一組碼中所有碼字都不相同(即所有信源符號(hào)映射到不同的碼符號(hào)序列，不同信源符號(hào)可分辨)，則稱為非奇異碼。奇異碼：反之，若碼組中含有相同的碼字則為奇異碼。同價(jià)碼：若碼符號(hào)集X：{x1,x2,…,xr}中每個(gè)碼符號(hào)所占的傳輸時(shí)間都相同，則所得的碼為同價(jià)碼。4.1編碼器及碼的分類碼的N次擴(kuò)展碼：信源符號(hào)出現(xiàn)概率碼1碼2s1P(s1)000s2P(s2)0101s3P(s3)10001s4P(s4)11111信源碼字信源碼字信源碼字a100＝W1W1=B1a5...010＝W2W1=B1.......a16....111111=W4W4=B16a2001＝W1W2=B2a30001＝W1W3=B3a40111＝W1W4=B44.1編碼器及碼的分類惟一可譯碼：若碼的任意一串有限長(zhǎng)的碼符號(hào)序列只能被惟一地譯成所對(duì)應(yīng)的信源符號(hào)序列，則此碼稱為惟一可譯碼（單義可譯碼）。否則就稱為非惟一可譯碼或非單義可譯碼。表1中碼1是惟一可譯碼，而碼2是非惟一可譯碼。因?yàn)閷?duì)于碼2，其有限長(zhǎng)的碼符號(hào)序列能譯成不同的信源符號(hào)序列。如碼符號(hào)序列0010，可譯成s1s2s1或s3s1，就不惟一了。問題：怎樣才能做到無失真編碼即惟一可譯碼？4.2等長(zhǎng)碼若要實(shí)現(xiàn)無失真編碼，不但要求信源符號(hào)si與碼字Wi是一一對(duì)應(yīng)的，而且要求碼符號(hào)序列的反變換也是惟一的。即所編的碼必須是惟一可譯碼。對(duì)于等長(zhǎng)碼來說，若等長(zhǎng)碼是非奇異碼，則它的任意有限長(zhǎng)N次擴(kuò)展碼一定也是非奇異碼。等長(zhǎng)非奇異碼一定是惟一可譯碼。信源符號(hào)碼1碼2s10000s20111s31010s41111非奇異碼唯一可譯碼奇異碼非惟一可譯碼4.2等長(zhǎng)碼等長(zhǎng)編碼惟一可譯的必要條件：其中：q為信源符號(hào)數(shù),r為符號(hào)集中的碼元數(shù),l為碼長(zhǎng)。例如：若信源符號(hào)數(shù)

q＝4，進(jìn)行二元等長(zhǎng)編碼，則碼符號(hào)個(gè)數(shù)為

r＝2。信源S存在惟一可譯等長(zhǎng)碼的條件是碼長(zhǎng)

l≥2。若q＝8，r＝2，l≥3。4.2等長(zhǎng)碼對(duì)兩邊取對(duì)數(shù)得平均每個(gè)信源符號(hào)所需的碼符號(hào)個(gè)數(shù)上式表明：對(duì)于等長(zhǎng)惟一可譯碼而言，平均每個(gè)信源符號(hào)至少需要用logq／logr個(gè)碼符號(hào)來表示。即：每個(gè)信源符號(hào)所需最短碼長(zhǎng)為logq／logr個(gè)。4.2等長(zhǎng)碼當(dāng)r=2(二元碼)時(shí)logr=1,

上式變成上式表明：對(duì)于二元等長(zhǎng)惟一可譯碼，平均每個(gè)信源符號(hào)至少需要用logq個(gè)碼符號(hào)來變換?；颍簩?duì)信源進(jìn)行二元等長(zhǎng)不失真編碼時(shí)，每個(gè)信源符號(hào)所需的極限值為logq個(gè)。4.2等長(zhǎng)碼當(dāng)考慮到符號(hào)之間的依賴關(guān)系或關(guān)聯(lián)性時(shí)，可以從N次擴(kuò)展信源中去掉一些符號(hào)，使得總符號(hào)數(shù)小于，這樣使編碼所需碼字個(gè)數(shù)大大減少，因此平均每個(gè)信源符號(hào)所需的碼符號(hào)個(gè)數(shù)就可以大大減少，從而提高傳輸效率。當(dāng)N足夠長(zhǎng)后，這種誤差概率可以任意小，做到幾乎無失真編碼。等長(zhǎng)編碼定理給出了信源進(jìn)行等長(zhǎng)編碼所需碼長(zhǎng)的理論極限值。4.4等長(zhǎng)信源編碼定理定理4.3(等長(zhǎng)信源編碼定理):一個(gè)熵為H(S)的離散無記憶信源，若對(duì)信源長(zhǎng)為N的符號(hào)序列進(jìn)行等長(zhǎng)編碼，設(shè)碼字是從r個(gè)字母的碼符號(hào)集中選取l個(gè)碼元組成。對(duì)于任意ε＞0，只要滿足：則當(dāng)N足夠大時(shí)，可實(shí)現(xiàn)幾乎無失真編碼，即譯碼錯(cuò)誤概率能為任意小。反之，若當(dāng)N足夠大時(shí)，譯碼錯(cuò)誤概率近似為1,不可能實(shí)現(xiàn)無失真編碼。4.4等長(zhǎng)信源編碼定理說明：定理4.3是在平穩(wěn)無記憶離散信源的條件下得出，但它同樣適合于平穩(wěn)有記憶信源。當(dāng)進(jìn)行二元編碼時(shí)，r＝2，則：一般情況下，信源符號(hào)并非等概率分布，且符號(hào)之間有很強(qiáng)的關(guān)聯(lián)性，故信源的熵H(S)<<logq。等長(zhǎng)編碼時(shí)平均每個(gè)信源符號(hào)所需的二元碼符號(hào)的理論極限信源等概分布時(shí)4.4等長(zhǎng)信源編碼定理從定理4.3可知，在等長(zhǎng)編碼中每個(gè)信源符號(hào)平均所需的二元碼符號(hào)可大大減少，從而使編碼效率提高。定理4.3中的條件式可改寫成：

長(zhǎng)為l的碼符號(hào)序列所能載荷的最大信息量長(zhǎng)為N的信源序列平均攜帶的信息量4.4等長(zhǎng)信源編碼定理所以等長(zhǎng)編碼定理告訴我們：只要碼字傳輸?shù)男畔⒘看笥谛旁葱蛄袛y帶的信息量，總可實(shí)現(xiàn)幾乎無失真編碼。令它是編碼后平均每個(gè)信源符號(hào)能載荷的最大信息量，稱為編碼信息率?？梢姡?dāng)編碼信息率大于信源的熵時(shí)，才能實(shí)現(xiàn)幾乎無失真編碼。為衡量編碼效果，引入編碼效率。4.4等長(zhǎng)信源編碼定理稱為編碼效率。由定理4.3可得最佳等長(zhǎng)編碼的效率為：

如果自信息的方差

和ε均為定值時(shí)，只要N足夠大，編碼錯(cuò)誤就可以小于任一正數(shù)δ。也即要求誤差小于δ時(shí)，4.4等長(zhǎng)信源編碼定理信源序列長(zhǎng)度N必須滿足：該式給出了在已知方差和信源熵的條件下，信源序列長(zhǎng)度N與最佳編碼效率

和允許錯(cuò)誤概率

的關(guān)系。允許錯(cuò)誤概率越小，編碼效率要求越高，則信源序列長(zhǎng)度N就必須越長(zhǎng)。實(shí)際情況下，要實(shí)現(xiàn)幾乎無失真的等長(zhǎng)編碼，N需要非常大。4.4等長(zhǎng)信源編碼定理例設(shè)離散無記憶信源信源熵自信息方差若對(duì)信源S采用等長(zhǎng)二元編碼，要求編碼效率η=0.96，允許錯(cuò)誤概率4.4等長(zhǎng)信源編碼定理則得即序列長(zhǎng)度達(dá)4130萬以上，這在實(shí)際中很難實(shí)現(xiàn)。因此，一般來說，當(dāng)N有限時(shí)，高傳輸效率的等長(zhǎng)碼往往要引入一定的失真和錯(cuò)誤，它不能像變長(zhǎng)碼那樣可以實(shí)現(xiàn)無失真編碼。下面介紹變長(zhǎng)碼，及其編碼定理。4.5變長(zhǎng)碼4.5.1惟一可譯變長(zhǎng)碼與即時(shí)碼等長(zhǎng)碼僅當(dāng)N很大才會(huì)有較高的編碼效率；變長(zhǎng)碼往往在N不很大時(shí)就可編出效率很高而且無失真的碼。等長(zhǎng)碼：非奇異惟一可譯變長(zhǎng)碼：任意有限長(zhǎng)N次擴(kuò)展碼是非奇異惟一可譯4.5變長(zhǎng)碼即時(shí)碼：在譯碼時(shí)無需參考后續(xù)的碼符號(hào)就能立即作出判斷，譯成對(duì)應(yīng)的信源符號(hào)的惟一可譯碼碼4以“1”作為結(jié)束符號(hào)，起到逗號(hào)的作用，又稱為逗點(diǎn)碼。逗點(diǎn)碼是一種即時(shí)碼。信源符號(hào)出現(xiàn)概率碼1碼2碼3碼4s1s2s3s41/21/41/81/80110011010000111010010001010010001非惟一可譯奇異碼非惟一可譯非奇異碼惟一可譯非奇異碼惟一可譯非奇異碼4.5變長(zhǎng)碼定義：如果一個(gè)碼組中的任一個(gè)碼字都不是另一個(gè)碼字的續(xù)長(zhǎng)，或者說，任何一個(gè)碼字都不是另一個(gè)碼字的前綴，則稱為即時(shí)碼也稱非延長(zhǎng)碼或前綴條件碼。

所有碼非奇異碼惟一可譯碼即時(shí)碼4.5變長(zhǎng)碼4.5.2即時(shí)碼的樹圖構(gòu)造法構(gòu)造即時(shí)碼的一種簡(jiǎn)單方法是樹圖法。信源符號(hào)碼4s1s2s3s41010010001根：樹的最上端樹枝的個(gè)數(shù)為r，r=2為二元碼樹01001111010010001碼4的樹圖ABCD中間節(jié)點(diǎn)（空心）節(jié)點(diǎn)：樹枝的終端，從節(jié)點(diǎn)生出樹枝，每個(gè)節(jié)點(diǎn)伸出r個(gè)枝終端節(jié)點(diǎn)（實(shí)心）碼字：從根到終端節(jié)點(diǎn)對(duì)應(yīng)的碼符號(hào)，又稱樹葉4.5變長(zhǎng)碼按樹圖法構(gòu)成的碼一定滿足即時(shí)碼的充要條件，因?yàn)閺母饺~所走的路徑各不相同，而且中間節(jié)點(diǎn)不安排為碼字，所以一定滿足對(duì)前綴的限制。該樹的5個(gè)終端節(jié)點(diǎn)W1,W2,W3,W4,W5分別表示5個(gè)二進(jìn)制碼字0，100，111，1010，10114.5變長(zhǎng)碼碼樹的性質(zhì)：任一即時(shí)碼都可用樹圖表示。當(dāng)碼字長(zhǎng)度給定，即時(shí)碼不是惟一的。整樹：每個(gè)節(jié)點(diǎn)上都有r個(gè)分枝。非整樹：至少有一個(gè)節(jié)點(diǎn)上沒有r個(gè)分枝的樹。4.5.4惟一可譯變長(zhǎng)碼的判斷法結(jié)論：不能用Kraft不等式，只能根據(jù)定義判斷碼C是否是惟一可譯碼。依據(jù)：非惟一可譯變長(zhǎng)碼

有限長(zhǎng)的碼符號(hào)序列能譯成兩種不同的碼字序列。惟一可譯變長(zhǎng)碼判別：將碼C中所有可能的尾隨后綴組成一個(gè)集合F，當(dāng)且僅當(dāng)集合F中沒有包含任一碼字時(shí)，碼C為惟一可譯變長(zhǎng)碼。4.5.4惟一可譯變長(zhǎng)碼的判斷法構(gòu)成集合F的方法：首先，觀察碼C中最短的碼字是否是其他碼字的前綴。若是，將其所有可能的尾隨后綴排列出。而這些尾隨后綴又可能是某些碼字的前綴，再將由這些尾隨后綴產(chǎn)生的新的尾隨后綴列出。依此下去，直至沒有一個(gè)尾隨后綴是碼字的前綴或沒有新的尾隨后綴產(chǎn)生為止。接著，按照上述步驟將次短的碼字直至所有碼字可能產(chǎn)生的尾隨后綴全部列出。4.6變長(zhǎng)信源編碼定理對(duì)于已知信源S可用碼符號(hào)X進(jìn)行變長(zhǎng)編碼，而且對(duì)同一信源可有多種即時(shí)碼或惟一可譯碼。選擇哪一種最好呢？從高速度傳輸信息的角度，希望用短的碼符號(hào)組成碼字，即用碼長(zhǎng)作為選擇準(zhǔn)則——引進(jìn)碼的平均長(zhǎng)度。4.6變長(zhǎng)信源編碼定理設(shè)信源為編碼后的碼字為其碼長(zhǎng)分別為對(duì)于惟一可譯碼，有則這個(gè)碼的平均長(zhǎng)度為：?jiǎn)挝皇谴a符號(hào)/信源符號(hào)，是每個(gè)信源符號(hào)平均需用的碼元數(shù)。4.6變長(zhǎng)信源編碼定理編碼后信道的信息傳輸率（編碼后平均每個(gè)碼元攜帶的信息量）:若傳輸一個(gè)碼符號(hào)平均需要t秒鐘，則編碼后信道每秒傳輸?shù)男畔⒘繛榭梢?，碼的平均長(zhǎng)度越短、越大，信息傳輸效率就越高。對(duì)于編碼者來說，感興趣的是平均碼長(zhǎng)短的碼。問題：如何找到碼長(zhǎng)最短的惟一可譯碼？

4.6變長(zhǎng)信源編碼定理緊致碼（最佳碼）：對(duì)于某一信源和某一碼符號(hào)集來說，若有一個(gè)惟一可譯碼，其平均長(zhǎng)度小于所有其他惟一可譯碼的平均長(zhǎng)度，則該碼稱為緊致碼，或稱最佳碼。無失真信源編碼的基本問題轉(zhuǎn)化為找出緊致碼。最佳碼也就是緊致碼的平均長(zhǎng)度不是可以無限制縮小的，在理論上是有它的極限值的（在無失真信源編碼的條件下），香農(nóng)第一定理給出了這一極限值，這一定理有很大的實(shí)際意義。

4.6變長(zhǎng)信源編碼定理定理4.8

無失真變長(zhǎng)信源編碼定理(即香農(nóng)第一定理)

：離散無記憶信源S的N次擴(kuò)展信源，其熵為，并有碼符號(hào)X={x1,x2,…,xr}

。對(duì)信源進(jìn)行編碼，總可以找到一種編碼方法，構(gòu)成惟一可譯碼，使信源S中每個(gè)信源符號(hào)所需的平均碼長(zhǎng)滿足：4.6變長(zhǎng)信源編碼定理當(dāng)時(shí)，得其中表示對(duì)N個(gè)信源符號(hào)的序列進(jìn)行編碼。4.6變長(zhǎng)信源編碼定理定理4.8是香農(nóng)信息論的主要定理之一，它說明要做到無失真的信源編碼，編碼每個(gè)信源符號(hào)平均所需最少的r元碼元數(shù)為信源的熵Hr(S)

。即熵Hr(S)

是無失真信源壓縮的極限值。若編碼的平均碼長(zhǎng)小于信源的熵值Hr(S)

，則惟一可譯碼不存在，在譯碼或反變換時(shí)必然要帶來失真或差錯(cuò)。通過對(duì)擴(kuò)展信源進(jìn)行變長(zhǎng)編碼，當(dāng)時(shí)，平均碼長(zhǎng)4.6變長(zhǎng)信源編碼定理從信道角度看，信道的信息傳輸率因?yàn)樗詷O限情況下，編碼后信道的信息傳輸率為：這時(shí)信道的信息傳輸率等于無噪無損信通的信道容量C，信息傳輸效率最高。4.6變長(zhǎng)信源編碼定理香農(nóng)第一定理的物理意義：無失真信源編碼的實(shí)質(zhì)：對(duì)離散信源進(jìn)行適當(dāng)變換變換后新信源符號(hào)(信道的輸入信源)盡可能為等概率分布新信源符號(hào)平均所含的信息量達(dá)到最大使信道的信息傳輸率R達(dá)到信道容量C，實(shí)現(xiàn)信源與信道理想的統(tǒng)計(jì)匹配。4.6變長(zhǎng)信源編碼定理無失真信源編碼定理通常又稱為無噪信道編碼定理。表述為：若信道的信息傳輸率R不大于信道容量C，總能對(duì)信源的輸出進(jìn)行適當(dāng)?shù)木幋a，使得在無噪無損信道上能無差錯(cuò)地以最大信息傳輸率C傳輸信息，但要使信道的信息傳輸率R大于C而無差錯(cuò)地傳輸信息則是不可能的。4.6變長(zhǎng)信源編碼定理為了衡量各種編碼是否達(dá)到極限情況，定義變長(zhǎng)碼的編碼效率為：一般用碼的效率η來衡量各種編碼的優(yōu)劣。為了衡量各種編碼與理論極限的差距，定義碼的剩余度為：4.6變長(zhǎng)信源編碼定理在二元無損無噪信道中r=2，所以在二元無損無噪信道中信息傳輸率η和R數(shù)值相同但單位不同在二元信道中若η=1，即信息傳輸率R=1比特／碼符號(hào)，達(dá)到了信道的信道容量，編碼效率最高，碼剩余度為零。4.6變長(zhǎng)信源編碼定理例：有一離散無記憶信源其熵為：0.811用二元碼符號(hào)構(gòu)造一個(gè)即時(shí)碼平均碼長(zhǎng)編碼效率編碼效率較低，為此對(duì)信源S的二次擴(kuò)展信源S2進(jìn)行編碼。4.6變長(zhǎng)信源編碼定理平均碼長(zhǎng)即時(shí)碼s1s19/160s1s23/1610s2s13/16110s2s21/161114.6變長(zhǎng)信源編碼定理由此可得，編碼復(fù)雜了一些，但是信息傳輸率提高了同理，對(duì)信源S的三次和四次擴(kuò)展信源進(jìn)行編碼，其編碼效率和信道的信息傳輸率分別為：4.6變長(zhǎng)信源編碼定理很明顯，用變長(zhǎng)碼編碼時(shí)，N不需要很大就可以達(dá)到相當(dāng)高的編碼效率，而且可以實(shí)現(xiàn)無失真編碼。隨著擴(kuò)展信源次數(shù)的增加，編碼的效率越來越接近于1，編碼后信道的信息傳輸率R也越來越接近于無噪無損二元信道的信道容量C=1bit/symbol，達(dá)到信源與信道匹配，使信道得到充分利用。4.7霍夫曼碼和其他編碼方法本節(jié)介紹霍夫曼(Huffman)碼、費(fèi)諾(Fano)碼和香農(nóng)-費(fèi)諾-埃利斯(Shannon-Fano-Elias)碼。香農(nóng)第一定理指出了平均碼長(zhǎng)與信源熵之間的關(guān)系，同時(shí)也指出了通過編碼可使平均碼長(zhǎng)達(dá)到極限值。但沒有給出具體的編碼方法。那么如何編碼呢？也就是如何去構(gòu)造一個(gè)緊致碼？具體的編碼方法如何？下面我們來討論霍夫曼碼的編碼方法。4.7.1霍夫曼（Huffman）碼－編碼步驟1.將q個(gè)信源符號(hào)按概率遞減的方式排列起來。2.用“0”,“1”碼符號(hào)分別表示概率最小的兩個(gè)信源符號(hào)，并將這兩個(gè)概率最小的信源符號(hào)合并成一個(gè)符號(hào)，從而得到只包含q-1個(gè)符號(hào)的新信源，稱之為S信源的縮減信源S1。3.將縮減信源S1的符號(hào)仍按概率大小以遞減次序排列，再將其最后兩個(gè)概率最小的符號(hào)合并成一個(gè)符號(hào)，并分別用“0”，“1”碼符號(hào)表示，這樣又形成了q-2個(gè)符號(hào)的縮減信源S2。4.7.1霍夫曼（Huffman）碼－編碼步驟4.依次繼續(xù)下去，直到信源最后只剩下兩個(gè)符號(hào)為止，將這最后兩個(gè)符號(hào)分別用“0”，“1”碼符號(hào)表示，然后從最后一級(jí)縮減信源開始，向前返回，得出各信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即得出對(duì)應(yīng)的碼字。例設(shè)單符號(hào)離散無記憶信源如下，要求對(duì)信源編二進(jìn)制霍夫曼碼。編碼過程如下圖（后頁）。4.7.1霍夫曼（Huffman）碼霍夫曼碼是一種即時(shí)碼，可用碼樹形式來表示。將上圖左右顛倒過來重畫一下，即可得到二進(jìn)制哈夫曼碼的碼樹。01001111樹圖X1:1X2:001000011X3:011X4:0000X5:0100X6:0101X7:00010X8:000114.7.1霍夫曼（Huffman）碼信源熵為：平均碼長(zhǎng)為編碼效率為若采用定長(zhǎng)編碼,碼長(zhǎng)L=3,則編碼效率可見哈夫曼的編碼效率提高了12.7%。注意：霍夫曼編碼并不惟一。每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配“0”和“1”碼元是任意的，所以可得到不同的碼字。不同的碼元分配，得到的具體碼字不同，但碼長(zhǎng)li不變，平均碼長(zhǎng)也不變，所以沒有本質(zhì)區(qū)別；縮減信源時(shí)，若合并后的新符號(hào)概率與其他符號(hào)概率相等，從編碼方法上來說，這幾個(gè)符號(hào)的次序可任意排列，編出的碼都是正確的，但得到的碼字不相同。不同的編法得到的碼字長(zhǎng)度li也不盡相同。4.7.1霍夫曼（Huffman）碼例：?jiǎn)畏?hào)離散無記憶信源，用兩種不同的方法對(duì)其編二進(jìn)制霍夫曼碼。方法一：合并后的新符號(hào)排在其它相同概率符號(hào)的后面。siliWi概率s1s2s3s4s512344101000001000110.40.20.20.10.1

0.40.20.20.2

0.40.40.2

0.60.4010101014.7.1霍夫曼（Huffman）碼方法二：合并后的新符號(hào)排在其它相同概率符號(hào)的前面。這兩種編碼哪一種更好呢？我們來計(jì)算一下二者的平均碼長(zhǎng)。siliWi概率s1s2s3s4s5222330010110100110.40.20.20.10.1

0.40.20.20.2

0.40.40.2

0.60.4010101014.7.1霍夫曼（Huffman）碼兩種編碼的平均碼長(zhǎng)是一樣的，說明兩種編碼效率一樣，哪一種更好呢？我們可以計(jì)算一下平均碼長(zhǎng)的方差。定義碼字長(zhǎng)度的方差σ2：4.7.1霍夫曼（Huffman）碼可見：第二種編碼方法的碼長(zhǎng)方差要小許多。意味著第二種編碼方法的碼長(zhǎng)變化較小，比較接近于平均碼長(zhǎng)。第一種方法編出的5個(gè)碼字有4種不同的碼長(zhǎng)；第二種方法編出的碼長(zhǎng)只有2種不同的碼長(zhǎng)；顯然，第二種編碼方法更簡(jiǎn)單、更容易實(shí)現(xiàn)，所以更好。4.7.1霍夫曼（Huffman）碼結(jié)論：在霍夫曼編碼過程中，對(duì)縮減信源符號(hào)按概率由大到小的順序重新排列時(shí)，應(yīng)使合并后的新符號(hào)盡可能排在靠前的位置，這樣可使合并后的新符號(hào)重復(fù)編碼次數(shù)減少，使短碼得到充分利用。4.7.1霍夫曼（Huffman）碼霍夫曼碼的特點(diǎn)：

霍夫曼碼的編碼方法保證了概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)碼,即而且短碼得到充分利用。每次縮減信源的最后二個(gè)碼字總是最后一位碼元不同，前面各位碼元相同(二元編碼情況)。每次縮減信源的最長(zhǎng)兩個(gè)碼字有相同的碼長(zhǎng)。這三個(gè)特點(diǎn)保證了所得的霍夫曼碼一定是最佳碼。4.7.3霍夫曼（Huffman）碼的最佳性最佳碼的一些性質(zhì)：定理4.9

對(duì)于給定分布的任何信源，存在一個(gè)最佳即時(shí)碼(其平均碼長(zhǎng)最短)，此碼滿足以下性質(zhì)(1)若pj＞pk，則lj≤lk。(2)兩個(gè)最小概率的信源符號(hào)所對(duì)應(yīng)的碼字具有相同的碼長(zhǎng)。(3)兩個(gè)最小概率的信源符號(hào)所對(duì)應(yīng)的碼字，其除最后一位碼元不同外，前面各位碼元都相同。4.7.3霍夫曼（Huffman）碼的最佳性說明：定理4.9中所述的三個(gè)性質(zhì)正好是霍夫曼編碼三個(gè)特點(diǎn)。由此可見，霍夫曼碼C是信源給定后，所有可能的惟一可譯碼中平均碼長(zhǎng)最短的碼，即4.7.3霍夫曼（Huffman）碼的最佳性定理4.10

二元霍夫曼碼一定是最佳即時(shí)碼。即若C是霍夫曼碼，C’是任意其他即時(shí)碼，則有：因?yàn)榛舴蚵a是在信源給定情況下的最佳碼，所以其平均碼長(zhǎng)的界限為：對(duì)信源的N次擴(kuò)展信源同樣可以采取霍夫曼編碼方法。因?yàn)榛舴蚵a是緊致碼，所以編碼后單個(gè)信源符號(hào)所編得的平均碼長(zhǎng)隨N的增加很快接近于極限值——信源的熵。4.7.4費(fèi)諾（Fano）碼費(fèi)諾編碼也是一種常見的信源編碼方法。費(fèi)諾碼不是最佳的編碼方法，但有時(shí)也可得到最佳碼的性能。費(fèi)諾碼的編碼程序如下：（1）信源符號(hào)以概率遞減的次序排列起來，將排列好的信源符號(hào)劃分成兩大組，使每組的概率之和接近于相等，并各賦予一個(gè)二元碼符號(hào)“0”和“1”

；（2）將每一大組的信源符號(hào)再分成兩組，使同一組的兩個(gè)小組的概率之和接近于相等，再分別賦予一個(gè)二元碼符號(hào)。4.7.4費(fèi)諾（Fano）碼（3）依次下去，直至每個(gè)小組只剩一個(gè)信源符號(hào)為止。例設(shè)有一單符號(hào)離散信源對(duì)該信源編二進(jìn)制費(fèi)諾碼。4.7.4費(fèi)諾（Fano）碼該信源的熵為平均碼長(zhǎng)為編碼效率為本例中費(fèi)諾編碼有較高的編碼效率。費(fèi)諾碼比較適合于每次分組概率都很接近的信源。特別是對(duì)每次分組概率都相等的信源進(jìn)行編碼時(shí)，可達(dá)到理想的編碼效率。4.7.4費(fèi)諾（Fano）碼費(fèi)諾碼的編碼方法實(shí)際上是一種構(gòu)造碼樹的方法，所以費(fèi)諾碼是即時(shí)碼。費(fèi)諾碼考慮了信源的統(tǒng)計(jì)特性，使概率大的信源符號(hào)能對(duì)應(yīng)碼長(zhǎng)短的碼字。從而有效地提高了編碼效率。費(fèi)諾編碼方法不一定使短碼得到充分利用。尤其當(dāng)信源符號(hào)較多時(shí)，若有一些符號(hào)概率分布很接近時(shí)，分兩大組的組合方法會(huì)很多。可能某種分大組的結(jié)果，會(huì)使后面小組的“概率和”相差較遠(yuǎn)，使平均碼長(zhǎng)增加。費(fèi)諾碼不一定是最佳碼。

4.7.5香農(nóng)－費(fèi)諾－埃利斯碼香農(nóng)-費(fèi)諾-埃利斯(Shannon-Fano-Elias)編碼方法，是采用信源符號(hào)的累積分布函數(shù)來分配碼字的。設(shè)信源符號(hào)集，定義累積分布函數(shù)：定義修正的累積分布函數(shù)：4.7.5香農(nóng)－費(fèi)諾－埃利斯碼累積分布函數(shù)為每臺(tái)階的上界值。而臺(tái)階的高度為的值，的值正處于對(duì)應(yīng)于臺(tái)階的中點(diǎn)當(dāng)，知道了就能確定信源符號(hào)為,因此可用的值作為符號(hào)的碼字。1234561.04.7.5香農(nóng)－費(fèi)諾－埃利斯碼每個(gè)信源符號(hào)ak所編碼的碼字對(duì)應(yīng)的區(qū)域都沒有重疊，碼組滿足前綴條件，為即時(shí)碼。用二進(jìn)數(shù)表示，一般為無限位二進(jìn)制數(shù)。取小數(shù)后l(ak)位，即截去后面的位數(shù)，得的近似值，并用這l(ak)位二進(jìn)數(shù)作為ak的碼字。其中表示取l位使小于等于x的數(shù)。一般取4.7.5香農(nóng)－費(fèi)諾－埃利斯碼例離散無記憶信源，它的香農(nóng)－費(fèi)諾－埃利斯碼表如下：平均碼長(zhǎng)信源熵信源概率F(S)

的二進(jìn)數(shù)碼長(zhǎng)碼字Ws1s2s3s40.250.50.1250.1250.250.750.8751.00.1250.50.81250.93750.0010.100.11010.1111324400110110111114.7.5香農(nóng)－費(fèi)諾－埃利斯碼例給出另一信源的香農(nóng)－費(fèi)諾－埃利斯碼平均碼長(zhǎng)信源概率F(S)

的二進(jìn)數(shù)碼長(zhǎng)碼字Ws1s2s3s4s50.250.250.20.150.150.250.50.70.851.00.1250.3750.60.7750.9250.0010.01133444001011100111001110一些結(jié)論霍夫曼碼、費(fèi)諾碼、香－費(fèi)－埃碼都考慮了信源的統(tǒng)計(jì)特性，使經(jīng)常出現(xiàn)的信源符號(hào)對(duì)應(yīng)較短的碼字，使信源的平均碼長(zhǎng)縮短，從而實(shí)現(xiàn)了對(duì)信源的壓縮；霍夫曼碼和費(fèi)諾碼的編碼方法都不惟一；費(fèi)諾碼比較適合于對(duì)分組概率相等或接近的信源編碼；霍夫曼碼對(duì)信源的統(tǒng)計(jì)特性沒有特殊要求，編碼效率比較高，對(duì)編碼設(shè)備的要求也比較簡(jiǎn)單，因此綜合性能優(yōu)于費(fèi)諾碼和香－費(fèi)－埃碼。4.8幾種實(shí)用的無失真信源編碼方法在實(shí)際編碼壓縮技術(shù)中，常常結(jié)合實(shí)際信源情況，在壓縮技術(shù)上給以改進(jìn)，使便于操作和軟硬件實(shí)現(xiàn)，本節(jié)介紹幾種實(shí)用的無失真信源編碼的方法。4.8.1MH碼MH（ModifiedHuffman），即修正的霍夫曼編碼，MH編碼是用于黑白二值文件傳真的數(shù)據(jù)壓縮，1997年被CCITT推薦為傳真機(jī)一維壓縮編碼的國(guó)際標(biāo)準(zhǔn)。4.8.1MH碼文件傳真是指一般文件、圖紙、手寫稿、表格、報(bào)紙等文件的傳真。它們是黑白二值的，也就是信源是二元信源q=2。文件圖紙根據(jù)清晰度的要求來決定空間掃描分辨率，將文件圖紙?jiān)诳臻g上離散化。分辨率越高，分的越細(xì)，質(zhì)量越高。國(guó)際規(guī)定，A4（210mm×297mm）幅面文件應(yīng)該有1188或2376條掃描線，每條掃描線有1728個(gè)像素的掃描分辨率（相當(dāng)于垂直4或8線/mm，水平8點(diǎn)/mm）。4.8.1MH碼因此，A4文件紙約有2.05M像素/公文紙或4.1M像素/公文紙，從節(jié)省傳送時(shí)間和存儲(chǔ)空間來說，必須進(jìn)行數(shù)據(jù)壓縮。MH編碼是一維編碼方案，即對(duì)一行一行的數(shù)據(jù)進(jìn)行編碼。它將游程編碼和霍夫曼編碼相結(jié)合，是一種標(biāo)準(zhǔn)的改進(jìn)霍夫曼碼。從文件來看，每行中會(huì)出現(xiàn)連續(xù)個(gè)“白”像素或連續(xù)個(gè)“黑”像素，同一符號(hào)出現(xiàn)而形成字符串的長(zhǎng)度稱之為游程長(zhǎng)度。4.8.1MH碼MH碼分別對(duì)“白”、“黑”的不同游程長(zhǎng)度進(jìn)行霍夫曼編碼，形成黑、白兩張碼表。編、譯碼通過查表進(jìn)行。每行總是從白色游程開始（如第一像素為黑色，則此長(zhǎng)度可設(shè)為零）。如游程長(zhǎng)度超過63個(gè)像素則分成兩部分：前面是組合基干碼，后為結(jié)尾碼。修正MH編碼一次只壓縮一掃描行，各行獨(dú)立不相關(guān)，因此是一種"一維編碼方案"。4.8.1MH碼例設(shè)某頁傳真文件中某一掃描行的像素點(diǎn)為|17白|5黑|55白|10黑|1641白|該行HM碼為101011|0011|010110000|0000100|010010101|00101010|EOL數(shù)據(jù)壓縮比：1728/54＝32，壓縮率很高。4.8.2算術(shù)編碼算術(shù)編碼不同于霍夫曼碼，它是非分組碼。它從全序列出發(fā)，考慮符號(hào)之間的依賴關(guān)系來進(jìn)行編碼的?；舴蚵a必須對(duì)二元信源的N次擴(kuò)展信源進(jìn)行編碼時(shí)，才能使平均碼長(zhǎng)很快接近信源的熵，編碼效率才高，而MH碼的碼表非常的龐大。問題，對(duì)于很長(zhǎng)的信源符號(hào)序列是否存在簡(jiǎn)單有效的編碼方法呢？4.8.2算術(shù)編碼由香－費(fèi)－埃推廣得到的算術(shù)編碼就可以達(dá)到這個(gè)目的。下面舉例說明算術(shù)碼是如何具體編碼的。例設(shè)二元無記憶信源對(duì)二元序列做算術(shù)編碼。解：4.8.2算術(shù)編碼信源符號(hào)序列s的累積分布函數(shù)：從上式得得