《媒體信號(hào)編碼》課件第3章

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

3.2編碼的基本概念

3.3唯一可譯碼的判斷與構(gòu)造

3.4無失真信源編碼3.5率失真函數(shù)與限失真信源編碼

習(xí)題與思考題

3.1離散信源的熵

根據(jù)香農(nóng)信息論的理論，簡單離散信源X可以由信源符號(hào)的概率分布函數(shù)來描述，即

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

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

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

I(aj)=－logapj (3-4)另外，從發(fā)送端的角度來說，符號(hào)aj的概率pj本身就表示信息源X發(fā)出符號(hào)aj的一種不確定性。若pj大，則不確定性小，這時(shí)接收者收到符號(hào)aj的信息量就??；若pj小，則不確定性大，這時(shí)接收者收到符號(hào)aj的信息量就大。極端情況下，如果符號(hào)aj出現(xiàn)的概率pj=1，則接收者肯定只收到符號(hào)aj，其不確定性變?yōu)榱恪＿@些都與式(3-4)的計(jì)算結(jié)果一致，另外，根據(jù)對(duì)數(shù)函數(shù)的性質(zhì)和概率空間pj的定義，可知自信息量具有下列特性：

(1)pj=1,Ij=0;pj=0,Ij=∞?？芍厝皇录男畔⒘繛?，不可能事件的信息量無限大。

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

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

(4)可加性。若兩個(gè)符號(hào)ai、bj同時(shí)出現(xiàn)，可用聯(lián)合概率pi,j來表示。這時(shí)的自信息量I(ai,bj)=－logapi,j，當(dāng)ai和bj相互獨(dú)立時(shí)，有pi,j=pi*pj，那么此時(shí)信息量具有可加性，即I(ai,bj)=I(ai)+I(bj)。

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

【解】根據(jù)式(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離散信源熵及其性質(zhì)

1.熵的定義

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

離散信源熵的物理意義：它表征信源消息符號(hào)集合Am中符號(hào)出現(xiàn)的平均不確定性(或整體不確定性)，即為確定集合Am中某一符號(hào)出現(xiàn)所需的平均信息量(觀察之前)；反之，即為每出現(xiàn)一個(gè)符號(hào)所給出的平均信息量(觀察之后)。一般而言，信源給定后，信源的消息符號(hào)集合Am及其對(duì)應(yīng)的概率空間也隨之確定，信源的熵值就是一個(gè)確定值。當(dāng)然，不同的信源因?yàn)橄⒓霞案怕士臻g不一樣，熵值也不一樣。

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

【解】由于像素灰度均勻分布，則像素點(diǎn)為每一級(jí)灰度值的概率為1/256，因此有pi=1/256=2－8；又因?yàn)檎鶊D片有1024×768個(gè)像素，即m=1024×768，所以

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

【例3-3】二元信源是離散信源的特例。該信源消息符號(hào)集合有兩個(gè)，分別用0和1表示。對(duì)應(yīng)的符號(hào)概率分布為p和q，且p+q=1。求該信源的熵。

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

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

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

【例3-4】某信源有4個(gè)符號(hào)，出現(xiàn)概率如下：

求該信源的熵。

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

2.聯(lián)合熵、條件熵的定義

設(shè)信源X和Y的消息符號(hào)集分別為Am={a1,a2,…,am}和Bn={b1,b2,…,bn}，對(duì)X和Y做笛卡爾積，就構(gòu)成聯(lián)合信源X×Y，我們把X與Y的聯(lián)合熵H(X,Y)定義為

其中，p(ai,bj)為聯(lián)合信源X×Y取值為(ai,bj)的概率。聯(lián)合熵H(X,Y)的物理意義為聯(lián)合信源X×Y的消息符號(hào)集合上的每對(duì)元素(ai,bj)的自信息量的概率加權(quán)統(tǒng)計(jì)平均值(數(shù)學(xué)期望),或者說X和Y同時(shí)發(fā)生的平均不確定度。(3-6)我們把X與Y的條件熵定義為

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

證明聯(lián)合熵H(X,Y)和條件熵H(X|Y)、H(Y|X)以及單符號(hào)熵H(X)、H(Y)之間存在如下關(guān)系：

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

【例3-5】設(shè)離散二維平穩(wěn)信源X的概率空間如下：

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

3.熵的性質(zhì)

熵的主要特性如下：

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

該性質(zhì)是很顯然的。因?yàn)殡S機(jī)變量X的所有取值的概率分布滿足0<pi<1，當(dāng)取對(duì)數(shù)的底大于1時(shí)，lbpi<0，而－pilbpi>0，則得到的熵是正值。只有當(dāng)隨機(jī)變量X為確定事件，即某一事件ai出現(xiàn)概率為1時(shí)等號(hào)才成立。

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

上式表明，熵函數(shù)所有變?cè)猵1、p2、…、pn位置可以互換，而不影響熵的大小。該性質(zhì)說明：熵只與信源的總體統(tǒng)計(jì)特性有關(guān)。如果某些信源的統(tǒng)計(jì)特性相同(含有的符號(hào)數(shù)和概率分布相同)，那么這些信源的熵就相同。

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

上式表明，只要信源符號(hào)中有一個(gè)符號(hào)的出現(xiàn)概率為1，信源熵就等于零。這是因?yàn)楫?dāng)一個(gè)符號(hào)的概率為1后(必然事件)，根據(jù)概率的公理化定義，其他符號(hào)的概率也必然為0(不可能事件)，因此該信源沒有不確定性。

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

上式表明，兩個(gè)信源X和Y的聯(lián)合信源的熵等于信源X的熵加上在X已知條件下信源Y的條件熵；或者等于信源Y的熵加上在Y已知條件下信源X的條件熵。對(duì)于統(tǒng)計(jì)獨(dú)立信源X和Y，則其聯(lián)合信源的熵等于各個(gè)熵之和。

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

上式表明，條件熵一般都小于無條件熵，只有當(dāng)X與Y統(tǒng)計(jì)獨(dú)立時(shí)條件熵才等于無條件熵。這說明在獲得信源X的某種相關(guān)信息Y后X的不確定性已經(jīng)減少。

(6)香農(nóng)輔助定理。

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

該式表明，對(duì)任意概率分布pi，它對(duì)其他概率分布qi的自信息量－lbqi取數(shù)學(xué)期望時(shí)，必大于pi本身的熵。等號(hào)僅當(dāng)P=Q時(shí)成立。(3-10)

(7)最大熵定理。

【定理3-2】離散無記憶信源輸出M個(gè)不同的消息符號(hào)，當(dāng)且僅當(dāng)各個(gè)符號(hào)出現(xiàn)概率相等時(shí)(即pi=1/M),熵最大,即

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

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

非平均互信息量指單個(gè)符號(hào)之間的互信息，一般用I(ai;bj)表示，其物理意義為觀察到bj后收到關(guān)于ai的信息量，香農(nóng)將其定義為符號(hào)后驗(yàn)概率與先驗(yàn)概率比值的對(duì)數(shù)，即

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

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

I(X;Y)是指兩個(gè)集合之間的平均互信息量。例如，對(duì)于圖3-3所示的簡化通信系統(tǒng)模型，信源X經(jīng)過信道傳輸或信號(hào)處理后，得到信宿Y。根據(jù)香農(nóng)信息論，兩者之間的平均互信息量I(X;Y)可定義為互信息量I(ai;bj)的概率加權(quán)平均值(數(shù)學(xué)期望)，即

式中，I(X;Y)就是在收到集合Y后所能獲得的關(guān)于集合X的平均信息量，即平均互信息量，簡稱平均互信息，也稱平均交互信息量或交互熵。(3-14)圖3-3簡化通信系統(tǒng)模型下面根據(jù)前面所學(xué)的知識(shí)來推導(dǎo)平均互信息具體應(yīng)用的計(jì)算表達(dá)式。

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

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

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

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

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

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)在兩個(gè)概率空間X和Y的統(tǒng)計(jì)平均(數(shù)學(xué)期望)，互信息I(x;y)是代表收到消息y后獲得的關(guān)于事件x的信息量，可正可負(fù)，但平均互信息量I(X;Y)總是非負(fù)。

各類熵與平均互信息之間的關(guān)系如圖3-4所示。左邊的橢圓代表隨機(jī)變量X的熵，右邊的橢圓代表隨機(jī)變量Y的熵，兩個(gè)橢圓重疊部分代表平均互信息量I(X;Y)，每個(gè)橢圓減去平均互信息后剩余部分代表?xiàng)l件熵，兩個(gè)橢圓合在一起代表聯(lián)合熵。圖3-4平均互信息與各類熵之間的關(guān)系

3.平均互信息的性質(zhì)

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

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

非負(fù)性表明，平均互信息量I(X;Y)一般都為正數(shù)，即總能從接收信號(hào)Y中獲得或多或少關(guān)于X的信息，只有當(dāng)X和Y統(tǒng)計(jì)獨(dú)立時(shí)，才收不到任何有用信息，此時(shí)互信息為零。

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

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

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

對(duì)稱性表明，從Y中獲得的關(guān)于X的信息量等于從X中獲得的關(guān)于Y的信息量。

(4)凸?fàn)钚?。由?3-14)可得，

又(3-17)由此可知，平均互信息只是輸入信源X的概率分布P(X)和條件概率分布P(Y|X)的函數(shù)。凸?fàn)钚杂蓛刹糠纸M成，分別如下：

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

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

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

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

對(duì)于離散無記憶信源，其熵可以用前面討論單符號(hào)離散信源的熵進(jìn)行計(jì)算。然而實(shí)際的數(shù)字化后的媒體信源一般都是離散有記憶信源，即輸出序列中的符號(hào)存在前后相關(guān)性。此時(shí)需要用聯(lián)合概率分布函數(shù)或條件概率分布函數(shù)來描述信源發(fā)出的符號(hào)間的關(guān)系。本節(jié)主要介紹香農(nóng)信息論中有關(guān)離散有記憶序列信源的熵。

設(shè)信源輸出的隨機(jī)序列為X，而X=(X1，X2，…，XL)，序列中每個(gè)單符號(hào)是一個(gè)隨機(jī)變量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)記作

平均每個(gè)符號(hào)的熵記作

對(duì)于序列信源的熵，有如下結(jié)論：

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

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

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

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

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

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

(3-22)

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

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

冗余度(剩余度)是指給定信源在實(shí)際輸出消息時(shí)所包含的多余信息。如果表達(dá)一個(gè)消息的信息比特?cái)?shù)比實(shí)際這個(gè)消息包含的比特?cái)?shù)多，那么這樣的消息就存在冗余。

冗余度來自兩個(gè)方面：

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

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

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

最后，考察英文文本和實(shí)際的圖像的熵值作為本小節(jié)結(jié)束。

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

【解】英文字母共有26個(gè)，加上空格共27個(gè)符號(hào)，測(cè)得的平均符號(hào)熵如表3-1所示。表3-1英文字母出現(xiàn)熵值的測(cè)量

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

表3-2是對(duì)一組CCIR601號(hào)建議的電視圖像、四幅高清晰度電視圖像、CCITT建議的8幅傳真測(cè)試圖像，進(jìn)行實(shí)際概率測(cè)量而得到的平均熵值。表3-2圖像熵值的測(cè)量

3.2編碼的基本概念

3.2.1編碼的數(shù)學(xué)定義

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

Y=C(X)

X∈An,Y∈Cm

(3-25)

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

【例3-7】學(xué)生成績通常記為優(yōu)、良、中、及格、不及格五種，試采用二進(jìn)制編碼無失真該信源。

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

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

1.分組碼和非分組碼

如果在編碼過程中，將信源符號(hào)分組，每組有固定對(duì)應(yīng)的碼字，則稱之為分組碼；反之稱為非分組碼。表3-3中的全部碼都是分組碼。

2.二元碼和多元碼

根據(jù)碼符號(hào)集的碼符號(hào)個(gè)數(shù)m，可將碼分為m元碼。如碼符號(hào)集為W={0,1}，碼符號(hào)個(gè)數(shù)為2，編碼所得的碼字都是一些二元序列，則稱為二元碼。二元碼是數(shù)字通信和計(jì)算機(jī)系統(tǒng)中最常用的一種碼。表3-3所有碼字都為二元碼。

3.定長碼和變長碼

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

4.奇異碼和非奇異碼

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

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

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

6.即時(shí)碼和非即時(shí)碼

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

設(shè)離散無記憶平穩(wěn)信源為

編碼后每個(gè)符號(hào)對(duì)應(yīng)的碼字為w1，w2，…，wn；每個(gè)碼字對(duì)應(yīng)的碼長為l1，l2，…，ln。定義該碼的平均長度為

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

3.3唯一可譯碼的判斷與構(gòu)造

3.3.1克勞夫特不等式

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

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

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

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

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

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

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

設(shè)S0為原始碼字的集合。再構(gòu)造一系列集合S1,S2,…,Sn。為得到集合S1，首先分析S0中的所有碼字。若碼字Wj是碼字Wi的前綴，即Wi=WjA，則將后綴A列為S1中的元素，S1就是由所有具有這種性質(zhì)的A構(gòu)成的集合。一般地，要構(gòu)成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中的元素。如此便可構(gòu)成集合Sn。依此下去，直至集合為空或者沒有新的后綴產(chǎn)生。在得到集合S1,S2,…,Sn后，一種碼是唯一可譯碼的充要條件是S1,S2,…,Sn中沒有一個(gè)含有S0中的碼字。

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

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

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

因此，當(dāng)我們按Kraft不等式的要求，對(duì)n個(gè)消息符號(hào)An={a1，a2，…，an}分配了長度為l1，l2，…，ln后，用二進(jìn)制碼樹來生成即時(shí)碼的算法為：

①從根出發(fā)生出2枝；

②每枝用1個(gè)碼元符號(hào)wj∈W2={0，1}來表示；③枝盡節(jié)來，節(jié)外生枝。繼續(xù)生枝的節(jié)點(diǎn)是中間節(jié)點(diǎn)，不再生枝的節(jié)點(diǎn)為葉節(jié)點(diǎn)。深度為r的葉節(jié)點(diǎn)數(shù)量等于序列l(wèi)1，l2，…，ln中l(wèi)j=r的數(shù)量；

④給每個(gè)葉節(jié)點(diǎn)配置信源符號(hào)；

⑤連接從根節(jié)點(diǎn)到對(duì)應(yīng)的葉節(jié)點(diǎn)的分枝上所遇到的碼元wj所構(gòu)成的符號(hào)，即為該信源符號(hào)對(duì)應(yīng)的二進(jìn)制碼字ci。 3.4無失真信源編碼

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

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

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

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

則當(dāng)L足夠大時(shí)，必可使譯碼誤差小于δ，即譯碼錯(cuò)誤概率可以任意小。反之，若

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

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

(3-30)

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

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

【解】其信息熵為

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

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

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

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

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

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

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

【例3-11】設(shè)離散平穩(wěn)無記憶二元信源為

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

【解】信源熵

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

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

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

繼續(xù)增加L，就可使每個(gè)符號(hào)的平均碼長→0.469比特/符號(hào),ηL→1。

以上所討論的編碼定理，主要針對(duì)的是信源符號(hào)分布的不均勻性，并沒有考慮符號(hào)前后之間的相關(guān)性?？紤]符號(hào)前后相關(guān)性的編碼方法主要是預(yù)測(cè)編碼、變換編碼等，這將在后續(xù)章節(jié)中進(jìn)行介紹。 3.5率失真函數(shù)與限失真信源編碼

3.5.1失真函數(shù)

在實(shí)際應(yīng)用中，信號(hào)有一定的失真是可以容忍的，如通信過程中的語音信號(hào)稍微有一點(diǎn)失真，人耳往往是察覺不到的，因而不影響通信質(zhì)量。但是當(dāng)失真大于某一限度后，信息質(zhì)量將被嚴(yán)重?fù)p傷，甚至喪失其實(shí)用價(jià)值。要規(guī)定失真限度，必須先有一個(gè)定量的失真測(cè)度，為此可引入失真函數(shù)。

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

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

均方失真：

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

(3-36)

絕對(duì)失真：

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

(3-37)

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

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

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

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

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

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

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

【例3-12】設(shè)信源的符號(hào)表為A＝{a1，a2，…，a2n},概率分布為 ,i＝1，2，…，2n，失真函數(shù)規(guī)定為 ，即符號(hào)不發(fā)生差錯(cuò)時(shí),失真為0，一

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

【解】由信源概率分布可求出信源的熵為這就是說，如果對(duì)信源進(jìn)行不失真編碼，平均每個(gè)符號(hào)需要至少lb2n個(gè)比特?，F(xiàn)在由于允許一定失真，平均失真要求小于等于0.5，即每100個(gè)符號(hào)允許有最多不超過50個(gè)符號(hào)有差錯(cuò)。

設(shè)想這樣一個(gè)編碼方案：對(duì)a1到an的前n個(gè)符號(hào)，編碼器按照信源符號(hào)的原樣發(fā)送出去；而對(duì)an+1到a2n的后n個(gè)符號(hào)，都發(fā)送an，如圖3-9所示。這個(gè)方案肯定能達(dá)到失真要求，因?yàn)殄e(cuò)誤發(fā)生在發(fā)送an+1到a2n這些符號(hào)上，而這些符號(hào)出現(xiàn)的概率為0.5，因此平均失真為0.5。圖3-9編碼器的映射關(guān)系下面計(jì)算信源輸出的信息率。

由于編碼器的前n－1個(gè)符號(hào)輸入與輸出一一對(duì)應(yīng)，因此輸出端b1到bn－1的出現(xiàn)概率為

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

所以，編碼器輸出Y的熵為3.5.3率失真函數(shù)的性質(zhì)

1.R(Dmin)和Dmin

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

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

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

(3-44)

2.R(Dmax)和Dmax

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

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

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

值最小的j，當(dāng)該j對(duì)應(yīng)的pj=1，而其余pj為零時(shí)，上式右邊達(dá)到最小，這時(shí)上式可簡化成

3.凸?fàn)钚?/p>

R(D)是關(guān)于D的下凸函數(shù)，也是關(guān)于D的連續(xù)函數(shù)。

4.單調(diào)性

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

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

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

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

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

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

編碼輸出為

y=［b1,b2,…,br］

失真度定義為

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

【解】由已知易得

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

所以有

此時(shí)可得相應(yīng)的試驗(yàn)編碼轉(zhuǎn)移概率矩陣為這時(shí)，容易計(jì)算出平均互信息為

相應(yīng)的信息率失真曲線如圖3-11所示。圖3-11

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

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