第3章無失真信源編碼-廖-2013-本科生

第3章

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

內(nèi)容提要用盡可能少的符號來傳輸信源消息，目的是提高傳輸效率，這是信源編碼應(yīng)考慮的問題，這章討論在不允許失真情況下的信源編碼。等長編碼定理給出了等長編碼條件下，其碼長的下限值，變長編碼定理（香農(nóng)第一定理）給出了信源無失真變長編碼時其碼長的上、下限值。本章還介紹了三種通用信源編碼方法：香農(nóng)編碼法、Fano編碼法和霍夫曼編碼法。離散信源：消息集X為離散集合。即時間和幅度取值都離散的信源。3．1概述為了實現(xiàn)高質(zhì)量、高效率的通信，引入了信源編碼和信道編碼。信源編碼和信道編碼主要需要解決以下兩個問題。提高傳輸效率

增強(qiáng)通信的可靠性

信息論的研究對象--通信系統(tǒng)模型，信源，編碼器，信道，譯碼器，信宿。（1）提高傳輸效率，用盡可能少的信道傳輸符號來傳遞信源消息，目的是提高傳輸效率，這是信源編碼主要應(yīng)考慮的問題。這里又分兩種情況討論，即允許接收信號有一定的失真或不允許失真。綜上所述，提高抗干擾能力往往是以降低信息傳輸效率為代價的，而為了提高傳輸效率又往往削弱了其抗干擾能力。這樣，設(shè)計者在取舍之間就要作均衡考慮。

（2）

增強(qiáng)通信的可靠性如何增加信號的抗干擾能力，提高傳輸?shù)目煽啃?，這是信道編碼主要考慮的問題。解決這一問題，一般是采用冗余編碼法，賦予信碼自身一定的糾錯和檢錯能力，只要采取適當(dāng)?shù)男诺谰幋a和譯碼措施，就可使信道傳輸?shù)牟铄e概率降到允許的范圍之內(nèi)。信源編碼包括兩個功能：（1）

將信源符號變換成適合信道傳輸?shù)姆?；?）

壓縮信源冗余度，提高傳輸效率。7由于信源符號之間存在分布不均勻和相關(guān)性，使得信源存在冗余度，信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。

8信源編碼的基本途徑有兩個：使序列中的各個符號盡可能地互相獨立，即解除相關(guān)性；使編碼中各個符號出現(xiàn)的概率盡可能地相等，即概率均勻化。9信源編碼的基礎(chǔ)是信息論中的兩個編碼定理：無失真編碼定理---香農(nóng)第一定律，給出了信源無失真變長編碼時其碼長的上、下限值。限失真編碼定理

無失真編碼只適用于離散信源

對于連續(xù)信源，只能在失真受限制的情況下進(jìn)行限失真編碼

無失真信源編碼：能夠精確地復(fù)現(xiàn)信源的輸出，保證信源產(chǎn)生的全部信息無損地送給信宿，這時的信源編碼就是無失真信源編碼。3.1.1信源編碼的相關(guān)概念

編碼器3.1圖3.1信源編碼器3.1書上例子：3.1,3.2信源編碼有以下3種主要方法：(1)匹配編碼根據(jù)信源符號的概率不同，編碼的碼長不同：概率大的信源符號，所編的代碼短；概率小的信源符號所編的代碼長，這樣使平均碼長最短。將要講述的香農(nóng)編碼、哈夫曼編碼、費(fèi)諾碼都是概率匹配編碼，都是無失真信源編碼。(2)變換編碼先對信號進(jìn)行變換，從一種信號空間變換為另一種信號空間，然后針對變換后的信號進(jìn)行編碼。(3)識別編碼識別編碼主要用于印刷或打字機(jī)等有標(biāo)準(zhǔn)形狀的文字符號和數(shù)據(jù)的編碼，比如中文文字和語音的識別。后兩種信源編碼均為有失真的信源編碼。無失真信源編碼主要針對離散信源，連續(xù)信源在量化編碼的過程中必然會有量化失真，所以對連續(xù)信源只能近似地再現(xiàn)信源的消息。信源編碼可看成是從信源符號集到碼符號集的一種映射，即將信源符號集中的每個元素（可以是單符號，也可以是符號序列）映射成一個長度為n的碼字。對于同一個信源，編碼方法是多種的?！纠?.3】用{u1

，u2

，u3，u4}表示信源的四個消息，碼符號集為{0,1}，表3-1列出了該信源的幾種不同編碼。表3-1同一信源的幾種不同編碼信源消息各消息概率碼1碼2碼3碼4u1q(u1)000001u2q(u2)1101110u3q(u3)101000100u4q(u4)11111110003.1.2碼的分類3.變長碼若碼字集合C中的所有碼字cm(m=1,2,…,M)，其碼長不都相同，碼中的碼字長短不一，稱碼C為變長碼，表3-1中列出的碼3、碼4就是變長碼。2.等長碼在一組碼字集合C中的所有碼字cm(m=1,2,…,M)，其碼長都相同，碼中所有碼字的長度，都相同，則稱這組碼C為等長碼，表3-1中列出的碼1、碼2就碼長n=2等長碼。一般，可以將碼簡單的分成如下幾類：1.二元碼若碼符號集為{0，1}，則碼字就是二元序列，稱為二元碼,二元碼通過二進(jìn)制信道傳輸，這是數(shù)字通信和計算機(jī)通信中最常見的一種碼，表3-1列出的4種碼都是二元碼。5.非奇異碼從信源消息到碼字的影射是一一對應(yīng)的，每一個不同的信源消息都用不同的碼字對其編碼，若一組碼中所有碼字都不相同，則稱為非奇異碼。例表3-1中的碼2、碼3和碼4都是非奇異碼。4.奇異碼對奇異碼來說，從信源消息到碼字的影射不是一一對應(yīng)的。若一組碼中有相同的碼字，則稱為奇異碼。例表3-1中的碼1，信源消息u2和u4都用碼字11對其編碼，因此這種碼就是奇異碼，奇異碼不具備惟一可譯性。

擴(kuò)展信源

信源編碼器

信源符號{a1,a2,…,aK}

信道符號（碼符號）{b1,b2,…,bD}

消息

u1

…uN=(u11u12…

u1L)…

(uN1uN2…

uNL)N次擴(kuò)展碼字

c1

…cN=(c11c12…

c1n)…

(cN1cN2…

cNn)圖3-2N次擴(kuò)展信源編碼器模型

原碼的N次擴(kuò)展碼是將信源作N次擴(kuò)展得到的新信源符號序列u（N）=u1

…uN=(u11u12…

u1L)…

(uN1uN2…

uNL)，對應(yīng)碼符號序列c（N）=c1

…cN=(c11c12…

c1n)…

(cN1cN2…

cNn)，記集合C(N)={c1(N),c2(N),…}，C

(N)即原碼C的N次擴(kuò)展碼。6.原碼C的N次擴(kuò)展碼原碼C的N次擴(kuò)展碼中的每個元素是N次擴(kuò)展信源中的序列所對應(yīng)的N個碼字組成的序列。草稿對于定長碼，若原碼是惟一可譯碼，則它的N次擴(kuò)展碼也是惟一可譯的，而對于變長碼則不盡然，見表3-2。信源消息各消息概率碼1碼2碼3u1q(u1)011u2q(u2)11001u3q(u3)00100001u4q(u4)1110000001表3-2同一信源的幾種不同變長編碼表3-2同一信源的幾種不同變長編碼

7.惟一可譯碼定義3.1如果碼的任意N次擴(kuò)展碼都是非奇異碼，則稱該碼為惟一可譯碼。NYY對于碼1，由于它的每一個信源符號對應(yīng)不同的碼字，所以它本身是唯一可譯，但將它進(jìn)行二次擴(kuò)展后得到的二次擴(kuò)展碼就不唯一可譯，例如，二次擴(kuò)展碼中的u1u3和u3u1對應(yīng)同一個碼字000，u2u4和u4u2對應(yīng)同一個碼字111，因此碼1不是唯一可譯碼。對于碼2，碼3不僅本身是唯一可譯碼，進(jìn)行N次擴(kuò)展后得到的N次擴(kuò)展碼也是唯一可譯的，按照定義3.1，碼2、碼3是唯一可譯碼。第三章：離散信源無失真編碼

編碼器碼的分類

1.二元碼：若碼符號集為{0，1}，則碼字就是二元序列，稱為二元碼；2.等長碼：碼中所有碼字的長度，都相同；3.變長碼：碼中的碼字長短不一；4.奇異碼：若一組碼中有相同的碼字，則稱為奇異碼；5.非奇異碼：若一組碼中所有碼字都不相同。6.原碼C的N次擴(kuò)展碼7.惟一可譯碼：如果碼的任意N次擴(kuò)展碼都是非奇異碼，則稱該碼為惟一可譯碼。8.即時碼對于變長碼，又有如下定義定義3.2

對于碼字c

=c1c2…

cn,稱c、

=c1c2…

ci(i<n)為碼字c的字頭（前綴）。定義3.3若碼中任一碼字都不是另一碼字的字頭，稱該碼為異字頭碼（無前綴碼）。碼3是無前綴碼，碼1和2都不是無前綴碼表3-2中碼3，收到“1”后就知道一個碼字已經(jīng)完結(jié)，無須等待下一個符號抵達(dá)，所以無前綴碼能夠即時譯碼,稱之為即時可譯碼，簡稱即時碼。而對于碼2，收到“1”后，并不能立即做出判決，就是收到“10”也不能立即做出判決，則還要收到下面的碼元才能做出判決。所以非異字頭碼不能即時譯碼，稱為非即時碼，由于非異字頭碼的其中一些碼字是另一些碼字的延長，故也稱延長碼。顯然，即時碼是惟一可譯碼，而惟一可譯碼不一定是即時碼。因為有些非即時碼(延長碼)具有唯一可譯性，但不滿足前綴條件，不能即時譯碼即時碼可用樹圖法來構(gòu)造。對給定碼字的全體集合來說，可以用碼樹來描述它，例子下面。所謂樹，既有根，枝，又有節(jié)點。樹中最頂部的節(jié)點稱為根節(jié)點，從根出發(fā)向下伸出樹枝，樹枝的數(shù)目等于碼符號的總數(shù)r。沒有子節(jié)點的節(jié)點稱為葉子節(jié)點。所有根節(jié)點的子節(jié)點稱為一階節(jié)點，所有一階節(jié)點的子節(jié)點稱為二階節(jié)點，依此類推。n階節(jié)點最多有個。節(jié)點的階次又稱為節(jié)點的深度。當(dāng)某一節(jié)點被安排為碼字后，它就不再繼續(xù)伸枝，此節(jié)點稱為終端節(jié)點，用粗黑點表示。圖3-3用樹圖法編碼樹根編碼深度u1：1u2：01u3：001u4：00011

0u1u2u3u41

1

1

00【例3.4】用樹圖法表示表3-2中的碼3，如圖3-3所示（D=2）。復(fù)習(xí)上次課的內(nèi)容：編碼器碼的分類復(fù)習(xí)上次課的內(nèi)容：碼的分類

1.二元碼：若碼符號集為{0，1}，則碼字就是二元序列，稱為二元碼；2.等長碼：碼中所有碼字的長度，都相同；3.變長碼：碼中的碼字長短不一；4.奇異碼：若一組碼中有相同的碼字，則稱為奇異碼；5.非奇異碼：若一組碼中所有碼字都不相同。6.原碼C的N次擴(kuò)展碼7.惟一可譯碼：如果碼的任意N次擴(kuò)展碼都是非奇異碼，則稱該碼為惟一可譯碼。8.即時碼:無需考慮后續(xù)的碼符號就可以從碼符號序列中譯出碼字，這樣的唯一可譯碼稱為即時碼。8.即時碼對于變長碼，又有如下定義定義3.2

對于碼字c

=c1c2…

cn,稱c、

=c1c2…

ci(i<n)為碼字c的字頭（前綴）。定義3.3若碼中任一碼字都不是另一碼字的字頭，稱該碼為異字頭碼（無前綴碼）。碼3是無前綴碼，碼1和2都不是無前綴碼表3-2中碼3，收到“1”后就知道一個碼字已經(jīng)完結(jié)，無須等待下一個符號抵達(dá)，所以無前綴碼能夠即時譯碼,稱之為即時可譯碼，簡稱即時碼。而對于碼2，收到“1”后，并不能立即做出判決，就是收到“10”也不能立即做出判決，則還要收到下面的碼元才能做出判決。所以非異字頭碼不能即時譯碼，稱為非即時碼，由于非異字頭碼的其中一些碼字是另一些碼字的延長，故也稱延長碼。顯然，即時碼是惟一可譯碼，而惟一可譯碼不一定是即時碼。因為有些非即時碼(延長碼)具有唯一可譯性，但不滿足前綴條件，不能即時譯碼即時碼可用樹圖法來構(gòu)造。對給定碼字的全體集合來說，可以用碼樹來描述它，例子下面。所謂樹，既有根，枝，又有節(jié)點。樹中最頂部的節(jié)點稱為根節(jié)點，從根出發(fā)向下伸出樹枝，樹枝的數(shù)目等于碼符號的總數(shù)r。沒有子節(jié)點的節(jié)點稱為葉子節(jié)點。所有根節(jié)點的子節(jié)點稱為一階節(jié)點，所有一階節(jié)點的子節(jié)點稱為二階節(jié)點，依此類推。n階節(jié)點最多有個。節(jié)點的階次又稱為節(jié)點的深度。當(dāng)某一節(jié)點被安排為碼字后，它就不再繼續(xù)伸枝，此節(jié)點稱為終端節(jié)點，用粗黑點表示。圖3-3用樹圖法編碼樹根編碼深度u1：1u2：01u3：001u4：00011

0u1u2u3u41

1

1

00【例3.4】用樹圖法表示表3-2中的碼3，如圖3-3所示（D=2）。即時碼的樹圖構(gòu)造法我們可以用樹圖的形式構(gòu)造即時碼，如01001111010010001碼4的樹圖10110000101001000碼3的樹圖樹根——碼字的起點樹枝數(shù)——碼的數(shù)節(jié)點數(shù)——碼字的一部分節(jié)數(shù)——碼長端點——碼字滿樹——等長碼非滿樹——變長碼書上例子3.59同價碼

同價碼：每個碼符號所占的傳輸時間都相同的碼。對同價碼來說，等長碼中每個碼字的傳輸時間相同。而變長碼中的每個碼字的傳輸時間不一定相同。電報中常用的莫爾斯碼是非同價碼，其碼符號點（．）和劃（-）所占的傳輸時間不相同。最早的摩爾斯電碼是一些表示數(shù)字的點和劃。數(shù)字對應(yīng)單詞，需要查找一本代碼表才能知道每個詞對應(yīng)的數(shù)。用一個電鍵可以敲擊出點、劃以及中間的停頓。雖然摩爾斯發(fā)明了電報，但他缺乏相關(guān)的專門技術(shù)。他與艾爾菲德·維爾簽定了一個協(xié)議，讓他幫自己制造更加實用的設(shè)備。艾爾菲德·維爾構(gòu)思了一個方案，通過點、劃和中間的停頓，可以讓每個字元和標(biāo)點符號彼此獨立地發(fā)送出去。他們達(dá)成一致，同意把這種標(biāo)識不同符號的方案放到摩爾斯的專利中。這就是現(xiàn)在我們所熟知的美式摩爾斯電碼。10.分組碼和非分組碼

定義

將信源符號集中的每個信源符號固定地映射成一個碼字Wi，這樣的碼稱為分組碼。用分組碼對信源符號進(jìn)行編碼時，為了使接收端能夠迅速準(zhǔn)確地將碼譯出，分組碼必須具有一些直觀屬性。與分組碼對應(yīng)的是非分組碼，又稱為樹碼、樹碼編碼器輸出的碼符號通常與編碼器的所有信源符號都有關(guān)。si圖3-5碼的分類結(jié)構(gòu)圖

圖3-5是碼的分類結(jié)構(gòu)圖

由上面的結(jié)構(gòu)圖可看出，我們只討論非奇異碼。非奇異碼又分為惟一可譯碼和非惟一可譯碼兩大類，我們只討論惟一可譯碼。

3.1.3平均碼長的計算

對于變長碼，碼集C的平均碼長，用符號表示，定義為碼C中每個碼字cm(m=1,2,…，M)其碼長的概率加權(quán)平均值為 (3-1)式中nm是碼字cm所對應(yīng)的碼字的長度，p(cm

)是碼字cm出現(xiàn)的概率。對于等長碼，由于碼集C中的每個碼字的碼長都相同，平均碼長就等于每個碼字的碼長書上例子P54頁，計算平均碼長n1,n2,n3,n4N次擴(kuò)展碼的平均碼長等于擴(kuò)展碼中碼字長度的概率加權(quán)平均值。對于2次擴(kuò)展碼，有：

(3-2)設(shè)nm,

ns分別是原信源消息um,

us所對應(yīng)的碼長,cm,

cs是um,

us所對應(yīng)的碼字，則式(3-2)中的nm+ns是擴(kuò)展后新的信源序列nmns所對應(yīng)的碼字cmcs的長度，q(um)q(us)是cmcs出現(xiàn)的概率。書上的例子3.63.1.4信息傳輸速率信道的信息傳輸速率為信道單位時間內(nèi)所傳輸?shù)膶嶋H信息量。若信息量以比特為單位，時間以秒為單位，則信息傳輸率定義為： (比特/秒)(3-3)若信息量以比特為單位，時間以碼元時間（傳輸一個碼符號的時間）為單位，則信息傳輸率記為

(比特/碼元時間) (3-4)

為編碼后的平均碼長；H(X)為信源熵；式中：t為傳輸一個碼符號的時間?？梢钥闯?，越小，則越大，信息傳輸率就越高，因此我們感興趣的碼是使平均碼長最短的碼。書上例子。3.7【例3.8】

給定信源，為提高傳輸效率，使平均碼長盡可能短，遵照概率大取碼長短，概率小取碼長長的原則對上述信源進(jìn)行二進(jìn)制不等長編碼，得到，求編碼后的信息傳輸率RD。解：根據(jù)定義如果碼的任意N次擴(kuò)展碼都是非奇異碼，則稱該碼為惟一可譯碼。(非奇異碼為碼中所有碼字都不相同)DS2S3:10110,S5S1:10110FS1S4:0110S6S1:0110信源S共有q=4個信源符號，s1,s2,s3,s4,現(xiàn)進(jìn)行二元等長編碼，其中碼符號個數(shù)r=2，則根據(jù)5.1式可知，存在唯一可譯等長碼的條件是碼長l必須不小于2如果N=1，則，則與前面的5.1式一樣。l/N是平均每個信源符號所需要的碼符號個數(shù)，表明對于等長唯一可譯碼，每個信源符號至少需要用個碼符號來變換,也就是說，每個信源符號所需最短的碼長為個。當(dāng)r=2（二元碼）時，logr=1.則式5.2成為這結(jié)果表明，對于二元等長唯一可譯碼，每個信源符號至少需要用logq個二元符號來變換，也表明對信源進(jìn)行二元等長不失真編碼時，每個信源符號所需碼長的極限值為logq個。定理3.1

等長編碼定理

設(shè)離散無記憶信源S={x1

，x2

，…，xk}的熵為H（X），S的L維擴(kuò)展信源為，對信源輸出的L長序列si，i=1,2,…,KL進(jìn)行等長編碼，碼字是長度為n的D進(jìn)制符號串，當(dāng)滿足條件，則L→∞時，可使譯碼差錯pe<δ(ε、δ為無窮小量)；反之，當(dāng) 時，則不可能實現(xiàn)無差錯編碼。定理3.1

等長編碼定理將定理要求的下界與式（3-6）要求的下界作一個比較:H（X）是單符號信源S={x1

，x2

，…，xk}的熵，根據(jù)極大離散熵定理，信源等概分布時熵值最大，其最大值為logk，即有H（X）

logK，這就說明了定理3.1要求的下界比式（3-6）要求的下界更緊致，對的要求更低。

仍然考慮[例3-7]中所列舉的英文字符信源，根據(jù)式（3-6），可求出根據(jù)定理3.1要求，可求出顯然n1>n2，實際上由于要求碼長取整數(shù)，故只能取n1=n2=5。n為碼長----lK信源的符號個數(shù)----qD碼符號個數(shù)---rn為碼長----lL為信源序列長度---N編碼效率定理3.1要求，即，可看出比值是一個小于1的無量綱純數(shù)，定義它為等長編碼的編碼效率，記為

（3-7）

定理3.1要求，是為了實現(xiàn)無差錯編碼每個信源符號所需要的最少碼符號數(shù)，這是等長碼編碼時的理論極限。事實上這種幾乎無失真的代價是要求信源序列長L→∞,L大就意味著實現(xiàn)的復(fù)雜性及譯碼的時延加大。n為碼長----lL為信源序列長度---ND碼符號個數(shù)---r例子3.9P583.3變長碼及變長編碼定理

3.3.1變長碼對變長碼的討論是在L足夠大的條件下得到的結(jié)論，當(dāng)L為有限值時，則總會帶來一定程度的失真。對于變長碼，往往在L不是很大的情況下就可編出高效且無失真的碼。變長碼也要求原碼的任意L次擴(kuò)展碼也是惟一可譯的。變長碼分為即時碼和延長碼，為保證即時譯碼，要求變長惟一可譯碼采用即時碼。對于變長碼，要求整個碼集的平均碼長力求最小，此時編碼效率最高。對于給定信源，使平均碼長達(dá)到最小的編碼方法，稱為最佳編碼，得到的碼集稱為最佳碼。3.3.2克拉夫特不等式定理3.2

D進(jìn)制碼字集合C={c1,c2,…,cM}，碼集中每一cm（m=1,2,…,M）都是一個D進(jìn)制符號串，設(shè)c1,c2,…,cM對應(yīng)的碼長分別是n1,n2,

…,nM

，則存在唯一可譯碼的充要條件是

(3-10)

式（3-10）也稱克拉夫特不等式

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

575.1編碼的定義例：設(shè)二進(jìn)制碼樹中X(a1，a2，a3，a4)，l1＝1，l2＝2，l3＝2，l4＝3，應(yīng)用上述判斷定理：

因此不存在滿足這種li的唯一可譯碼。

585.1編碼的定義a1=1

01

01

01a2=01a3=001a4=000{1，01，001，000}

惟一可譯碼；{1，01，101，000}

不是惟一可譯碼；均滿足克勞夫特不等式595.1編碼的定義克勞夫特不等式只是用來說明唯一可譯碼是否存在，并不能作為唯一可譯碼的判據(jù)。3.3.3變長編碼定理定理3.3

給定熵為H（X）的離散無記憶信源，及有D個元素的碼符號集，則總可找到一種無失真編碼方法，構(gòu)成惟一可譯碼，其平均碼長滿足： （3-19）證明：(1)先證下界，即證。設(shè)離散無記憶信源含M個消息，信源熵為H（X），其統(tǒng)計模型為

則：（利用克拉夫特不等式）當(dāng)即

時，上式中等號成立，有

→這時得到的碼就是緊致碼，意味著信源消息概率分布q(xm)必須有(hm為整數(shù))的形式，直接取各消息碼字的碼長nm等于q(xm)所對應(yīng)的指數(shù)hm即可。這就是[例3.8]所例舉的情況，在[例3.8]中，信源分布可以表示為取信源各消息相應(yīng)的碼字的碼長等于其分布概率所對應(yīng)的指數(shù)，即n0=2n1=2n2=3n3=3n4=4n5=4n6=4n7=4得到的信源編碼就是緊致碼（最佳碼）。[定理3.3]說明，只有滿足否則惟一可譯碼不存在。但平均碼長應(yīng)該小于，這是按應(yīng)盡可能短的要求，這時得到的碼是最佳碼，其實，也能找到惟一可譯碼。

，才能構(gòu)成惟一可譯碼，【例3.10】

信源對信源進(jìn)行二進(jìn)制變長編碼，D=2，信源各消息概率恰好表示成D=2的整數(shù)次冪，取碼長等于其冪次，即取n1=1n2=2n3=3n4=3對信源各消息編碼，得到的碼就是緊致碼，下面計算RD。（碼元/符號）因為信息傳輸率RD的值小于等于1，所以上述RD=1達(dá)到最大值，得到的碼集為緊致碼。（比特/碼元時間）【例3.11】對下述信源進(jìn)行二進(jìn)制變長編碼，

根據(jù)式(3-20)，即碼長nm

應(yīng)滿足tm

nm<

tm

+1

，tm是消息xm（m=1，2，3，4，5）的2次冪概率所對應(yīng)的冪次，取{x1,x2,x3,x4,x5}所對應(yīng)的碼字的碼長分別為n1=3n2=4n3=2n4=3

n5=2，計算出平均碼長熵

=2.228（比特/符號）

滿足式(3-19)

則有

定理3.4

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

給定熵為H（X）的離散無記憶信源，其L次擴(kuò)展信源的熵記為H（X），給定有D個元素的碼符號集，對擴(kuò)展信源進(jìn)行編碼，總可以找到一種惟一可譯碼，使碼長滿足(3-23)

定理3.3推廣到L次擴(kuò)展信源，就得到如下定理，即Shannon第一定理記為信源每個符號所對應(yīng)的平均碼字?jǐn)?shù)，則式(3-23)為

（3-24）

Shannon第一定理的物理意義在于：對信源進(jìn)行編碼，使編碼后的碼集中各碼字盡可能等概分布，如果將這碼集看成為一個新的信源，這時新信源所含信息量最大。定義編碼效率(3-26)η是一個無量綱的數(shù)，一般情況下η<1，在極限情況下η=1。講書上例子3.12,3.13,P66對于同一種信源，三種編碼法中以香農(nóng)編碼法的編碼效率最低，費(fèi)諾編碼法也不是一種最佳編碼法，但用這種方法有時候也能找到緊致碼。一般情況下，霍夫曼編碼法得到的平均碼長最短，即編碼效率最高。3.4變長碼的編碼方法香農(nóng)（Shannon）編碼法費(fèi)諾(Fano)編碼法霍夫曼(Huffman)編碼法變長編碼法：705.2無失真信源編碼最佳變長編碼

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

715.2無失真信源編碼能獲得最佳碼的編碼方法主要有：香農(nóng)（Shannon）費(fèi)諾（Fano）哈夫曼（Huffman）等

725.2無失真信源編碼香農(nóng)（Shannon）編碼1.將信源消息符號按其出現(xiàn)的概率大小依次排列2.確定滿足下列不等式的整數(shù)碼長Ki。735.2無失真信源編碼為了編成唯一可譯碼，計算第i個消息的累加概率將累加概率Pi變換成二進(jìn)制數(shù)。取Pi二進(jìn)數(shù)的小數(shù)點后Ki位即為該消息符號的二進(jìn)制碼字。745.2無失真信源編碼例設(shè)信源共7個符號消息，其概率和累加概率如下表所示。---后面有題目

【例3.14】對給定信源

進(jìn)行D=2進(jìn)制香農(nóng)編碼。消息符號ai消息概率qi-log2qi碼長ni累加概率碼字cia10.22.3430000a20.192.4130.2001a30.182.4830.39011a40.172.5630.57100a50.152.7430.74101a60.103.3440.891110a70.016.6670.991111110

表3-8香農(nóng)編碼

765.2無失真信源編碼信源消息符號ai符號概率(ai)累加概率Pi-logp(ai)碼字長度Ki碼字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.170.572.563100a50.150.742.743101a60.100.893.3241110a70.010.996.6471111110以消息x5為例，對其進(jìn)行編碼：計算出-logq(x5)=-log0.15=2.74，取整數(shù)n5=3作為x5的碼字的碼長，計算出消息x1,x2,x3,x4累加概率將0.74變換成二進(jìn)制小數(shù)(0.74)10=(0.1011110)2，取小數(shù)點后面三位101作為x5的代碼。

計算該編碼的編碼效率

先算出信源熵=2.61(比特/符號)平均碼長=3.14(比特/符號)則編碼效率

785.2無失真信源編碼以i=4為例，復(fù)習(xí)上一次課的主要內(nèi)容一、平均碼長的計算二、等長編碼定理三、變長編碼定理(Shannon第一定理)3.1.3平均碼長的計算

對于變長碼，碼集C的平均碼長，用符號表示，定義為碼C中每個碼字cm(m=1,2,…，M)其碼長的概率加權(quán)平均值為 (3-1)式中nm是碼字cm所對應(yīng)的碼字的長度，p(cm

)是碼字cm出現(xiàn)的概率。對于等長碼，由于碼集C中的每個碼字的碼長都相同，平均碼長就等于每個碼字的碼長3.1.4信息傳輸速率信道的信息傳輸速率為信道單位時間內(nèi)所傳輸?shù)膶嶋H信息量。若信息量以比特為單位，時間以秒為單位，則信息傳輸率定義為： (比特/秒)(3-3)若信息量以比特為單位，時間以碼元時間（傳輸一個碼符號的時間）為單位，則信息傳輸率記為

(比特/碼元時間) (3-4)

為編碼后的平均碼長；H(X)為信源熵；式中：t為傳輸一個碼符號的時間?？梢钥闯?，越小，則越大，信息傳輸率就越高，因此我們感興趣的碼是使平均碼長最短的碼。信源S共有q=4個信源符號，s1,s2,s3,s4,現(xiàn)進(jìn)行二元等長編碼，其中碼符號個數(shù)r=2，則根據(jù)5.1式可知，存在唯一可譯等長碼的條件是碼長l必須不小于2如果N=1，則，則與前面的5.1式一樣。l/N是平均每個信源符號所需要的碼符號個數(shù)，表明對于等長唯一可譯碼，每個信源符號至少需要用個碼符號來變換,也就是說，每個信源符號所需最短的碼長為個。當(dāng)r=2（二元碼）時，logr=1.則式5.2成為這結(jié)果表明，對于二元等長唯一可譯碼，每個信源符號至少需要用logq個二元符號來變換，也表明對信源進(jìn)行二元等長不失真編碼時，每個信源符號所需碼長的極限值為logq個。定理3.1

等長編碼定理

設(shè)離散無記憶信源S={x1

，x2

，…，xk}的熵為H（X），S的L維擴(kuò)展信源為，對信源輸出的L長序列si，i=1,2,…,KL進(jìn)行等長編碼，碼字是長度為n的D進(jìn)制符號串，當(dāng)滿足條件，則L→∞時，可使譯碼差錯pe<δ(ε、δ為無窮小量)；反之，當(dāng) 時，則不可能實現(xiàn)無差錯編碼。定理3.1

等長編碼定理編碼效率定理3.1要求，即，可看出比值是一個小于1的無量綱純數(shù)，定義它為等長編碼的編碼效率，記為

（3-7）

定理3.1要求，是為了實現(xiàn)無差錯編碼每個信源符號所需要的最少碼符號數(shù)，這是等長碼編碼時的理論極限。事實上這種幾乎無失真的代價是要求信源序列長L→∞,L大就意味著實現(xiàn)的復(fù)雜性及譯碼的時延加大。n為碼長----lL為信源序列長度---ND碼符號個數(shù)---r3.3變長碼及變長編碼定理

3.3.1變長碼對變長碼的討論是在L足夠大的條件下得到的結(jié)論，當(dāng)L為有限值時，則總會帶來一定程度的失真。對于變長碼，往往在L不是很大的情況下就可編出高效且無失真的碼。對于變長碼，要求整個碼集的平均碼長力求最小，此時編碼效率最高。對于給定信源，使平均碼長達(dá)到最小的編碼方法，稱為最佳編碼，得到的碼集稱為最佳碼。3.3.2克拉夫特不等式定理3.2

D進(jìn)制碼字集合C={c1,c2,…,cM}，碼集中每一cm（m=1,2,…,M）都是一個D進(jìn)制符號串，設(shè)c1,c2,…,cM對應(yīng)的碼長分別是n1,n2,

…,nM

，則存在唯一可譯碼的充要條件是

(3-10)

式（3-10）也稱克拉夫特不等式

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

3.3.3變長編碼定理定理3.3

給定熵為H（X）的離散無記憶信源，及有D個元素的碼符號集，則總可找到一種無失真編碼方法，構(gòu)成惟一可譯碼，其平均碼長滿足： （3-19）[定理3.3]說明，只有滿足否則惟一可譯碼不存在。但平均碼長應(yīng)該小于，這是按應(yīng)盡可能短的要求，這時得到的碼是最佳碼，其實，也能找到惟一可譯碼。

，才能構(gòu)成惟一可譯碼，定理3.4

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

給定熵為H（X）的離散無記憶信源，其L次擴(kuò)展信源的熵記為H（X），給定有D個元素的碼符號集，對擴(kuò)展信源進(jìn)行編碼，總可以找到一種惟一可譯碼，使碼長滿足(3-23)

定理3.3推廣到L次擴(kuò)展信源，就得到如下定理，即Shannon第一定理記為信源每個符號所對應(yīng)的平均碼字?jǐn)?shù)，則式(3-23)為

（3-24）

Shannon第一定理的物理意義在于：對信源進(jìn)行編碼，使編碼后的碼集中各碼字盡可能等概分布，如果將這碼集看成為一個新的信源，這時新信源所含信息量最大。定義編碼效率(3-26)η是一個無量綱的數(shù)，一般情況下η<1，在極限情況下η=1。對于同一種信源，三種編碼法中以香農(nóng)編碼法的編碼效率最低，費(fèi)諾編碼法也不是一種最佳編碼法，但用這種方法有時候也能找到緊致碼。一般情況下，霍夫曼編碼法得到的平均碼長最短，即編碼效率最高。3.4變長碼的編碼方法香農(nóng)（Shannon）編碼法費(fèi)諾(Fano)編碼法霍夫曼(Huffman)編碼法變長編碼法：945.2無失真信源編碼香農(nóng)（Shannon）編碼1.將信源消息符號按其出現(xiàn)的概率大小依次排列2.確定滿足下列不等式的整數(shù)碼長Ki。955.2無失真信源編碼計算第i個消息的累加概率將累加概率Pi變換成二進(jìn)制數(shù)。取Pi二進(jìn)數(shù)的小數(shù)點后Ki位即為該消息符號的二進(jìn)制碼字。例1，對單符號離散信源編二進(jìn)制香農(nóng)碼，并計算其編碼效率。解：①將xi按概率進(jìn)行降序排列xip(xi)pa(xj)ki碼字x10.5x20.3x30.15x40.05②令p(x0)=0，計算第j-1個碼字的累加概率pa(x1)=0pa(x2)=0+0.5=0.5pa(x3)=0.5+0.3=0.8pa(x4)=0.8+0.15=0.95③確定第i個碼字的碼長ki：④將pa(xj)用二進(jìn)制表示，取小數(shù)點后ki位作為xi的碼字pa(x1)=0.0=(0.0)2→0pa(x2)=0.5=(0.10)2→10pa(x3)=0.8=(0.110…)2→110pa(x4)=0.95=(0.11110…)2→11110xip(xi)pa(xj)ki碼字x10.5010x20.30.5210x30.150.83110x40.050.95511110信息傳輸率=1035.2無失真信源編碼費(fèi)諾編碼方法費(fèi)諾編碼屬于概率匹配編碼(1)將信源消息符號按其出現(xiàn)的概率大小依次排列：(2)將依次排列的信源符號按概率值分為兩大組，使兩個組的概率之和近于相同，并對各組賦予一個二進(jìn)制碼元“0”和“1”。1045.2無失真信源編碼(3)將每一大組的信源符號進(jìn)一步再分成兩組，使劃分后的兩個組的概率之和近于相同，并又賦予兩個組一個二進(jìn)制符號“0”和“1”。(4)如此重復(fù)，直至每個組只剩下一個信源符號為止。(5)信源符號所對應(yīng)的碼字即為費(fèi)諾碼。1055.2無失真信源編碼例對以下信源進(jìn)行費(fèi)諾編碼。

消息符號ai各個消息概率p(ai)第一次分組第二次分組第三次分組第四次分組二元碼字碼長Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.011111141065.2無失真信源編碼

碼元/符號

bit/符號

1095.2無失真信源編碼

哈夫曼編碼方法(1)將信源消息符號按其出現(xiàn)的概率大小依次排列，(2)取兩個概率最小的字母分別配以0和1兩個碼元，并將這兩個概率相加作為一個新字母的概率，與未分配的二進(jìn)符號的字母重新排隊。Thesixthweek1105.2無失真信源編碼(3)對重排后的兩個概率最小符號重復(fù)步驟(2)的過程。(4)不斷繼續(xù)上述過程，直到最后兩個符號配以0和1為止。(5)從最后一級開始，向前返回得到各個信源符號所對應(yīng)的碼元序列，即相應(yīng)的碼字?！纠?.15】

對[例3.14]給出的信源進(jìn)行費(fèi)諾編碼

（1）將信源消息分成兩個子集{

x1，x2，x3}和{

x4，x5，x6，x7}，兩個子集的和概率分別為0.2+0.19+0.18=0.57與0.17+0.15+0.10+0.01=0.43，賦予第一個子集碼元“0”，賦予第二個子集碼元“1”；

（2）又將子集分成和概率盡可能接近相等的兩個子集，分別賦予第一個子集碼元“0”，賦予第二個子集碼元“1”；

（3）一直進(jìn)行下去，直到每個子集僅含一個消息為止。

該編碼的編碼效率：[例3.14]中已算出信源熵H（X）=2.61（比特/符號）

平均碼長=2.74則編碼效率：

1125.2無失真信源編碼例對以下信源進(jìn)行哈夫曼編碼

信源符號ai概率p(ai)碼字Wi碼長Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.01011141135.2無失真信源編碼0.20 0.200.260.350.390.611.00.190.190.200.260.350.390.180.180.190.200.260.170.170.180.190.150.150.170.100.110.010101010101011145.2無失真信源編碼

碼元/符號

bit/符號

1215.2無失真信源編碼哈夫曼編碼方法得到的碼并非唯一的每次對信源縮減時，賦予信源最后兩個概率最小的符號，用0和1是可以任意的，所以可以得到不同的哈夫曼碼，但不會影響碼字的長度。1225.2無失真信源編碼對信源進(jìn)行縮減時，兩個概率最小的符號合并后的概率與其它信源符號的概率相同時，這兩者在縮減信源中進(jìn)行概率排序，其位置放置次序是可以任意的，故會得到不同的哈夫曼碼。此時將影響碼字的長度，一般將合并的概率放在上面，這樣可獲得較小的碼方差。1235.2無失真信源編碼例設(shè)有離散無記憶信源1245.2無失真信源編碼信源符號ai概率p(ai)碼字Wi1碼長Ki1碼字Wi2碼長K’i2a10.411002a20.2012102a30.20003112a40.1001040103a50.1001140113

其有兩種哈夫曼編碼方法：1255.2無失真信源編碼0.40.40.40.61.00.20.20.40.40.20.20.20.10.20.10.40.40.40.61.00.20.20.40.40.20.20.20.10.20.101010101010101011265.2無失真信源編碼

碼元/符號

1275.2無失真信源編碼1285.2無失真信源編碼

進(jìn)行哈夫曼編碼時，為得到碼方差最小的碼，應(yīng)使合并的信源符號位于縮減信源序列盡可能高的位置上，以減少再次合并的次數(shù)，充分利用短碼。

1295.2無失真信源編碼哈夫曼碼是用概率匹配方法進(jìn)行信源編碼。哈夫曼碼的編碼方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，充分利用了短碼；縮減信源的最后二個碼字總是最后一位不同，從而保證了哈夫曼碼是即時碼。r進(jìn)制哈夫曼編碼考慮習(xí)題：書P3.18本

章

小

結(jié)

本章討論在不允許失真前提下對信源的編碼，分為兩種情況，等長編碼和變長編碼。等長編碼定理和變長編碼定理分別給出了這兩種情況，在無失真和碼長盡可能短這兩個約束條件下的平均碼長的上界和下界。等長編碼定理

記H（X）為單符號信源熵，L為擴(kuò)展信源輸出序列長度，n為碼字長度，D為碼符號集元素個數(shù)，當(dāng)滿足條件，則L→∞時，可使譯碼差錯pe<δ(ε、δ為無窮小量)；反之，當(dāng)時，則不可能實現(xiàn)無差錯編碼。變長編碼定理(Shannon第一定理)記H（X）為單符號信源熵，L為擴(kuò)展信源輸出的序列長度，為信源每個符號所對應(yīng)的平均碼字?jǐn)?shù)，D為碼符號集元素個數(shù)，則對信源進(jìn)行編碼，總可以找到一種惟一可譯碼，使碼長滿足平均碼長

克拉夫特不等式

本章還介紹了常見的三種變長碼的編碼方法：香農(nóng)編碼法、Fano編碼法和霍夫曼編碼法。對于同一信源的編碼，三種方法中，以霍夫曼編碼的編碼效率最高。香農(nóng)編碼法沒有太多實用價值，但它在證明變長編碼定理時起了重要作用，F(xiàn)ano編碼法是遵照變長編碼定理（香農(nóng)第一定理）的指導(dǎo)思想導(dǎo)出的一種編碼方法。

作業(yè)：書P3.18復(fù)習(xí)上次課的內(nèi)容：編碼器碼的分類等長編碼定理變長編碼定理(Shannon第一定理)變長碼的編碼方法復(fù)習(xí)上次課的內(nèi)容：碼的分類

1.二元碼：若碼符號集為{0，1}，則碼字就是二元序列，稱為二元碼；2.等長碼：碼中所有碼字的長度，都相同；3.變長碼：碼中的碼字長短不一；4.奇異碼：若一組碼中有相同的碼字，則稱為奇異碼；5.非奇異碼：若一組碼中所有碼字都不相同。6.原碼C的N次擴(kuò)展碼7.惟一可譯碼：如果碼的任意N次擴(kuò)展碼都是非奇異碼，則稱該碼為惟一可譯碼。8.即時碼:無需考慮后續(xù)的碼符號就可以從碼符號序列中譯出碼字，這樣的唯一可譯碼稱為即時碼。9.同價碼：每個碼符號所占的傳輸時間都相同的碼。10.分組碼將信源符號集中的每個信源符號固定地映射成一個碼字Wi，這樣的碼稱為分組碼。定理3.1

等長