信息理論與編碼4

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

——信源符號集合；

——碼元組成的集合；

——信道能夠傳送的符號，稱為碼元；

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

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

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

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

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

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

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

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

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

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

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

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

的碼樹；（b）W4

的碼樹；（c）W5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1111

1

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

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

1111

1

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

1111

1

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

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

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

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

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

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

1111

1

000000信息理論與編碼62第4章離散無記憶信源無失真編碼可求出費諾編碼的平均碼長和編碼效率碼元/符號

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

費諾編碼的平均碼長比霍夫曼編碼略長，編碼效率稍有下降。因此，費諾編碼不是平均碼長最短意義下的最佳編碼，可將其看作準(zhǔn)最佳編碼。信息理論與編碼64第4章離散無記憶信源無失真編碼費諾編碼的基本特點（1）費諾編碼在構(gòu)造碼樹時，是從樹根開始到終端節(jié)點結(jié)束，這與霍夫曼編碼相反；（2）由于賦碼元時的任意性，因此費諾編碼編出的碼字也不唯一；（3）費諾編碼雖屬概率匹配范疇，但并未嚴(yán)格遵守匹配規(guī)則，因此平均碼長一般不會最小。信息理論與編碼65第4章離散無記憶信源無失真編碼4.5.3香農(nóng)編碼香農(nóng)編碼二進(jìn)制編碼步驟（1）將信源符號按概率從大到小的排序；（2）按下式求i個信源符號對應(yīng)的碼長，并取整；（3）按下式求i個信源符號的累加概率；（4）將累加概率轉(zhuǎn)換成二進(jìn)制數(shù)；（5）取二進(jìn)制數(shù)小數(shù)點后個二進(jìn)制數(shù)字作為第i個信源符號的碼字。信息理論與編碼66第4章離散無記憶信源無失真編碼例設(shè)信源有7個符號，其二進(jìn)制香農(nó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章離散無記憶信源無失真編碼表中信源符號已按概率大小排序，設(shè)i=3，由于則碼長滿足取。為了決定碼字，先計算累加概率：信息理論與編碼68第4章離散無記憶信源無失真編碼將轉(zhuǎn)換成二進(jìn)制數(shù)：取二進(jìn)制數(shù)小數(shù)點后位二進(jìn)制數(shù)作為碼字，即為“011”。計算出平均碼長和編碼效率：碼元/符號比較可知，霍夫曼編碼效率最高，費諾編碼效率次之，香農(nóng)編碼效率最低，甚至低于定長編碼的效率。信息理論與編碼69第4章離散無記憶信源無失真編碼4.6幾種實用的無失真信源編碼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)行編碼，即表示背景（白色）時像素為碼元“0”，表示內(nèi)容（黑字）時像素為碼元“1”。參照國際標(biāo)準(zhǔn)：一張A4幅面的二值文件共可分1188行，每行有1728個像素，則整幅總共有2.05M個像素。分析各類傳真文件可知:任意一個掃描行的像素序列均是由若干個連“0”像素序列及若干連“1”像素序列組合而成。對大量出現(xiàn)的連“0”或連“1”（黑或白）像素序列在傳輸時,可通過像素類別（黑、白像素）加重復(fù)次數(shù)的方式來加以表示，即稱為游程編碼（RLC）。而重復(fù)出現(xiàn)的同類像素的長度則稱為游程長度。信息理論與編碼72第4章離散無記憶信源無失真編碼信源的符號中重復(fù)出現(xiàn)的連“0”或連“1”像素序列經(jīng)游程編碼表示后，可歸一化為統(tǒng)一的編碼單元。其單元結(jié)構(gòu)如下：其中，符號碼表示當(dāng)前的像素類別是“0”（白底）或“1”（黑字）；標(biāo)識碼是一種有別于符號碼的區(qū)分符號（如#符號）。例如，若信源的字符序列為其游程編碼的格式表達(dá)為:字符數(shù)量由38個減少為13個。符號碼標(biāo)識碼游程長度信息理論與編碼73第4章離散無記憶信源無失真編碼MH碼

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

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

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

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

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

序列的概率序列相應(yīng)區(qū)間長度信息理論與編碼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ìn)行映射和計