第五章信源編碼5.1.1碼字唯一可譯的條件5.1.2香農(nóng)編碼5.1.3費(fèi)諾編碼5.1.4赫夫曼編碼5.1.5游程編碼5.1.6冗余位編碼1信源編碼概述編碼是為了優(yōu)化通信系統(tǒng)，一般的通信系統(tǒng)的主要性能指標(biāo)：有效性、可靠性和安全性信源編碼的目的：提高通信系統(tǒng)的有效性，通常通過壓縮信源的冗余度來實(shí)現(xiàn)，即壓縮每個(gè)信源符號(hào)的信息量，使得同樣多的信息用較少的信息傳輸率來傳送信源編碼的思路：根據(jù)信源輸出符號(hào)序列的統(tǒng)計(jì)特性，尋找一定的把信源輸出符號(hào)序列變換為最短碼字序列的方法信源編碼的基本途徑：使編碼后的符號(hào)序列中的各個(gè)符號(hào)盡可能地相互獨(dú)立，即解除相關(guān)性；使編碼后各個(gè)符號(hào)出現(xiàn)的概率盡可能的相等，即概率均勻化。信源編碼的基礎(chǔ)：無失真編碼定理和限失真編碼定理25.1離散信源

5.1.1碼字唯一可譯的條件碼的分類按碼長(zhǎng)分類定長(zhǎng)碼：碼中所有碼字的碼長(zhǎng)都相等奇異碼：碼中存在有相同的碼字(對(duì)應(yīng)不同的信源符號(hào))唯一可譯碼：由碼的碼字組成任意有限長(zhǎng)的碼字序列只能被唯一地譯為對(duì)應(yīng)的信源符號(hào)序列即時(shí)碼：譯碼器收到一個(gè)完整的唯一可譯碼字以后，無需參考后續(xù)的碼字(碼元)就能立即譯碼定長(zhǎng)碼非奇異碼唯一可譯碼35.1.1碼字唯一可譯的條件1001001碼C11100100碼B11100000碼A0.100.150.250.50概率信源碼F碼E碼D0011001101100111001111111000碼A：奇異碼、定長(zhǎng)碼、非唯一可譯碼碼B：非奇異碼、定長(zhǎng)碼、唯一可譯碼碼C：非奇異碼、非唯一可譯碼碼D：唯一可譯碼碼E：非即時(shí)碼碼F：即時(shí)碼即時(shí)碼中任何一個(gè)碼字均不是其它碼字的前綴變長(zhǎng)碼即時(shí)碼唯一可譯碼4定義：如果一個(gè)碼組中的任一個(gè)碼字都不是另一個(gè)碼字的延長(zhǎng)或者找不到任何一個(gè)碼字是另一個(gè)碼字的前綴，或者說，任何一個(gè)碼字后加上若干碼元后都不是碼組中另一個(gè)碼字，則稱為即時(shí)碼或非延長(zhǎng)碼。也叫前綴條件碼/異前置碼/異字頭碼/逗點(diǎn)碼所有的碼非奇異碼唯一可譯碼即時(shí)碼5.1.1碼字唯一可譯的條件55.1.1碼字唯一可譯的條件用樹圖法可以方便地構(gòu)造即時(shí)碼。從樹根開始，樹中每個(gè)中間節(jié)點(diǎn)都伸出1至r

個(gè)樹枝，不同的樹枝標(biāo)記不同的碼元。將所有的碼字都安排在終端節(jié)點(diǎn)上就可以得到即時(shí)碼每個(gè)中間節(jié)點(diǎn)都正好有r

個(gè)分枝的樹稱為整樹(滿樹)所有終端節(jié)點(diǎn)的階數(shù)都相等的樹為完全樹，對(duì)應(yīng)于定長(zhǎng)碼65.1.1碼字唯一可譯的條件二元滿樹二元非滿樹三元非滿樹三元滿樹7唯一可譯定長(zhǎng)碼存在的條件對(duì)于定長(zhǎng)碼，非奇異碼一定是唯一可譯碼注意：上述條件是唯一可譯定長(zhǎng)碼存在的必要條件， 而非充分條件平均每個(gè)單信源符號(hào)所需要碼元的個(gè)數(shù)8克拉夫特(Kraft)不等式9唯一可譯碼判別準(zhǔn)則10唯一可譯碼判別準(zhǔn)則—舉例設(shè)信源消息集合{x1,x2,x3,x4,x5,x6,x7}，它們分別被編碼為{a,c,ad,abb,bad,deb,bbcde}，可構(gòu)造出下表所示的嗎符號(hào)集序列S0S1S2S3S4S5S6S7adebdebaddebcbbcdebcdeadabbbaddebbbcde當(dāng)n＞7時(shí)，sn是空集，而s5都包含s0中的元素，因此不是唯一可譯碼115.1.2香農(nóng)編碼香農(nóng)編碼是采用信源符號(hào)的累計(jì)概率分布函數(shù)來分配碼字的設(shè)某離散無記憶信源

2進(jìn)制香農(nóng)編碼步驟：將信源符號(hào)以概率遞減的次序排列起來，為方便起見，令：按下式求x

i

對(duì)應(yīng)碼字的碼長(zhǎng)l

i

：按下式逐步求信源符號(hào)x

i

的概率累加和P

i

：將所有的累加和概率

P

i

變換成

2

進(jìn)制數(shù)；取小數(shù)點(diǎn)后

P

i

位作為信源符號(hào)

x

i

的

2

進(jìn)制碼字12編碼所得的碼字，沒有相同的，所以是非奇異碼，也沒有一個(gè)碼字是其它碼字的前綴，所以是即時(shí)碼。香農(nóng)碼的效率不高，其冗余度較大，不是最佳碼，實(shí)用性受到較大限制xip

(

xi

)Pi-log

p

(

xi

)li碼字x10.3701.434200x20.160.372.6443010x30.140.582.8373100x40.130.672.9433101x50.070.803.83741100x60.060.874.059511011x70.040.934.644511101x80.030.975.059611111013例：有一單符號(hào)離散無記憶信源練習(xí)二進(jìn)制香農(nóng)編碼

xi

p(xi)

pa(xj)

ki

碼字

x1

0.25

0.000

2

00(0.000)2

x2

0.25

0.250

2

01(0.010)2

x3

0.20

0.500

3

100(0.100)2

x4

0.15

0.700

3

101(0.101)2

x5

0.10

0.850

4

1101(0.1101)2

x6

0.05

0.950

5

11110(0.11110)2

對(duì)該信源編二進(jìn)制香農(nóng)碼。其編碼過程如下表所示。145.1.3

費(fèi)諾編碼費(fèi)諾編碼又稱為子集分解法，通過將信源符號(hào)的概率分組，對(duì)每個(gè)組分配相應(yīng)的碼元來實(shí)現(xiàn)編碼，其編碼步驟如下：將信源符號(hào)以概率遞減的次序排列起來，為方便起見，令:將依次排列的信源符號(hào)按概率分成r組，使每個(gè)組的信源符號(hào)的概率和盡可能接近或相等，然后賦予每組一個(gè)r元碼符號(hào)；例如編

2

進(jìn)制費(fèi)諾碼，則每次分組均分成兩組，每個(gè)組分別賦予一個(gè)2元碼符號(hào)“0”或“1”將每一大組的信源符號(hào)按概率和遞減的次序再分成r組，使同一大組細(xì)分的r

個(gè)小組的信源符號(hào)的概率和盡可能接近或相等，并分別賦予每小組一個(gè)r元碼符號(hào)；重復(fù)上述的分組，分配r

元碼符號(hào)的過程，直至最個(gè)分得的每個(gè)小組只剩一個(gè)信源符號(hào)為止，最后每個(gè)信源符號(hào)所對(duì)應(yīng)的碼元序列就是相應(yīng)的碼字15xip

(

xi

)費(fèi)諾編碼碼字lix10.3700002x20.161012x30.141001003x40.1311013x50.0710011004x60.06111014x70.041011104x80.0311111416費(fèi)諾編碼的碼樹圖實(shí)質(zhì)上是一種構(gòu)造碼樹的方法，所以費(fèi)諾碼是即時(shí)碼概率大，則分解的次數(shù)小；概率小,則分解的次數(shù)多碼字集合是唯一的分解完后，碼字與碼長(zhǎng)便確定了費(fèi)諾碼考慮了信源的統(tǒng)計(jì)特性，使經(jīng)常出現(xiàn)的信源符號(hào)對(duì)應(yīng)短碼字，但是不一定能使短碼得到充分利用，尤其當(dāng)信源符號(hào)較多時(shí)，若有一些符號(hào)概率分布很接近時(shí)，分兩大組的組合方法就會(huì)很多。可能某種分大組的結(jié)果，會(huì)使后面小組的“概率和”相差較遠(yuǎn)，從而使平均碼長(zhǎng)增加。費(fèi)諾編碼特點(diǎn)17xip

(

xi

)費(fèi)諾編碼碼字lix10.2500002x20.251012x30.1251001003x40.12511013x50.062510011004x60.0625111014x70.06251011104x80.0625111114費(fèi)諾碼適合于每次分組概率都很接近的信源。特別是對(duì)每次分組概率都相等的信源進(jìn)行編碼時(shí)，可達(dá)到理想的編碼效率費(fèi)諾碼考慮了信源的統(tǒng)計(jì)特性，使概率大的信源符號(hào)能對(duì)應(yīng)碼長(zhǎng)短的碼字，從而有效地提高了編碼效率。一般而言，費(fèi)諾編碼不是最佳編碼，它的編碼效率(優(yōu)于香農(nóng)碼)要比赫夫曼編碼效率稍低18例：設(shè)有一單符號(hào)離散信源對(duì)該信源編二進(jìn)制費(fèi)諾碼。練習(xí)195.1.4赫夫曼編碼赫夫曼編碼是一種最佳的逐個(gè)符號(hào)的編碼方法，所得的碼是即時(shí)碼，其平均碼長(zhǎng)最短，因而是最佳編碼2進(jìn)制赫夫曼編碼的步驟如下：將信源符號(hào)以概率遞減的次序排列起來，為方便起見，令:將兩個(gè)概率最小的信源符號(hào)

x

n

-1,x

n

各分配一個(gè)碼元“0”和“1”，并將這兩個(gè)符號(hào)合并成一個(gè)新符號(hào)，合并后新符號(hào)概率為原來兩個(gè)符號(hào)概率之和，從而得到包含

n

-

1

個(gè)符號(hào)的縮減信源

S1

把縮減信源

S1

的符號(hào)仍按概率遞減次序排列，重復(fù)步驟

2

得到只含有n

-

2個(gè)信源符號(hào)的縮減信源

S2

重復(fù)上述步驟，直至縮減信源只剩

1

個(gè)信源符號(hào)為止；然后從最后一級(jí)縮減信源開始，依編碼路徑向前返回，就得到各信源符號(hào)所對(duì)應(yīng)的碼元序列，即對(duì)應(yīng)的碼字20xip(xi)縮減信源碼字liS1S2S3S4S5S6S7x10.37x20.16x30.14x40.13x50.07x60.06x70.04x80.030.0701010.130.200.270.360.631.0010101010121赫夫曼編碼的碼樹赫夫曼編碼的特點(diǎn)概率大的符號(hào)安排在離根節(jié)點(diǎn)較近的終端節(jié)點(diǎn)保證了概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)碼每次縮減信源的最長(zhǎng)兩個(gè)碼字具有相同碼長(zhǎng)每次縮減信源的最后兩個(gè)碼字總是最后一位碼元不同，前面各位碼元相同(2元碼情況)編碼不具有惟一性赫夫曼編碼是最佳碼22方差越小，各碼字長(zhǎng)度就越接近平均碼長(zhǎng)，設(shè)計(jì)的編碼器也就越簡(jiǎn)單赫夫曼編碼的非唯一性每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配“0”或“1”碼元是任意的，所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性，即能得到可分離碼字不同的碼元分配，得到的具體碼字不同，但碼長(zhǎng)

li

不變，平均碼長(zhǎng)也不變，所以沒有本質(zhì)區(qū)別縮減信源時(shí)，若合并后新符號(hào)的概率與其它符號(hào)概率相等，從編碼方法上來說，這幾個(gè)符號(hào)的次序可任意排列，編出的碼都是正確的，但得到的碼字不相同。不同的編法得到的碼字長(zhǎng)度

li

也不盡相同，但平均碼長(zhǎng)仍不變對(duì)同一信源的多種赫夫曼編碼，除了用平均碼長(zhǎng)來衡量外，當(dāng)平均碼長(zhǎng)相同時(shí)，可以碼長(zhǎng)

li

偏離平均碼長(zhǎng)的方差來判斷：23xip(xi)編碼過程碼字lix10.37x20.16x30.14x40.13x50.07x60.06x70.04x80.03方案一24xip(xi)縮碼過程碼字lix10.37x20.16x30.14x40.13x50.07x60.06x70.04x80.03方案二25赫夫曼編碼的非唯一性（續(xù)）xip(xi)碼長(zhǎng)li方案一方案二x10.3711x20.1633x30.1433x40.1343x50.0744x60.0645x70.0456x80.0356平均碼長(zhǎng)方案一較好，其碼長(zhǎng)變化較小在赫夫曼編碼過程中，當(dāng)縮減信源符號(hào)按概率大小，以遞減次序自上而下重新排列時(shí)，應(yīng)把合并后的新符號(hào)盡量置于縮減信源中具有相同概率的其它符號(hào)之上，減少合并后的新符號(hào)被重復(fù)賦予碼元的次數(shù)，進(jìn)而減小碼字長(zhǎng)度相對(duì)于平均碼長(zhǎng)的擺動(dòng)上述方法不會(huì)引起平均碼長(zhǎng)的變化，可以使短碼得到充分利用26r

進(jìn)制赫夫曼編碼r

進(jìn)制赫夫曼編碼是

2

進(jìn)制編碼的推廣；求縮減信源時(shí)需要求

r

個(gè)信源符號(hào)使其概率和最小，并對(duì)

r

個(gè)信源符號(hào)分別分配碼元0,1,

,

r

-

1，然后將它們縮減為一個(gè)新符號(hào)，重復(fù)上述縮減和分配碼元的步驟直至縮減信源中只剩下一個(gè)符號(hào)為止r

進(jìn)制霍夫曼編碼，如果從一始就每

r

個(gè)符號(hào)縮減為一個(gè)新符號(hào)，則縮減到最后時(shí)剩下的信源符號(hào)可能不到

r

個(gè)，為了使平均碼長(zhǎng)最短，必須使最后一步縮減信源有

r

個(gè)信源符號(hào)全樹非全樹碼樹圖中至少有一個(gè)中間節(jié)點(diǎn)的后續(xù)枝數(shù)不足r碼樹圖中每個(gè)中間節(jié)點(diǎn)后續(xù)枝數(shù)為

r2

進(jìn)制碼不存在非全樹的情況，因?yàn)楹罄m(xù)枝數(shù)是1時(shí)，這個(gè)枝就可以去掉使碼字長(zhǎng)度縮短27r

進(jìn)制赫夫曼編碼(續(xù))對(duì)r進(jìn)制編碼，若所有碼字構(gòu)成全樹，可分離的碼字?jǐn)?shù)必為：k為信源縮減次數(shù)-1若信源所含的符號(hào)數(shù)n不能構(gòu)成r進(jìn)制全樹，必須增加s

個(gè)不用的碼字形成全樹，且

s

<r

-

1若

s

=r

-

1，意味著某個(gè)中間節(jié)點(diǎn)之后只有一個(gè)分枝，為了節(jié)約碼長(zhǎng)，這一分枝可以省略為了使平均碼長(zhǎng)最短，當(dāng)碼樹為非全樹時(shí)，有s

個(gè)碼字不用：第一次對(duì)最小概率和的符號(hào)分配碼元時(shí)只取

r

-

s

個(gè)，分別賦予碼元

0,1,

,

r

-

s

-

1，把這些符號(hào)的概率相加作為一個(gè)新符號(hào)的概率，與其它符號(hào)一起重新排列以后每次就可以取

r

個(gè)符號(hào)，分別賦予碼元

0,1,

,

r

-

1；如此下去直至縮減至

1

個(gè)信源符號(hào)，得到各符號(hào)的

r

進(jìn)制碼字28可見，要發(fā)揮赫夫曼編碼的優(yōu)勢(shì)，一般情況下，信源符號(hào)集的符號(hào)數(shù)應(yīng)遠(yuǎn)大于碼元數(shù)xip(xi)3

進(jìn)制赫夫曼縮碼過程碼字lix10.37x20.16x30.14x40.13x50.07x60.06x70.04x80.03xip(xi)4

進(jìn)制赫夫曼縮碼過程碼字lix10.37x20.16x30.14x40.13x50.07x60.06x70.04x80.0329練習(xí)設(shè)單符號(hào)離散無記憶信源如下，要求對(duì)信源編二進(jìn)制霍夫曼碼。在圖中讀取碼字的時(shí)候，一定要從后向前讀，此時(shí)編出來的碼字才是可分離的異前置碼。若從前向后讀取碼字，則碼字不可分離。30香農(nóng)碼、費(fèi)諾碼和

赫夫曼碼總結(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)碼編碼結(jié)果唯一，但在很多情況下編碼效率不是很高費(fèi)諾碼和赫夫曼碼的編碼方法都不唯一費(fèi)諾碼比較適合于對(duì)分組概率相等或接近的信源編碼赫夫曼碼對(duì)信源的統(tǒng)計(jì)特性沒有特殊要求，編碼效率比較高，對(duì)編碼設(shè)備的要求也比較簡(jiǎn)單，因此綜合性能優(yōu)于香農(nóng)碼和費(fèi)諾碼赫夫曼碼通常適用于多元信源，對(duì)于二元信源，必須采用合并符號(hào)的方法，才能得到較高的編碼效率315.1.5游程編碼概述香農(nóng)碼、費(fèi)諾碼、赫夫曼碼主要是針對(duì)無記憶信源；當(dāng)信源有記憶時(shí)上述編碼的效率不高游程編碼是一種對(duì)相關(guān)信源較為有效的擴(kuò)展符號(hào)集的編碼方法，是赫夫曼編碼的改進(jìn)和應(yīng)用，主要用于只有黑、白二值灰度的文件傳真，如文件、報(bào)紙、表格、手寫體字、圖紙等文件傳真是把一頁文件掃描為

n

m

個(gè)像素。由于黑、白二值文件只有兩個(gè)灰度值，因此采用2進(jìn)制編碼。如果每一個(gè)像素用一位二進(jìn)制碼(0：白色，1：黑色)表示，顯然一頁文件的碼元數(shù)就等于該頁文件的像素?cái)?shù)例如，參照國(guó)際標(biāo)準(zhǔn)，一張

A4

幅面(210

mm

297

mm)的二值文件掃描的辨率為：1728像素/行，4行/mm即一幅

A4

頁面共可分為

1188

行，每行

1728

像素。整幅共有

2.05

M

個(gè)像素，若用

4800

bit/s

的信息傳輸率進(jìn)行傳輸約需7.2分鐘，直接傳真將需耗費(fèi)大量的通信時(shí)間32游程編碼概述(續(xù))統(tǒng)計(jì)表明，此類傳真文件黑白兩個(gè)灰度值出現(xiàn)的概率為：顯然一個(gè)像素用一位二進(jìn)制編碼，會(huì)有很大冗余度，要提高傳真效率，必須去除冗余對(duì)于二值灰度的文件，每一掃描行均是由若干個(gè)連白(0)像素序列及若干個(gè)連黑(1)像素序列組合而成，且同類像素連續(xù)出現(xiàn)的概率很大，因此可通過像素類別(黑或白)加重復(fù)次數(shù)來表示，由此思想構(gòu)成的編碼稱為游程編碼重復(fù)出現(xiàn)的同類像素的長(zhǎng)度稱為游程長(zhǎng)度；白(0)像素序列稱為白(0)游程，黑(1)像素序列稱為黑(1)游程33游程編碼概述(續(xù))游程編碼的基本結(jié)構(gòu)是編碼單元：符號(hào)碼標(biāo)識(shí)碼游程長(zhǎng)度像素序列：白白黑黑黑黑白白白白白白黑黑黑游程編碼：白#2黑#4白#6黑#3實(shí)際上，每一掃描行的白像素序列和黑像素序列是交替出現(xiàn)的，若規(guī)定第一游程為白游程(若第一游程為黑游程，則在黑游程前插入一個(gè)游程長(zhǎng)度為

0

的白游程)，則可將編碼中的“符號(hào)碼”和“標(biāo)識(shí)碼”均省略，這樣就可把像素序列變換為游程長(zhǎng)度序列，且二者是可逆的。例如：像素類別：“白”(0)“黑”(1)符號(hào)碼和游程長(zhǎng)度之間的分割符游程長(zhǎng)度序列：45287613321黑白像素序列：00001111100111111110000000111111011100011045287613321游程長(zhǎng)度是隨機(jī)的，取值為1,2,

直至無窮一一對(duì)應(yīng)的可逆變換34游程：數(shù)字序列中連續(xù)出現(xiàn)相同符號(hào)的一段二元序列的游程：只有“0”和“1”兩種符號(hào)連“0”這一段稱為“0”游程，游程長(zhǎng)度：L(0)連“1”這一段稱為“1”游程，游程長(zhǎng)度：L(1)在二元序列中，“0”游程和“1”游程總是交替出現(xiàn)的游程變換將二元序列變換成了多元序列，減弱了原序列符號(hào)間的相關(guān)性，這樣就適合于用其它方法，如赫夫曼編碼，進(jìn)一步壓縮信源，提高通信效率r

元序列同樣也可以變換游程長(zhǎng)度序列，但是

r

元序列，總共有

r

種游程，為能保證一一對(duì)應(yīng)的可逆變換性，必須再加一些分隔標(biāo)志符號(hào)，才能區(qū)分游程長(zhǎng)度序列中的某一個(gè)長(zhǎng)度是

r

種游程中的哪一個(gè)長(zhǎng)度；增加分隔標(biāo)志符號(hào)可能會(huì)抵消壓縮編碼得到的好處，故一般不對(duì)多元序列進(jìn)行游程編碼游程編碼的方法：首先測(cè)定“0”游程長(zhǎng)度和“1”游程長(zhǎng)度的概率分布，即以游程長(zhǎng)度為元素，構(gòu)造一個(gè)新的信源對(duì)新的信源(游程長(zhǎng)度序列)進(jìn)行赫夫曼編碼游程編碼一般規(guī)定二元序列總是從“0”開始35二元獨(dú)立序列的游程長(zhǎng)度序列注：在計(jì)算

p[

L(

0

)]

時(shí)第一個(gè)信源符號(hào)必然是“0”，否則就不是“0”游程，若下一個(gè)符號(hào)是“1”，則游程長(zhǎng)度為

1，其概率是

p1

=

1

-

p0；若下一個(gè)符號(hào)為“0”、再下一個(gè)符號(hào)為“1”，則游程長(zhǎng)度為

2，其概率為

p0

p1；依此類推同理可得：若二元獨(dú)立序列的概率特性已知，由于二元獨(dú)立序列與游程長(zhǎng)度序列的一一對(duì)應(yīng)性，可計(jì)算出游程長(zhǎng)度序列的概率特性設(shè)二元獨(dú)立序列中符號(hào)“0”和“1”出現(xiàn)的概率分別為

p0

和p1

，則“0”游程長(zhǎng)度L(0)的概率為：36“0”游程長(zhǎng)度序列的熵：“1”游程長(zhǎng)度序列的熵：同理可得：

37“0”游程的平均長(zhǎng)度：“1”游程的平均長(zhǎng)度：同理可得二元獨(dú)立序列的熵：“0”游程長(zhǎng)度序列的熵與“1”游程長(zhǎng)度序列的熵之和除以它們的平均游程長(zhǎng)度之和，即為對(duì)應(yīng)的原二元獨(dú)立序列的熵H

(

X

)游程變換后符號(hào)熵保持不變。因?yàn)橛纬套儞Q是一一對(duì)應(yīng)的可逆變換38游程編碼的編碼效率根據(jù)編碼效率的定義和前述分析可得二元序列的編碼效率：假設(shè)h0

>h1，易知：h0

>h

>h1當(dāng)“0”游程和“1”游程的編碼效率都很高時(shí)，采用游程編碼的整體編碼效率也很高，至少不會(huì)低于較小的那個(gè)游程的編碼效率要想游程的整體編碼效率盡可能高，應(yīng)盡可能提高熵值較大的游程的編碼效率假設(shè)“0”游程長(zhǎng)度和“1”游程長(zhǎng)度的赫夫曼編碼效率分別為h1,h2，即：39游程編碼的截?cái)嗵幚肀M管游程長(zhǎng)度可以從

1

一直到無窮長(zhǎng)，但建立游程長(zhǎng)度與赫夫曼碼字之間的一一對(duì)應(yīng)碼表將是非常困難游程越長(zhǎng)，其出現(xiàn)的概率就越小，所以：

由赫夫曼碼的編碼規(guī)則，概率越小，碼字越長(zhǎng)；但小概率對(duì)應(yīng)的長(zhǎng)碼字對(duì)平均碼長(zhǎng)影響很小，故對(duì)較長(zhǎng)的二元序列，游程編碼一般需采用截?cái)嗵幚?，以下為一種截?cái)嗵幚矸椒ㄟx取適當(dāng)?shù)?/p>

n

值，將游程長(zhǎng)度分別為的游程進(jìn)行赫夫曼編碼，得到相應(yīng)的碼表所有游程長(zhǎng)度大于等于的游程，將其編碼為多個(gè)固定的碼字

C

串接游程長(zhǎng)度減去所得余數(shù)的二進(jìn)制表示，具體為：游程長(zhǎng)度：，則游程編碼為

CA，其中

A

為游程長(zhǎng)度減去

所得余數(shù)補(bǔ)足為

n

位的二進(jìn)制表示，游程長(zhǎng)度：

，則游程編碼為

C00

0CA，其中A

為游程長(zhǎng)度減去所得余數(shù)的二進(jìn)制表示，依此類推n個(gè)40游程編碼的截?cái)嗵幚?續(xù))例如：如選擇

n

=

8，則可用

255

個(gè)碼字構(gòu)成的赫夫曼碼表對(duì)應(yīng)于游程長(zhǎng)度不超過

255

的游程；如用

C

表示所有游程長(zhǎng)度超過255

的游程對(duì)應(yīng)的碼字的前半部分，則：游程長(zhǎng)度編碼260C00000100516C00000000C00000100772C00000000C000000000C00000100“0”游程和“1”游程當(dāng)分別編碼，建立各自的碼表兩個(gè)碼表中的碼字可以有重復(fù)，但C碼必須不同，即分別用

C0,

C1

編碼“0”游程和“1”游程譯碼器要根據(jù)后面的碼字來判斷當(dāng)前游程的長(zhǎng)度繼續(xù)考察更后面的碼字后面碼字為：

41MH

碼MH

碼是黑白二值文件、傳真類數(shù)據(jù)壓縮編碼國(guó)際標(biāo)準(zhǔn)，是由游程編碼和赫夫曼編碼綜合而成的改進(jìn)型赫夫曼編碼對(duì)于

A4

幅面的文件，一頁應(yīng)有

1188

或

2376

條掃描線，每一行掃描線有

1728

個(gè)像素；一頁A4

紙張約

2.05

M

或

4.1

M

像素，從節(jié)省傳送時(shí)間和存儲(chǔ)空間來說，必須進(jìn)行數(shù)據(jù)壓縮這些像素可能是全黑、全白或黑、白相間隔，黑游程和白游程長(zhǎng)度均為

0

～

1728

之間，共有

2

1728

種可能的游程，但不需要對(duì)所有這些可能的游程制定編碼表將碼表劃分成兩大類：結(jié)尾碼：其長(zhǎng)度為

0

～

63

位，分別按游程特性制定對(duì)應(yīng)的赫夫曼編碼表；組合基干碼：其長(zhǎng)度為64的整數(shù)倍，按游程特性制定對(duì)應(yīng)的霍夫曼編碼表42MH編碼規(guī)則黑、白游程長(zhǎng)度在

0

～

63

之間時(shí)，直接用結(jié)尾碼表編碼黑、白游程長(zhǎng)度在

64

～1728時(shí)，采用組合基干加結(jié)尾碼進(jìn)行聯(lián)合編碼每行以白游程開始，以同步碼EOL

結(jié)束，且每頁文件以同步碼EOL開始每行游程總和為1728個(gè)像素每行傳輸時(shí)間范圍

20

ms

～

5s不足

20

ms

的行，需在

EOL

碼前填入足夠的“0”

每頁文件以

6

個(gè)

EOL

結(jié)束組合基干碼碼表結(jié)尾碼碼表000000000001000000000001EOL000000110010101001101117280000110010001001012800000011111101164黑游程碼字白游程碼字RL0000011001110011010063110111201000011110000110111001101010黑游程碼字白游程碼字RL43文件頁傳真

MH編碼格式EOL數(shù)據(jù)EOL數(shù)據(jù)EOL數(shù)據(jù)…數(shù)據(jù)EOL數(shù)據(jù)6個(gè)EOL頁首頁尾00…0行首行尾2265366155922根據(jù)MH碼表編碼，有：22(白)： 對(duì)應(yīng)編碼為00000116(黑)： 對(duì)應(yīng)編碼為001053(白)： 對(duì)應(yīng)編碼為0010010066(黑)： 因66=64+2，對(duì)應(yīng)編碼為

0000001111,111559(白)：因1559=1536+23，對(duì)應(yīng)

編碼為

010011001,000010022(黑)： 對(duì)應(yīng)編碼為00000110111例如，幅面A4的傳真文件某行的掃描像素序列如下：編碼前總碼長(zhǎng)1728，編碼后總碼長(zhǎng)

58，壓縮比非常高0000011600100100

000000111111010011001000010000000110111MH碼的編碼表是由各類文件的平均統(tǒng)計(jì)特性指標(biāo)得到的，固定不變，因而多數(shù)情況下，MH碼不是最佳碼游程的碼字由構(gòu)造碼和結(jié)尾碼組成，使碼字大大縮短445.1.6冗余位編碼概述在許多信源序列中，常有不少符號(hào)不攜帶信息，除了它的數(shù)目或所占時(shí)長(zhǎng)外，完全可以不傳送在電話通信中，講話時(shí)常有間隙，如字句間的停頓，聽對(duì)方講話而靜默，一般可以不傳送圖像信源中，