信息論與編碼-第六章

第六章無(wú)失真信源編碼

信源信源編碼信道編碼信道譯碼信源譯碼信宿信道第一節(jié)單義可譯碼

信源編碼：就是在輸入信道之前，用信道能傳輸?shù)姆?hào)集，即信道的輸入符號(hào)集作為碼符號(hào)集，用碼符號(hào)集中的碼符號(hào)，對(duì)信源的每一種不同的符號(hào)進(jìn)行編碼，構(gòu)成由碼符號(hào)組成的序列，即碼字。一個(gè)碼字代表信源的一種符號(hào)。因?yàn)槊恳粋€(gè)碼字都是由信道能夠傳遞符號(hào)組成的符號(hào)序列，都能通過信道，所以，每一個(gè)碼字所代表的信源的符號(hào)必能通過信道，使信源適合與信道的傳輸。

信源編碼編出的每一種碼字要與信源發(fā)出的每一種不同的符號(hào)一一對(duì)應(yīng)，而且同時(shí)還要求信源的N個(gè)符號(hào)組成的序列所代表的消息，與相對(duì)應(yīng)的碼字組成的碼字序列也必須一一對(duì)應(yīng)。只有這樣，才能保證任何一個(gè)碼字或碼字序列唯一地翻譯成相對(duì)應(yīng)的信源的符號(hào)或符號(hào)序列，達(dá)到無(wú)失真?zhèn)鬟f信源發(fā)出的消息的目的。無(wú)失真信源編碼必須具有這種單義可譯性。單義可譯的碼稱為單義可譯碼。

第二節(jié)非延長(zhǎng)碼及其構(gòu)成

沒有任何一個(gè)碼字是另一個(gè)碼字的延長(zhǎng)。這就是即時(shí)碼W(5)在結(jié)構(gòu)上的特點(diǎn)，所以，從結(jié)構(gòu)的角度，即時(shí)碼又稱為非延長(zhǎng)碼。非延長(zhǎng)碼是單義可譯碼的一類子碼。非延長(zhǎng)碼一定單義可譯。反之，單義可譯碼不一定都是非延長(zhǎng)碼。有些延長(zhǎng)碼亦單義可譯。

由于非延長(zhǎng)碼單義可譯，而且又能即時(shí)譯碼，所以無(wú)失真信源編碼中經(jīng)常采用這種碼，我們經(jīng)常采用“樹突法”構(gòu)造非延長(zhǎng)碼。非延長(zhǎng)碼的信源符號(hào)、碼符號(hào)集碼符號(hào)數(shù)以及個(gè)碼字的碼長(zhǎng)這三種結(jié)構(gòu)參數(shù)之間，存在著內(nèi)在的約束關(guān)系。這就是說，能否編出非延長(zhǎng)碼，取決于對(duì)編碼的結(jié)構(gòu)要求。

第三節(jié)單義可譯定理

設(shè)信源的符號(hào)集；碼符號(hào)集；個(gè)碼字長(zhǎng)度分別為。則存在單義可譯碼的充分必要條件是滿足克拉夫不等式，即

通過對(duì)定理的必要性和充分性的證明，得到：由定理的必要性，任何一個(gè)結(jié)構(gòu)為的單義可譯碼，一定滿足Kraft不等式；由定理的充分性，滿足Kraft不等式的，至少可構(gòu)成一種結(jié)構(gòu)為的非延長(zhǎng)碼。所以，我們可得到一個(gè)重要結(jié)論：任一單義可譯碼均可由一個(gè)結(jié)構(gòu)相同（與單義可譯碼相同）的非延長(zhǎng)碼來代替。因此，對(duì)單義可譯碼的討論，就可側(cè)重于對(duì)非延長(zhǎng)碼的討論了。

第四節(jié)平均碼長(zhǎng)與有效性

要討論通信的有效性問題，首先要解決如何估量無(wú)噪信道中每一碼符號(hào)攜帶信息量的多少問題，也就是要解決衡量有效性高低的標(biāo)準(zhǔn)問題。為此，必須引入有關(guān)“平均碼長(zhǎng)”的概念。設(shè)信源的信源空間為且有若對(duì)此信源用無(wú)噪信道輸入符號(hào)集，即碼符號(hào)集進(jìn)行單義可譯碼編碼，其單義可譯碼的碼字的長(zhǎng)度為，且與信源符號(hào)一一對(duì)應(yīng)。

一個(gè)信源符號(hào)所需的平均碼符號(hào)數(shù)，就應(yīng)該等于個(gè)碼字長(zhǎng)度在信源的概率空間中的統(tǒng)計(jì)平均值，即這個(gè)平均值（碼符號(hào)/信源符號(hào)）稱為非延長(zhǎng)碼的平均碼長(zhǎng)。另一方面，待信源是給定的，信源每一個(gè)信源符號(hào)所含有的平均信息量，就等于信源的信息熵其值是固定不變的。

由以上兩式可得，非延長(zhǎng)碼每一個(gè)碼符號(hào)所攜帶的平均信息量，即碼的信息傳輸率（又稱碼率）為碼率體現(xiàn)非延長(zhǎng)碼在無(wú)噪信道中傳輸信息的有效性的高低。越大，表示每一個(gè)碼符號(hào)攜帶的平均信息量越多，即有效性越高；越小，表示每一個(gè)碼符號(hào)攜帶的平均信息量越少，即有效性越低。

在無(wú)失真前提下，還要求有較高的有效性的話，則在編碼時(shí)，不僅要使結(jié)構(gòu)參數(shù)滿足Kraft不等式，而且還要考慮個(gè)碼長(zhǎng)（即相應(yīng)的碼字）與信源的概率空間中個(gè)概率分量（即相應(yīng)的信源符號(hào)）之間的合理搭配，充分利用和挖掘信源的統(tǒng)計(jì)特性的潛力，使其平均碼長(zhǎng)盡量小。

要使非延長(zhǎng)碼的平均碼長(zhǎng)盡量小，使無(wú)失真信源編碼盡量有效，必須遵循碼字長(zhǎng)度與信源概率空間的概率分量之間的正確搭配原則：概率大（經(jīng)常出現(xiàn)）的信源符號(hào)盡量賦于碼長(zhǎng)小的碼字（短碼）；概率?。ú唤?jīng)常出現(xiàn)）的信源符號(hào)盡量附于碼長(zhǎng)大的碼字（長(zhǎng)碼）。采取這樣的搭配原則，才能充分利用和挖掘信源統(tǒng)計(jì)特性的潛力，提高無(wú)失真信源編碼的有效性。

第五節(jié)平均碼長(zhǎng)的界限定理引言:

碼字的信息傳輸率(碼率)為

.比特/碼符號(hào)碼率R越大，表示每一個(gè)碼符號(hào)攜帶的平均信息量越多，即有效性越高；R越小，表示每一個(gè)碼符號(hào)攜帶的平均信息量越少，即有效性越多低。

而平均碼長(zhǎng)為碼符號(hào)/信源符號(hào),

所以,平均碼長(zhǎng)越小則每一個(gè)碼符號(hào)攜帶的平均信息量越多，即有效性越高.在進(jìn)行無(wú)失真信源編碼時(shí)，若要使有效性最高，不僅要使結(jié)構(gòu)參數(shù)滿足Kraft不等式,還要考慮q個(gè)碼長(zhǎng)與信源S的信源概率空間P中的q個(gè)概率分量之間的合理搭配，充分利用和挖掘信源的統(tǒng)計(jì)特性的潛力，使平均碼長(zhǎng)盡量小。

若離散無(wú)記憶信源的信息熵為，碼符號(hào)集，如要求的q個(gè)碼字長(zhǎng)度為，且滿足Kraft不等式。則總找到一種單義可譯碼，使其平均碼長(zhǎng)滿足這就是平均碼長(zhǎng)的界限定理。以下分別對(duì)其下界和上界給予證明。下界的證明：設(shè)離散無(wú)記憶信源S的信源空間為且有要證只需證

根據(jù)平均碼長(zhǎng)定義以及信源信息熵的定義得：利用上凸函數(shù)的性質(zhì)得到由于非延長(zhǎng)碼滿足Kraft不等式，即所以證得即由于當(dāng)且僅當(dāng)?shù)仁讲懦闪?，即?/p>

當(dāng)且僅當(dāng)信源符號(hào)和概率分布滿足時(shí)，平均碼長(zhǎng)才能達(dá)到下界值。當(dāng)平均碼長(zhǎng)達(dá)到最小值時(shí)，這種碼應(yīng)該是最有效的無(wú)失真信源編碼，稱它為最佳碼。新問題：若平均碼長(zhǎng)小于下界值，會(huì)出現(xiàn)什么結(jié)果呢？

我們運(yùn)用反證法進(jìn)行證明，假設(shè)有根據(jù)平均碼長(zhǎng)和信息熵定義得整理并移項(xiàng)得

即因?yàn)橛胁坏仁?，現(xiàn)令由不等式可得可得所以

這時(shí)，結(jié)構(gòu)參數(shù)不滿足Kraft不等式時(shí)，不能構(gòu)成單義可譯碼。結(jié)論：?jiǎn)瘟x可譯碼的平均碼長(zhǎng)一定不小于下界值；凡是平均碼長(zhǎng)小于下界值的碼，一定不能構(gòu)成單義可譯碼。

我們運(yùn)用換底公式可得：

所以，單義可譯碼的平均碼長(zhǎng)的下界值在數(shù)量上取決于給定信源的信息熵。信源給定，其熵值隨之確定，該信源的無(wú)失真信源編碼的平均碼長(zhǎng)的也就隨之確定了，無(wú)失真信源編碼的有效性的最高限度也就確定了。如不改變碼字所代表的對(duì)象，只靠改變編碼方法來繼續(xù)提高有效性，已無(wú)潛力可挖。如要進(jìn)一步提高編碼有效性，勢(shì)必對(duì)編碼對(duì)象，即信源本身作文章，進(jìn)一步挖掘信源本身的潛力。上界的證明：在區(qū)間取碼長(zhǎng)，則有進(jìn)而有即所以進(jìn)行對(duì)數(shù)變換得：取各項(xiàng)倒數(shù)有取和可得

既然，在上述區(qū)間選擇時(shí)，結(jié)構(gòu)參數(shù)滿足Kraft不等式，可構(gòu)成非延長(zhǎng)碼。所以，可用乘不等式兩邊得：所以，

上界定理得證。

結(jié)論：平均碼長(zhǎng)在不超過其上界值的情況下，就可以構(gòu)成非延長(zhǎng)碼。但這并不意味著平均碼長(zhǎng)超過上界值時(shí)就不能構(gòu)成非延長(zhǎng)碼，只是因?yàn)槲覀兛偸窍Ｍ骄a長(zhǎng)能夠盡量小。在一般情況下，在構(gòu)成非延長(zhǎng)碼時(shí)，沒有必要使平均碼長(zhǎng)大于其上界值。而決定能否構(gòu)成非延長(zhǎng)碼的關(guān)鍵是結(jié)構(gòu)參數(shù)必須滿足Kraft不等式。所以，平均碼長(zhǎng)的下界值定理才是關(guān)鍵。問題：如要進(jìn)一步降低非延長(zhǎng)碼的平均碼長(zhǎng)，提高無(wú)失真信源編碼的有效性，單靠改善編碼方法，已無(wú)潛力可挖。要進(jìn)一步提高有效性，必須把我們的注意力轉(zhuǎn)向信源本身，通過改變信源的熵值的途徑，進(jìn)一步挖掘信源本身的潛力。第六節(jié)信源擴(kuò)展與數(shù)據(jù)壓縮舊的編碼方式：將單個(gè)信源符號(hào)作為編碼對(duì)象。新的編碼方法：我們可以在構(gòu)成非延長(zhǎng)碼時(shí)，直接把消息作為編碼對(duì)象，使一個(gè)完整的碼字不對(duì)應(yīng)單個(gè)信源符號(hào)，而直接對(duì)應(yīng)一個(gè)消息，使碼字與一一對(duì)應(yīng)。以下，就對(duì)信源的無(wú)記憶和有記憶兩種情況，在運(yùn)用這種編碼方式時(shí)平均碼長(zhǎng)的變化進(jìn)行討論。（一）無(wú)記憶信源設(shè)離散無(wú)記憶信源S的信源空間為且則信源S的熵H(S)是確定的，它是

由信源S的信源空間可得信源S的N次擴(kuò)展信源的信源空間為其中所以，有所以N次擴(kuò)展信源的熵也是確定的，它是現(xiàn)在直接對(duì)N次擴(kuò)展信源的每一個(gè)“大符號(hào)”，即消息進(jìn)行一一對(duì)應(yīng)的無(wú)失真編碼，構(gòu)成非延長(zhǎng)碼。

令表示N次擴(kuò)展信源的平均碼長(zhǎng)，則的含義應(yīng)該是N個(gè)信源符號(hào)所需的平均碼符號(hào)，由平均碼長(zhǎng)的界限定理可得不等式兩邊同乘一1/N得其中為信源每一個(gè)信源符號(hào)所需要的平均碼符號(hào)數(shù)，即平均碼長(zhǎng)。當(dāng)擴(kuò)展次數(shù)，可得所以

且接近程度隨著擴(kuò)展次數(shù)N的增加而增加。所以，可以采用擴(kuò)展信源的手段達(dá)到數(shù)據(jù)壓縮的目的，提高通信的有效性，但編碼的難度將增加。（二）有記憶信源信源S的各維條件概率為

所以可得信源S的N次擴(kuò)展信源的概率分布為且有信源S的N次擴(kuò)展信源的熵為對(duì)于平穩(wěn)遍歷有記憶信源S，當(dāng)每發(fā)一個(gè)信源符號(hào)所含有的平均信息量，即極限熵為

與無(wú)記憶信源同樣，有記憶信源也遵循平均碼長(zhǎng)界限定理，可得由“大符號(hào)”消息的平均碼長(zhǎng)界限定理可以推得信源符號(hào)的平均碼長(zhǎng)界限定理，并且當(dāng)時(shí)所以即得所以，直接把信源S的N次擴(kuò)展信源的“大符號(hào)”（消息）作為編碼對(duì)象，進(jìn)行一一對(duì)應(yīng)的編碼，編出的非延長(zhǎng)碼的平均碼長(zhǎng)，將隨著擴(kuò)展次數(shù)N的增加，可無(wú)限接近于已知可得即可得所以

由于考慮了N次擴(kuò)展信源中N個(gè)隨機(jī)變量之間的統(tǒng)計(jì)依賴關(guān)系，挖掘并利用了有記憶信源S各時(shí)刻隨機(jī)變量之間的依賴關(guān)系對(duì)減少碼符號(hào)數(shù)，提高通信有效性的潛力，所以其平均碼長(zhǎng)下界值，比不考慮各時(shí)刻隨機(jī)變量之間的統(tǒng)計(jì)依賴關(guān)系的無(wú)記憶信源S的N次擴(kuò)展信源的平均碼長(zhǎng)的下界值，又有了進(jìn)一步的減少。特別當(dāng)平穩(wěn)遍歷有記憶信源S是m階Markov信源時(shí)，m階Markov信源的極限熵就是m階條件熵，即其平均碼長(zhǎng)的極限值又因?yàn)樗?，每一信源符?hào)所需要的平均符號(hào)數(shù)（平均碼長(zhǎng)）可無(wú)限接近其下界，而下界值又隨記憶長(zhǎng)度m的增大而減小，記憶長(zhǎng)度m越長(zhǎng)，每一信源符號(hào)所需的平均符號(hào)數(shù)（平均碼長(zhǎng)）的下界值就越小，數(shù)據(jù)壓縮的程度就越大，無(wú)失真信源編碼的有效性就越高。第七節(jié)無(wú)失真信源編碼定理

無(wú)失真信源編碼定理，以無(wú)失真信源編碼在無(wú)噪信道中每單位時(shí)間通過的信源符號(hào)數(shù)（碼字?jǐn)?shù)），即碼速度為有效性的衡量測(cè)度，論述無(wú)失真信源編碼有效性的限度。設(shè)離散無(wú)記憶信源S的熵為，離散無(wú)噪信道的信道容量為。則信源S的無(wú)失真信源編碼在無(wú)噪信道上的碼速度的限度為每秒個(gè)信源符號(hào)（其中是任意小的正數(shù)）。要使碼速度大于是不可能的。注意：1、區(qū)分信道傳輸率（碼率）與信道的平均信息傳輸速率（碼速率）；2、信道容量與信道的最大平均信息傳輸率（最大碼速率）；3、特別是各個(gè)變量的單位。證明：無(wú)噪信道每一碼符號(hào)傳輸?shù)钠骄畔⒘浚葱诺赖男畔鬏斅剩ùa率）由于離散無(wú)記憶信源S的無(wú)失真信源編碼的平均碼長(zhǎng)可無(wú)限接近于下界值所以，當(dāng)時(shí)，有有r個(gè)輸入符號(hào)的離散無(wú)噪信道的信道容量綜合上面兩式得這表明，無(wú)失真信源編碼編出的非延長(zhǎng)碼，每一碼符號(hào)所攜帶的平均信息量（碼率），即無(wú)噪離散信道的平均信息傳輸率可以無(wú)限接近，但不能超過無(wú)噪信道的容量。

若離散無(wú)噪信道每傳遞一個(gè)碼符號(hào)需要t秒時(shí)間，則離散無(wú)噪信道在每秒時(shí)間內(nèi)能傳輸?shù)钠骄畔⒘?，即信道的平均信息傳輸速率（碼速率）同樣由信道容量的定義，可得離散無(wú)噪信道在每秒時(shí)間內(nèi)，能傳輸?shù)淖畲笃骄畔⒘?，即信道的最大平均信息傳輸率（最大碼速率）當(dāng)，得

由離散無(wú)噪信道在單位時(shí)間（每秒）內(nèi)傳遞的信源符號(hào)數(shù)，也就是碼速度當(dāng)時(shí)，得若令為任意小的正數(shù)，則所以定理得證。

這表明，在無(wú)失真信源編碼中，采用擴(kuò)展信源的手段，雖然可以減少每一信源符號(hào)所需要的平均碼符號(hào)數(shù)，使編碼的有效性有所提高。但無(wú)論怎樣擴(kuò)展，無(wú)失真信源編碼編出的非延長(zhǎng)碼，在無(wú)噪離散信道中傳輸?shù)挠行允怯幸欢ǖ南薅鹊摹Ｒ部梢詫⑸鲜龆ɡ硗茝V到平穩(wěn)遍歷有記憶信源的情況。設(shè)平穩(wěn)遍歷有記憶信源S的極限熵為，離散無(wú)噪信道的信道容量為。則信源S的無(wú)失真信源編碼在離散無(wú)噪信道上的平均信息傳輸速率的限度為每秒個(gè)信源符號(hào)（其中是任意小的正數(shù)）。要使平均信息傳輸速率大于是不可能的。證明：無(wú)失真信源編碼的平均碼長(zhǎng)的極限值為而無(wú)失真信源編碼在離散無(wú)噪信道中的信息傳輸率，也就是碼率R的極限值由離散無(wú)噪信道的容量，有

則無(wú)失真信源編碼在離散無(wú)噪信道上的平均信息傳輸速率，也就是碼速率的極限值所以，離散無(wú)噪信道在單位時(shí)間內(nèi)傳遞的信源符號(hào)數(shù)，用碼速度表示，則有若令為任意小的正數(shù)，則

將平穩(wěn)遍歷有記憶信源的極限熵與離散無(wú)記憶信源的信息熵比較得：所以，比較兩者的碼速度可得到

這表明，在采用擴(kuò)展信源的辦法，來提高通信有效性的過程中，考慮信源發(fā)出符號(hào)之間的統(tǒng)計(jì)依賴關(guān)系，比不考慮信源發(fā)出符號(hào)之間的統(tǒng)計(jì)依賴關(guān)系時(shí)的有效性要高。無(wú)失真信源編碼定理，就是香農(nóng)第一定理。又因?yàn)橐M(jìn)行無(wú)失真?zhèn)鬏?，在無(wú)失真信源編碼后，必須接入無(wú)噪信道.所以,無(wú)失真信源編碼定理,也稱為無(wú)噪離散信道編碼定理。

比特/符號(hào)數(shù)信道的信息傳輸率（碼率）比特/符號(hào)數(shù)信道容量（即信道的最大信息傳輸率）比特/秒信道的平均信息傳輸速率（碼速率）比特/秒信道的最大平均信息傳輸速率（最大碼速率）信源符號(hào)/秒信道在單位時(shí)間內(nèi)傳遞的信源符號(hào)數(shù)（碼速度）

無(wú)失真信源編碼定理（香農(nóng)第一定理）是一個(gè)極限定理，它指出了單義可譯的非延長(zhǎng)碼的平均碼長(zhǎng)可無(wú)限接近極限值，無(wú)噪信道在傳輸無(wú)失真信源編碼的碼符號(hào)時(shí)，信息傳輸率可無(wú)限接近信道容量的美好前景但定理本身并沒有給出如何構(gòu)造這種有效碼的方法。第八節(jié)霍夫曼（Huffman）有效碼1952年，霍夫曼（Huffman）提出了一種無(wú)失真信源編碼的方法。這種編碼方法，根據(jù)給定信源的信源空間和規(guī)定的碼符號(hào)集，合理利用信源的統(tǒng)計(jì)特性，構(gòu)造出單義可譯的非延長(zhǎng)碼，并具有盡可能小的平均碼長(zhǎng)，使無(wú)失真信源編碼具有較高的有效性。為此，用霍夫曼編碼編出的碼通常稱之為有效碼。霍夫曼編碼方法：若以為碼符號(hào)集，用霍夫曼編碼方法，對(duì)信源空間為（其中：）的離散無(wú)記憶信源，進(jìn)行無(wú)失真信源編碼的具體步驟是：（1）把個(gè)信源符號(hào)按其概率分布的大小，以遞減次序，由大到小，自上至下排成一列；

（2）對(duì)處于最下面的概率最小的個(gè)信源符號(hào)，一一對(duì)應(yīng)地分別賦于碼符號(hào)。把這個(gè)概率最小的信源符號(hào)相應(yīng)的概率相加，所得和值用一個(gè)虛擬符號(hào)代表，與余下的個(gè)信源符號(hào)組成含有個(gè)符號(hào)的第一次縮減信源；（3）縮減信源中的符號(hào)，仍按其概率大小，以遞減次序，由小到大，自上至下排列。對(duì)處于最下面的個(gè)概率最小的符號(hào)，按步驟（2）中的同樣順序，一一對(duì)應(yīng)地分別賦于碼符號(hào)。把這個(gè)概率最小的符號(hào)相應(yīng)的概率相加，所得和值用一個(gè)虛擬符號(hào)代表，與余下的個(gè)符號(hào)組成含有個(gè)符號(hào)的第二次縮減信源；

（4）按照以上方法，依次繼續(xù)下去。每次縮減所減少的符號(hào)數(shù)是，縮減到第次時(shí)，總共減少的符號(hào)數(shù)是，第次縮減信源含有的符號(hào)數(shù)是。當(dāng)縮減信源含有符號(hào)數(shù)大于碼符號(hào)集碼符號(hào)數(shù)時(shí)，縮減過程繼續(xù)進(jìn)行下去；（5）當(dāng)?shù)诖慰s減信源中所含符號(hào)數(shù)正好等于碼符號(hào)集碼符號(hào)數(shù)，即有時(shí)，表明縮減過程已到最后一次，對(duì)這最后余下的個(gè)符號(hào)，按以前的同樣順序，一一對(duì)應(yīng)地分別賦于碼符號(hào)。最后余下的這個(gè)符號(hào)的概率之和，必定等于1。

（6）從最后賦于的碼符號(hào)開始，沿著每一信源符號(hào)在各次縮減過程中得到碼符號(hào)的行進(jìn)路線向前返回，達(dá)至每一信源符號(hào)。按前后次序，把返回路途中所遇到的碼符號(hào)排成碼符號(hào)序列。這個(gè)碼符號(hào)序列，就是返回路線終點(diǎn)信源符號(hào)相應(yīng)的碼字。到此，完成編碼過程。（7）若第次縮減信源含有符號(hào)數(shù)小于碼符號(hào)集碼符號(hào)數(shù)，即則必須中止縮減過程。在原來按概率大小，以遞減次序，由大到小，自上而下排列的信源符號(hào)列隊(duì)下面，增添個(gè)概率為零（實(shí)際上不用的）虛假信源符號(hào)。正整數(shù)等于碼符號(hào)集碼符號(hào)數(shù)，與第次縮減信源含有的符號(hào)數(shù)的差值，即。

的新信源。按照前面所講的步驟對(duì)新信源進(jìn)行縮減。對(duì)最后余下的個(gè)符號(hào)，一一對(duì)應(yīng)地分別賦于碼符號(hào)。然后，按步驟（6）得到新信源各符號(hào)相應(yīng)的碼字：。其中，前個(gè)碼字是我們所需要的，后個(gè)碼字概率為零的虛假碼字，我們可以丟掉不用。最終，我們所編的碼，就是由所組成的碼。這樣，就完成了編碼全過程。此時(shí)，信源原有的個(gè)符號(hào)與增添的個(gè)虛假符號(hào)組成符號(hào)數(shù)為信源空間為霍夫曼編碼方式信源符號(hào)sis1s2s3s4s5得霍夫曼碼其平均碼長(zhǎng)

信源符號(hào)sis1s2s3s4s5另一種霍夫曼編碼方式最終，得霍夫曼碼信源符號(hào)相應(yīng)的碼字為其平均碼長(zhǎng)

兩種霍夫曼編碼的不同之處僅僅在于碼長(zhǎng)相同的兩種碼字的碼符號(hào)序列形式不同。由此可見，同一信源的霍夫曼碼的形式不是唯一的。

在遵循“縮減信源中的符號(hào)按其概率大小，以遞減次序，由大到小，自上至下排列”這個(gè)原則的前提下，各次縮減所得的虛擬符號(hào)可能有多于1個(gè)合適的位置。合適位置的不同選擇，也會(huì)導(dǎo)致構(gòu)成結(jié)構(gòu)相同、有效性相同，而形式不同的多種霍夫曼碼。

驗(yàn)證可知，本題不滿足上述的關(guān)系，所以需要增加概率為零的虛擬符號(hào)，因?yàn)?，所以，?dāng)時(shí)，，需增加的符號(hào)數(shù)為：編碼過程如下表碼長(zhǎng)碼字信源符號(hào)概率第一次縮減第二次縮減

0.5411s1

0.24

0.240.24200s2

0.20

0.22

0.22201s3

0.18

0.20

202s4

0.16

0.18

220s5

0.14

0.16

221s60.08

222s1

0

由霍夫曼編碼得出的碼長(zhǎng)求得平均碼長(zhǎng)：

若不設(shè)置一個(gè)概率為零的虛擬信號(hào)，直接對(duì)含有6個(gè)信源符號(hào)的原信源進(jìn)行霍夫曼編碼，如下表:碼長(zhǎng)碼字信源符號(hào)概率第一次縮減第二次縮減

2100.24

0.38

0.382100.20

0.24

2120.18

0.20

2200.16

0.18

2210.14

2220.08

根據(jù)上述表中求出的碼長(zhǎng)得出平均碼長(zhǎng)：0.62

從以上兩個(gè)表中可以看出：直接對(duì)含有6個(gè)信源符號(hào)的原信源進(jìn)行霍夫曼編碼，在最后一次縮減信源賦于的碼符號(hào)“0”構(gòu)成的碼長(zhǎng)為1的最短碼字就不可能代表概率最大的信源符號(hào)，碼長(zhǎng)為1的最短碼字沒有得到合理而充分的利用。相反，把碼長(zhǎng)為最長(zhǎng)的碼字不合理地給了信源符號(hào)，所以導(dǎo)致平均碼長(zhǎng)增大，其有效性下降?；舴蚵a是非延長(zhǎng)碼

以[例6.1]為例，以霍夫曼編碼縮減過程的終點(diǎn)作為“樹根”，以碼符號(hào)集碼符號(hào)數(shù)r=2作為“分枝”數(shù)，經(jīng)過四次分枝可得具有四階節(jié)點(diǎn)的“碼樹”，可知，賦于各信源符號(hào)的碼字都是“碼樹”的“端點(diǎn)”。所以，表6.3所得霍夫曼碼在結(jié)構(gòu)上是非延長(zhǎng)碼。對(duì)于表6.4，同樣可得相應(yīng)的“碼樹”如圖6.7所示。表6.4中的霍夫曼碼的碼字同樣也是圖6.7所示“碼樹”的“端點(diǎn)”。所以，霍夫曼碼在結(jié)構(gòu)上也是非延長(zhǎng)碼。

由以上的實(shí)例分析可知：霍夫曼編碼方法中的逐次縮減過程，實(shí)際上是“碼樹”構(gòu)碼方法中逐級(jí)分枝過程的逆過程；霍夫曼編碼方法對(duì)碼字的構(gòu)成原則，確?；舴蚵a各碼字是“碼樹”的“端點(diǎn)”。因此，霍夫曼碼在結(jié)構(gòu)上是非延長(zhǎng)碼，是單義可譯碼?；舴蚵a是有效碼霍夫曼碼的兩個(gè)特點(diǎn)：保證概率大的信源符號(hào)對(duì)應(yīng)短碼；概率小的信源符號(hào)對(duì)應(yīng)長(zhǎng)碼。而且，所有短碼都得到充分利用；

每次縮減信源中概率最小的r個(gè)符號(hào)對(duì)應(yīng)的碼符號(hào)序列中，總是最后一個(gè)碼符號(hào)不同，前面各位碼符號(hào)均相同。

這兩個(gè)特點(diǎn)保證了霍夫曼碼的平均碼長(zhǎng)是用其它編碼方法編出的結(jié)構(gòu)相同的單義可譯碼的平均碼長(zhǎng)中最小的平均碼長(zhǎng)。即，霍夫曼碼是有效碼。兩種霍夫曼碼的比較信源符號(hào)sis1s2s3s4s5平均碼長(zhǎng)：表6.3信源符號(hào)sis1s2s3s4s5平均碼長(zhǎng)：表6.7

兩種霍夫曼碼的平均碼長(zhǎng)是相等的，由二者的“碼樹”圖可以看出，兩種霍夫曼碼的碼字在“碼樹”上的“端點(diǎn)”的位置不同，這體現(xiàn)了兩種霍夫曼碼的碼字長(zhǎng)度結(jié)構(gòu)的區(qū)別。所以，兩種霍夫曼碼都是非延長(zhǎng)碼，且都是有效碼。A010=w110=w21100=w51101110w4=1101w3=111表一的“碼樹”圖101101001010w(1)=11w(4)=101w(5)=100w(2)=01w(3)=00A10表二的“碼樹”圖101為了區(qū)分兩種方法，我們引入碼長(zhǎng)方差的概念：設(shè)碼中各碼字的長(zhǎng)度分別為，其平均碼長(zhǎng)為。則碼中