第5(8)章無失真信源編碼定理(OK)

第5(8)章無失真信源編碼定理(OK)第一頁，共54頁。5.1信源編碼概論--基本概念噪聲信道信源編碼信源信宿等效無噪信道信源譯碼信道編碼信道譯碼傳輸之前的兩次變換：信源編碼、信道編碼。傳輸之后的兩次反變換，變換與反變換是成對出現(xiàn)的。討論無失真信源編碼可以先不考慮抗干擾問題，因此，圖中虛框部分可近似地視為一個等效的無噪信道，這一點是我們討論信源編碼的前提。1、基本概念第二頁，共54頁。信源編碼分類：無失真編碼、有失真編碼。無失真編碼：只對信源的冗余度進行壓縮，不會改變信源的熵，又稱冗余度壓縮編碼，它能保證碼元序列經(jīng)譯碼后能無失真地恢復成信源符號序列。有失真編碼：又稱熵壓縮編碼，將在第7章討論。無失真信源編碼的作用：（1）符號變換：使信源的輸出符號與信道的輸入符號相匹配；（2）冗余度壓縮：使編碼之后的新信源概率分布均勻化，信息含量效率等于或接近于100%。5.1信源編碼概論--基本概念第三頁，共54頁。5.1信源編碼概論----編碼器模型碼C碼字集C

碼字wi

碼元集

X碼元xi

編碼器f信源信源編碼

：一一對應的變換:基本概念：碼長li、等長碼、變長碼、平均碼長第四頁，共54頁。碼長li

：碼字wi所含碼元的個數(shù)。單位：碼元/符號，r進制單位/符號。

等長碼(FLC，F(xiàn)ixedLengthcode)：碼中所有碼字均有相同的碼長l；否則稱為變長碼(VLC，VariableLengthcode)。平均碼長：碼元/符號

定長碼：

平均碼長是衡量碼的性能的重要參數(shù)，“平均碼長小”說明平均一個碼元所攜帶的信息量大，信息的冗余就小。5.1信源編碼概論--編碼器模型碼元/符號

變長碼：第五頁，共54頁。例：編碼設一信源的概率空間為對其單個符號進行二進制編碼。

碼元/符號

碼元/符號

編碼策略：經(jīng)常出現(xiàn)（概率大）的符號采用較短的碼字，不經(jīng)常出現(xiàn)（概率?。┑姆柌捎幂^長的碼字。編碼策略：采用等長的碼字。第六頁，共54頁。3、編碼器的輸出f是一一對應的映射

新信源X：編碼后的信道的信息傳輸率R

：平均每個碼元攜帶的信息量。平均碼長越小，每個碼元攜帶的信息量就越多，傳輸一個碼元就傳輸了較多的信息。5.1信源編碼概論編碼器f信源第七頁，共54頁。4、編碼效率為了衡量編碼效果，定義編碼效率：編碼后的實際信息率與編碼后的最大信息率之比。

注：編碼效率實際上也是新信源X的信息含量效率或熵的相對率。新信源的冗余度也是碼的冗余度：5.1信源編碼概論編碼器f信源第八頁，共54頁。5.2碼的唯一可譯性f為一一對應的變換只是無失真編碼的必要條件，并不充分;要保證將碼元序列無失真地恢復成信源符號序列，還要求編出的碼自身具有獨特的結構。有實用價值的碼應該具有唯一可譯性，即能從碼字序列（也是碼元序列）唯一地恢復成信源符號序列。噪聲信道信源編碼信源信宿等效無噪信道信源譯碼信道編碼信道譯碼f-1f第九頁，共54頁。1、唯一可譯碼（UDC，UniquelyDecodableCode）唯一可譯碼（UDC）：該碼的碼字組成的任意有限長碼字序列都能恢復成唯一的信源序列。否則稱為非唯一可譯碼。碼是唯一可譯碼的充分必要條件是：由碼中的碼字組成的任意有限長的碼字序列（也是碼元序列），都能唯一劃分成一個個的碼字，且任一碼字只與唯一一個信源符號對應。奇異碼：含相同碼字的碼稱奇異碼。否則稱為非奇異碼。

5.2碼的唯一可譯性第十頁，共54頁。即時碼：在惟一可譯變長碼中，有一類碼，它在譯碼時無需參考后續(xù)的碼符號就能立即做出判斷，譯成對應的信源符號，則這類碼稱為即時碼。

前綴條件碼：碼中任一完整碼字都不是另一碼字的前綴。該碼也稱異前置碼或非延長碼。此碼為即時碼。

5種不同的碼例題：5.2碼的唯一可譯性第十一頁，共54頁。W3：變長非奇異碼，但不是UDC

。W5：變長碼、非奇異碼、延長碼。是UDC。W4：變長碼、非奇異碼、是UDC

。5種不同的碼例題：W1：等長非奇異碼。是UDC。W2：等長奇異碼，不是UDC。等長非奇異碼一定是惟一可譯碼。5.2碼的唯一可譯性第十二頁，共54頁。唯一可譯碼等長非奇異碼即時碼非奇異碼惟一可譯碼的判斷方法：P182：將碼中所有碼字可能的尾隨后綴組成一個集合F，當且僅當集合F中沒有包含任一碼字，則可判斷此碼為惟一可譯碼。5.2碼的唯一可譯性第十三頁，共54頁。2、碼樹

一階節(jié)點二階節(jié)點三階節(jié)點W1={00，01，10，11}W4={0，10，110，111}W5={0，01，011，111}5.2碼的唯一可譯性第十四頁，共54頁。碼樹從樹根開始向上長出樹枝，樹枝代表碼元，樹枝與樹枝的交點叫做節(jié)點。r進制碼樹：碼元個數(shù)為r，各節(jié)點（含樹根）向上長出的樹枝數(shù)不大于r。l階節(jié)點：經(jīng)過l根樹枝才能到達的節(jié)點。終端節(jié)點或端點：向上不長出樹枝的節(jié)點。碼字：與碼樹上的節(jié)點對應，組成該碼字的碼元就是從樹根開始到該節(jié)點所經(jīng)過的樹枝（或碼元）。非延長碼：所有碼字均處于終端節(jié)點，即端點上。

整樹：r進制碼樹各節(jié)點（包括樹根）向上長出的樹枝數(shù)均等于r。5.2碼的唯一可譯性第十五頁，共54頁。不滿足Kraft不等式的碼肯定不是非延長碼；滿足Kraft不等式的碼也不一定是非延長碼；根據(jù)滿足Kraft不等式的碼長集合可構造出一個非延長碼；上述定理對唯一可譯碼仍然成立。

即時碼存在性定理：對于任一進制即時碼，各碼字的碼長為則必定滿足Kraft不等式：

反過來，若上式成立，就一定能構造一個進制即時碼。5.2碼的唯一可譯性（--Kraft不等式）第十六頁，共54頁。5.3等長編碼定理和等長編碼方法1、對信源輸出的符號序列進行編碼

信源編碼器f信源編碼器f對信源U的單個符號進行編碼

對信源U的N長符號串進行編碼

對擴展信源UN的單個符號進行編碼

第十七頁，共54頁。2、等長編碼定理

信源編碼器fr進制定長編碼，碼長為lN，可用的碼字數(shù)目：唯一可譯5.3等長編碼定理和等長編碼方法第十八頁，共54頁。

等長無失真編碼定理：用r元符號對離散無記憶信源U的N長符號序列進行定長編碼，N長符號序列對應的碼長為lN，若對于任意小的正數(shù)，有不等式

就幾乎能做到無失真編碼，且隨著序列長度N的增大，譯碼差錯率趨于0。反過來，若

就不可能做到無失真編碼，且隨著N的增大，譯碼差錯率趨于1。5.3等長編碼定理和等長編碼方法第十九頁，共54頁。3、等長編碼方法（例）對U的單個符號進行2進制編碼。碼元集：X={0，1}

取l=3bit/符號碼元/符號提高編碼效率的方法：對符號串進行編碼，同時引入一定的失真。第二十頁，共54頁。5.4變長編碼定理(香農(nóng)第一定理

)定理5.8：無失真變長信源編碼定理：離散無記憶信源的N次擴展信源，其熵為，并有碼符號對信源進行編碼，總可以找到一種編碼方法，構成惟一可譯碼，使信源S中的每個信源符號所需的平均碼長滿足：第二十一頁，共54頁。5.5變長編碼方法變長編碼采用非延長碼；力求平均碼長最小，此時編碼效率最高，信源的冗余得到最大程度的壓縮；對給定的信源，使平均碼長達到最小的編碼方法稱為最佳編碼，編出的碼稱為最佳碼；三種變長編碼方法：霍夫曼編碼、費諾編碼以及香農(nóng)編碼；霍夫曼編碼是真正意義下的最佳編碼。第二十二頁，共54頁。1、霍夫曼編碼

二進制霍夫曼編碼過程如下：（1）將信源符號按概率大小排序；（2）對概率最小的兩個符號求其概率之和，同時給兩符號分別賦予碼元“0”和“1”；（3）將“概率之和”當作一個新符號的概率，與剩下符號的概率一起，形成一個縮減信源，再重復上述步驟，直到“概率之和”為1為止；（4）按上述步驟實際上構造了一個碼樹，從樹根到端點經(jīng)過的樹技即為碼字。5.5變長編碼方法第二十三頁，共54頁。符號概率碼字Wi碼長li11012001300014000015000001600000062進制霍夫曼編碼。碼元集：X={0，1}

非延長碼，平均碼長最小，碼字不唯一。第二十四頁，共54頁?；舴蚵幋a的基本特點編出的碼是非延長碼：霍夫曼編碼實際上構造了一個碼樹，碼樹從最上層的端點開始構造，直到樹根結束，最后得到一個橫放的碼樹。平均碼長最?。夯舴蚵幋a采用概率匹配方法來決定各碼字的碼長，概率大的符號對應于短碼，概率小的符號對應于長碼。碼字不唯一：每次對概率最小的兩個符號求概率之和形成縮減信源時，就構造出兩個樹枝，由于給兩個樹枝賦碼元時是任意的，碼字不唯一。第二十五頁，共54頁。等長編碼與變長編碼冗余壓縮效果比較等長編碼變長編碼碼元/符號碼元/符號bit/符號bit/符號bit/符號第二十六頁，共54頁。符號概率碼字Wi碼長li0.35110.300120.2000130.10000140.040000150.00500000160.00500000062進制霍夫曼編碼。碼元集：X={0，1}

bit/符號第二十七頁，共54頁。r進制霍夫曼編碼每次求縮減信源時，求r個最小概率之和，即將個概率最小的r符號縮減為一個新符號，直到概率之和為1終止。新問題：縮減到最后時剩下不到r個符號了。為保證平均碼長最小，希望縮減到最后剛好還剩下r個符號。為達到此目的，可給信源添加幾個無用的符號（概率為0的符號），使得信源符號數(shù)q滿足:q=(r-1)θ+r

信源縮減的次數(shù)第二十八頁，共54頁。符號概率碼字Wi碼長li0.32210.22120.180220.160120.0800230.0400130.003進制霍夫曼編碼。碼元集：X={0，1，2}

bit/符號第二十九頁，共54頁。符號串的霍夫曼編碼例：對如下DMS進行2進制霍夫曼編碼，分別對單個符號和二元符號串進行編碼。bit/符號符號概率碼字碼長u10.4511u20.35012u30.20002碼元/符號對單個符號進行編碼第三十頁，共54頁。符號概率碼字碼長u1u10.2025112u1u20.15750113u2u10.15750013u2u20.12250003u1u30.091013u3u10.0901014u2u30.0701004u3u20.0710014u3u30.0410004碼元/符號對二元符號串進行編碼第三十一頁，共54頁。2、費諾（Fano）編碼

費諾（Fano）編碼也是構造一個碼樹，因此，編出的碼是非續(xù)長碼，但不一定是最佳碼。費諾編碼步驟(以二進制編碼為例)：（1）將信源符號按概率從大到小的排序；（2）將信源符號分成2組，使2組信源符號的概率之和近似相等，并給2組信源符號分別賦碼元“0”和“1”；（3）接下來再把各小組的信源符號細分為2組并賦碼元，方法與第一次分組相同；（4）如此一直進行下去，直到每一小組只含一個信源符號為止；（5）由此即可構造一個碼樹，所有終端節(jié)點上的碼字組成費諾碼。第三十二頁，共54頁。符號ui概率P(u1)碼字Wi碼長liu10.20002u20.190103u30.180113u40.17102u50.151103u60.1011104u70.01111142進制費諾編碼。碼元集：X={0，1}

碼元/符號bit/符號第三十三頁，共54頁。概率大，則分解的次數(shù)少；概率小,則分解的次數(shù)多。這符合最佳編碼原則。碼字集合是唯一的。分解完了，碼字出來了，碼長也有了。因此，費諾編碼方法又稱為子集分解法。費諾編碼方法比較適合于每次分組概率都很接近的信源，特別是對每次分組概率都相等的信源進行編碼時，可達到理想的編碼效率。費諾編碼特點第三十四頁，共54頁。3、香農(nóng)編碼設離散無記憶信源二進制香農(nóng)碼的編碼步驟如下：將信源符號按概率從大到小的順序排列，為方便起見，令p(x1)≥p(x2)≥…≥p(xn)令p(x0)=0，用pa(xj)，j=i+1表示第i個碼字的累加概率，則第三十五頁，共54頁。3、香農(nóng)編碼確定滿足下列不等式的整數(shù)ki，并令ki為第i個碼字的長度－log2

p(xi)≤ki<1－log2

p(xi)將pa(xj)用二進制表示，并取小數(shù)點后ki位作為符號xi的編碼。第三十六頁，共54頁。1.某信源具有7個消息符號，其概率分別為：0.20,0.19,0.18,0.17,0.15,0.10,0.01。欲對其進行香農(nóng)方法的二進制編碼，求其二進制代碼組及其編碼效率。

解：先計算每一個碼字的碼長，分別為：3,3,3,3,3,4,7；再計算累加概率。例如：P4=p1+p2+p3=0.20+0.19=0.18=0.57，變換成二進制數(shù)為：0.1001···，因為b4=3，故對于概率為0.17的消息符號x4，其編碼為100。依此類推，與本題有關的數(shù)據(jù)和編碼結果列于下表。例題第三十七頁，共54頁。例題第三十八頁，共54頁?？梢郧蟪銎淦骄a長和信源熵分別為3.14碼元/符號和2.16比特/符號，故其信息傳輸速率為同樣，本題也是二進制信道，信道容量C=1比特/碼元時間，故其編碼效率在數(shù)值上等于信息傳輸速率，即=83.1%。上述兩個例子可見，香農(nóng)編碼方法對有的信源能夠達到最佳編碼而有的則不能，因此還不能說它是最佳編碼。例題第三十九頁，共54頁。香農(nóng)編碼方法特點：由于bi總是進一取整，香農(nóng)編碼方法不一定是最佳的；由于第一個消息符號的累加概率總是為0，故它對應的碼字總是0、00、000、0…0的式樣；碼字集合是唯一的，且為即時碼；先有碼長再有碼字；對于一些信源，編碼效率不高，冗余度稍大，因此其實用性受到較大限制。3、香農(nóng)編碼第四十頁，共54頁。游程：指的是字符序列中各個字符連續(xù)重復出現(xiàn)而形成字符串的長度，又稱游程長度或游長。編碼方法：首先測定“0”游程長度和“1”游程長度的概率分布，即以游程長度為元素，構造一個新的信源；對新的信源（游程序列）進行哈夫曼編碼。4、二元游程編碼第四十一頁，共54頁。其中為“0”游程長度的霍夫曼編碼效率，為“1”游程長度的霍夫曼編碼效率。4、二元游程編碼游程長度概率：二元序列的編碼效率：第四十二頁，共54頁。游程變換減弱了原序列符號間的相關性。游程變換將二元序列變換成了多元序列；這樣就適合于用其他方法，如哈夫曼編碼，進一步壓縮信源，提高通信效率。多元序列也可以變換成游程序列，如m元序列可有m種游程。但是變換成游程序列時，需要增加標志位才能區(qū)分游程序列中的“長度”是m種游程中的哪一個的長度，否則，變換就不可逆。這樣，增加的標志位可能會抵消壓縮編碼得到的好處。所以，對多元序列進行游程變換的意義不大。4、二元游程編碼第四十三頁，共54頁。1.一個信源包含6個符號消息，它們的出現(xiàn)概率分別為0.3,0.2,0.15,0.15,0.1,0.1，信道基本符號為二進制碼元，試用哈夫曼編碼方法對該信源的6個符號進行信源編碼，并求出代碼組的平均長度和信息傳輸速率。解根據(jù)哈夫曼編碼的步驟，可得其編碼過程和編碼結果，如下圖所示。習題1第四十四頁，共54頁。習題1第四十五頁，共54頁。由編碼結果，求得平均碼長為=2.5碼元/符號信源熵為信息傳輸速率為由此可得其編碼效率為98.8%，接近于最佳編碼。習題1第四十六頁，共54頁。習題22.信源符號X有8種消息，概率為(1/2,1/4,1/8,1/16,1/3