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

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

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

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

4、則信源長度則信源長度必須滿足必須滿足:22L 2(X) EI(xi) H(X)2 信源序列的自信息方差信源序列的自信息方差為了衡量編碼效果為了衡量編碼效果,定義定義編碼效率編碼效率：最佳編碼效率最佳編碼效率：5H L(X) 變長編碼定理變長編碼定理 1H(X)log m K 離散平穩(wěn)無記憶序列變長編碼定理離散平穩(wěn)無記憶序列變長編碼定理 對于平均符號熵為對于平均符號熵為HL(X)的離散平穩(wěn)無記憶信源的離散平穩(wěn)無記憶信源,必存在一種必存在一種 無失真編碼方法無失真編碼方法,使平均信息率使平均信息率 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、源符號編以短的碼字。概率小將概率大的信源符號編以短的碼字。概率小的符號編以長的碼字，這樣使得平均碼字長度最短。的符號編以長的碼字，這樣使得平均碼字長度最短。 主要有：主要有： 香農(nóng)香農(nóng)（Shannon） 費諾費諾（Fano） 哈夫曼哈夫曼（Huffma ）7香農(nóng)編碼香農(nóng)編碼香農(nóng)第一定理指出了香農(nóng)第一定理指出了平均碼長平均碼長與與信源信源之間的關(guān)系之間的關(guān)系,同同時也指出了可以通過編碼使平均碼長達到時也指出了可以通過編碼使平均碼長達到極限值極限值,這這是一個很重要的極限定理。是一個很重要的極限定理。 香農(nóng)第一定理指出香農(nóng)第一定理指出,選擇每個碼字的長度選擇每個碼字的長度Ki滿足下式：滿足下式：或

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

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

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

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

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

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

14、(x2) p(xn)取兩個取兩個概率最小概率最小的字母分別配以的字母分別配以0和和1兩碼元兩碼元,并將這并將這兩個兩個概率相加概率相加作為一個作為一個新字母新字母的概率的概率,與未分配的二與未分配的二進符號的字母進符號的字母重新排隊重新排隊。 對重排后的兩個概率最小符號重復(fù)步驟的過程。對重排后的兩個概率最小符號重復(fù)步驟的過程。不斷繼續(xù)上述過程不斷繼續(xù)上述過程,直到最后兩個符號直到最后兩個符號配以配以0和和1為止。為止。 從最后一級開始從最后一級開始,向前返回向前返回得到各個信源符號所對應(yīng)得到各個信源符號所對應(yīng)的碼元序列的碼元序列,即相應(yīng)的碼字。即相應(yīng)的碼字。哈夫曼編碼哈夫曼編碼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 設(shè)單符號離散無記憶信源如下設(shè)單符號離散無記憶信源如下, ,要求對信源要求對信源編編二進制二進制哈夫曼碼。編碼過程如下表哈夫曼碼。編碼過程如下表哈夫曼編碼哈夫曼編碼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不變不變,平均碼長也不變平均碼長也不變,所以沒有本質(zhì)區(qū)別；所以沒有本質(zhì)區(qū)別； 縮減信源時縮減信源時,若合并后的新符號概率與其他符號概率若合并后的新符號概率與其他符號概率相等相等,從編碼方法上來說從編碼方法上來說,這幾個符號的這幾個符號的次序可任意排次序可任意排列列,編出的碼都是正確的編出的碼都是正確的,但得到的但得到的碼字不相同碼字不相同。 不同的編法得到的碼字長度不同的編法得到的碼字長度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、長； 第二種方法編出的碼長只有兩種不同的碼長；第二種方法編出的碼長只有兩種不同的碼長； 第二種編碼方法更簡單、更容易實現(xiàn)第二種編碼方法更簡單、更容易實現(xiàn),所以更好。所以更好。 結(jié)論：結(jié)論： 在哈夫曼編碼過程中在哈夫曼編碼過程中,對縮減信源符號按概率由大到小的順序?qū)s減信源符號按概率由大到小的順序重新排列時重新排列時,應(yīng)使合并后的應(yīng)使合并后的新符號盡可能排在靠前新符號盡可能排在靠前的位置的位置,這樣這樣可使合并后的新符號重復(fù)編碼次數(shù)減少可使合并后的新符號重復(fù)編碼次數(shù)減少,使短碼得到充分利用。使短碼得到充分利用。 特征特征:是是一種分組碼一種分組碼：各個信源符號都被映射成一組固定次序的碼：各個信源

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

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

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

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

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

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

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

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

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

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

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