《信息論與編碼》課件1第7章

第7章無失真信源編碼

7.1信源編碼的作用與構(gòu)成7.2等長信源編碼的相關(guān)概念和編碼定理7.3變長碼的基本概念7.4變長信源編碼定理7.5最佳編碼定理與統(tǒng)計編碼方法7.6變長編碼基本方法習(xí)題77.1信源編碼的作用與構(gòu)成在一個信息傳輸系統(tǒng)中，信源以輸出符號的形式輸出信息。例如，離散無記憶信源的符號集U={u1,u2,…,un}輸出的符號或消息可以表示字母、數(shù)字、文字等不同的內(nèi)容。然而，某些信息系統(tǒng)對于傳輸、存儲和處理的信息載體的形式有特定的要求。例如，電報通信系統(tǒng)傳輸?shù)氖请妶蟠a，計算機(jī)中可以運行的指令和可以被計算、處理的數(shù)據(jù)必須是二進(jìn)制符號。為了使這些載荷信源信息的各種符號、消息能夠通過某種信息系統(tǒng)傳輸、存儲和處理，信源輸出的符號、消息必須轉(zhuǎn)換為信息系統(tǒng)所要求的信號或碼字形式。因此，從一般意義上講，這種將各種信源輸出的符號、消息轉(zhuǎn)換成特定信息系統(tǒng)所要求的、易于處理的表示形式的過程稱為信源編碼。設(shè)信源符號集為U={u1,u2,…,un}根據(jù)信息系統(tǒng)的要求，我們可以設(shè)計碼符號集：X={x1,x2,…,xi}其中,xi(i=1,2,…,m)適合系統(tǒng)的要求，稱為碼符號或碼元。由若干位碼元（如K位）可以組成一個碼符號序列：Wi=X1X2…XK其中，Xj∈X(j=1,2,…,K)。這樣的碼符號序列Wi亦稱做碼字。由所有碼字構(gòu)成的集合稱為碼本：C={W1,W2,…,Wn}信源編碼實際上是信源符號與碼字之間按照一定規(guī)則進(jìn)行的一種變換處理，即將信源符號集中的符號ui(i=1,2,…,n)變換成長度為K的碼符號序列（碼字）：Wi=X1X2…XK或者將信源輸出的長為L的信源符號序列:與碼本:

中的碼字Wi構(gòu)成某種對應(yīng)關(guān)系。經(jīng)過這樣的變換處理，信源符號ui、信源符號序列U1U2…UL所表示的信源信息就載荷在碼字X1X2…XK中了。信源譯碼是信源編碼的逆過程，即由碼字X1X2…XK通過反變換處理恢復(fù)信源符號ui、信源符號序列U1U2…UL。無失真信源編碼要求譯碼結(jié)果與信源的輸出相比不產(chǎn)生歧義，信源符號或者信源符號序列與碼本中的碼字之間必須構(gòu)成一種一一對應(yīng)的變換關(guān)系。這不但要求每一個信源符號ui和信源符號序列U1U2…UL與碼本中的碼字X1X2…XK具有確定的變換關(guān)系，而且要求由碼符號序列到信源符號序列的反變換即譯碼的結(jié)果也是唯一的，即一串有限長的碼符號序列的譯碼結(jié)果只能是唯一的一串信源符號序列。因此，在無失真信源編碼中，信源符號ui、信源符號序列U1U2…UL與碼字X1X2…XK之間必須具有確定的一一對應(yīng)的變換關(guān)系。圖7-1示出了無失真信源編碼器中信源符號與碼符號序列之間的變換關(guān)系。圖7-1無失真信源編碼器在實際的通信系統(tǒng)和電子信息系統(tǒng)中，我們可以看到多種信源編碼的應(yīng)用實例。電報通信系統(tǒng)中，信源符號集為U={文字，符號}，碼符號集為X={點，畫，間隔}，碼本則是由不同長度的點、畫的組合所構(gòu)成的碼字的集合。電報通信系統(tǒng)的信源編碼通過文字、符號與碼字的一一對應(yīng)的變換處理來完成。在計算機(jī)系統(tǒng)中，C語言編寫的程序由英文字母和符號組成，即U={A,B,…,Z,+,－,…}，而計算機(jī)機(jī)器碼的碼符號集為X={0,1}，通過ASCII的映射關(guān)系將字母、符號組成的計算機(jī)程序編譯連接為二進(jìn)制符號序列。由上述討論可知，信源編碼將信源輸出的符號、消息轉(zhuǎn)換為能夠在信息系統(tǒng)中傳輸、存儲和處理的信號，對于構(gòu)成信息系統(tǒng)具有重要意義。信源編碼器是各類通信系統(tǒng)和電子信息系統(tǒng)研究、開發(fā)中的一項不可缺少的組成部分。對于離散無記憶信源，信源符號等概率分布時，信源輸出的信息量最大，即H0=logn。然而一般信源是非等概分布的，其熵因此，在信源輸出的符號序列中存在一定的信息冗余，即

在信源編碼處理中，信源符號ui和信源符號序列U1U2…UL與碼字X1X2…XK可以有多種對應(yīng)關(guān)系，即可以有多種不同的編碼方式。我們總可以在這些編碼方式中選擇一種最有效的編碼，在將信源符號轉(zhuǎn)換為信息系統(tǒng)要求的信號形式的同時，減小甚至消除信源的信息冗余。由此可知，無失真信源編碼的另一個重要作用就是選擇適當(dāng)?shù)木幋a方法，在不產(chǎn)生信號畸變和失真的條件下，減小或去除信源符號中的冗余成分，提高通信系統(tǒng)和電子信息系統(tǒng)的有效性。信源編碼將信源符號ui或信源符號序列U1U2…UL變換成長度為K的碼字X1X2…XK(Xj∈X,j=1,2,…,K)。這樣的編碼在工程實現(xiàn)中可以分為兩種形式。第一種編碼方法所使用的碼字均由位數(shù)相同的碼符號組合而成，即碼本包含的碼字X1X2…XK中的K是一個不變的常數(shù)。這類碼稱為等長碼。另一種編碼方法的碼本中碼字的長度可以不同，即對應(yīng)于不同的信源符號ui或信源符號序列U1U2…UL，其編碼的碼字X1X2…XK的長度K可能不同。這類編碼稱為變長碼。我們首先討論等長信源編碼中的基本問題和編碼定理。7.2等長信源編碼的相關(guān)概念和編碼定理7.2.1等長碼和編碼效率設(shè)有離散無記憶信源：根據(jù)系統(tǒng)的特性和應(yīng)用要求，已確定碼符號集為X={x1,x2,…,xm}。如果碼字長度為K，則碼符號集中最多可以包含mK個不同的碼字。下面我們首先考慮對信源符號ui(i=1,2,…,n)進(jìn)行無失真編碼。為了使信源符號與碼字之間具有一一對應(yīng)關(guān)系，顯然必須滿足：mK≥n

(7.1)即K≥logmn

(7.2)例如，設(shè)某信源U中n=8。由于信源含有8種符號，因此若進(jìn)行二進(jìn)制等長編碼(m=2)，則碼字的長度K≥log8=3，即等長編碼時碼字的長度至少為3比特。若離散無記憶信源U輸出一個信源符號所含有的平均信息量為H（U），編碼后一個信源符號使用K位碼符號表示，則平均來講，每一個碼符號所攜帶的平均信息量（即編碼的信息傳輸率，又稱碼率）為(7.3)碼率體現(xiàn)了信息傳輸有效性的高低。R越大，表示每一個碼元攜帶的平均信息量越多，即有效性越高；R越小，表示每一個碼元攜帶的平均信息量越少，即有效性越低。因為編碼器的碼符號集為X={x1,x2,…,xm}，所以編碼器能夠傳輸?shù)淖畲笮畔⒙蕿閘ogm。若編碼碼率達(dá)到了這一最大信息率，即R=logm則表明通過編碼去除了信源符號中的冗余，編碼效率達(dá)到了100%。一般情況下，編碼效率可能達(dá)不到100%，即R≤logm。為了衡量編碼方法去除信源信息冗余的能力，定義等長碼編碼器的編碼效率為

(7.4)進(jìn)一步可以求出編碼后仍然存在的冗余度為

(7.5)如果對離散無記憶信源U的L次擴(kuò)展信源UL輸出的樣矢量ui=U1U2…UL(i=1,2,…,nL)進(jìn)行無失真信源編碼，則因為L次擴(kuò)展信源UL中包含的樣矢量的個數(shù)為nL，所以為了實現(xiàn)無失真編碼，使擴(kuò)展信源UL中每一個樣矢量與碼字之間具有一一對應(yīng)關(guān)系，必須滿足：mK≥nL(7.6)即K≥Llogmn(7.7)

例如，仍設(shè)某信源U中n=8，若考慮其二次擴(kuò)展信源(L=2)的二進(jìn)制等長編碼(m=2)，則因為U2中的樣矢量個數(shù)為nL=82=64，所以碼符號集中碼字的長度應(yīng)當(dāng)滿足：K≥Llogmn=2log28=6即碼字的長度至少為6比特。在考慮離散無記憶信源的L次擴(kuò)展信源UL的無失真編碼時，我們將信源輸出的樣矢量U1U2…UL變換成碼符號序列X1X2…XK。在這樣的處理中，我們不僅要求能夠無失真地由X1X2…XK恢復(fù)信源輸出的樣矢量U1U2…UL，同時希望傳送X1X2…XK時需要的信息率達(dá)到最小。因為編碼器的碼符號集仍為X={x1,x2,…,xm}，即X有m種取值，所以對于等長信源編碼，碼字X1X2…XK的可能組合形式有mK種。于是傳送一個碼字X1X2…XK時，編碼器輸出的最大信息量為logmK=Klogm

(7.8)然而，傳送一個碼字X1X2…XK對應(yīng)于傳送擴(kuò)展信源輸出的一個樣矢量U1U2…UL。由于一個樣矢量由L個信源符號組成，因此當(dāng)信源輸出一個符號時，編碼器需要輸出的平均信息率為

(7.9)為了提高編碼效率，顯然應(yīng)當(dāng)在滿足無失真的條件下尋找使編碼器輸出的信息率即最小的編碼方式。然而，在無失真編、譯碼的要求下，信源編碼處理所能夠?qū)崿F(xiàn)的最小信息率滿足什么樣的關(guān)系？其理論極限為何？下面討論的等長無失真信源編碼定理將回答這些問題。7.2.2信源符號序列的劃分為了證明等長無失真信源編碼定理，我們首先分析離散無記憶信源U及其L次擴(kuò)展信源UL的統(tǒng)計特性和輸出信源符號或樣矢量所載荷的信息量所具有的統(tǒng)計關(guān)系，并依此將信源符號和樣矢量進(jìn)行分類劃分，建立幾個不等式。設(shè)有離散無記憶信源：其中，。其L次擴(kuò)展信源為

(7.10)其中:

(7.11)且

(7.12)根據(jù)系統(tǒng)的要求，設(shè)已選定編碼符號集為X={x1,

x2,…,xm},于是，我們可以考慮對信源U和L次擴(kuò)展信源UL進(jìn)行碼字長度為K的等長無失真編碼。由7.2.1節(jié)的討論我們知道，無失真信源編碼要求信源符號或擴(kuò)展信源的樣矢量與其編碼的碼字之間必須具有一一對應(yīng)的變換關(guān)系。不同的信息源及其擴(kuò)展信源中信源符號的個數(shù)和樣矢量的個數(shù)可能不同，然而由碼符號集可以看出，能夠組合使用的碼字最多只有mK個，即編碼器可以使用的碼字個數(shù)受到了限制。因此，在無失真信源編碼中，我們只能夠設(shè)法充分、有效地利用碼本中的mK個碼字，使信源U和擴(kuò)展信源UL輸出的信息量中貢獻(xiàn)較大的信源符號和樣矢量有確定的一一對應(yīng)的碼字，以保證包含信息量較多的這一部分信源符號和樣矢量不產(chǎn)生譯碼差錯。對于輸出信息量很少的信源符號和樣矢量，由于有mK個可用碼字的限制，因此不能夠保證分配一一對應(yīng)的碼字。雖然這一部分信源符號和樣矢量在譯碼時可能會產(chǎn)生失真，但是由于它們對信源和擴(kuò)展信源輸出的信息量貢獻(xiàn)很小，因此仍可使信源編碼系統(tǒng)的失真得到嚴(yán)格的控制。下面我們將在編碼器可用碼字受到限制的實際情況下，按照這樣的編碼處理思想分析信源符號和樣矢量的信息特性及它們與信源熵的關(guān)系，找出使譯碼失真最小，滿足無失真信源編碼要求的統(tǒng)計關(guān)系。下面主要以信源符號編碼為例進(jìn)行討論。由第2章的討論我們知道，反映信源符號ui(i=1,2,…,n)基本特性的參數(shù)是其載荷的信息量，即信源符號的自信息I(ui)。對于信源符號ui，其發(fā)生的概率為P(ui)，當(dāng)信源輸出ui時，ui載荷的自信息為I(ui)=－logP(ui)i=1,2,…,n信源輸出大小為I(ui)的自信息是伴隨著信源輸出ui而發(fā)生的。我們知道,ui是一個發(fā)生概率為P(ui)的隨機(jī)變量，因此I(ui)也是一個隨機(jī)變量，它與ui具有相同的概率分布，即P(ui)(i=1,2,…,n)。可以求出I(ui)的均值和方差：(7.13)(7.14)當(dāng)n為有限值時，σ2(U)<+∞是一個有限的定值。信源符號的自信息的統(tǒng)計平均值即為信源的熵H（U），也就是信源U所輸出的平均信息量。然而，式(7.13)表明，不同的信源符號ui所攜帶的自信息量對信源輸出的平均信息量的貢獻(xiàn)－P(ui)logP(ui)

(i=1,2,…,n)一般是不相同的。結(jié)合式(7.14)可以進(jìn)一步看出，如果信源符號ui的自信息I(ui)與信源U的熵H(U)接近（偏差較?。瑒t相應(yīng)地－P(ui)logP(ui)在熵H(U)的計算中將發(fā)揮較大的作用。這表明這一類信源符號ui所載荷的自信息量在信源U輸出的平均信息量中占有重要成分，對信源U輸出信息的貢獻(xiàn)較大。反之，如果I(ui)與信源U的熵H(U)相差較遠(yuǎn)（偏差較大），則相應(yīng)地－P(ui)logP(ui)在熵H(U)的計算中作用很小，該信源符號ui對信源U輸出信息的貢獻(xiàn)也就很小。于是，我們可以依據(jù)信源符號ui輸出的自信息I(ui)與信源輸出的平均信息量H(U)的偏差大小，將信源符號劃分為不同的類型。根據(jù)契比雪夫（Chebyshev）不等式，對于任意的ε>0，有

(7.15)式(7.15)反映出了信源符號的自信息與信源的熵的偏差（兩者之差的絕對值）不小于ε的事件發(fā)生的概率與給定的偏差范圍ε、I(ui)的方差σ2(U)的關(guān)系。下面我們考慮離散無記憶信源U的L次擴(kuò)展信源UL（見式(7.10)~式(7.12)）中的關(guān)系。

L次擴(kuò)展信源UL輸出的樣矢量所載荷的自信息為

(7.16)樣矢量的自信息I(ui)是伴隨著隨機(jī)樣矢量ui的發(fā)生而發(fā)生的隨機(jī)變量，與樣矢量ui有相同的概率分布。于是，我們可以求出I(ui)的均值和方差：

(7.17)(7.18)顯然，樣矢量的自信息I(ui)的統(tǒng)計平均值即為L次擴(kuò)展信源UL所輸出的平均信息量，它是離散無記憶信源U的熵的L倍;方差σ2［I(ui)］反映出了樣矢量的自信息與UL的熵之間的平均偏差。與式(7.14)相比可以看出，樣矢量自信息I(ui)的方差增大為了信源符號自信息I(ui)的方差的L倍。為了分析L次擴(kuò)展信源UL所輸出的樣矢量ui(i=1,2,…,nL)對UL輸出信息的貢獻(xiàn)大小，以區(qū)分不同的樣矢量對信源輸出信息的重要程度，我們?nèi)匀粡臉邮噶康淖孕畔(ui)與其統(tǒng)計平均值的偏差入手。設(shè)已給定一個I(ui)與H(UL)的偏差控制范圍Lε>0。根據(jù)契比雪夫不等式，某一樣矢量ui的自信息與LH(U)的偏差超過Lε(即事件|I(ui)－LH(U)|≥Lε發(fā)生)的概率滿足：(7.19)由式(7.10)我們知道，L次擴(kuò)展信源UL中有nL個不同的樣矢量ui，這些樣矢量所包含的自信息在UL輸出的平均信息量中有不同的貢獻(xiàn)。根據(jù)ui載荷的自信息與其統(tǒng)計平均值的偏差，我們可以將這nL個樣矢量分類并構(gòu)成兩個互補(bǔ)的集合Aε和。組成這兩個集合的樣矢量分別滿足：(7.20)(7.21)由不等式(7.19)可以知道，集合所表示的事件發(fā)生的概率為

根據(jù)概率分布律，集合所表示的事件發(fā)生的概率還應(yīng)當(dāng)滿足：

于是，有

(7.22)另外，由于集合Aε和是互補(bǔ)的，因此集合Aε所表示的事件發(fā)生的概率為

(7.23)可以看出，當(dāng)L→∞時，有

(7.24)即L次擴(kuò)展信源UL中的nL個樣矢量全部屬于集合Aε，而集合中樣矢量的個數(shù)為零。由樣矢量劃分集合的定義可知，如果樣矢量ui∈，則其攜帶的自信息I（ui）與UL的熵H(UL)具有很大的偏差，表明該樣矢量對于UL輸出信息的貢獻(xiàn)很小。反之，如果樣矢量ui∈Aε，則它所攜帶自信息I(ui)與UL的熵H(UL)的偏差在規(guī)定的范圍ε之內(nèi)，該樣矢量的自信息在UL輸出平均信息量的計算中發(fā)揮了較大的作用。因此，在無失真信源編碼中，集合Aε中的樣矢量ui應(yīng)當(dāng)重點考慮。那么，L次擴(kuò)展信源UL的nL個樣矢量中，屬于集合Aε的樣矢量個數(shù)滿足怎樣的關(guān)系呢？能否保證在mK個可用碼字中找到一一對應(yīng)的編碼關(guān)系？我們將從ui∈Aε的自信息的特點入手，找出集合Aε中樣矢量的個數(shù)所滿足的不等式關(guān)系。設(shè)集合Aε中樣矢量ui的個數(shù)為Mε，顯然，Mε≤nL。由集合Aε

的定義可知，樣矢量ui∈Aε所具有的共同特點是:它們的自信息與信源熵的偏差在給定的范圍ε之內(nèi)，即對于ui∈Aε，有：因此

2－L(H(U)－ε)>P(ui)>2－L(H(U)+ε)

(7.25)

由于事件Aε發(fā)生的概率為ui∈Aε的概率之和，因此依式(7.25)左端可以得到，事件Aε發(fā)生的概率滿足下面的關(guān)系：

(7.26)

同理，由式(7.25)右端的不等式關(guān)系可以得到：(7.27)在前面的討論中，我們根據(jù)契比雪夫不等式以及集合Aε和的互補(bǔ)性，從嚴(yán)格的概率關(guān)系得出了事件Aε發(fā)生概率的取值范圍（見式(7.23)）。同時，我們也通過對樣矢量ui∈Aε的概率求和，得到了式(7.26)和式(7.27)指出的P(Aε)的上、下界。顯然，式(7.26)和式(7.27)所指出的上、下界應(yīng)當(dāng)在式(7.23)所規(guī)定的范圍之內(nèi)。于是，事件Aε發(fā)生的概率的上界（見式(7.26)的右端）一定大于式(7.23)所規(guī)定的最小值，即(7.28)同理，事件Aε發(fā)生的概率的下界（見式(7.27)的右端）也不會超過式(7.23)所規(guī)定的最大值，即Mε×2－L(H(U)+ε)<1

(7.29)因此，集合Aε中樣矢量ui的個數(shù)Mε滿足不等式：

(7.30)應(yīng)用上述分析所得到的基本關(guān)系和不等式，我們便可以證明無失真等長信源編碼定理。7.2.3等長信源編碼定理

定理7.1(等長信源編碼定理)由L個符號組成、每個符號的熵為H(U)的離散無記憶平穩(wěn)信源符號序列U1U2…UL可以用K個符號X1X2…XK（每個符號有m種取值可能）進(jìn)行等長編碼。對于任意的ε>0，δ>0,只要：

(7.31)當(dāng)L足夠大時，就可使譯碼差錯小于δ。反之，當(dāng)

(7.32)時，譯碼差錯一定是有限值。當(dāng)L足夠大時，譯碼幾乎必定出錯。

證明：這個定理由正定理和逆定理兩部分組成。下面先證明正定理。設(shè)離散無記憶信源有n種輸出符號，則其L次擴(kuò)展信源UL有nL種不同的樣矢量ui。根據(jù)前面給出的無失真信源編碼的基本思想，在正定理的證明中我們并不把這nL種樣矢量ui全部進(jìn)行一一對應(yīng)的編碼，而是只保證對擴(kuò)展信源UL輸出信息貢獻(xiàn)較大的屬于集合Aε中的Mε個樣矢量ui實現(xiàn)一一對應(yīng)的編碼。由定理給出的條件可知，由于碼符號集中有m個碼符號，因此可以組成mK個長度為K的碼字，于是只要mK大于Mε，就能夠?qū)崿F(xiàn)上述編碼方案。定理中的式(7.31)給出的條件等價于logmK≥L(H(U)+ε)即mK≥2L(H(U)+ε)

而由式(7.30)可知:Mε<2L(H(U)+ε)

所以，在滿足式(7.31)給定的條件時，一定能夠滿足mK>Mε。因此，我們總可以找到一種編碼方法，使得集合Aε中的Mε個樣矢量ui與mK個碼字有一一對應(yīng)的關(guān)系，譯碼將不會產(chǎn)生錯誤。但是，此時并沒有保證集合中的樣矢量ui也可以找到一一對應(yīng)的輸出碼字。因此，譯碼中樣矢量ui∈可能會產(chǎn)生錯誤。由此可知，經(jīng)過這樣的編碼處理，系統(tǒng)產(chǎn)生的失真僅由樣矢量ui∈的譯碼差錯造成，系統(tǒng)的譯碼差錯概率pe不會超過所發(fā)生的概率。由前面關(guān)于集合Aε與的劃分的討論和式(7.22)所指出的概率關(guān)系可知，在此條件下譯碼差錯概率滿足：

(7.33)當(dāng)ε2、σ2均為確定值時，對于任意小的δ>0，當(dāng)L足夠大，即

(7.34)時，譯碼差錯的概率pe一定滿足pe<δ，并且有

正定理得證。在逆定理中，式(7.32)所給出的條件等價于：logmK≤L(H(U)－2ε)即

mK≤2L(H(U)－2ε)=2L(H(U)－ε)×2－Lε

(7.35)表明在逆定理所給出的條件下，編碼器可以使用的碼字個數(shù)受到了限制，需要判斷在逆定理條件下屬于集合Aε的樣矢量ui能否找到一一對應(yīng)的編碼。假定集合Aε中樣矢量ui的個數(shù)僅為其最小值。依據(jù)式(7.30)指出的集合Aε中樣矢量ui的個數(shù)Mε的取值范圍，Mε的取值也必須滿足：

(7.36)即集合Aε中的樣矢量ui最少時，Mε也不可能小于其下界。為了找出此Mε的下界與滿足逆定理條件時碼字個數(shù)mK的關(guān)系，將式(7.35)除以式(7.36)，便有

(7.37)當(dāng)信源符號序列長度L大于某定值L0時，由于2－Lε減小得更快，必可使，即mK<Mε因此，集合Aε中，一定會有一部分樣矢量ui在mK個碼字中找不到一一對應(yīng)的變換關(guān)系，使得譯碼時無法正確地恢復(fù)而出錯。所以，在逆定理的條件下，譯碼差錯不可能是無限小。進(jìn)一步，若L→∞，則由式(7.37)可知

(7.38)由式(7.24)得：P(Aε)→1而P(

)→0，即當(dāng)L→∞時，L次擴(kuò)展信源中的nL個樣矢量ui全部在集合Aε中，然而可以使用的碼字的總數(shù)mK卻遠(yuǎn)小于nL，以至于集合Aε中的絕大多數(shù)樣矢量ui無法找到一一對應(yīng)的碼字，譯碼時幾乎必定出錯，此即逆定理所給出的結(jié)論。證畢。定理7.1表明，在進(jìn)行等長無失真信源編碼時，信源的平均符號熵H(U)是編碼器輸出信息率的一個臨界值。由式(7.9)可知，當(dāng)編碼器允許的輸出信息率，即信源每輸出一個信源符號編碼器必須輸出的信息率為時，只要R′>H(U)，即編碼器允許的輸出信息率大于信源輸出的信息率(即信源的熵)，編碼器就一定可以做到幾乎無失真，譯碼差錯接近于零（見式(7.33)），條件是信源符號序列的長度L足夠大（見式(7.34)）。反之，當(dāng)R′<H(U)時，不可能構(gòu)成無失真的編碼，即不存在一種編碼器，能夠使譯碼差錯的概率趨近于零。R′=H(U)為編碼器的臨界狀態(tài)，可能會產(chǎn)生譯碼差錯，也可能不產(chǎn)生譯碼差錯。例如對于信源U，當(dāng)n個信源符號為等概率分布且n恰為2的整數(shù)冪，即時，信源的熵為

采用二進(jìn)制K0位的等長編碼可以實現(xiàn)n個信源符號與個碼字之間一一對應(yīng)的變換關(guān)系，譯碼無失真且編碼器的輸出信息率恰為R′=H(U)。如果信源非等概分布，則在R′=H(U)時一般會產(chǎn)生譯碼差錯。定理7.1從理論上闡明了無失真且編碼效率接近于1的理想等長信源編碼器的存在性。按照定理7.1及其證明過程中的處理方法，離散無記憶信源的L次擴(kuò)展信源UL輸出的樣矢量ui可以用K個碼符號（碼符號集有m個元素）組成的等長碼進(jìn)行編碼。在給定ε和δ之后，按照式(7.34)規(guī)定的信源符號序列長度L的值計算每一個樣矢量ui的概率，將概率較大的樣矢量選為集合Aε中的元素，并使P(Aε)=1－δ,然后將Aε中的樣矢量使用一一對應(yīng)的碼字編碼表示，便完成了對L次擴(kuò)展信源UL的編碼處理。只要所取的δ足夠小，譯碼差錯的概率pe<δ將足夠小。這時編碼器的編碼效率為(7.39)只要所取的ε足夠小，η便接近于1。但是，要使ε、δ足夠小，便要求L足夠大。對于pe→0,η→1的理想編碼器，必須使L→∞。顯然，這是無法實現(xiàn)的。

【例7.1】已知某信源的概率空間為

可以求出H(U)=2.5524(比特/符號)和σ2(U)=7.82。若要求編碼效率為90%，即

可解得ε≈0.28。設(shè)譯碼差錯率為10－6，即pe=δ=10－6

由式(7.34)可知，信源符號序列的長度必須滿足：

可見，在差錯率和編碼效率的要求并不是很高的情況下，必須把近108個信源符號一起編碼，才能夠滿足要求。因此，我們需要研究更加有效并且便于工程實現(xiàn)的編碼方法，如變長編碼的方法。7.3變長碼的基本概念從碼符號集X={x1,x2,…,xm}中可以選出若干位碼元（如K位）組成碼字X1X2…XK。在由這樣的碼字構(gòu)成的碼本中，如果碼字的長度K并不是一個固定不變的量，則這樣的一組碼字便被稱為變長碼。下面首先討論有關(guān)變長碼的一些基本概念和關(guān)系。7.3.1平均碼長與編碼效率由前面幾節(jié)的討論我們知道，所謂信源編碼，是將信源符號ui或擴(kuò)展信源的樣矢量ui與碼本C中的碼字X1X2…XK構(gòu)成映射關(guān)系。因為變長碼碼本C中碼字的長度不同，所以經(jīng)過信源編碼處理，與不同的ui或ui對應(yīng)的碼符號序列（碼字）所含有的碼符號個數(shù)即編碼長度（碼長）各不相同。為了衡量變長編碼的效果，需要引入平均碼長的概念。對于離散無記憶信源:

在實現(xiàn)一一對應(yīng)的無失真變長信源編碼后，相應(yīng)于各信源符號的碼字：W1,W2,…,Wn分別具有碼長：K1,K2,…,Kn已知信源符號ui發(fā)生的概率為P(ui)，碼長Ki發(fā)生的概率也為P(ui)，于是我們可以知道這組碼字的平均碼長為

(7.40)平均碼長表示了每一個信源符號平均使用的碼元個數(shù)，其單位為碼符號/信源符號。若已知信源的熵為H(U)，即信源輸出一個信源符號時平均輸出的信息量為H(U)比特/信源符號，那么，變長信源編碼器輸出一位碼元時所輸出的平均信息率為

(7.41)已知碼符號集由m個符號組成，編碼器輸出的最大信息率便為logm比特/碼符號。若編碼器的輸出信息率達(dá)到了此最大信息率，即R=logm，則表明通過編碼消除了信源符號中的冗余，編碼效率為100%。在等長信源編碼中，我們定義了編碼效率來衡量編碼器去除信源信息冗余的能力。因為等長編碼中，由式(7.4)和式(7.5)我們可以推出變長信源編碼時的編碼效率和編碼冗余，即(7.42)(7.43)和同樣，對于L次擴(kuò)展信源UL，熵為H(UL)=LH(U)，其變長無失真信源編碼是將輸出的樣矢量U1U2…UL變換成長度不同的碼符號序列X1X2…XK。設(shè)碼符號集X={x1,x2,…,xm}，樣矢量的平均碼長為（單位為比特/樣矢量）。于是，由式(7.42)和式(7.43)可知，擴(kuò)展信源UL的變長無失真信源編碼的編碼效率和編碼冗余為(7.44)(7.45)其中，/L表示與一個信源符號相對應(yīng)的平均碼長。7.3.2變長碼的結(jié)構(gòu)與分類如果對信源U進(jìn)行變長編碼，我們對于經(jīng)常出現(xiàn)（概率較大）的信源符號可以用一個短碼（Ki較小）表示，而對于出現(xiàn)概率很小的信源符號使用長碼（Ki較大）表示，則平均碼長相對于等長編碼時將會減小。因此，選擇恰當(dāng)?shù)淖冮L編碼可以提高編碼效率。然而，在各類通信系統(tǒng)和電子信息系統(tǒng)的設(shè)計中，并不是任意一種變長碼都可以使用，即工程中允許使用的變長碼必須滿足一定的條件。在下面的例子中，我們給出幾種不同的變長碼。雖然它們的平均碼長都較小，但是有的碼卻不能夠在工程中使用。

【例7.2】對于信源:

使用碼符號集X={0,1}作二進(jìn)制變長編碼。此處我們給出四種編碼方案：對于編碼A，信源符號u1和u2的碼字都是0，當(dāng)接收端收到碼符號0時便無法確定信源輸出的是哪一個符號。對于編碼B，如果接收到符號序列00，則譯碼時無法確定信源的輸出是u3還是u1u1。對于編碼C和編碼D，設(shè)接收到一個碼符號序列0010110…。編碼C解碼得到信源符號序列u1u2u3…，而編碼D的譯碼結(jié)果為信源符號序列u1u1u2u3…。由上述分析可知，編碼C和編碼D能夠用于無失真變長編碼，而編碼A和編碼B則不能唯一、正確地恢復(fù)信源符號和信源符號序列，不能用于信源編碼。因此，在各類通信系統(tǒng)和電子信息系統(tǒng)中使用的信源編碼方案必須具有一定的性質(zhì)，滿足特定的碼字結(jié)構(gòu)要求。

1.唯一可譯碼對于每一個有限長的信源符號序列，其編碼形成的碼符號序列不與任何其他的碼符號序列相重合，則稱這樣的碼是唯一可譯碼，否則為非唯一可譯碼。工程中使用的編碼方案必須是這種滿足唯一可譯性或單義可譯性的唯一可譯碼。由唯一可譯碼所構(gòu)成的碼字序列，可以不需要任何間隔符號就能夠在接收端正確地分離碼字并譯出相應(yīng)的信源符號或信源符號序列。在例7.2中，編碼A和編碼B的譯碼結(jié)果都可能會產(chǎn)生歧義，編碼A和編碼B是非唯一可譯碼。而對于某一個碼符號序列，編碼C和編碼D分別得到了一個唯一的信源符號序列，因此編碼C和編碼D是滿足唯一可譯性的唯一可譯碼。雖然編碼C和編碼D都是唯一可譯碼，但是它們兩者之間也有各自不同的特點。編碼C中，u1的碼字0事實上構(gòu)成了其他信源符號的編碼碼字的字頭，即信源符號u2、u3和u4的碼字中起始的部分均為u1的碼字0。同理，u2的碼字01構(gòu)成了u3和u4的碼字011和0111的字頭；u3的碼字011是u4碼字0111的字頭。由于碼字結(jié)構(gòu)的這一特點，對一個碼符號序列進(jìn)行碼字分離處理時，若某一碼字的最后一位碼符號出現(xiàn)，則我們并不能即時地完成該碼字的分離。因為這組碼符號可能是某一信源符號的碼字，也可能是另外一些信源符號的碼字的字頭，只有當(dāng)下一個信源符號的碼字中的第一位碼符號被接收到時，我們才能完成前一個碼字與下一個碼字的分離。與編碼C相比，編碼D的結(jié)構(gòu)有不同的特點。編碼D中的任何信源符號的碼字都不構(gòu)成其他碼字的字頭。于是對一個碼符號序列的碼字分離，不吸引下一個信源符號的碼字出現(xiàn)，只要當(dāng)前信源符號的碼字接收完畢，即該碼字的最后一位碼符號出現(xiàn)，便可即時地完成該碼字的分離處理。

2.字首碼若任一信源符號碼字的前面任一起始部分都不構(gòu)成其他信源符號的碼字，則稱具有這種結(jié)構(gòu)的編碼為字首碼。字首碼可以實現(xiàn)碼字的即時分離，又稱為即時碼（可以即時地譯碼）。顯然，字首碼滿足唯一可譯性，即字首碼是唯一可譯碼的一類子碼，字首碼一定是唯一可譯碼。反之，唯一可譯碼不一定是字首碼，有些唯一可譯碼可能不滿足字首性。根據(jù)字首碼的結(jié)構(gòu)特點我們知道，例7.2中，編碼D是字首碼，而編碼C的結(jié)構(gòu)不滿足字首性，故編碼C是非字首碼。按照字首性結(jié)構(gòu)的要求仍然可以得到不同的編碼方案，這些不同的編碼方案的平均碼長可能不同。例如，對于例7.2給出的信源U的四個信源符號，我們可再構(gòu)造一種編碼E：u1→0,u2→101,u3→110,u4→111編碼E不僅具有唯一可譯性，而且滿足字首性，也是字首碼。因為編碼D和編碼E中u2碼字的長度不同，所以。

3.緊致碼平均碼長最短的字首碼稱為緊致碼。通過上面對變長碼的各種結(jié)構(gòu)特點和性質(zhì)的討論，我們可以將變長碼劃分為如圖7-2所示的幾種類型。圖7-2變長碼的分類信源編碼的主要目的是去除信源的信息冗余，提高系統(tǒng)的有效性，因此，在考慮變長無失真信源編碼中，希望平均碼長盡量地短。然而，通過對各類變長碼的結(jié)構(gòu)特點的分析，我們應(yīng)當(dāng)明確，在通信系統(tǒng)和電子信息系統(tǒng)的設(shè)計中，所追求的平均碼長最短（有效性最高）是有條件的。最優(yōu)的變長編碼并不是單純地追求平均碼長最短，而是在滿足唯一可譯性和字首性的條件下追求平均碼長最短，即對于某一離散無記憶信源U和L次擴(kuò)展信源UL，尋找其變長無失真編碼的緊致碼。緊致碼是滿足唯一可譯性和字首性時平均碼長最短的碼。下面我們給出一種表示和構(gòu)造字首碼的方法，然后討論一組字首碼的碼長所滿足的關(guān)系，即字首碼存在的條件。7.3.3碼的樹形圖表示設(shè)碼符號集為X={x1,x2,…,xm}，由X中選出K個碼符號構(gòu)成的碼字X1X2…XK可以使用m進(jìn)制的樹形圖來表示。這樣的樹形圖我們也稱為碼樹圖。所謂樹形圖，是一種由根、枝和節(jié)點表示的樹狀圖形。圖7-3所示即為一樹形圖。其中，根是樹形圖的出發(fā)點（如圖中的點A）。由根可以伸出枝，枝的另外一端稱為節(jié)點，每一個節(jié)點又可以再伸出新的枝，不再伸出枝的節(jié)點即為葉。在下面的討論中，我們將繼續(xù)伸枝的節(jié)點稱為中間節(jié)點，見圖7-3中的點B和C，而將不再伸枝的節(jié)點即樹葉稱為終端節(jié)點，見圖7-3中的點D、E、F和G。圖7-3碼樹圖如果每一個根或中間節(jié)點最多可以伸出m個枝，則樹形圖是m進(jìn)制的。由根到葉可以串接不同節(jié)數(shù)的枝，距根為k節(jié)的節(jié)點稱為k階節(jié)點。如果一個樹形圖中串接的最大枝數(shù)為K，即階數(shù)最高的終端節(jié)點為K階，則稱樹形圖是K階的樹形圖。由此可知，圖7-3所示為一個二進(jìn)制三階的樹形圖。在一個m進(jìn)制K階的樹形圖中，如果所有的K－1階節(jié)點都伸出了m個枝，全部K階節(jié)點都成為終端節(jié)點，則這樣的樹形圖是一個K階的滿樹，否則該樹形圖是非滿樹。顯然，m進(jìn)制K階的滿樹有mK個終端節(jié)點。圖7-4所示為一個三進(jìn)制三階的滿樹，它有mK=33=27個終端節(jié)點。在圖7-5中，一階節(jié)點B和二階節(jié)點C、D、E、F都沒有伸出枝，樹形圖的終端節(jié)點中有一個一階節(jié)點、四個二階節(jié)點和六個三階節(jié)點。因此，圖7-5是一個非滿樹。圖7-4滿樹碼樹圖圖7-5非滿樹碼樹圖以樹形圖的根作為起始點，沿著根和中間節(jié)點伸出的枝可以走到終端節(jié)點。由樹形圖的結(jié)構(gòu)可以清楚地看出，從根到每一個終端節(jié)點所經(jīng)過的路徑是完全不同的。如果我們將根或中間節(jié)點所伸出的一組枝分別標(biāo)注0、1、…、m，則由根到每一個終端節(jié)點所經(jīng)過的不同路徑便可以用互不相同的一組有序數(shù)據(jù)（序列）來表示。對于一組信源符號，我們可以設(shè)計一個樹形圖并將信源符號放置在樹形圖的終端節(jié)點上，從樹形圖的根到信源符號的路徑構(gòu)成的數(shù)據(jù)序列便可用作該信源符號的編碼。由于從根到不同信源符號的路徑不同，因此這組碼字互不相同且一定滿足唯一可譯性，構(gòu)成唯一可譯碼。在上述考慮中，我們沒有在樹形圖的中間節(jié)點上安排信源符號，在由根到每一個信源符號的路徑中不會遇到其他信源符號。因此任何信源符號的碼字都不會成為其他信源符號碼字的前綴。顯然，這樣構(gòu)成的碼字也同時滿足了字首性，即為一組字首碼。因此，我們可以得到一個重要結(jié)論：在一個樹形圖中，只要不在任何中間節(jié)點安排信源符號，而是將所有的信源符號放在終端節(jié)點，所構(gòu)成的碼字就一定滿足字首性。反過來講，任何一種字首碼都可以用一個信源符號全部處于終端節(jié)點的樹形圖來表示。由此可知，樹形圖是表示和構(gòu)造字首碼的一種有效的方法。如果一種編碼的m進(jìn)制K階樹形圖是一個滿樹，則共有mK個信源符號可以被分別安排在其mK個終端節(jié)點上。此時由樹形圖的根到每一個信源符號的路徑長度相同，均為樹形圖的階數(shù)K，所表示的是一組長為K的等長碼。由此也可以看出，等長碼滿足字首性，也是一種字首碼。若一種字首碼的m進(jìn)制K階樹形圖是一個非滿樹，則由根到每一個信源符號的路徑的長度可能不同。因此，若信源符號全部處于非滿樹的終端節(jié)點，則該樹形圖表示的是一組變字長的字首碼。7.3.4字首碼存在性定理由上面的分析我們知道，工程中使用的變長碼應(yīng)當(dāng)滿足字首性。字首碼存在性定理指出了一組字首碼存在的條件。

定理7.2(字首碼存在性定理)設(shè)信源符號集U={u1,u2,…,un}，其碼字長度分別為K1,K2,…,Kn的m進(jìn)制的字首碼存在的充分必要條件是：(7.46)此不等式由克拉夫特（Kraft）于1949年提出并加以證明，因此稱為克拉夫特不等式。碼字的樹形圖可以直觀地表示出一組字首碼所滿足的基本關(guān)系，下面我們結(jié)合碼字樹形圖來證明克拉夫特不等式。

證明：取碼符號集X={x1,x2,…,xm},并對信源符號u1,u2,…,un進(jìn)行m進(jìn)制的變字長編碼，設(shè)各信源符號的碼字：W1,W2,…,Wn分別具有碼長：K1,K2,…,Kn

(7.47)

下面首先證明字首碼存在的必要性。我們構(gòu)造一個m進(jìn)制K階的滿樹，顯然該滿樹具有mK個K階節(jié)點（如圖7-4所示的三進(jìn)制三階滿樹）。假定我們所得到的一組碼字W1,W2,…,Wn是字首碼，且這組字首碼可以用一個m進(jìn)制K－1階的樹形圖加以表示，則這組碼字的碼長滿足:maxKi≤K－1由字首碼的結(jié)構(gòu)和樹形圖表示時的基本特點我們知道，此時信源符號所在的節(jié)點必為該樹形圖的某一終端節(jié)點。對于信源符號ui，已知其碼字Wi的長度是Ki，則該信源符號ui一定位于樹形圖的某一個Ki階的節(jié)點上。因為Wi是字首碼，所以該Ki階的節(jié)點成為一個終端節(jié)點，即此節(jié)點不能夠再伸出新枝。于是，與此Ki階節(jié)點相關(guān)聯(lián)的階次高于Ki的中間節(jié)點和終端節(jié)點便不能被使用，在K階滿樹中的K階節(jié)點個數(shù)將減少

。對于信源符號u1,u2,…,un，我們已編碼得到了n個字首碼，即由K階滿樹中分別選出了階數(shù)為K1,K2,…,Kn的n個節(jié)點作為終端節(jié)點。于是，在原K階滿樹中，去掉的K階節(jié)點的總數(shù)為顯然，去掉的K階節(jié)點的總數(shù)不會超過原K階滿樹中K階節(jié)點的總數(shù)mK，并滿足：

即

因此對于字首碼W1,W2,…,Wn，其碼字長度K1,K2,…,Kn一定滿足克拉夫特不等式。必要性得證。接下來證明充分性。假設(shè)式(7.47)表示的這組信源符號碼字的碼長滿足克拉夫特不等式。顯然，式(7.46)等價于：

構(gòu)造一個m進(jìn)制K階滿樹，其中K>maxKi。對于此滿樹中的mK個K階節(jié)點，可以按照下述方法劃分為n組。第i組（i=1,2,…,n）中的節(jié)點滿足：包含個K階節(jié)點且以同一個Ki階的節(jié)點Ai作為出發(fā)點（母節(jié)）。由樹形圖的結(jié)構(gòu)可以看出，若以某一個Ki階的節(jié)點作為母節(jié)點，則樹形圖的K階（K>Ki）節(jié)點中有個節(jié)點是與其對應(yīng)的子節(jié)點。因此，這樣的劃分是合理的。于是，我們可以將信源符號ui放置在Ki階的節(jié)點Ai上。按照字首碼的結(jié)構(gòu)要求，節(jié)點Ai便成為該樹形圖中的一個終端節(jié)點。由樹形圖的根到節(jié)點Ai即信源符號ui的路徑所構(gòu)成的碼字Wi滿足字首性且碼字長度為Ki。如果一組碼字的長度滿足克拉夫特不等式，則符合這組碼長的字首碼一定存在。證畢。在上面的定理中，我們給出了字首碼存在的充分必要條件，而由證明的過程也可看出，唯一可譯碼存在的充分必要條件也滿足克拉夫特不等式。事實上，在不改變碼字長度的條件下，任何唯一可譯碼均可用一組字首碼來代替。因此，下面我們將主要討論字首碼的構(gòu)造方法。7.4變長信源編碼定理變長無失真信源編碼是將信源符號U或符號序列U1U2…UL變換成長度不同的碼符號序列X1X2…XK，以減小或消除信源中的冗余，提高系統(tǒng)的有效性。由于不同碼字的長度不同，因此計算其平均碼長是衡量編碼效果的常用方法。然而，由上面的分析我們已經(jīng)明確，在通信系統(tǒng)和電子信息系統(tǒng)的設(shè)計中，我們所追求的有效性是有條件的，即必須是在滿足唯一可譯性和字首性的條件下，尋找平均碼長最短的編碼，也就是找出其緊致碼。無失真變長信源編碼定理給出了離散無記憶信源U及其擴(kuò)展信源UL的緊致碼的平均碼長所達(dá)到的下界。

定理7.3

已知離散無記憶信源U的熵為H(U)，若使用碼符號集X={x1,x2,…,xm}進(jìn)行變字長無失真編碼，則總可以找到一組字首碼，其碼字的平均長度滿足：

(7.48)定理7.3給出了緊致碼的平均碼長與信源熵H(U)、碼符號個數(shù)m之間的關(guān)系。由定理7.3可以看出，平均碼長以H(U)/logm為極限。當(dāng)小于此極限時，m元的變字長字首碼和唯一可譯碼不存在。同時，定理也給出了的一個上界。但是由前面關(guān)于變長碼的討論我們應(yīng)當(dāng)明確，這并不表明在時不能夠得到字首碼，而是由于我們希望盡可能地短，因此所追求的緊致碼的平均碼長不應(yīng)超過。

證明：設(shè)有離散無記憶信源:

若信源符號ui使用長為Ki的碼字表示，并使

(7.49)顯然，滿足式(7.49)的整數(shù)Ki一定存在。因為P(ui)≥0，所以若將式(7.49)的每一端都乘以P(ui)，則此不等式中的關(guān)系不變，成為

(7.50)將式(7.50)表示的n個不等式的每一端分別相加，即不等式中的每一端對i求和，得到：即

于是，定理7.3中的結(jié)論得證。但是，由于我們要得到的碼字必須是字首碼，因此還需要考察式(7.49)所表示的這組碼字的碼長Ki(i=1,2,…,n)是否滿足克拉夫特不等式(7.46)。因為Ki是大于零的整數(shù)，所以只要其取值范圍中的最小值能夠滿足克拉夫特不等式，按照式(7.49)確定碼字長度就可構(gòu)造出字首碼。于是，我們考察式(7.49)左端的不等關(guān)系，可知：Ki

logm≥－logP(ui)此即

同取以2為底的指數(shù)（反對數(shù)）得

便可得到:

若將此不等式的兩端分別對i=1,2,…,n求和，則不等式關(guān)系不變，即

于是由式(7.49)確定的一組碼字的長度Ki滿足克拉夫特不等式。所以，對于i=1,2,…,n，若信源符號ui使用式(7.49)給出的長度為Ki的一組碼字表示，則必可找到一種編碼方式，使碼字滿足字首性。證畢。對于離散無記憶信源的L次擴(kuò)展信源UL，其字首碼的存在性由下述定理描述。

定理7.4

對于由L個符號組成的、每個符號的熵為H(U)的離散無記憶信源，若取碼符號集為X={x1,x2,…,xm}，則一定可以找到一種無失真編碼方法構(gòu)成字首碼，使信源U中每個符號所需要的碼字平均長度滿足：

(7.51)當(dāng)L→∞時，有：(7.52)此處，我們考慮的是信源符號序列的變長編碼，即對其L次擴(kuò)展信源UL進(jìn)行編碼。定理7.4中，表示L次擴(kuò)展信源UL中每一個樣矢量ui的碼字的平均碼長。由于樣矢量ui由L個信源符號組成，因此對于信源UL中的每一個信源符號ui而言，碼字的平均長度便為/L。顯然，最有效的編碼可以達(dá)到最短的平均碼長/L。

證明：設(shè)有熵為H(U)的離散無記憶信源：

其L次擴(kuò)展信源為其中:

且

H(UL)=LH(U)依定理7.4的要求，取編碼符號集X={x1,x2,…,xm}對信源U和L次擴(kuò)展信源UL進(jìn)行碼字變長無失真編碼。設(shè)對樣矢量ui(i=1,2,…,nL)進(jìn)行編碼后，碼字的平均長度為。由定理7.3的結(jié)論可知，總可以找到一種編碼方法使此平均碼長滿足式(7.48)，即將不等式的三端同除以樣矢量中信源符號序列的長度L，便有：

即得到式(7.51)。顯然，當(dāng)L→∞時，有。于是，定理7.4中的結(jié)論得到了證明。由于證明中使用了定理7.3中的結(jié)論，因此L次擴(kuò)展信源UL的字首碼也必定存在。證畢。若將定理7.4的結(jié)論推廣到平穩(wěn)遍歷的有記憶信源，如馬爾可夫信源，則有：定理7.3和定理7.4所表示的物理意義是十分明確的，即指出了無失真信源編碼時每一個信源符號平均需要的m進(jìn)制碼符號的個數(shù)與信源熵的關(guān)系。定理7.3和定理7.4指出，無失真信源編碼平均碼長的理論極限就是信源的熵。如果平均碼長，則不可能找到滿足唯一可譯性的編碼方案，必定產(chǎn)生譯碼差錯和失真。(7.53)同時由定理7.3和定理7.4還可看出，如果是對L次擴(kuò)展信源UL進(jìn)行編碼，則信源符號序列愈長，平均碼長愈短，當(dāng)L→∞時，平均碼長可以達(dá)到極限值?？梢姡瑴p小平均碼長的代價是增加信源符號序列的長度，進(jìn)而增加了編碼處理的復(fù)雜性。對于擴(kuò)展信源的無失真變長編碼，我們也可以通過計算編碼效率來衡量一種字首碼的有效性。根據(jù)式(7.44)，編碼效率為而由定理7.4指出的結(jié)論即式(7.51)可知:

于是，結(jié)合式(7.44)和定理7.4，取為其最大值，可以求出變長編碼能夠達(dá)到的編碼效率的下限，即

可見，L愈大，編碼效率愈高，只有信源符號序列的長度L→∞時，才能使η→1。因此,變長信源編碼定理也是一個極限定理。

【例7.3】已知離散無記憶信源其熵為

比特/符號此信源輸出的符號中的信息冗余為

(1)取碼符號集X={0,1}構(gòu)成信源U的編碼：u0→0,u1→1這組碼字的樹形圖如圖7-6所示。因為圖7-6是一個二元一階的滿樹，所以這組碼字為1比特的等長字首碼。圖7-6信源U的碼數(shù)圖可以求出這組碼字的平均碼長：

編碼效率：

因此，編碼冗余為γd=1－η=1－0.65=35%可見，對于給定的二元信源，采用1比特的等長碼雖然簡單且易于實現(xiàn)，但是并沒有減小信源的信息冗余，對提高系統(tǒng)的有效性沒有幫助。由編碼定理可知，若想提高編碼效率，則應(yīng)當(dāng)對擴(kuò)展信源進(jìn)行編碼。（2）考慮U的二次擴(kuò)展信源U2并給出如下編碼：圖7-7給出了這組碼字的樹形圖。圖7-7是一個二進(jìn)制三階的非滿樹，由于信源符號都在樹形圖的終端節(jié)點上，因此這組碼為字首碼。可以求出：圖7-7擴(kuò)展信源U的碼數(shù)圖編碼效率為

編碼冗余減小為γd=1－η=11.7%

(3)對于U的三次擴(kuò)展信源U3,我們給出如下編碼：圖7-8為這組碼字的樹形圖。由樹形圖可知，這組碼是字首碼。圖7-8三次擴(kuò)展信源U的碼數(shù)圖編碼效率和編碼冗余為

可見，對信源U的擴(kuò)展信源編碼并增加輸出信源符號序列的長度時，可以提高編碼器的編碼效率。事實上，如果L進(jìn)一步增加，則編碼效率η將隨之進(jìn)一步提高并趨近于1。例7.3所表現(xiàn)出的趨勢與編碼定理的結(jié)論是一致的。另一方面，與等長信源編碼方法相比，在達(dá)到相同的編碼效率時，變長編碼所要求的信源符號序列長度要小得多。在例7.1中，已知H(U)=2.55比特/符號，仍取m=3并且要求編碼效率η>90%。若進(jìn)行變長編碼，則根據(jù)：

可以求出：

只要信源符號序列的長度大于4，即可滿足η>0.9的要求。此處的討論中我們給出的是充分條件。實際上，只要選擇恰當(dāng)?shù)淖冮L編碼方法，便可以在L=1時，即僅對信源U進(jìn)行變長編碼使編碼效率達(dá)到97.7%。而由關(guān)于等長編碼方法的討論我們已經(jīng)知道，為了滿足η>90%的要求，需要將L≈108個信源符號進(jìn)行等長編碼。所以，對于離散無記憶信源及其擴(kuò)展信源的無失真編碼處理，變長編碼能夠以較低的編碼復(fù)雜度有效地提高編碼效率，與等長信源編碼方法相比，具有突出的優(yōu)點。因此，變長編碼是無失真信源編碼中的常用方法。7.5最佳編碼定理與統(tǒng)計編碼方法前幾節(jié)我們深入討論了無失真信源編碼中的一些基本問題，特別是通過無失真信源編碼定理分析了離散無記憶信源的編碼所能達(dá)到的極限，為高效無失真編碼方法的研究提供了重要的理論依據(jù)。

Shannon的變長無失真信源編碼定理不是一個構(gòu)造性的定理，它所指出的只是緊致碼的存在性，表明對于離散無記憶信源U，一定存在一種平均碼長接近的編碼（緊致碼）。然而，這一存在性定理并沒有告訴我們怎樣得到這樣一組緊致碼，即由這一編碼定理我們還不能夠得到緊致碼的構(gòu)造方法。因此，針對不同信源和信息系統(tǒng)的特點與應(yīng)用要求，研究緊致碼或接近編碼定理所指出的理論極限的高效無失真信源編碼方法一直是信源編碼理論和應(yīng)用研究中的主要內(nèi)容之一。對于離散無記憶信源：

(7.54)假設(shè)我們已找到一組與其一一對應(yīng)的無失真變字長信源編碼，相應(yīng)于各信源符號的碼字：W1，W2，…，Wn

(7.55)分別具有碼長：K1,K2,…,Kn

(7.56)如果式(7.55)所示的碼字滿足唯一可譯性和字首性，并且式(7.56)表示一組碼字的平均碼長最短，則稱式(7.55)給出的這組碼字是信源U的最優(yōu)碼。這一節(jié)我們將討論構(gòu)造最優(yōu)碼時碼字長度分配和碼符號分配與信源符號發(fā)生的概率之間的關(guān)系，以及最優(yōu)編碼處理中應(yīng)當(dāng)遵循的基本規(guī)則，并由此引出統(tǒng)計編碼的一般思想和處理方法。

定理7.5(最優(yōu)碼長分配規(guī)則)在對離散無記憶信源U進(jìn)行變字長的無失真編碼時，如果使碼字的長度嚴(yán)格地按照信源符號概率大小的相反順序排列，即出現(xiàn)概率大的信源符號使用短碼表示，出現(xiàn)概率小的信源符號使用長碼表示，則其平均碼長一定不大于按照任何其他符號排列方式所得編碼的平均碼長。

證明：對于式(7.54)所示的離散無記憶信源U，假設(shè)式(7.55)和式(7.56)是一組按照定理7.5規(guī)定的碼長分配規(guī)則所得到的一組編碼，這組碼字的平均碼長為

(7.57)其中,概率為P(ui)的信源符號ui所對應(yīng)的碼字長度為Ki。根據(jù)定理中的要求，每一個信源符號碼字的碼長嚴(yán)格地與信源符號發(fā)生的概率成反比，即如果P(ul)≥P(us)則Kl≤Ks

(7.58)其中:l,s=1,2,…,n

且l≠s。如果按照這種碼長排列方法所得到的碼字的平均碼長最短，則由任何其他的碼長排列方式所得到的平均碼長都將大于式(7.57)所示的平均碼長。為了證明這一論點，我們調(diào)整這組碼字與信源符號的對應(yīng)關(guān)系，觀察其平均碼長的變化情況。為使碼長變化的關(guān)系簡單且不失一般性，我們可以僅將信源符號ul的碼字與信源符號us的碼字互換，而不改變其他信源符號的碼字。于是信源符號ul的碼字長度成為Ks，信源符號us的碼字長度成為Kl，其他信源符號的碼字長度不變。信源符號ul和us的碼字互換后，編碼系統(tǒng)的平均碼長改變?yōu)橐驗镵s－Kl≥0且P(ul)－P(us)≥0，所以一定有?？梢姡瑢τ谶@組給定的碼字，只有使每一個信源符號的碼字長度嚴(yán)格地與其發(fā)生的概率成反比，才能構(gòu)成信源U的一組平均碼長最短的碼。證畢。雖然定理7.5仍然不是一個構(gòu)造性的編碼定理，但是它指出了構(gòu)造最優(yōu)碼所遵從的一個基本關(guān)系，即在離散無記憶信源的無失真編碼中，應(yīng)將編碼的碼字長度與信源符號的概率統(tǒng)計關(guān)系聯(lián)系起來。按照定理7.5所指出的關(guān)系，對于某信源U或者其L次擴(kuò)展信源UL，我們應(yīng)當(dāng)對其概率分布特性有深入的了解，然后依據(jù)各個信源符號和信源符號序列出現(xiàn)的概率大小，對它們分配不同長度的碼字，將出現(xiàn)概率大的信源符號（序列）用短碼表示，出現(xiàn)概率小的信源符號（序列）則用長碼表示。由于這種編碼處理的基本出發(fā)點是信源的統(tǒng)計特性，因此通過將碼字的長度與信源符號（序列）發(fā)生的概率相匹配，可使碼字長度的統(tǒng)計平均值達(dá)到其最小值，從而提高系統(tǒng)的有效性，這類編碼方法稱為統(tǒng)計編碼或概率匹配編碼，并成為變長無失真信源編碼的基本方法。根據(jù)定理7.5指出的碼長分配規(guī)則，編碼處理中應(yīng)當(dāng)首先將各信源符號按照其概率的大小重新排列。此處，我們不失一般地使信源U中的信源符號按其發(fā)生概率由大到小的順序進(jìn)行排列，即在式(7.54)所示的信源U的概率空間中，使P(u1)≥P(u2)≥…≥P(un)

(7.59)并且使式(7.55)所示的碼字的碼字長度（見式(7.56)）滿足K1≤K2≤…≤Kn

(7.60)在這樣的前提下，我們給出有關(guān)構(gòu)造二元最優(yōu)碼的兩個定理。

定理7.6

對于給定的信源，存在一個最優(yōu)的滿足字首性的二元碼，其最小概率的兩個碼字Wn－1和Wn的碼長最長且相等，它們所構(gòu)成的碼符號序列之間只有最后一位碼符號取值不同，即如果Wn－1的末位碼符號取0，則Wn的末位碼符號為1。

證明：取碼符號集為X={0,1}，則給定信源的二元字首碼可以用一個二元的非滿樹來表示(如圖7-3所示的碼樹圖)。按照定理7.6的碼長分配規(guī)則，應(yīng)當(dāng)使具有最小概率的兩個信源符號un－1和un所對應(yīng)的碼字Wn－1和Wn最長，同時根據(jù)字首碼的結(jié)構(gòu)我們知道，由樹形圖的根到信源符號un－1和un所處的終端節(jié)點的路徑將只有最后一步不同。于是，信源符號un－1和un的碼字Wn－1和Wn具有相同的碼符號序列長度，且Wn－1和Wn只有最后一位碼符號取值不同。如果不是這樣，如假設(shè)Kn=Kn－1+1，則Wn的碼符號序列中的最后一位可以除去而不會影響碼的唯一可譯性和字首性（參見圖7-3）。如果有三個以上概率最小的信源符號的碼字長度相同，則總可以在不改變平均碼長的前提下調(diào)換這些信源符號的碼字，使得信源符號un－1和un所處的終端節(jié)點是由一個母節(jié)點延長一步而得到的兩個子節(jié)點，它們的碼符號序列之間只有最后一位取值不同。于是，定理7.6的最優(yōu)二元碼中，使具有最小概率的兩個信源符號的碼字具有相同的編碼長度，并且它們的碼符號序列中只有最后一位碼符號取值不同的編碼一定存在。證畢。定理7.6給出了一種構(gòu)造二進(jìn)制最優(yōu)碼時應(yīng)當(dāng)遵循的碼符號分配規(guī)則，即概率最小的兩個信源符號的碼符號序列的長度應(yīng)當(dāng)相同，且這兩個碼符號序列只有最后一位碼符號不同，分別為0和1。為了構(gòu)造平均碼長最短的最優(yōu)碼，按照這樣的碼符號分配規(guī)則和概率匹配的編碼原則，首先應(yīng)當(dāng)在給定的信源U中找出概率最小的兩個信源符號un－1和un，分別對un－1和un分配碼符號0和1，以確定它們的碼符號序列中的最后一位碼符號。為了能夠按照這樣的碼字分配規(guī)則繼續(xù)處理，應(yīng)當(dāng)將信源U做適當(dāng)?shù)慕M合變形，然后繼續(xù)尋找概率最小的兩個符號并對其碼符號序列的最后一位分配不同的碼符號，直至完成信源U的編碼處理。于是，我們將信源U的符號重新組合，構(gòu)造出信源U的一個輔助集合：(7.61)其中:(7.62)對于這一輔助集合U′，我們也將其包含的符號按照概率由大到小的順序重新排列，并對概率最小的兩個符號和的碼符號序列中的最后一位分配碼符號，即分別賦以0和1。如此重復(fù)，直至信源的輔助集合中只包含兩個符號，分別對這兩個符號的碼符號序列中的最后一位賦以碼符號0和1為止，就完成了信源U的編碼處理。但是，對于輔助集合U′的這種處理能否保證所得的碼字一定是信源U的最優(yōu)碼呢？下面的定理給出了肯定的結(jié)論。

定理7.7

對于輔助集合U′為最優(yōu)的碼字對原信源的符號集U也是最優(yōu)的。

證明：對于給定的信源U，其概率空間如式(7.54)所示。通過信源符號的組合，我們可以得到式(7.61)所示的輔助集合U′。輔助集合U′中符號的概率滿足式(7.62)。對于輔助集合U′，假設(shè)已找到一組最優(yōu)碼:

(7.63)相應(yīng)的碼字長度為

按照前面討論的編碼策略，可以構(gòu)造出信源U的一組碼字：

W1,W2,…,Wn其碼字長度為

信源U的這組碼字的平均碼長為因為，所以有：

(7.64)式中，(P(un－1)+P(un))與輔助集合U′中的碼字分配無關(guān)，對于給定的信源U它是一個常量；是輔助集合U′的編碼的平均碼長。已知式(7.63)所示的碼字是一組最優(yōu)碼，其平均碼長對于輔助集合U′而言是一個最小值。因此，式(7.64)所示的這組碼字的平均碼長對于信源U而言必定也是最短的。證畢。定理7.7給出了一個重要的結(jié)論：輔助集合U′的最優(yōu)碼也是信源U的最優(yōu)碼。于是尋求具有n個符號的信源U的最優(yōu)碼的過程可以轉(zhuǎn)化為尋求具有n－1個符號的輔助集合U′的最優(yōu)碼。應(yīng)用這一結(jié)論并加以推廣，我們可以得出一個構(gòu)造最優(yōu)碼的編碼策略：對信源中的符號逐次地組合變形構(gòu)成符號個數(shù)遞減的輔助集合，對每一個輔助集合都應(yīng)用概率匹配的編碼思想和最優(yōu)碼的碼符號分配規(guī)則進(jìn)行處理得到輔助集合的最優(yōu)碼，最終構(gòu)成的碼字一定是信源U的最優(yōu)碼。有了這樣的構(gòu)造最優(yōu)碼的編碼策略，我們就可以討論變長無失真信源編碼的基本方法了。7.6變長編碼基本方法7.6.1霍夫曼編碼霍夫曼編碼是一種高效的無失真信源編碼方法，在各類無失真數(shù)據(jù)壓縮和數(shù)據(jù)傳輸系統(tǒng)中得到了廣泛的應(yīng)用。

1952年，霍夫曼（D.A.Huffman）提出了一種構(gòu)造字首碼的編碼方法，一般稱為霍夫曼碼。由于這種編碼方法直接應(yīng)用了最優(yōu)碼的構(gòu)造策略，所得到的碼字具有最短的平均碼長，因此霍夫曼碼是一種最優(yōu)碼。下面我們給出二進(jìn)制霍夫曼碼的編碼處理步驟。設(shè)有離散無記憶信源：如果取碼符號集X={0,1}對信源符號ui(i=1,2,…,n)進(jìn)行霍夫曼編碼，則編碼處理的基本步驟如下：（1）將n種信源符號按照概率由大到小的順序重新排列，設(shè)P(u1)≥P(u2)≥…≥P(un)

(2)取出概率最小的兩個符號，分別分配碼符號0和1，而后將這兩個符號合并為一個新符號，新符號的概率是分配碼符號的兩個符號的概率之和。將此新符號與未分配碼符號的其他符號按照概率由大到小的順序重新排列。（3）重復(fù)第（2）步的處理直至合并后只有一個符號，其概率為1。