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

第二章無(wú)失真信源編碼信息量、熵和互信息信源編碼定理霍夫曼碼及其他編碼方法算術(shù)編碼游程編碼改進(jìn)的霍夫曼碼通用編碼第二章無(wú)失真信源編碼無(wú)失真編碼：保證信源產(chǎn)生的全部信息無(wú)失真地傳遞給信宿。（只有對(duì)離散信源可以實(shí)現(xiàn)無(wú)失真信源編碼。）實(shí)質(zhì)上是一種概率匹配編碼。限失真信源編碼：在確定標(biāo)準(zhǔn)和準(zhǔn)則的條件下，信源所必須傳遞的最小信息量。也稱(chēng)信息率失真函數(shù)（限定波形失真——波形編碼，限定特性參量失真——參量編碼）。第二章無(wú)失真信源編碼信源中的統(tǒng)計(jì)多余度主要取決于以下兩個(gè)主要因素：一是消息概率分布的非均勻性，另一個(gè)是消息間的相關(guān)性。對(duì)無(wú)記憶信源主要取決于概率分布的非均勻性，但是，對(duì)于有記憶信源，兩者都起作用，且相關(guān)性更加重要。第二章無(wú)失真信源編碼統(tǒng)計(jì)匹配編碼：是根據(jù)信源的不同概率分布而選用與之相匹配的編碼，以達(dá)到的系統(tǒng)同中傳信速率最小，且滿(mǎn)足在信宿復(fù)制時(shí)無(wú)失真或低于某一允許的失真限度值。2．1信息量、熵和互信息量時(shí)間發(fā)生的概率越小，不確定性就越大，給人的信息量就越?。话l(fā)生的概率越大，不確定性就越小，給人的信息量就越大。

條件概率聯(lián)合概率必須掌握的概率論知識(shí)必須掌握的概率論知識(shí)全概率：設(shè)B1

,B2

,…是一列互不相容的事件(Bi

Bj=0），且有B1

∪B2

∪…=Ω（樣本空間）；p（Bi）＞0，i=1，2，…，則對(duì)任一事件A，有：必須掌握的概率論知識(shí)4)Bayes公式:

設(shè)B1

,B2

,…是一列互不相容的事件(Bi

Bj=0），且有B1

∪B2

∪…=Ω（樣本空間）；

p（Bi）＞0，i=1，2，…，則對(duì)任一事件A，有：一個(gè)離散無(wú)記憶信源是由n個(gè)符號(hào)消息組成的集合:X={x1，x2

·

··xn

}，這n個(gè)符號(hào)消息的概率分布為了：稱(chēng)為符號(hào)xi

的先驗(yàn)概率,散信源數(shù)學(xué)模型表示為：

稱(chēng)為概率空間,其中從概率的角度看，可以將符號(hào)消息xi看一個(gè)隨機(jī)事件。因此xi具有不確定性。

2．1信息量、熵和互信息量信息量定義：2．1信息量、熵和互信息量信息量定義：美國(guó)科學(xué)家L.V.R.Hartley

于1928年給出了信息的度量方法。定義若信源發(fā)出一符號(hào)xi，由于信道存在干擾，收到的不是xi而是yi，從yi中獲取有關(guān)xi的信息量用I(xi；yi)表示，稱(chēng)為互信息量。

定義上述情況，若信道無(wú)干擾，收到的就是xi本身，這樣I(xi；yi)就可以用I(xi；xi)表示，或簡(jiǎn)單記作I(xi)，并稱(chēng)為自信息量。一、自信息量1)函數(shù)I(xi)的屬性

1o若有兩個(gè)事件xi

，xj

，其先驗(yàn)概率為p(xi)＜p(xj)，則事件xi比事件xj有更大的不確定性，同時(shí)會(huì)帶來(lái)更多的信息量；I(xi

)>I(xj

)2o事件xi先驗(yàn)概率p(xi)=1（確定事件）,則不存在不確定性，同時(shí)不會(huì)帶來(lái)信息量；I(xi)=0.3o事件xi先驗(yàn)概率p(xi)=0（不可能事件）,則存在不確定性應(yīng)為無(wú)窮大，同時(shí)會(huì)帶來(lái)無(wú)窮的信息量；I(xi)→∞.4o兩個(gè)統(tǒng)計(jì)獨(dú)立事件的聯(lián)合自信息量應(yīng)等于它們各自信息量之和;則I(xy)=

I(x)＋I(xiàn)(y)2)

定義一個(gè)符號(hào)消息xi的自信息量為其發(fā)生概率的對(duì)數(shù)的負(fù)數(shù)，并記為I(xi)：

I(xi)=－logp(xi)

當(dāng)p(xi)=0，則I(xi)→∞；當(dāng)p(xi)=1，則I(xi)=0.3)自信息量的單位自信息量的單位與所用對(duì)數(shù)的底有關(guān)：

1o對(duì)數(shù)的底是2時(shí)，單位為比特—bit(binaryunit)2o對(duì)數(shù)的底是e(自然對(duì)數(shù))時(shí)，單位為奈特

—nat(natureunit)3o對(duì)數(shù)的底是10(常用對(duì)數(shù))時(shí)，單位為笛特或哈特

—det(decimalunit)orHart(Hartley)三種信息量單位之間的換算：

1det=log210≈3.322bit1bit=ln2≈0.6931nat

1bit=lg

2≈0.3010det1nat=log2e≈1.4427bit

在信息論中常用以2為底的對(duì)數(shù)，為了書(shū)寫(xiě)方便，以后將log2書(shū)寫(xiě)為log，因其單位為比特bit，不會(huì)產(chǎn)生混淆；注意有些文獻(xiàn)將log2書(shū)寫(xiě)為lb4)自信息量的含義是隨機(jī)量、根據(jù)單個(gè)符號(hào)消息的先驗(yàn)概率確定其信息量和不確定度。二、離散信源熵信源X發(fā)出某一個(gè)符號(hào)提供的信息量不適合描述信源X發(fā)出一個(gè)符號(hào)提供的信息量。定義信息源的平均不確定度為信源中各個(gè)符號(hào)不確定度的數(shù)學(xué)期望，記作H(X)

其中

H(X)又稱(chēng)為信源X的信源熵。

2)H(X)

的含義

1o表示的是信源的平均不確定度。

2o表示信源X發(fā)出一個(gè)符號(hào)提供的平均信息量。

3o是統(tǒng)計(jì)量、數(shù)學(xué)期望（統(tǒng)計(jì)平均）、各個(gè)符號(hào)平均不確定度和平均信息量。

3)

信源熵單位：二進(jìn)制:bit/信源符號(hào)，或bit/信源序列十進(jìn)制:det/信源符號(hào)，或det/信源序列

e進(jìn)制:nat/信源符號(hào)，或nat/信源序列

4)信源熵的三種特殊情況1o當(dāng)

p(xi)=0時(shí)（p(xi)→0），則p(xi)logp(xi)=02o信源X={x1，x2

·

··xn

}

，若其中xi

的概率p(xi)=1

則其余xj

的p(xj)=0，因?yàn)閯tH(X)=0bit/信源符號(hào)3o當(dāng)信源中X所有n個(gè)符號(hào)均有相同的概率p(xi)=1/n，

則H(X)=-(1/n)log(1/n)=lognbit/信源符號(hào)2o聯(lián)合熵（共熵）

聯(lián)合熵是聯(lián)合符號(hào)集合XY上的每個(gè)元素對(duì)xi

,

yj的自信息量的概率加權(quán)的統(tǒng)計(jì)平均值。3o條件熵與聯(lián)合熵的關(guān)系

I(xi

|yj)=－logp(xi

|

yj)

，I(xi

yj)=－logp(xi

yj)

因

全概率公式5)條件熵與聯(lián)合熵

1o條件熵在給定yj條件下，xi的條件自信息量為：

I(xi

|yj)=－logp(xi

|

yj)

集合X的條件熵為：

在給定Y（即各個(gè)yj）條件下，集合X的條件熵定義為：三、互信息（一）簡(jiǎn)單的通信模型

若信源發(fā)出符號(hào)xi，由于信道存在干擾，收到的不是xi而是yi，從yi中獲取有關(guān)xi的信息量稱(chēng)為互信息量，用I(xi;yi)表示。信源X有干擾離散信道信宿Y干擾源所以H(XY)=H(X

)＋H(Y|X)同理H(XY)=H(Y)＋H(X|Y)含義：平均從Y獲得的關(guān)于X的信息量。 （又稱(chēng)信道 的信息傳輸率R）（二）平均互信息※I(X;Y)與熵：※I(X;Y)與I(x;y)：

I(x;y)表示由隨機(jī)事件y中獲得的關(guān)于事件x的信息?；バ畔?關(guān)系：I(X;Y)＝EXY[I(x;y)]注意：（二）平均互信息

※比較：I(x;y)可正可負(fù)，1．非負(fù)性I(X;Y)≥0（三）平均互信息的性質(zhì)

※

當(dāng)I(X;Y)=0全損信道：H(X)=H(X|Y)，說(shuō)明：

通信的意義——通過(guò)消息的傳遞可獲得信息信源加密密鑰源信道解密信宿保密通信系統(tǒng)框圖XY’Y非法用戶(hù)全損信道（三）平均互信息的性質(zhì)

※信息處理的一般規(guī)律：通過(guò)傳輸獲得的信息量不大于提供的信息量。

※

I(X;Y)=H(X)無(wú)損信道：H(X|Y)=02．

極值性，P(x|y)=0or1（三）平均互信息的性質(zhì)

I(X;Y)=I(Y;X)３．交互性（對(duì)稱(chēng)性)（三）平均互信息的性質(zhì)I(X;Y)=H(X)－H(X|Y)=H(Y)－H(Y|X)

4.

I(X;Y)與各類(lèi)熵的關(guān)系

文氏圖H(X∣Y)H(Y∣X)信源熵信道疑義度噪聲熵（散布度）I(X;Y)

=H(X)+H(Y)－H(XY)信宿熵H(XY)（三）平均互信息的性質(zhì)特殊信道特殊信道總結(jié)

信道名稱(chēng)信道特征信息傳輸情況全損信道P(xy)=P(x)P(y)H(X︱Y)=H(X)I(X；Y)=0無(wú)噪信道

P(y︱x)=0or1H(Y︱X)=0I(X；Y)=H(Y)無(wú)損信道

P(x︱y)=0or1H(X︱Y)=0I(X；Y)=H(X)（三）平均互信息的性質(zhì)

5．

凸?fàn)钚訧(X;Y)=f[P(x)，P(y|x)]（三）平均互信息的性質(zhì)Th3.2：對(duì)于固定信源分布，平均互信息I(X;Y)是信道傳遞概率p(y|x)的∪型凸函數(shù)。※不同信源通過(guò)不同信道傳輸?shù)玫降钠骄バ畔⒉煌?/p>

5．

凸?fàn)钚訲h3.1：對(duì)于固定信道，平均互信息I(X;Y)是信源概率分布p(x)的∩型凸函數(shù)。平均互信息是信源符號(hào)概率分布的上凸函數(shù)平均互信息是信道轉(zhuǎn)移概率的下凹函數(shù)（三）平均互信息的性質(zhì)

例1．

分析二元信源通過(guò)BSC信道的I(X;Y)特性信源：，信道：1－p1－ppp0011則（三）平均互信息的性質(zhì)其中，

（三）平均互信息的性質(zhì)，得：（三）平均互信息的性質(zhì)

I.

固定信道（p一定），∴H(p)一定I(X;Y)∝H(ω+p－2ωp)由熵上凸性的該I(X;Y)為ω的上凸函數(shù)I(X;Y)1－H(p)01/21ωω＝1/2時(shí)，I(X;Y)極大I(X;Y)＝H(1/2)－H(p)=1－H(p)

（三）平均互信息的性質(zhì)Ⅱ.

固定信源（ω一定）則I(X;Y)～p，∴I(X;Y)=I(p)∴I(p)為下凹函數(shù)可求：p=1/2,I(X;Y)=0,極小p=0,I(X;Y)=H(ω)p=1,I(X;Y)=H(ω)I(X;Y)01/21p（三）平均互信息的性質(zhì)2．2信源編碼定理信源編碼的無(wú)失真編碼：接收端信宿要求無(wú)失真精確的復(fù)制信源輸出的消息。只有對(duì)離散信源才可以實(shí)現(xiàn)無(wú)失真編碼。實(shí)質(zhì)上是一種統(tǒng)計(jì)匹配編碼——根據(jù)信源的不同概率分布而選用與之相匹配的編碼，以達(dá)到在系統(tǒng)中傳送速率最小，且滿(mǎn)足在信宿復(fù)制時(shí)無(wú)失真或低于某一允許的失真限度值。2．2．1信源編碼的基本概念信源編碼：將信源輸出符號(hào)，經(jīng)信源編碼器變換成另外的壓縮符號(hào)，然后將壓縮有信息經(jīng)信道傳送到信宿。只考慮信源和信宿兩個(gè)因素。通信系統(tǒng)模型簡(jiǎn)化為P15圖2-1編碼A器輸入為：編碼器輸出的碼字為：符號(hào)碼1碼2碼3碼4等長(zhǎng)碼變長(zhǎng)碼u100001u201101101u3100000001u311011100012．2．1信源編碼的基本概念樹(shù)圖（碼樹(shù)）法：樹(shù)根=碼字的起點(diǎn)樹(shù)的度=碼元數(shù)分支結(jié)點(diǎn)=碼的符號(hào)的一部分終端結(jié)點(diǎn)=待編碼符號(hào)滿(mǎn)樹(shù)=等長(zhǎng)碼：樹(shù)中各結(jié)點(diǎn)有相同樹(shù)枝數(shù)，且每層結(jié)點(diǎn)樹(shù)達(dá)到最大值。非滿(mǎn)樹(shù)=變長(zhǎng)碼2．2．1信源編碼的基本概念編碼方法：1）將待編碼的字符作為終端結(jié)點(diǎn)，構(gòu)造碼樹(shù)；2）按一定規(guī)則給每個(gè)樹(shù)枝分配一個(gè)標(biāo)記；3）將從根到終端結(jié)點(diǎn)的路徑上的編號(hào)依次相連，作為該終端結(jié)點(diǎn)所表示的字符的編碼。2．2．1信源編碼的基本概念譯碼方法：1）從樹(shù)根出發(fā)，根據(jù)接收到的第一個(gè)碼字符號(hào)來(lái)選擇應(yīng)走的第一條路徑。2）沿所選路徑走到分支結(jié)點(diǎn)，在根據(jù)收到的第而個(gè)碼字選擇應(yīng)走的第二條路徑。直至走到終端結(jié)點(diǎn)為止。3）根據(jù)所走路徑，可立即判斷出接收到的碼符號(hào)。4）重新返回到樹(shù)根，再作下一個(gè)接收碼符號(hào)的判斷。2．2．1信源編碼的基本概念

分組碼（塊碼）分類(lèi)

1°按碼字的碼長(zhǎng)分類(lèi)定長(zhǎng)碼：碼集中所有碼字的碼長(zhǎng)相等。變長(zhǎng)碼：碼集中所有碼字的碼長(zhǎng)不全相等。

2°按信源符號(hào)與碼字對(duì)應(yīng)關(guān)系分類(lèi)非奇異碼：信源符號(hào)與碼字是一一對(duì)應(yīng)的。奇異碼：信