信息論-無(wú)失真信源編碼

信息論_無(wú)失真信源編碼第一頁(yè)，共78頁(yè)。信源編碼：以提高通信有效性為目的的編碼。通常通過(guò)壓縮信源的冗余度來(lái)實(shí)現(xiàn)。采用的一般方法是壓縮每個(gè)信源符號(hào)的平均比特?cái)?shù)或信源的碼率。即同樣多的信息用較少的碼率傳送，使單位時(shí)間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。信道編碼：是以提高信息傳輸?shù)目煽啃詾槟康牡木幋a。通常通過(guò)增加信源的冗余度來(lái)實(shí)現(xiàn)。采用的一般方法是增大碼率/帶寬。與信源編碼正好相反。密碼：是以提高通信系統(tǒng)的安全性為目的的編碼。通常通過(guò)加密和解密來(lái)實(shí)現(xiàn)。從信息論的觀點(diǎn)出發(fā)，“加密”可視為增熵的過(guò)程，“解密”可視為減熵的過(guò)程。第一節(jié)引言第二頁(yè)，共78頁(yè)。信源編碼理論是信息論的一個(gè)重要分支，其理論基礎(chǔ)是信源編碼的兩個(gè)定理。無(wú)失真信源編碼定理：是離散信源/數(shù)字信號(hào)編碼的基礎(chǔ)；限失真信源編碼定理：是連續(xù)信源/模擬信號(hào)編碼的基礎(chǔ)。信源編碼的分類：離散信源編碼、連續(xù)信源編碼和相關(guān)信源編碼三類。離散信源編碼：獨(dú)立信源編碼，可做到無(wú)失真編碼；連續(xù)信源編碼：獨(dú)立信源編碼，只能做到限失真信源編碼；相關(guān)信源編碼：非獨(dú)立信源編碼。第一節(jié)引言第三頁(yè)，共78頁(yè)。第二節(jié)碼的分類編碼器可以看作這樣一個(gè)系統(tǒng)，它的輸入端為原始信源S，其符號(hào)集為；而信道所能傳輸?shù)姆?hào)集為編碼器的功能是用符號(hào)集X中的元素，將原始信源的符號(hào)變換為相應(yīng)的碼字符號(hào)，所以編碼器輸出端的符號(hào)集為

稱為碼字，為碼字的碼元個(gè)數(shù)，稱為碼字的碼字長(zhǎng)度，簡(jiǎn)稱碼長(zhǎng)。編碼器第四頁(yè)，共78頁(yè)。1、二元碼：碼符號(hào)集X={0,1}，如果要將信源通過(guò)二元信道傳輸，必須將信源編成二元碼，這也是最常用的一種碼。2、等長(zhǎng)碼：若一組碼中所有碼字的長(zhǎng)度都相同，稱為等長(zhǎng)碼。3、變長(zhǎng)碼：若一組碼中所有碼字的長(zhǎng)度各不相同，稱為變長(zhǎng)碼。4、非奇異碼：若一組碼中所有碼字都不相同，稱為非奇異碼。第二節(jié)碼的分類第五頁(yè)，共78頁(yè)。5、奇異碼：若一組碼中有相同的碼字，稱為奇異碼。6、碼的N次擴(kuò)展：若碼，碼則稱碼B為碼C的N次擴(kuò)展碼。7、唯一可譯碼：若碼的任意一串有限長(zhǎng)的碼符號(hào)序列只能被唯一的譯成所對(duì)應(yīng)的信源符號(hào)序列，則稱此碼為唯一可譯碼。第二節(jié)碼的分類第六頁(yè)，共78頁(yè)。例：如果有四個(gè)信源符號(hào){s1，s2，s3，s4}，采用二元編碼，l=2，則可以編成s1=00，s2=01，s3=10，s4=11。第三節(jié)等長(zhǎng)信源編碼定理如果我們要對(duì)信源的N次擴(kuò)展信源進(jìn)行編碼，也必須滿足，兩邊取對(duì)數(shù)得：表示平均每個(gè)信源符號(hào)所需的碼符號(hào)個(gè)數(shù)。若對(duì)信源進(jìn)行等長(zhǎng)編碼，則必須滿足其中，l是碼長(zhǎng)，r是碼符號(hào)集中的碼元數(shù)，q信源符號(hào)個(gè)數(shù)。第七頁(yè)，共78頁(yè)。第二節(jié)等長(zhǎng)碼例：對(duì)英文電報(bào)得32個(gè)符號(hào)進(jìn)行二元編碼，根據(jù)上述關(guān)系：我們繼續(xù)討論上面得例子，我們已經(jīng)知道英文的極限熵是1.4bit,遠(yuǎn)小于5bit，也就是說(shuō)，5個(gè)二元碼符號(hào)只攜帶1.4bit的信息量，實(shí)際上，5個(gè)二元符號(hào)最多可以攜帶5bit信息量。我們可以做到讓平均碼長(zhǎng)縮短，提高信息傳輸率第八頁(yè)，共78頁(yè)。第二節(jié)等長(zhǎng)碼我們舉例說(shuō)明：

設(shè)信源而其依賴關(guān)系為：第九頁(yè)，共78頁(yè)。第二節(jié)等長(zhǎng)碼若不考慮符號(hào)間的依賴關(guān)系，可得碼長(zhǎng)l＝2若考慮符號(hào)間的依賴關(guān)系，則對(duì)此信源作二次擴(kuò)展可見(jiàn)，由于符號(hào)間依賴關(guān)系的存在，擴(kuò)展后許多符號(hào)出現(xiàn)的概率為0，此信源只有4個(gè)字符，可得碼長(zhǎng)，但平均每個(gè)信源符號(hào)所需碼符號(hào)為第十頁(yè)，共78頁(yè)。第二節(jié)等長(zhǎng)碼我們?nèi)砸杂⑽碾妶?bào)為例，在考慮了英文字母間的相關(guān)性之后，我們對(duì)信源作N次擴(kuò)展，在擴(kuò)展后形成的信源（也就是句子）中，有些句子是有意義的，而有些句子是沒(méi)有意義的，我們可以只對(duì)有意義的句子編碼，而對(duì)那些沒(méi)有意義的句子不進(jìn)行編碼，這樣就可以縮短每個(gè)信源符號(hào)所需的碼長(zhǎng)。等長(zhǎng)信源編碼定理給出了進(jìn)行等長(zhǎng)信源編碼所需碼長(zhǎng)的極限值。第十一頁(yè)，共78頁(yè)。定理4.3（等長(zhǎng)信源編碼定理）一個(gè)熵為H(S)的離散無(wú)記憶信源，若對(duì)其N次擴(kuò)展信源進(jìn)行等長(zhǎng)r元編碼，碼長(zhǎng)為l，對(duì)于任意大于0，只要滿足當(dāng)N無(wú)窮大時(shí)，則可以實(shí)現(xiàn)幾乎無(wú)失真編碼，反之，若：則不可能實(shí)現(xiàn)無(wú)失真編碼，當(dāng)N趨向于無(wú)窮大是，譯碼錯(cuò)誤率接近于1。第三節(jié)等長(zhǎng)信源編碼定理第十二頁(yè)，共78頁(yè)。定理4.3的條件式可寫成：左邊表示長(zhǎng)為的碼符號(hào)所能載荷的最大信息量，而右邊代表長(zhǎng)為N的序列平均攜帶的信息量。因此，只要碼字傳輸?shù)男畔⒘看笥谛旁葱蛄袛y帶的信息量，總可以實(shí)現(xiàn)無(wú)失真編碼。第三節(jié)等長(zhǎng)信源編碼定理定理4.3的條件式也可寫成：令：稱之為編碼信息率?？梢?jiàn)，編碼信息率大于信源的熵，才能實(shí)現(xiàn)無(wú)失真編碼。第十三頁(yè)，共78頁(yè)。最佳編碼效率為：第三節(jié)等長(zhǎng)信源編碼定理為了衡量編碼效果，引進(jìn)稱為編碼效率。第十四頁(yè)，共78頁(yè)。例：設(shè)離散無(wú)記憶信源：若采用等長(zhǎng)二元編碼，要求編碼效率，允許錯(cuò)誤率，則：也就是長(zhǎng)度要達(dá)到4130萬(wàn)以上。第三節(jié)等長(zhǎng)信源編碼定理第十五頁(yè)，共78頁(yè)。1、唯一可譯變長(zhǎng)碼與及時(shí)碼信源符號(hào)出現(xiàn)概率碼1碼2碼3碼4s1s2s3s41/21/41/81/80110011010000111010010001010010001第四節(jié)變長(zhǎng)信源編碼定理第十六頁(yè)，共78頁(yè)。第五節(jié)變長(zhǎng)碼碼1是一個(gè)奇異碼，不是唯一可譯碼；碼2也不是唯一可譯碼，因?yàn)槭盏揭淮蛄惺?，無(wú)法唯一譯出對(duì)應(yīng)的原符號(hào)序列，如0100，即可譯作s4s3s1,也可譯作s4s1s3,s1s2s3或s1s2s1s1；碼3和碼4都是唯一可譯的。但碼3和碼4也不太一樣，碼4稱作逗點(diǎn)碼，只要收到1，就可以立即作出譯碼；而碼3不同，當(dāng)受到一個(gè)或幾個(gè)碼是，必須參考后面的碼才能作出判斷。

定義，在唯一可譯碼中，有一類碼，它在譯碼是無(wú)須參考后面的碼字就可以作出判斷，這種碼稱為即時(shí)碼。第十七頁(yè)，共78頁(yè)。定義：如果一個(gè)碼組中的任一個(gè)碼字都不是另一個(gè)碼字的續(xù)長(zhǎng)，或者說(shuō)，任何一個(gè)碼字后加上若干碼元后都不是碼組中另一個(gè)碼字，則稱為即時(shí)碼。所有的碼非奇異碼唯一可譯碼即時(shí)碼第四節(jié)變長(zhǎng)信源編碼定理第十八頁(yè)，共78頁(yè)。2、即時(shí)碼的樹圖構(gòu)造法我們可以用樹圖的形式構(gòu)造即時(shí)碼，如01001111010010001碼4的樹圖10110000101001000碼3的樹圖第四節(jié)變長(zhǎng)信源編碼定理樹根——碼字的起點(diǎn)樹枝數(shù)——碼的數(shù)節(jié)點(diǎn)數(shù)——碼字的一部分節(jié)數(shù)——碼長(zhǎng)端點(diǎn)——碼字滿樹——等長(zhǎng)碼非滿樹——變長(zhǎng)碼第十九頁(yè)，共78頁(yè)。在每個(gè)節(jié)點(diǎn)上都有r個(gè)分枝的樹稱為整樹，否則稱為非整樹。即時(shí)碼的樹圖還可以用來(lái)譯碼第四節(jié)變長(zhǎng)信源編碼定理第二十頁(yè)，共78頁(yè)。3、克拉夫特（Kraft）不等式定理4.4對(duì)于碼符號(hào)為的任意即時(shí)碼，所對(duì)應(yīng)的碼長(zhǎng)為，則必定滿足：反之，若碼長(zhǎng)滿足上式，則一定存在這樣的即時(shí)碼?？梢愿鶕?jù)即時(shí)碼的樹圖構(gòu)造法來(lái)證明。后來(lái)，B.McMillan證明了對(duì)于唯一可譯碼也必須滿足上面的不等式，第四節(jié)變長(zhǎng)信源編碼定理第二十一頁(yè)，共78頁(yè)。定理4.6若存在一個(gè)碼長(zhǎng)為唯一可譯碼，則一定存在一個(gè)同樣長(zhǎng)度的即時(shí)碼。這說(shuō)明，其他唯一可譯碼在碼長(zhǎng)方面并不比即時(shí)碼占優(yōu)。所以在討論唯一可譯碼時(shí)，只需要討論即時(shí)碼就可以了。第四節(jié)變長(zhǎng)信源編碼定理第二十二頁(yè)，共78頁(yè)。設(shè)信源編碼后的碼字為：碼長(zhǎng)為：則這個(gè)碼的平均長(zhǎng)度為：平均每個(gè)碼元攜帶的信息量即編碼后的信息傳輸率為：若有一個(gè)唯一可譯碼，它的平均碼長(zhǎng)小于其他唯一可譯碼的長(zhǎng)度，則稱此碼為緊致碼或最佳碼，無(wú)失真信源編碼的基本問(wèn)題就是尋找緊致碼。第四節(jié)變長(zhǎng)信源編碼定理第二十三頁(yè)，共78頁(yè)。定理4.8無(wú)失真變長(zhǎng)信源編碼定理（香農(nóng)第一定理）離散無(wú)記憶信源S的N次擴(kuò)展信源，其熵為，并且編碼器的碼元符號(hào)集為A：對(duì)信源進(jìn)行編碼，總可以找到一種編碼方法，構(gòu)成單義可譯碼，使信源S中每個(gè)符號(hào)si所需要的平均碼長(zhǎng)滿足當(dāng)則得：第四節(jié)變長(zhǎng)信源編碼定理第二十四頁(yè)，共78頁(yè)。這個(gè)定理是香農(nóng)信息論中非常重要得一個(gè)定理，它指出，要做到無(wú)失真得信源編碼，信源每個(gè)符號(hào)所需要的平均碼元數(shù)就是信源的熵值，如果小于這個(gè)值，則唯一可譯碼不存在，可見(jiàn)，熵是無(wú)失真信源編碼的極限值。定理還指出，通過(guò)對(duì)擴(kuò)展信源進(jìn)行編碼，當(dāng)N趨向于無(wú)窮時(shí)，平均碼長(zhǎng)可以趨進(jìn)該極限值。還可以證明，如果我們不確切知道信源的概率分布，我們用估計(jì)的概率分布去進(jìn)行編碼時(shí)，平均碼長(zhǎng)會(huì)加長(zhǎng)，但是如果估計(jì)的偏差不大的話，平均碼長(zhǎng)也不會(huì)增加太多（定理4.9的內(nèi)容）。第四節(jié)變長(zhǎng)信源編碼定理第二十五頁(yè)，共78頁(yè)。由得：就是編碼后每個(gè)信源符號(hào)所攜帶的平均信息量第一定理可以表述如下：若就存在唯一可譯變長(zhǎng)碼，若則不存在唯一可譯變長(zhǎng)碼。第四節(jié)變長(zhǎng)信源編碼定理定義：若從信道角度講，信道的信息傳輸率因?yàn)椋核援?dāng)平均碼長(zhǎng)達(dá)到極限值時(shí)，編碼后信道的信息傳輸率為：第二十六頁(yè)，共78頁(yè)。無(wú)噪信道編碼定理若信道的信息傳輸率R不大于信道容量C，總能對(duì)信源的輸出進(jìn)行適當(dāng)?shù)木幋a，使的在無(wú)噪無(wú)損信道上能無(wú)差錯(cuò)的以最大信息傳輸率C傳輸信息，若R小于C，則無(wú)差錯(cuò)傳輸是不可能的。第四節(jié)變長(zhǎng)信源編碼定理編碼效率：碼的剩余度：在二元無(wú)噪無(wú)損信道中：在二元無(wú)噪無(wú)損信道中信息傳輸率：第二十七頁(yè)，共78頁(yè)。例：其熵為：H(S)=0.811我們令s1=0，s2=1，這時(shí)平均碼長(zhǎng)，編碼的效率為。第四節(jié)變長(zhǎng)信源編碼定理二次擴(kuò)展信源進(jìn)行編碼：即時(shí)碼s1s19/160s1s23/1610s2s13/16110s2s21/16111第二十八頁(yè)，共78頁(yè)。第五節(jié)香農(nóng)編碼設(shè)離散無(wú)記憶信源二進(jìn)制香農(nóng)碼的編碼步驟如下：將信源符號(hào)按概率從大到小的順序排列，為方便起見(jiàn)，令p(x1)≥p(x2)≥…≥p(xn)令p(x0)=0，用pa(xj)，j=i+1表示第i個(gè)碼字的累加概率，則：確定滿足下列不等式的整數(shù)ki，并令ki為第i個(gè)碼字的長(zhǎng)度－log2

p(xn)≤ki<－log2

p(xn)+1將pa(xj)用二進(jìn)制表示，并取小數(shù)點(diǎn)后ki位作為符號(hào)xi的編碼。第二十九頁(yè)，共78頁(yè)。第五節(jié)香農(nóng)編碼例有一單符號(hào)離散無(wú)記憶信源對(duì)該信源編二進(jìn)制香農(nóng)碼。其編碼過(guò)程如下表所示。第三十頁(yè)，共78頁(yè)。第五節(jié)香農(nóng)編碼計(jì)算出給定信源香農(nóng)碼的平均碼長(zhǎng)若對(duì)上述信源采用等長(zhǎng)編碼，要做到無(wú)失真譯碼，每個(gè)符號(hào)至少要用3個(gè)比特表示。相比較，香農(nóng)編碼對(duì)信源進(jìn)行了壓縮。由離散無(wú)記憶信源熵定義，可計(jì)算出：對(duì)上述信源采用香農(nóng)編碼的信息率為編碼效率為信源熵和信息率之比。則可以看出，編碼效率并不是很高。第三十一頁(yè)，共78頁(yè)。第六節(jié)費(fèi)諾編碼費(fèi)諾編碼也是一種常見(jiàn)的信源編碼方法。編碼步驟如下：將概率按從大到小的順序排列，令p(x1)≥p(x2)≥…≥p(xn)按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接近或相等。如編二進(jìn)制碼就分成兩組，編m進(jìn)制碼就分成m組。給每一組分配一位碼元。將每一分組再按同樣原則劃分，重復(fù)步驟2和3，直至概率不再可分為止。第三十二頁(yè)，共78頁(yè)。第六節(jié)費(fèi)諾編碼例設(shè)有一單符號(hào)離散信源對(duì)該信源編二進(jìn)制費(fèi)諾碼。編碼過(guò)程如下表。第三十三頁(yè)，共78頁(yè)。第六節(jié)費(fèi)諾編碼該信源的熵為平均碼長(zhǎng)為編碼效率為本例中費(fèi)諾編碼有較高的編碼效率。費(fèi)諾碼比較適合于每次分組概率都很接近的信源。特別是對(duì)每次分組概率都相等的信源進(jìn)行編碼時(shí)，可達(dá)到理想的編碼效率。第三十四頁(yè)，共78頁(yè)。第六節(jié)費(fèi)諾編碼題中碼字還可用碼樹來(lái)表示，如圖所示。第三十五頁(yè)，共78頁(yè)。第七節(jié)霍夫曼編碼霍夫曼(Huffman)編碼是一種效率比較高的變長(zhǎng)無(wú)失真信源編碼方法。編碼步驟二進(jìn)制哈夫曼編碼m進(jìn)制哈夫曼編碼第三十六頁(yè)，共78頁(yè)。第七節(jié)霍夫曼編碼——編碼步驟將信源符號(hào)按概率從大到小的順序排列，令p(x1)≥p(x2)≥…≥p(xn)給兩個(gè)概率最小的信源符號(hào)p(xn-1)和p(xn)各分配一個(gè)碼位“0”和“1”，將這兩個(gè)信源符號(hào)合并成一個(gè)新符號(hào)，并用這兩個(gè)最小的概率之和作為新符號(hào)的概率，結(jié)果得到一個(gè)只包含(n－1)個(gè)信源符號(hào)的新信源。稱為信源的第一次縮減信源，用S1表示。將縮減信源S1的符號(hào)仍按概率從大到小順序排列，重復(fù)步驟2，得到只含(n－2)個(gè)符號(hào)的縮減信源S2。重復(fù)上述步驟，直至縮減信源只剩兩個(gè)符號(hào)為止，此時(shí)所剩兩個(gè)符號(hào)的概率之和必為1。然后從最后一級(jí)縮減信源開始，依編碼路徑向前返回，就得到各信源符號(hào)所對(duì)應(yīng)的碼字。第三十七頁(yè)，共78頁(yè)。第七節(jié)霍夫曼編碼——二進(jìn)制哈夫曼編碼例設(shè)單符號(hào)離散無(wú)記憶信源如下，要求對(duì)信源編二進(jìn)制霍夫曼碼。編碼過(guò)程如下圖（后頁(yè)）。在圖中讀取碼字的時(shí)候，一定要從后向前讀，此時(shí)編出來(lái)的碼字才是可分離的異前置碼。若從前向后讀取碼字，則碼字不可分離。第三十八頁(yè)，共78頁(yè)。第七節(jié)霍夫曼編碼——二進(jìn)制哈夫曼編碼第三十九頁(yè)，共78頁(yè)。第七節(jié)霍夫曼編碼——二進(jìn)制哈夫曼編碼將上圖左右顛倒過(guò)來(lái)重畫一下，即可得到二進(jìn)制哈夫曼碼的碼樹。第四十頁(yè)，共78頁(yè)。信源熵為：平均碼長(zhǎng)為編碼效率為若采用定長(zhǎng)編碼，碼長(zhǎng)K=3，則編碼效率可見(jiàn)哈夫曼的編碼效率提高了12.7%。第七節(jié)霍夫曼編碼——二進(jìn)制哈夫曼編碼第四十一頁(yè)，共78頁(yè)。第七節(jié)霍夫曼編碼——二進(jìn)制哈夫曼編碼注意：哈夫曼的編法并不惟一。每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配“0”和“1”碼元是任意的，所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性，即能得到可分離碼字。不同的碼元分配，得到的具體碼字不同，但碼長(zhǎng)ki不變，平均碼長(zhǎng)也不變，所以沒(méi)有本質(zhì)區(qū)別；縮減信源時(shí)，若合并后的新符號(hào)概率與其他符號(hào)概率相等，從編碼方法上來(lái)說(shuō)，這幾個(gè)符號(hào)的次序可任意排列，編出的碼都是正確的，但得到的碼字不相同。不同的編法得到的碼字長(zhǎng)度ki也不盡相同。第四十二頁(yè)，共78頁(yè)。例：?jiǎn)畏?hào)離散無(wú)記憶信源，用兩種不同的方法對(duì)其編二進(jìn)制哈夫曼碼。siliWi概率s1s2s3s4s512344101000001000110.40.20.20.10.10.40.20.20.20.40.40.20.60.4010101方法一：合并后的新符號(hào)排在其它相同概率符號(hào)的后面。第七節(jié)霍夫曼編碼——二進(jìn)制哈夫曼編碼第四十三頁(yè)，共78頁(yè)。siliWi概率s1s2s3s4s512344101000001000110.40.20.20.10.10.40.20.20.20.40.40.20.60.4010101這兩種編碼哪一種更好呢，我們來(lái)計(jì)算一下二者的碼長(zhǎng)。方法二：合并后的新符號(hào)排在其它相同概率符號(hào)的前面。第七節(jié)霍夫曼編碼——二進(jìn)制哈夫曼編碼第四十四頁(yè)，共78頁(yè)。兩種編碼的平均碼長(zhǎng)是一樣的，都是2.2，那一種更好呢，我們可以計(jì)算一下平均碼長(zhǎng)的方差。定義碼字長(zhǎng)度的方差σ2：第七節(jié)霍夫曼編碼——二進(jìn)制哈夫曼編碼第四十五頁(yè)，共78頁(yè)。第七節(jié)霍夫曼編碼——二進(jìn)制哈夫曼編碼可見(jiàn)：第二種編碼方法的碼長(zhǎng)方差要小許多。意味著第二種編碼方法的碼長(zhǎng)變化較小，比較接近于平均碼長(zhǎng)。第一種方法編出的5個(gè)碼字有4種不同的碼長(zhǎng)；第二種方法編出的碼長(zhǎng)只有兩種不同的碼長(zhǎng)；顯然，第二種編碼方法更簡(jiǎn)單、更容易實(shí)現(xiàn)，所以更好。結(jié)論：在哈夫曼編碼過(guò)程中，對(duì)縮減信源符號(hào)按概率由大到小的順序重新排列時(shí)，應(yīng)使合并后的新符號(hào)盡可能排在靠前的位置，這樣可使合并后的新符號(hào)重復(fù)編碼次數(shù)減少，使短碼得到充分利用。第四十六頁(yè)，共78頁(yè)。第七節(jié)霍夫曼編碼——m進(jìn)制哈夫曼編碼“全樹”概念定義：碼樹圖中每個(gè)中間節(jié)點(diǎn)后續(xù)的枝數(shù)為m時(shí)稱為全樹；若有些節(jié)點(diǎn)的后續(xù)枝數(shù)不足m，就稱為非全樹。二進(jìn)制碼不存在非全樹的情況，因?yàn)楹罄m(xù)枝數(shù)是一時(shí)，這個(gè)枝就可以去掉使碼字長(zhǎng)度縮短。對(duì)m進(jìn)制編碼：若所有碼字構(gòu)成全樹，可分離的碼字?jǐn)?shù)（信源個(gè)數(shù)）必為m+k(m－1)。k為信源縮減次數(shù)。若信源所含的符號(hào)數(shù)n不能構(gòu)成m進(jìn)制全樹，必須增加s個(gè)不用的碼字形成全樹。顯然s<m－1，若s=m－1，意味著某個(gè)中間節(jié)點(diǎn)之后只有一個(gè)分枝，為了節(jié)約碼長(zhǎng)，這一分枝可以省略。第四十七頁(yè)，共78頁(yè)。第七節(jié)霍夫曼編碼——m進(jìn)制哈夫曼編碼在編m進(jìn)制哈夫曼碼時(shí)為了使平均碼長(zhǎng)最短，必須使最后一步縮減信源有m個(gè)信源符號(hào)。非全樹時(shí)，有s個(gè)碼字不用：第一次對(duì)最小概率符號(hào)分配碼元時(shí)就只取(m－s)個(gè)，分別配以0,1,…,m－s－1，把這些符號(hào)的概率相加作為一個(gè)新符號(hào)的概率，與其它符號(hào)一起重新排列。以后每次就可以取m個(gè)符號(hào)，分別配以0,1,…,m－1；…；如此下去，直至所有概率相加得1為止，即得到各符號(hào)的m進(jìn)制碼字。第四十八頁(yè)，共78頁(yè)。第七節(jié)霍夫曼編碼——m進(jìn)制哈夫曼編碼例：對(duì)如下單符號(hào)離散無(wú)記憶信源(例5.4.1)編三進(jìn)制哈夫曼碼。這里：m=3，n=8令k=3，m+k(m－1)=9，則s=9－n=9－8=1所以第一次取m－s=2個(gè)符號(hào)進(jìn)行編碼。第四十九頁(yè)，共78頁(yè)。第七節(jié)霍夫曼編碼——m進(jìn)制哈夫曼編碼第五十頁(yè)，共78頁(yè)。第七節(jié)霍夫曼編碼——m進(jìn)制哈夫曼編碼平均碼長(zhǎng)為：信息率為：編碼效率為：可見(jiàn)：哈夫曼的編碼效率相當(dāng)高，對(duì)編碼器的要求也簡(jiǎn)單得多。第五十一頁(yè)，共78頁(yè)。一些結(jié)論香農(nóng)碼、費(fèi)諾碼、哈夫曼碼都考慮了信源的統(tǒng)計(jì)特性，使經(jīng)常出現(xiàn)的信源符號(hào)對(duì)應(yīng)較短的碼字，使信源的平均碼長(zhǎng)縮短，從而實(shí)現(xiàn)了對(duì)信源的壓縮；香農(nóng)碼有系統(tǒng)的、惟一的編碼方法，但在很多情況下編碼效率不是很高；費(fèi)諾碼和哈夫曼碼的編碼方法都不惟一；費(fèi)諾碼比較適合于對(duì)分組概率相等或接近的信源編碼；哈夫曼碼對(duì)信源的統(tǒng)計(jì)特性沒(méi)有特殊要求，編碼效率比較高，對(duì)編碼設(shè)備的要求也比較簡(jiǎn)單，因此綜合性能優(yōu)于香農(nóng)碼和費(fèi)諾碼。第五十二頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼香農(nóng)編碼、費(fèi)諾編碼、哈夫曼編碼主要是針對(duì)無(wú)記憶信源。當(dāng)信源有記憶時(shí)上述編碼效率不高；游程編碼對(duì)相關(guān)信源編碼更有效；香農(nóng)編碼、費(fèi)諾編碼、哈夫曼編碼屬于無(wú)失真信源編碼；游程編碼屬于限失真信源編碼。第五十三頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼、冗余編碼游程：數(shù)字序列中連續(xù)出現(xiàn)相同符號(hào)的一段。二元序列的游程：只有“0”和“1”兩種符號(hào)。連“0”這一段稱為“0”游程，它的長(zhǎng)度稱為游程長(zhǎng)度L(0)；連“1”這一段稱為“1”游程，它的游程長(zhǎng)度用L(1)表示。游程編碼①二元獨(dú)立序列游程長(zhǎng)度概率若規(guī)定二元序列總是從“0”開始。對(duì)于隨機(jī)序列，游程長(zhǎng)度是隨機(jī)的其取值可為1,2,3,…，直至無(wú)窮。游程長(zhǎng)度序列/游程序列：用交替出現(xiàn)的“0”游程和“1”游程長(zhǎng)度表示任意二元序列。游程變換：是一種一一對(duì)應(yīng)的變換，也是可逆變換。例如：二元序列：0001…，可變換成如下游程序列：第五十四頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼、冗余編碼游程變換減弱了原序列符號(hào)間的相關(guān)性。游程變換將二元序列變換成了多元序列；這樣就適合于用其他方法，如哈夫曼編碼，進(jìn)一步壓縮信源，提高通信效率。編碼方法：首先測(cè)定“0”游程長(zhǎng)度和“1”游程長(zhǎng)度的概率分布，即以游程長(zhǎng)度為元素，構(gòu)造一個(gè)新的信源；對(duì)新的信源（游程序列）進(jìn)行哈夫曼編碼。游程編碼第五十五頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼、冗余編碼②二元獨(dú)立序列游程長(zhǎng)度的熵若二元序列的概率特性已知，由于二元序列與游程變換序列的一一對(duì)應(yīng)性，可計(jì)算出游程序列的概率特性。令“0”和“1”的概率分別為p0和p1，則“0”游程長(zhǎng)度L(0)的概率為p[L(0)]=p0L(0)－1p1式中L(0)=1,2,…,在計(jì)算p[L(0)]時(shí)必然已有“0”出現(xiàn)，否則就不是“0”游程，若下一個(gè)符號(hào)是“1”，則游程長(zhǎng)度為1，其概率是p1=1－p0；若下一個(gè)符號(hào)為“0”、再下一個(gè)符號(hào)為“1”，則游程長(zhǎng)度為2，其概率將為p0p1；依此類推。游程編碼第五十六頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼、冗余編碼游程編碼游程長(zhǎng)度至少是1，理論上，游程長(zhǎng)度可以是無(wú)窮，但很長(zhǎng)的游程實(shí)際出現(xiàn)的概率非常小。同理可得“1”游程長(zhǎng)度L(1)的概率為：P[L(1)]=p1L(1)-1p0“0”游程長(zhǎng)度的熵：第五十七頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼、冗余編碼③二元獨(dú)立序列的平均游程長(zhǎng)度“0”游程序列的平均游程長(zhǎng)度同理可得“1”游程長(zhǎng)度的熵和平均游程長(zhǎng)度游程編碼第五十八頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼、冗余編碼游程編碼④二元獨(dú)立序列的熵“0”游程序列的熵與“1”游程長(zhǎng)度的熵之和除以它們的平均游程長(zhǎng)度之和，即為對(duì)應(yīng)原二元序列的熵H(X)游程變換后符號(hào)熵沒(méi)有變。因?yàn)橛纬套儞Q是一一對(duì)應(yīng)的可逆變換，所以變換后熵值不變。第五十九頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼、冗余編碼游程變換有較好的去相關(guān)效果，因而對(duì)游程序列進(jìn)行哈夫曼編碼可獲得較高的編碼效率。假設(shè)“0”游程長(zhǎng)度的哈夫曼編碼效率為η0，“1”游程長(zhǎng)度的哈夫曼編碼效率為η1，由編碼效率的定義和式(5.4.9)可得對(duì)應(yīng)二元序列的編碼效率（信源熵和信息率之比為編碼效率η=H(X)/R）當(dāng)“0”游程和“1”游程的編碼效率都很高時(shí)，采用游程編碼的效率也很高，至少不會(huì)低于較小的那個(gè)效率。要想編碼效率盡可能高，應(yīng)盡可能提高熵值較大的游程編碼效率。游程編碼第六十頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼算術(shù)編碼不同于哈夫曼碼，它是非分組（非塊）碼。它從全序列出發(fā)，考慮符號(hào)之間的關(guān)系來(lái)進(jìn)行編碼。算術(shù)編碼利用了累積概率的概念。算術(shù)碼主要的編碼方法是計(jì)算輸入信源符號(hào)序列所對(duì)應(yīng)的區(qū)間。因?yàn)樵诰幋a過(guò)程中，每輸入一個(gè)符號(hào)要進(jìn)行乘法和加法運(yùn)算，所以稱此編碼方法為算術(shù)編碼。二元序列的算術(shù)編碼可用于黑白圖像的編碼，例如傳真。第六十一頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼設(shè)信源符號(hào)集A={a1,a2,…,an}，其相應(yīng)概率分布為P(ai)，P(ai)>0(i=1,2,…,n)信源符號(hào)的累積分布函數(shù)為：所得累積分布函數(shù)為每臺(tái)級(jí)的下界值，則其區(qū)間為[0,1)左閉右開區(qū)間。

F(a1)=0

F(a2)=P(a1)

F(a3)=P(a1)+P(a2)…當(dāng)A={0,1}二元信源時(shí)：F(0)=0，F(xiàn)(1)=P(0)第六十二頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼計(jì)算二元無(wú)記憶信源序列的累積分布函數(shù)初始時(shí)：在[0,1)區(qū)間內(nèi)由F(1)劃分成二個(gè)子區(qū)間[0,F(1))和[F(1),1)，F(xiàn)(1)=P(0)。子區(qū)間[0,F(1))的寬度為A(0)=P(0)，對(duì)應(yīng)于信源符號(hào)“0”；子區(qū)間[F(1),1)的寬度為A(1)=P(1)，對(duì)應(yīng)于信源符號(hào)“1”；若輸入符號(hào)序列的第一個(gè)符號(hào)為s=“0”，落入[0,F(1))區(qū)間，得累積分布函數(shù)F(s=“0”)=F(0)=0；

第六十三頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼輸入第二個(gè)符號(hào)為“1”，s=“01”s=“01”所對(duì)應(yīng)的區(qū)間是在區(qū)間[0,F(1))中進(jìn)行分割；符號(hào)序列“00”對(duì)應(yīng)的區(qū)間寬度為:A(00)=A(0)P(0)=P(0)P(0)=P(00)；對(duì)應(yīng)的區(qū)間為[0,F(s=“01”))。符號(hào)序列“01”對(duì)應(yīng)的區(qū)間寬度為A(01)=A(0)P(1)=P(0)P(1)=P(01)=A(0)－A(00)；對(duì)應(yīng)的區(qū)間為[F(s=“01”),F(1))。累積分布函數(shù)F(s=“01”)=P(00)=P(0)P(0)第六十四頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼第六十五頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼輸入第三個(gè)符號(hào)為“1”：輸入序列可記做s1=“011”（若第三個(gè)符號(hào)輸入為“0”，可記做s0=“010”）；現(xiàn)在，輸入序列s1=“011”對(duì)應(yīng)的區(qū)間是對(duì)區(qū)間[F(s),F(1))進(jìn)行分割；序列s0=“010”對(duì)應(yīng)的區(qū)間寬度為A(s=“010”)=A(s=“01”)P(0)=A(s)P(0)其對(duì)應(yīng)的區(qū)間為[F(s),F(s)+A(s)P(0))；序列s1=“011”對(duì)應(yīng)的區(qū)間寬度為

A(s=“011”)=A(s)P(1)=A(s=“01”)－A(s=“010”)=A(s)－A(s0)其對(duì)應(yīng)的區(qū)間為[F(s)+A(s)P(0),F(1))；符號(hào)序列s1=“011”的累積分布函數(shù)為F(s1)=F(s)+A(s)P(0)；若第三個(gè)符號(hào)輸入為“0”，符號(hào)序列s0=“010”的區(qū)間下界值仍為F(s)，得符號(hào)序列s0=“010”的累積分布函數(shù)為F(s0)=F(s)。第六十六頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼歸納當(dāng)已知前面輸入符號(hào)序列為s，若接著再輸入一個(gè)符號(hào)“0”，序列s0的累積分布函數(shù)為：F(s0)=F(s)對(duì)應(yīng)區(qū)間寬度為：A(s0)=A(s)P(0)若接著輸入的一個(gè)符號(hào)是“1”，序列的累積分布函數(shù)為：F(s1)=F(s)+A(s)P(0)對(duì)應(yīng)區(qū)間寬度為：A(s1)=A(s)P(1)=A(s)－A(s0)第六十七頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼符號(hào)序列對(duì)應(yīng)的區(qū)間寬度A(s=“0”)=P(0)A(s=“1”)=1－A(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=“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)

信源符號(hào)序列s所對(duì)應(yīng)區(qū)間的寬度等于符號(hào)序列s的概率P(s)。第六十八頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼二元信源符號(hào)序列的累積分布函數(shù)的遞推公式F(sr)=F(s)+P(s)F(r)(r=0,1)

sr表示已知前面信源符號(hào)序列為s，接著再輸入符號(hào)為rF(0)=0，F(xiàn)(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)第六十九頁(yè)，共78頁(yè)。第八節(jié)游程編碼、算術(shù)編碼、冗余編碼算術(shù)編碼舉例：已輸入二元符號(hào)序列為s=“011”，接著再輸入符號(hào)為“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”)+P(0)P(0)+P(01)P(0)+P(011)P(0)=0+P(00)+P(010)+P(0110)對(duì)應(yīng)的區(qū)間寬度為A(s1)=P(s=“011”)P(1)=P(011)P(1)=P(0111)上述整個(gè)分析過(guò)程可用圖5.6.1描述式(5.6.1)和(5.6.2)是可遞推運(yùn)算，在實(shí)際中，只需兩個(gè)存儲(chǔ)器，把P(s)和F(s)存下來(lái)，然后，根據(jù)輸入符號(hào)和式(5.6.1)、(5.6.2)更新兩個(gè)存儲(chǔ)器中的數(shù)值