信息論與編碼第5章(2)

1、信源編碼1無失真信源編碼無失真信源編碼實(shí)現(xiàn)實(shí)現(xiàn)無失真無失真的信源編碼的信源編碼,要求要求: 信源符號(hào)信源符號(hào)X1 X2Xl XL是一一對(duì)應(yīng)的是一一對(duì)應(yīng)的 碼字碼字Y1 Y2Yk YKKLLlog M1Llog m _K 能夠無失真或能夠無失真或無差錯(cuò)地從無差錯(cuò)地從Y恢復(fù)恢復(fù)X,也就是能正確地進(jìn)行反也就是能正確地進(jìn)行反變換或譯碼變換或譯碼 ; 傳送傳送Y時(shí)所需要的時(shí)所需要的信息率最小信息率最小信息率最小信息率最小就是找到一種編碼方式使就是找到一種編碼方式使最小最小信源編碼器信源編碼器碼表碼表信源信源信道信道XYL長序列長序列K長碼字長碼字2定長編碼定理定長編碼定理定長編碼定理定長編碼定理： 由由

2、L個(gè)符號(hào)組成的、每個(gè)符號(hào)的熵為個(gè)符號(hào)組成的、每個(gè)符號(hào)的熵為HL(X)的無記憶的無記憶平穩(wěn)信源符號(hào)序列平穩(wěn)信源符號(hào)序列X1XlXL,可用可用 KL個(gè)符號(hào)個(gè)符號(hào)Y1YkYKL(每個(gè)符號(hào)有每個(gè)符號(hào)有m種可能值種可能值)進(jìn)行定長編碼。進(jìn)行定長編碼。則當(dāng)則當(dāng)L足夠大時(shí)足夠大時(shí),必可使譯碼差錯(cuò)小于必可使譯碼差錯(cuò)小于;反之反之,當(dāng)當(dāng)時(shí)時(shí),譯碼差錯(cuò)一定是有限值譯碼差錯(cuò)一定是有限值,而當(dāng)而當(dāng)L足夠大時(shí)足夠大時(shí),譯碼幾乎譯碼幾乎必定出錯(cuò)必定出錯(cuò))(logXLLHmLK2)(logXLLHmLK3定長編碼定理定長編碼定理當(dāng)編碼器容許的輸出信息率當(dāng)編碼器容許的輸出信息率,也就是當(dāng)每個(gè)信源符號(hào)所必須也就是當(dāng)每個(gè)信源符號(hào)

3、所必須輸出的碼長是輸出的碼長是 時(shí)時(shí),只要只要 K HL(X) ,這種編碼器一定可以做到幾乎這種編碼器一定可以做到幾乎無失真無失真,也就是收端的譯碼差錯(cuò)概率接近于零也就是收端的譯碼差錯(cuò)概率接近于零,條件是所取的符號(hào)數(shù)條件是所取的符號(hào)數(shù)L足夠大足夠大。將定理的條件改寫成將定理的條件改寫成KL logm LHL(X) H(X)其中：其中：左邊：左邊：KL長碼字所能攜帶的最大信息，長碼字所能攜帶的最大信息，右邊：右邊：L長信源序列攜帶的信息量。長信源序列攜帶的信息量。4 (X) 定長編碼定理定長編碼定理, 0 HL(X)HL(X) 對(duì)定長編碼對(duì)定長編碼,若要實(shí)現(xiàn)幾乎無失真編碼若要實(shí)現(xiàn)幾乎無失真編碼,

4、則信源長度則信源長度必須滿足必須滿足:22L 2(X) EI(xi) H(X)2 信源序列的自信息方差信源序列的自信息方差為了衡量編碼效果為了衡量編碼效果,定義定義編碼效率編碼效率：最佳編碼效率最佳編碼效率：5H L(X) 變長編碼定理變長編碼定理 1H(X)log m K 離散平穩(wěn)無記憶序列變長編碼定理離散平穩(wěn)無記憶序列變長編碼定理 對(duì)于平均符號(hào)熵為對(duì)于平均符號(hào)熵為HL(X)的離散平穩(wěn)無記憶信源的離散平穩(wěn)無記憶信源,必存在一種必存在一種 無失真編碼方法無失真編碼方法,使平均信息率使平均信息率 K 滿足不等滿足不等式式HL(X) K HL(X) 單個(gè)符號(hào)變長編碼定理單個(gè)符號(hào)變長編碼定理： 若一

5、離散無記憶信源的符號(hào)熵為若一離散無記憶信源的符號(hào)熵為H(X),每個(gè)信源符號(hào)用每個(gè)信源符號(hào)用m進(jìn)進(jìn)制碼元進(jìn)行變長編碼制碼元進(jìn)行變長編碼,一定存在一種無失真編碼方法一定存在一種無失真編碼方法,其碼其碼字平均長度滿足下列不等式字平均長度滿足下列不等式: H(X)log m H L(X)log mL編碼效率的下界編碼效率的下界： H L(X) K65.2.3最佳變長編碼最佳變長編碼最佳碼最佳碼：對(duì)于某一信源和某一碼符號(hào)集來說對(duì)于某一信源和某一碼符號(hào)集來說,若有一唯一可若有一唯一可譯碼譯碼,其其平均碼長平均碼長小于所有其他唯一可譯碼的平均小于所有其他唯一可譯碼的平均長度。長度。 方法：方法：將概率大的信

6、源符號(hào)編以短的碼字。概率小將概率大的信源符號(hào)編以短的碼字。概率小的符號(hào)編以長的碼字，這樣使得平均碼字長度最短。的符號(hào)編以長的碼字，這樣使得平均碼字長度最短。 主要有：主要有： 香農(nóng)香農(nóng)（Shannon） 費(fèi)諾費(fèi)諾（Fano） 哈夫曼哈夫曼（Huffma ）7香農(nóng)編碼香農(nóng)編碼香農(nóng)第一定理指出了香農(nóng)第一定理指出了平均碼長平均碼長與與信源信源之間的關(guān)系之間的關(guān)系,同同時(shí)也指出了可以通過編碼使平均碼長達(dá)到時(shí)也指出了可以通過編碼使平均碼長達(dá)到極限值極限值,這這是一個(gè)很重要的極限定理。是一個(gè)很重要的極限定理。 香農(nóng)第一定理指出香農(nóng)第一定理指出,選擇每個(gè)碼字的長度選擇每個(gè)碼字的長度Ki滿足下式：滿足下式：或

7、或: log2 p(xi) Ki log2 p(xi)+1 就可以得到這種碼。就可以得到這種碼。 這種編碼方法稱為這種編碼方法稱為香農(nóng)編碼香農(nóng)編碼8二進(jìn)制香農(nóng)碼的二進(jìn)制香農(nóng)碼的編碼步驟編碼步驟如下：如下：香農(nóng)編碼香農(nóng)編碼將信源符號(hào)按概率從大到小的順序排列將信源符號(hào)按概率從大到小的順序排列, p1 p2 pn確定滿足下列不等式的整數(shù)確定滿足下列不等式的整數(shù)Ki,log2 pi Ki log2 pi+1計(jì)算第計(jì)算第i個(gè)碼字的累加概率，個(gè)碼字的累加概率，將將Pi用二進(jìn)制表示用二進(jìn)制表示,并取并取小數(shù)點(diǎn)后小數(shù)點(diǎn)后Ki位位作為符號(hào)作為符號(hào)ai的的編編碼碼。9信源消息信源消息符號(hào)符號(hào)ai符號(hào)概率符號(hào)概率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例例 有一個(gè)信源共有有一個(gè)信源共有7個(gè)符號(hào)，其概率及其累加和如下表所示：個(gè)符號(hào)，其概率及其累加和如下表所示：香農(nóng)編碼香農(nóng)編碼10()2.610.831/3.14H XRK比特 碼元 由上表可以看出，一共有由上表可以看出，一共有5個(gè)三位的代碼組，各代個(gè)三位的代碼組，各代碼

9、組之間至少有一位數(shù)字不相同，故是唯一可譯碼。碼組之間至少有一位數(shù)字不相同，故是唯一可譯碼。還可以判斷出，這還可以判斷出，這7個(gè)代碼組都屬于即時(shí)碼。個(gè)代碼組都屬于即時(shí)碼。 平均碼長平均碼長 平均信息傳輸速率平均信息傳輸速率香農(nóng)編碼香農(nóng)編碼1( )3.14niiiKp x k 碼元/符號(hào)11 香農(nóng)編碼方法特點(diǎn)香農(nóng)編碼方法特點(diǎn)：由于由于ki總是進(jìn)一取整，香農(nóng)編碼方法不一定是最佳的；總是進(jìn)一取整，香農(nóng)編碼方法不一定是最佳的；由于第一個(gè)消息符號(hào)的累加概率總是為由于第一個(gè)消息符號(hào)的累加概率總是為0，故它對(duì)應(yīng)，故它對(duì)應(yīng)的碼字總是的碼字總是0、00、000、00的式樣；的式樣；碼字集合是唯一的，且為即時(shí)碼；碼

10、字集合是唯一的，且為即時(shí)碼；先有碼長再有碼字；先有碼長再有碼字；對(duì)于一些信源，編碼效率不高，冗余度稍大，因此對(duì)于一些信源，編碼效率不高，冗余度稍大，因此其實(shí)用性受到較大限制。其實(shí)用性受到較大限制。結(jié)論結(jié)論12費(fèi)諾編碼費(fèi)諾編碼費(fèi)諾編碼屬于費(fèi)諾編碼屬于概率匹配概率匹配編碼編碼 。 編碼步驟如下：編碼步驟如下： 將概率按從大到小的順序排列將概率按從大到小的順序排列,令令p(x1) p(x2) p(xn) 按編碼進(jìn)制數(shù)將概率分組按編碼進(jìn)制數(shù)將概率分組,使使每組概率盡可能接近每組概率盡可能接近或或相等相等。如編二進(jìn)制碼就分成兩組。如編二進(jìn)制碼就分成兩組,編編m進(jìn)制碼就分成進(jìn)制碼就分成m組。組。 給每一組

11、分配一位碼元。給每一組分配一位碼元。 將每一分組再按同樣原則劃分將每一分組再按同樣原則劃分,重復(fù)步驟重復(fù)步驟2和和3,直至概直至概率不再可分為止。率不再可分為止。13xi符號(hào)概符號(hào)概率率編碼編碼碼字碼字碼長碼長x10.3200002x20.221012x30.1810102x40.16101103x50.081011104x60.04111114費(fèi)諾編碼費(fèi)諾編碼14 費(fèi)諾編碼特點(diǎn)費(fèi)諾編碼特點(diǎn)：概率大，則分解的次數(shù)??；概率小概率大，則分解的次數(shù)?。桓怕市? 則分解的次數(shù)多。則分解的次數(shù)多。這符合最佳編碼原則。這符合最佳編碼原則。碼字集合是唯一的。碼字集合是唯一的。分解完了，碼字出來了，碼長也有了

12、。分解完了，碼字出來了，碼長也有了。因此，費(fèi)諾編碼方法又稱為子集分解法。因此，費(fèi)諾編碼方法又稱為子集分解法。費(fèi)諾編碼方法比較適合于每次分組概率都很接近的信費(fèi)諾編碼方法比較適合于每次分組概率都很接近的信結(jié)論結(jié)論源，特別是對(duì)每次分組概率都相等的信源進(jìn)行編碼時(shí)，源，特別是對(duì)每次分組概率都相等的信源進(jìn)行編碼時(shí)，可達(dá)到理想的編碼效率?？蛇_(dá)到理想的編碼效率。 r 元費(fèi)諾碼元費(fèi)諾碼: 前面討論的費(fèi)諾碼是二元費(fèi)諾碼，對(duì)前面討論的費(fèi)諾碼是二元費(fèi)諾碼，對(duì)r元費(fèi)諾碼，元費(fèi)諾碼，與二元費(fèi)諾碼編碼方法相同，只是每次分組時(shí)應(yīng)將符號(hào)分成概與二元費(fèi)諾碼編碼方法相同，只是每次分組時(shí)應(yīng)將符號(hào)分成概率分布接近的率分布接近的r個(gè)組。

13、個(gè)組。15哈夫曼編碼哈夫曼編碼哈夫曼編碼也是用碼樹來分配各符號(hào)的碼字。哈夫曼編碼也是用碼樹來分配各符號(hào)的碼字。哈夫曼哈夫曼(Huffman)編碼是一種效率比較高的編碼是一種效率比較高的變長無失變長無失真信源編碼真信源編碼方法。方法?；舴蚵幋a及其變種，在壓縮編碼領(lǐng)域中應(yīng)用的非常廣泛霍夫曼編碼及其變種，在壓縮編碼領(lǐng)域中應(yīng)用的非常廣泛數(shù)字圖像：數(shù)字圖像：JPEGJPEG運(yùn)動(dòng)圖像：運(yùn)動(dòng)圖像：MPEG2MPEG2、H.261H.261、H.263 H.263 16哈夫曼哈夫曼編碼的編碼的步驟步驟如下：如下： 將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列 p(x1)p

14、(x2) p(xn)取兩個(gè)取兩個(gè)概率最小概率最小的字母分別配以的字母分別配以0和和1兩碼元兩碼元,并將這并將這兩個(gè)兩個(gè)概率相加概率相加作為一個(gè)作為一個(gè)新字母新字母的概率的概率,與未分配的二與未分配的二進(jìn)符號(hào)的字母進(jìn)符號(hào)的字母重新排隊(duì)重新排隊(duì)。 對(duì)重排后的兩個(gè)概率最小符號(hào)重復(fù)步驟的過程。對(duì)重排后的兩個(gè)概率最小符號(hào)重復(fù)步驟的過程。不斷繼續(xù)上述過程不斷繼續(xù)上述過程,直到最后兩個(gè)符號(hào)直到最后兩個(gè)符號(hào)配以配以0和和1為止。為止。 從最后一級(jí)開始從最后一級(jí)開始,向前返回向前返回得到各個(gè)信源符號(hào)所對(duì)應(yīng)得到各個(gè)信源符號(hào)所對(duì)應(yīng)的碼元序列的碼元序列,即相應(yīng)的碼字。即相應(yīng)的碼字。哈夫曼編碼哈夫曼編碼17信源符信源符

15、 符號(hào)概符號(hào)概號(hào)號(hào)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 設(shè)單符號(hào)離散無記憶信源如下設(shè)單符號(hào)離散無記憶信源如下, ,要求對(duì)信源要求對(duì)信源編編二進(jìn)制二進(jìn)制哈夫曼碼。編碼過程如下表哈夫曼碼。編碼過程如下表哈夫曼編碼哈夫曼編碼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哈夫曼的哈夫曼的編法并不編法并不唯一唯一。 每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配分配“0”和和“1”碼元是碼元是任意任意的的,所以可得到不同的碼字。所以可得到不同的碼字。 不同的碼元分配不同的碼元分配,得到的具體碼字不同得到的具體碼字不同,但碼

17、長但碼長Ki不變不變,平均碼長也不變平均碼長也不變,所以沒有本質(zhì)區(qū)別；所以沒有本質(zhì)區(qū)別； 縮減信源時(shí)縮減信源時(shí),若合并后的新符號(hào)概率與其他符號(hào)概率若合并后的新符號(hào)概率與其他符號(hào)概率相等相等,從編碼方法上來說從編碼方法上來說,這幾個(gè)符號(hào)的這幾個(gè)符號(hào)的次序可任意排次序可任意排列列,編出的碼都是正確的編出的碼都是正確的,但得到的但得到的碼字不相同碼字不相同。 不同的編法得到的碼字長度不同的編法得到的碼字長度Ki也不盡相同。也不盡相同。哈夫曼編碼哈夫曼編碼20哈夫曼編碼哈夫曼編碼信源符號(hào)信源符號(hào)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單符號(hào)信源編二進(jìn)制哈夫曼碼單符號(hào)信源編二進(jìn)制哈夫曼碼, ,編碼效率主要決定編碼效率主要決定于信源熵和平均碼長之比于信源熵和平均碼長之比。 對(duì)相同的信源編碼對(duì)相同的信源編碼, ,其熵是一樣的其熵是一樣的, ,采用不同的編法采用不同的編法, ,得到的平均碼長可能不同。得到的平均碼長可能不同。 平均碼長越短平均碼長越短, ,編碼效率

19、就越高。編碼效率就越高。編法一的平均碼長為編法一的平均碼長為5i 1編法二的平均碼長為編法二的平均碼長為5i 1兩種編法的平均碼長相同兩種編法的平均碼長相同, ,所以編碼效率相同。所以編碼效率相同。哈夫曼編碼哈夫曼編碼23討論：哪種方法更好？討論：哪種方法更好？ 定義碼字長度的方差定義碼字長度的方差2 2：第二種編碼方法的碼長方差要小許多。第二種編碼方法的碼長方差要小許多。 第二種編碼方法的碼長變化較小第二種編碼方法的碼長變化較小, ,比較接近于平均碼比較接近于平均碼長。長。哈夫曼編碼哈夫曼編碼24哈夫曼編碼哈夫曼編碼第一種方法編出的第一種方法編出的5個(gè)碼字有個(gè)碼字有4種不同的碼長；種不同的碼

20、長； 第二種方法編出的碼長只有兩種不同的碼長；第二種方法編出的碼長只有兩種不同的碼長； 第二種編碼方法更簡(jiǎn)單、更容易實(shí)現(xiàn)第二種編碼方法更簡(jiǎn)單、更容易實(shí)現(xiàn),所以更好。所以更好。 結(jié)論：結(jié)論： 在哈夫曼編碼過程中在哈夫曼編碼過程中,對(duì)縮減信源符號(hào)按概率由大到小的順序?qū)s減信源符號(hào)按概率由大到小的順序重新排列時(shí)重新排列時(shí),應(yīng)使合并后的應(yīng)使合并后的新符號(hào)盡可能排在靠前新符號(hào)盡可能排在靠前的位置的位置,這樣這樣可使合并后的新符號(hào)重復(fù)編碼次數(shù)減少可使合并后的新符號(hào)重復(fù)編碼次數(shù)減少,使短碼得到充分利用。使短碼得到充分利用。 特征特征:是是一種分組碼一種分組碼：各個(gè)信源符號(hào)都被映射成一組固定次序的碼：各個(gè)信源

21、符號(hào)都被映射成一組固定次序的碼符號(hào)符號(hào). .是是一種一種唯唯一可解碼一可解碼：任何碼符號(hào)序列只能以一種方式譯碼：任何碼符號(hào)序列只能以一種方式譯碼. .是是一種即時(shí)碼一種即時(shí)碼：由于代表信源符號(hào)的節(jié)點(diǎn)都是終端節(jié)點(diǎn)，因：由于代表信源符號(hào)的節(jié)點(diǎn)都是終端節(jié)點(diǎn)，因此其編碼不可能是其它終端節(jié)點(diǎn)對(duì)應(yīng)的編碼的前綴，哈夫曼編此其編碼不可能是其它終端節(jié)點(diǎn)對(duì)應(yīng)的編碼的前綴，哈夫曼編碼所得的碼字一定是即時(shí)碼。碼所得的碼字一定是即時(shí)碼。25由于哈夫曼碼是一類無失真信源最佳變長碼，就是說在由于哈夫曼碼是一類無失真信源最佳變長碼，就是說在研究這類無失真信源編碼時(shí)認(rèn)為信道傳輸是理想的，是研究這類無失真信源編碼時(shí)認(rèn)為信道傳輸是

22、理想的，是不產(chǎn)生差錯(cuò)的，然而實(shí)際信道中總是存在噪聲的，不產(chǎn)生差錯(cuò)的，然而實(shí)際信道中總是存在噪聲的，噪聲噪聲引入后必然要破壞變長碼的結(jié)構(gòu)引入后必然要破壞變長碼的結(jié)構(gòu)。同時(shí)由于變長碼是不。同時(shí)由于變長碼是不加同步的碼，無法自動(dòng)清洗所產(chǎn)生的影響，所以必然要加同步的碼，無法自動(dòng)清洗所產(chǎn)生的影響，所以必然要產(chǎn)生誤差的擴(kuò)散，即產(chǎn)生誤差的擴(kuò)散，即噪聲所影響的不僅是被干擾的碼元，噪聲所影響的不僅是被干擾的碼元，而是一直要擴(kuò)散下去影響后面一系列碼元而是一直要擴(kuò)散下去影響后面一系列碼元。以至于在低以至于在低信噪比下無法工作。信噪比下無法工作。目前對(duì)這類誤差擴(kuò)散還沒有特別有效的克服方法，在工目前對(duì)這類誤差擴(kuò)散還沒有

23、特別有效的克服方法，在工程上一般哈夫曼碼只能程上一般哈夫曼碼只能適合于高信噪比的優(yōu)質(zhì)信道適合于高信噪比的優(yōu)質(zhì)信道，以，以減小誤差擴(kuò)散帶來的影響。同時(shí)工程上還常常采用減小誤差擴(kuò)散帶來的影響。同時(shí)工程上還常常采用定期定期清洗清洗，以犧牲編碼效率來達(dá)到限制誤差擴(kuò)散的目的。另，以犧牲編碼效率來達(dá)到限制誤差擴(kuò)散的目的。另一種方法是一種方法是加檢錯(cuò)糾錯(cuò)碼加檢錯(cuò)糾錯(cuò)碼。誤差擴(kuò)散問題誤差擴(kuò)散問題26由于絕大多數(shù)信源其消息是不等概率的，因而編成的變由于絕大多數(shù)信源其消息是不等概率的，因而編成的變長碼長度也是不相等的，這必然導(dǎo)致信源輸出速率是變長碼長度也是不相等的，這必然導(dǎo)致信源輸出速率是變化的，然而在實(shí)際信道中

24、傳送的信息率是固定不變化的?；模欢趯?shí)際信道中傳送的信息率是固定不變化的。因而因而信源與信道之間必然存在一個(gè)速率匹配信源與信道之間必然存在一個(gè)速率匹配問題。問題。解決該問題的辦法，在工程上一般解決該問題的辦法，在工程上一般采用緩沖存儲(chǔ)器的方采用緩沖存儲(chǔ)器的方法以達(dá)到變速輸入，恒速輸出法以達(dá)到變速輸入，恒速輸出。但是這個(gè)緩存器的容量。但是這個(gè)緩存器的容量選取顯然與輸入變速特性即信源統(tǒng)計(jì)特性和編碼方法，選取顯然與輸入變速特性即信源統(tǒng)計(jì)特性和編碼方法，以及輸出速率密切相關(guān)。這是一個(gè)需要在實(shí)際的工程設(shè)以及輸出速率密切相關(guān)。這是一個(gè)需要在實(shí)際的工程設(shè)計(jì)中進(jìn)一步深入探討的問題。計(jì)中進(jìn)一步深入探討的問題

25、。速率匹配問題速率匹配問題27香農(nóng)碼、費(fèi)諾碼、哈夫曼碼香農(nóng)碼、費(fèi)諾碼、哈夫曼碼都考慮了信源的都考慮了信源的統(tǒng)計(jì)特性統(tǒng)計(jì)特性,使使經(jīng)常出現(xiàn)的信源符號(hào)對(duì)應(yīng)較短的碼字經(jīng)常出現(xiàn)的信源符號(hào)對(duì)應(yīng)較短的碼字,使信源的平均碼長使信源的平均碼長縮短縮短,從而實(shí)現(xiàn)了對(duì)信源的壓縮；從而實(shí)現(xiàn)了對(duì)信源的壓縮；香農(nóng)碼香農(nóng)碼有系統(tǒng)的、有系統(tǒng)的、唯唯一一的編碼方法的編碼方法,但在很多情況下編碼但在很多情況下編碼效率不是很高；效率不是很高；費(fèi)諾費(fèi)諾碼和碼和哈夫曼哈夫曼碼的編碼方法都碼的編碼方法都不不唯唯一一；費(fèi)諾碼比較適合于對(duì)分組概率相等或接近的信源編碼費(fèi)諾碼比較適合于對(duì)分組概率相等或接近的信源編碼,費(fèi)費(fèi)諾碼也可以編諾碼也可以

26、編m進(jìn)制碼進(jìn)制碼,但但m越大越大,信源的符號(hào)數(shù)越多信源的符號(hào)數(shù)越多,可能可能的編碼方案就越多的編碼方案就越多,編碼過程就越復(fù)雜編碼過程就越復(fù)雜,有時(shí)短碼未必能得有時(shí)短碼未必能得到充分利用；到充分利用；哈夫曼碼哈夫曼碼對(duì)信源的統(tǒng)計(jì)特性沒有特殊要求對(duì)信源的統(tǒng)計(jì)特性沒有特殊要求,編碼效率比較編碼效率比較高高,對(duì)編碼設(shè)備的要求也比較簡(jiǎn)單對(duì)編碼設(shè)備的要求也比較簡(jiǎn)單,因此因此綜合性能優(yōu)于綜合性能優(yōu)于香農(nóng)香農(nóng)碼和費(fèi)諾碼。碼和費(fèi)諾碼?？偨Y(jié)總結(jié)28信源符號(hào)信源符號(hào)X有有8種消息，概率為種消息，概率為(1/2,1/4,1/8, 1/16, 1/32,1/64,1/128,1/128)(1)用香農(nóng)編碼編成二進(jìn)變長碼

27、，計(jì)算其編碼效率。用香農(nóng)編碼編成二進(jìn)變長碼，計(jì)算其編碼效率。(2)用費(fèi)諾編碼編成二進(jìn)變長碼，計(jì)算其編碼效率。用費(fèi)諾編碼編成二進(jìn)變長碼，計(jì)算其編碼效率。(3)用哈夫曼編碼編成二進(jìn)變長碼，計(jì)算其編碼效率。用哈夫曼編碼編成二進(jìn)變長碼，計(jì)算其編碼效率。舉例舉例29解解: 二進(jìn)制香農(nóng)編碼二進(jìn)制香農(nóng)編碼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費(fèi)諾編碼費(fèi)諾編碼舉例舉例31碼字碼字字長（1/2）（1/4）（1/8）（1/16）（1/32）（1/64）哈夫曼編碼哈夫曼編碼舉

29、例舉例32習(xí)題習(xí)題5-12作業(yè)作業(yè)335.3限失真信源編碼定理限失真信源編碼定理在很多實(shí)際信源中在很多實(shí)際信源中,特別在模擬的連續(xù)信源中特別在模擬的連續(xù)信源中,無無失真要求是完全沒有必要的失真要求是完全沒有必要的,而且也是達(dá)不到的。而且也是達(dá)不到的。在實(shí)際中限失真信源在實(shí)際中限失真信源編碼編碼是具有現(xiàn)實(shí)意義的是具有現(xiàn)實(shí)意義的。信息率失真函數(shù)給出了失真小于信息率失真函數(shù)給出了失真小于D時(shí)所必須具有的最時(shí)所必須具有的最小信息率小信息率R(D)；只要信息率大于；只要信息率大于R(D)，一定可以找，一定可以找到一種編碼，使譯碼后的失真小于到一種編碼，使譯碼后的失真小于D。 34限失真信源編碼定理限失真

30、信源編碼定理限失真信源編碼定理：限失真信源編碼定理： 設(shè)離散無記憶信源設(shè)離散無記憶信源X的信息率失真函數(shù)為的信息率失真函數(shù)為R(D) , 當(dāng)信息率當(dāng)信息率 RR(D)時(shí)時(shí),只要信源序列長度只要信源序列長度 L 足夠長足夠長,一定存在一種編碼方法一定存在一種編碼方法,其譯碼失真小于或等于其譯碼失真小于或等于D+,為任意小的正數(shù)；為任意小的正數(shù)； 反之反之,若若RR(D) ,則無論采用什么樣的編碼方法則無論采用什么樣的編碼方法,其其譯碼失真必大于譯碼失真必大于D。 如是二元信源如是二元信源,則對(duì)于任意小的則對(duì)于任意小的0,每一個(gè)信源符號(hào)每一個(gè)信源符號(hào)的平均碼長滿足如下公式：的平均碼長滿足如下公式：

31、R(D) K R(D) 35限失真信源編碼定理限失真信源編碼定理限失真信源編碼定理限失真信源編碼定理只能說明只能說明最佳編碼最佳編碼是存在的，是存在的，而具體構(gòu)造編碼方法卻一無所知。因而就不能象無而具體構(gòu)造編碼方法卻一無所知。因而就不能象無損編碼那樣從證明過程中引出概率匹配的編碼方法。損編碼那樣從證明過程中引出概率匹配的編碼方法。一般只能從優(yōu)化的思路去求最佳編碼。實(shí)際上迄今一般只能從優(yōu)化的思路去求最佳編碼。實(shí)際上迄今尚無合適的可實(shí)現(xiàn)的編碼方法可接近尚無合適的可實(shí)現(xiàn)的編碼方法可接近R(D)這個(gè)界。這個(gè)界。 36對(duì)信源編碼定理的統(tǒng)一理解對(duì)信源編碼定理的統(tǒng)一理解 定長信源無失真編碼定理：定長信源無失

32、真編碼定理： 變長信源無失真編碼定理（香農(nóng)第一定理）：變長信源無失真編碼定理（香農(nóng)第一定理）： 保真度準(zhǔn)則下的信源編碼定理（香農(nóng)第三定理）：保真度準(zhǔn)則下的信源編碼定理（香農(nóng)第三定理）： 從編碼信息率的角度，當(dāng)從編碼信息率的角度，當(dāng)時(shí)，則信源編碼無失真或失真可控。時(shí)，則信源編碼無失真或失真可控。()loglog()KRKH XLHmmXL lo()l(gg)oLLKRKHmHLXLmX()RR D ()()RH XRR D或37常用信源編碼常用信源編碼香農(nóng)編碼、費(fèi)諾編碼、哈夫曼編碼主要是針對(duì)香農(nóng)編碼、費(fèi)諾編碼、哈夫曼編碼主要是針對(duì)無記無記憶憶信源，屬于信源，屬于無失真信源編碼無失真信源編碼； 當(dāng)信源有記憶時(shí)上述編碼效率不高；當(dāng)信源有記憶時(shí)上述編碼效率不高； 游程編碼游程編碼 算術(shù)編碼算術(shù)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼變換編碼變換編碼385.4.1 游程編碼游程編碼游程游程： 數(shù)字序列中連續(xù)出現(xiàn)相同符號(hào)的一段。數(shù)字序列中連續(xù)出現(xiàn)相同符號(hào)的一段。二元序列的游程：只有二元序列的游程：只有“0”和和“1”