第二章無失真信源編碼

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

第5頁，課件共43頁，創(chuàng)作于2023年2月條件概率聯(lián)合概率必須掌握的概率論知識第6頁，課件共43頁，創(chuàng)作于2023年2月必須掌握的概率論知識全概率：設B1

,B2

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

Bj=0），且有B1

∪B2

∪…=Ω（樣本空間）；p（Bi）＞0，i=1，2，…，則對任一事件A，有：第7頁，課件共43頁，創(chuàng)作于2023年2月必須掌握的概率論知識4)Bayes公式:設B1

,B2

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

Bj=0），且有B1

∪B2

∪…=Ω（樣本空間）；

p（Bi）＞0，i=1，2，…，則對任一事件A，有：第8頁，課件共43頁，創(chuàng)作于2023年2月一個離散無記憶信源是由n個符號消息組成的集合:X={x1，x2

·

··xn

}，這n個符號消息的概率分布為了：稱為符號xi

的先驗概率,散信源數學模型表示為：

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

2．1信息量、熵和互信息量信息量定義：第9頁，課件共43頁，創(chuàng)作于2023年2月2．1信息量、熵和互信息量信息量定義：美國科學家L.V.R.Hartley于1928年給出了信息的度量方法。定義若信源發(fā)出一符號xi，由于信道存在干擾，收到的不是xi而是yi，從yi中獲取有關xi的信息量用I(xi；yi)表示，稱為互信息量。

定義上述情況，若信道無干擾，收到的就是xi本身，這樣I(xi；yi)就可以用I(xi；xi)表示，或簡單記作I(xi)，并稱為自信息量。第10頁，課件共43頁，創(chuàng)作于2023年2月一、自信息量1)函數I(xi)的屬性1o若有兩個事件xi，xj，其先驗概率為p(xi)＜p(xj)，則事件xi比事件xj有更大的不確定性，同時會帶來更多的信息量；I(xi)>I(xj)2o事件xi先驗概率p(xi)=1（確定事件）,則不存在不確定性，同時不會帶來信息量；I(xi)=0.3o事件xi先驗概率p(xi)=0（不可能事件）,則存在不確定性應為無窮大，同時會帶來無窮的信息量；I(xi)→∞.4o兩個統(tǒng)計獨立事件的聯(lián)合自信息量應等于它們各自信息量之和;則I(xy)=

I(x)＋I(y)第11頁，課件共43頁，創(chuàng)作于2023年2月2)

定義一個符號消息xi的自信息量為其發(fā)生概率的對數的負數，并記為I(xi)：I(xi)=－logp(xi)

當p(xi)=0，則I(xi)→∞；當p(xi)=1，則I(xi)=0.3)自信息量的單位自信息量的單位與所用對數的底有關：1o對數的底是2時，單位為比特—bit(binaryunit)2o對數的底是e(自然對數)時，單位為奈特—nat(natureunit)3o對數的底是10(常用對數)時，單位為笛特或哈特—det(decimalunit)orHart(Hartley)第12頁，課件共43頁，創(chuàng)作于2023年2月三種信息量單位之間的換算：

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

1bit=lg

2≈0.3010det1nat=log2e≈1.4427bit在信息論中常用以2為底的對數，為了書寫方便，以后將log2書寫為log，因其單位為比特bit，不會產生混淆；注意有些文獻將log2書寫為lb4)自信息量的含義是隨機量、根據單個符號消息的先驗概率確定其信息量和不確定度。第13頁，課件共43頁，創(chuàng)作于2023年2月二、離散信源熵信源X發(fā)出某一個符號提供的信息量不適合描述信源X發(fā)出一個符號提供的信息量。定義信息源的平均不確定度為信源中各個符號不確定度的數學期望，記作H(X)

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

第14頁，課件共43頁，創(chuàng)作于2023年2月2)H(X)的含義

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

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

3o是統(tǒng)計量、數學期望（統(tǒng)計平均）、各個符號平均不確定度和平均信息量。

3)信源熵單位：二進制:bit/信源符號，或bit/信源序列十進制:det/信源符號，或det/信源序列e進制:nat/信源符號，或nat/信源序列

第15頁，課件共43頁，創(chuàng)作于2023年2月4)信源熵的三種特殊情況1o當p(xi)=0時（p(xi)→0），則p(xi)logp(xi)=02o信源X={x1，x2

·

··xn

}，若其中xi

的概率p(xi)=1則其余xj的p(xj)=0，因為則H(X)=0bit/信源符號3o當信源中X所有n個符號均有相同的概率p(xi)=1/n，則H(X)=-(1/n)log(1/n)=lognbit/信源符號第16頁，課件共43頁，創(chuàng)作于2023年2月2o聯(lián)合熵（共熵）

聯(lián)合熵是聯(lián)合符號集合XY上的每個元素對xi

,

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

|yj)=－logp(xi

|

yj)，I(xi

yj)=－logp(xi

yj)

因

全概率公式第17頁，課件共43頁，創(chuàng)作于2023年2月5)條件熵與聯(lián)合熵

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

|yj)=－logp(xi

|

yj)集合X的條件熵為：

在給定Y（即各個yj）條件下，集合X的條件熵定義為：第18頁，課件共43頁，創(chuàng)作于2023年2月三、互信息（一）簡單的通信模型

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

)＋H(Y|X)同理H(XY)=H(Y)＋H(X|Y)第19頁，課件共43頁，創(chuàng)作于2023年2月含義：平均從Y獲得的關于X的信息量。 （又稱信道 的信息傳輸率R）（二）平均互信息第20頁，課件共43頁，創(chuàng)作于2023年2月※I(X;Y)與熵：※I(X;Y)與I(x;y)：

I(x;y)表示由隨機事件y中獲得的關于事件x的信息?；バ畔?關系：I(X;Y)＝EXY[I(x;y)]注意：（二）平均互信息第21頁，課件共43頁，創(chuàng)作于2023年2月

※比較：I(x;y)可正可負，1．非負性I(X;Y)≥0（三）平均互信息的性質第22頁，課件共43頁，創(chuàng)作于2023年2月

※

當I(X;Y)=0全損信道：H(X)=H(X|Y)，說明：

通信的意義——通過消息的傳遞可獲得信息信源加密密鑰源信道解密信宿保密通信系統(tǒng)框圖XY’Y非法用戶全損信道（三）平均互信息的性質第23頁，課件共43頁，創(chuàng)作于2023年2月

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

※

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

極值性，P(x|y)=0or1（三）平均互信息的性質第24頁，課件共43頁，創(chuàng)作于2023年2月

I(X;Y)=I(Y;X)３．交互性（對稱性)（三）平均互信息的性質第25頁，課件共43頁，創(chuàng)作于2023年2月I(X;Y)=H(X)－H(X|Y)=H(Y)－H(Y|X)

4.

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

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

=H(X)+H(Y)－H(XY)信宿熵H(XY)（三）平均互信息的性質第26頁，課件共43頁，創(chuàng)作于2023年2月特殊信道特殊信道總結

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

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

P(x︱y)=0or1H(X︱Y)=0I(X；Y)=H(X)（三）平均互信息的性質第27頁，課件共43頁，創(chuàng)作于2023年2月

5．

凸狀性I(X;Y)=f[P(x)，P(y|x)]（三）平均互信息的性質第28頁，課件共43頁，創(chuàng)作于2023年2月Th3.2：對于固定信源分布，平均互信息I(X;Y)是信道傳遞概率p(y|x)的∪型凸函數?！煌旁赐ㄟ^不同信道傳輸得到的平均互信息不同；

5．

凸狀性Th3.1：對于固定信道，平均互信息I(X;Y)是信源概率分布p(x)的∩型凸函數。平均互信息是信源符號概率分布的上凸函數平均互信息是信道轉移概率的下凹函數（三）平均互信息的性質第29頁，課件共43頁，創(chuàng)作于2023年2月

例1．

分析二元信源通過BSC信道的I(X;Y)特性信源：，信道：1－p1－ppp0011則（三）平均互信息的性質第30頁，課件共43頁，創(chuàng)作于2023年2月其中，

（三）平均互信息的性質第31頁，課件共43頁，創(chuàng)作于2023年2月，得：（三）平均互信息的性質第32頁，課件共43頁，創(chuàng)作于2023年2月

I.

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

（三）平均互信息的性質第33頁，課件共43頁，創(chuàng)作于2023年2月Ⅱ.

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

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

2°按信源符號與碼字對應關系分類非奇異碼：信源符號與碼字是一一對