信息論與編碼第三版-第3章

第三章離散信源無失真編碼

§3.1概述

一．信源編碼的模型為了實現(xiàn)高質(zhì)量、高效率的通信，引入了信源編碼和信道編碼。信源編碼和信道編碼主要需要解決以下兩個問題。

（1）提高傳輸效率：用盡可能少的信道傳輸符號來傳遞信源消息，目的是提高傳輸效率，這是信源編碼主要應(yīng)考慮的問題。這里又分兩種情況討論，即允許接收信號有一定的失真或不允許失真。（2）增強通信的可靠性：如何增加信號的抗干擾能力，提高傳輸?shù)目煽啃?，這是信道編碼主要考慮的問題。解決這一問題，一般是采用冗余編碼法，賦予信碼自身一定的糾錯和檢錯能力，只要采取適當(dāng)?shù)男诺谰幋a和譯碼措施，就可使信道傳輸?shù)牟铄e概率降到允許的范圍之內(nèi)。綜上所述，提高抗干擾能力往往是以降低信息傳輸效率為代價的，而為了提高傳輸效率又往往削弱了其抗干擾能力。這樣，設(shè)計者在取舍之間就要作均衡考慮。信源編碼的概念：對信源的原始符號按一定的數(shù)學(xué)規(guī)則進行變換的一種代碼。信源編碼包括兩個功能：（1）將信源符號變換成適合信道傳輸?shù)姆?；?）壓縮信源冗余度，提高傳輸效率。信源編碼模型：{a1,a2,…,ak}為信源符號集，序列中每一個符號uml都取自信源符號集。{b1,b2,…,bD}是適合信道傳輸?shù)腄個符號，用作信源編碼器的編碼符號。

編碼輸出碼字cm

=cm1

cm2…cmn，cmk∈{b1,b2,…,bD}，k=1,2,

…,n

，n表示碼字長度，簡稱碼長?！纠恐形碾妶缶幋a：

信源編碼器I

：1－10000個漢字分別對應(yīng)0000－9999

信源編碼器II：每位數(shù)字對應(yīng)五位二進制等重碼。對應(yīng)關(guān)系如下：

（1→01011，2→11001，...，9→10011，0→01101）

如：二．碼的分類信源編碼可看成是從信源符號集到碼符號集的一種映射，即將信源符號集中的每個元素（可以是單符號，也可以是符號序列）映射成一個長度為n的碼字。對于同一個信源，編碼方法是多種的?！纠?/p>

用{u1

，u2

，u3，u4}表示信源的四個消息，碼符號集為{0,1}，下表列出了該信源的幾種不同編碼。信源消息各消息概率碼1碼2碼3碼4u1p(u1)000001u2p(u2)1101110u3p(u3)101000100u4p(u4)1111111000一般，可以將碼簡單的分成如下幾類:1．二元碼若碼符號集為{0，1}，則碼字就是二元序列，稱為二元碼，二元碼通過二進制信道傳輸，這是數(shù)字通信和計算機通信中最常見的一種碼，例子列出的4種碼都是二元碼。2．等長碼在一組碼字集合C中的所有碼字cm(m=1,2,…,M)，其碼長都相同，則稱這組碼C為等長碼，例中的碼1、碼2就碼長n=2等長碼。3．變長碼若碼字集合C中的所有碼字cm(m=1,2,…,M)，其碼長不都相同，稱碼C為變長碼，例中列出的碼3、碼4就是變長碼。信源消息各消息概率碼1碼2碼3碼4u1p(u1)000001u2p(u2)1101110u3p(u3)101000100u4p(u4)11111110004．奇異碼對奇異碼來說，從信源消息到碼字的映射不是一一對應(yīng)的。例中的碼1，信源消息u2和u4都用碼字11對其編碼，因此這種碼就是奇異碼，奇異碼不具備惟一可譯性。5．非奇異碼從信源消息到碼字的映射是一一對應(yīng)的，每一個不同的信源消息都用不同的碼字對其編碼，例中的碼2、碼3和碼4都是非奇異碼。信源消息各消息概率碼1碼2碼3碼4u1p(u1)000001u2p(u2)1101110u3p(u3)101000100u4p(u4)11111110006．原碼C的N次擴展碼原碼C的N次擴展碼中的每個元素是N次擴展信源中的序列所對應(yīng)的N個碼字組成的序列。原碼的N次擴展碼是將信源作N次擴展得到的新信源符號序列u（N）=u1…uN=(u11

u12…u1L)…(uN1

uN2…uNL)，對應(yīng)碼符號序列c（N）=c1…cN=(c11c12…c1n)…(cN1cN2…cNn)，記集合C(N)={c1(N),c2(N),…}，C(N)

即原碼C的N次擴展碼。7．唯一可譯碼定義：如果碼的任意N次擴展碼都是非奇異碼，則稱該碼為惟一可譯碼。

例中的碼1不是唯一可譯碼。對于定長碼，若原碼是惟一可譯碼，則它的N次擴展碼也是惟一可譯的，而對于變長碼則不盡然。信源消息各消息概率碼1碼2碼3碼4u1p(u1)000001u2p(u2)1101110u3p(u3)101000100u4p(u4)1111111000信源消息各消息概率碼1碼2碼3u1p(u1)011u2p(u2)11001u3p(u3)00100001u4p(u4)1110000001碼1不是唯一可譯碼，碼2、碼3是唯一可譯碼。8．即時碼對于變長碼，有兩個定義：（1）前綴：對于碼字C=c1

c2…cn，稱c’=c1

c2…ci

(i<n)為碼字c的字頭（前綴）。（2）異字頭碼：若碼中任一碼字都不是另一碼字的字頭，稱該碼為異字頭碼（無前綴碼）。碼3是無前綴碼；其他都不是無前綴碼。即時碼：例中碼3，收到“1”后就知道一個碼字已經(jīng)完結(jié)，無須等待下一個符號抵達，所以無前綴碼能夠即時譯碼，稱之為即時可譯碼，簡稱即時碼。

信源消息各消息概率碼1碼2碼3u1p(u1)011u2p(u2)11001u3p(u3)00100001u4p(u4)1110000001而對于碼2，收到“1”后，并不能立即做出判決，就是收到“10”也不能立即做出判決，則還要收到下面的碼元才能做出判決。所以非異字頭碼不能即時譯碼，稱為非即時碼，由于非異字頭碼的其中一些碼字是另一些碼字的延長，故也稱延長碼。

即時碼是惟一可譯碼，而惟一可譯碼不一定是即時碼。即時碼的樹圖構(gòu)造方法：對于D進制碼，從樹根出發(fā)，可引出D根樹枝，每根樹枝分別賦予一個不同的碼符號，樹枝的端點為節(jié)點，每一個節(jié)點又可引出D根分枝，又分別賦予這D根分枝每根一個不同的碼符號，如某一節(jié)點被定為碼字后，就不再引出樹枝，該節(jié)點稱為終節(jié)點。碼字就是從樹根出發(fā)，到達終節(jié)點所對應(yīng)的碼符號序列。

【例】用樹圖法表示碼（1，01，001，0001）。碼的分類結(jié)構(gòu)圖由上面的結(jié)構(gòu)圖可看出，將碼分為奇異碼和非奇異碼兩大類，我們只討論非奇異碼。非奇異碼又分為惟一可譯碼和非惟一可譯碼兩大類，我們只討論惟一可譯碼三．平均碼長的計算對于變長碼，碼集C的平均碼長定義為碼C中每個碼字cm(m=1,2,…，M)其碼長的概率加權(quán)平均值，用符號表示

式中nm是碼字cm所對應(yīng)的碼字的長度，p(cm

)是碼字cm出現(xiàn)的概率。對于等長碼，由于碼集C中的每個碼字的碼長都相同，平均碼長就等于每個碼字的碼長【例】計算下表各碼的平均碼長：

信源消息各消息概率碼1碼2碼3碼4u10.4000001u20.21101110u30.2101000100u40.21111111000碼長221.42.2【推廣】N次擴展碼的平均碼長等于擴展碼中碼字長度的概率加權(quán)平均值。

對于2次擴展碼，有：設(shè)nm，ns分別是原信源消息um，us所對應(yīng)的碼長，cm，cs是um，us所對應(yīng)的碼字，則式中的nm

+ns是擴展后新的信源序列umus所對應(yīng)的碼字cmcs的長度，p(um)p(us)是cmcs出現(xiàn)的概率。

四．信息傳輸速率定義：信道的信息傳輸速率為信道單位時間內(nèi)所傳輸?shù)膶嶋H信息量。

（1）若信息量以比特為單位，時間以秒為單位，則信息傳輸速率定義為：

（比特/秒）

式中：H(X)為信源熵；為編碼后的平均碼長；t為傳輸一個碼符號的時間。

（2）若信息量以比特為單位，時間以碼元時間（傳輸一個碼符號的時間）為單位，則信息傳輸率記為：

(比特/碼元時間)

【例】給定信源為提高傳輸效率，使平均碼長盡可能短，遵照概率大取碼長短，概率小取碼長長的原則對上述信源進行二進制不等長編碼，得到如右編碼方案，求編碼后的信息傳輸率RD。（比特/符號）

（碼元/符號）

(比特/碼元時間)

§3.2等長碼及等長編碼定理一．等長編碼定理考慮對一簡單信源S進行等長編碼，信源符號集有K個符號，碼符號集含D個符號，碼字長度記為n。對信源作等長無差錯編碼，要得到惟一可譯碼，必須滿足下式：K≤Dn對單符號信源S的L次擴展信源S（L）進行等長編碼，要得到長為n的惟一可譯碼，必須滿足:KL

≤Dn對上式兩邊取對數(shù)，得：，對信源輸出的L長序列si

，i=1,2,…,KL

進行等長編碼，碼字是長度為n的D進制符號串，當(dāng)滿足條件，則L→∞時，可使譯碼差錯pe

<δ(ε、δ為無窮小量)；反之，當(dāng)時，則不可能實現(xiàn)無差錯編碼。對于那些出現(xiàn)概率極小的字符序列不予編碼，這樣可以減小平均碼長，當(dāng)然這樣會帶來一定的失真。下面的定理將證明，當(dāng)滿足一定的條件時，在L→∞時，失真pe→0。【定理】等長編碼定理

設(shè)離散無記憶信源S={x1,x2,…,xk}的熵為H(X)，S的L維擴展信源為二．編碼效率根據(jù)等長碼的編碼定理，我們可以得到一個衡量編碼質(zhì)量的重要指標(biāo)，編碼效率。等長編碼定理要求，即，可看出比值是一個小于1的無量綱純數(shù)，定義它為等長編碼的編碼效率，記為：編碼效率η是衡量編碼質(zhì)量的一個重要指標(biāo)，對信源編碼時應(yīng)盡量提高編碼效率?！纠?/p>

（1）給定離散無記憶信源，對該信源進行二進制等長編碼，并求編碼效率。

【解】先確定碼長：信源消息數(shù)目K＝3，信源序列長度L＝1，碼符號數(shù)D＝2①根據(jù)

②根據(jù)等長編碼定理：

（比特/符號）

根據(jù)前面計算，由等長編碼定理計算出的下界更小，但由于碼長都取整，故取n1=n2=2。并做如下編碼：，得到唯一可譯碼。

編碼效率為：

（2）對原信源進行L=2維擴展，得到新信源：

對擴展信源進行二進制等長編碼。

【解】對擴展碼K＝3，信源序列長度L＝2，碼符號數(shù)D＝2

①由確定碼長：

取n3=4，對擴展信源編碼的編碼如下：

信源序列x0x0x0x1x0x2x1x0x1x1x1x2x2x0x2x1x2x2碼字000000010010001101000101011001111000編碼效率：

②按等長編碼定理：

取n4=3，對擴展信源編碼的編碼如下：

信源序列x0x0x0x1x0x2x1x0x1x1x1x2x2x0x2x1x2x2碼字000001000010011100101110111對于二進制碼，取碼長為3，共可構(gòu)成8個不同的碼字，而擴展信源含9個序列，故編碼時對序列中概率小的兩個序列賦予同一個碼字000，這樣勢必存在譯碼差錯概率pe：

§3.3變長碼及變長編碼定理一．變長碼對等長碼的討論是在L足夠大的條件下得到的結(jié)論，當(dāng)L為有限值時，則總會帶來一定程度的失真。對于變長碼，往往在L不是很大的情況下就可編出高效且無失真的碼。變長碼也要求原碼的任意L次擴展碼也是惟一可譯的。變長碼分為即時碼和延長碼，為保證即時譯碼，要求變長惟一可譯碼采用即時碼。對于變長碼，要求整個碼集的平均碼長力求最小，此時編碼效率最高。對于給定信源，使平均碼長達到最小的編碼方法，稱為最佳編碼，得到的碼集稱為最佳碼。二．克拉夫特不等式定理：D進制碼字集合C={c1，c2，…，cM}，碼集中每一cm（m=1,2,…,M）都是一個D進制符號串，設(shè)c1，c2，…，cM

對應(yīng)的碼長分別是n1，n2，…，nM，則存在唯一可譯碼的充要條件是（克拉夫特不等式）

定理只是說是存在惟一可譯碼的充要條件，這里強調(diào)的是“存在”，但它并不是唯一可譯碼的充要條件，換言之，惟一可譯碼一定滿足克拉夫特不等式，反之，滿足克拉夫特不等式的碼不一定是惟一可譯碼。三．變長編碼定理

平均碼長極限定理（離散無記憶信源變長編碼定理）：

給定熵為H（X）的離散無記憶信源，及有D個元素的碼符號集，則總可找到一種無失真編碼方法，構(gòu)成惟一可譯碼，其平均碼長滿足：

定理的證明過程給了我們一種最佳編碼的構(gòu)造方法，即如果信源的概率分布均有

的形式，那么直接取ni作為對應(yīng)消息符號的碼字長度，就可以得到緊致碼（最佳碼）。

等號成立時編碼效率最高，此時的碼稱為最佳碼【例3.3.1】對其進行二元編碼，碼長分別取{1，2，3，3}此時的平均碼長為（碼元/符號）信源熵為（bit/符號）編碼效率信息傳輸率（bit/碼元）其L次擴展信源的熵記為

定理：變長編碼定理(Shannon第一定理)

給定熵為H（X）的離散無記憶信源

給定有D個元素的碼符號集，對擴展信源進行編碼，總可以找到一種惟一可譯碼，使碼長滿足：

記為信源每個符號所對應(yīng)的平均碼字數(shù)，則上式為：

編碼效率：

η是一個無量綱的數(shù)，一般情況下η<1，在極限情況下η=1。

Shannon第一定理的物理意義在于：對信源進行編碼，使編碼后的碼集中各碼元符號盡可能等概分布，如果將這碼集看成為一個新的信源，這時新信源的每個碼符號平均所含信息量達到最大。【例】已知離散無記憶信源對X進行二進制等長編碼取n=1,x1→0,x2→1,

（bit/符號）對X2進行二進制變長編碼x1x1x1x2x2x1x2x2Pi9/163/163/161/16C010110111(嚴格的無失真編碼)

若進行等長編碼效率η=0.96,差錯率

Pe≤10-5,L≥4.13×107（有失真編碼）③對X3進行二進制變長編碼

η=98.5%，R=0.985bit/碼元④對X4進行二進制變長編碼

η=99.1%，R=0.991bit/碼元§3.4變長碼的編碼方法常用的變長編碼法：①香農(nóng)（Shannon）編碼法②費諾(Fano)編碼法③霍夫曼(Huffman)編碼法

對于同一種信源，三種編碼法中以香農(nóng)編碼法的編碼效率最低，費諾編碼法也不是一種最佳編碼法，但用這種方法有時候也能找到緊致碼（在所有的唯一可譯碼中，平均碼長最小的碼稱緊致碼，也就是最佳碼）。一般情況下，霍夫曼編碼法得到的平均碼長最短，即編碼效率最高。

一.香農(nóng)編碼法記離散信源

給定有D個元素的碼符號集，對信源進行變長編碼，將各消息概率p(xm)(m=1,2,…,M)寫成如下的形式：取碼長nm(m=1,2,…,M)滿足：由此得香農(nóng)編碼法碼長取值范圍:對于二進制香農(nóng)編碼法，有

編碼步驟：（1）將信源發(fā)出的M個消息，按其概率遞減順序進行排列；

（2）計算出各消息的－logp(xm)值，m=1,2,…,M；

（3）根據(jù)式：計算出每個消息的二進制代碼的長度nm。

（－logp(xm)為整數(shù)時取等號）（4）計算出第m個消息的累加概率，再將pi變換成二進制小數(shù)，取小數(shù)點后面nm位作為第m個消息的代碼組。

【例】對給定信源進行D=2進制香農(nóng)編碼并求編碼效率?！窘狻浚?）編碼消息符號xi消息概率p(xm)－logp(xm)碼長ni累加概率pi碼字Cix10.22.3430000x20.192.4130.2001x30.182.4830.39011x40.172.5630.57100x50.152.7430.74101x60.103.3440.891110x70.016.6670.991111110（2）求編碼效率信源熵：

比特/符號

平均碼長：

碼元/符號

編碼效率：

消息符號xi消息概率p(xm)－logp(xm)碼長ni累加概率pi碼字Cix10.22.3430000x20.192.4130.2001x30.182.4830.39011x40.172.5630.57100x50.152.7430.74101x60.103.3440.891110x70.016.6670.991111110二．費諾編碼法費諾編碼法的具體步驟如下：

（1）信源發(fā)出的M個消息，按其概率遞減順序進行排列，把消息集{x1,x2,x3,…,xM}按其概率大小分解成兩個子集，使兩個子集的概率之和盡可能接近相等，把第一個子集編碼為“0”，第二個子集編碼為“1”，作為代碼組的第一個碼元；（2）對子集做第二次分解，同樣分解成兩個子集，并使兩個