信息論第8章北理工

1、1第一節(jié)第一節(jié) 香農(nóng)編碼香農(nóng)編碼第八章第八章 無失真的信源編碼無失真的信源編碼2信源編碼概述信源編碼概述o 信源編碼理論是信息論的一個重要分支，其理信源編碼理論是信息論的一個重要分支，其理 論基礎是信源編碼的兩個定理。論基礎是信源編碼的兩個定理。n 無失真信源編碼無失真信源編碼：針對離散信源或數(shù)字信號：針對離散信源或數(shù)字信號n 限失真信源編碼限失真信源編碼：適用于波形信源或波形信號（模：適用于波形信源或波形信號（模擬信號）。擬信號）。信源編碼的分類：離散信源編碼、連續(xù)信源編碼和相信源編碼的分類：離散信源編碼、連續(xù)信源編碼和相關信源編碼三類。關信源編碼三類。n 離散信源編碼離散信源編碼：獨立信源

2、編碼，可做到無失真：獨立信源編碼，可做到無失真編碼；編碼；n 連續(xù)信源編碼連續(xù)信源編碼：獨立信源編碼，只能做到限失：獨立信源編碼，只能做到限失真信源編碼；真信源編碼；n 相關信源編碼相關信源編碼：非獨立信源編碼。：非獨立信源編碼。3o 有些編碼原理和技術在通信原理和信號處理等有些編碼原理和技術在通信原理和信號處理等相關課程中已經(jīng)介紹過。例如：相關課程中已經(jīng)介紹過。例如：n連續(xù)信源編碼：脈沖編碼調(diào)制連續(xù)信源編碼：脈沖編碼調(diào)制(PCM)(PCM)、矢量量、矢量量化技術；化技術；n相關信源編碼：相關信源編碼：o預測編碼預測編碼：增量編碼、差分脈沖調(diào)制：增量編碼、差分脈沖調(diào)制(DPCM)(DPCM)、

3、自適應差分脈沖調(diào)制自適應差分脈沖調(diào)制(ADPCM)(ADPCM)、線性預測聲、線性預測聲碼器；碼器；o變換編碼變換編碼：K KL L變換、離散變換、子帶編碼、變換、離散變換、子帶編碼、小波變換。小波變換。4定理定理5.8 5.8 無失真變長信源編碼定理（香農(nóng)第一定理）無失真變長信源編碼定理（香農(nóng)第一定理）離散無記憶信源離散無記憶信源S的的N次擴展信源次擴展信源 ，其熵為，其熵為 ，并且編，并且編碼器的碼元符號集為碼器的碼元符號集為A： 對信源對信源 進行編碼，總進行編碼，總可以找到一種編碼方法，構成唯一可譯碼，使信源可以找到一種編碼方法，構成唯一可譯碼，使信源S中每個符中每個符號所需要的平均碼

4、長滿足號所需要的平均碼長滿足 NS()NH S12,.,q NS()()1loglogNHSLHSrNrNlim( )rNLHS當 則得：N 回顧香農(nóng)第一定理回顧香農(nóng)第一定理5 這個定理是香農(nóng)信息論中非常重要的一個定理，這個定理是香農(nóng)信息論中非常重要的一個定理，它指出，要做到無失真的信源編碼，信源每個符號它指出，要做到無失真的信源編碼，信源每個符號所需要的平均碼元數(shù)就是信源的熵值，如果小于這所需要的平均碼元數(shù)就是信源的熵值，如果小于這個值，則唯一可譯碼不存在，可見，個值，則唯一可譯碼不存在，可見，熵是無失真信熵是無失真信源編碼的極限值源編碼的極限值。定理還指出，通過對擴展信源進。定理還指出，通

5、過對擴展信源進行編碼，當行編碼，當N N趨向于無窮時，平均碼長可以趨近該趨向于無窮時，平均碼長可以趨近該極限值。極限值。 6第一節(jié)第一節(jié) 香農(nóng)編碼香農(nóng)編碼qiiqqxpxpxpxpxxx121211)(,)(.)()(.設有離散無記憶信源設有離散無記憶信源7)(log)(logiiixplxp221的的碼碼字字位位作作為為點點后后的的用用二二進進制制表表示示，用用小小數(shù)數(shù)把把iijaxlxp)(1234香農(nóng)編碼方法的步驟香農(nóng)編碼方法的步驟按信源符號的概率從大到小的順序排隊)(.)()(qxpxpxp21設設個碼字的累加概率表示第，用令iijxpxpja1),(0)(0111)()(jiijax

6、pxp8 例例 有一單符號離散無記憶信源有一單符號離散無記憶信源o 對該信源編二進制香農(nóng)碼。其編碼過程如下表所示。對該信源編二進制香農(nóng)碼。其編碼過程如下表所示。05.010.015.020.025.025.0,)(654321xxxxxxXPX表表5.1.1 二進制香農(nóng)編碼二進制香農(nóng)編碼xip(xi)pa(xj)li碼字碼字x10.250200(0.000)2x20.250.25201(0.010)2x30.20.53100(0.100)2x40.150.73101(0.101)2x50.10.8541101(0.1101)2x60.050.955111110(0.11110)29o計算出給定

7、信源香農(nóng)碼的平均碼長計算出給定信源香農(nóng)碼的平均碼長o若對上述信源采用等長編碼，要做到無失真譯碼，每若對上述信源采用等長編碼，要做到無失真譯碼，每個符號至少要用個符號至少要用3 3個比特表示。相比較，香農(nóng)編碼對信個比特表示。相比較，香農(nóng)編碼對信源進行了壓縮。源進行了壓縮。)/(.).(.)(符號符號比特比特7250504100315020222501qiiilxpL10o 由離散無記憶信源熵定義，可計算出：由離散無記憶信源熵定義，可計算出：o 對上述信源采用香農(nóng)編碼的信息率為對上述信源采用香農(nóng)編碼的信息率為o 編碼效率為信源熵和信息率之比。則編碼效率為信源熵和信息率之比。則可以看出，編碼效率并不

8、是很高?？梢钥闯?，編碼效率并不是很高。)/(42. 2)x(plog)x(p)X(H61ii2i符號符號比特比特2172217222rNrNLR,.log.log這里這里%63.897 . 242. 2)(RXH11第二節(jié)第二節(jié) 費諾編碼費諾編碼 費諾編碼也是一種常見的信源編碼方法。編碼步驟費諾編碼也是一種常見的信源編碼方法。編碼步驟如下：如下：o 將概率按從大到小的順序排列，令將概率按從大到小的順序排列，令p p( (x x1 1) ) p p( (x x2 2) p p( (x xq q) )o 按編碼進制數(shù)將概率分組，使每組概率和盡可能按編碼進制數(shù)將概率分組，使每組概率和盡可能接近或相等

9、。如編二進制碼就分成兩組，編接近或相等。如編二進制碼就分成兩組，編r r進進制碼就分成制碼就分成r r組。組。o 給每一組分配一位碼元。給每一組分配一位碼元。o 將每一分組再按同樣原則劃分，重復步驟將每一分組再按同樣原則劃分，重復步驟2 2和和3 3，直至概率不再可分為止。直至概率不再可分為止。12 例例 設有一單符號離散信源設有一單符號離散信源o 對該信源編二進制費諾碼。編碼過程如下表。對該信源編二進制費諾碼。編碼過程如下表。05. 010. 015. 020. 025. 025. 0 x,x,x,x,x,x)X(PX654321表5.3.1 二進制費諾編碼信源符號信源符號概率概率編碼編碼碼

10、字碼字碼長碼長x10.2500002x20.251012x30.2010102x40.15101103x50.101011104x60.0511111413o 上述碼字還可用碼樹來表示，如圖下所示。14o 該信源的熵為該信源的熵為o 平均碼長為平均碼長為o 編碼效率為編碼效率為o 本例中費諾編碼有較高的編碼效率。費諾碼比較適合本例中費諾編碼有較高的編碼效率。費諾碼比較適合于于每次分組概率都很接近每次分組概率都很接近的信源。特別是對每次的信源。特別是對每次分組分組概率都相等概率都相等的信源進行編碼時，可達到理想的編碼效的信源進行編碼時，可達到理想的編碼效率。率。)/(42325. 2)x(plo

11、g)x(p)X(H61ii2i符號符號比特比特)/(.)(符號符號比特比特61452iiilxpL219198452423224232214522rNrXHNL,%.log.log)(.這里這里15 例例 有一單符號離散無記憶信源有一單符號離散無記憶信源o對該信源編二進制費諾碼，編碼過程如表。對該信源編二進制費諾碼，編碼過程如表。16/116/116/116/18/18/14/14/1,)(87654321xxxxxxxxXPX16o 碼樹圖如圖。碼樹圖如圖。o 信源熵為信源熵為 H H( (X X)=2.75()=2.75(比特比特/ /符號符號) )o 平均碼長為平均碼長為o 編碼效率為編

12、碼效率為=1=1。之所以如此，因為每次所分兩組的概率恰。之所以如此，因為每次所分兩組的概率恰好相等。好相等。)/(.).(符號符號比特比特7524406250321202250250L17第三節(jié)第三節(jié) 霍夫曼編碼霍夫曼編碼 霍夫曼霍夫曼(Huffman)編碼是一種效率比較高的變長編碼是一種效率比較高的變長無失真信源編碼方法。無失真信源編碼方法。o編碼步驟編碼步驟o二進制霍夫曼編碼二進制霍夫曼編碼or進制霍夫曼編碼進制霍夫曼編碼18o 將信源符號按概率從大到小的順序排列，令將信源符號按概率從大到小的順序排列，令p(x1) p(x2) p(xq)o 給兩個概率最小的信源符號給兩個概率最小的信源符號

13、p(xn-1)和和p(xn)各分配一個碼位各分配一個碼位“0”和和“1”，將這兩個信源符號合并成一個新符號，并用這兩個，將這兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，結果得到一個只包含最小的概率之和作為新符號的概率，結果得到一個只包含(q1)個信源符號的新信源。稱為個信源符號的新信源。稱為信源的第一次縮減信源信源的第一次縮減信源，用，用S1表示。表示。o 將縮減信源將縮減信源S1的符號仍按概率從大到小順序排列，重復步驟的符號仍按概率從大到小順序排列，重復步驟2，得到只含得到只含(q2)個符號的縮減信源個符號的縮減信源S2。o 重復上述步驟，直至縮減信源只剩兩個符號

14、為止，此時所剩重復上述步驟，直至縮減信源只剩兩個符號為止，此時所剩兩個符號的概率之和必為兩個符號的概率之和必為1。然后從最后一級縮減信源開始，。然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應的碼字。依編碼路徑向前返回，就得到各信源符號所對應的碼字。19例例 設單符號離散無記憶信源如下，要求對信源編二進制設單符號離散無記憶信源如下，要求對信源編二進制 霍夫曼碼。編碼過程如下圖（后頁）。霍夫曼碼。編碼過程如下圖（后頁）。12345678,()0.40.180.10.10.070.060.050.04XxxxxxxxxP Xn在圖中讀取碼字的時候，一定要從后向前讀，此時編出在

15、圖中讀取碼字的時候，一定要從后向前讀，此時編出來的碼字才是可分離的異前置碼。若從前向后讀取碼字，來的碼字才是可分離的異前置碼。若從前向后讀取碼字，則碼字不可分離。則碼字不可分離。2021o 將上圖左右顛倒過來重畫一下，即可得到二進制哈夫?qū)⑸蠄D左右顛倒過來重畫一下，即可得到二進制哈夫曼碼的碼樹。曼碼的碼樹。22o 信源熵為：信源熵為：o 平均碼長為平均碼長為o 編碼效率為編碼效率為o 若采用定長編碼，碼長若采用定長編碼，碼長L=3，則編碼效率，則編碼效率o 可見哈夫曼的編碼效率提高了可見哈夫曼的編碼效率提高了12.7%。821( )( )log( )2.55(/)iiiH Xp xp x比特 符

16、號()()2.552.6197.7%HXHXRK2.55385%)/(.)(符號符號比特比特81612iiilxpL23注意：注意：哈夫曼的編法并不惟一哈夫曼的編法并不惟一。o每次對縮減信源兩個概率最小的符號分配每次對縮減信源兩個概率最小的符號分配“0 0”和和“1 1”碼元是任意的，所以可得到不同的碼字。只碼元是任意的，所以可得到不同的碼字。只要要在各次縮減信源中保持碼元分配的一致性在各次縮減信源中保持碼元分配的一致性，即即能得到可分離碼字。能得到可分離碼字。o不同的碼元分配，得到的具體碼字不同，但碼長不同的碼元分配，得到的具體碼字不同，但碼長L Li i不變，平均碼長也不變，所以沒有本質(zhì)區(qū)

17、別；不變，平均碼長也不變，所以沒有本質(zhì)區(qū)別；o縮減信源時，若合并后的新符號概率與其他符號縮減信源時，若合并后的新符號概率與其他符號概率相等，從編碼方法上來說，概率相等，從編碼方法上來說，這幾個符號的次這幾個符號的次序可任意排列，編出的碼都是正確的，但得到的序可任意排列，編出的碼都是正確的，但得到的碼字不相同碼字不相同。不同的編法得到的不同的編法得到的碼字長度碼字長度L Li i也不也不盡相同盡相同。24例例 設有離散無記憶信源設有離散無記憶信源1 . 01 . 02 . 02 . 04 . 0)(54321xxxxxXPX用兩種不同的方法對其編二進制用兩種不同的方法對其編二進制huffmanh

18、uffman碼碼25方法一方法一方法二方法二26 27信源符號信源符號xi概率概率p(xi) 碼字碼字Wi1碼長碼長Li1碼字碼字Wi2碼長碼長Li2x10.411002x20.2012102x30.20003112x40.1001040103x50.1001140113兩種不同的編碼方法得到的碼字和碼長的對比兩種不同的編碼方法得到的碼字和碼長的對比28兩種編碼的平均碼長是一樣的，都是兩種編碼的平均碼長是一樣的，都是2.2，那一種更好，那一種更好呢，我們可以計算一下平均碼長的方差。呢，我們可以計算一下平均碼長的方差。511( )0.4 1 0.2 20.2 30.1 40.1 42.2iiiL

19、P s l 521( )0.4 20.2 20.2 20.1 30.1 32.2iiiLP s l 2221() ( )()qiiiiE lLP slL522111( )()1.36iiiP slL522221( )()0.16iiiP slL定義碼字長度的方差定義碼字長度的方差2：29n可見：第二種編碼方法的碼長方差要小許多。意味著可見：第二種編碼方法的碼長方差要小許多。意味著第二種編碼方法的碼長變化較小，比較接近于平均碼第二種編碼方法的碼長變化較小，比較接近于平均碼長。長。l第一種方法編出的第一種方法編出的5 5個碼字有個碼字有4 4種不同的碼長；種不同的碼長；l第二種方法編出的碼長只有兩

20、種不同的碼長；第二種方法編出的碼長只有兩種不同的碼長；l顯然，顯然，第二種編碼方法更簡單、更容易實現(xiàn)，所以第二種編碼方法更簡單、更容易實現(xiàn)，所以更好更好。結論：結論：在哈夫曼編碼過程中，對縮減信源符號按概率由大在哈夫曼編碼過程中，對縮減信源符號按概率由大到小的順序重新排列時，應到小的順序重新排列時，應使合并后的新符號盡可能使合并后的新符號盡可能排在靠前的位置排在靠前的位置，這樣可使合并后的新符號重復編碼，這樣可使合并后的新符號重復編碼次數(shù)減少，使短碼得到充分利用。次數(shù)減少，使短碼得到充分利用。30“全樹全樹”概念概念o 定義：碼樹圖中每個中間節(jié)點后續(xù)的枝數(shù)為定義：碼樹圖中每個中間節(jié)點后續(xù)的枝數(shù)

21、為r時稱為時稱為全樹全樹；若有些節(jié)點的后續(xù)枝數(shù)不足若有些節(jié)點的后續(xù)枝數(shù)不足r，就稱為，就稱為非全樹非全樹。o 二進制碼不存在非全樹的情況，因為后續(xù)枝數(shù)是二進制碼不存在非全樹的情況，因為后續(xù)枝數(shù)是1時，這個時，這個枝就可以去掉使碼字長度縮短。枝就可以去掉使碼字長度縮短。o 對對r進制編碼：若所有碼字構成全樹，可分離的碼字數(shù)（信進制編碼：若所有碼字構成全樹，可分離的碼字數(shù)（信源個數(shù)）必為源個數(shù)）必為 r+k(r1)。k為信源縮減次數(shù)。為信源縮減次數(shù)。o 若信源所含的符號數(shù)若信源所含的符號數(shù)q不能構成不能構成r進制全樹，必須增加進制全樹，必須增加s個不個不用的碼字形成全樹。用的碼字形成全樹。31o

22、在編在編r進制哈夫曼碼時為了使平均碼長最短，必須使最進制哈夫曼碼時為了使平均碼長最短，必須使最后一步縮減信源有后一步縮減信源有r個信源符號。非全樹時，有個信源符號。非全樹時，有s個碼字個碼字不用不用.n 第一次對最小概率符號分配碼元時就只取第一次對最小概率符號分配碼元時就只取(rs)個，個，分別配以分別配以0,1,rs1，把這些符號的概率相加作，把這些符號的概率相加作為一個新符號的概率，與其它符號一起重新排列。為一個新符號的概率，與其它符號一起重新排列。n 以后每次就可以取以后每次就可以取r個符號，分別配以個符號，分別配以0,1,r1；如此下去，直至所有概率相加得如此下去，直至所有概率相加得1

23、為止，即得到各符為止，即得到各符號的號的r進制碼字。進制碼字。32例：對如下單符號離散無記憶信源編三進制哈夫曼碼。例：對如下單符號離散無記憶信源編三進制哈夫曼碼。這里：這里：r=3，q=8o 令令k=3，r+k(r1)=9，則，則 s=9q=98=1o 所以第一次取所以第一次取rs=2個符號進行編碼。個符號進行編碼。12345678,()0.40.180.10.10.070.060.050.04XxxxxxxxxP X333435o 平均碼長為平均碼長為o 信息率為信息率為o 編碼效率為編碼效率為o 可見：哈夫曼的編碼效率相當高，對編碼器的要求可見：哈夫曼的編碼效率相當高，對編碼器的要求也簡單

24、得多。也簡單得多。)/(.).().(.)(符號符號比特比特6913040050206007010180140511iiilxpL)/(.log.log符號符號比特比特68231691322NLR%2 .9568. 255. 2)(RXH36(3) (3) 結論結論o 香農(nóng)碼、費諾碼、赫夫曼碼都考慮了信源的統(tǒng)計特性，使香農(nóng)碼、費諾碼、赫夫曼碼都考慮了信源的統(tǒng)計特性，使經(jīng)常出現(xiàn)的信源符號對應較短的碼字，使信源的平均碼長經(jīng)常出現(xiàn)的信源符號對應較短的碼字，使信源的平均碼長縮短，從而實現(xiàn)了對信源的壓縮；縮短，從而實現(xiàn)了對信源的壓縮；o 香農(nóng)碼有系統(tǒng)的、惟一的編碼方法，但在很多情況下編碼香農(nóng)碼有系統(tǒng)的、

25、惟一的編碼方法，但在很多情況下編碼效率不是很高；效率不是很高；o 費諾碼和赫夫曼碼的編碼方法都不惟一；費諾碼和赫夫曼碼的編碼方法都不惟一；o 費諾碼比較適合于對分組概率相等或接近的信源編碼，費費諾碼比較適合于對分組概率相等或接近的信源編碼，費諾碼也可以編諾碼也可以編r r進制碼，但進制碼，但r r越大，信源的符號數(shù)越多，可越大，信源的符號數(shù)越多，可能的編碼方案就越多，編碼過程就越復雜，有時短碼未必能的編碼方案就越多，編碼過程就越復雜，有時短碼未必能得到充分利用；能得到充分利用；o 赫夫曼碼對信源的統(tǒng)計特性沒有特殊要求，編碼效率比較赫夫曼碼對信源的統(tǒng)計特性沒有特殊要求，編碼效率比較高，對編碼設備

26、的要求也比較簡單，因此綜合性能優(yōu)于香高，對編碼設備的要求也比較簡單，因此綜合性能優(yōu)于香農(nóng)碼和費諾碼農(nóng)碼和費諾碼。37實際使用中注意的問題實際使用中注意的問題o 誤差擴散問題：誤差擴散問題： 實際信道中有噪聲存在，必然要破壞變長碼的實際信道中有噪聲存在，必然要破壞變長碼的結構。同時由于變長碼是不加同步的碼，無法自結構。同時由于變長碼是不加同步的碼，無法自動清洗產(chǎn)生的錯誤使得產(chǎn)生的錯誤擴散。動清洗產(chǎn)生的錯誤使得產(chǎn)生的錯誤擴散。 在工程上哈夫曼碼只能適合于高信噪比的優(yōu)在工程上哈夫曼碼只能適合于高信噪比的優(yōu)質(zhì)信道，如：誤碼率低于質(zhì)信道，如：誤碼率低于1010-6-6以下。以下。 工程上還常常采用定期清

27、洗的方法，如在文件工程上還常常采用定期清洗的方法，如在文件或報紙中采用按行清洗的方式，以犧牲編碼效率或報紙中采用按行清洗的方式，以犧牲編碼效率達到限制誤差擴散的目的。達到限制誤差擴散的目的。38o 速率匹配問題速率匹配問題 由于信源消息是不等概率的，因而編成的變長由于信源消息是不等概率的，因而編成的變長碼長度也是不相同的，這必然導致信源輸出速率是碼長度也是不相同的，這必然導致信源輸出速率是變化的，然而在實際信道中傳送的信息率是變化的，然而在實際信道中傳送的信息率是固定不固定不變化變化的。的。 一般在工程中采用緩沖存儲器的方法，變速輸一般在工程中采用緩沖存儲器的方法，變速輸入恒速輸出，存儲器容量

28、的選取與信源統(tǒng)計特性和入恒速輸出，存儲器容量的選取與信源統(tǒng)計特性和編碼方法，以及輸出速率密切相關。容量選大了浪編碼方法，以及輸出速率密切相關。容量選大了浪費設備，容量小了會產(chǎn)生溢出或取空現(xiàn)象。費設備，容量小了會產(chǎn)生溢出或取空現(xiàn)象。實際使用中注意的問題39o 與信源統(tǒng)計特性相匹配的問題與信源統(tǒng)計特性相匹配的問題 一般變長碼更適合于大的消息集，而不大一般變長碼更適合于大的消息集，而不大適合消息集小且概率分布相差很大的集合。小適合消息集小且概率分布相差很大的集合。小集合只有在很特殊情況下才能實現(xiàn)統(tǒng)計匹配。集合只有在很特殊情況下才能實現(xiàn)統(tǒng)計匹配。 如果信源的統(tǒng)計特性不完全知道，則無如果信源的統(tǒng)計特性不

29、完全知道，則無法實現(xiàn)變長編碼。法實現(xiàn)變長編碼。實際使用中注意的問題40第四節(jié)第四節(jié) 游程編碼游程編碼一一. .游程編碼對象和性質(zhì)游程編碼對象和性質(zhì)二二. . 游程編碼的定義游程編碼的定義三三. . 二元獨立序列二元獨立序列四四. . 游程編碼的效率游程編碼的效率五五. . 長碼的截斷處理方法長碼的截斷處理方法41一一. . 游程編碼對象和性質(zhì)游程編碼對象和性質(zhì)o香農(nóng)編碼、費諾編碼、哈夫曼編碼主要是針對無記憶香農(nóng)編碼、費諾編碼、哈夫曼編碼主要是針對無記憶信源。當信源有記憶時上述編碼效率不高；信源。當信源有記憶時上述編碼效率不高；o游程編碼對游程編碼對相關信源相關信源編碼更有效；編碼更有效；o香農(nóng)

30、編碼、費諾編碼、哈夫曼編碼屬于香農(nóng)編碼、費諾編碼、哈夫曼編碼屬于無失真信源編無失真信源編碼碼；o游程編碼屬于游程編碼屬于限失真信源編碼限失真信源編碼。42二二. . 游程編碼的定義游程編碼的定義o游程游程：數(shù)字序列中連續(xù)出現(xiàn)相同符號的一段。：數(shù)字序列中連續(xù)出現(xiàn)相同符號的一段。o二元序列的游程：只有二元序列的游程：只有“0 0”和和“1 1”兩種符號。兩種符號。n連連“0 0”這一段稱為這一段稱為“0 0”游程，它的長度稱為游程，它的長度稱為游程游程長度長度L L(0)(0)；n連連“1 1”這一段稱為這一段稱為“1 1”游程，它的游程長度用游程，它的游程長度用L L(1)(1)表示。表示。43

31、三三. . 二元獨立序列二元獨立序列 二元獨立序列游程長度概率二元獨立序列游程長度概率o若規(guī)定二元序列總是從若規(guī)定二元序列總是從“0 0”開始，第一個游程是開始，第一個游程是“0 0”游程，則第二個游程必為游程，則第二個游程必為“1 1”游程，第三個又游程，第三個又是是“0 0”游程游程。o對于隨機序列，游程長度是隨機的其取值可為對于隨機序列，游程長度是隨機的其取值可為1,2,3,1,2,3,，直至無窮。，直至無窮。44o游程長度序列游程長度序列/ /游程序列：用交替出現(xiàn)的游程序列：用交替出現(xiàn)的“0 0”游程和游程和“1 1”游程長度表示任意二元序列。游程長度表示任意二元序列。o游程變換游程變

32、換：是一種一一對應的變換，也是可逆變換。：是一種一一對應的變換，也是可逆變換。 例如：二元序列例如：二元序列 000101110010001000101110010001 可變換成如下游程序列可變換成如下游程序列 3113213131132131o游程變換減弱了原序列符號間的相關性。游程變換減弱了原序列符號間的相關性。o游程變換游程變換將二元序列變換成了多元序列將二元序列變換成了多元序列；這樣就適；這樣就適合于用其他方法，如哈夫曼編碼，進一步壓縮信源，合于用其他方法，如哈夫曼編碼，進一步壓縮信源，提高通信效率。提高通信效率。45編碼方法編碼方法n 首先測定首先測定“0 0”游程長度和游程長度和

33、“1 1”游程長度的概率分布，游程長度的概率分布，即即以游程長度為元素，構造一個新的信源以游程長度為元素，構造一個新的信源；n 對新的信源（游程序列）進行哈夫曼編碼。對新的信源（游程序列）進行哈夫曼編碼。 多元序列也可以變換成游程序列，如多元序列也可以變換成游程序列，如r r元序列可元序列可有有r r種游程。但是變換成游程序列時，需要增加標志位種游程。但是變換成游程序列時，需要增加標志位才能區(qū)分游程序列中的才能區(qū)分游程序列中的“長度長度”是是r r種游程中的哪一個種游程中的哪一個的長度，否則，變換就不可逆。這樣，增加的標志位的長度，否則，變換就不可逆。這樣，增加的標志位可能會抵消壓縮編碼得到的

34、好處。所以，可能會抵消壓縮編碼得到的好處。所以，對多元序列對多元序列進行游程變換的意義不大進行游程變換的意義不大。46 二元獨立序列游程長度的熵二元獨立序列游程長度的熵o若二元序列的概率特性已知，由于二元序列與游程若二元序列的概率特性已知，由于二元序列與游程變換序列的一一對應性，可計算出游程序列的概率變換序列的一一對應性，可計算出游程序列的概率特性。特性。o令令“0 0”和和“1 1”的概率分別為的概率分別為p p0 0和和p p1 1，則，則“0 0”游程長度游程長度L L(0)(0)的概率為的概率為 p p L L(0)=(0)=p p0 0L L(0)(0)1 1p p1 1 式中式中L

35、 L(0)=1,2,(0)=1,2, ,o在計算在計算p p L L(0)(0)時必然已有時必然已有“0 0”出現(xiàn)，否則就不是出現(xiàn)，否則就不是“0 0”游程，若下一個符號是游程，若下一個符號是“1 1”，則游程長度為，則游程長度為1 1，其概率是其概率是p p1 1 =1 =1p p0 0；若下一個符號為；若下一個符號為“0 0”、再下一、再下一個符號為個符號為“1 1”，則游程長度為，則游程長度為2 2，其概率將為，其概率將為p p0 0p p1 1 ；依此類推。依此類推。47o游程長度至少是游程長度至少是1 1，理論上，游程長度可以是無窮，理論上，游程長度可以是無窮，但很長的游程實際出現(xiàn)的

36、概率非常小。但很長的游程實際出現(xiàn)的概率非常小。o同理可得同理可得“1 1”游程長度游程長度L L(1)(1)的概率為的概率為P P L L(1)=(1)=p p1 1L L(1)-1(1)-1p p0 0(0) 1(0) 10110(0) 1(0) 1(0) 12110001234 (0)(1)11(1)1LLLLLp Lpppppppppxxxxx 11)1 (101) 1 (ppLpL48121)0(001)0(0201121)0(021)0(011)0(1211)0(01)0(1)0(0211)0(01)0(11)0(0211)0(01)0(2log)log(loglog 1)0(log

37、loglog)0(log)0()0(ppdpdpppppLppppppppppppLpLpLHLLLLLLLLLLLLL2(0) 1(0) 1(0) 101201(0) 1(0) 1(0) 1(0) 101200121(0) 1(0) 1(0) 1(0) 1110100(0) 1(0) 1 (0) (0)log (0)log log logloglog (0) 1LLLLLLLLLLLLLH Lp Lp LpppppppppppppppLp 根011102000010111 (0)loglog11()logpH LpppppppH ppppp 據(jù)無窮等比級數(shù)和的公式得：o“0”游程長度的熵游程

38、長度的熵49 二元獨立序列的平均游程長度二元獨立序列的平均游程長度o“0 0”游程序列的平均游程長度游程序列的平均游程長度o同理可得同理可得“1 1”游程長度的熵和平均游程長度游程長度的熵和平均游程長度(0) 1001(0) 1(0) 112011234 (0)(0) (0)(0)11(1)(1)1LLLlE LLp LLpppppxxxxx 01001)1 ()()1 (pLElppHLH50 二元獨立序列的熵二元獨立序列的熵o“0 0”游程序列的熵與游程序列的熵與“1 1”游程長度的熵之和除以游程長度的熵之和除以它們的平均游程長度之和，即為對應原二元序列它們的平均游程長度之和，即為對應原二

39、元序列的熵的熵H H( (X X) )o游程變換后符號熵沒有變。因為游程變換是一一游程變換后符號熵沒有變。因為游程變換是一一對應的可逆變換，所以變換后熵值不變，這也說對應的可逆變換，所以變換后熵值不變，這也說明變換后的游程序列是獨立序列。明變換后的游程序列是獨立序列。0101 (0) (1)()()()(8.30)H LH LH XH pH pll51o對于有相關性的二元序列，也可以證明變換后的游對于有相關性的二元序列，也可以證明變換后的游程序列是獨立序列，并且也有程序列是獨立序列，并且也有 的結論，只是此時的結論，只是此時H H L L(0)(0)，H H L L(1)(1)，l l0 0和

40、和l l1 1的具體的具體表達形式不同，它們是相關符號的聯(lián)合概率和條件表達形式不同，它們是相關符號的聯(lián)合概率和條件概率的函數(shù)。概率的函數(shù)。01 (0) (1)()H LH LH Xll52五. 長碼的截斷處理方法o理論上，游程長度可從理論上，游程長度可從1 1到無窮，要建立游程長度和到無窮，要建立游程長度和碼字之間的一一對應的碼表是困難的。碼字之間的一一對應的碼表是困難的。o一般情況下，游程越長，出現(xiàn)的概率越?。划斢纬涕L一般情況下，游程越長，出現(xiàn)的概率越?。划斢纬涕L度趨向于無窮時，出現(xiàn)的概率也趨于度趨向于無窮時，出現(xiàn)的概率也趨于0 0。o按照哈夫曼編碼規(guī)則，概率越小，碼字越長。但小概按照哈夫曼

41、編碼規(guī)則，概率越小，碼字越長。但小概率的碼字對平均碼長影響較小。所以在實際應用時，率的碼字對平均碼長影響較小。所以在實際應用時，常對長碼采用截斷處理的方法。常對長碼采用截斷處理的方法。8.5.1 算術編碼特點及應用8.5.2 信源符號序列的累積分布函數(shù)F(s)及對應的區(qū)間8.5.3 信源序列累積分布函數(shù)的遞推公式8.5.4 算術編碼方法8.5.5 算術編碼的譯碼538.5 8.5 算術編碼算術編碼o 算術編碼不同于哈夫曼碼，它是非分組（非塊）碼。它從全序列出發(fā)，考慮符號之間的關系來進行編碼。o 算術編碼利用了累積概率的概念。o 算術碼主要的編碼方法是計算輸入信源符號序列所對應的區(qū)間。o 因為在

42、編碼過程中，每輸入一個符號要進行乘法和加法運算，所以稱此編碼方法為算術編碼。o 二元序列的算術編碼可用于黑白圖像的編碼，例如傳真。548.5.1 8.5.1 算術編碼的碼特點及應用算術編碼的碼特點及應用o 設信源符號集A=a1,a2,an，其相應概率分布為P(ai)，P(ai) 0(i=1,2, ,n)o 信源符號的累積分布函數(shù)為 所得累積分布函數(shù)為每臺級的下界值，則其區(qū)間為0,1)左閉右開區(qū)間。 F(a1)=0 F(a2)=P(a1) F(a3)=P(a1)+P(a2) o 當A=0,1二元信源二元信源時： F(0)=0 F(1)=P(0),()()(11AaaaPaFkikiik558.5

43、.2 信源符號序列的累積分布函數(shù)信源符號序列的累積分布函數(shù)F(s s)及對應的區(qū)間及對應的區(qū)間o 計算二元無記憶信源序列二元無記憶信源序列的累積分布函數(shù)n 初始時：在0,1)區(qū)間內(nèi)由F(1)劃分成二個子區(qū)間0,F(1)和F(1),1)， F(1)= P(0)。o 子區(qū)間0,F(1)的寬度為A(0)= P(0)，對應于信源符號“0”；o 子區(qū)間F(1),1)的寬度為A(1)= P(1)，對應于信源符號“1”；o 若輸入符號序列的第一個符號為s=“0”，落入0,F(1)區(qū)間，得 累積分布函數(shù)F(s=“0”)= F(0)=0； 56n 輸入第二個符號為“1”，s=“01”os=“01”所對應的區(qū)間是

44、在區(qū)間0,F(1)中進行分割；o 符號序列“00”對應的區(qū)間寬度為A(00)=A(0)P(0)=P(0)P(0)=P(00)；o 對應的區(qū)間為0,F(s=“01”)。o 符號序列“01”對應的區(qū)間寬度為A(01)=A(0)P(1)=P(0)P(1)=P(01)= A(0)A(00)；o 對應的區(qū)間為F(s=“01”),F(1)。o 累積分布函數(shù)F(s=“01”)=P(00)= P(0)P(0)57n輸入第三個符號為“1”：o 輸入序列可記做s1=“011”（若第三個符號輸入為“0”，可記做s0=“010”）；o 現(xiàn)在，輸入序列s1=“011”對應的區(qū)間是對區(qū)間F(s),F(1)進行分割；o 序

45、列s0=“010”對應的區(qū)間寬度為 A(s=“010”)=A(s=“01”)P(0)=A(s)P(0) 其對應的區(qū)間為F(s), F(s)+ A(s)P(0)；o 序列s1=“011”對應的區(qū)間寬度為 A(s=“011”)=A(s)P(1)=A(s=“01”)A(s=“010”)= A(s )A(s0) 其對應的區(qū)間為F(s)+A(s)P(0),F(1)；o 符號序列s1=“011”的累積分布函數(shù)為F(s1)=F(s)+A(s)P(0)；o 若第三個符號輸入為“0”，符號序列s0=“010”的區(qū)間下界值仍為F(s)，得符號序列s0=“010”的累積分布函數(shù)為F(s0)=F(s)。58n 歸納o

46、 當已知前面輸入符號序列為s，若接著再輸入一個符號“0”，序列s0的累積分布函數(shù)為： F(s0)=F(s)o 對應區(qū)間寬度為： A(s0)=A(s)P(0)o 若接著輸入的一個符號是“1”，序列的累積分布函數(shù)為：F(s1)=F(s)+A(s)P(0)o 對應區(qū)間寬度為： A(s1)=A(s)P(1)=A(s)A(s0)59n 符號序列對應的區(qū)間寬度A(s=“0”)=P(0)A(s=“1”)=1A(s=“0”)=P(1)A(s=“00”)=P(00)=A(0)P(0)=P(0)P(0)A(s=“01”)=A(s=“0”)A(s=“00”)=P(01)=A(0)P(1)=P(0)P(1)A(s=“

47、10”)=P(10)=A(1)P(0)=P(1)P(0)A(s=“11”)=A(s=“1”)A(s=“10”)=P(11)= A(s=“1”)P(1)=P(1)P(1)A(s=“010”)=A(s=“01”)P(0)=P(01)P(0)P(010)A(s=“011”)=A(s=“01”)A(s=“010”)=A(s=“01”)P(1)=P(01)P(1)=P(011) 信源符號序列信源符號序列s s所對應區(qū)間的寬度所對應區(qū)間的寬度A(s)等于符號序列等于符號序列s s的概率的概率P(s s)。60o 二元信源符號序列的累積分布函數(shù)的遞推公式nF(sr)=F(s)+P(s)F(r) (r=0,1

48、) (8.51)sr表示已知前面信源符號序列為s，接著再輸入符號為rF(0)=0， F(1)=P(0)F(s0)=F(s)F(s1)=F(s)+P(s)F(1)= F(s)+P(s)P(0)nA(sr)=P(sr)=P(s)P(r) (r=0,1) (8.52) A(s0)=P(s0)=P(s)P(0) A(s1)=P(s1)=P(s)P(1)618.58.5.3 信源序列累積分布函數(shù)的遞推公式o 舉例：已輸入二元符號序列為s=“011”，接著再輸入符號為“1”，得序列累積分布函數(shù)為： F(s1)=F(0111)=F(s=“011”)+P(011)P(0) =F(s=“01”)+P(01)P(

49、0)+P(011)P(0) =F(s=“0”)+P(0)P(0) +P(01)P(0)+P(011)P(0) =0+P(00)+P(010)+P(0110) 對應的區(qū)間寬度為 A(s1)=P(s=“011”)P(1)=P(011)P(1)=P(0111)62o 上述整個分析過程可用圖8.9描述o 式(8.51)和(8.52)是可遞推運算，在實際中，只需兩個存儲器，把P(s)和F(s)存下來，然后，根據(jù)輸入符號和式(8.51)、(8.52)更新兩個存儲器中的數(shù)值。因此在編碼過程中，每輸入一個符號要進行乘法和加法運算，所以稱為算算術編碼術編碼。63) 1 ()() 1() 1()0()()0()0

50、()0()()() 1()()0(PPPAPPPAPPFFFFsssssssssss64 通過關于信源符號序列的累積分布函數(shù)的計算，把區(qū)間分割成許多小區(qū)間，不同的信源符號序列對應不同的區(qū)間為F(s),F(s)+P(s) ?？扇⌒^(qū)間內(nèi)的一點來代表這序列。o 編碼方法：將符號序列的累積分布函數(shù)寫成二進位的小數(shù)，取小數(shù)點后k位，若后面有尾數(shù)，就進位到第k位，這樣得到的一個數(shù)C，并使k滿足o 舉例 。的碼字為得符號序列設整數(shù)代表大于或等于的最小kkkzzzzzzzCPk21212s,1 , 0. 0) s (1log658.58.5.4 算術編碼方法。的碼字為，得則110s110. 0371) s

51、(10110001. 0) s (CkPFo 編碼效率n 這樣選取的數(shù)值C，一般根據(jù)二進位小數(shù)截去尾數(shù)的影響，得 CF(s)Cn 而P(s)1/2kn 信源符號序列對應區(qū)間的上界為 F(s)+P(s)F(s)+1/2kCn 可見，數(shù)值在區(qū)間F(s),F(s)+P(s)內(nèi)。而信源符號序列對應的不同區(qū)間（左封右開）是不重疊的，所以編得的碼是即時碼。66o 算術編碼的編碼效率很高。當信源符號序列很長時，L很大時，平均碼長接近信源的熵。mLKRLSHRLKSH2log1)()(67)()(1)()(1)(log)()()()(log)()(1log222SLHSHLLSHLKLSHpPkPKPPPkL

52、LL若信源是無記憶，平均每個符號的碼長為得由于ssssssssss例：設二元無記憶信源S=0,1，其P(0)=1/4，P(1)=3/4。對二元序列11111100做算術編碼。解：P(s=11111100)=P2(0)P6(1)=(3/4)6(1/4)2F(sr)=F(s)+P(s)F(r)F(s0)=F(s) F(s1)=F(s)+P(s)F(1)= F(s)+P(s)P(0)F(s)=P(0)+P(1)P(0)+P(1)2P(0)+P(1)3P(0)+P(1)4P(0)+P(1)5P(0) =0.82202=0.110100100111得C0.1101010 得s的碼字為1101010。編碼

53、效率 7)(1log2sPk68舉 例%928/7811. 0/)()(LKsHRsH) 1 () s () 1s () 1s ()0() s ()0s ()0s ()0() s () s () 1s () s ()0s (PPPAPPPAPPFFFF69舉 例70一一. . 冗余編碼特點及應用冗余編碼特點及應用二二. . 冗余編碼方法冗余編碼方法三三. . L LD D編碼方法編碼方法四四. . L LD D譯碼方法譯碼方法五五. . 舉例舉例第六節(jié)第六節(jié) 冗余編碼冗余編碼71o 冗余位冗余位：在信源序列中，常有許多符號不攜帶信息，：在信源序列中，常有許多符號不攜帶信息，除了符號的數(shù)目或所占時長外，完全可以不傳送。這除了符號的數(shù)目或所占時長外，完全可以不傳送。這些符號稱為冗余位。些符號稱為冗余位。如語音通信中講話的間歇；圖像如語音通信中講話的間歇；圖像通信中，圖像的背景基本不變，并在圖像中占相當大通信中