信息理論與編碼4

第4章離散無記憶信源無失真編碼信息傳輸系統(tǒng)編碼和譯碼示意圖噪聲信道信源編碼信源信宿等效無噪信道信源譯碼信道編碼信道譯碼信息傳輸系統(tǒng)編碼和譯碼示意圖信息理論與編碼1第4章離散無記憶信源無失真編碼信源編（譯）碼和信道編（譯）碼信源發(fā)出的消息序列通常不能直接送給信道傳輸，需要經(jīng)過兩次變換，分別稱為信源編碼和信道編碼，然后送給信道傳送，信道輸出經(jīng)過兩次反變換，即信道譯碼和信源譯碼，就可送給信宿接受了。信息理論與編碼2第4章離散無記憶信源無失真編碼無失真編碼和有失真編碼信源編碼可分為無失真編碼和有失真編碼兩類。無失真編碼只對(duì)信源的冗余度進(jìn)行壓縮，而不會(huì)改變信源的熵，又稱冗余度壓縮編碼。與之相對(duì)的是有失真編碼，又稱熵壓縮編碼。信息理論與編碼3第4章離散無記憶信源無失真編碼無失真信源編碼的作用（1）符號(hào)變換：使信源的輸出符號(hào)與信道的輸入符號(hào)相匹配；（2）冗余度壓縮：使編碼之后的新信源概率分布均勻化，信息含量效率等于或接近于100%。信息理論與編碼4第4章離散無記憶信源無失真編碼本章主要內(nèi)容4.1信源編碼概論4.2碼的唯一可譯性4.3定長(zhǎng)編碼定理和定長(zhǎng)編碼方法4.4變長(zhǎng)編碼定理4.5變長(zhǎng)編碼方法4.6幾種實(shí)用的無失真信源編碼信息理論與編碼5第4章離散無記憶信源無失真編碼4.1信源編碼概論信源編碼器示意圖定長(zhǎng)編碼和變長(zhǎng)編碼平均碼長(zhǎng)編碼效率信息理論與編碼6第4章離散無記憶信源無失真編碼信源編碼器示意圖

——信源符號(hào)集合；

——碼元組成的集合；

——信道能夠傳送的符號(hào)，稱為碼元；

——信源編碼，一一對(duì)應(yīng)映射，

——把信源輸出的符號(hào)變換成的碼元序列，稱為碼字；

——所有碼字組成的集合，稱為碼或碼字集。

——所含碼元的個(gè)數(shù)，稱為該碼字的碼長(zhǎng)，單位“碼元/符號(hào)”或“r進(jìn)制單位/符號(hào)”。編碼器信源信源編碼器示意圖信息理論與編碼7第4章離散無記憶信源無失真編碼定長(zhǎng)編碼和變長(zhǎng)編碼

如果所有碼字均有相同的碼長(zhǎng)，即則稱為定長(zhǎng)編碼；否則，稱為變長(zhǎng)編碼。平均碼長(zhǎng)對(duì)碼W中所有碼字的碼長(zhǎng)求統(tǒng)計(jì)平均，碼元/符號(hào)對(duì)于定長(zhǎng)碼，平均碼長(zhǎng)與各碼字的碼長(zhǎng)相等，即碼元/符號(hào)小說明平均一個(gè)碼元所攜帶的信息量大，信息的冗余就小。信息理論與編碼8第4章離散無記憶信源無失真編碼例設(shè)DMS的概率空間為對(duì)其單個(gè)符號(hào)進(jìn)行二進(jìn)制編碼，即碼元集合為。定義編碼為碼元/符號(hào)信息理論與編碼9第4章離散無記憶信源無失真編碼定義編碼為

碼元/符號(hào)信息理論與編碼10第4章離散無記憶信源無失真編碼編碼效率信源編碼器輸出可視為一個(gè)新信源，該信源若以碼字集作為符號(hào)集，則為信源W，若以碼元集當(dāng)作符號(hào)集，則為信源X，如圖所示。

將信源編碼器的輸出視為新信源W或X

無失真編碼信源符號(hào)與碼字是一一對(duì)應(yīng)的，故，所以編碼前后的熵保持不變：

bit/碼字或bit/符號(hào)即無失真信源編碼是保熵的。編碼器信源信息理論與編碼11第4章離散無記憶信源無失真編碼將信源編碼器輸出視為新信源X，則有

bit/碼元編碼后的信息率，記為R，就是X的熵，

bit/碼元定義編碼后的實(shí)際信息率與編碼后的最大信息率之比為編碼效率，記為，冗余度：信息理論與編碼12第4章離散無記憶信源無失真編碼4.2碼的唯一可譯性4.2.1常見碼及其唯一可譯性4.2.2碼樹和Kraft不等式信息理論與編碼13第4章離散無記憶信源無失真編碼4.2.1常見碼及其唯一可譯性唯一可譯碼和非唯一可譯碼碼W是唯一可譯碼的充分必要條件奇異碼和非奇異碼非續(xù)長(zhǎng)碼和續(xù)長(zhǎng)碼及時(shí)碼或立即碼各種碼的關(guān)系信息理論與編碼14第4章離散無記憶信源無失真編碼唯一可譯碼和非唯一可譯碼若碼的碼字組成的任意有限長(zhǎng)碼字序列都能恢復(fù)成唯一的信源序列，則稱該碼為唯一可譯碼（UDC，UniquelyDecodableCode），否則稱為非唯一可譯碼。碼是唯一可譯碼的充分必要條件由W中的碼字組成的任意有限長(zhǎng)的碼字序列（也是碼元序列），都能唯一劃分成一個(gè)個(gè)的碼字，且任一碼字只與唯一一個(gè)信源符號(hào)對(duì)應(yīng)。信息理論與編碼15第4章離散無記憶信源無失真編碼下表中，對(duì)信源U編了5種不同的碼，碼的特征各有不同。W1和W2是定長(zhǎng)碼，其余是變長(zhǎng)碼。這5種碼中，有些能唯一譯碼，有些不能。表5種不同的碼信息理論與編碼16第4章離散無記憶信源無失真編碼奇異碼和非奇異碼含相同碼字的碼稱為奇異碼，否則稱為非奇異碼。奇異碼肯定不是UDC。定長(zhǎng)非奇異碼肯定是UDC。非續(xù)長(zhǎng)碼和續(xù)長(zhǎng)碼任一碼字都不是另一碼字的續(xù)長(zhǎng)（加長(zhǎng)），這種碼稱為非續(xù)長(zhǎng)碼；有些碼字是在另一些碼字后面添加碼元（續(xù)長(zhǎng)）得來的，稱為續(xù)長(zhǎng)碼。及時(shí)碼或立即碼碼字的最后一個(gè)碼元出現(xiàn)時(shí)，譯碼器能立即判斷一個(gè)碼字已經(jīng)結(jié)束，可以立即譯碼。信息理論與編碼17第4章離散無記憶信源無失真編碼各種碼的關(guān)系各種碼的關(guān)系圖非續(xù)長(zhǎng)碼不但唯一可譯，而且即時(shí)可譯；而續(xù)長(zhǎng)碼中只有一部分是唯一可譯的，并且不是即時(shí)可譯的。唯一可譯碼定長(zhǎng)非奇異碼非續(xù)長(zhǎng)碼非奇異碼信息理論與編碼18第4章離散無記憶信源無失真編碼4.2.2碼樹和Kraft不等式碼樹非續(xù)長(zhǎng)碼可用碼樹表示。碼樹從樹根開始向上長(zhǎng)出樹枝，樹枝代表碼元，樹枝與樹枝的交點(diǎn)叫做節(jié)點(diǎn)。經(jīng)過l根樹枝才能到達(dá)的節(jié)點(diǎn)稱為l階節(jié)點(diǎn)。向上不長(zhǎng)出樹枝的節(jié)點(diǎn)稱為終端節(jié)點(diǎn)或端點(diǎn)。

r進(jìn)制碼樹各節(jié)點(diǎn)（包括樹根）向上長(zhǎng)出的樹枝數(shù)不會(huì)超過r，若等于r則稱為整樹。信息理論與編碼19第4章離散無記憶信源無失真編碼下圖中，(a)和(b)是整樹，(c)為非整樹。二進(jìn)制碼樹：（a）W1

的碼樹；（b）W4

的碼樹；（c）W5

的碼樹一階節(jié)點(diǎn)二階節(jié)點(diǎn)三階節(jié)點(diǎn)信息理論與編碼20第4章離散無記憶信源無失真編碼定理對(duì)于任一r進(jìn)制非續(xù)長(zhǎng)碼，各碼字的碼長(zhǎng)，，必須滿足Kraft不等式：反過來，若上式成立，就一定能構(gòu)造一個(gè)r進(jìn)制非續(xù)長(zhǎng)碼。本定理是非續(xù)長(zhǎng)碼的存在性定理。不滿足Kraft不等式的碼肯定不是非續(xù)長(zhǎng)碼，而滿足Kraft不等式的碼也不一定是非續(xù)長(zhǎng)碼。信息理論與編碼21第4章離散無記憶信源無失真編碼定理對(duì)于任一r進(jìn)制唯一可譯碼（UDC），各碼字的碼長(zhǎng)，，必須滿足Kraft不等式：反過來，若上式成立，就一定能構(gòu)造一個(gè)r進(jìn)制唯一可譯碼（UDC）。奇異碼肯定不是唯一可譯碼；非續(xù)長(zhǎng)碼一定是唯一可譯碼。信息理論與編碼22第4章離散無記憶信源無失真編碼4.3定長(zhǎng)編碼定理和定長(zhǎng)編碼方法定長(zhǎng)編碼惟一可譯條件定長(zhǎng)無失真編碼定理信息理論與編碼23第4章離散無記憶信源無失真編碼定長(zhǎng)編碼惟一可譯條件

假設(shè)DMS為，發(fā)出的長(zhǎng)符號(hào)序列或的單個(gè)符號(hào)總共有個(gè)，因此要找個(gè)r進(jìn)制碼字與之對(duì)應(yīng)。對(duì)于定長(zhǎng)編碼，平均碼長(zhǎng)與各碼字的碼長(zhǎng)相等。碼長(zhǎng)為的r進(jìn)制定長(zhǎng)非奇異碼總共含個(gè)碼字，可用的碼字?jǐn)?shù)不少于的符號(hào)數(shù)，即就可做到唯一譯碼。信息理論與編碼24第4章離散無記憶信源無失真編碼將上式整理一下得

式中，代表的一個(gè)符號(hào)所用去的碼元數(shù)目，量綱為“碼元/符號(hào)”；代表的最大r進(jìn)制熵，量綱為“r進(jìn)制單位/符號(hào)”。物理意義：對(duì)的長(zhǎng)符號(hào)序列進(jìn)行等長(zhǎng)編碼，若要求所編的碼唯一可譯，則的一個(gè)符號(hào)所需用去的碼元數(shù)目以的最大r進(jìn)制熵為下界，再小就不能唯一可譯了。信息理論與編碼25第4章離散無記憶信源無失真編碼定長(zhǎng)無失真編碼定理

用r元符號(hào)表對(duì)離散無記憶信源的長(zhǎng)符號(hào)序列進(jìn)行定長(zhǎng)編碼，長(zhǎng)符號(hào)序列對(duì)應(yīng)的碼長(zhǎng)為，若對(duì)于任意小的正數(shù)，有不等式

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

就不可能做到無失真編碼，且隨著的增大，譯碼差錯(cuò)率趨于1。信息理論與編碼26第4章離散無記憶信源無失真編碼幾點(diǎn)說明：（1）碼長(zhǎng)的界。用r元符號(hào)表對(duì)信源進(jìn)行定長(zhǎng)編碼，是定長(zhǎng)無失真編碼單符號(hào)碼長(zhǎng)的下界。（2）定理是針對(duì)離散無記憶信源給出的，對(duì)更一般的信源也有類似結(jié)論。（3）定長(zhǎng)編碼的效率為信息理論與編碼27第4章離散無記憶信源無失真編碼例1

DMS為用碼元表對(duì)的單個(gè)符號(hào)進(jìn)行編碼，即對(duì)的單個(gè)符號(hào)進(jìn)行2進(jìn)制編碼。解用的兩個(gè)碼元對(duì)的七個(gè)符號(hào)進(jìn)行編碼，

碼元/符號(hào)取l=3；碼長(zhǎng)為3的2進(jìn)制碼字有8個(gè)，取其中任意7個(gè)碼字分別賦給7個(gè)信源符號(hào)即可，

信息理論與編碼28第4章離散無記憶信源無失真編碼如容易算出信源的熵為

bit/符號(hào)平均碼長(zhǎng)和編碼效率分別為碼元/符號(hào)顯然，編碼效率是不高的。信息理論與編碼29第4章離散無記憶信源無失真編碼若要提高編碼效率，可對(duì)的符號(hào)序列進(jìn)行編碼，同時(shí)引入一定的失真。定長(zhǎng)編碼定理限定了定長(zhǎng)編碼碼長(zhǎng)的最小值，因此最佳的定長(zhǎng)編碼效率為

可以證明，差錯(cuò)率滿足如下關(guān)系式中，為信源自信息量的方差信息理論與編碼30第4章離散無記憶信源無失真編碼對(duì)于任一正數(shù)，只要就可使信息理論與編碼31第4章離散無記憶信源無失真編碼例2對(duì)上例所給信源的符號(hào)序列進(jìn)行2進(jìn)制編碼，要求編碼效率，允許的差錯(cuò)率為。解已求出信源的熵，自信息量的方差為所以由此可見，要達(dá)到要求的編碼效率，必須取很長(zhǎng)的信源序列（），這在實(shí)際中是很難實(shí)現(xiàn)的。信息理論與編碼32第4章離散無記憶信源無失真編碼4.4變長(zhǎng)編碼定理無失真變長(zhǎng)編碼定理（香農(nóng)第一定理）用r元符號(hào)表對(duì)離散無記憶信源U的N長(zhǎng)符號(hào)序列進(jìn)行變長(zhǎng)編碼，記N長(zhǎng)符號(hào)序列對(duì)應(yīng)的平均碼長(zhǎng)為，那么，要做到無失真編碼，平均碼長(zhǎng)必須滿足信息理論與編碼33第4章離散無記憶信源無失真編碼另一方面，一定存在唯一可譯碼，其平均碼長(zhǎng)滿足

當(dāng)信源序列長(zhǎng)度趨于無窮時(shí)平均碼長(zhǎng)的極限：由此可得編碼效率的極限為信息理論與編碼34第4章離散無記憶信源無失真編碼4.5變長(zhǎng)編碼方法最佳碼對(duì)給定的信源，使平均碼長(zhǎng)達(dá)到最小的編碼方法稱為最佳編碼，編出的碼稱為最佳碼。本節(jié)介紹三種變長(zhǎng)編碼方法：霍夫曼編碼、費(fèi)諾編碼以及香農(nóng)編碼。其中只有霍夫曼編碼是真正意義下的最佳編碼。信息理論與編碼35第4章離散無記憶信源無失真編碼本節(jié)主要內(nèi)容4.5.1霍夫曼編碼4.5.2費(fèi)諾編碼4.5.3香農(nóng)編碼信息理論與編碼36第4章離散無記憶信源無失真編碼4.5.1霍夫曼編碼二進(jìn)制霍夫曼編碼編碼效果分析r進(jìn)制霍夫曼編碼符號(hào)序列的霍夫曼編碼信息理論與編碼37第4章離散無記憶信源無失真編碼二進(jìn)制霍夫曼編碼

二進(jìn)制霍夫曼編碼過程如下：（1）將信源符號(hào)按概率大小排序；（2）對(duì)概率最小的兩個(gè)符號(hào)求其概率之和，同時(shí)給兩符號(hào)分別賦予碼元“0”和“1”；（3）將“概率之和”當(dāng)作一個(gè)新符號(hào)的概率，與剩下符號(hào)的概率一起，形成一個(gè)縮減信源，再重復(fù)上述步驟，直到“概率之和”為1為止；（4）按上述步驟實(shí)際上構(gòu)造了一個(gè)碼樹，從樹根到端點(diǎn)經(jīng)過的樹技即為碼字。

信息理論與編碼38第4章離散無記憶信源無失真編碼符號(hào)概率碼字碼長(zhǎng)1101200130001400001500000160000006霍夫曼編碼步驟示意1

1111

1

0000001.00信息理論與編碼39第4章離散無記憶信源無失真編碼采用霍夫曼編碼方法重新進(jìn)行變長(zhǎng)編碼，其平均碼長(zhǎng)和編碼效率分別為碼元/符號(hào)由此可見，平均碼長(zhǎng)縮短了，達(dá)到了編碼定理所給的下界值，即等于信源的熵，因此編碼效率達(dá)到最大，為100%。信息理論與編碼40第4章離散無記憶信源無失真編碼編碼效果分析（1）有效的信源編碼可取得較好的冗余壓縮效果。原信源的冗余度為經(jīng)過單符號(hào)無失真定長(zhǎng)編碼，新信源X的冗余度為經(jīng)過符號(hào)序列有失真定長(zhǎng)編碼，新信源X的冗余度為信息理論與編碼41第4章離散無記憶信源無失真編碼經(jīng)過單符號(hào)霍夫曼編碼之后，新信源X的冗余度為一般來說，定長(zhǎng)編碼只有在引入失真且取很長(zhǎng)的序列編碼時(shí)，才會(huì)取得一定的冗余壓縮效果，而變長(zhǎng)編碼在無失真的前提下，只須取較短的序列編碼就可取得滿意的冗余壓縮效果。信息理論與編碼42第4章離散無記憶信源無失真編碼（2）有效的信源編碼可使輸出碼元概率均勻化。設(shè)單符號(hào)無失真定長(zhǎng)編碼的碼字為把編碼器的輸出看作一個(gè)新的信源，其取值符號(hào)表就是碼元表X={0,1}，概率空間為現(xiàn)在求X的概率分布。信息理論與編碼43第4章離散無記憶信源無失真編碼設(shè)平均每個(gè)碼字所含碼元“0”和“1”的個(gè)數(shù)為分別為和，根據(jù)上面的等長(zhǎng)碼字可求得碼元/符號(hào)碼元/符號(hào)于是原信源7個(gè)符號(hào)的概率從到，差別很大，編碼之后所得的新信源2個(gè)符號(hào)的概率分別為0.6和0.4，差別縮小，概率得到一定程度的均勻。信息理論與編碼44第4章離散無記憶信源無失真編碼再看霍夫曼編碼，

碼元/符號(hào)碼元/符號(hào)于是此時(shí)，碼元的概率分布完全均勻化了。信息理論與編碼45第4章離散無記憶信源無失真編碼霍夫曼編碼過程中，由于碼元分配的任意性，會(huì)造成碼字不唯一。但平均碼長(zhǎng)是相同的，因而編碼效率是相同的，看下例。例1對(duì)如下DMS進(jìn)行2進(jìn)制霍夫曼編碼。解采用霍夫曼編碼方法，會(huì)出現(xiàn)兩種情況。信息理論與編碼46第4章離散無記憶信源無失真編碼符號(hào)概率碼字碼長(zhǎng)0.35110.300120.2000130.10000140.040000150.00500000160.0050000006霍夫曼編碼之一1

1111

1

0000001.000.010.050.150.350.65信息理論與編碼47第4章離散無記憶信源無失真編碼符號(hào)概率碼字碼長(zhǎng)0.351120.301020.200120.1000130.04000140.0050000150.005000005霍夫曼編碼之二1

1111

1

0000001.000.010.050.150.350.65信息理論與編碼48第4章離散無記憶信源無失真編碼分別求得平均碼長(zhǎng)為碼元/符號(hào)和碼元/符號(hào)兩種情況下，碼字不同，碼長(zhǎng)也不同，但平均碼長(zhǎng)是相同的，因此編碼效率是相同的。信息理論與編碼49第4章離散無記憶信源無失真編碼兩種碼的其它性能還是有差別的。在相同的編碼效率下，我們希望得到碼長(zhǎng)變化小的碼，于是引入碼長(zhǎng)的方差：大，說明碼長(zhǎng)變化大。分別計(jì)算兩種碼的：因此后者的碼較好，其碼長(zhǎng)變化相對(duì)較小。信息理論與編碼50第4章離散無記憶信源無失真編碼r進(jìn)制霍夫曼編碼每次求縮減信源時(shí)，改為求r個(gè)最小概率之和，即將r個(gè)概率最小的符號(hào)縮減為一個(gè)新符號(hào)，直到概率之和為1終止。為保證平均碼長(zhǎng)最小，希望縮減到最后剛好還剩下r個(gè)符號(hào)，為達(dá)到此目的，可給信源添加幾個(gè)無用的符號(hào)，這些無用的符號(hào)概率為零，使得信源符號(hào)數(shù)q滿足其中為信源縮減的次數(shù)。信息理論與編碼51第4章離散無記憶信源無失真編碼符號(hào)概率碼字碼長(zhǎng)0.32210.22110.180220.160120.0800230.0400130.00三元霍夫曼編碼21211

0001.0020.120.46例2信息理論與編碼52第4章離散無記憶信源無失真編碼平均碼長(zhǎng)和編碼效率分別為

碼元/符號(hào)信息理論與編碼53第4章離散無記憶信源無失真編碼符號(hào)序列的霍夫曼編碼一般來說，對(duì)序列編碼比對(duì)單個(gè)符號(hào)編碼更為有效，這與編碼定理的結(jié)論是一致的。例3對(duì)如下DMS進(jìn)行2進(jìn)制霍夫曼編碼，分別對(duì)單個(gè)符號(hào)和二元符號(hào)序列進(jìn)行編碼。信息理論與編碼54第4章離散無記憶信源無失真編碼解

霍夫曼編碼之一（單個(gè)符號(hào)情形）符號(hào)概率碼字碼長(zhǎng)0.45110.350120.200020.551.000011信息理論與編碼55第4章離散無記憶信源無失真編碼可求出平均碼長(zhǎng)：碼元/符號(hào)信源熵為

bit/符號(hào)編碼效率為信息理論與編碼56第4章離散無記憶信源無失真編碼霍夫曼編碼之二（2元符號(hào)序列情形）符號(hào)概率碼字碼長(zhǎng)0.20251120.157501130.157500130.122500030.0910130.09010140.07010040.07100140.04100040.110.160.280.200.37150.59750.40251.000000000011111111信息理論與編碼57第4章離散無記憶信源無失真編碼對(duì)二元符號(hào)序列進(jìn)行編碼相當(dāng)于對(duì)2次擴(kuò)展信源的單個(gè)符號(hào)進(jìn)行編碼，得到二元符號(hào)序列對(duì)應(yīng)的平均碼長(zhǎng)為碼元/二元符號(hào)編碼效率為因此，與單個(gè)符號(hào)編碼相比，對(duì)二元符號(hào)序列編碼的效率更高。信息理論與編碼58第4章離散無記憶信源無失真編碼4.5.2費(fèi)諾編碼費(fèi)諾編碼的步驟費(fèi)諾編碼的基本特點(diǎn)信息理論與編碼59第4章離散無記憶信源無失真編碼費(fèi)諾編碼的步驟（1）將信源符號(hào)按概率從大到小的排序；（2）將信源符號(hào)分成2組，使2組信源符號(hào)的概率之和近似相等，并給2組信源符號(hào)分別賦碼元“0”和“1”；（3）接下來再把各小組的信源符號(hào)細(xì)分為2組并賦碼元，方法與第一次分組相同；（4）如此一直進(jìn)行下去，直到每一小組只含一個(gè)信源符號(hào)為止；（5）由此即可構(gòu)造一個(gè)碼樹，所有終端節(jié)點(diǎn)上的碼字組成費(fèi)諾碼。信息理論與編碼60第4章離散無記憶信源無失真編碼設(shè)DMS

為采用費(fèi)諾編碼方法，用碼元表X={0,1}對(duì)U進(jìn)行編碼。信息理論與編碼61第4章離散無記憶信源無失真編碼符號(hào)概率碼字碼長(zhǎng)0.200020.1901030.1801130.171020.1511030.10111040.0111114費(fèi)諾編碼步驟示意1

1111

1

000000信息理論與編碼62第4章離散無記憶信源無失真編碼可求出費(fèi)諾編碼的平均碼長(zhǎng)和編碼效率碼元/符號(hào)

bit/符號(hào)信息理論與編碼63第4章離散無記憶信源無失真編碼如對(duì)該信源進(jìn)行霍夫曼編碼，碼元/符號(hào)

費(fèi)諾編碼的平均碼長(zhǎng)比霍夫曼編碼略長(zhǎng)，編碼效率稍有下降。因此，費(fèi)諾編碼不是平均碼長(zhǎng)最短意義下的最佳編碼，可將其看作準(zhǔn)最佳編碼。信息理論與編碼64第4章離散無記憶信源無失真編碼費(fèi)諾編碼的基本特點(diǎn)（1）費(fèi)諾編碼在構(gòu)造碼樹時(shí)，是從樹根開始到終端節(jié)點(diǎn)結(jié)束，這與霍夫曼編碼相反；（2）由于賦碼元時(shí)的任意性，因此費(fèi)諾編碼編出的碼字也不唯一；（3）費(fèi)諾編碼雖屬概率匹配范疇，但并未嚴(yán)格遵守匹配規(guī)則，因此平均碼長(zhǎng)一般不會(huì)最小。信息理論與編碼65第4章離散無記憶信源無失真編碼4.5.3香農(nóng)編碼香農(nóng)編碼二進(jìn)制編碼步驟（1）將信源符號(hào)按概率從大到小的排序；（2）按下式求i個(gè)信源符號(hào)對(duì)應(yīng)的碼長(zhǎng)，并取整；（3）按下式求i個(gè)信源符號(hào)的累加概率；（4）將累加概率轉(zhuǎn)換成二進(jìn)制數(shù)；（5）取二進(jìn)制數(shù)小數(shù)點(diǎn)后個(gè)二進(jìn)制數(shù)字作為第i個(gè)信源符號(hào)的碼字。信息理論與編碼66第4章離散無記憶信源無失真編碼例設(shè)信源有7個(gè)符號(hào)，其二進(jìn)制香農(nóng)編碼過程如下。符號(hào)概率累加概率自信息量碼長(zhǎng)碼字0.2002.3430000.190.202.4130010.180.392.4830110.170.572.5631000.150.742.7431010.100.893.34411100.010.996.6671111110表香農(nóng)編碼信息理論與編碼67第4章離散無記憶信源無失真編碼表中信源符號(hào)已按概率大小排序，設(shè)i=3，由于則碼長(zhǎng)滿足取。為了決定碼字，先計(jì)算累加概率：信息理論與編碼68第4章離散無記憶信源無失真編碼將轉(zhuǎn)換成二進(jìn)制數(shù)：取二進(jìn)制數(shù)小數(shù)點(diǎn)后位二進(jìn)制數(shù)作為碼字，即為“011”。計(jì)算出平均碼長(zhǎng)和編碼效率：碼元/符號(hào)比較可知，霍夫曼編碼效率最高，費(fèi)諾編碼效率次之，香農(nóng)編碼效率最低，甚至低于定長(zhǎng)編碼的效率。信息理論與編碼69第4章離散無記憶信源無失真編碼4.6幾種實(shí)用的無失真信源編碼4.6.1游程編碼4.6.2算術(shù)編碼4.6.3基于字典的編碼信息理論與編碼70第4章離散無記憶信源無失真編碼4.6.1游程編碼游程編碼基本原理MH碼MH碼編碼規(guī)則MH碼與霍夫曼碼存在的差異信息理論與編碼71第4章離散無記憶信源無失真編碼游程編碼基本原理

游程編碼是霍夫曼編碼的一種改進(jìn)和應(yīng)用，主要用于黑、白二值文件的傳真。以文本文件的傳真為例，白紙黑字的二值文件采用二元碼進(jìn)行編碼，即表示背景（白色）時(shí)像素為碼元“0”，表示內(nèi)容（黑字）時(shí)像素為碼元“1”。參照國(guó)際標(biāo)準(zhǔn)：一張A4幅面的二值文件共可分1188行，每行有1728個(gè)像素，則整幅總共有2.05M個(gè)像素。分析各類傳真文件可知:任意一個(gè)掃描行的像素序列均是由若干個(gè)連“0”像素序列及若干連“1”像素序列組合而成。對(duì)大量出現(xiàn)的連“0”或連“1”（黑或白）像素序列在傳輸時(shí),可通過像素類別（黑、白像素）加重復(fù)次數(shù)的方式來加以表示，即稱為游程編碼（RLC）。而重復(fù)出現(xiàn)的同類像素的長(zhǎng)度則稱為游程長(zhǎng)度。信息理論與編碼72第4章離散無記憶信源無失真編碼信源的符號(hào)中重復(fù)出現(xiàn)的連“0”或連“1”像素序列經(jīng)游程編碼表示后，可歸一化為統(tǒng)一的編碼單元。其單元結(jié)構(gòu)如下：其中，符號(hào)碼表示當(dāng)前的像素類別是“0”（白底）或“1”（黑字）；標(biāo)識(shí)碼是一種有別于符號(hào)碼的區(qū)分符號(hào)（如#符號(hào)）。例如，若信源的字符序列為其游程編碼的格式表達(dá)為:字符數(shù)量由38個(gè)減少為13個(gè)。符號(hào)碼標(biāo)識(shí)碼游程長(zhǎng)度信息理論與編碼73第4章離散無記憶信源無失真編碼MH碼

MH碼是國(guó)際電話電報(bào)咨詢委員會(huì)提出的文件、傳真類一維數(shù)據(jù)壓縮編碼的國(guó)際標(biāo)準(zhǔn)。

MH碼在編碼中對(duì)游程長(zhǎng)度進(jìn)行分割，并相應(yīng)將長(zhǎng)游程碼（游程長(zhǎng)度>64）分割為結(jié)尾碼（終止碼）和組合碼（形成碼）兩部分，如下頁(yè)表所示。信息理論與編碼74第4章離散無記憶信源無失真編碼RL長(zhǎng)度白游程碼字黑游程碼字RL長(zhǎng)度白游程碼字黑游程碼字RL長(zhǎng)度白游程碼字黑游程碼字0001101010000110111220000011000001101114300101100000011011011100011101023000010000000101000440010110100000101010020111112401010000000001011145000001000000010101013100010250101011000000110004600000101000001010110410110112600100110000110010104700001010000001010111511000011270100100000011001011480000101100000110010061110001028001100000001100110049010100100000011001017111100011290000001000001100110150010100110000010100108100110010130000000110000011010005101010100000001010011910100000100310001101000000110100152010101010000001001001000111000010032000110110000011010105300100100000000110111110100000001013300010010000001101011540010010100000011100012001000000011134000100110000110100105501011000000000100111130000110000010035000101000000110100115601011001000000101000141101000000011136000101010000110101005701011010000001011000151101010000110003700010110000011010101580101101100000101100116101010000001011138000101110000110101105901001010000000101011171010110000011000390010100000001101011160010010110000001011001801001110000001000400010100100000110110061001100100000010110101900011000000110011141001010100000011011016200110011000001100110200001000000011010004200101011000011011010630011010000000110011121001011100001101100表MH碼表(一)結(jié)尾碼信息理論與編碼75第4章離散無記憶信源無失真編碼RL長(zhǎng)度白游程碼字黑游程碼字RL長(zhǎng)度白游程碼字黑游程碼字64110110000001111960011010100000000111001112810010000011001001024011010101000000111010019201011100001100100110880110101100000001110101256011011100000101101111520110101110000001110110320001101100000001100111216011011000000000111011138400110111000000110100128001101100100000010100104480110010000000011010113440110110100000001010011512011001010000001101100140011011011000000101010057601101000000000110110114720100110000000001010101640011001110000001001010153601001100100000010110107040110011000000001001011160001001101000000010110117680110011010000001001100166401100000000011001008320110100100000001001101172801001101100000011001018960110100110000001110010EOL000000000001000000000001表MH碼表（二）組合基干碼信息理論與編碼76第4章離散無記憶信源無失真編碼而對(duì)于加寬的紙型規(guī)定了一套加寬的組合碼，如下表所示。游程長(zhǎng)度組合基干碼碼字游程長(zhǎng)度組合基干碼碼字1792000000010002240000000010110185600000001100230400000001011119200000000110123680000000111001984000000010010243200000001110120480000000100112496000000011110211200000001010025600000000111112176000000010101

MH碼表（三）供加大紙寬用的組合基干碼（1792～2560，黑、白相同）信息理論與編碼77第4章離散無記憶信源無失真編碼MH編碼規(guī)則（1）游程長(zhǎng)度在0~63之間時(shí)，碼字直接由相應(yīng)的終止碼表示；（2）游程長(zhǎng)度在64~1728之間時(shí)，碼字由一個(gè)組合碼加上一個(gè)終端碼構(gòu)成；（3）每行必須以白游程開始，以一個(gè)同步碼EOL結(jié)束，且每頁(yè)文件也必須以同步碼EOL開始（用以清洗系統(tǒng)，防止誤差擴(kuò)散）；（4）每行游程總和必須為1728個(gè)像素，否則該行出錯(cuò)；（5）為達(dá)成同步操作，每行編碼的傳輸時(shí)間最短為20mS,最長(zhǎng)為5s；不足20ms的行,需在EOL碼之前填入足夠的“0”碼元；（6）連續(xù)6個(gè)EOL表示文件頁(yè)傳輸?shù)慕Y(jié)束。信息理論與編碼78第4章離散無記憶信源無失真編碼例若傳真文件某行的掃描像素序列如表所示白游程22，黑游程6，白游程53，黑游程22均可查表直接獲得編碼。黑游程66和白游程1559則需采用組合碼與終端碼進(jìn)行合成編碼。其中，黑游程66的編碼由長(zhǎng)度為64的黑游程組合碼與長(zhǎng)度為2的黑游程終端碼共同構(gòu)成，碼字為000000111111。白游程1559的編碼由長(zhǎng)度為1536的白游程組合碼與長(zhǎng)度為23的白游程終端碼組成，碼字為0100110010000100。白游程黑游程白游程黑游程白游程黑游程

2265366155922EOL00000110010001001000000001111101001100100001000000011000000000001信息理論與編碼79第4章離散無記憶信源無失真編碼MH碼與霍夫曼碼存在的差異（1）MH碼的編碼表是由各類文件的平均統(tǒng)計(jì)特性指標(biāo)得到的，并且固定不變，因而多數(shù)情況下，MH碼并非緊制碼（最佳碼）。（2）游程的碼字由形成碼和中止碼組成，可使碼字大大縮短。信息理論與編碼80第4章離散無記憶信源無失真編碼4.6.2算術(shù)編碼編碼過程

將各信源符號(hào)序列依累積概率分布函數(shù)的大小映射到[0,1)區(qū)間，將[0,1)區(qū)間分成許多互不重疊的小區(qū)間。此時(shí)每個(gè)符號(hào)序列均有一個(gè)小區(qū)間與之對(duì)應(yīng)，因而可在小區(qū)間內(nèi)取點(diǎn)來代表該符號(hào)序列。為達(dá)到與信源符號(hào)序列在概率上的匹配，選取編碼的碼長(zhǎng)與信源序列的概率成反比，即取碼長(zhǎng)l為其中:表示信源符號(hào)序列的概率，符號(hào)表示取大于或等于該值的最小整數(shù)。信息理論與編碼81第4章離散無記憶信源無失真編碼例設(shè)一信源符號(hào)集為，若各信源符號(hào)相互統(tǒng)計(jì)獨(dú)立,則信源符號(hào)序列的概率為，現(xiàn)對(duì)信源符號(hào)序列進(jìn)行算術(shù)編碼。定義信源符號(hào)的累積概率分布函數(shù)為信息理論與編碼82第4章離散無記憶信源無失真編碼現(xiàn)輸入信源符號(hào)序列，則即:信源符號(hào)集的累積概率分布函數(shù)將區(qū)間分割為與信源序列相對(duì)應(yīng)的四個(gè)大區(qū)間。序列首個(gè)信源符號(hào)確定本序列的相應(yīng)區(qū)間，后續(xù)信源符號(hào)則是對(duì)選定區(qū)間的再分割。信息理論與編碼83第4章離散無記憶信源無失真編碼計(jì)算分割過程如下：（1）信源符號(hào)輸入，序列對(duì)應(yīng)區(qū)間為區(qū)間，且，。（2）符號(hào)輸入，確定相應(yīng)區(qū)間為區(qū)間。序列的累積概率分布函數(shù)值序列的概率序列相應(yīng)區(qū)間長(zhǎng)度信息理論與編碼84第4章離散無記憶信源無失真編碼（3）符號(hào)輸入，確定相應(yīng)區(qū)間為區(qū)間。序列的累積概率分布函數(shù)序列的概率序列相應(yīng)區(qū)間長(zhǎng)度（4）經(jīng)符號(hào)輸入引起再一次分割，得到全序列的累積概率分布函數(shù)及其對(duì)應(yīng)的區(qū)間，且此時(shí)序列累積概率分布函數(shù)

序列的概率序列相應(yīng)區(qū)間長(zhǎng)度信息理論與編碼85第4章離散無記憶信源無失真編碼A(u1)=p(u1)A(u2)=p(u2)A(u3)=p(u3)F(u1)F(u2)F(u3)F(u4)A(u4)=p(u4)1F(u1u1)F(u1u2)F(u1u3)F(u1u4)A(u1u2)=A(u1)p(u1)A(u1)p(u2)A(u1)p(u3)A(u1)p(u4)A(u1u2)p(u3)A(u1u1)p(u4)F(u1u2u2)F(u1u2u3)F(u1u2u4)A(u1u2)p(u1)A(u1u2)p(u2)F(u1u2u1)F(u1u2u4u4)A(u1u2u4)p(u3)A(u1u2u4)p(u4)F(u1u2u4u2)F(u1u2u4u3)A(u1u2u4)p(u1)A(u1u2u4)p(u2)F(u1u2u4u1)算術(shù)編碼過程圖信息理論與編碼86第4章離散無記憶信源無失真編碼將結(jié)論推廣到任意序列，則可得通用的遞推計(jì)算公式為

采用遞推公式進(jìn)行映射和計(jì)