/10/101第1章緒論重點(diǎn)掌握信息特征信息、消息、信號(hào)聯(lián)絡(luò)和區(qū)分通信系統(tǒng)物理模型

普通了解信息論理論形成和發(fā)展過(guò)程信息論研究?jī)?nèi)容

第1頁(yè)/10/102信息特征信息基本概念在于它不確定性，任何已確定事物都不含信息。接收者在收到信息之前，對(duì)它內(nèi)容是不知道，所以信息是新知識(shí)、新內(nèi)容信息是能使認(rèn)識(shí)主體對(duì)某一事物未知性或不確定性降低有用知識(shí)信息能夠產(chǎn)生，也能夠消失，同時(shí)信息能夠被攜帶、貯存及處理信息是能夠量度，信息量有多少差異第2頁(yè)/10/103消息、信號(hào)和信息信號(hào)最詳細(xì)，它是一物理量，可測(cè)量、可顯示、可描述，同時(shí)它又是載荷信息實(shí)體消息是詳細(xì)、非物理，可描述為語(yǔ)言文字、符號(hào)、數(shù)據(jù)、圖片，能夠被感覺(jué)到，同時(shí)它是信息載荷體，是信息論中主要描述形式信息是抽象、非物理

哲學(xué)層表示信息物理層表示信息數(shù)學(xué)層表示第3頁(yè)/10/104通信系統(tǒng)模型介紹信道信源信源編碼加密信道編碼干擾源信宿信源解碼解密信道解碼加密密鑰解密密鑰第4頁(yè)/10/105第2章信源及信源熵重點(diǎn)掌握信源分類(lèi)和數(shù)學(xué)描述自信息量、互信息離散信源熵離散序列信源熵熵性質(zhì)普通了解連續(xù)信源熵冗余度第5頁(yè)/10/106信源分類(lèi)離散信源{離散無(wú)記憶信源離散有記憶信源{{發(fā)出單個(gè)符號(hào)無(wú)記憶信源發(fā)出符號(hào)序列無(wú)記憶信源發(fā)出符號(hào)序列有記憶信源發(fā)出符號(hào)序列馬爾可夫信源第6頁(yè)/10/107信源數(shù)學(xué)描述單符號(hào)無(wú)記憶信源用一維離散型隨機(jī)變量X來(lái)描述這些信息輸出。數(shù)學(xué)模型符號(hào)序列無(wú)記憶信源很多實(shí)際信源輸出消息往往是由一系列符號(hào)組成，這種用每次發(fā)出1組含2個(gè)以上符號(hào)符號(hào)序列來(lái)代表一個(gè)消息信源叫做發(fā)出符號(hào)序列信源。設(shè)信源輸出隨機(jī)序列為X， 序列中變量第7頁(yè)/10/108信源數(shù)學(xué)描述有記憶信源聯(lián)合概率表示比較復(fù)雜，需要引入條件概率來(lái)反應(yīng)信源發(fā)出符號(hào)序列內(nèi)各個(gè)符號(hào)之間記憶特征。第8頁(yè)/10/109信源數(shù)學(xué)描述一階馬爾可夫信源m階馬爾可夫信源第9頁(yè)/10/1010自信息量隨機(jī)事件自信息量定義為其概率對(duì)數(shù)負(fù)值，即I(xi)

含義:當(dāng)事件xi發(fā)生以前，表示事件xi發(fā)生不確定性當(dāng)事件xi發(fā)生以后，表示事件xi所含有信息量第10頁(yè)/10/1011自信息量特征I(xi)是非負(fù)值當(dāng)p(xi)=1時(shí)，I(xi)=0當(dāng)p(xi)=0時(shí)，I(xi)=∞I(xi)是先驗(yàn)概率p(xi)單調(diào)遞減函數(shù)，即當(dāng)p(x1)＞p(x2)時(shí)，I(x1)＜I(x2)兩個(gè)獨(dú)立事件聯(lián)合信息量等于它們分別信息量之和。即：統(tǒng)計(jì)獨(dú)立信源信息量等于它們分別信息量之和。第11頁(yè)/10/1012聯(lián)合自信息量?jī)蓚€(gè)消息xi，yj同時(shí)出現(xiàn)聯(lián)合自信息量當(dāng)xi,yj相互獨(dú)立時(shí)，有p(xi

yj)=p(xi)p(yj)，那么就有I(xi

yj)=I(xi)+I(yj)。xi

yj所包含不確定度在數(shù)值上也等于它們自信息量。第12頁(yè)/10/1013條件自信息量在事件yj出現(xiàn)條件下，隨機(jī)事件xi發(fā)生條件概率為p(xi/yj)，則它條件自信息量定義為條件概率對(duì)數(shù)負(fù)值：在給定yj條件下，隨機(jī)事件xi所包含不確定度在數(shù)值上與條件自信息量相同，但二者含義不一樣。聯(lián)合自信息量、條件自信息量和自信息量第13頁(yè)/10/1014信源熵離散信源熵為信源中各個(gè)符號(hào)不確定度數(shù)學(xué)期望信源熵物理含義表示信源輸出前信源平均不確定性表示信源輸出后每個(gè)符號(hào)所攜帶平均信息量第14頁(yè)/10/1015條件熵在給定yj條件下，xi條件自信息量為I(xi/yj)，X集合條件熵在給定Y（即各個(gè)yj）條件下，X集合條件熵在給定X（即各個(gè)xi）條件下，Y集合條件熵條件熵是在聯(lián)合符號(hào)集合XY上條件自信息量聯(lián)合概率加權(quán)統(tǒng)計(jì)平均值。條件熵H(X/Y)表示已知Y后，X不確定度。第15頁(yè)/10/1016聯(lián)合熵聯(lián)合熵是聯(lián)合符號(hào)集合XY上每個(gè)元素對(duì)xiyj自信息量概率加權(quán)統(tǒng)計(jì)平均值聯(lián)合熵H(XY)表示X和Y同時(shí)發(fā)生不確定度。聯(lián)合熵、信源熵和條件熵之間關(guān)系第16頁(yè)/10/1017互信息定義：xi后驗(yàn)概率與先驗(yàn)概率比值對(duì)數(shù)事件xi是否發(fā)生含有不確定性，用I(xi)度量。接收到符號(hào)yj后，事件xi是否發(fā)生仍保留有一定不確定性，用I(xi

/yj)度量。接收到某消息yj后取得關(guān)于事件xi信息量，用I(xi;yj)表示。第17頁(yè)/10/1018平均互信息互信息量I(xi;yj)在X集合上統(tǒng)計(jì)平均值為I(X;yj)在Y集合上概率加權(quán)統(tǒng)計(jì)平均值平均互信息（量）第18頁(yè)/10/1019平均互信息量物理意義H(X/Y)：信道疑義度，損失熵信源符號(hào)經(jīng)過(guò)有噪信道傳輸后引發(fā)信息量損失。信源X熵等于接收到信息量加損失掉信息量。

H(Y/X)：噪聲熵，散布度它反應(yīng)了信道中噪聲源不確定性。輸出端信源Y熵H(Y)等于接收到關(guān)于X信息量I(X;Y)加上H(Y/X)，這完全是由信道中噪聲引發(fā)。第19頁(yè)/10/1020熵性質(zhì)非負(fù)性H(X)＝H(x1,x2,……,xn)≥0等號(hào)在p(xi)=1時(shí)成立對(duì)稱(chēng)性H(x1,x2,……,xn)＝H(x2,x1,……,xn)熵函數(shù)只與隨機(jī)變量總體結(jié)構(gòu)相關(guān)確定性H(0,1)＝H(1,0,0,……,0)＝0只要信源符號(hào)集中有一個(gè)符號(hào)出現(xiàn)概率為1，信源熵就等于零第20頁(yè)/10/1021熵性質(zhì)香農(nóng)輔助定理對(duì)于P＝(p1,p2,……,pn)和Q＝(q1,q2,……,qn)對(duì)任意概率分布pi，它對(duì)其它概率分布qi自信息量取數(shù)學(xué)期望時(shí)，必大于pi本身熵最大熵定理離散無(wú)記憶信源輸出M個(gè)不一樣信息符號(hào)，當(dāng)且僅當(dāng)各個(gè)符號(hào)出現(xiàn)概率時(shí)（即等概率分布），熵最大第21頁(yè)/10/1022互信息量與熵H(X/Y)H(X)H(Y)H(XY)H(Y/X)I(X;Y)第22頁(yè)/10/1023離散無(wú)記憶信源序列熵設(shè)信源輸出隨機(jī)序列為X

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

xn}信源序列熵能夠表示為信源序列中，平均每個(gè)符號(hào)熵為離散無(wú)記憶信源平均每個(gè)符號(hào)符號(hào)熵HL(X)等于單個(gè)符號(hào)信源符號(hào)熵H(X)無(wú)記憶無(wú)記憶、平穩(wěn)第23頁(yè)/10/1024離散有記憶信源序列熵若信源輸出一個(gè)L長(zhǎng)序列，則信源序列熵為平均每個(gè)符號(hào)熵為信源無(wú)記憶時(shí)滿足平穩(wěn)時(shí)第24頁(yè)/10/1025離散平穩(wěn)信源結(jié)論1：H(XL/XL-1)是L單調(diào)非增函數(shù)結(jié)論2：HL

(X)≥H(XL/XL-1)結(jié)論3：HL

(X)是L單調(diào)非增函數(shù)結(jié)論4：當(dāng)L→∞時(shí)，H∞(X)稱(chēng)為極限熵第25頁(yè)/10/1026馬爾可夫信源若一個(gè)信源滿足下面兩個(gè)條件，則稱(chēng)為馬爾可夫信源：某一時(shí)刻信源輸出符號(hào)概率只與當(dāng)前所處狀態(tài)相關(guān)，而與以前狀態(tài)無(wú)關(guān)；信源下一個(gè)狀態(tài)由當(dāng)前狀態(tài)和下一刻輸出符號(hào)唯一確定。符號(hào)條件概率信源在某一時(shí)刻出現(xiàn)符號(hào)xj概率與信源此時(shí)所處狀態(tài)si相關(guān)，用條件概率表示為p(xj/si)。狀態(tài)轉(zhuǎn)移概率當(dāng)信源符號(hào)xj出現(xiàn)后，信源所處狀態(tài)將發(fā)生改變，并轉(zhuǎn)入一個(gè)新?tīng)顟B(tài)。這種狀態(tài)轉(zhuǎn)移可用狀態(tài)轉(zhuǎn)移概率p(sj/si)表示。第26頁(yè)/10/1027狀態(tài)轉(zhuǎn)移圖（香農(nóng)線圖）齊次馬爾可夫鏈能夠用其狀態(tài)轉(zhuǎn)移圖（香農(nóng)線圖）表示每個(gè)圓圈代表一個(gè)狀態(tài)

狀態(tài)之間有向線代表從某一狀態(tài)向另一狀態(tài)轉(zhuǎn)移有向線一側(cè)符號(hào)和數(shù)字分別代表發(fā)出符號(hào)和條件概率sos1x2/0.6x1/0.3x1/0.4s2x2/0.2x1/0.8x2/0.7p(x1/s2)=0.8p(s2/s2)=0.8第27頁(yè)/10/1028穩(wěn)定馬爾可夫信源極限概率Wj一個(gè)不可約、非周期、狀態(tài)有限馬爾可夫鏈，其k步轉(zhuǎn)移概率pij(k)在k→∞時(shí)趨于一個(gè)和初始狀態(tài)無(wú)關(guān)概率，即不論起始狀態(tài)怎樣，這種馬氏鏈都能夠最終到達(dá)穩(wěn)定，即全部變量Xk概率分布均不變。能夠用P這一矩陣充分描述穩(wěn)定馬氏鏈。平穩(wěn)分布Wj可用以下方程組求得第28頁(yè)/10/1029馬爾可夫信源熵M階馬爾可夫信源極限熵齊次、遍歷馬爾可夫信源熵處于狀態(tài)si時(shí)符號(hào)平均不確定性第29頁(yè)/10/1030第3章信道與信道容量重點(diǎn)掌握有干擾無(wú)記憶信道數(shù)學(xué)描述信道容量定義對(duì)稱(chēng)和準(zhǔn)對(duì)稱(chēng)DMC信道信道容量計(jì)算香農(nóng)公式普通了解信道各種分類(lèi)無(wú)干擾離散信道信道容量信源和信道匹配第30頁(yè)/10/1031信道分類(lèi)按信道用戶數(shù)量來(lái)劃分 單用戶信道、多用戶信道按輸入/輸出之間關(guān)系來(lái)劃分

無(wú)反饋信道、反饋信道按信道參數(shù)與時(shí)間關(guān)系來(lái)劃分 固定參數(shù)信道、時(shí)變參數(shù)信道按信道中噪聲種類(lèi)來(lái)劃分

隨機(jī)差錯(cuò)信道、突發(fā)差錯(cuò)信道按輸入/輸出信號(hào)在幅度和時(shí)間上取值劃分離散信道、連續(xù)信道、半離散半連續(xù)信道、波形信道第31頁(yè)/10/1032信道模型依據(jù)干擾和記憶性分類(lèi)無(wú)干擾（無(wú)噪聲）信道有干擾無(wú)記憶信道有干擾有記憶信道信道模型信道輸入Xi={a1,a2,…,an}信道輸出Yj={b1,b2,…,bm}信道轉(zhuǎn)移概率矩陣p(Y/X)信道輸入X輸出Yp(Y/X)第32頁(yè)/10/1033信道模型二進(jìn)制離散信道：BSC信道輸入符號(hào)X取值{0,1}輸出符號(hào)Y取值{0,1}離散無(wú)記憶信道：DMC信道輸入符號(hào)集

X={a1,a2,…,an}輸出符號(hào)集

Y={b1,b2,…,bm}第33頁(yè)/10/1034信道模型離散輸入、連續(xù)輸出信道輸入符號(hào)集：X={a1,a2,…,an}輸出未經(jīng)量化，即Y={-∞,∞}輸出特征由離散輸入X、連續(xù)輸出Y以及一組條件概率密度函數(shù)p(y/X=ai)

來(lái)決定。波形信道輸入是模擬波形，輸出也是模擬波形連續(xù)無(wú)記憶信道和連續(xù)有記憶信道y(t)＝x(t)＋n(t)

n(t)代表加性噪聲第34頁(yè)/10/1035信道容量定義信道傳輸率R＝I(X;Y)bit/符號(hào)信道中平均每個(gè)符號(hào)能傳送信息量信息傳輸速率Rt＝I(X;Y)/t

bit/s信道中單位時(shí)間傳送信息量信道容量給定轉(zhuǎn)移概率矩陣P后，平均互信息I(X;Y)是概率矢量Px上凸函數(shù)。I(Px)極大值就是信道容量。第35頁(yè)/10/1036離散單符號(hào)信道離散單個(gè)符號(hào)信道無(wú)干擾離散信道有擾離散信道對(duì)稱(chēng)DMC信道準(zhǔn)對(duì)稱(chēng)DMC信道普通DMC信道無(wú)噪無(wú)損信道無(wú)噪有損信道有噪無(wú)損信道第36頁(yè)/10/1037無(wú)干擾離散信道無(wú)噪無(wú)損信道C=maxI(X;Y)=logn無(wú)噪有損信道C=maxI(X;Y)=maxH(Y)有噪無(wú)損信道C=maxI(X;Y)=maxH(X)第37頁(yè)/10/1038DMC信道容量對(duì)稱(chēng)DMC信道性質(zhì)對(duì)稱(chēng)信道條件熵H(Y/X)與信道輸入符號(hào)概率分布無(wú)關(guān)。假如信道輸入符號(hào)等概率分布，則信道輸出符號(hào)也等概率分布；反之，若信道輸出符號(hào)等概率分布時(shí)，信道輸入符號(hào)也是等概率分布。當(dāng)信道輸入符號(hào)等概率分布時(shí)，對(duì)稱(chēng)DMC信道到達(dá)其信道容量。第38頁(yè)/10/1039DMC信道容量準(zhǔn)對(duì)稱(chēng)DMC信道容量假如轉(zhuǎn)移概率矩陣P輸入對(duì)稱(chēng)而輸出不對(duì)稱(chēng)，則稱(chēng)該信道是準(zhǔn)對(duì)稱(chēng)DMC信道。當(dāng)信道輸入符號(hào)等概率分布時(shí)，準(zhǔn)對(duì)稱(chēng)DMC信道到達(dá)其信道容量C。矩陣分解法：將轉(zhuǎn)移概率矩陣劃分成若干個(gè)互不相交對(duì)稱(chēng)子矩陣。第39頁(yè)/10/1040DMC信道容量普通DMC信道容量以輸入符號(hào)概率矢量Px為自變量函數(shù)I(Px)極大值，即信道容量。為了使I(X;Y)最大化，即求取信道容量值，輸入概率集{p(xi)}必須滿足充分必要條件是：I(xi;Y)＝C，對(duì)于全部滿足p(xi)＞0條件iI(xi;Y)≤C，對(duì)于全部滿足p(xi)＝0條件i每一個(gè)概率不為0輸入符號(hào)對(duì)輸出提供相同互信息第40頁(yè)/10/1041離散序列信道及其容量信道輸入X輸出Yp(Y/X)X=(X1,X2,…,XL)Xl={a1,a2,…,an}Y=(Y1,Y2,…,YL)Yl={b1,b2,…,bm}獨(dú)立、無(wú)記憶、平穩(wěn)離散序列信道信道容量為：無(wú)記憶離散序列信道轉(zhuǎn)移概率為：第41頁(yè)/10/1042連續(xù)信道連續(xù)單符號(hào)加性信道信道輸入和輸出都是取值連續(xù)一維隨機(jī)變量，加入信道噪聲是均值為零、方差為σ2加性高斯噪聲。多維無(wú)記憶加性連續(xù)信道可等價(jià)成L個(gè)獨(dú)立并聯(lián)高斯加性信道注水法：噪聲小子信道分配到輸入功率大，傳輸比特?cái)?shù)多。受加性高斯白噪聲干擾帶限波形信道輸入x(t)、輸出y(t)和噪聲n(t)：模擬波形第42頁(yè)/10/1043香農(nóng)公式香農(nóng)公式W：頻帶寬度，簡(jiǎn)稱(chēng)帶寬SNR(信噪比)：表示信號(hào)功率與噪聲功率比值加性白噪聲功率譜密度為N0/2Pav：信號(hào)平均功率香農(nóng)限每傳輸1比特信息所需能量。當(dāng)歸一化信噪比小于香農(nóng)限（-1.6dB）時(shí)，歸一化信道容量為零，即信道完全喪失通信能力。第43頁(yè)/10/1044香農(nóng)公式討論帶寬W一定時(shí)，信道容量C

隨信噪比SNR增加而單調(diào)增加，所以增大信號(hào)功率、減小信道噪聲能夠增加信道容量。信道容量C一定時(shí)，帶寬W增大，信噪比SNR可降低，即二者能夠交換。假如輸入信號(hào)功率PS固定，信道容量C

隨帶寬W增加而增加。但到一定階段后，增加變得遲緩。第44頁(yè)/10/1045信源與信道匹配符號(hào)匹配信源輸出符號(hào)必須是信道能夠傳送符號(hào)，這是實(shí)現(xiàn)信息傳輸必要條件。信息匹配對(duì)于某一信道，只有當(dāng)輸入符號(hào)概率分充滿足一定條件時(shí)，才能到達(dá)其信道容量。信道冗余度信道絕對(duì)冗余度＝C－I(X;Y)信道相對(duì)冗余度第45頁(yè)/10/1046第4章信息率失真函數(shù)重點(diǎn)掌握失真函數(shù)、平均失真保真度準(zhǔn)則信息率失真函數(shù)定義域信息率失真函數(shù)與信道容量比較普通了解信息率失真函數(shù)性質(zhì)連續(xù)信源平均失真第46頁(yè)/10/1047失真函數(shù)單符號(hào)失真函數(shù)定義為：將全部d(xi,yj)排列起來(lái)，用矩陣表示為d稱(chēng)為失真矩陣第47頁(yè)/10/1048失真函數(shù)假如假定離散信源輸出符號(hào)序列X=(X1X2…Xl…XL),

Xl∈A={a1,…an}，其中L長(zhǎng)符號(hào)序列xi=(xi1xi2…xiL)，經(jīng)信源編碼后輸出符號(hào)序列Y=(Y1Y2…Yl…YL)，Yl∈B={b1,…bm}，其中L長(zhǎng)符號(hào)序列 yj=(yj1yj2…yjL)， 序列失真函數(shù)定義為式中，d(xil,yjl)表示信源輸出符號(hào)序列xi第l個(gè)符號(hào)和編碼輸出符號(hào)序列yj第l個(gè)符號(hào)之間失真函數(shù)信源序列失真度等于序列中對(duì)應(yīng)單個(gè)符號(hào)失真度之和第48頁(yè)/10/1049平均失真將失真函數(shù)數(shù)學(xué)期望或統(tǒng)計(jì)平均值稱(chēng)為平均失真。失真函數(shù)d(xi,yj)描述某個(gè)信源符號(hào)經(jīng)過(guò)傳輸后失真大小。對(duì)于不一樣信源符號(hào)和不一樣接收符號(hào)，其值是不一樣。平均失真：平均失真對(duì)信源和信道進(jìn)行統(tǒng)計(jì)平均。描述某一信源在某一試驗(yàn)信道傳輸下失真大小，是從總體上描述整個(gè)系統(tǒng)失真情況。第49頁(yè)/10/1050平均失真L維信源符號(hào)序列平均失真度當(dāng)信源與信道無(wú)記憶時(shí)，信源符號(hào)平均失真度（平均每個(gè)符號(hào)平均失真度）表示信源符號(hào)序列第l個(gè)符號(hào)平均失真第50頁(yè)/10/1051保真度準(zhǔn)則保真度準(zhǔn)則平均失真度小于允許失真D允許信道D允許試驗(yàn)信道，即滿足保真度準(zhǔn)則試驗(yàn)信道。滿足保真度準(zhǔn)則全部試驗(yàn)信道，即轉(zhuǎn)移概率分布p(yj/xi)，組成了一個(gè)信道集合第51頁(yè)/10/1052信息率失真函數(shù)信息率失真函數(shù)R(D)限定失真為D條件下，信源輸出最小信息率。R(D)定義域率失真函數(shù)定義域問(wèn)題就是在信源和失真函數(shù)已知情況下，討論允許平均失真度D最小和最大取值問(wèn)題，即[Dmin,Dmax]Dmin計(jì)算Dmax計(jì)算第52頁(yè)/10/1053信息率失真函數(shù)性質(zhì)

R(D)是非負(fù)實(shí)數(shù)，0≤R(D)≤H(X)

定義域?yàn)?≤Dmin≤D≤Dmax

當(dāng)D＞Dmax時(shí)，R(D)≡0

R(D)是關(guān)于D下凸函數(shù)R(D)在定義域內(nèi)是失真度DU型下凸函數(shù)。R(D)在定義域內(nèi)是關(guān)于D連續(xù)函數(shù)。

R(D)單調(diào)遞減性允許失真度越大，所要求信息率越小。第53頁(yè)/10/1054率失真函數(shù)和信道容量比較平均互信息I(X;Y)信源概率分布p(xi)上凸函數(shù)。信道傳遞概率p(yj/xi)下凸函數(shù)。信道容量信息率失真函數(shù)信道固定輸入概率分布固定第54頁(yè)/10/1055率失真函數(shù)和信道容量比較第55頁(yè)/10/1056第5章信源編碼重點(diǎn)掌握分組碼屬性唯一可譯碼判斷方法信源編碼定理香農(nóng)編碼、費(fèi)諾編碼、哈夫曼編碼普通了解編碼術(shù)語(yǔ)游程編碼、算術(shù)編碼第56頁(yè)/10/1057分組碼屬性碼非分組碼分組碼奇異碼非奇異碼非唯一可譯碼唯一可譯碼非即時(shí)碼即時(shí)碼（非延長(zhǎng)碼）第57頁(yè)/10/1058碼樹(shù)中間節(jié)點(diǎn)不安排碼字，只在終端節(jié)點(diǎn)安排碼字每個(gè)終端節(jié)點(diǎn)對(duì)應(yīng)碼字由從根節(jié)點(diǎn)出發(fā)到終端節(jié)點(diǎn)走過(guò)路徑上所對(duì)應(yīng)符號(hào)組成當(dāng)?shù)趇階節(jié)點(diǎn)作為終端節(jié)點(diǎn)，且分配碼字，則碼字碼長(zhǎng)為i按樹(shù)圖法組成碼一定滿足即時(shí)碼定義樹(shù)碼各個(gè)分支都延伸到最終一級(jí)端點(diǎn)，則稱(chēng)為滿樹(shù)，不然為非滿樹(shù)

滿樹(shù)碼是定長(zhǎng)碼，非滿樹(shù)碼是變長(zhǎng)碼第58頁(yè)/10/1059克勞夫特不等式唯一可譯碼存在充分和必要條件為：各碼字長(zhǎng)度Ki應(yīng)滿足下式。m是進(jìn)制數(shù)，n是信源符號(hào)數(shù)注意：克拉夫特不等式只是說(shuō)明唯一可譯碼是否存在，并不能作為唯一可譯碼判據(jù)。第59頁(yè)/10/1060唯一可譯碼判斷法將碼C中全部可能尾隨即綴組成一個(gè)集合F，當(dāng)且僅當(dāng)集合F中沒(méi)有包含任一碼字，則可判斷此碼C為唯一可譯碼。集合F組成方法首先觀察碼C中最短碼字是否是其它碼字前綴。若是，將其全部可能尾隨即綴排列出。而這些尾隨即綴又有可能是一些碼字前綴（或者一些碼字是這些尾隨即綴前綴），再將這些尾隨即綴產(chǎn)生新尾隨即綴列出。依此下去，直到?jīng)]有一個(gè)尾隨即綴是碼字前綴為止。按照上述步驟將次短碼字、…等等全部碼字可能產(chǎn)生尾隨即綴全部列出。最終得到碼C全部可能尾隨即綴集合F。第60頁(yè)/10/1061唯一可譯碼判斷方法和步驟首先，觀察是否是奇異碼。若是，一定不是唯一可譯碼。其次，計(jì)算碼長(zhǎng)是否滿足Kraft不等式。若不滿足，一定不是唯一可譯碼。按照樹(shù)圖結(jié)構(gòu)法則，若能將碼畫(huà)成碼樹(shù)則是即時(shí)碼，也就是唯一可譯碼。按唯一可譯碼判斷法進(jìn)行判斷。只有唯一可譯碼判斷法能確切判斷是否是唯一可譯碼第61頁(yè)/10/1062無(wú)失真信源編碼設(shè)信源符號(hào)序列長(zhǎng)度為L(zhǎng)變換成由KL個(gè)符號(hào)組成 碼序列（碼字）變換要求能夠無(wú)失真或無(wú)差錯(cuò)地從Y恢復(fù)X，也就是能正確地進(jìn)行反變換或譯碼傳送Y時(shí)所需要信息率最小第62頁(yè)/10/1063定長(zhǎng)編碼定理定長(zhǎng)編碼定理：由L個(gè)符號(hào)組成、每個(gè)符號(hào)熵為HL(X)無(wú)記憶平穩(wěn)信源符號(hào)序列X1X2…Xl…XL，可用KL個(gè)符號(hào)Y1,Y2,…,Yk,…YKL（每個(gè)符號(hào)有m種可能值）進(jìn)行定長(zhǎng)編碼。對(duì)任意ε>0，δ>0，只要 則當(dāng)L足夠大時(shí)，必可使譯碼差錯(cuò)小于δ；反之，當(dāng) 時(shí)，譯碼差錯(cuò)一定是有限值，而當(dāng)L足夠大時(shí)，譯碼幾乎必定犯錯(cuò)。第63頁(yè)/10/1064編碼效率差錯(cuò)概率當(dāng)信源序列長(zhǎng)度L滿足 時(shí)， 就能到達(dá)差錯(cuò)率要求。編碼效率最正確編碼效率為第64頁(yè)/10/1065變長(zhǎng)編碼定理單個(gè)符號(hào)變長(zhǎng)編碼定理若一離散無(wú)記憶信源符號(hào)熵為H(X)，每個(gè)信源符號(hào)用m進(jìn)制碼元進(jìn)行變長(zhǎng)編碼，一定存在一個(gè)無(wú)失真編碼方法，其碼字平均長(zhǎng)度滿足以下不等式第65頁(yè)/10/1066變長(zhǎng)編碼定理離散平穩(wěn)無(wú)記憶序列變長(zhǎng)編碼定理對(duì)于平均符號(hào)熵為HL(X)離散平穩(wěn)無(wú)記憶信源，必存在一個(gè)無(wú)失真編碼方法，使平均信息率滿足不等式其中，ε為任意小正數(shù)。第66頁(yè)/10/1067香農(nóng)編碼步驟將信源消息符號(hào)按其概率從大到小排列確定滿足以下不等式整數(shù)碼長(zhǎng)Ki令P1=0，計(jì)算第i個(gè)消息累加概率將累加概率Pi變換成二進(jìn)制數(shù)，取小數(shù)點(diǎn)后Ki位為該消息碼字第67頁(yè)/10/1068費(fèi)諾編碼方法費(fèi)諾編碼屬于概率匹配編碼，不是最正確編碼方法。編碼過(guò)程以下：將信源消息符號(hào)按其出現(xiàn)概率依次排列

p(x1)≥p(x2)≥…≥p(xn)按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能靠近或相等，并為每一組分配一位碼元。如編二進(jìn)制碼就分成兩組，編m進(jìn)制碼就分成m組。將每一分組再按一樣標(biāo)準(zhǔn)劃分，重復(fù)步驟2，直至概率不再可分為止。信源符號(hào)所對(duì)應(yīng)碼字即為費(fèi)諾碼。第68頁(yè)/10/1069哈夫曼編碼方法哈夫曼編碼步驟將信源消息符號(hào)按其出現(xiàn)概率大小依次排列

p(x1)≥p(x2)≥…≥p(xn)取兩個(gè)概率最小符號(hào)分別配以0和1，并將這兩個(gè)概率相加作為一個(gè)新符號(hào)概率，與未分配碼元符號(hào)重新排隊(duì)。對(duì)重排后兩個(gè)概率最小符號(hào)重復(fù)步驟2過(guò)程。繼續(xù)上述過(guò)程，直到最終兩個(gè)符號(hào)配以0和1為止。從最終一級(jí)開(kāi)始，向前返回得到各個(gè)信源符號(hào)所對(duì)應(yīng)碼元序列，即對(duì)應(yīng)碼字。第69頁(yè)/10/1070三種編碼比較香農(nóng)碼、費(fèi)諾碼、哈夫曼碼都考慮了信源統(tǒng)計(jì)特征，經(jīng)常出現(xiàn)信源符號(hào)對(duì)應(yīng)較短碼字，使信源平均碼長(zhǎng)縮短，從而實(shí)現(xiàn)對(duì)信源壓縮。香農(nóng)碼有系統(tǒng)、惟一編碼方法，但在很多情況下編碼效率不是很高。費(fèi)諾碼和哈夫曼碼編碼方法都不惟一。費(fèi)諾碼比較適合于對(duì)分組概率相等或靠近信源編碼。哈夫曼碼對(duì)信源統(tǒng)計(jì)特征沒(méi)有特殊要求，編碼效率比較高，對(duì)編碼設(shè)備要求也比較簡(jiǎn)單，所以綜合性能優(yōu)于香農(nóng)碼和費(fèi)諾碼。第70頁(yè)/10/1071限失真信源編碼定理設(shè)離散無(wú)記憶信源X信息率失真函數(shù)為R(D)當(dāng)信息率R＞R(D)時(shí)，只要信源序列長(zhǎng)度L

足夠長(zhǎng)，一定存在一個(gè)編碼方法，其譯碼失真小于或等于D＋ε，ε為任意小正數(shù)。反之，若R＜R(D)，則不論采取什么樣編碼方法，其譯碼失真必大于D。假如是二元信源，則對(duì)于任意小