信息論與編碼總復(fù)習(xí)

信息論與編碼總復(fù)習(xí)知識點(diǎn)信息、消息和信號信息是事物運(yùn)動狀態(tài)或存在方式的不確定性的描述。信息是用以消除隨機(jī)不確定性的東西消息是指包含有信息的語言、文字和圖像等信號是消息的物理體現(xiàn)。在通信系統(tǒng)中，實(shí)際傳輸?shù)氖切盘?，但本質(zhì)的內(nèi)容是信息。信息包含在信號之中，信號是信息的載體。通信的結(jié)果是消除或部分消除不確定性，從而獲得信息。香農(nóng)信息的定義

信息論研究的內(nèi)容狹義信息論：主要研究信息的測度、信道容量以及信源和信道編碼理論等問題。一般信息論：主要也是研究信息傳輸和處理問題，除香農(nóng)信息論，還包括噪聲理論、信號濾波和預(yù)測、統(tǒng)計檢測和估計、調(diào)制理論、信息處理理論以及保密理論等。廣義信息論：不僅包括上述兩方面內(nèi)容，而且包括所有與信息有關(guān)的自然和社會領(lǐng)域，如模式識別、計算機(jī)翻譯、心理學(xué)、遺傳學(xué)、神經(jīng)生理學(xué)、語言學(xué)、語義學(xué)甚至包括社會學(xué)中有關(guān)信息的問題數(shù)字通信系統(tǒng)模型信道信源信源編碼加密信道編碼干擾源信宿信源解碼解密信道解碼加密密鑰解密密鑰概率論基礎(chǔ)無條件概率、條件概率、聯(lián)合概率的性質(zhì)和關(guān)系⑴⑵⑶概率論基礎(chǔ)無條件概率、條件概率、聯(lián)合概率的性質(zhì)和關(guān)系⑷⑸⑹

{信源離散信源:文字、數(shù)據(jù)、電報—隨機(jī)序列連續(xù)信源:話音、圖像—隨機(jī)過程

信源的分類按照信源發(fā)出的消息在時間上和幅度上的分布情況可將信源分成離散信源和連續(xù)信源兩大類連續(xù)信源指發(fā)出在時間和幅度上都是連續(xù)分布的連續(xù)消息（模擬消息）的信源，如語音、圖像、圖形等都是連續(xù)消息。

離散信源{離散無記憶信源離散有記憶信源{{發(fā)出單個符號的無記憶信源發(fā)出符號序列的無記憶信源發(fā)出符號序列的有記憶信源發(fā)出符號序列的馬爾可夫信源信源的分類離散信源指發(fā)出在時間和幅度上都是離散分布的離散消息的信源，如文字、數(shù)字、數(shù)據(jù)等符號都是離散消息。離散無記憶信源所發(fā)出的各個符號是相互獨(dú)立的，發(fā)出的符號序列中的各個符號之間沒有統(tǒng)計關(guān)聯(lián)性，各個符號的出現(xiàn)概率是它自身的先驗(yàn)概率。發(fā)出單個符號的信源指信源每次只發(fā)出一個符號代表一個消息；發(fā)出符號序列的信源指信源每次發(fā)出一組含二個以上符號的符號序列代表一個消息信源的描述設(shè)信源輸出的隨機(jī)序列為

X=(X1X2…Xl…XL)序列中的變量Xl∈{x1,x2,…

xn}這種由信源X輸出的L長隨機(jī)序列X所描述的信源稱為離散無記憶信源X的L次擴(kuò)展信源隨機(jī)序列的概率當(dāng)信源無記憶時

有記憶信源所發(fā)出的各個符號的概率是有關(guān)聯(lián)的。發(fā)出符號序列的有記憶信源發(fā)出符號序列的馬爾可夫信源馬爾可夫信源m階馬爾可夫信源：信源輸出某一符號的概率僅與以前的m個符號有關(guān)，而與更前面的符號無關(guān)。一階馬爾可夫信源：14馬爾可夫信源一類相對簡單的離散平穩(wěn)有記憶信源該信源在某一時刻發(fā)出字母的概率除與該字母有關(guān)外,只與此前發(fā)出的有限個字母有關(guān)m階馬爾可夫信源：信源輸出某一符號的概率僅與以前的m個符號有關(guān)，而與更前面的符號無關(guān)。條件概率馬爾科夫鏈的概念若把有限個字母記作一個狀態(tài)S，則信源發(fā)出某一字母的概率除與該字母有關(guān)外，只與該時刻信源所處的狀態(tài)有關(guān)。信源將來的狀態(tài)及其送出的字母將只與信源現(xiàn)在的狀態(tài)有關(guān)，而與信源過去的狀態(tài)無關(guān)。狀態(tài)的數(shù)目與階數(shù)的關(guān)系；描述馬爾科夫鏈的狀態(tài)轉(zhuǎn)移：——狀態(tài)轉(zhuǎn)移概率——符號條件概率——狀態(tài)轉(zhuǎn)移圖馬爾科夫信源達(dá)到穩(wěn)定狀態(tài)的條件；極限概率及其含義16馬氏鏈的基本概念令si

=(xi1,

xi2,

…xim)xi1,,xi2,

…xim

∈(a1,

a2,

…an)狀態(tài)集S={s1,s2,…,sQ}Q=nm信源輸出的隨機(jī)符號序列為：x1,x2,…xi-1,xi…信源所處的隨機(jī)狀態(tài)序列為：s1,s2,…si-1,si

…例：二元序列為…01011100…考慮m=2，Q=nm=22=4s1=00s2=01s3=10s4=11變換成對應(yīng)的狀態(tài)序列為

…s2s3s2s4s4s3s1…17馬爾可夫信源設(shè)信源在時刻m處于si狀態(tài),它在下一時刻(m+1)狀態(tài)轉(zhuǎn)移到sj的轉(zhuǎn)移概率為：

pij(m)=p{Sm+1=sj|Sm=si}=p{sj|si}pij(m)：基本轉(zhuǎn)移概率（一步轉(zhuǎn)移概率）若pij(m)與m的取值無關(guān),則稱為齊次馬爾可夫鏈

pij=p{Sm+1=sj|Sm=si}=p{S2=sj|S1=si}pij具有下列性質(zhì)：

pij≥018若信源處于某一狀態(tài)si,當(dāng)它發(fā)出一個符號后,所處狀態(tài)就變了,任何時候信源處于什么狀態(tài)完全由前一時刻的狀態(tài)和發(fā)出符號決定。系統(tǒng)在任一時刻可處于狀態(tài)空間S={s1,s2,…,sQ}中的任意一個狀態(tài),狀態(tài)轉(zhuǎn)移時,轉(zhuǎn)移概率矩陣符號條件概率矩陣區(qū)別19馬爾可夫信源狀態(tài)轉(zhuǎn)移圖齊次馬爾可夫鏈可以用其狀態(tài)轉(zhuǎn)移圖(香農(nóng)線圖)表示每個圓圈代表一種狀態(tài)

狀態(tài)之間的有向線代表某一狀態(tài)向另一狀態(tài)的轉(zhuǎn)移有向線一側(cè)的符號和數(shù)字分別代表發(fā)出的符號和條件概率sos11/0.60/0.30/0.4s21/0.20/0.81/0.720馬爾可夫信源遍歷狀態(tài)：非周期的、常返的狀態(tài),如圖中的狀態(tài)s2和s3閉集：狀態(tài)空間中的某一子集中的任何一狀態(tài)都不能到達(dá)子集以外的任何狀態(tài)不可約的：閉集中除自身全體外再沒有其他閉集特殊結(jié)論21馬爾可夫信源一個不可約的、非周期的、狀態(tài)有限的馬爾可夫鏈其k步轉(zhuǎn)移概率pij(k)在k→∞時趨于一個和初始狀態(tài)無關(guān)的極限概率Wj，它是滿足方程組的唯一解；Wj

：馬爾可夫鏈的一個平穩(wěn)分布，

Wj[或p(sj)]就是系統(tǒng)此時處于狀態(tài)sj的概率。無論隨機(jī)點(diǎn)從哪一個狀態(tài)si出發(fā)，當(dāng)轉(zhuǎn)移的步數(shù)k足夠大時，轉(zhuǎn)移到狀態(tài)sj的概率pij(k)都近似于一個常數(shù)Wj平均互信息互信息、平均互信息的定義方式；平均互信息的含義；平均互信息的數(shù)學(xué)性質(zhì)（包括與熵之間的關(guān)系及其含義）；數(shù)據(jù)處理定理（信息不增性原理）?；バ畔⒘慷x互信息量表示先驗(yàn)的不確定性減去尚存的不確定性，這就是收信者獲得的信息量；互信息量可能為正數(shù)、負(fù)數(shù)、零；對于無干擾信道，I(xi;yj)=I(xi)；對于全損信道，I(xi;yj)=0；xiyj信道p(xi):發(fā)送端發(fā)送

xi的概率（也叫先驗(yàn)概率）；P(xi|yj):

接收端收到

yj后，發(fā)送端發(fā)送

xi的概率（也叫后驗(yàn)概率）定義:平均互信息量定義：與其他熵的關(guān)系：

I(X;Y)=H(X)-H(X|Y)I(X;Y)=H(Y)-H(Y|X)I(X;Y)=H(X)+H(Y)-H(X,Y)表達(dá)平均互信息量的熵I(X;Y),是確定通過信道的信息量的多少，因此稱它為信道傳輸率或傳信率。平均互信息量另一種定義：離散隨機(jī)變量X和Y之間的平均互信息量根據(jù)概率之間的關(guān)系式有：I(X;Y)和I(Y;X)是隨機(jī)變量X和Y之間相互提供的信息量

——稱為互信息是完全確切的平均互信息量平均互信息I(X;Y)和I(Y;X)是對X和Y之間統(tǒng)計依存程度的信息量度：當(dāng)隨機(jī)變量X和Y之間有確定的關(guān)系時，X可以唯一確定Y，此時，H(Y|X)=0→I(X;Y)=H(Y)Y可以唯一確定X，此時，H(X|Y)=0→I(X;Y)=H(X)在通信系統(tǒng)中，若發(fā)端的符號是X，而收端的符號是Y，則互信息I(X;Y)就是在接收端收到Y(jié)后所能獲得的關(guān)于X的信息。若干擾很大，Y基本上與X無關(guān)，或者說X與Y相互獨(dú)立，那時就收不到任何關(guān)于X的信息，即I(X;Y)=0；若沒有干擾，Y是X的確知一一對應(yīng)函數(shù)，那時就能充分地收到X的信息，即I(X;Y)=H(X)∴互信息的范圍是：0≤I(X;Y)≤H(X)平均互信息量的性質(zhì)平均互信息量的基本性質(zhì)非負(fù)性：即I(X;Y)>=0極值性：即I(X;Y)<=H(X)對稱性：即I(X;Y)=I(Y;X)平均互信息量I(X;Y)是輸入信源X的概率分布p(xi)和信道轉(zhuǎn)移概率p(yj|xi)的函數(shù)，即I[p(xi)，p(yj|xi)]當(dāng)p(xi)一定時，I是關(guān)于p(yj|xi)的∪型下凸函數(shù)，存在極小值；當(dāng)p(yj|xi)一定時，I是關(guān)于p(xi)的∩型上凸函數(shù)，存在極大值；對于無損信道，有I(X;Y)=H(X)=H(Y)=H(X,Y)對于全損信道，有I(X;Y)=0已知級聯(lián)處理器在Y條件下，X與Z相互獨(dú)立，即I(X;Z|Y)=0;而且I(X:Y|Z)和I(Y:Z|X)均為非負(fù)量，故可得：I(X;Z)≤I(Y;Z),I(X;Z)≤I(X;Y)結(jié)論：當(dāng)消息通過多級處理器時，隨著處理器數(shù)目的增多，輸入消息與輸出消息之間的平均互信息量趨于變小。第一級處理器第二級處理器XYZ§2.2.5數(shù)據(jù)處理中信息的變化信息處理定理：數(shù)據(jù)處理過程中只會失掉一些信息，決不會創(chuàng)造出新的信息——信息不增性。信息處理定理說明：任何信息處理過程總會丟掉信息，最多保持原來的信息，一旦丟掉了信息，用任何處理手段也不可能再恢復(fù)丟失的信息。對于觀測采集到的數(shù)據(jù)做任何加工和處理，只會造成有用信息的損失，或不確定性的增加。因此，由計算機(jī)系統(tǒng)對輸入數(shù)據(jù)進(jìn)行處理，絕對不會增加信息量，要減少信息處理過程中信息的損失，就需要增加計算處理的工作量，或采用較為復(fù)雜的處理設(shè)備。§2.2.5數(shù)據(jù)處理中信息的變化一般通信系統(tǒng)的信息流程：根據(jù)信息不增性原理有：

I(U;V)≤I(X;V)，I(X;V)≤I(X;Y)從而有I(U;V)≤I(X;Y)編碼信道譯碼UXYV信源信宿§2.2.5數(shù)據(jù)處理中信息的變化§2.2.5數(shù)據(jù)處理中信息的變化數(shù)據(jù)處理定理得另一個應(yīng)用——多次測量如果想從測量結(jié)果Y中得到越來越多的關(guān)于X的信息量，必須付出代價。常用的方法是通過多次測量。

∵H(X|Y1,Y2)≤H(X|Y1)∴I(X|Y1,Y2)≥I(X|Y1)可證明取測量值Y的次數(shù)越多，X的條件熵越小，獲得的信息量就越大。尤其當(dāng)各次測量值相互獨(dú)立時，趨勢更明顯。取Y無數(shù)次后，H(X|Y1,Y2,Y3,…)→0自信息量

概率越大，不確定性越小；反之符號出現(xiàn)的概率越小，不確定性越大。定義方式；I

(xi)含義；消息xi的概率P(xi)對數(shù)的負(fù)值為該消息的自信息量，用I(xi)表示。自信息的單位的確定；單位由對數(shù)的底a決定——當(dāng)a=2時為比特(bit，binaryunit)*；a=e時為奈特(nat，natureunit)；a=10時為哈特(Hart，Hartley)。以比特(bit)為單位的自信息量可記為目前的通信系統(tǒng)多以二進(jìn)制為基礎(chǔ)，因此信息量的單位以bit最為常用。I(xi)的特性：⑴I(xi)是非負(fù)值⑵當(dāng)p(xi)=1時，I(xi)=0⑶當(dāng)p(xi)=0時，I(xi)=∞⑷I(xi)是先驗(yàn)概率p(xi)的單調(diào)遞減函數(shù)，即當(dāng)p(x1)＞p(x2)時，I(x1)＜I(x2)⑸兩個獨(dú)立事件的聯(lián)合信息量等于它們分別的信息量之和。即統(tǒng)計獨(dú)立信源的信息量等于它們分別的信息量之和。I(Xi|Yj)=I(Xi)+I(Yj)離散信源熵

信源各消息自信息量的數(shù)學(xué)期望為該信源的熵，也叫無條件熵，用H(X)表示。定義方式單位單位一般是比特/消息(bit/message)，對單符號信源，是比特/符號(bit/symbol)。H(X)反映信源每發(fā)出一條消息所提供的平均信息量，不反映信源發(fā)出某條特定消息的信息量H(X)表示信源的平均不確定性一般情況下，H(X)并不等于每接受一條消息所獲得的平均信息量。含義及與自信息的區(qū)別；條件熵和聯(lián)合熵的定義方式；聯(lián)合熵X1、X2可以是具有相同的概率空間的隨機(jī)變量條件熵X1、X2可以是具有相同的概率空間的隨機(jī)變量n=2,3,…LH(X1/X2):表示已知一個符號(X1發(fā)出)時,信源將要輸出下一個符號(X2發(fā)出)的平均不確定性.對于L維離散隨機(jī)序列X1X2…XL,當(dāng)已知前n-1個符號時,后面將要出現(xiàn)第下n個符號的平均不確定性就是條件熵:信源熵的數(shù)學(xué)性質(zhì)1、對稱性：H(P)的取值與分量p1,p2

,

···

,pq的順序無關(guān)。2、確定性：H(1,0)=H(1,0,0)=H(1,0,0…,0)=0只要信息源符號中，有一個符號出現(xiàn)的概率為1，信源熵就等于零。3、非負(fù)性：H(X)04、嚴(yán)格上凸性5、可加性

統(tǒng)計獨(dú)立信源X和Y的聯(lián)合信源的熵等于信源X和Y各自的熵之和。H(XY)=H(X)+H(Y)

6、條件熵小于無條件熵H(Y|X)≤H(Y)兩個條件下的條件熵小于一個條件下的條件熵，H(Z|X,Y)≤H(Z|Y)聯(lián)合熵小于信源熵之和，H(X,Y)≤H(X)+H(Y)7、香農(nóng)輔助定理

任一概率分布{p(ai)}，它對其它概率分布{p(bi)}的自信息取數(shù)學(xué)期望時，必大于{p(ai)}本身的熵8、最大熵定理（極值性）在離散信源情況下，信源各符號等概率分布時，熵值達(dá)到最大。性質(zhì)表明等概率分布信源的平均不確定性為最大。這是一個很重要的結(jié)論，稱為最大離散熵定理。9、擴(kuò)展性性質(zhì)說明：信源的取值數(shù)增多時，若這些取值對應(yīng)的概率很小(接近于零)，則信源的熵不變。所以，上式成立因?yàn)殡x散平穩(wěn)信源如果各維聯(lián)合概率分布均與時間起點(diǎn)無關(guān)，那么，信源是完全平穩(wěn)的。這種各維聯(lián)合概率分布均與時間起點(diǎn)無關(guān)的完全平穩(wěn)信源稱為離散平穩(wěn)信源。這時有：P(xi)=P(xj)P(xixi+1)=P(xjxj+1)……P(xixi+1…xi+N)=P(xjxj+1…xi+N)輸出序列的信源的序列熵；H(X)=H(X1X2…XL)=H(X1)+H(X2/X1)++H(X3/X1X2)…+H(XL/X1X2….XL-1)記作H（X）=H（XL）=平均符號熵N長的信源符號序列中平均每個信源符號所攜帶的信息量稱為平均符號熵.H（X）=1/LH（XL）若當(dāng)信源退化為無記憶時,有H(X)=若進(jìn)一步又滿足平穩(wěn)性時，則有H(X)=LH(X)平均符號熵與條件熵的四條性質(zhì)及其含義①條件熵是L的單調(diào)非遞增函數(shù)②當(dāng)L給定時,平均符號熵≥條件熵,即③平均符號熵HL(X)是L的單調(diào)非增函數(shù)④H∞(X)=HL(X)=H(XL/X1X2…XL-1)稱H∞為平穩(wěn)信源的極限熵或極限信息量。馬爾科夫信源熵的計算方法；計算熵Hm+1H∞(X)對狀態(tài)的全部可能性作統(tǒng)計平均,就可以得到馬爾可夫信源的平均符號熵是馬爾可夫鏈的平穩(wěn)分布表示處于某一狀態(tài)時發(fā)出一個消息符號的平均不確定性,即冗余度與效率的定義及其含義。冗余度（多余度、剩余度）表示給定信源在實(shí)際發(fā)出消息時所包含的多余信息。冗余度來自兩個方面:一是信源符號間的相關(guān)性，由于信源輸出符號間的依賴關(guān)系使得信源熵減小，這就是信源的相關(guān)性。相關(guān)程度越大(長)，信源的實(shí)際熵越小，趨于極限熵H

（X）；反之相關(guān)程度減小，信源實(shí)際熵就增大。另一個方面是信源符號分布的不均勻性，當(dāng)?shù)雀怕史植紩r信源熵最大。而實(shí)際應(yīng)用中大多是不均勻分布，使得實(shí)際熵減小。當(dāng)信源輸出符號間彼此不存在依賴關(guān)系且為等概率分布時，信源實(shí)際熵趨于最大

H0(X)=Hmax(X)。

信息效率（熵的相對率）

信源的實(shí)際信息熵與具有同樣符號集的最大熵的比值

表示不肯定的程度冗余度

表示肯定性的程度，因?yàn)榭隙ㄐ圆缓行畔⒘浚虼耸侨哂嗟?。信道信道的分類用戶?shù)量：單用戶、多用戶輸入端和輸出端關(guān)系：無反饋、有反饋信道參數(shù)與時間的關(guān)系：固定參數(shù)（光纖、電纜信道）、時變參數(shù)（無線信道）噪聲種類：隨機(jī)差錯（高斯白噪聲）、突發(fā)差錯（干擾的影響是前后相關(guān)的，錯誤成串出現(xiàn)，衰落信道、碼間干擾信道）輸入輸出特點(diǎn)：離散、連續(xù)、半離散半連續(xù)、波形信道按輸入/輸出信號在幅度和時間上的取值:離散信道：輸入和輸出的信號在時間和幅度上均是離散的連續(xù)信道：幅度是連續(xù)的時間是離散的半離散(半連續(xù))信道：輸入變量、輸出變量取值一個連續(xù)一個離散波形信道：信道的輸入和輸出在時間和幅度上均連續(xù)按輸入/輸出之間關(guān)系的記憶性來劃分：無記憶信道：信道的輸出只與信道該時刻的輸入有關(guān),而與其他時刻的輸入無關(guān)有記憶信道：信道的輸出不但與信道現(xiàn)時的輸入有關(guān)而且還與以前時刻的輸入有關(guān)按輸入／輸出信號之間的關(guān)系是否是確定關(guān)系:無干擾信道：輸入/輸出符號之間有確定的一一對應(yīng)關(guān)系有干擾信道：輸入/輸出之間關(guān)系是一種統(tǒng)計依存的關(guān)系輸入/輸出的統(tǒng)計關(guān)系：離散無記憶信道：用條件概率矩陣來描述。離散有記憶信道：可像有記憶信源中那樣引入狀態(tài)的概念。3.1信道分類和表示參數(shù)信道參數(shù)信道種類信道容量的定義；信息傳輸率信道在單位時間內(nèi)平均傳輸?shù)男畔⒘慷x為信息傳輸速率R=I(X;Y)=H(X)－H(X/Y)比特/符號Rt=I(X;Y)/t比特/秒信道容量比特/符號（bits/symbol或bits/channeluse）

無干擾離散信道的描述與特點(diǎn)：無噪無損信道有噪無損信道無噪有損信道無噪無損信道n=m：轉(zhuǎn)移概率為：

信道矩陣為單位陣：

無噪無損I(X;Y)=H(X)=H(Y)C=maxI(X；Y)=logn無噪有損信道(確定信道)n>m：無噪→噪聲熵H(Y|X)=0；有損→

疑義度H(X|Y)≠0

；

I(X;Y)=H(Y)≤H(X)

C=maxI(X；Y)=maxH(Y)有噪無損信道：n<m疑義度H(X|Y)=0噪聲熵H(Y|X)≠0H(X)≤H(Y)

；C=maxI(X；Y)=maxH(X)DMC信道對稱離散無記憶DMC信道特點(diǎn)及其信道容量信道矩陣中的每一行都是第一行的重排列（輸入對稱）；信道矩陣中的每一列都是第一列的重排列（輸出對稱）。準(zhǔn)對稱DMC信道特點(diǎn)及其信道容量；如果轉(zhuǎn)移概率矩陣P是輸入對稱而輸出不對稱，即轉(zhuǎn)移概率矩陣P的每一行都包含同樣的元素而各列的元素可以不同，則稱該信道是準(zhǔn)對稱DMC信道二元對稱信道BSC的信道容量：0101XYpp1-p1-p設(shè)輸入符號的概率分布為

p(0)=a,p(1)=1-a,條件概率

p(0|0)=p(1|1)=p,p(1|0)=p(0|1)=1-p,則有§3.2.2對稱DMC信道的信道容量從而可以計算出：又因?yàn)?/p>

但是僅發(fā)生在下，故BSC的信道容量為：當(dāng)p=1/2時，二元對稱信道的信道容量C=0，不管輸入概率分布如何都能達(dá)到信道容量。該信道輸入端不能傳遞任何信息到輸出端。這種信道是沒有任何實(shí)際意義的，但它從理論上說明了信道的最佳輸入分布不一定是惟一的。二進(jìn)制對稱信道容量C＝1－H（p）0.51.000.51.0cp§3.2.2對稱DMC信道的信道容量3.2離散單個符號信道及其容量串聯(lián)信道C(1,2)=maxI(X;Z)，C(1,2,3)=maxI(X;W)…3.8串聯(lián)信道及其信道容量若信道II的傳遞概率使其輸出只與輸入Y有關(guān)，與前面的輸入X無關(guān)，即滿足

稱這兩信道的輸入和輸出X，Y，Z序列構(gòu)成馬爾可夫鏈。

這兩個串聯(lián)信道可以等價成一個總的離散信道，其輸入為X，輸出為Z，取值，此信道的轉(zhuǎn)移概率為則總信道的傳遞矩陣若X，Y，Z滿足馬爾可夫鏈，得總信道的傳遞概率

信道矩陣為

對于串聯(lián)信道，若其輸入輸出變量之間組成一個馬爾可夫鏈，則存在下述定理。該定理對于串聯(lián)的單符號離散信道或是輸入、輸出都是隨機(jī)序列的一般信道都成立。兩個定理定理3.7當(dāng)且僅當(dāng)時等式成立。定理3.8若X、Y、Z組成一個馬爾可夫鏈，則有定理3.8表明通過數(shù)據(jù)處理后，一般只會增加信息的損失，最多保持原來獲得的信息，不可能比原來獲得的信息有所增加。也就是說，對接收到的數(shù)據(jù)Y進(jìn)行處理后，無論變量Z是Y的確定對應(yīng)關(guān)系還是概率關(guān)系，決不會減少關(guān)于X的不確定性。故定理3.8稱為數(shù)據(jù)處理定理。3.3離散序列信道及其容量

離散序列信道

信道

p(Y/X)

Y

X

X=(X1X2…XL)Xl

{a1,a2,…,an}Y=(Y1Y2…YL)Yl

{b1,b2,…,bm}3.3離散序列信道及其容量

離散無記憶序列信道

11111進(jìn)一步信道是平穩(wěn)的

3.3離散序列信道及其容量

離散無記憶序列信道

11111如果信道無記憶如果輸入矢量X中的各個分量相互獨(dú)立

當(dāng)信道平穩(wěn)時CL=LC1，一般情況下，I(X;Y)

LC1

限時限頻限功率的加性高斯白噪聲信道

高斯白噪聲加性信道單位時間的信道容量——香農(nóng)公式。高斯白噪聲加性信道單位時間的信道容量：

Ps是信號的平均功率；N0W為高斯白噪聲在帶寬W內(nèi)的平均功率（功率譜密度為N0/2）；信道的信噪比SNR=Ps/

N0W——著名且重要的Shannon香農(nóng)公式當(dāng)信道輸入信號是平均功率受限的高斯信號時，信道中的信息傳輸率可達(dá)到上式的信道容量。此為在噪聲信道中可靠通信，信息傳輸速率的上限值。由香農(nóng)公式可以得到一般非高斯波形信道的信道容量的下限值。4.1.1失真函數(shù)X={xi}，xi

{a1,…an}

信源編碼器

Y={yj}，yj

{b1,…bm}失真函數(shù)d(xi，yj)失真矩陣

單個符號的失真度的全體構(gòu)成的矩陣，稱為失真矩陣4.1.2

平均失真

失真函數(shù)的數(shù)學(xué)期望稱為平均失真，記為已知p(xi)和d(xi，yj)，平均失真只是符號轉(zhuǎn)移概率p(yj/xi)的函數(shù)。p(yj/xi

)在此實(shí)質(zhì)上代表編碼方式。信源編碼器

對于連續(xù)隨機(jī)變量同樣可以定義平均失真對于L長序列編碼情況，平均失真為

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

信源編碼器的目的是使編碼后所需的信息傳輸率R盡量小，R給定失真的限制值D，使

D，找最小R，

R(D)，定義為信息率失真函數(shù)。4.1.3信息率失真函數(shù)R(D)信源編碼器XY假想信道將信源編碼器看作信道，信源編碼器輸出的信息率R對應(yīng)到信道，即為接收端Y需要獲得的有關(guān)X的信息量，也就是互信息I(X;Y)。p(yj/xi)信源符號編碼概率信道轉(zhuǎn)移概率D允許試驗(yàn)信道

若p(xi)和d(xi，yj)已定，則可給出滿足條件的所有轉(zhuǎn)移概率分布pij，它們構(gòu)成了一個信道集合PD

稱為D允許試驗(yàn)信道。

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

當(dāng)p(xi)一定時，互信息I是關(guān)于p(yj/xi)的U型凸函數(shù)，存在極小值(2.2節(jié)）。在上述允許信道PD中，可以尋找一種信道pij，使給定的信源p(xi)經(jīng)過此信道傳輸后，互信息I(X；Y)達(dá)到最小。D=?p(yj/xi)=pij?R(D)=?I[p(xi)，p(yj/xi)]對于離散無記憶信源，R(D)函數(shù)可寫成

p(ai)，i＝1，2，…，n

是信源符號概率分布；

p(bj/ai)，i＝1，2，…，n，j＝1，2，…，m

是轉(zhuǎn)移概率分布；

p(bj)，j＝1，2，…，m是接收端收到符號概率分布。

R(D)的物理意義無失真時：R=H(X)有失真時：R=R(D)=H(X)－H(X/Y)H(X)H(X/Y)：由于壓縮編碼損失的信息對于給定信源，在平均失真不超過失真限度D的條件下，信息率容許壓縮的最小值R(D)信源編碼器H(X)R4.1.4信息率失真函數(shù)的性質(zhì)

R(D)函數(shù)的定義域⑴Dmin和R(Dmin)

Dmin＝0

對于連續(xù)信源

何時Dmin=0?只有當(dāng)失真矩陣中每行至少有一個零元素。何時R(0)=H(X)?只有當(dāng)失真矩陣中每行至少有一個零，并每一列最多只有一個零。否則R(0)可以小于H(X)，表示這時信源符號集中有些符號可以壓縮、合并而不帶來任何失真。

(2)Dmax和R(Dmax)

R(Dmax)=0選擇所有滿足R(D)＝0中D的最小值，定義為R(D)定義域的上限D(zhuǎn)max，即因此可以得到R(D)的定義域?yàn)镽(D)＝0就是I(X;Y)＝0，這時試驗(yàn)信道輸入與輸出是互相獨(dú)立的，所以條件概率p(yj/xi)與xi無關(guān)。即需滿足條件從上式觀察可得：在j=1，…，m中，可找到值最小的j，當(dāng)該j對應(yīng)的pj＝1，而其余pj為零時，上式右邊達(dá)到最小，這時上式可簡化成2、R(D)函數(shù)的下凸性和連續(xù)性

3、R(D)函數(shù)的單調(diào)遞減性容許的失真度越大，所要求的信息率越小。反之亦然。R(D)是非負(fù)的實(shí)數(shù)，即R(D)

0。其定義域?yàn)?～Dmax，其值為0～H(X)。當(dāng)D>Dmax時，R(D)

0。R(D)是關(guān)于D的下凸函數(shù)，因而也是關(guān)于D的連續(xù)函數(shù)。R(D)是關(guān)于D的嚴(yán)格遞減函數(shù)。容許的D越大，所要求的R越小。反之亦然。信道容量C率失真函數(shù)R(D)R(D)與C的比較研究對象信道信源給定條件信道轉(zhuǎn)移概率p(yj/xi)信源分布p(xi)選擇參數(shù)信源分布p(xi)信源編碼器編碼方法p(yj/xi)限制條件結(jié)論I(X;Y)=H(X)-H(X/Y)噪聲干擾消失的信息量H(X/Y)壓縮損失的信息量H(X/Y)編碼的定義編碼器輸入端為原始信源X=(X1X2…Xl…XL)，其符號集為A，即Xl∈{a1,a2,…ai,…an}信道所能傳輸?shù)姆柤疊={b1,b2,…bj,…bm}編碼器的功能是用符號集B中的元素，將原始信源的符號序列Xi變換為相應(yīng)的符號序列Yj

=(Y1Y2…Yj…YKL)編碼器L長序列KL長碼字編碼的定義二元信道是常用的一種信道，其基本符號集為{0,1}若將信源X通過一個二元信道傳輸，就必須把信源符號xi變換成由0,1符號組成的碼符號序列，即編碼。分組碼：每個符號序列Xi依照固定的碼表映射成一個符號序列Yj碼字：變換后的各個符號序列Yj碼長：碼字Yj的長度（符號數(shù)）KL碼元：組成碼字Yj的各位代碼符號bj碼：所有碼字的集合編碼：全部Xi←→Yj的映射關(guān)系定長碼和變長碼定長碼：所有碼字的長度都相同變長碼：可變長度碼，碼中的碼字長短不一奇異碼和非奇異碼奇異碼：一組碼中有相同的碼字。非奇異碼：信源符號和碼字一一對應(yīng)，所有碼字都不相同。唯一可譯碼任意有限長的碼元序列，只能被唯一地分割成一個個的碼字，便稱為唯一可譯碼。奇異碼不是唯一可譯碼，而非奇異碼中有非唯一可譯碼和唯一可譯碼。非即時碼和即時碼非即時碼：指接收端收到一個完整的碼字后，不能立即譯碼，還需等下一個碼字開始接收后才能判斷是否可以譯碼。即時碼：無須考慮后續(xù)的碼符號，即可從碼元序列中譯出碼字。唯一可譯碼成為即時碼的充分條件是：其中任何一個碼字都不是其他碼字的前綴。碼樹碼樹用來表示各碼字的構(gòu)成。A0100000000000011111111111樹根—碼字的起點(diǎn)分成r個樹枝—碼的進(jìn)制數(shù)中間節(jié)點(diǎn)—生出樹枝終端節(jié)點(diǎn)—碼字11010120000011111222220021碼樹中間節(jié)點(diǎn)不安排碼字，只在終端節(jié)點(diǎn)安排碼字每個終端節(jié)點(diǎn)對應(yīng)的碼字由從根節(jié)點(diǎn)出發(fā)到終端節(jié)點(diǎn)走過的路徑上所對應(yīng)的符號組成當(dāng)?shù)趇階的節(jié)點(diǎn)作為終端節(jié)點(diǎn)，且分配碼字，則碼字的碼長為i按樹圖法構(gòu)成的碼一定滿足即時碼的定義樹碼的各個分支都延伸到最后一級端點(diǎn)，則稱為滿樹，否則為非滿樹

滿樹碼是定長碼，非滿樹碼是變長碼碼樹克勞夫特不等式唯一可譯碼存在的充分和必要條件為：各碼字的長度Ki

應(yīng)滿足下式。m是進(jìn)制數(shù)，n是信源符號數(shù)注意：克拉夫特不等式只是說明唯一可譯碼是否存在，并不能作為唯一可譯碼的判據(jù)。綜上所述，可將碼作所示的分類：有mKL種可能的組合無失真信源編碼設(shè)信源符號序列的長度為L變換成由KL個符號組成的碼序列（碼字）有nL種序列組合有nL種信源消息有mKL種可能的碼字無失真信源編碼變換要求能夠無失真或無差錯地從Y恢復(fù)X，也就是能正確地進(jìn)行反變換或譯碼傳送Y時所需要的信息率最小信息率Yk有m種可能值，平均每個符號輸出的最大信息量為log2m，KL長碼字的最大信息量為KLlog2m。用該碼字表示L長的信源序列，送出一個信源符號所需要的信息率平均為Y所能編成的碼字的個數(shù)找到使最小的編碼方式定長編碼在定長編碼中，各碼字的碼長相等，即K為定值。編碼器輸入X=(X1X2…Xl…XL),

Xl∈{a1,…an},

輸入的消息總共有nL種可能的組合輸出的碼字Y=(Y1Y2…Yk…YK),

Yk∈{b1,…bm}

輸出的碼字總共有mK種可能的組合只要碼長K足夠長，即滿足:

則每個信源符號串都可以找到一一對應(yīng)的碼字定長編碼的目的：尋找最小K值定長編碼定理定長編碼定理：由L個符號組成的、每個符號的熵為HL(X)的無記憶平穩(wěn)信源符號序列X1X2…Xl…XL，可用KL個符號Y1,Y2,…,Yk,…YKL（每個符號有m種可能值）進(jìn)行定長編碼。對任意ε>0，δ>0，只要 則當(dāng)L足夠大時，必可使譯碼差錯小于δ；反之，當(dāng) 時，譯碼差錯一定是有限值，而當(dāng)L足夠大時，譯碼幾乎必定出錯。定長編碼定理當(dāng)編碼器容許的輸出信息率，即每個信源符號所需要的信息率為 時，只要，這種編碼器一定可以做到幾乎無失真，也就是收端的譯碼差錯概率接近于零，條件是所取的符號數(shù)L足夠大。定理的條件可以改寫為KL長碼字所能攜帶的最大信息L長信源序列攜帶的信息量定長編碼定理定理表明：只要碼字所能攜帶的信息量大于信源序列輸出的信息量，則可以使傳輸幾乎無失真，條件是L足夠大。反之，當(dāng)時，不可能構(gòu)成無失真的編碼，也就是不可能做一種編碼器，能使收端譯碼時差錯概率趨于零。時，則為臨界狀態(tài)，可能無失真，也可能有失真。變長編碼定理在變長編碼中，碼長K是變化的。我們可根據(jù)信源各個符號的統(tǒng)計特性，概率大的符號用短碼，概率小的用較長的碼，這樣在大量信源符號編成碼后平均每個信源符號所需的輸出符號數(shù)就可以降低，從而提高編碼效率。變長編碼定理單個符號變長編碼定理若一離散無記憶信源的符號熵為H(X)，每個信源符號用m進(jìn)制碼元進(jìn)行變長編碼，一定存在一種無失真編碼方法，其碼字平均長度滿足下列不等式變長編碼定理離散平穩(wěn)無記憶序列變長編碼定理對于平均符號熵為HL(X)的離散平穩(wěn)無記憶信源，必存在一種無失真編碼方法，使平均信息率滿足不等式其中，ε為任意小正數(shù)。平均編碼最佳碼（緊致碼）對于某個給定信源，在所有可能的唯一可譯碼中平均碼長最短的碼。最佳碼可能不止一個。平均碼長為了使平均碼長最短，將概率大的信息符號編以短的碼字，概率小的符號編以長的碼字。編碼效率編碼效率信源的平均符號熵HL(X)，采用平均符號信息率來編碼，所得的效率。最佳編碼效率為編碼定理從理論上給出了編碼效率接近1的理想編碼器的存在，即編碼效率的下界編碼效率總是小于1的，可以用它來衡量各種編碼方法的優(yōu)劣。碼的剩余度：衡量各種編碼方法與最佳碼的差距香農(nóng)編碼方法香農(nóng)第一定理指出了平均碼長與信源之間的關(guān)系，同時也指出了可以通過編碼使平均碼長達(dá)到極限值。香農(nóng)第一定理指出，選擇每個碼字的長度Ki滿足就可以得到這種碼。這種編碼方法稱為香農(nóng)編碼。香農(nóng)編碼步驟將信源消息符號按其概率從大到小排列確定滿足下列不等式的整數(shù)碼長Ki令P1=0，計算第i個消息的累加概率將累加概率Pi變換成二進(jìn)制數(shù)，取小數(shù)點(diǎn)后Ki位為該消息的碼字費(fèi)諾編碼方法費(fèi)諾編碼屬于概率匹配編碼，不是最佳的編碼方法。編碼過程如下：將信源消息符號按其出現(xiàn)的概率依次排列

p(x1)≥p(x2)≥…≥p(xn)按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接近或相等，并為每一組分配一位碼元。如編二進(jìn)制碼就分成兩組，編m進(jìn)制碼就分成m組。將每一分組再按同樣原則劃分，重復(fù)步驟2，直至概率不再可分為止。信源符號所對應(yīng)的碼字即為費(fèi)諾碼。費(fèi)諾碼比較適合于每次分組概率都很接近的信源哈夫曼編碼方法哈夫曼編碼的步驟將信源消息符號按其出現(xiàn)的概率大小依次排列

p(x1)≥p(x2)≥…≥p(xn)取兩個概率最小的符號分別配以0和1，并將這兩個概率相加作為一個新符號的概率，與未分配碼元的符號重新排隊。對重排后的兩個概率最小符號重復(fù)步驟2的過程。繼續(xù)上述過程，直到最后兩個符號配以0和1為止。從最后一級開始，向前返回得到各個信源符號所對應(yīng)的碼元序列，即相應(yīng)的碼字。哈夫曼編碼方法哈夫曼的編法并不惟一每次對信源縮減時，給兩個概率最小的符號分配“0”和“1”是任意的，所以可得到不同的碼字。不同的碼元分配，得到的具體碼字不同，但碼長Ki不變，平均碼長也不變，所以沒有本質(zhì)區(qū)別?？s減信源時，若合并后的新符號概率與其他符號概率相等，從編碼方法上來說，這幾個符號的次序可任意排列，由此編出的碼都是正確的，而得到的碼字卻不相同。不同的編碼方法得到的碼長Ki不盡相同。游程編碼游程符號序列中某符號連續(xù)重復(fù)出現(xiàn)而形成符號串的長度，又稱為游程長度或游長。游程編碼將這種符號序列映射成游程長度和對應(yīng)符號序列的位置的標(biāo)志序列。如果知道了游程長度和對應(yīng)符號序列的位置的標(biāo)志序列，就可以完全恢復(fù)出原來的符號序列。游程編碼二元序列的游程連續(xù)出現(xiàn)“0”，稱為“0”游程，表示為L(0)。連續(xù)出現(xiàn)“1”，稱為“1”游程，表示為L(1)。若規(guī)定二元序列總是從“0”開始，第一個游程是“0”游程，則第二個游程必為“1”游程，第三個又是“0”游程……對于隨機(jī)序列，游程長度是隨機(jī)的其取值可為1,2,3,…，直至無窮。用交替出現(xiàn)的“0”游程和“1”游程長度表示任意二元序列。一種一一對應(yīng)的變換，是可逆變換。游程編碼游程變換減弱了原序列符號間的相關(guān)性。游程變換將二元序列變換成了多元序列，這樣就適合于用其他方法，如哈夫曼編碼，進(jìn)一步壓縮信源，提高通信效率。首先測定“0”游程長度和“1”游程長度的概率分布，即以游程長度為元素，構(gòu)造一個新的信源。對新的信源(游程序列)進(jìn)行哈夫曼編碼。游程編碼多元序列游程多元序列也可以變換成游程序列，如m元序列可有m種游程。但是變換成游程序列時，需要增加標(biāo)志位才能區(qū)分游程序列中的“長度”是m種游程中的哪一個的長度，否則，變換就不可逆。增加的標(biāo)志位可能會抵消壓縮編碼得到的好處。所以，對多元序列進(jìn)行游程變換的意義不大。算術(shù)編碼算術(shù)編碼是近十多年來發(fā)展迅速的一種無失真信源編碼，它與最佳的哈夫曼碼相比，理論性能稍加遜色，而實(shí)際壓縮率和編碼效率卻往往還優(yōu)于哈夫曼碼，且實(shí)現(xiàn)簡單，故很受工程上的重視。算術(shù)編碼不同于哈夫曼碼，它屬于非分組碼。它從全序列出發(fā)，考慮符號之間的關(guān)系來進(jìn)行編碼。算術(shù)編碼利用了累積概率的概念。算術(shù)碼主要的