第三章-無(wú)失真信源編碼(2-2)

離散、無(wú)失真、無(wú)記憶信源符號(hào)序列編碼的一般模型：

每個(gè)符號(hào)Ui有n種取值采用m進(jìn)制編碼，Ci有m種取值信源編碼模型

對(duì)離散、無(wú)記憶、平穩(wěn)信源符號(hào)序列：U=(U1,U2…..UL)，平均每個(gè)符號(hào)的熵是可用K個(gè)碼元C=(C1,C2….Ck)進(jìn)行等長(zhǎng)編碼，對(duì)任意ε>0,δ>0，只要滿足：

則當(dāng)序列長(zhǎng)度L足夠大時(shí)，可使譯碼差錯(cuò)小于δ，反之，當(dāng)時(shí)，譯碼一定出錯(cuò)。3.3定長(zhǎng)編碼定理左邊是K長(zhǎng)碼字所能攜帶的最大信息量，右邊是長(zhǎng)為L(zhǎng)的信源序列所攜帶的信息量。只要碼字所攜帶的信息量大于信源序列輸出的信息量，則可以使傳輸幾乎無(wú)失真，條件是L足夠大。說(shuō)明：沒(méi)有一種編碼器實(shí)現(xiàn)無(wú)失真譯碼臨界，可能失真也可能無(wú)失真幾個(gè)概念：1個(gè)信源符號(hào)所攜帶的碼元平均信息比特/符號(hào)K個(gè)碼元的信息量比特/K個(gè)碼元序列的平均碼長(zhǎng)碼元/序列碼元/符號(hào)每個(gè)符號(hào)的平均碼長(zhǎng)L=1,編碼效率:信源實(shí)際信息率與編碼后的最大信息率之比。若信源的符號(hào)熵HL(U)給定，編碼后每個(gè)信源符號(hào)平均用個(gè)碼元來(lái)變換，編碼后的最大信息率為當(dāng)m=2,下面分析一下等長(zhǎng)編碼的編碼過(guò)程：例如，某信源有8種符號(hào)，每種符號(hào)的輸出概率分別為{0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04},L=1，用二元定長(zhǎng)碼進(jìn)行編碼。分析：種符號(hào)，還有部分符號(hào)沒(méi)有對(duì)應(yīng)的碼字。如果用來(lái)編碼，則只能編信源一旦出現(xiàn)這些符號(hào)，就只能用其他碼字代替編碼，因而引起差錯(cuò)。差錯(cuò)發(fā)生的可能性取決于這些符號(hào)出現(xiàn)的概率。當(dāng)L足夠大時(shí)，小概率事件發(fā)生的概率變得很小，使得差錯(cuò)概率達(dá)到足夠小。

所以，當(dāng)采用定長(zhǎng)編碼時(shí)，如果允許一定的差錯(cuò)，則無(wú)需對(duì)全部組合的nL種信息一一編碼，而僅需對(duì)集合中少數(shù)大概率事件的元素進(jìn)行編碼即可。

任何一個(gè)離散隨機(jī)序列信源，可以分成大概率事件集合Aε

與小概率事件集合,即，集Aε

中的元素有對(duì)應(yīng)的輸出碼字，而中的元素沒(méi)有對(duì)應(yīng)的碼字，因而會(huì)在譯碼時(shí)發(fā)生差錯(cuò)。如果允許一定的差錯(cuò)δ，則編碼時(shí)只需要對(duì)屬于集合Aε

中的個(gè)樣本賦以不同的碼字，即輸出碼字的總個(gè)數(shù)大于就可以了。在這種編碼方式下，差錯(cuò)概率即為集合中元素發(fā)生的概率，此時(shí)要求可以證明：為信源自信息量的方差。即當(dāng)信源序列長(zhǎng)度L滿足下式時(shí)，能達(dá)到差錯(cuò)要求。當(dāng)σ2

和ε均為定值時(shí)，只要L足夠大，差錯(cuò)概率可以小于任一正數(shù)δ，這些在Aε中的元素分別用不同碼字來(lái)代表，就完成了編碼過(guò)程。計(jì)算所有可能的信源序列樣本矢量的概率，按概率大小排列，選用概率較大的作為Aε中的元素，直到定長(zhǎng)編碼過(guò)程：在給定ε和δ后，用下式規(guī)定了L的大小。最佳編碼效率（考慮了失真）例：設(shè)有一簡(jiǎn)單離散信源：L=1,n=4對(duì)其進(jìn)行近似無(wú)失真的等長(zhǎng)編碼，若要求其編碼效率為95%，差錯(cuò)率低于10-6，試求符號(hào)聯(lián)合編碼長(zhǎng)度L=？

解：由σ2=0.6875編碼效率：可見(jiàn),需要100萬(wàn)個(gè)信源符號(hào)聯(lián)合編碼,才能達(dá)到上述要求,這顯然是不現(xiàn)實(shí)的。定長(zhǎng)編碼既要實(shí)現(xiàn)幾乎無(wú)失真，并且也要有較高的編碼效率是不能同時(shí)滿足的，必須考慮變長(zhǎng)編碼。再由:3.4變長(zhǎng)編碼定理根據(jù)信源各符號(hào)的統(tǒng)計(jì)特性，對(duì)概率大的符號(hào)用短碼，對(duì)概率小的用較長(zhǎng)的碼進(jìn)行信源編碼。單個(gè)符號(hào)變長(zhǎng)編碼定理：若離散無(wú)記憶信源的符號(hào)熵為H(X),每個(gè)信源符號(hào)用m進(jìn)制碼元進(jìn)行變長(zhǎng)編碼，一定存在一種無(wú)失真編碼方法，其碼字平均長(zhǎng)度滿足下列不等式離散平穩(wěn)無(wú)記憶序列變長(zhǎng)編碼定理：對(duì)于平均符號(hào)熵為HL(X)的離散平穩(wěn)無(wú)記憶信源，一定存在一種無(wú)失真編碼方法，使編碼后的平均信息率滿足下列不等式ε為任意小正數(shù)，當(dāng)L足夠大時(shí)，可使，則證明該定理成立。證明:

設(shè)用m進(jìn)制碼元作變長(zhǎng)編碼，序列長(zhǎng)度為L(zhǎng)個(gè)信源符號(hào)，可以得到平均碼字長(zhǎng)度滿足下列不等式說(shuō)明:

（1）用變長(zhǎng)編碼來(lái)達(dá)到相當(dāng)高的編碼效率，一般所要求的符號(hào)長(zhǎng)度L可以比定長(zhǎng)編碼小得多?？梢缘玫骄幋a效率的下界：

(2)例如：用二進(jìn)制編碼，m＝2，log2m=l，H(X)=2.55比特／符號(hào)，若要求，則編碼效率的下界為

(3)碼的剩余度為

碼的剩余度用來(lái)衡量各種編碼方法與最佳碼的差距。

（4）編碼后碼字的平均碼長(zhǎng)：（對(duì)長(zhǎng)度為L(zhǎng)的符號(hào)序列編碼）單個(gè)符號(hào)的平均碼長(zhǎng)符號(hào)序列的平均碼長(zhǎng)P(Xi)為符號(hào)序列的概率。例：設(shè)離散無(wú)記憶信源的概率空間為解:其信源熵為

比特/符號(hào)求:定長(zhǎng)編碼和變長(zhǎng)編碼的編碼效率?(1)定長(zhǎng)編碼若用二元定長(zhǎng)編碼（0，1）來(lái)構(gòu)造一個(gè)即時(shí)碼：這時(shí)平均碼長(zhǎng)為=1碼元/符號(hào)，

編碼效率為(對(duì)于無(wú)記憶信源而言,有HL(X)=H(X))輸出的信息率為L(zhǎng)=1比特/碼元(2)變長(zhǎng)編碼假定信源序列的長(zhǎng)度為L(zhǎng)=1,采用二元變長(zhǎng)編碼，其即時(shí)碼如下表所示。

符號(hào)符號(hào)概率即時(shí)碼x13/40x2101/4碼元/符號(hào)這個(gè)碼的平均碼字長(zhǎng)度碼元/符號(hào)

單個(gè)符號(hào)的平均碼長(zhǎng)

編碼效率

輸出的信息率為

R1＝0.6488比特／碼元

假定信源序列的長(zhǎng)度為L(zhǎng)=2,采用二元變長(zhǎng)編碼，其即時(shí)碼如下表所示。

序列序列概率即時(shí)碼x1x19/160x1x2x2x1x2x21/163/163/1611111010這個(gè)序列的碼字平均長(zhǎng)度單個(gè)符號(hào)的平均碼長(zhǎng)

編碼效率輸出的信息率為

R2＝0.961比特／碼元符號(hào)將信源序列的長(zhǎng)度增加，L＝3或L=4，對(duì)這些信源序列X進(jìn)行變長(zhǎng)編碼，并求出其編碼效率分別為

如果對(duì)這一信源采用定長(zhǎng)二元碼編碼，要求編碼效率達(dá)到96％時(shí)，允許譯碼錯(cuò)誤概率。則自信息的方差

信息傳輸率分別為：

R3＝0．985比特／碼元符號(hào)

R4＝0．991比特／碼元符號(hào)所需要的信源序列長(zhǎng)度(1)最佳碼定義是什么?

凡是能載荷一定的信息量，且碼字的平均長(zhǎng)度最短，可分離的變長(zhǎng)碼的碼字集合都可稱為最佳碼。

(2)最佳編碼思想是什么?

將概率大的信息符號(hào)編以短的碼字，概率小的符號(hào)編以長(zhǎng)的碼字，使得平均碼字長(zhǎng)度最短。

(3)最佳碼的編碼主要方法有哪些?

香農(nóng)（Shannon）、費(fèi)諾（Fano）、哈夫曼（Huffman）編碼等。

3.5最佳編碼1.霍夫曼編碼（一）二進(jìn)制的霍夫曼編碼①把信源發(fā)出的n個(gè)消息按其概率遞減次序排列②把概率最小的兩個(gè)消息分別編成“1”和“0”碼元(即把概率較大的消息編為“1”，概率較小的消息編為“0”；或反之也可),并對(duì)這兩個(gè)消息求概率之和③把上述的概率和作為一個(gè)新消息的概率，再與原來(lái)的其他消息按概率遞減的次序排列④重復(fù)上述編碼步驟②與③，直到概率和是1為止⑤從最終的編碼步驟，在各個(gè)消息編碼方向線的逆行程順序地取下所編出的碼元，構(gòu)成相應(yīng)的代碼組例：碼元/符號(hào)bit/符號(hào)bit/碼元由上可得代碼組的平均長(zhǎng)度為：

所以，信息傳輸速率R為：

編碼效率η為：例：已知信源X的概率空間，用霍夫曼編碼方法找出各消息的代碼組，并計(jì)算編碼效率η。解1：X，P(X)＝X1，X2，X3，X4，X50.4，0.1，0.2，0.2，0.1

由題意可得：bit/符號(hào)[碼元/符號(hào)]bit/碼元

解2：[碼元/符號(hào)]定義碼字長(zhǎng)度的方差σ2：兩種編法的平均碼長(zhǎng)相同,所以編碼效率相同。討論：哪種方法更好？結(jié)論：在哈夫曼編碼過(guò)程中,對(duì)縮減信源符號(hào)按概率由大到小的順序重新排列時(shí),應(yīng)使合并后的新符號(hào)盡可能排在靠前的位置,。這樣可使合并后的新符號(hào)重復(fù)編碼次數(shù)減少,使短碼得到充分利用。2、第一種方法編出的5個(gè)碼字只有兩種不同的碼長(zhǎng)，第二種方法編出的碼字有4種不同的碼長(zhǎng)，因此第一種編碼方法更簡(jiǎn)單、更容易實(shí)現(xiàn),所以更好。1、第一種編碼方法的碼方差要小許多。也就是說(shuō)第一種編碼方法的碼長(zhǎng)變化較小,比較接近于平均碼長(zhǎng)。二、m

進(jìn)制霍夫曼編碼1.編碼步驟同二進(jìn)制，但需注意兩點(diǎn)

(1)每次取最小的m個(gè)概率,分別賦以0,1,…,m-1；

(2)為使平均碼長(zhǎng)最短，當(dāng)對(duì)應(yīng)的碼樹(shù)為非全樹(shù)時(shí)，

第一次采用小于m個(gè)概率，此后每次均用m個(gè)概率2.非全樹(shù)時(shí)的編碼

(1)全樹(shù)——碼樹(shù)中,每個(gè)中間節(jié)點(diǎn)的后續(xù)枝數(shù)必為m(2)非全樹(shù)——碼樹(shù)中,有些中間節(jié)點(diǎn)的后續(xù)枝數(shù)不足m三進(jìn)制滿樹(shù)（等長(zhǎng)碼）三進(jìn)制全樹(shù)（少一根即為非全樹(shù)）(3)m進(jìn)制的全樹(shù)的終端節(jié)點(diǎn)數(shù)(即時(shí)碼個(gè)數(shù))

m+k(m-1),k=0,1,2,….(每從一個(gè)節(jié)點(diǎn)分出m枝,就增加m-1個(gè)終端)(4)當(dāng)n<m+k(m-1)時(shí),令s=[m+k(m-1)]-n,s(<m-1)為構(gòu)成全樹(shù)所缺少的碼字(分支)數(shù)。(5)非全樹(shù)時(shí)的霍夫曼編碼

第一次取最小概率時(shí)，只取m-s個(gè),

分別賦以0,1,2,…,m-s-1。此后每次都取m個(gè)XP(X)X1,X2,X3,X4,X5,X6,X7,X80.40,0.18,0.1,0.1,0.07,0.06,0.05,0.04例：對(duì)下列信源作三進(jìn)制霍夫曼編碼(1)分析

n=8,m=3,∴m+k(m-1)=3+2k,取k=3，得s=1.于是m-s=2，即第一次取兩個(gè)概率。(2)編碼0.090.220.381.00120121

x5

0.0722

x6

0.06200

x7

0.05201

x8

0.0411

x3

0.112

x4

0.110

x2

0.180

x1

0.40012012(3)說(shuō)明①平均碼長(zhǎng)③編碼效率

=95.2%2.費(fèi)諾編碼1)將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列為2)將依次排列的信源符號(hào)按概率值分為兩組，使劃分后的兩個(gè)組的概率之和近似相同，并對(duì)各組賦予一個(gè)二進(jìn)制碼元0和13)將每一大組的信源符號(hào)再分成兩組，使劃分后的兩個(gè)組的概率之和近似相同，并對(duì)各組賦予一個(gè)二進(jìn)制符號(hào)0和1。4)如此重復(fù)，直至每個(gè)組只剩下一個(gè)信源符號(hào)為止。5)信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾碼（按順序）。XP(X)X1,X2,X3,X4,X5,X6,X7,0.20,0.19,0.18,0.17,0.15,0.10,0.01例：對(duì)下列信源進(jìn)行費(fèi)諾編碼xiP(xi)第一次分組第二次分組第三次分組第四次分組二元碼字碼長(zhǎng)KiX10.2000002X20.19100103X30.1810113X40.1710102X50.15101103X60.101011104X70.01111114

費(fèi)諾碼的平均碼長(zhǎng)

信息傳輸速率編碼效率：

=95.3%

[說(shuō)明]i=1時(shí)，pi=0i=2時(shí)，pi=p(x1)i=3時(shí)，pi=p(x2)+p(x1)②根據(jù)式計(jì)算第i個(gè)消息的二進(jìn)制代碼組的長(zhǎng)度Ki(取正整數(shù))③為了編出唯一可譯碼組，首先計(jì)算出第i個(gè)消息的累加概率

(即不包括Xi本身的前(i-1)個(gè)消息的累加概率)，再把Pi

變換成二進(jìn)制小數(shù)，取小數(shù)點(diǎn)后的Ki位數(shù)作為第i個(gè)消息的代碼組

3.香農(nóng)編碼①把信源發(fā)出的N個(gè)消息按其概率遞減的次序排列，得例：設(shè)信源有7個(gè)符號(hào)，其二進(jìn)制香農(nóng)編碼過(guò)程如下Ki[小結(jié)]1.香農(nóng)碼,費(fèi)諾碼,霍夫曼碼均考慮了信源概率分布特性

——大概率用短碼，因而平均碼長(zhǎng)短，稱為最佳編碼。2.三者中，以霍夫曼碼最好，應(yīng)用廣泛。3.局限性——均需預(yù)知概率分布，主要用于無(wú)記憶信源。3.4游程編碼游程（Run-Length，簡(jiǎn)記RL）是指符號(hào)序列中各個(gè)符號(hào)連續(xù)重復(fù)出現(xiàn)而形成符號(hào)串的長(zhǎng)度，又稱游程長(zhǎng)度或游長(zhǎng)。游程編碼（Run-LengthCoding，簡(jiǎn)記RLC）就是將原始符號(hào)序列映射成游程長(zhǎng)度和對(duì)應(yīng)符號(hào)序列的位置的標(biāo)志序列。如果知道了游程長(zhǎng)度和對(duì)應(yīng)符號(hào)序列的位置的標(biāo)志序列，就可以完全恢復(fù)出原來(lái)的符號(hào)序列。一、術(shù)語(yǔ)游程——序列中，相連的同種元素的統(tǒng)稱游程長(zhǎng)度——同種元素的長(zhǎng)度(連碼個(gè)數(shù))游程(長(zhǎng)度)序列——由游程長(zhǎng)度構(gòu)成的序列游程長(zhǎng)度編碼——對(duì)游程長(zhǎng)度序列進(jìn)行編碼游程編碼特別適用于對(duì)相關(guān)信源的編碼。對(duì)二元相關(guān)信源，其輸出序列往往會(huì)出現(xiàn)多個(gè)連續(xù)的“0”或連續(xù)的“1”。在信源輸出的二元序列中，連續(xù)出現(xiàn)的“0”符號(hào)稱為“0游程”，連續(xù)出現(xiàn)的“1”符號(hào)稱為“1游程”，對(duì)應(yīng)連續(xù)同一符號(hào)的個(gè)數(shù)分別稱為“0”游程長(zhǎng)度和“1游程”長(zhǎng)度，游程長(zhǎng)度是隨機(jī)的，其取值可以是1，2，3，…。對(duì)二元序列，“0”游程和“1游程”總是交替出現(xiàn)的，如果規(guī)定二元序列是以“0”開(kāi)始的，那么第一個(gè)游程是“0”游程，第二個(gè)游程必為“1”游程，第三個(gè)游程又是“0”游程等等。將任何二元序列變換成游程長(zhǎng)度序列，這種變換是一一對(duì)應(yīng)的，因此是可逆的、無(wú)失真的。1.[例]000101110010001…原序列(二元)31132131…游程序列2.說(shuō)明(1)可逆(2)規(guī)定：從“0”游程開(kāi)始(此后交替)(3)游程序列為多元序列，可用霍夫曼編碼等方法進(jìn)行編碼(4)原則上亦可用于m元序列，但需增設(shè)標(biāo)志位，因而減小了壓縮比由于游程長(zhǎng)度可從“1”直到無(wú)窮大，這在碼字的選擇和碼表的建立方面都有困難，實(shí)際應(yīng)用時(shí)尚需采取某些措施來(lái)改進(jìn)。例如：線性碼——碼字長(zhǎng)度正比于游程長(zhǎng)度的編碼。MH編碼:MH編碼是一維編碼方案，它是一行一行的對(duì)文件傳真數(shù)據(jù)進(jìn)行編碼。MH編碼將游程編碼和霍夫曼碼相結(jié)合，是一種改進(jìn)的霍夫曼碼。文件傳真是指一般文件、圖紙、手寫稿、表格、報(bào)紙等文件的傳真，這種信源是黑白二值的，也即信源為二元信源。對(duì)黑白二值文件傳真，每一行由連續(xù)出現(xiàn)的“白（用碼符號(hào)0表示）像素”或連續(xù)出現(xiàn)“黑（用碼符號(hào)1表示）像素”組成。MH碼分別對(duì)“黑”、“白”像素的不同游程長(zhǎng)度進(jìn)行霍夫曼編碼，形成黑、白兩張霍夫曼碼表。MH碼的編、譯碼都通過(guò)查表進(jìn)行。MH碼以國(guó)際電話電報(bào)咨詢委員會(huì)