信息論與編碼計算器1編輯ppt簡介

是一門應用概率論、隨機過程、數(shù)理統(tǒng)計和近代代數(shù)的方法，來研究信息傳輸、提取和處理中一般規(guī)律的學科。奠基人：美國數(shù)學家香農(nóng)〔C.E.Shannon〕1948年“通信的數(shù)學理論〞2編輯ppt簡介信息論的根本問題—信息的度量無失真信源編碼定理—香農(nóng)第一定理信道編碼定理—香農(nóng)第二定理信源編碼、信道編碼3編輯ppt緒論第1章4編輯ppt1.1信息的概念

5編輯ppt情報：是人們對于某個特定對象所見、所聞、所理解而產(chǎn)生的知識。知識：一種具有普遍和概括性質(zhì)的高層次的信息，以實踐為根底，通過抽象思維，對客觀事物規(guī)律性的概括。消息：用文字、符號、語音、圖像等能夠被人們感覺器官所感知的形式，把客觀物質(zhì)運動和主觀思維活動的狀態(tài)表達出來。幾個常見概念6編輯ppt香農(nóng)信息的度量〔1〕樣本空間某事物各種可能出現(xiàn)的不同狀態(tài)?！?〕概率測度對每一個可能選擇的消息指定一個概率?！?〕概率空間先驗概率p(xi)：選擇符號xi作為消息的概率。樣本空間概率測度7編輯ppt例：氣象預報

甲乙“甲地晴〞比“乙地晴〞的不確定性小。某一事物狀態(tài)出現(xiàn)的概率越小，其不確定性越大。某一事物狀態(tài)出現(xiàn)的概率接近于1,即預料中肯定會出現(xiàn)的事件，那它的不確定性就接近于零。8編輯ppt對xi的不確定性可表示為先驗概率p(xi)的倒數(shù)的某一函數(shù)?！?〕自信息〔5〕互信息先驗的不確定性減去尚存的不確定性。后驗概率p(ai|bj)：接收端收到消息bj后而發(fā)送端發(fā)的是ai的概率。9編輯ppt信息的特征信息是物質(zhì)存在的普遍屬性，信息和能量、物質(zhì)規(guī)定了事物的功能和性能；接收者在收到信息之前，對它的內(nèi)容是不知道的，所以，信息是新知識、新內(nèi)容；它使認識主體對某一事物的未知性或不確定性減少的有用知識；信息的存在具有普遍性、無限性、動態(tài)性、時效性和相對獨立性；信息可以產(chǎn)生，也可以消失，同時信息可以被傳遞、轉(zhuǎn)換、擴散、復制、貯存、分割，具有可共享性；信息是可以量度的，信息量有多少的差異。10編輯ppt1.2信息論研究的對象、目的和內(nèi)容11編輯ppt研究對象：通信系統(tǒng)模型信道信源信源編碼加密信道編碼干擾源信宿信源解碼解密信道解碼加密密鑰解密密鑰12編輯ppt信源：發(fā)送消息的源離散信源模擬信源信源是信息論的主要研究對象之一.我們不探討信源的內(nèi)部結(jié)構(gòu)和機理，而關(guān)注信源的輸出。重點討論其描述方法及性質(zhì)。信宿：信息歸宿之意，亦即收信者或用戶，是信息傳送的終點或目的地。信道：傳輸信息的物理媒介。信源、信道、信宿13編輯ppt信源編碼器通過信源編碼可以壓縮信源的冗余度,以提高通信系統(tǒng)傳輸消息的效率。

信源編碼器分為兩類無失真信源編碼：適用于離散信源或數(shù)字信號；

限失真信源編碼：用于連續(xù)信源或模擬信號,如語音、圖像等信號的數(shù)字處理。信源編碼器與譯碼器信源編碼器的主要指標是它的編碼效率。一般來說，效率越高，編譯碼器的代價也將越大。信源譯碼器把信道譯碼器的輸出變換成信宿所需的消息形式，相當于信源編碼器的逆過程。

14編輯ppt信道編碼器與譯碼器信道編碼主要作用是提高信息傳送的可靠性。信道編碼器的作用在信源編碼器輸出的代碼組上有目的地增加一些監(jiān)督碼元,使之具有檢錯或糾錯的能力。信道編碼的主要方法增大碼率或頻帶,即增大所需的信道容量。這恰與信源編碼相反。信道譯碼器的作用具有檢錯或糾錯的功能,它能將落在其檢錯或糾錯范圍內(nèi)的錯傳碼元檢出或糾正,以提高傳輸消息的可靠性。

15編輯ppt1.3信息論的形成和開展16編輯ppt信息論是在長期的通信工程實踐和理論研究的根底上開展起來的。簡史現(xiàn)代信息論是從20世紀20年代奈奎斯特和哈特萊的工作開始的：1924年奈奎斯特(Nyquist)的“影響電報速率因素確實定〞。1928年哈特萊(Hartley)的“信息傳輸〞一文研究了通信系統(tǒng)傳輸信息的能力，并給出了信息度量方法。信息論的形成17編輯ppt1946年柯切爾尼柯夫的學位論文“起伏噪聲下的潛在抗干擾理論〞，根據(jù)最小錯誤概率準那么和最小均方誤差準那么研究了離散和連續(xù)信道的最正確接收問題。1948年香農(nóng)的權(quán)威性長文“通信的數(shù)學理論〞，討論了信源和信道特性，1949年香農(nóng)“噪聲中的通信〞，兩論文奠定了現(xiàn)代信息論的理論根底。此后，在根本理論和實際應用方面，信息論都得到了巨大的開展。18編輯ppt第2章離散信源及其信息測度

2.1信源的數(shù)學模型及分類2.2離散信源的信息熵2.3信息熵的根本性質(zhì)2.5離散無記憶的擴展信源2.6離散平穩(wěn)信源2.7馬爾可夫信源2.8信源剩余度與自然語言的熵19編輯ppt信源產(chǎn)生消息或消息序列的源。消息攜帶信息，是信息的具體形式。描述方法通信過程中，信源發(fā)出何種消息是不確定的、是隨機的。因此，信源可用隨機變量、隨機矢量或隨機過程〔或樣本空間及其概率測度〕來描述。不同的信源根據(jù)其輸出消息的不同的隨機性質(zhì)進行分類。2.1信源的數(shù)學模型及分類20編輯ppt1、隨機變量描述的信源〔單符號〕特點：輸出單符號消息。符號集的取值A:{a1,a2,…,aq}是有限的或可數(shù)的,可用離散型隨機變量X描述。數(shù)學模型：設每個信源符號ai出現(xiàn)的(先驗)概率p(ai)(i=1,2,…,q)滿足：概率空間能表征離散信源的統(tǒng)計特性，因此也稱概率空間為信源空間。1〕離散信源21編輯ppt1〕平穩(wěn)信源特點:

信源輸出的消息由一符號序列所組成。

可用N維隨機矢量

X＝(X1,X2,…,XN)描述，且隨機矢量X的各維概率分布都與時間起點無關(guān)。離散平穩(wěn)信源：每個隨機變量Xi(i＝1,2,…,N)是取值離散的隨機變量。連續(xù)平穩(wěn)信源：每個隨機變量Xi(i＝1,2,…,N)是取值連續(xù)的隨機變量。2、隨機矢量描述的信源22編輯ppt2〕離散無記憶平穩(wěn)信源離散平穩(wěn)信源的特例，信源發(fā)出的符號都相互統(tǒng)計獨立，即各隨機變量Xi(i＝1,2,…,N)之間統(tǒng)計獨立。性質(zhì)：獨立－>P(X)=P(X1,X2,…,XN)=P1(X1)·P2(X2)···PN(XN)平穩(wěn)－>P1(Xi)=P2(Xi)=···=PN(Xi)=P(Xi)〔下標1-N為時間標志〕N維隨機矢量的一個取值，

i＝(ai1ai2…aiN)P(aik)是符號集A的一維概率分布假設各隨機變量Xi取值同樣符號集A:{a1,a2,…,aq}，那么23編輯ppt信源X的各輸出Xi間統(tǒng)計獨立、且取值同一符號集A。該信源輸出的N維隨機矢量X為離散無記憶信源X的N次擴展信源。此擴展信源取值為符號集

i＝(ai1ai2…aiN),其中(i1,i2,…,iN=1,2

,

…,q)，其數(shù)學模型是X信源空間的N重空間：3〕離散無記憶信源的N次擴展信源假設X為離散無記憶信源：24編輯ppt4〕有記憶信源

信源在不同時刻發(fā)出的符號之間是相互依賴的，即信源輸出的隨機序列X中，各隨機變量Xi之間相互依賴。須使用隨機矢量的聯(lián)合概率分布和條件概率分布來說明它們之間的關(guān)聯(lián)關(guān)系。例：漢字組成的中文序列中，只有根據(jù)中文的語法、習慣用語、修辭制約和表達實際意義的制約所構(gòu)成的中文序列才是有意義的中文句子或文章。所以，在漢字序列中前后文字的出現(xiàn)是有依賴的，是彼此相關(guān)的。25編輯ppt5〕m階馬爾可夫信源〔非平穩(wěn)信源〕不同時刻發(fā)出的符號間的依賴關(guān)系記憶信源的記憶長度為m+1時，稱這種有記憶信源為m階馬爾可夫信源。假設上述條件概率與時間起點i無關(guān)，信源輸出的符號序列可看成為時齊馬爾可夫鏈，那么此信源稱為時齊馬爾可夫信源。26編輯ppt2.2離散信源的信息熵

根本的離散信源：輸出單符號消息，且這些消息間兩兩互不相容。用一維隨機變量X來描述信源的輸出，其數(shù)學模型可抽象為:問題：這樣的信源能輸出多少信息?

每個消息的出現(xiàn)攜帶多少信息量?27編輯ppt信息的度量要點：信息的度量〔信息量〕和不確定性消除的程度有關(guān)，消除的不確定性＝獲得的信息量；不確定性就是隨機性，可以用概率論和隨機過程來測度；推論：概率小－>信息量大，即信息量是概率的單調(diào)遞減函數(shù)；信息量應該具有可加性；信息量的計算公式為〔香農(nóng)〔自〕信息量的度量〕：28編輯ppt2.1.1自信息

設離散信源X的概率空間為：I(ai)代表兩種含義：〔1〕當事件ai發(fā)生以前，表示事件ai發(fā)生的不確定性〔2〕當事件ai發(fā)生以后，表示事件ai所提供的信息量自信息量：事件ai發(fā)生所含有的信息量29編輯ppt度量單位計算自信息量時要注意有關(guān)事件發(fā)生概率的計算；自信息量的單位取決于對數(shù)的底；底為2，單位為“比特〔bit,binaryunit〕〞；底為e，單位為“奈特〔nat,natureunit〕〞；底為10，單位為“哈特〔hat,Hartley〕〞；根據(jù)換底公式得：一般計算都采用以“2〞為底的對數(shù)，為了書寫簡潔，常把底數(shù)“2〞略去不寫1nat=1.44bit,1hat=3.32bit；30編輯ppt收信者收到某消息獲得的信息量＝不確定性減少的量＝(收到此消息前關(guān)于某事件的不確定性)-(收到此消息后關(guān)于某事件的不確定性)通信的實質(zhì)？

即：傳遞信息，消除不確定性。

31編輯ppt2.2.2信息熵對一個信源發(fā)出不同消息所含有的信息量也不同。所以自信息I(ai)是一個隨機變量，不能用它來作為整個信源的信息測度。信息熵：自信息的數(shù)學期望，平均自信息量Hr(X)：r進制單位/符號32編輯ppt熵的含義熵是從整個集合的統(tǒng)計特性來考慮的，它從平均意義上來表征信源的總體特征。信源輸出前，熵H(X)表示信源的平均不確定性；信源輸出后，熵H(X)表示每個消息的平均信息量；信息熵H(X)表征了變量X的隨機性。33編輯ppt

信息熵是信源概率空間的一種特殊函數(shù)。這個函數(shù)的取值大小，與信源的符號數(shù)及其概率分布有關(guān)。

用概率矢量P來表示概率分布P(x)：3.3信息熵的根本性質(zhì)那么信息熵H(X)是概率矢量P或它的分量p1，p2，…，pq的q-1元函數(shù)(獨立變量只有q-1元)。那么H(X)可寫成：34編輯ppt熵函數(shù)的向量形式H(P)是概率矢量P的函數(shù)，稱為熵函數(shù)。我們用下述表示方法：用H(x)表示以離散隨機變量x描述的信源的信息熵；用H(P)或H(p1,p2,…,pq)表示概率矢量為 P=(p1,p2,…,pq)的q個符號信源的信息熵。假設當q=2時，因為p1+p2=1,所以將兩個符號的熵函數(shù)寫成H(p1)或H(p2)。熵函數(shù)H(P)是一種特殊函數(shù)，具有以下性質(zhì)。35編輯ppt熵函數(shù)性質(zhì)1、對稱性：

H(P)的取值與分量p1,p2,···,pq的順序無關(guān)。說明：

H(P)=

pi·

logpi中的和式滿足交換率；熵只與隨機變量的總體統(tǒng)計特性有關(guān)。例子：36編輯ppt2、確定性：H(1,0)=H(1,0,0)=H(1,0,0…,0)=0說明：從總體來看，信源雖然有不同的輸出符號，但它只有一個符號幾乎必然出現(xiàn)，而其它符號那么是幾乎不可能出現(xiàn)，那么，這個信源是一個確知信源，其熵為零。分析：假設Pi=1,PilogPi=0；其他Pj趨于0，PjlogPj趨于0。由羅比塔法那么：因此37編輯ppt3、非負性：H(P)0說明：隨機變量X的概率分布滿足0＜pi＜1，對數(shù)函數(shù)的底大于1時，log(pi)＜0，-pilog(pi)＞0，即得的熵為正值。只有當隨機變量是一確知量時熵才等于零。這種非負性適宜于離散信源的熵，對連續(xù)信源來說這一性質(zhì)并不存在〔基于差熵、相對熵概念〕。非負性表達信息是非負的。38編輯ppt4、擴展性說明：信源的符號數(shù)增多時，假設這些取值對應的概率很小(接近于零)，那么信源的熵不變。所以，上式成立。因為趨于039編輯ppt5、可加性

統(tǒng)計獨立信源X和Y的聯(lián)合信源XY的熵等于信源X和Y各自的熵之和：

H(XY)=H(X)+H(Y)

即：另外：可加性是熵函數(shù)的一個重要特性，正因具有可加性，才能保證熵函數(shù)的形式是唯一的。信源XY的符號聯(lián)合概率40編輯ppt證明：=1=141編輯ppt例如，甲信源為它們的聯(lián)合信源是可計算得聯(lián)合信源的聯(lián)合熵：H(Z)=H(XY)=log(nm)=logm+logn=H(X)+H(Y)乙信源為42編輯ppt6、強可加性兩個互相關(guān)聯(lián)的信源X和Y的聯(lián)合信源XY的熵等于信源X的熵加上在X條件下信源Y的條件熵。H〔XY〕=H〔X〕+H〔Y|X〕證明：

設X、Y的概率分布為X、Y之間存在關(guān)聯(lián)，用條件概率描述：

同時，聯(lián)合信源XY的各個符號，由X、Y信源中的符號構(gòu)成，每個聯(lián)合符號的聯(lián)合概率為：43編輯ppt顯然那么聯(lián)合概率44編輯ppt=1條件熵條件熵45編輯ppt條件熵：H〔Y|X〕表示信源X輸出一符號的條件下，信源Y再輸出一符號所能提供的平均信息量。也即：由前面的推導，可得：46編輯ppt7、遞增性假設原信源X中有一個符號分割成了m個元素(符號)，這m個元素的概率之和等于原元素的概率，而其他符號的概率不變，那么新信源的熵增加。熵的增加量等于由分割而產(chǎn)生的不確定性量。47編輯ppt#〔選講〕#證明:可以從熵的定義或強可加性得出：48編輯ppt因為而當i≠n時pij=0，所以即得：49編輯ppt遞增性的推廣它表示n個元素的信源熵可以遞推成(n-1)個二元信源的熵函數(shù)的加權(quán)和。這樣，可使多元信源的熵函數(shù)的計算簡化成計算假設干個二元信源的熵函數(shù)。因此，熵函數(shù)的遞增性又可稱為遞推性。50編輯ppt#〔選講〕#[例]：運用熵函數(shù)的遞增性〔的推廣〕，計算熵函數(shù)H(1/3，1/3，1/6，1/6)的數(shù)值。51編輯ppt8、極值性在離散信源情況下，信源各符號等概率分布時，熵值到達最大。

等概率分布信源的平均不確定性為最大。這是一個重要結(jié)論，稱為最大離散熵定理。證明：因為對數(shù)函數(shù)是∩型凸函數(shù)，滿足詹森不等式E[logY]logE[Y]，令矢量Y=1/P即〔yi=1/pi〕，那么有：=152編輯ppt特例：二進制離散信源。

該信源符號只有二個，設為“0〞和“1〞。符號輸出的概率分別為“〞和“1-〞，即信源的概率空間為：H(X)=-log–(1-)log(1-)=H()

即信息熵H(x)是

的函數(shù)。

取值于[0，1]區(qū)間，可畫出熵函數(shù)H(

)的曲線來，如右圖所示。53編輯ppt熵函數(shù)H(P)是概率矢量P＝(p1，p2，…，pq)的嚴格∩型凸函數(shù)(或稱上凸函數(shù))?！惨驗镠(P)是由具有嚴格上凸性的對數(shù)函數(shù)-xlogx〔二階導數(shù)≤0〕的線性組合。〕即：對任意概率矢量P1＝(p1,p2,…,pq)和P2＝(p’1,p’2,…,p’q)，和任意的0＜＜1，有：H[P1+(1-)P2]＞H(P1)+(1-)H(P2)因為熵函數(shù)具有上凸性，所以熵函數(shù)具有極值，其最大值存在。9、上凸性54編輯ppt擴展信源的由來：當離散無記憶信源信源發(fā)出固定長度的消息序列時，那么得到原信源的擴展信源。例如：在電報系統(tǒng)中，假設信源輸出的是二個符號組成的符號序列，此時可認為是一個新的信源，它由四個符號〔00，01，10，11〕組成，我們把該信源稱為二元無記憶信源的二次擴展信源。更進一步，如果把N個二元符號組成一組，那么信源等效成一個具有2N個符號的新信源，把它稱為二元無記信源的N次擴展信源。2.4離散無記憶的擴展信源55編輯ppt概念：一般地，對一個離散無記憶信源X，其樣本空間為{a1,a2,…,aq}，對它的輸出消息序列，可用一組組長度為N的序列來表示它。這時，它等效成一個新信源。新信源輸出的符號是N維離散隨機矢量X=(X1，X2,……,XN)，其中每個分量Xi(i＝1,2,…,N)都是隨機變量，它們都取值于同一信源符號集，并且分量之間統(tǒng)計獨立，那么由隨機矢量X組成的新信源稱為離散無記憶信源X的N次擴展信源。56編輯ppt單符號離散無記憶信源X的數(shù)學模型：N次擴展信源與單符號離散信源比較，其輸出不是單個符號，而是一串N個相互獨立的符號序列： X＝(X1,X2,…,XN)，聯(lián)合分布密度P(X)=P(X1X2…XN)它們把X等效為一個新信源-----X的N次擴展信源。N次擴展N次擴展信源N次擴展信源的數(shù)學模型57編輯pptN次擴展信源數(shù)學模型表示為：因為是無記憶的(彼此統(tǒng)計獨立)那么：58編輯ppt性質(zhì)：離散平穩(wěn)無記憶N次擴展信源的熵

H(XN)=N·H(X)其中：同理計算式中其余各項，得到：

H(XN)=H(X)+H(X)+……+H(X)=NH(X)

證明：分解為N重求和59編輯ppt一、概念在一般情況下，信源在t=i

時刻將要發(fā)出什么樣的符號決定于兩方面：

(1)信源在t=i

時刻，隨機變量Xi

取值的概率分布P(xi)。

[一般P(xi)

P(xj)](2)t=i時刻以前信源發(fā)出的符號。

[即與條件概率P(xi|xi-1xi-2…)有關(guān)]平穩(wěn)隨機序列：其統(tǒng)計性質(zhì)與時間的推移無關(guān)，即信源發(fā)出符號序列的概率分布與時間起點無關(guān)。

2.5離散平穩(wěn)信源

60編輯ppt一維平穩(wěn)信源：假設當t=i，t=j時(i,j是大于1的任意整數(shù))，信源輸出的隨機序列滿足一維概率分布時間起點無關(guān)條件 P(xi)=P(xj)=P(x)二維平穩(wěn)信源：除滿足上述一維平穩(wěn)信源條件外，如果聯(lián)合概率分布P(xixi+1)也與時間起點無關(guān)，即P(xixi+1)=P(xjxj+1)(i,j為任意整數(shù)且ij)它表示任何時刻，信源先后發(fā)出二個符號的聯(lián)合概率分布也完全相等。61編輯ppt完全平穩(wěn)信源：如果各維聯(lián)合概率分布均與時間起點無關(guān)，那么信源是完全平穩(wěn)的〔N為任意正整數(shù)〕。由于聯(lián)合概率與條件概率有以下關(guān)系：62編輯ppt平穩(wěn)信源的特點：對于平穩(wěn)信源發(fā)出的隨機序列，其前后符號依賴的條件概率均與時間起點無關(guān)，只與關(guān)聯(lián)長度N有關(guān)。如果某時刻發(fā)出什么符號只與前面發(fā)出的N個符號有關(guān)，那么由平穩(wěn)性，那么任何時刻它們的依賴關(guān)系都是一樣的。那么由前面兩個關(guān)系，可推知各維條件概率也滿足時間起點無關(guān)性：63編輯ppt三、離散平穩(wěn)信源的極限熵對于一般平穩(wěn)有記憶信源，設其概率空間為：發(fā)出的符號序列為(X1，X2，…，XN，…)，假設信源符號之間的依賴長度為N，且各維概率分布為：簡記為64編輯ppt且滿足完備集條件，各維概率密度之和皆為1：65編輯ppt聯(lián)合概率分布，可得離散平穩(wěn)信源的一系列聯(lián)合熵：N長的信源符號序列中平均每符號攜帶的信息量為：平均符號熵:信息度量1——平均符號熵66編輯ppt另一方面，因信源符號之間的依賴關(guān)系長度為N,所以可以求出前面N-1個符號時，后面出現(xiàn)一個符號的平均不確定性。條件熵:假設前面N一1個符號，后面出現(xiàn)一個符號的平均不確定性〔平均信息量〕，即得一系列的條件熵：信息度量2——條件熵67編輯ppt對離散平穩(wěn)信源，假設H1(X)＜，那么有：1)條件熵、平均符號熵都隨序列長度N的增加是非遞增的；2)對于任意序列長度N，平均符號熵不小于條件熵；3)極限熵H存在，并且等于序列長度N無窮大時的平均符號熵或條件熵。對于一般平穩(wěn)信源，求H相當困難〔N取無窮大〕。但N不很大時有：HHN(X)或HH(XN|X1X2…XN-1)。離散平穩(wěn)信源性質(zhì)總結(jié)近似計算68編輯ppt對離散二維平穩(wěn)信源，一維和二維概率分布確定，且與時間推移無關(guān)。對于這樣的二維平穩(wěn)信源，二符號之間的條件概率反映了前面輸出某一個符號、后面再輸出某一個符號的概率，其輸出符號序列中依賴關(guān)系是有限的，所以有：特例分析：離散二維平穩(wěn)信源69編輯ppt聯(lián)合概率滿足完備性邊緣分布概率另外，可從聯(lián)合概率得到邊緣分布概率：那么條件熵表示為：70編輯ppt此時：可見：離散二維平穩(wěn)信源的極限熵，等于條件熵H(X2|X1)

。N-2維邊緣概率71編輯ppt推廣：一般情況，如果平穩(wěn)信源的記憶長度有限，也即某時刻輸出什么符號只與前面的m個符號有關(guān)。此時，那么可用有限記憶長度的條件熵來測度離散平穩(wěn)信源的極限熵：72編輯ppt第3章離散信道及其信道容量第一節(jié)信道的數(shù)學模型及分類第二節(jié)平均互信息第三節(jié)平均互信息的特性第四節(jié)信道容量及其計算方法第五節(jié)離散無記憶擴展信道及其信道容量第六節(jié)信源與信道的匹配73編輯ppt信道的任務：以信號方式傳輸信息和存儲信息。研究內(nèi)容：信道中能夠傳送或存儲的最大信息量，即信道容量。74編輯ppt3.1信道的數(shù)學模型和分類數(shù)字通信系統(tǒng)的一般模型75編輯ppt二、離散信道的數(shù)學模型條件概率P(y|x)描述了輸入信號和輸出信號之間統(tǒng)計依賴關(guān)系，反映了信道的統(tǒng)計特性。根據(jù)信道的統(tǒng)計特性的不同，離散信道又可分成3種情況：1.無干擾信道2.有干擾無記憶信道3.有干擾有記憶信道76編輯ppt

(1)無干擾(無噪聲)信道

信道中沒有隨機性的干擾或者干擾很小，輸出符號y與輸入符號x之間有確定的、一一對應的關(guān)系。即：y＝f(x)77編輯ppt(2)有干擾無記憶信道信道輸入和輸出之間的條件概率是一般的概率分布。如果任一時刻輸出符號只統(tǒng)計依賴于對應時刻的輸入符號，那么這種信道稱為無記憶信道。78編輯ppt

(3)有干擾(噪聲)有記憶信道

實際信道往往是既有干擾(噪聲)又有記憶的這種類型。例如在數(shù)字信道中，由于信道濾波頻率特性不理想時造成了碼字間串擾。在這一類信道中某一瞬間的輸出符號不但與對應時刻的輸入符號有關(guān)，而且還與此以前其他時刻信道的輸入符號及輸出符號有關(guān)，這樣的信道稱為有記憶信道。79編輯ppt三、單符號離散信道單符號離散信道特性：輸入符號為X，取值于{a1,a2,…,ar}輸出符號為Y，取值于{b1,b2,…,bs}條件概率：P(y|x)＝P(y=bj|x=ai)＝P(bj|ai)

這一組條件概率稱為信道的傳遞概率或轉(zhuǎn)移概率。

信道中有干擾(噪聲)存在，可以用傳遞概率P(bj|ai)來描述干擾影響的大小。80編輯ppt一般簡單的單符號離散信道可用

X,P(y|x),Y三者加以表述，其數(shù)學模型可以用如下概率空間

[X,P(y|x),Y]也可用圖形來描述：

a1b1

a2b2X .

.Y..arbsP(bj/ai)單符號離散信道81編輯ppt信道矩陣〔轉(zhuǎn)移矩陣〕模型一般離散單符號信道的傳遞概率可用矩陣形式表示，即

矩陣P完全描述了信道的特性，可用它作為離散單符號信道的另一種數(shù)學模型的形式。矩陣P中元素有些是信道干擾引起的錯誤概率，有些是信道正確傳輸?shù)母怕省?/p>

b1b2…bsa1P(b1|a1)P(b2|a1)…P(bs|a1)a2P(b1|a2)P(b2|a2)…P(bs|a2)…….……arP(b1|ar)P(b2|ar)…P(bs|ar)82編輯ppt[例]

二元對稱信道，[BSC，BinarySymmetricalChannel]解：此時，X:{0,1};Y:{0,1};r=s=2，a1=b1=0；a2=b2=1。傳遞概率:p是單個符號傳輸發(fā)生錯誤的概率?！?-p〕表示是無錯誤傳輸?shù)母怕?。轉(zhuǎn)移矩陣:

01011－p

a1=00=b11－p

a2=11=b2pp83編輯ppt〔1〕聯(lián)合概率其中前向概率，描述信道的噪聲特性后向概率〔后驗概率〕輸入符號的先驗概率單符號離散信道的相關(guān)概率關(guān)系〔2〕輸出某符號的概率84編輯ppt含義：輸出端收到的某符號，必是輸入端某一符號輸入所致?！?〕后驗概率且根據(jù)貝葉斯定理，可知：85編輯ppt3.2信道疑義度與平均互信息研究離散單符號信道的信息傳輸問題。一、信道疑義度先驗熵：即信道輸入信源X的熵

H(X)是在接收到輸出Y以前，關(guān)于輸入變量X的先驗不確定性。

86編輯ppt后驗熵：

接收到bj后，關(guān)于輸入變量X的不確定性。

后驗熵是當信道接收端接收到輸出符號bj后，關(guān)于輸入符號的不確定性的信息測度。87編輯ppt信道疑義度：后驗熵在輸出符號集Y范圍內(nèi)是隨機量。對后驗熵在符號集Y中求數(shù)學期望，即--信道疑義度：88編輯ppt互信息量

I(x

;y)：

收到消息y后獲得關(guān)于x的信息量，即消除的不確定性量?；バ畔⒘勘硎鞠闰灥牟淮_定性減去尚存的不確定性，是收信者獲得的信息量。假設互信息I(x;y)<0，說明在收到信息量y以前對消息x是否出現(xiàn)的不確定性較??；但由于信道噪聲的存在，反而使得接收到消息y后，反而對x是否出現(xiàn)的不確定程度增加了。二、平均互信息89編輯ppt平均互信息I(X;Y)：接收到符號Y后,平均每個符號獲得的關(guān)于X的信息量，表達輸入與輸出兩個隨機變量間的統(tǒng)計約束程度。90編輯ppt另一角度：平均互信息=通信過程所消除的不確定性：I(X;Y)是I(x;y)的統(tǒng)計平均，可以證明I(X;Y)≥0。假設I(X;Y)=0，表示在信道輸出端接收到符號后不獲得任何關(guān)于輸入符號的信息。91編輯ppt

I(X;Y)

I(X;Y)=H(X)-H(X|Y)

I(X;Y)=H(Y)-H(Y|X)

I(X;Y)=H(X)+H(Y)-H(XY)其中：平均互信息與各類熵的關(guān)系92編輯ppt維拉圖：可用于各類熵與平均互信息之間關(guān)系

H(X|Y)=H(X)-I(X;Y)損失熵/信道疑義度

H(Y|X)=H(Y)-I(X;Y)噪聲熵/散布度

H(XY)=H(X)+H(Y)-I(X;Y)

H(X)圖中，左邊的圓代表隨機變量X的熵，右邊的圓代表隨機變量Y的熵，兩個圓重疊局部是平均互信息I(X;Y)。每個圓減去I(X;Y)后剩余的局部代表兩個疑義度。H(Y)H(X|Y)H(Y|X)H(XY)I(X;Y)93編輯ppt信息傳輸率信道中平均每個符號所能傳送的信息量。而平均互信息I(X;Y)那么反映了接收到一符號Y后平均每個符號獲得的關(guān)于X的信息量。因此，信息傳輸率可作如下定義：信息傳輸率RR=I(X;Y)=H(X)–H(X|Y)(比特/符號)3.4離散信道的信道容量信息傳輸速率Rt：信道在單位時間內(nèi)平均傳輸?shù)男畔⒘?。即信道中平均每秒傳輸?shù)男畔⒘浚篟t＝R/t=I(X;Y)/t=H(X)/t–H(X|Y)/t〔bit/s〕94編輯ppt一、信道容量由于平均互信息I(X;Y)是輸入隨機變量的∩型凸函數(shù)，所以對一固定的信道，總存在一種信源的輸入分布概率，使傳輸每個符號平均獲得的信息量最大。信道容量：對任何一個固定信道，存在一個最大的信息傳輸率（比特/符號）與之相對應的輸入分布概率P(X)那么稱為最正確輸入分布。95編輯ppt(Bit/s)Ct仍稱為信道容量：假設平均傳輸一個符號需要t秒鐘，那么信道在單位時間內(nèi)平均傳輸?shù)淖畲笮畔⒘繛镃t：性質(zhì)信道容量與輸入信源的概率分布無關(guān)，只是信道傳輸概率的函數(shù)，只與信道的統(tǒng)計特性有關(guān)。信道容量是完全描述信道特性的參量，是信道的最大信息傳輸率。96編輯ppt即：[例]

二元對稱信道容量的計算因此，二元對稱信道的信道容量為：前述二元對稱信道，I(X;Y)時，I(X;Y)最大。當(比特／符號)97編輯ppt1.無噪無損信道〔無噪一一對應信道〕二、簡單離散信道的信道容量例如：也即98編輯ppt其信道矩陣是單位矩陣：滿足：損失熵H(X|Y)=0、噪聲熵H(Y|X)=0，故I(X;Y)=H(X)=H(Y)

H(X)H(Y)H(X|Y)

=H(Y|X)=0I(X;Y)=H(X)=H(Y)那么信道容量：維拉圖：最正確輸入分布：等概率分布99編輯ppt2.有噪無損信道信道特點：輸入一個符號X對應假設干個輸出符號Y，且每一個X值所對應的Y值不重合。輸入符號通過傳輸變換成了假設干個輸出符號，不滿足一一對應關(guān)系，但這些輸出符號仍可以分成互不相交的一些子集合。例100編輯ppt一旦接收到符號Y后，可消除對X符號的不確定性。分析一下：

損失熵H(X|Y)，噪聲熵H(Y|X)信道矩陣特點：除了每行元素之和為1外，每一列中只有一個非零項。說明一個接收符號只對應一個發(fā)送符號，而一個發(fā)送符號對應多個接收符號，是一對多關(guān)系。101編輯ppt所以：I(X;Y)=H(X)—H(X|Y)=H(X)且I(X;Y)=H(Y)—H(Y/X)<H(Y)那么I(X;Y)=H(X)<H(Y)損失熵(信道疑義度)=0：噪聲熵〔散布度〕>0102編輯pptH(X)=I(X;Y)H(Y)H(X/Y)=0H(Y/X)>0I(X;Y)那么信道容量為：最正確輸入分布：等概率分布。維拉圖103編輯ppt3.無噪有損信道〔確定信道〕信道特點：輸入X與輸出Y之間為多對一關(guān)系，接收到符號Y后不能完全消除對X的不確定性。

前向概率

P(y|x)=0or1

后向概率

P(x|y)≠0or1可計算損失熵H(X|Y)、噪聲熵H(Y|X)。噪聲熵〔散布度〕=0損失熵〔信道疑義度〕>0104編輯ppt滿足：I(X;Y)=H(Y)—H(Y/X)=H(Y) I(X;Y)=H(X)—H(X/Y)<H(X)因此：I(X;Y)=H(Y)<H(X)

那么信道容量為：輸出符號等概率分布時H(Y)最大，且一定可以找到一種輸入分布，使得輸出符號Y到達等概率分布。H(Y)=I(X;Y)H(X)H(X/Y)>0H(Y/X)=0I(X;Y)維拉圖105編輯ppt三類信道特點：

無噪無損信道：損失熵、損失熵皆為0；

無損信道：損失熵H(X|Y)為0，噪聲熵不為0；

無噪信道:噪聲熵H(Y|X)為0，損失熵不為0；

這三類信道的信道容量的計算，從求平均互信息的極限問題退化為求信息熵的極值問題。106編輯ppt信道特點：信道矩陣P中每一行都是由同一集合{p1’，p2’，…，ps’}中的諸元素不同排列組成；信道矩陣P每一列也都是由同一集合{q1’，q2’，…，qr’}中的諸元素不同排列組成。一般s≠r。當r=s，兩個集合相同； 假設r<s，那么{qi’}是{pi’}的子集。三、對稱離散信道的信道容量例：對稱離散信道107編輯ppt非對稱離散信道強對稱信道〔均勻信道〕：假設輸入/輸出符號個數(shù)相同，都等于r，且信道矩陣為特點：總的錯誤概率為p

，對稱地平均分配給r-1個輸出符號。它是對稱離散信道的特例。108編輯ppt該項是固定X＝x時對Y求和，即對信道矩陣的行求熵。由于是對稱信道，所以H(Y/X=x)與x無關(guān)，為一常數(shù)。那么考察：對稱離散信道的平均互信息

I(X;Y)=H(Y)-H(Y/X)其中109編輯ppt因此對稱離散信道的信道容量應為：可以看出，這是在某種P(x)分布情況下，使得輸出等概分布時，即H(Y)=logs時的信道容量。在什么樣的信源輸入情況下，信道輸出等概分布呢？可以證明，輸入等概分布時，輸出也等概分布：假設輸入概率為等概率p(x)=1/r，那么110編輯ppt因是對稱離散信道，信道矩陣的每一列元素之和相等：那么有也就是：信道的輸出也是等概分布的：111編輯ppt注意：信道容量本身與輸入無關(guān)；但只有當滿足輸入的等概分布時，信息傳輸率才能到達信道容量。那么對稱離散信道的信道容量：112編輯ppt在這個信道中，每個符號平均能夠傳輸?shù)淖畲笮畔?.0817比特。[例]

某對稱離散信道的信道矩陣如下，求其信道容量。解：s=4,r=2113編輯ppt特例：對于二元對稱信道這個式子很重要。特例：對于強對稱信道，其信道容量為：114編輯ppt信道容量計算步驟當信道矩陣P是非奇異矩陣，信道容量計算過程：1〕計算βj2〕計算信道容量C3〕計算輸出分布概率P(bj)4〕計算輸入分布概率P(ai)115編輯ppt例離散無記憶信道a1a2a3a4b1b2b3b41/21/41/4111/41/41/4不是對稱信道。r=s=4,信道矩陣非奇異。利用：116編輯ppt那么有計算信道容量計算輸出概率分布可得117編輯ppt計算最正確輸入分布根據(jù)方程組求解輸入分布可得：118編輯ppt3.5

離散無記憶信道的擴展信道對于離散無記憶信道(DMC，DiscreteMemorylessChannel)，其傳遞概率滿足：可用[X，P(y/x)，Y]概率空間來描述。設離散無記憶信道的輸入符號集A＝{a1，…，ar}，輸出符號集B＝{b1

，…，bs}，信道矩陣為:119編輯ppt那么此無記憶信道的N次擴展信道的數(shù)學模型如下圖:而信道矩陣：其中：120編輯ppt[例]求二元無記憶對稱信道〔BSC〕的二次擴展信道。解：BSC的輸入和輸出變量X和Y的取值都是0或1，因此，二次擴展信道的輸入符號集為A＝{00，01，10，11}，共有22＝4個符號，輸出符號集為B＝{00，01，10，11}。由于是無記憶信道，可求得二次擴展信道的傳遞概率：信道矩陣：121編輯ppt考察：無記憶信道的N次擴展信道的平均互信息122編輯ppt定理3.5：對于一般離散信道，假設信道的輸入隨機序列為X=(X1X2…XN)，通過信道傳輸，接收到的隨機序列為Y＝(Y1Y2…YN)。其中，Xi，Yi是對應第i時刻的隨機變量。1〕假假設信道是無記憶的，即信道傳遞概率滿足：2〕假假設輸入信源是無記憶的，即滿足3〕假設信道和信源都是無記憶的，那么：123編輯ppt無記憶N次擴展信道的平均互信息1〕信道的輸入序列X=(X1X2…XN)中的隨機變量Xi取自于同一信源符號集，并且具有同一種概率分布;2〕通過相同的信道傳輸?shù)捷敵龆恕残诺纻鬟f概率不隨i改變〕隨機向量Y=(Y1Y2…YN)中隨機變量Yi也取自同一符號集，那么由定理3.5，無記憶信道的N次擴展信道假設信源也是無記憶的，那么：說明：信源無記憶時，無記憶的N次擴展信道的平均互信息等于原信道的平均互信息的N倍。124編輯ppt無記憶N次擴展信道的信道容量

一般的離散無記憶信道的N次擴展信道的信道容量是某時刻

i

通過DMC傳輸?shù)淖畲笮畔⒘啃诺赖妮斎腚S機序列X=(X1X2…XN)在同一信道中傳輸，故Ci=C一般情況下，消息序列在離散無記憶的N次擴展信道中傳輸?shù)男畔⒘浚篒〔X;Y〕NC信道容量在信源是無記憶信源且每一個輸入變量Xi到達最正確分布時到達。125編輯ppt3.8信源與信道的匹配在一般情況下，當信源與信道相連接時，其信息傳輸率并未到達最大。假設使信息傳輸率能到達或盡可能接近于信道容量，只有在信源取最正確分布時才能實現(xiàn)?！捌ヅ洙暜斝诺来_定后，信道的實際信息傳輸率與信源分布是密切相關(guān)的。當?shù)竭_信道容量時，稱信源與信道到達匹配，否那么認為信道有剩余。126編輯ppt信道剩余度

相對信道剩余度

——信道的實際信息傳輸率和信道傳輸能力之差。——可以用來衡量信道利用率的上下。

特例

在無損信道中，信道容量

C＝logr

(r是信道輸入符號數(shù))。而I(X;Y)＝H(X)，因而：信道的相對剩余度==信源的剩余度127編輯ppt意義提高無損信道的信息傳輸率，就等于減少信源的剩余度。對于無損信道，可通過信源編碼，減少信源剩余度，使信息傳輸率到達信道容量。因此在通信系統(tǒng)中，應將信源發(fā)出的符號轉(zhuǎn)換成適合信道傳輸?shù)姆?，從而使信源與信道匹配。例某離散無記憶信源通過一個無噪無損二元離散信道進行傳輸。128編輯ppt分析：

此二元信道的信道容量為：C＝1(比特／信道符號)

信源的信息熵為H(X)＝1.937(比特／信源符號)要使多符號信源在此二元信道傳輸，須對X進行二元編碼：對于碼(比特／信道符號)對于碼(比特／信道符號)信道有剩余。因此，必須通過適宜的信源編碼，使信道的信息傳輸率接近或等于信道容量。129編輯ppt第5章無失真信源編碼定理第一節(jié)編碼器第二節(jié)等長碼第五節(jié)變長信源編碼定理第三節(jié)等長信源編碼定理第四節(jié)變長碼130編輯ppt信息通過信道傳輸?shù)叫潘薜倪^程。要做到既不失真又快速地通信，需要解決兩個問題：信源編碼:在不失真或允許一定失真條件下，提高信息傳輸率.信道編碼:在信道受到干擾的情況下，增加信號的抗干擾能力，同時又使得信息傳輸率最大.最正確編碼：一般來說，抗干擾能與信息傳輸率二者相互矛盾。而編碼定理理論上證明，至少存在某種最正確的編碼能夠解決上述矛盾，做到既可靠又有效地傳輸信息。信源編碼：信源雖然多種多樣，但無論是哪種類型的信源，信源符號之間總存在相關(guān)性和分布的不均勻性，使得信源存在冗余度。信源編碼的目的就是要減少冗余，提高編碼效率。引言131編輯ppt研究方法研究信源編碼時，將信道編碼與譯碼看成是信道的一局部，從而突出信源編碼；研究信道編碼時，將信源編碼與譯碼看成是信源與信宿的一局部，從而突出信道編碼。5.1編碼器編碼器：對信源的符號按一定的數(shù)學規(guī)那么進行的變換。它可以看作這樣一個系統(tǒng)，它的輸入端為原始信源S，其符號集為而信道所能傳輸?shù)姆柤癁?32編輯ppt編碼器功能：用符號集X中的元素，將原始信源的符號變換為相應的碼字符號，編碼器輸出符號集為(碼或碼書)

稱為碼字，li為碼字的碼元個數(shù)〔碼字長度，碼長〕。碼字集合C稱為碼或碼書。133編輯ppt假設要實現(xiàn)無失真編碼，這種映射應是一一對應的可逆映射。編碼的形式化描述：

從信源符號到碼符號的一種映射或：134編輯ppt6、唯一可譯碼(單義可譯碼〕由碼構(gòu)成的任意一串有限長的碼符號序列只能被唯一的譯成所對應的信源符號序列。否那么,就為非惟一可譯碼或非單義可譯碼。例：對于二元碼，當任意給定一串碼字序列，例如…10001101…只可唯一地劃分為1,00,01,1,01，因此是惟一可譯碼；而對另一個二元碼，當碼字序列為…01001…可劃分為0,10,01或01,0,01，所以是非惟一可譯的。135編輯ppt唯一可譯碼的條件1〕不同的信源符號變換成不同的碼字(非奇異碼)；2〕任意有限長的信源序列所對應的碼元序列各不相同.即:碼的任意有限長N次擴展碼都是非奇異碼。Or:碼符號序列的反變換也唯一的〔擴展碼非奇異〕原因：假設要使某一碼為惟一可譯碼，那么對于任意有限長的碼符號序列，必須只能被惟一地分割成一個個的碼字，才能實現(xiàn)唯一的譯碼。136編輯ppt無失真的編碼的一般條件1〕碼字與信源符號之間一一對應〔非奇異碼〕；2〕碼符號序列的反變換也唯一的〔擴展碼非奇異〕。即：編碼必須是唯一可譯碼。否那么，就會引起譯碼的錯誤與失真。等長碼是唯一可譯碼的條件假設等長碼是非奇異碼，那么它的任意有限長N次擴展碼一定也是非奇異碼。因此，等長非奇異碼字一定是唯一可譯碼,因為采用固定長度劃分碼字序列.5.2等長碼137編輯ppt1〕假設對每個信源符號進行等長編碼，那么必須滿足:

其中:l是碼長，r是碼符號集的碼元數(shù)，q信源符號數(shù)。2〕假設對信源的N次擴展信源進行編碼，必須滿足:表示平均每個信源符號所需的碼符號個數(shù)。即為了使等長碼為非奇異碼〔唯一可譯碼〕，那么:138編輯ppt例證：根據(jù)依賴關(guān)系，信源符號平均所需碼符號數(shù)可減少。例設信源而其依賴關(guān)系為：1〕假設不考慮符號間的依賴關(guān)系，可得每符號碼長l＝2；2〕假設考慮符號間的二元依賴關(guān)系，可作二次擴展信源進行分析。根據(jù)條件概率僅有4項的概率不為零，可得擴展信源的碼長l’=2，而每個信源符號的平均碼長為l’/N=1。139編輯ppt5.3等長信源編碼定理給出了等長信源編碼所需碼長的極限值。定理等長信源編碼定理一熵為H(S)的離散無記憶信源，假設對其N次擴展信源進行等長r元編碼，碼長為l，對于任意大于0，只要滿足當N足夠大時，那么可以實現(xiàn)幾乎無失真編碼，反之，假設：那么不可能實現(xiàn)無失真編碼，當N趨向于無窮大時，譯碼錯誤率接近于1。140編輯ppt1、唯一可譯變長碼信源符號出現(xiàn)概率碼1碼2碼3碼4s1s2s3s41/21/41/81/801100110100001110100100010100100015.4變長碼優(yōu)勢：容易實現(xiàn)效率很高的編碼。變長碼也必須是唯一可譯碼，才能實現(xiàn)無失真編碼。碼1是一個奇異碼，故不是唯一可譯碼；碼2也不是唯一可譯碼，因為收到一串序列，無法唯一譯出對應的原符號序列，如01000，即可譯作s4s3s1,也可譯作s4s1s3,s1s2s3或s1s2s1s1；141編輯ppt因此，對于碼C：假設其為唯一可譯碼，那么必為非奇異碼；假設其為即時碼，那么必是唯一可譯碼；反之，作為唯一可譯碼，那么不一定是即時碼。所有的碼非奇異碼唯一可譯碼即時碼〔非延長碼〕142編輯ppt信源符號碼4s1s2s3s410100100012、即時碼〔非延時碼〕的樹圖構(gòu)造法對于給定碼字集合C，可用碼樹來描述。同時，樹圖法可構(gòu)造即時碼。01001111010010001碼4的樹圖描述143編輯ppt非即時碼的樹圖中間節(jié)點安排為碼字1.樹圖中間節(jié)點不作為碼字；2.一旦某節(jié)點作為碼字，那么不再繼續(xù)進行分枝。這樣可保證每個碼字不同，且滿足前綴條件碼的條件。一般編碼方法選擇相應節(jié)點作為碼字：不同的路徑上的分支，對應了相應的碼元符號，那么可得到所編碼字。10001101001000構(gòu)造即時碼144編輯ppt譯碼方法因為每一碼元對應于一個的樹圖分枝路徑，那么即時碼的樹圖可以用來譯碼。譯碼器系統(tǒng)對一串符號序列譯碼過程：1〕首先從樹根出發(fā)，根據(jù)接收的第一個碼元符號來選擇應走的第一條路徑；2〕假設沿著所選路徑走到某中間節(jié)點，再根據(jù)接收的第二個碼元符號來選擇第二條路經(jīng)；3〕假設又走到中間節(jié)點，再依次繼續(xù)選擇路徑，直到終端節(jié)點為止。這時，可根據(jù)所經(jīng)歷的枝路，判斷出所接收的碼字。4〕重新返回樹根，再作下一個接收碼字的判斷。

這樣，便可將接收到的一串碼符號序列譯成信源符號序列。145編輯ppt3、克拉夫特〔Kraft〕不等式定理對于碼符號為的任意r元即時碼，假設所對應的碼長，那么必定滿足：反之，假設碼長滿足上式，那么一定存在這樣的即時碼。*可以證明，對于唯一可譯碼也須滿足Kraft不等式。這說明，其他唯一可譯碼并不比即時碼占優(yōu)。而即時碼很容易用樹圖法構(gòu)造，所以在討論唯一可譯碼時，只需要討論即時碼就可以了。定理假設存在一個碼長為的唯一可譯碼，那么一定存在一個同樣長度的即時碼。146編輯ppt例：設二進制碼樹中X=(a1,a2,a3,a4),L1=1,L2=2,L3=2,L4=3,應用Kraft不等式,得：不存在滿足這種Li的唯一可譯碼如果將各碼字長度改成L1=1,L2=2,L3=3,L4=3,那么存在滿足這種Li唯一可譯碼0001101011011碼樹11100011010110147編輯ppt設信源編碼后的碼字為：碼長為：碼的平均長度〔平均碼長〕為：5.5變長信源編碼定理〔碼符號/信源符號〕碼的平均長度信息傳輸率〔碼率〕：平均每個碼元攜帶的信息量，即編碼后信道的信息傳輸率：〔比特/碼符號〕148編輯ppt假設信道傳輸一個碼符號平均需要t秒鐘，那么編碼后信道的每秒傳輸?shù)男畔⒘繛椋骸脖忍?秒〕由此可見：

平均碼長越短，信息傳輸效率越高。緊致碼〔最正確碼〕對于某一信源和某一個碼符號集合，假設有一個唯一可譯碼，它的平均碼長小于其他唯一可譯碼的長度。無失真信源編碼的根本問題就是尋找緊致碼。149編輯ppt定理假設對一熵為H(S)的離散無記憶信源S進行r元編碼，那么總是可以找到一種無失真編碼方法構(gòu)成唯一可譯碼，使其平均碼長滿足：

說明：下界：平均碼長不能小于極限H(s)/logr,否那么唯一可譯碼不存在。上界：給出了平均碼長的上界。但并不是說大于這個上界就不能構(gòu)成唯一可譯碼。而是說在上界范圍內(nèi)，可找到唯一可譯碼。150編輯ppt無失真變長信源編碼定理〔香農(nóng)第一定理〕離散無記憶信源S的N次擴展信源，其熵為，且編碼器碼元符號集為.對信源進行編碼，總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使信源S中每個信源符號si所需要的平均碼長滿足當那么得：151編輯ppt定理含義：

要做到無失真信源編碼，變換每個信源符號平均所需最少的r元碼元數(shù)是信源的熵值。

假設編碼的平均碼長小于信源的熵，那么唯一可譯碼不存在，在譯碼時必然帶來失真或過失。

同時，通過對擴展信源進行變長編碼，當擴展長度N足夠大時，平均碼長可到達此極限值。

信源的熵是無失真信源壓縮的極限值。

152編輯ppt定理推廣：

可以推廣到平穩(wěn)有記憶信源和馬爾科夫信源：153編輯ppt如果將定理中的下式改寫：為編碼后平均每個信源符號所能承載的最大信息量，即變長編碼后信源的信息傳輸率〔編碼信息率〕。這樣，香農(nóng)第一定理也可表述為：假設R’>=H(S),就存在唯一可譯變長編碼；假設R’<H(S),唯一可譯邊長碼不存在，不能實現(xiàn)無失真德信源編碼。那么定義：等長編碼154編輯ppt從信道角度看，編碼后信道的信息傳輸率：由此可見，此時信道的信息傳輸率等于無噪無損信道的信道容量C，信息傳輸率最高。因此，無失真信源編碼的實質(zhì)是：對離散信源進行適當編碼，使變換后新的碼符號信源〔信道的輸入信源〕盡可能等概率分布，以使新信源的每個碼符號平均所含的信息量到達最大，從而使信道的信息傳輸率R到達信道容量C，實現(xiàn)信源與信道的統(tǒng)計匹配。所以，無失真信源編碼實質(zhì)上就是無噪信道編碼問題。而那么：即：當平均碼長為極限值H(S)/logr時，那么R=logr.〔香農(nóng)第一定理〕155編輯ppt無噪信道編碼定理假設信道的信息傳輸率R≤無噪無損信道容量C=logr，總能對信源的輸出進行適當?shù)木幋a，使得在無噪無損信道上能無過失地、以最大信息傳輸率C傳輸信息；反之，假設R大C，那么無過失傳輸是不可能的。因此，信道容量C是無噪信道的無過失傳輸?shù)淖畲笮畔鬏斅?。編碼效率——衡量各種編碼距極限壓縮值得情況：156編輯ppt碼的剩余度：特別地，在二元無噪無損信道中，編碼效率為：所以，在二元無噪無損信道中信息傳輸率：即：在二元信道中，可直接用編碼的效率來衡量編碼后信道的信息傳輸率是否提高了。157編輯ppt香農(nóng)第一定理〔無失真信源編碼定理〕指出了信源無損壓縮與信源信息熵之間的關(guān)系：信息熵是無損壓縮編碼所需平均碼長的極限值，可以通過編碼使平均碼長到達極限值。物理意義：由于信息熵表達了事物所含的信息量，因此，不可能用少于信息熵的比特數(shù)來確切地表達這一事物。158編輯ppt第6章有噪信道編碼定理錯誤概率與譯碼規(guī)那么錯誤概率與編碼方法有噪信道編碼定理聯(lián)合信源信道編碼定理159編輯ppt前面已經(jīng)從理論上討論了，對于無噪無損信道只要對信源進行適當?shù)木幋a，總能以信道容量無過失的傳遞信息。但是一般信道總會存在噪聲和干擾，信息傳輸會造成損失。那么在有噪信道中怎樣能使消息傳輸發(fā)生的錯誤最少？進行無錯傳輸?shù)目蛇_的最大信息傳輸率是多少呢？這就是本章所要討論的問題。本章的核心是香農(nóng)第二定理。160編輯ppt6.1錯誤概率與譯碼規(guī)那么為了減少傳輸錯誤，提高通信的可靠性，就必須分析錯誤概率與哪些因素有關(guān)，有沒有方法控制？能控制到什么程度？一般地，錯誤概率與如下因素相關(guān)：信道的統(tǒng)計特性譯碼規(guī)那么161編輯ppt總的譯碼規(guī)那么數(shù)目信道的s個輸出符號的每一個譯碼輸出有r種選擇，因此，總的譯碼規(guī)那么總數(shù)為譯碼規(guī)那么的選擇依據(jù)一個自然的依據(jù)就是使平均錯誤概率最小。為了選擇譯碼規(guī)那么，需要計算平均錯誤概率。平均錯誤概率分析：譯碼規(guī)那么確定后，設信道輸出端收到時一定譯為。如果發(fā)送端剛好發(fā)送的就是，那么為正確譯碼，譯碼的條件正確概率為：162編輯ppt而錯誤譯碼的概率為收到后翻譯為，但發(fā)送端實際上發(fā)送的卻不是，那么為錯誤譯碼，其條件錯誤概率為：

e表示：除了以外的所有輸入符號的集合。那么可得平均錯誤譯碼概率：它表示經(jīng)過譯碼后平均每收到一個符號所產(chǎn)生錯誤的大小，也稱平均錯誤概率。163編輯ppt條件正確概率如何設計譯碼規(guī)那么，使平均錯誤概率最??？最小錯誤概率準那么〔最大后驗概率準那么〕條件錯誤概率滿足關(guān)系：因此應選擇譯碼規(guī)那么

也即收到一個符號以后譯成具有最大后驗概率的那個輸入符號。決定于譯碼規(guī)那么i為待定164編輯ppt根據(jù)貝葉斯定理，上式可寫成當信源等概分布時，那么最小錯誤概率準那么變?yōu)檫@稱為最大似然譯碼準那么，方法是收到一個后，在信道矩陣的第j列元素中選擇最大的值所對應的輸入符號作為譯碼輸出。最大似然譯碼準那么即165編輯ppt當譯碼規(guī)那么確定后，可進一步計算平均錯誤概率：平均錯誤概率的計算信道傳遞概率平均正確概率上式中，平均錯誤概率計算是在聯(lián)合概率矩陣[P(ai)P(bj|ai)]中：1〕先求每一列除去F(bj)=a*所對應的P(a*bj)以外的元素之和；2〕然后，對所有列求和。166編輯ppt例：某信道1〕假設根據(jù)最大似然準那么選擇譯碼函數(shù)為B：假設輸入等概率，那么平均錯誤概率為假設輸入不等概分布，那么錯誤概率為：167編輯ppt2〕采用最小錯誤概率譯碼準那么，那么聯(lián)合矩陣為：所得譯碼函數(shù)為：C：平均錯誤概率：168編輯ppt6.2錯誤概率與編碼方法一般信道傳輸時都會產(chǎn)生錯誤，而選擇譯碼準那么并不會消除錯誤，那么如何減少錯誤概率呢？下邊討論通過編碼方法來降低錯誤概率。例：對于如下二元對稱信道01010.990.990.010.01按照最大似然準那么譯碼，169編輯ppt如何提高信道傳輸?shù)恼_率呢？可用重復消息的方法，即嘗試擴展信道的方法。未用的碼字〔禁用碼字〕001010011100101110用作消息的碼字〔許用碼字〕000〔表示0〕111〔表示1〕輸出端接收序列000001010011100101110111二元對稱信道的三次擴展信道170編輯ppt那么信道矩陣為：根據(jù)最大似然譯碼準那么，當p=0.01，可得譯碼函數(shù)為：F(000)=000F(001)=000F(010)=000F(011)=111F(100)=000F(101)=111F(110)=111F(111)=111一位錯誤當000、111等概時，平均錯誤概率變小了：171編輯ppt現(xiàn)在碼元個數(shù)n=3，已經(jīng)將錯誤概率降低了兩個數(shù)量級；假設重復更屢次，n=5，7，…，還可以進一步降低錯誤概率，上例中：當n=5時當n=7時當n=9時當n=11時但是n很大時，信道的信息傳輸率會降低很多：〔M為許用碼字的個數(shù)，即輸入消息個數(shù)，n為編碼后碼字的長度〕在上例中：M=2當n=1時R=1當n=3時R=1/3當n=5時R=1/5〔比特/碼符號〕〔比特/碼符號〕〔比特/碼符號〕172編輯ppt分析前邊的例子，只用了擴展信源的兩個字符，因此信息率降低了，如果把8個字符全用上，信