第3章信源編碼理論3.1離散信源的熵

3.2編碼的基本概念

3.3唯一可譯碼的判斷與構造

3.4無失真信源編碼3.5率失真函數與限失真信源編碼

習題與思考題

3.1離散信源的熵

根據香農信息論的理論，簡單離散信源X可以由信源符號的概率分布函數來描述，即

式中，{a1,a2,…,am}是信源X的輸出符號集合，用Am表示；p(aj)(j=1,2,…,m)(簡記為pj)是信源輸出符號aj的先驗概率。根據概率公理化定義，pj應滿足(3-2)(3-1)3.1.1自信息量

香農信息論里的信息量用來描述不確定性的物理量。我們已經知道，事件發生的不確定性與事件發生的概率有關。事件發生的概率越小，猜測它發生的難易程度就越大，不確定性就越大；而事件發生的概率越大，猜測該事件發生的可能性就越大，不確定性就越小。對于發生概率等于1的必然事件，就不存在不確定性。比如，如果你告訴某個人他已經知道的某件事，你提供給他的信息量就為零。因此，某事件發生所含有的信息量應該是該事件發生的先驗概率的函數，即

式中,p(aj)是事件aj發生的先驗概率，I(aj)表示事件aj發生所含有的自信息量。(3-3)基于上述想法，香農定義的信息量的度量方法如下：設有一個離散信息源X，其輸出符號集合為Am={a1,a2,…,am}，在任一時刻它可以發出這m種符號中的任一符號，以此構成符號序列來表示某種事件發生。假設從信源X發出符號aj的概率是pj，那么信息源X發出符號aj的自信息量，或者接收者(信宿)收到了這個符號以后獲得的信息量可定義為

I(aj)=－logapj (3-4)另外，從發送端的角度來說，符號aj的概率pj本身就表示信息源X發出符號aj的一種不確定性。若pj大，則不確定性小，這時接收者收到符號aj的信息量就小；若pj小，則不確定性大，這時接收者收到符號aj的信息量就大。極端情況下，如果符號aj出現的概率pj=1，則接收者肯定只收到符號aj，其不確定性變為零。這些都與式(3-4)的計算結果一致，另外，根據對數函數的性質和概率空間pj的定義，可知自信息量具有下列特性：

(1)pj=1,Ij=0;pj=0,Ij=∞。可知必然事件的信息量為0，不可能事件的信息量無限大。

(2)非負性。由于符號出現的概率總是在閉區間［0,1］,那么根據式(3-4)必然有自信息量為非負值。

(3)單調遞減性。若pi<pj，則有Ii>Ij。

(4)可加性。若兩個符號ai、bj同時出現，可用聯合概率pi,j來表示。這時的自信息量I(ai,bj)=－logapi,j，當ai和bj相互獨立時，有pi,j=pi*pj，那么此時信息量具有可加性，即I(ai,bj)=I(ai)+I(bj)。

【例3-1】英文文本中，字母“e”的出現概率為0.105，“c”的出現概率為0.023，“o”的出現概率為0.001，分別計算它們的自信息量。

【解】根據式(3-4)可求得：

“e”的自信息量I(e)=－lb0.105=3.25bit；

“c”的自信息量I(c)=－lb0.023=5.44bit；

“o”的自信息量I(o)=－lb0.001=9.97bit。3.1.2離散信源熵及其性質

1.熵的定義

上述自信息量表征的是信源輸出單個符號所攜帶的信息量，那么如何衡量信源的整體不確定性呢？香農通過熵，即自信息量的概率平均值(數學期望)來表征信源輸出消息的平均信息量或平均不確定性，其表示式為(3-5)熵的單位一般取“比特/符號”(對數以2為底)。另外，當某一符號ai的概率p(ai)為零時，pilbpi在熵公式中無意義，為此規定pilbpi也為零。當信源X中有一個符號的概率為1時，信源為確定信源，輸出符號可以精確預測，即無不確定性，因此熵為零。

離散信源熵的物理意義：它表征信源消息符號集合Am中符號出現的平均不確定性(或整體不確定性)，即為確定集合Am中某一符號出現所需的平均信息量(觀察之前)；反之，即為每出現一個符號所給出的平均信息量(觀察之后)。一般而言，信源給定后，信源的消息符號集合Am及其對應的概率空間也隨之確定，信源的熵值就是一個確定值。當然，不同的信源因為消息集合及概率空間不一樣，熵值也不一樣。

【例3-2】一幅像素為1024×768的灰度圖片，按每個像素點有256個灰度等級，像素的灰度值均勻分布，則平均每幅圖片可提供的信息量為多少？

【解】由于像素灰度均勻分布，則像素點為每一級灰度值的概率為1/256，因此有pi=1/256=2－8；又因為整幅圖片有1024×768個像素，即m=1024×768，所以

即每幅圖片可提供的信息量為12288bit。

【例3-3】二元信源是離散信源的特例。該信源消息符號集合有兩個，分別用0和1表示。對應的符號概率分布為p和q，且p+q=1。求該信源的熵。

【解】由式(3-5)可得二元信源熵為

H(X)=－plbp－qlbq=－plbp－(1－p)lb(1－p)=H(p)

由上式可見,信源信息熵是輸出符號概率p的函數，通常用H(p)表示。H(p)函數曲線如圖3-1所示。從圖中不難看出：如果二元信源的輸出符號是確定的，即p或q為1，則該信源不提供任何消息，熵為0；反之，當二元信源符號0和1以等概率發生時，信源熵達到極大值，為1bit信息量。圖3-1二元信源的熵函數H(p)

【例3-4】某信源有4個符號，出現概率如下：

求該信源的熵。

【解】根據式(3-5)，信源的熵為

2.聯合熵、條件熵的定義

設信源X和Y的消息符號集分別為Am={a1,a2,…,am}和Bn={b1,b2,…,bn}，對X和Y做笛卡爾積，就構成聯合信源X×Y，我們把X與Y的聯合熵H(X,Y)定義為

其中，p(ai,bj)為聯合信源X×Y取值為(ai,bj)的概率。聯合熵H(X,Y)的物理意義為聯合信源X×Y的消息符號集合上的每對元素(ai,bj)的自信息量的概率加權統計平均值(數學期望),或者說X和Y同時發生的平均不確定度。(3-6)我們把X與Y的條件熵定義為

其中，p(ai|bj)為在Y取值為bj時X取值為ai的概率。條件熵H(X|Y)的物理意義是聯合信源X×Y的消息集合上的每對元素ai|bj的條件自信息量的聯合概率加權統計平均值(數學期望),或者說在已知Y后X也發生的平均不確定度。

證明聯合熵H(X,Y)和條件熵H(X|Y)、H(Y|X)以及單符號熵H(X)、H(Y)之間存在如下關系：

H(X,Y)=H(Y)+H(X|Y) (3-8) H(X,Y)=H(X)+H(Y|X) (3-9)(3-7)證明：

【例3-5】設離散二維平穩信源X的概率空間如下：

其二維聯合概率p(aiaj)如圖3-2(a)所示。求獨立熵、條件熵、聯合熵和平均符號熵。圖3-2二元隨機變量的聯合概率密度和條件概率密度

3.熵的性質

熵的主要特性如下：

(1)非負性，即H(X)≥0。

該性質是很顯然的。因為隨機變量X的所有取值的概率分布滿足0<pi<1，當取對數的底大于1時，lbpi<0，而－pilbpi>0，則得到的熵是正值。只有當隨機變量X為確定事件，即某一事件ai出現概率為1時等號才成立。

(2)對稱性，即H(X)=H(p1,p2,…,pn)=…=H(pn,pn－1,…,p1)。

上式表明，熵函數所有變元p1、p2、…、pn位置可以互換，而不影響熵的大小。該性質說明：熵只與信源的總體統計特性有關。如果某些信源的統計特性相同(含有的符號數和概率分布相同)，那么這些信源的熵就相同。

(3)確定性，即H(1,0)=H(1,0,0)=H(1,0,…,0)=0。

上式表明，只要信源符號中有一個符號的出現概率為1，信源熵就等于零。這是因為當一個符號的概率為1后(必然事件)，根據概率的公理化定義，其他符號的概率也必然為0(不可能事件)，因此該信源沒有不確定性。

(4)可加性，即H(X,Y)=H(Y)+H(X|Y)=H(X)+H(Y|X)。

上式表明，兩個信源X和Y的聯合信源的熵等于信源X的熵加上在X已知條件下信源Y的條件熵；或者等于信源Y的熵加上在Y已知條件下信源X的條件熵。對于統計獨立信源X和Y，則其聯合信源的熵等于各個熵之和。

(5)條件熵小于無條件熵，即H(X|Y)≤H(X)。

上式表明，條件熵一般都小于無條件熵，只有當X與Y統計獨立時條件熵才等于無條件熵。這說明在獲得信源X的某種相關信息Y后X的不確定性已經減少。

(6)香農輔助定理。

【定理3-1】對于任意n維概率矢量P=(p1,p2,…,pn)和Q=(q1,q2,…,qn)，下列不等式成立：

該式表明，對任意概率分布pi，它對其他概率分布qi的自信息量－lbqi取數學期望時，必大于pi本身的熵。等號僅當P=Q時成立。(3-10)

(7)最大熵定理。

【定理3-2】離散無記憶信源輸出M個不同的消息符號，當且僅當各個符號出現概率相等時(即pi=1/M),熵最大,即

該式也表明等概率分布信源的平均不確定性為最大，這也在圖3-1中得到反映(對于2符號信源，在輸出符號0和1以等概率發生時，信源熵達到極大值)。(3-11)3.1.3互信息及其性質

1.非平均互信息量I(ai；bj)

非平均互信息量指單個符號之間的互信息，一般用I(ai;bj)表示，其物理意義為觀察到bj后收到關于ai的信息量，香農將其定義為符號后驗概率與先驗概率比值的對數，即

由此可見，它也等于關于ai的先驗不確定性I(ai)減去觀察到bj后對ai保留的不確定性I(ai|bj)。由式(3-12)可知，它滿足下式：(3-12)(3-13)

2.平均互信息I(X;Y)

I(X;Y)是指兩個集合之間的平均互信息量。例如，對于圖3-3所示的簡化通信系統模型，信源X經過信道傳輸或信號處理后，得到信宿Y。根據香農信息論，兩者之間的平均互信息量I(X;Y)可定義為互信息量I(ai;bj)的概率加權平均值(數學期望)，即

式中，I(X;Y)就是在收到集合Y后所能獲得的關于集合X的平均信息量，即平均互信息量，簡稱平均互信息，也稱平均交互信息量或交互熵。(3-14)圖3-3簡化通信系統模型下面根據前面所學的知識來推導平均互信息具體應用的計算表達式。

(1)首先分析收到bj后，從bj中獲得關于ai的非平均信息量，即

(2)然后分析收到bj后，從bj中獲得關于集合X的平均信息量，即

(3)最后分析收到集合Y后，從Y中獲得關于集合X的平均信息量，即

可知，平均互信息具有如下物理含義：

平均互信息≡(先驗的平均不確定性)－(觀察到集合Y以后對集合X保留的平均不確定性)≡平均不確定性消除的程度≡收到集合Y后獲得關于集合X的平均信息量。(3-15)由式(3-14)和式(3-15)可以推導下面等式也成立：

I(X;Y)=I(Y;X)=H(Y)－H(Y|X)

(3-16)

需要注意的是,平均互信息量I(X;Y)和互信息I(x;y)之間的異同。平均互信息量I(X;Y)是互信息I(x;y)在兩個概率空間X和Y的統計平均(數學期望)，互信息I(x;y)是代表收到消息y后獲得的關于事件x的信息量，可正可負，但平均互信息量I(X;Y)總是非負。

各類熵與平均互信息之間的關系如圖3-4所示。左邊的橢圓代表隨機變量X的熵，右邊的橢圓代表隨機變量Y的熵，兩個橢圓重疊部分代表平均互信息量I(X;Y)，每個橢圓減去平均互信息后剩余部分代表條件熵，兩個橢圓合在一起代表聯合熵。圖3-4平均互信息與各類熵之間的關系

3.平均互信息的性質

平均互信息I(X;Y)的主要特性如下：

(1)非負性，即I(X;Y)≥0。

非負性表明，平均互信息量I(X;Y)一般都為正數，即總能從接收信號Y中獲得或多或少關于X的信息，只有當X和Y統計獨立時，才收不到任何有用信息，此時互信息為零。

(2)極值性，即I(X;Y)≤min［H(X),H(Y)］。

極值性表明，從某一事件獲得另一事件的信息量，最多只有另一事件的信息熵那么多，不會超過該事件自身所含有的信息量。

(3)對稱性，即I(X;Y)=I(Y;X)。

對稱性表明，從Y中獲得的關于X的信息量等于從X中獲得的關于Y的信息量。

(4)凸狀性。由式(3-14)可得，

又(3-17)由此可知，平均互信息只是輸入信源X的概率分布P(X)和條件概率分布P(Y|X)的函數。凸狀性由兩部分組成，分別如下：

①平均互信息量I(X;Y)是信源概率分布P(X)的∩型凸函數，存在極大值。

②平均互信息量I(X;Y)是條件概率分布P(Y|X)的∪型凸函數，存在極小值。

(5)信息不增性，即I(X;Yn)≤I(X;Yn－1)≤…≤I(X;Y1)。

信息不增性表明，消息經過多級處理時(如圖3-5所示)，隨著處理級數的增多，輸入消息與輸出消息之間的平均互信息量趨于變小；也就是說，數據處理過程中，由于噪聲和干擾的存在，只會丟失信息而不會創造關于信源的新的信息。圖3-5消息的多級處理模型3.1.4有記憶信源的熵

對于離散無記憶信源，其熵可以用前面討論單符號離散信源的熵進行計算。然而實際的數字化后的媒體信源一般都是離散有記憶信源，即輸出序列中的符號存在前后相關性。此時需要用聯合概率分布函數或條件概率分布函數來描述信源發出的符號間的關系。本節主要介紹香農信息論中有關離散有記憶序列信源的熵。

設信源輸出的隨機序列為X，而X=(X1，X2，…，XL)，序列中每個單符號是一個隨機變量Xl∈Am={a1,a2,…,am}，l=1，2，…，L，即序列長度為L。序列熵定義為

H(X)=H(X1，X2，…，XL)

=H(X1)+H(X2|X1)+…+H(XL|X1，X2，…，XL－1)

(3-18)記作

平均每個符號的熵記作

對于序列信源的熵，有如下結論：

(1)H(XL|XL－1)是L的單調非增函數，即隨著L增加，條件熵H(XL|XL－1)會減小。

(2)HL(X)≥H(XL|XL－1)，即L長序列的平均符號熵大于等于在(X1，X2，…，XL－1)已知時XL出現的條件熵。

(3)HL(X)是L的單調非增函數，即隨著L增加，序列的平(3-20)(3-19)均符號熵會減小。

(4)定義極限熵(極限信息量)為

推廣結論(3)和(4)，可得如下不等式：

H∞(X)≤…≤HL(X)≤…≤H1(X)≤H0(X)=lbM

(3-22)

其中，H0(X)為信源的最大離散熵，M為信源輸出符號的總數，HL(X)為L長序列的平均符號熵。

結論(4)雖然從理論上定義了平穩離散有記憶信源的極限熵，但實際按此公式計算極限熵幾乎是不可能的。這是因為當L很大時，條件概率p(XL|XL－1)幾乎不可能被計算出來。幸運的是，對于一般離散平穩信源，由于L不是很大時，HL(X)就很接近H∞(X)，因此常取L很小的HL(X)作為H∞(X)的近似值。(3-21)3.1.5信源冗余度

冗余度(剩余度)是指給定信源在實際輸出消息時所包含的多余信息。如果表達一個消息的信息比特數比實際這個消息包含的比特數多，那么這樣的消息就存在冗余。

冗余度來自兩個方面：

(1)信源序列的前后符號存在相關性。從式(3-22)可以看出，對于有記憶信源，隨著信源序列長度增加，信源序列的平均單符號熵減小，這是由于信源序列前后符號存在相關性造成的。

(2)信源符號分布的不均勻性，當等概分布時信源熵最大。實際的信源這兩方面的冗余度都存在。對于一般平穩信源來說，極限熵為H∞(X)，這就是說要傳輸或編碼這一信源，理論上每符號平均只需要H∞(X)比特。這在后面無失真信源編碼定理介紹中會論述。但實際上對它的概率分布并不是完全清楚的，只能計算出HL(X)。若用HL(X)去編碼或傳輸極限熵為H∞(X)的信源，由于HL(X)≥H∞(X)，因此必然存在冗余。定義信息效率和冗余度為(3-23)(3-24)從式(3-23)和式(3-24)可以看出，信息效率一般小于1，冗余度一般大于0。編碼的目的就在于使信息效率盡量接近1，或者冗余度接近0。

事實上，當只知道信源符號有M個可能取值，而對其概率特性不清楚時，合理的假設就是這M個取值等概分布，因此此時有最大熵lbM，即H0。一旦測得其一維分布，就得到H1。根據式(3-22)可知H0－H1≥0，也就是說，用H1去編碼或傳輸信源比用H0去編碼或傳輸信源效率更高，冗余度更少。若所有維分布都可以得到，即可以求出H∞，此時編碼效率最高。

最后，考察英文文本和實際的圖像的熵值作為本小節結束。

【例3-6】以英文字母的符號為例來說明編碼效率和冗余度。

【解】英文字母共有26個，加上空格共27個符號，測得的平均符號熵如表3-1所示。表3-1英文字母出現熵值的測量

(比特/符號)從表3-1給出的熵值可以看到，隨著序列的長度增加，序列的平均符號熵逐步逼近極限熵。若采用一般傳輸方式(假設信源各輸出符號等概)，則信息效率和冗余度分別為

表3-2是對一組CCIR601號建議的電視圖像、四幅高清晰度電視圖像、CCITT建議的8幅傳真測試圖像，進行實際概率測量而得到的平均熵值。表3-2圖像熵值的測量

3.2編碼的基本概念

3.2.1編碼的數學定義

編碼實質上是對信源的輸出符號按一定的數學規則進行的一種變換，如圖3-6所示。圖3-6編碼器的一般定義圖3-6是編碼器的一般框圖。它的輸入是信源輸出符號集An={a1,a2，…，an}，信源的每個輸出x都取自該符號集，即x∈An。同時存在另一個碼符號集Wl={w1，w2，…，wl}，其每個元素稱為碼符號(或碼元)。編碼器將信源符號集的符號ai(或者長為L的序列ai1ai2…aiL變換成由w組成的長度為li的序列cj，cj的全體構成碼字集合Cm={c1，c2，…，cm}，簡稱“碼”。Cm每個元素都是由碼符號w組成的，其長度li(即符號w的個數)稱為碼字長度或簡稱碼長。編碼器的數學表示為

Y=C(X)

X∈An,Y∈Cm

(3-25)

上式中，C代表從信源符號到碼字符號的一種映射。若要實現無失真編碼，必要條件就是這種映射必須是一一對應的，此時，式(3-25)中的n=m；如果是實現有損壓縮編碼，則這種映射一般為多對一，此時式(3-25)中的n>m。

【例3-7】學生成績通常記為優、良、中、及格、不及格五種，試采用二進制編碼無失真該信源。

【解】該信源的符號集為A5={優、良、中、及格、不及格}，碼符號集W2={0，1}，可取碼字集C5={000，001，010，011，100}；信源符號集A5到碼字集C5的一一映射共有5！=120種，任取一種作為C：{優→000，良→001，中→010，及→011，不及格→100}。3.2.2常用碼的定義及分類

下面我們將給出一些常用碼的定義，并舉例說明。

1.分組碼和非分組碼

如果在編碼過程中，將信源符號分組，每組有固定對應的碼字，則稱之為分組碼；反之稱為非分組碼。表3-3中的全部碼都是分組碼。

2.二元碼和多元碼

根據碼符號集的碼符號個數m，可將碼分為m元碼。如碼符號集為W={0,1}，碼符號個數為2，編碼所得的碼字都是一些二元序列，則稱為二元碼。二元碼是數字通信和計算機系統中最常用的一種碼。表3-3所有碼字都為二元碼。

3.定長碼和變長碼

根據碼字集中的碼字長度，碼可以分為變長碼和定長碼兩類。若碼字集中所有碼字的長度都相同，即lj=l(j＝1,2,…,m),則稱為定長碼，如表3-3中的碼1;反之，則稱為變長碼，如表3-3中的其他碼。

4.奇異碼和非奇異碼

若碼字集中所有碼字都不相同，那么所有信源符號映射到不同的碼字，則稱之為非奇異碼，如表3-3中的碼1、2、4、5都是非奇異碼;反之，若碼字集中有相同的碼字，則稱為奇異碼，如表3-3中的碼3。

5.唯一可譯碼與非唯一可譯碼

若由碼字集的碼構成的任意一串有限長序列，只能唯一地譯成所對應的信源符號序列，則稱此碼為唯一可譯碼(單義可譯碼);反之稱為非唯一可譯碼(非單義可譯碼)。顯然,奇異碼不是唯一可譯碼，而非奇異碼有唯一可譯碼和非唯一可譯碼。表3-3中的碼1和碼2等都是唯一可譯碼，而碼3和碼4都是非唯一可譯碼。

6.即時碼和非即時碼

唯一可譯碼中又分為即時碼和非即時碼。如果接收端收到一個完整的碼字后，不能立即譯碼，還需等下一個碼字開始接收后才能判斷是否可以譯碼，這樣的碼叫做非即時碼;反之則稱為即時碼。如表3-3中的碼1和碼2等都是即時碼，而碼5雖然說是唯一可譯，但并不是即時碼。即時碼又稱為非延長碼，其特征是任意一個碼字都不是其他碼字的前綴部分，有時叫做異前綴碼。表3-3碼的不同屬性綜上所述，碼可以按圖3-7進行分類。圖3-7常用碼的分類3.2.3平均碼長與編碼效率

設離散無記憶平穩信源為

編碼后每個符號對應的碼字為w1，w2，…，wn；每個碼字對應的碼長為l1，l2，…，ln。定義該碼的平均長度為

實際編碼效率公式定義為(3-26)(3-27)

3.3唯一可譯碼的判斷與構造

3.3.1克勞夫特不等式

克勞夫特(Kraft)不等式給出了信源符號數和碼字長度之間應滿足什么條件才可能構成唯一可譯碼。該定理如下：

【定理3-3】對于碼符號集為Wl={w1，w2，…，wl}的任意m元唯一可譯碼(一般l=2m)，其構成的碼字集為Cn={c1，c2，…，cn}，對應碼長為l1，l2，…，ln，則碼長li必定滿足Kraft不等式(3-28)

上述不等式是唯一可譯碼存在的充要條件。必要性表現在如果碼是唯一可譯碼，則碼長必然滿足該不等式；充分性表現在如果碼長滿足該不等式，則這種碼長的唯一可譯碼一定存在。需要說明的是，該不等式是判定唯一可譯碼存在的充要條件，而不是判定唯一可譯碼的充要條件。這也就是說，并不是只要滿足上述不等式的碼，就一定是唯一可譯碼。

【例3-8】判斷表3-3中的碼是否為唯一可譯碼。

【解】根據前面討論的結果和Kraft不等式，判定結果如表3-4所示。從表中可以看到，碼1、碼2和碼4計算出的 都為1，即都滿足該不等式。然而實際上只有碼1和碼2是唯一可譯碼，而碼3是非唯一可譯碼。表3-4判定結果3.3.2唯一可譯碼的判斷準則

對于已知的某碼字集Cn={c1，c2，…，cn}，對應碼長為l1，l2，…，ln，如何判斷它是否是唯一可譯碼呢？

通過上面討論知道，Kraft不等式只能判斷某組碼長l1，l2，…，ln是否存在唯一可譯碼，它對于滿足不等式的碼不能做出正確判斷，因此不能用Kraft不等式來判斷某個碼字集Cn一定是唯一可譯碼。薩得納斯(A.A.Sardinas)和彼得森(G.W.Patterson)于1957年設計出一種判斷唯一可譯碼的測試方法，具體內容如下：

設S0為原始碼字的集合。再構造一系列集合S1,S2,…,Sn。為得到集合S1，首先分析S0中的所有碼字。若碼字Wj是碼字Wi的前綴，即Wi=WjA，則將后綴A列為S1中的元素，S1就是由所有具有這種性質的A構成的集合。一般地，要構成Sn(n>1)，則將S0與Sn－1比較。若有碼字W∈S0，且W是U∈Sn－1的前綴，即U=WA，則取后綴A為Sn中的元素。同樣，若有碼字U′∈Sn－1是W′∈S0的前綴，即W′=U′A′，則后綴A′亦為Sn中的元素。如此便可構成集合Sn。依此下去，直至集合為空或者沒有新的后綴產生。在得到集合S1,S2,…,Sn后，一種碼是唯一可譯碼的充要條件是S1,S2,…,Sn中沒有一個含有S0中的碼字。

【例3-9】設某信源消息集合共有7個元素{x1,x2,x3,x4,x5,x6,x7}，它們分別被編碼為{a,c,ad,abb,bad,deb,bbcde}。判定該碼組是否為唯一可譯碼。

【解】按照上述方法可構造出如表3-5所列的碼符號集序列。表3-5符號序列S1,S2,…,Sn3.3.3唯一可譯碼的構造

一種簡單的構造唯一可譯碼的方法就是采用碼樹，即采用樹圖來表示碼字的構成。樹圖最頂部的節點稱為樹根，從根節點分成m個樹枝，成為m進制樹(m等于碼符號數)。樹枝的盡頭是節點，中間節點生出樹枝，葉節點安排碼字，深度為L的m進制碼樹最多有mL個可能的葉節點。若將從每個節點出發的m個分支分別以0，1，…，m－1標號，則每個深度為r的節點需要用r個m元數字表示。如果想用某個深度為r的節點表示信源的一個符號，則該節點就不能再延伸，即該節點應該為葉節點(用粗黑點表示)，相應的碼字即為從樹根到此葉節點的分支標號序列，長度為r。這樣構造的碼一定滿足即時碼的條件，因為從樹根到每一個葉節點所走的路徑均不相同，故一定滿足異前綴的要求，即沒有一個碼字是另一個碼字的前綴。圖3-8給出一個二進制碼樹和一個三進制碼樹。圖3-8碼樹圖如果有q個信源符號，那么在碼樹上要選擇q個葉節點，用相應的從根節點到葉節點的分支標號序列代表該碼字，由這樣的方法構造出來的碼稱為碼樹。若碼樹的各個分支都延伸到葉節點，碼樹的深度為L，此時共有mL個碼字。這樣的碼樹稱為滿樹，否則稱為非滿樹。一般來說，滿樹對應著定長碼，非滿樹對應著變長碼。

因此，當我們按Kraft不等式的要求，對n個消息符號An={a1，a2，…，an}分配了長度為l1，l2，…，ln后，用二進制碼樹來生成即時碼的算法為：

①從根出發生出2枝；

②每枝用1個碼元符號wj∈W2={0，1}來表示；③枝盡節來，節外生枝。繼續生枝的節點是中間節點，不再生枝的節點為葉節點。深度為r的葉節點數量等于序列l1，l2，…，ln中lj=r的數量；

④給每個葉節點配置信源符號；

⑤連接從根節點到對應的葉節點的分枝上所遇到的碼元wj所構成的符號，即為該信源符號對應的二進制碼字ci。 3.4無失真信源編碼

信源編碼的目的在于增強信號傳輸或存儲時的有效性，減少冗余，提高編碼效率，也就是降低信源輸出符號的碼率。在無失真的情況下，要求解碼后信號能無失真地恢復出原始信號，即無失真信源編碼是可逆編碼，它只適合離散信源。

離散無記憶信源的編碼可以簡單描述如下：設離散無記憶信源X輸出符號序列x1x2…xl…，每個符號xl∈A={a1，a2，

…，an}。現將其分割成每L個為一組，組成L維矢量X，即Xi={x1,x2,…,xl,…,xL}，稱Xi為信源矢量。信源矢量Xi的全空間為AL，它共有nL種可能，對其用m個碼字Yk進行編碼表示，即Yk({b1，b2，…，bm}，一般取m≤nL。最后,編碼器的輸出為Y1Y2…Yi…。無失真信源編碼就是要求能夠無失真或無差錯地譯碼，即能從編碼器的輸出碼字Y無差錯地恢復編碼器的輸入矢量X，同時使傳送Y時所需要的信息率R最小。這個目標能否實現，最小信息率R又是多少，這正是無失真信源編碼定理要解決的問題。它又分為定長編碼定理和變長編碼定理。3.4.1無失真定長編碼定理

【定理3-4】由L個符號組成的平均符號熵為HL(X)的離散平穩無記憶信源進行定長編碼，設碼字是由w組成的長度為k的序列，其中w∈Wm={w1，w2，…，wm}。對于任意的ε>0、δ>0，只要滿足:

則當L足夠大時，必可使譯碼誤差小于δ，即譯碼錯誤概率可以任意小。反之，若

則不可能實現無失真編碼，而當L足夠大時，譯碼錯誤概率任意接近1。(3-29)式(3-29)可以改寫為

k*lbm≥L*HL(X)+ε

(3-30)

上式左邊是k長碼字最大攜帶的信息量，右邊為L長信源序列的平均信息量。上述定理表明，只要碼字所能攜帶的信息量大于信源序列輸出的信息量，則在L無限大條件下可以實現幾乎無失真編碼。如某離散信源輸出符號的概率分布為p(ai)={0.8,0.15,0.05}。要想使譯碼差錯δ<0.1，由于p(a3)=0.05<0.1，因此符號a3可以不編碼，因此可取L=1、k=1，實際的譯碼差錯δ=0.05(信源輸出符號a3時出現譯碼差錯)。如果取δ<0.01,可以對長度為2的信源序列進行等長編碼，此時信源一共有32=9種符號，符號p(a3a3)=0.0025<0.01，剩下8種符號需要3bit進行編碼，此時有L=2、k=3，實際的譯碼差錯δ=0.0025(信源輸出符號a3a3時出現譯碼差錯)。事實上，在已知信源輸出符號自信息量的方差D［I(x)］和熵H(X)的情況下，信源序列長度L與編碼效率η和允許錯誤概率δ的關系如式(3-31)。顯然，容許錯誤概率越小，編碼效率要越高，則信源序列長度L越長。在實際情況下，要實現幾乎無失真的等長編碼，L需要大到難以實現的程度。現我們來舉例說明。(3-31)

【例3-10】設離散無記憶信源 ，若對信源S采取等長二元編碼時，要求編碼效率η=0.96，允許錯誤概率δ≤10－5，問編碼碼長應該為多少？

【解】其信息熵為

其自信息的方差為若對信源S采取等長二元編碼，要求編碼效率η=0.96，允許錯誤概率δ≤10－5，則可求得：

即信源序列長度需長達4×107以上，才能實現給定的要求，這在實際中是很難實現的。由此可見，為提高編碼有效性需要付出很大的代價。因此，一般來說，對于無失真信源編碼，根據式(3-29)和式(3-30)，可以看出編碼效率總是小于1。

定長編碼定理的意義在于從理論上證明了編碼效率接近1的編碼器的存在性,但在實際實現中，通常都需要L非常大時才能使譯碼誤差δ很小，這在實際上是不可實現的。因此，一般來說，當L有限時，定長編碼往往要引入一定的失真(差錯)，它不能實現無失真的編碼。3.4.2無失真變長編碼定理

在變長編碼中，碼長k是變化的。變長編碼的基本思想就是概率匹配：即根據信源各個符號的概率統計特性分配不同長度的碼字，概率大的符號用短碼字，概率小的用長碼字，使得編碼后平均碼長最小，從而提高編碼效率。

【定理3-5】單符號信源變長編碼定理：設離散平穩無記憶信源的熵為H(X)，每個信源符號用m進制碼元進行變長編碼，必存在一種無失真編碼方法，使平均碼字長度滿足不等式：(3-32)

【定理3-6】序列信源變長編碼定理即香農第一定理：對由L個符號組成的、平均符號熵為HL(X)的離散平穩無記憶信源進行變長編碼，必存在一種無失真編碼方法，使平均碼字長度滿足不等式：

其中,ε為任意小正數。(3-33)變長編碼定理指出：要做到無失真信源編碼，編碼每個信源符號平均所需的最少m元碼元數就是信源的熵(信源的熵也以m進制進行測度)。若編碼的平均碼長小于信源的熵值，則唯一可譯碼不存在，在譯碼時必然要帶來失真或差錯。也就是說，信源的信息熵是無失真信源壓縮的極限值。同時，序列信源變長編碼定理也指出了達到這個極限值的途徑，即通過對信源進行L次擴展，當L→∞時，平均每個符號的碼長可以達到這個極限值。當然，減少平均碼長所付出的代價是增加了編碼的復雜性。

【例3-11】設離散平穩無記憶二元信源為

，試討論在L=1、2、3時的無失真最佳編碼及其編碼效率。

【解】信源熵

H(X)=－0.9×lb0.9－0.1×lb0.1=0.469比特/符號

當L=1時，信源每輸出一個符號就編一個碼，此時只有兩個符號，由于是無失真編碼，每種符號都需要一個碼字，因此最小平均碼長為1比特/符號。編碼效率為當L=2時，信源每輸出2個符號編一個碼，此時共有22=4種符號，概率分布如下：

采用Huffman編碼(具體編碼方法見下一章)方法得到的一種變長碼為0、10、110、111。短碼字對應大概率符號，長碼字對應小概率符號，即{0→a1a1,10→a1a2,110→a2a1,111→a2a2}。此時平均每個符號的碼長和編碼效率為當L=3時，信源每輸出3個符號編一個碼，此時共有23=8種符號。采用與上面相同的方法可得到=0.5327比特/符號，η3=88%。

繼續增加L，就可使每個符號的平均碼長→0.469比特/符號,ηL→1。

以上所討論的編碼定理，主要針對的是信源符號分布的不均勻性，并沒有考慮符號前后之間的相關性。考慮符號前后相關性的編碼方法主要是預測編碼、變換編碼等，這將在后續章節中進行介紹。 3.5率失真函數與限失真信源編碼

3.5.1失真函數

在實際應用中，信號有一定的失真是可以容忍的，如通信過程中的語音信號稍微有一點失真，人耳往往是察覺不到的，因而不影響通信質量。但是當失真大于某一限度后，信息質量將被嚴重損傷，甚至喪失其實用價值。要規定失真限度，必須先有一個定量的失真測度，為此可引入失真函數。

假如某一信源X，輸出符號為x(x∈{a1,a2,…,an})，經過有失真的信源編碼器，輸出Y，樣值為y(yj∈{b1,b2,…,bm})。如果x＝y，則認為沒有失真；如果x≠y，那么一般認為產生了失真。失真的大小用一個量d(ai，bj)來表示，以衡量用bj代替ai所引起的失真程度。一般失真函數定義為

所有的d(ai，bj)構成的矩陣［d(ai，bj)］稱為失真矩陣d，即(3-34)(3-35)需要指出的是，失真函數d(ai，bj)的數值是根據實際需要，人為決定用bj代替ai所導致的失真大小。常用的失真函數有以下幾個。

均方失真：

d(ai,bj)=(ai－bj)2

(3-36)

絕對失真：

d(ai,bj)=|ai－bj|

(3-37)

相對失真：(3-38)誤碼失真：

在實際應用中，選擇一個合適的、完全與主觀特性匹配(客觀度量出的失真大小與人主觀感覺的失真大小一致)的失真函數是非常困難的。信源不同，其對應的較好的失真函數也不相同，所以在實際問題中還有許多其他形式的失真函數。

由于x和y都是隨機變量，所以失真函數d(ai，bj)也是隨機變量，限失真時的總體失真大小用它的數學期望值(統計平均值)來度量，稱為平均失真，定義如下：(3-39)(3-40)3.5.2率失真函數R(D)

從式(3-40)不難得出，在信源的概率分布p(ai)和失真函數d(ai，bj)這兩個參量給定的情況下，平均失真只與p(bj|ai)有關。而p(bj|ai)則表征編碼器特征的參量，所以有損信源編碼產生的失真取決于編碼器的編碼條件轉移概率p(bj|ai)的分布。

信源編碼方式可用條件概率集合(3-41)對于信源編碼來說，平均互信息量I(X;Y)是編碼器輸出的信息率。信源編碼器的目的是使編碼輸出的信息率R盡量小，即在滿足平均失真≤D的條件下，選擇一種編碼方法使信息率R盡可能小。集合PD中的每個PC都滿足≤D這個條件，因此此時就是在集合PD中挑選使R最小的PC。根據平均互信息凸狀性性質第二條，I(X;Y)是條件概率分布P(Y|X)的∪型凸函數，存在極小值。因此，在上述允許信道PD中，一定可以找到一個PC(即p(bj|ai))，使給定的信源經過此編碼器后，平均互信息I(X;Y)達到最小，該最小的平均互信息就稱為信息率失真函數R(D)，即(3-42)對于離散無記憶信源，R(D)函數可寫成

其中，p(ai)，i＝1,2,…,n，是信源符號的概率分布；

p(bj/ai)，i＝1,2,…,n；j＝1,2,…,m，是編碼轉移概率分布；p(bj)，j＝1,2,…,m，是編碼輸出符號的概率分布。(3-43)

【例3-12】設信源的符號表為A＝{a1，a2，…，a2n},概率分布為 ,i＝1，2，…，2n，失真函數規定為 ，即符號不發生差錯時,失真為0，一

旦出錯失真為1，試研究在平均失真≤0.5的條件下信息壓縮的程度。

【解】由信源概率分布可求出信源的熵為這就是說，如果對信源進行不失真編碼，平均每個符號需要至少lb2n個比特。現在由于允許一定失真，平均失真要求小于等于0.5，即每100個符號允許有最多不超過50個符號有差錯。

設想這樣一個編碼方案：對a1到an的前n個符號，編碼器按照信源符號的原樣發送出去；而對an+1到a2n的后n個符號，都發送an，如圖3-9所示。這個方案肯定能達到失真要求，因為錯誤發生在發送an+1到a2n這些符號上，而這些符號出現的概率為0.5，因此平均失真為0.5。圖3-9編碼器的映射關系下面計算信源輸出的信息率。

由于編碼器的前n－1個符號輸入與輸出一一對應，因此輸出端b1到bn－1的出現概率為

又由于輸入端從an到a2n共有n+1個符號都是映射到輸出端的bn這個符號，因此bn出現的概率為

所以，編碼器輸出Y的熵為3.5.3率失真函數的性質

1.R(Dmin)和Dmin

Dmin代表最小失真，R(Dmin)代表在最小失真條件下的最小信息率。

由于D是非負實數d(ai，bj)(見式(3-40))的數學期望，因此D也是非負的實數。非負實數的下界是零，因此在選取d(ai，bj)時，一般在編碼沒有失真的情況下，其對應的D=Dmin=0，此時編碼器輸出端的熵等于信源的熵，因此有

R(Dmin)=R(0)=H(X)

(3-44)

2.R(Dmax)和Dmax

定義Dmax對應使R(D)=0的最小的D值，在有意義的允許失真中(即滿足R(D)>0)它是最大的。R(Dmax)代表在最大失真條件下的最小信息率。

由于平均互信息I(X;Y)是非負函數，而R(D)是在約束條件下的I(X;Y)最小值，因此R(D)也是一個非負函數，所以在最大失真條件下R(Dmax)=0。當R(D)為零時，意味著編碼器不需要輸出任何信息。這時編碼器輸入與輸出統計無關，所以條件概率p(bj|ai)與ai無關，即pij=p(bj|ai)=p(bj)=pj。因此有(3-45)

觀察上式可得：在j=1，2,…，m中，可找到使

值最小的j，當該j對應的pj=1，而其余pj為零時，上式右邊達到最小，這時上式可簡化成

3.凸狀性

R(D)是關于D的下凸函數，也是關于D的連續函數。

4.單調性

R(D)是關于D的嚴格遞減函數，即允許的平均失真越大，所要求的信息率越小。反之亦然。

根據以上結論，可畫出離散系統的R(D)的大致曲線，如圖3-10所示。(3-46)圖3-10離散系統的信息率失真曲線3.5.4率失真函數的計算及其指導意義與不足

【定理3-7】設信源的概率分布為P={p(a1),p(a2),…,p(an)}，失真矩陣為{d(ai,bj)}n×m。已知π為{1,2,…,n}上的一個置換,使p(ai)=pπ(ai)(i=1,2,…,n),ρ為{1,2,…,m}上的置換，使得d(ai,bj)=d(π(ai),ρ(bj))(i=1,2,…,n;j=1,2,…,m)，則存在一個達到信息率失真函數R(D)的編碼轉移概率分布Q={q(bj|ai}具有與{d(ai,bj)}n×m相同的對稱性，即

q(bj|ai)=q(ρ(bj)|π(ai)),

i=1,2,…,n;j=1,2,…,m(3-47)

【例3-13】設等概離散信源X的概率空間為

編碼輸出為

y=［b1,b2,…,br］

失真度定義為

求信息率失真函數R(D)。

【解】由已知易得

由定理3-7可得，存在與失真矩陣具有同樣對稱性的編碼轉移概率分布達到信息率失真函數R(D)，這個編碼轉移概率分布可以寫為在失真限制下,

所以有

此時可得相應的試驗編碼轉移概率矩陣為這時，容易計算出平均互信息為

相應的信息率失真曲線如圖3-11所示。圖3-11

r取值不同時對稱信源的R(D)從圖可知，對于同一平均失真度D，r越大，R(D)越大，信源壓縮性越小。若把r的取值看成信源分層后的符號數，即r越大就表示信源分層數越多。于是，在滿足相同的允許失真要求下，分層越多，信源的可壓縮性就越小；反之，分層越少，信源的可壓縮性就越大。這些規律對于實際信源的量化分層，數據壓縮有深刻的指導意義。

實際上，以率失真函數作為核心的率失真理論為有損信源編碼提供了定量分析的理論基礎。它指出了在給定平均失真的