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

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

第五頁(yè)，共四十三頁(yè)，編輯于2023年，星期四條件概率聯(lián)合概率必須掌握的概率論知識(shí)第六頁(yè)，共四十三頁(yè)，編輯于2023年，星期四必須掌握的概率論知識(shí)全概率：設(shè)B1

,B2

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

Bj=0），且有B1

∪B2

∪…=Ω（樣本空間）；p（Bi）＞0，i=1，2，…，則對(duì)任一事件A，有：第七頁(yè)，共四十三頁(yè)，編輯于2023年，星期四必須掌握的概率論知識(shí)4)Bayes公式:設(shè)B1

,B2

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

Bj=0），且有B1

∪B2

∪…=Ω（樣本空間）；

p（Bi）＞0，i=1，2，…，則對(duì)任一事件A，有：第八頁(yè)，共四十三頁(yè)，編輯于2023年，星期四一個(gè)離散無(wú)記憶信源是由n個(gè)符號(hào)消息組成的集合:X={x1，x2

·

··xn

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

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

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

2．1信息量、熵和互信息量信息量定義：第九頁(yè)，共四十三頁(yè)，編輯于2023年，星期四2．1信息量、熵和互信息量信息量定義：美國(guó)科學(xué)家L.V.R.Hartley于1928年給出了信息的度量方法。定義若信源發(fā)出一符號(hào)xi，由于信道存在干擾，收到的不是xi而是yi，從yi中獲取有關(guān)xi的信息量用I(xi；yi)表示，稱為互信息量。

定義上述情況，若信道無(wú)干擾，收到的就是xi本身，這樣I(xi；yi)就可以用I(xi；xi)表示，或簡(jiǎn)單記作I(xi)，并稱為自信息量。第十頁(yè)，共四十三頁(yè)，編輯于2023年，星期四一、自信息量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)第十一頁(yè)，共四十三頁(yè)，編輯于2023年，星期四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)第十二頁(yè)，共四十三頁(yè)，編輯于2023年，星期四三種信息量單位之間的換算：

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)概率確定其信息量和不確定度。第十三頁(yè)，共四十三頁(yè)，編輯于2023年，星期四二、離散信源熵信源X發(fā)出某一個(gè)符號(hào)提供的信息量不適合描述信源X發(fā)出一個(gè)符號(hào)提供的信息量。定義信息源的平均不確定度為信源中各個(gè)符號(hào)不確定度的數(shù)學(xué)期望，記作H(X)

其中H(X)又稱為信源X的信源熵。

第十四頁(yè)，共四十三頁(yè)，編輯于2023年，星期四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/信源序列

第十五頁(yè)，共四十三頁(yè)，編輯于2023年，星期四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)第十六頁(yè)，共四十三頁(yè)，編輯于2023年，星期四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)

因

全概率公式第十七頁(yè)，共四十三頁(yè)，編輯于2023年，星期四5)條件熵與聯(lián)合熵

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

|yj)=－logp(xi

|

yj)集合X的條件熵為：

在給定Y（即各個(gè)yj）條件下，集合X的條件熵定義為：第十八頁(yè)，共四十三頁(yè)，編輯于2023年，星期四三、互信息（一）簡(jiǎn)單的通信模型

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

)＋H(Y|X)同理H(XY)=H(Y)＋H(X|Y)第十九頁(yè)，共四十三頁(yè)，編輯于2023年，星期四含義：平均從Y獲得的關(guān)于X的信息量。 （又稱信道 的信息傳輸率R）（二）平均互信息第二十頁(yè)，共四十三頁(yè)，編輯于2023年，星期四※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)]注意：（二）平均互信息第二十一頁(yè)，共四十三頁(yè)，編輯于2023年，星期四

※比較：I(x;y)可正可負(fù)，1．非負(fù)性I(X;Y)≥0（三）平均互信息的性質(zhì)第二十二頁(yè)，共四十三頁(yè)，編輯于2023年，星期四

※

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

通信的意義——通過(guò)消息的傳遞可獲得信息信源加密密鑰源信道解密信宿保密通信系統(tǒng)框圖XY’Y非法用戶全損信道（三）平均互信息的性質(zhì)第二十三頁(yè)，共四十三頁(yè)，編輯于2023年，星期四

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

※

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

極值性，P(x|y)=0or1（三）平均互信息的性質(zhì)第二十四頁(yè)，共四十三頁(yè)，編輯于2023年，星期四

I(X;Y)=I(Y;X)３．交互性（對(duì)稱性)（三）平均互信息的性質(zhì)第二十五頁(yè)，共四十三頁(yè)，編輯于2023年，星期四I(X;Y)=H(X)－H(X|Y)=H(Y)－H(Y|X)

4.

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

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

=H(X)+H(Y)－H(XY)信宿熵H(XY)（三）平均互信息的性質(zhì)第二十六頁(yè)，共四十三頁(yè)，編輯于2023年，星期四特殊信道特殊信道總結(jié)

信道名稱信道特征信息傳輸情況全損信道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ì)第二十七頁(yè)，共四十三頁(yè)，編輯于2023年，星期四

5．

凸?fàn)钚訧(X;Y)=f[P(x)，P(y|x)]（三）平均互信息的性質(zhì)第二十八頁(yè)，共四十三頁(yè)，編輯于2023年，星期四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ì)第二十九頁(yè)，共四十三頁(yè)，編輯于2023年，星期四

例1．

分析二元信源通過(guò)BSC信道的I(X;Y)特性信源：，信道：1－p1－ppp0011則（三）平均互信息的性質(zhì)第三十頁(yè)，共四十三頁(yè)，編輯于2023年，星期四其中，

（三）平均互信息的性質(zhì)第三十一頁(yè)，共四十三頁(yè)，編輯于2023年，星期四，得：（三）平均互信息的性質(zhì)第三十二頁(yè)，共四十三頁(yè)，編輯于2023年，星期四

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ì)第三十三頁(yè)，共四十三頁(yè)，編輯于2023年，星期四Ⅱ.

固定信源（ω一定）則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ì)第三十四頁(yè)，共四十三頁(yè)，編輯于2023年，星期四2．2信源編碼定理信源編碼的無(wú)失真編碼：接收端信宿要求無(wú)失真精確的復(fù)制信源輸出的消息。只有對(duì)離散信源才可以實(shí)現(xiàn)無(wú)失真編碼。實(shí)質(zhì)上是一種統(tǒng)計(jì)匹配編碼——根據(jù)信源的不同概率分布而選用與之相匹配的編碼，以達(dá)到在系統(tǒng)中傳送速率最小，且滿足在信宿復(fù)制時(shí)無(wú)失真或低于某一允許的失真限度值。第三十五頁(yè)，共四十三頁(yè)，編輯于2023年，星期四2．2．1信源編碼的基本概念信源編碼：將信源輸出符號(hào)，經(jīng)信源編碼器變換成另外的壓縮符號(hào)，然后將壓縮有信息經(jīng)信道傳送到信宿。只考慮信源和信宿兩個(gè)因素。通信系統(tǒng)模型簡(jiǎn)化為P15圖2-1編碼A器輸入為：編碼器輸出的碼字為：第三十六頁(yè)，共四十三頁(yè)，編輯于2023年，星期四符號(hào)碼1碼2碼3碼4等長(zhǎng)碼變長(zhǎng)碼u100001u201101101u3100000001u311011100012．2．1信源編碼的基本概念第三十七頁(yè)，共四十三頁(yè)，編輯于2023年，星期四樹(shù)圖（碼樹(shù)）法：樹(shù)根=碼字的起點(diǎn)樹(shù)的度=碼元數(shù)分支結(jié)點(diǎn)=碼的符號(hào)的一部分終端結(jié)點(diǎn)=待編碼符號(hào)滿樹(shù)=等長(zhǎng)碼：樹(shù)中各結(jié)點(diǎn)有相同樹(shù)枝數(shù)，且每層結(jié)點(diǎn)樹(shù)達(dá)到最大值。非滿樹(shù)=變長(zhǎng)碼2．2．1信源編碼的基本概念第三十八頁(yè)，共四十三頁(yè)，編輯于2023年，星期四編碼方法：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信源編碼的基本概念第三十九頁(yè)，共四十三頁(yè)，編輯于2023年，星期四譯碼方法：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信源編碼的基本概念第四十頁(yè)，共四十三頁(yè)，編輯于2023年，星期四分組碼（塊碼）分類

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

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