信息論第四章

1、信息論第四章第1頁，共78頁，2022年，5月20日，1點23分，星期一信源編碼：以提高通信有效性為目的的編碼。通常通過壓縮信源的冗余度來實現(xiàn)。采用的一般方法是壓縮每個信源符號的平均比特數(shù)或信源的碼率。即同樣多的信息用較少的碼率傳送，使單位時間內傳送的平均信息量增加，從而提高通信的有效性。信道編碼：是以提高信息傳輸?shù)目煽啃詾槟康牡木幋a。通常通過增加信源的冗余度來實現(xiàn)。采用的一般方法是增大碼率/帶寬。與信源編碼正好相反。密碼：是以提高通信系統(tǒng)的安全性為目的的編碼。通常通過加密和解密來實現(xiàn)。從信息論的觀點出發(fā)，“加密”可視為增熵的過程，“解密”可視為減熵的過程。第一節(jié) 引言第2頁，共78頁，202

2、2年，5月20日，1點23分，星期一信源編碼理論是信息論的一個重要分支，其理論基礎是信源編碼的兩個定理。無失真信源編碼定理：是離散信源/數(shù)字信號編碼的基礎；限失真信源編碼定理：是連續(xù)信源/模擬信號編碼的基礎。信源編碼的分類：離散信源編碼、連續(xù)信源編碼和相關信源編碼三類。離散信源編碼：獨立信源編碼，可做到無失真編碼；連續(xù)信源編碼：獨立信源編碼，只能做到限失真信源編碼；相關信源編碼：非獨立信源編碼。第一節(jié) 引言第3頁，共78頁，2022年，5月20日，1點23分，星期一第二節(jié) 碼的分類 編碼器可以看作這樣一個系統(tǒng)，它的輸入端為原始信源S，其符號集為 ；而信道所能傳輸?shù)姆柤癁?編碼器的功能是用符號

3、集X中的元素，將原始信源的符號 變換為相應的碼字符號 ，所以編碼器輸出端的符號集為 稱為碼字， 為碼字 的碼元個數(shù)，稱為碼字 的碼字長度，簡稱碼長。 編碼器第4頁，共78頁，2022年，5月20日，1點23分，星期一1、二元碼： 碼符號集X=0,1，如果要將信源通過二元信道傳輸，必須將信源編成二元碼，這也是最常用的一種碼。2、等長碼： 若一組碼中所有碼字的長度都相同，稱為等長碼。3、變長碼： 若一組碼中所有碼字的長度各不相同，稱為變長碼。4、非奇異碼： 若一組碼中所有碼字都不相同，稱為非奇異碼。第二節(jié) 碼的分類第5頁，共78頁，2022年，5月20日，1點23分，星期一5、奇異碼： 若一組碼中

4、有相同的碼字，稱為奇異碼。6、碼的N次擴展： 若碼 ， 碼 則稱碼B為碼C的N次擴展碼。7、唯一可譯碼： 若碼的任意一串有限長的碼符號序列只能被唯一的譯成所對應的信源符號序列，則稱此碼為唯一可譯碼。 第二節(jié) 碼的分類第6頁，共78頁，2022年，5月20日，1點23分，星期一例：如果有四個信源符號s1，s2，s3，s4，采用二元編碼，l=2，則可以編成s1=00，s2=01，s3=10，s4=11。第三節(jié) 等長信源編碼定理如果我們要對信源的N次擴展信源進行編碼，也必須滿足 ， 兩邊取對數(shù)得：表示平均每個信源符號所需的碼符號個數(shù)。若對信源進行等長編碼，則必須滿足其中，l是碼長，r是碼符號集中的碼

5、元數(shù)，q信源符號個數(shù)。第7頁，共78頁，2022年，5月20日，1點23分，星期一第二節(jié) 等長碼例：對英文電報得32個符號進行二元編碼，根據(jù)上述關系： 我們繼續(xù)討論上面得例子，我們已經(jīng)知道英文的極限熵是1.4bit,遠小于5bit，也就是說，5個二元碼符號只攜帶1.4bit的信息量，實際上，5個二元符號最多可以攜帶5bit信息量。我們可以做到讓平均碼長縮短，提高信息傳輸率第8頁，共78頁，2022年，5月20日，1點23分，星期一第二節(jié) 等長碼 我們舉例說明： 設信源而其依賴關系為：第9頁，共78頁，2022年，5月20日，1點23分，星期一第二節(jié) 等長碼若不考慮符號間的依賴關系，可得碼長l2

6、若考慮符號間的依賴關系，則對此信源作二次擴展 可見，由于符號間依賴關系的存在，擴展后許多符號出現(xiàn)的概率為0，此信源只有4個字符，可得碼長 ，但平均每個信源符號所需碼符號為第10頁，共78頁，2022年，5月20日，1點23分，星期一第二節(jié) 等長碼 我們仍以英文電報為例，在考慮了英文字母間的相關性之后，我們對信源作N次擴展，在擴展后形成的信源（也就是句子）中，有些句子是有意義的，而有些句子是沒有意義的，我們可以只對有意義的句子編碼，而對那些沒有意義的句子不進行編碼，這樣就可以縮短每個信源符號所需的碼長。 等長信源編碼定理給出了進行等長信源編碼所需碼長的極限值。第11頁，共78頁，2022年，5月

7、20日，1點23分，星期一定理4.3（等長信源編碼定理） 一個熵為H(S)的離散無記憶信源，若對其N次擴展信源進行等長r元編碼，碼長為l，對于任意 大于0，只要滿足當N無窮大時，則可以實現(xiàn)幾乎無失真編碼，反之，若：則不可能實現(xiàn)無失真編碼，當N趨向于無窮大是，譯碼錯誤率接近于1。第三節(jié) 等長信源編碼定理第12頁，共78頁，2022年，5月20日，1點23分，星期一定理4.3的條件式可寫成：左邊表示長為 的碼符號所能載荷的最大信息量，而右邊代表長為N的序列平均攜帶的信息量。因此，只要碼字傳輸?shù)男畔⒘看笥谛旁葱蛄袛y帶的信息量，總可以實現(xiàn)無失真編碼 。 第三節(jié) 等長信源編碼定理定理4.3的條件式也可寫

8、成：令： 稱之為編碼信息率。可見，編碼信息率大于信源的熵，才能實現(xiàn)無失真編碼。第13頁，共78頁，2022年，5月20日，1點23分，星期一最佳編碼效率為：第三節(jié) 等長信源編碼定理為了衡量編碼效果，引進稱為編碼效率。第14頁，共78頁，2022年，5月20日，1點23分，星期一例：設離散無記憶信源：若采用等長二元編碼，要求編碼效率 ，允許錯誤率，則：也就是長度要達到4130萬以上。第三節(jié) 等長信源編碼定理第15頁，共78頁，2022年，5月20日，1點23分，星期一1、唯一可譯變長碼與及時碼信源符號出現(xiàn)概率碼1碼2碼3碼4s1s2s3s41/21/41/81/80110011010000111

9、010010001010010001第四節(jié) 變長信源編碼定理第16頁，共78頁，2022年，5月20日，1點23分，星期一第五節(jié) 變長碼 碼1是一個奇異碼，不是唯一可譯碼；碼2也不是唯一可譯碼，因為收到一串序列是，無法唯一譯出對應的原符號序列，如0100，即可譯作s4s3s1,也可譯作s4s1s3,s1s2s3或s1s2s1s1；碼3和碼4都是唯一可譯的。 但碼3和碼4也不太一樣，碼4稱作逗點碼，只要收到1，就可以立即作出譯碼；而碼3不同，當受到一個或幾個碼是，必須參考后面的碼才能作出判斷。 定義，在唯一可譯碼中，有一類碼，它在譯碼是無須參考后面的碼字就可以作出判斷，這種碼稱為即時碼。第17頁

10、，共78頁，2022年，5月20日，1點23分，星期一定義：如果一個碼組中的任一個碼字都不是另一個碼字的續(xù)長，或者說，任何一個碼字后加上若干碼元后都不是碼組中另一個碼字，則稱為即時碼。 所有的碼非奇異碼唯一可譯碼即時碼第四節(jié) 變長信源編碼定理第18頁，共78頁，2022年，5月20日，1點23分，星期一2、即時碼的樹圖構造法我們可以用樹圖的形式構造即時碼，如01001111010010001碼4的樹圖10110000101001000碼3的樹圖第四節(jié) 變長信源編碼定理樹根碼字的起點樹枝數(shù)碼的數(shù)節(jié)點數(shù)碼字的一部分節(jié)數(shù)碼長端點碼字滿樹等長碼非滿樹變長碼第19頁，共78頁，2022年，5月20日，1

11、點23分，星期一 在每個節(jié)點上都有r個分枝的樹稱為整樹，否則稱為非整樹。 即時碼的樹圖還可以用來譯碼第四節(jié) 變長信源編碼定理第20頁，共78頁，2022年，5月20日，1點23分，星期一3、克拉夫特（Kraft）不等式定理4.4 對于碼符號為 的任意即時碼，所對應的碼長為 ，則必定滿足： 反之，若碼長滿足上式，則一定存在這樣的即時碼 。 可以根據(jù)即時碼的樹圖構造法來證明。 后來，B.McMillan證明了對于唯一可譯碼也必須滿足上面的不等式，第四節(jié) 變長信源編碼定理第21頁，共78頁，2022年，5月20日，1點23分，星期一定理4.6 若存在一個碼長為 唯一可譯碼，則一定存在一個同樣長度的即

12、時碼。 這說明，其他唯一可譯碼在碼長方面并不比即時碼占優(yōu)。所以在討論唯一可譯碼時，只需要討論即時碼就可以了。第四節(jié) 變長信源編碼定理第22頁，共78頁，2022年，5月20日，1點23分，星期一設信源編碼后的碼字為：碼長為：則這個碼的平均長度為：平均每個碼元攜帶的信息量即編碼后的信息傳輸率為：若有一個唯一可譯碼，它的平均碼長小于其他唯一可譯碼的長度，則稱此碼為緊致碼或最佳碼，無失真信源編碼的基本問題就是尋找緊致碼。第四節(jié) 變長信源編碼定理第23頁，共78頁，2022年，5月20日，1點23分，星期一定理4.8 無失真變長信源編碼定理（香農(nóng)第一定理）離散無記憶信源S的N次擴展信源 ，其熵為 ，并

13、且編碼器的碼元符號集為A： 對信源 進行編碼，總可以找到一種編碼方法，構成單義可譯碼，使信源S中每個符號si所需要的平均碼長滿足 當 則得：第四節(jié) 變長信源編碼定理第24頁，共78頁，2022年，5月20日，1點23分，星期一 這個定理是香農(nóng)信息論中非常重要得一個定理，它指出，要做到無失真得信源編碼，信源每個符號所需要的平均碼元數(shù)就是信源的熵值，如果小于這個值，則唯一可譯碼不存在，可見，熵是無失真信源編碼的極限值。定理還指出，通過對擴展信源進行編碼，當N趨向于無窮時，平均碼長可以趨進該極限值。 還可以證明，如果我們不確切知道信源的概率分布，我們用估計的概率分布去進行編碼時，平均碼長會加長，但是

14、如果估計的偏差不大的話，平均碼長也不會增加太多（定理4.9的內容）。 第四節(jié) 變長信源編碼定理第25頁，共78頁，2022年，5月20日，1點23分，星期一由得：就是編碼后每個信源符號所攜帶的平均信息量第一定理可以表述如下：若 就存在唯一可譯變長碼，若 則不存在唯一可譯變長碼。第四節(jié) 變長信源編碼定理定義：若從信道角度講，信道的信息傳輸率因為：所以當平均碼長達到極限值時，編碼后信道的信息傳輸率為：第26頁，共78頁，2022年，5月20日，1點23分，星期一無噪信道編碼定理 若信道的信息傳輸率R不大于信道容量C，總能對信源的輸出進行適當?shù)木幋a，使的在無噪無損信道上能無差錯的以最大信息傳輸率C傳

15、輸信息，若R小于C，則無差錯傳輸是不可能的。第四節(jié) 變長信源編碼定理 編碼效率：碼的剩余度：在二元無噪無損信道中：在二元無噪無損信道中信息傳輸率：第27頁，共78頁，2022年，5月20日，1點23分，星期一例：其熵為：H(S)=0.811我們令s1=0，s2=1，這時平均碼長 ，編碼的效率為 。第四節(jié) 變長信源編碼定理二次擴展信源進行編碼：即時碼s1s19/160s1s23/1610s2s13/16110s2s21/16111第28頁，共78頁，2022年，5月20日，1點23分，星期一第五節(jié) 香農(nóng)編碼設離散無記憶信源二進制香農(nóng)碼的編碼步驟如下：將信源符號按概率從大到小的順序排列，為方便起見

16、，令 p(x1) p(x2) p(xn)令p(x0)=0，用pa(xj)，j=i+1表示第i個碼字的累加概率，則：確定滿足下列不等式的整數(shù)ki ，并令ki為第i個碼字的長度log2 p(xn)ki log2 p(xn)+1將pa(xj) 用二進制表示，并取小數(shù)點后ki 位作為符號xi的編碼。第29頁，共78頁，2022年，5月20日，1點23分，星期一第五節(jié) 香農(nóng)編碼例 有一單符號離散無記憶信源對該信源編二進制香農(nóng)碼。其編碼過程如下表所示。第30頁，共78頁，2022年，5月20日，1點23分，星期一第五節(jié) 香農(nóng)編碼計算出給定信源香農(nóng)碼的平均碼長若對上述信源采用等長編碼，要做到無失真譯碼，每個

17、符號至少要用3個比特表示。相比較，香農(nóng)編碼對信源進行了壓縮。由離散無記憶信源熵定義，可計算出：對上述信源采用香農(nóng)編碼的信息率為編碼效率為信源熵和信息率之比。則可以看出，編碼效率并不是很高。第31頁，共78頁，2022年，5月20日，1點23分，星期一第六節(jié) 費諾編碼費諾編碼也是一種常見的信源編碼方法。編碼步驟如下：將概率按從大到小的順序排列，令p(x1) p(x2) p(xn)按編碼進制數(shù)將概率分組，使每組概率盡可能接近或相等。如編二進制碼就分成兩組，編m進制碼就分成m組。給每一組分配一位碼元。將每一分組再按同樣原則劃分，重復步驟2和3，直至概率不再可分為止。第32頁，共78頁，2022年，5

18、月20日，1點23分，星期一第六節(jié) 費諾編碼例 設有一單符號離散信源對該信源編二進制費諾碼。編碼過程如下表。第33頁，共78頁，2022年，5月20日，1點23分，星期一第六節(jié) 費諾編碼該信源的熵為平均碼長為編碼效率為本例中費諾編碼有較高的編碼效率。費諾碼比較適合于每次分組概率都很接近的信源。特別是對每次分組概率都相等的信源進行編碼時，可達到理想的編碼效率。第34頁，共78頁，2022年，5月20日，1點23分，星期一第六節(jié) 費諾編碼題中碼字還可用碼樹來表示，如圖所示。第35頁，共78頁，2022年，5月20日，1點23分，星期一第七節(jié) 霍夫曼編碼 霍夫曼(Huffman)編碼是一種效率比較高

19、的變長無失真信源編碼方法。編碼步驟二進制哈夫曼編碼m進制哈夫曼編碼第36頁，共78頁，2022年，5月20日，1點23分，星期一第七節(jié) 霍夫曼編碼編碼步驟將信源符號按概率從大到小的順序排列，令p(x1) p(x2) p(xn)給兩個概率最小的信源符號p(xn-1)和p(xn)各分配一個碼位“0”和“1”，將這兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，結果得到一個只包含(n1)個信源符號的新信源。稱為信源的第一次縮減信源，用S1表示。將縮減信源S1的符號仍按概率從大到小順序排列，重復步驟2，得到只含(n2)個符號的縮減信源S2。重復上述步驟，直至縮減信源只剩兩個符號

20、為止，此時所剩兩個符號的概率之和必為1。然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應的碼字。第37頁，共78頁，2022年，5月20日，1點23分，星期一第七節(jié) 霍夫曼編碼二進制哈夫曼編碼例 設單符號離散無記憶信源如下，要求對信源編二進制 霍夫曼碼。編碼過程如下圖（后頁）。在圖中讀取碼字的時候，一定要從后向前讀，此時編出來的碼字才是可分離的異前置碼。若從前向后讀取碼字，則碼字不可分離。第38頁，共78頁，2022年，5月20日，1點23分，星期一第七節(jié) 霍夫曼編碼二進制哈夫曼編碼第39頁，共78頁，2022年，5月20日，1點23分，星期一第七節(jié) 霍夫曼編碼二進制哈夫

21、曼編碼將上圖左右顛倒過來重畫一下，即可得到二進制哈夫曼碼的碼樹。第40頁，共78頁，2022年，5月20日，1點23分，星期一信源熵為：平均碼長為編碼效率為若采用定長編碼，碼長K=3，則編碼效率可見哈夫曼的編碼效率提高了12.7%。第七節(jié) 霍夫曼編碼二進制哈夫曼編碼第41頁，共78頁，2022年，5月20日，1點23分，星期一第七節(jié) 霍夫曼編碼二進制哈夫曼編碼注意：哈夫曼的編法并不惟一。每次對縮減信源兩個概率最小的符號分配“0”和“1”碼元是任意的，所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性，即能得到可分離碼字。不同的碼元分配，得到的具體碼字不同，但碼長ki不變，平均碼長

22、也不變，所以沒有本質區(qū)別；縮減信源時，若合并后的新符號概率與其他符號概率相等，從編碼方法上來說，這幾個符號的次序可任意排列，編出的碼都是正確的，但得到的碼字不相同。不同的編法得到的碼字長度ki也不盡相同。第42頁，共78頁，2022年，5月20日，1點23分，星期一例：單符號離散無記憶信源 ，用兩種不同的方法對其編二進制哈夫曼碼。siliWi概率s1s2s3s4s512344101000001000110.40.20.20.10.1 0.4 0.2 0.2 0.2 0.4 0.4 0.2 0.6 0.4010101方法一：合并后的新符號排在其它相同概率符號的后面。第七節(jié) 霍夫曼編碼二進制哈夫曼

23、編碼第43頁，共78頁，2022年，5月20日，1點23分，星期一siliWi概率s1s2s3s4s512344101000001000110.40.20.20.10.1 0.4 0.2 0.2 0.2 0.4 0.4 0.2 0.6 0.4010101 這兩種編碼哪一種更好呢，我們來計算一下二者的碼長。方法二：合并后的新符號排在其它相同概率符號的前面。第七節(jié) 霍夫曼編碼二進制哈夫曼編碼第44頁，共78頁，2022年，5月20日，1點23分，星期一兩種編碼的平均碼長是一樣的，都是2.2，那一種更好呢，我們可以計算一下平均碼長的方差。定義碼字長度的方差2：第七節(jié) 霍夫曼編碼二進制哈夫曼編碼第45

24、頁，共78頁，2022年，5月20日，1點23分，星期一第七節(jié) 霍夫曼編碼二進制哈夫曼編碼可見：第二種編碼方法的碼長方差要小許多。意味著第二種編碼方法的碼長變化較小，比較接近于平均碼長。第一種方法編出的5個碼字有4種不同的碼長；第二種方法編出的碼長只有兩種不同的碼長；顯然，第二種編碼方法更簡單、更容易實現(xiàn)，所以更好。結論：在哈夫曼編碼過程中，對縮減信源符號按概率由大到小的順序重新排列時，應使合并后的新符號盡可能排在靠前的位置，這樣可使合并后的新符號重復編碼次數(shù)減少，使短碼得到充分利用。第46頁，共78頁，2022年，5月20日，1點23分，星期一第七節(jié) 霍夫曼編碼m進制哈夫曼編碼“全樹”概念定

25、義：碼樹圖中每個中間節(jié)點后續(xù)的枝數(shù)為m時稱為全樹；若有些節(jié)點的后續(xù)枝數(shù)不足m，就稱為非全樹。二進制碼不存在非全樹的情況，因為后續(xù)枝數(shù)是一時，這個枝就可以去掉使碼字長度縮短。對m進制編碼：若所有碼字構成全樹，可分離的碼字數(shù)（信源個數(shù)）必為 m+k(m1)。k為信源縮減次數(shù)。若信源所含的符號數(shù)n不能構成m進制全樹，必須增加s個不用的碼字形成全樹。顯然s0(i=1,2, ,n)信源符號的累積分布函數(shù)為： 所得累積分布函數(shù)為每臺級的下界值，則其區(qū)間為0,1)左閉右開區(qū)間。 F (a1)=0 F (a2)=P (a1) F (a3)=P (a1)+P (a2) 當A=0,1二元信源時： F (0)= 0

26、，F(xiàn) (1)=P (0)第62頁，共78頁，2022年，5月20日，1點23分，星期一第八節(jié) 游程編碼、算術編碼、冗余編碼算術編碼計算二元無記憶信源序列的累積分布函數(shù)初始時：在0,1)區(qū)間內由F (1)劃分成二個子區(qū)間0,F (1)和F (1),1)， F (1)= P (0)。子區(qū)間0,F (1)的寬度為A(0)= P (0)，對應于信源符號“0”；子區(qū)間F (1),1)的寬度為A(1)= P (1)，對應于信源符號“1”；若輸入符號序列的第一個符號為s=“0”，落入0,F (1)區(qū)間，得累積分布函數(shù)F (s=“0”)= F (0)=0； 第63頁，共78頁，2022年，5月20日，1點23

27、分，星期一第八節(jié) 游程編碼、算術編碼、冗余編碼算術編碼輸入第二個符號為“1”，s=“01”s=“01”所對應的區(qū)間是在區(qū)間0,F (1)中進行分割；符號序列“00”對應的區(qū)間寬度為: A(00)=A(0)P (0)=P (0)P (0)=P (00)；對應的區(qū)間為0,F (s=“01”)。符號序列“01”對應的區(qū)間寬度為 A(01)=A(0)P (1)=P (0)P (1)=P (01)= A(0)A(00)；對應的區(qū)間為F (s=“01”),F (1)。累積分布函數(shù)F (s=“01”)=P (00)= P (0)P (0)第64頁，共78頁，2022年，5月20日，1點23分，星期一第八節(jié)

28、游程編碼、算術編碼、冗余編碼算術編碼第65頁，共78頁，2022年，5月20日，1點23分，星期一第八節(jié) 游程編碼、算術編碼、冗余編碼算術編碼 輸入第三個符號為“1”：輸入序列可記做s1=“011”（若第三個符號輸入為“0”，可記做s0=“010”）；現(xiàn)在，輸入序列s1=“011”對應的區(qū)間是對區(qū)間F(s),F(1)進行分割；序列s0=“010”對應的區(qū)間寬度為 A(s=“010”)=A(s=“01”)P(0)=A(s)P(0) 其對應的區(qū)間為F(s), F(s)+ A(s)P(0)；序列s1=“011”對應的區(qū)間寬度為 A(s=“011”)=A(s)P(1)=A(s=“01”)A(s=“01

29、0”)= A(s )A(s0) 其對應的區(qū)間為F(s)+A(s)P(0),F(1)；符號序列s1=“011”的累積分布函數(shù)為F(s1)=F(s)+A(s)P(0)；若第三個符號輸入為“0”，符號序列s0=“010”的區(qū)間下界值仍為F(s)，得符號序列s0=“010”的累積分布函數(shù)為F(s0)=F(s)。第66頁，共78頁，2022年，5月20日，1點23分，星期一第八節(jié) 游程編碼、算術編碼、冗余編碼算術編碼歸納當已知前面輸入符號序列為s，若接著再輸入一個符號“0”，序列s0的累積分布函數(shù)為： F(s0)=F(s)對應區(qū)間寬度為： A(s0)=A(s)P(0)若接著輸入的一個符號是“1”，序列的

30、累積分布函數(shù)為：F(s1)=F(s)+A(s)P(0)對應區(qū)間寬度為： A(s1)=A(s)P(1)=A(s)A(s0)第67頁，共78頁，2022年，5月20日，1點23分，星期一第八節(jié) 游程編碼、算術編碼、冗余編碼算術編碼符號序列對應的區(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=“10”)=P(10)=A(1)P(0)=P(1)P(0)A(s=“11”)=A(s=“1”)A(s=“

31、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所對應區(qū)間的寬度等于符號序列s的概率P(s)。第68頁，共78頁，2022年，5月20日，1點23分，星期一第八節(jié) 游程編碼、算術編碼、冗余編碼算術編碼二元信源符號序列的累積分布函數(shù)的遞推公式F(sr)=F(s)+P(s)F(r) (r=0,1) sr表示已知前面信源符號序列為s，接著再輸入符號為rF(0)=0，

32、 F(1)=P(0)F(s0)=F(s)F(s1)=F(s)+P(s)F(1)= F(s)+P(s)P(0)A(sr)=P(sr)=P(s)P(r) (r=0,1) A(s0)=P(s0)=P(s)P(0) A(s1)=P(s1)=P(s)P(1)第69頁，共78頁，2022年，5月20日，1點23分，星期一第八節(jié) 游程編碼、算術編碼、冗余編碼算術編碼舉例：已輸入二元符號序列為s=“011”，接著再輸入符號為“1”，得序列累積分布函數(shù)為： F(s1)=F(0111)=F(s=“011”)+P(011)P(0) =F(s=“01”)+P(01)P(0)+P(011)P(0) =F(s=“0”)+

33、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)上述整個分析過程可用圖5.6.1描述式(5.6.1)和(5.6.2)是可遞推運算，在實際中，只需兩個存儲器，把P(s)和F(s)存下來，然后，根據(jù)輸入符號和式(5.6.1)、(5.6.2)更新兩個存儲器中的數(shù)值。因此在編碼過程中，每輸入一個符號要進行乘法和加法運算，所以稱為算術編碼。第70頁，共78頁，2022年，5月20日，1點23分，星期一第八節(jié) 游程編碼、算術編碼、冗余編碼算術編碼第71頁，共78頁，2022年，5月20日，1點23分，星期一第八節(jié) 游程編碼、算術編碼、冗余編碼算術編碼 通過關于信源符號序列的累積分布函數(shù)的計算，把區(qū)間分割成許多小區(qū)間，不同的信源符號序列對應不同的區(qū)間為F(s),F(s)+P(s) ?？扇⌒^(qū)間內的一點來代表這序列。編碼方法：將符號序列的累積分布函數(shù)寫成二進位的小數(shù)，取小數(shù)點后k位，若后面有尾數(shù)，就進位到第k位，這樣得到的一個數(shù)C，并使k滿足舉例第72頁，共78頁，2022年，5月20日，1點23分，星期一第八節(jié) 游程編碼、算術編碼、冗余編碼算術編碼編碼效率這樣選取的數(shù)值C，一般根據(jù)二進小數(shù)