信息論-總復(fù)習(xí)課件new.ppt

1、總 復(fù) 習(xí)1 概論2 信源及信息熵3 信源編碼4 信道及信道容量5 信道編碼6 信息率失真函數(shù)7 考試情況 1信息與消息和信號的區(qū)別消息：是指包含有信息的語言、文字和圖像等，可表達(dá)客觀物質(zhì)運(yùn)動(dòng)和主觀思維活動(dòng)的狀態(tài)。信號：把消息變換成適合信道傳輸?shù)奈锢砹浚@種物理量稱為信號（如電信號、光信號、聲音信號等）。信息是事物運(yùn)動(dòng)狀態(tài)和狀態(tài)改變的方式。第1章 概論2信息信息是事物運(yùn)動(dòng)狀態(tài)和狀態(tài)改變的方式。研究信息論的目的：它的主要目的是提高信息系統(tǒng)的可靠性、有效性和安全性以便達(dá)到系統(tǒng)最優(yōu)化。在通信系統(tǒng)中形式上傳輸?shù)氖窍ⅲ珜?shí)質(zhì)上傳輸?shù)氖切畔?。消息只是表達(dá)信息的工具，載荷信息的客體。3編碼器信宿信道消息干

2、擾消息通信系統(tǒng)模型信源信號解碼器信號+干擾噪聲源信息論的研究對象:通信系統(tǒng)模型.信源信道加密信源信道解密通信系統(tǒng)的基本任務(wù)要求可靠: 要使信源發(fā)出的消息經(jīng)過傳輸后，盡可能準(zhǔn)確地、不失真或限定失真地再現(xiàn)在接收端有效: 用盡可能短的時(shí)間和盡可能少的設(shè)備來傳輸最大的消息4單符號離散信源自信息量用概率測度定義信息量，設(shè)離散信源 X，其概率空間為如果知道事件 xi 已發(fā)生，則該事件所含有的自信息定義為第2章 信源熵5聯(lián)合自信息量當(dāng) X 和 Y 相互獨(dú)立時(shí)，p(xiyj)=p(xi)p(yj)6條件自信息量：已知yj 的條件下xi 仍然存在的不確定度。自信息量、條件自信息量和聯(lián)合自信息量之間的關(guān)系7互信息

3、量：yj 對 xi 的互信息量定義為的后驗(yàn)概率與先驗(yàn)概率比值的對數(shù)。兩個(gè)不確定度之差是不確定度被消除的部分，即等于自信息量減去條件自信息量。 8平均信息量信源熵：自信息的數(shù)學(xué)期望。也稱為信源的信息熵/信源熵/熵。信息熵的意義：信源的信息熵 H 是從整個(gè)信源的統(tǒng)計(jì)特性來考慮的。它是從平均意義上來表征信源的總體特性的。對于某特定的信源，其信息熵是唯一的。不同的信源因統(tǒng)計(jì)特性不同，其熵也不同。9條件熵：是在聯(lián)合符號集合 XY 上的條件自信息的數(shù)學(xué)期望。聯(lián)合熵 H(XY)：表示輸入隨機(jī)變量 X，經(jīng)信道傳輸?shù)竭_(dá)信宿，輸出隨機(jī)變量 Y。即收、發(fā)雙方通信后，整個(gè)系統(tǒng)仍然存在的不確定度。10信道疑義度H(X|

4、Y)：表示信宿在收到 Y 后，信源 X 仍然存在的不確定度。是通過有噪信道傳輸后引起的信息量的損失，故也可稱為損失熵。噪聲熵H(Y|X)：表示在已知 X 的條件下，對于符號集 Y 尚存在的不確定性，這完全是由于信道中噪聲引起的。唯一確定信道噪聲所需要的平均信息量。11平均互信息量定義：互信息量 I(xi;yj) 在聯(lián)合概率空間 P(XY) 中的統(tǒng)計(jì)平均值。從一個(gè)事件獲得另一個(gè)事件的平均互信息需要消除不確定度，一旦消除了不確定度，就獲得了信息。12熵H(X)H(X)=H(X|Y)H(X)=H(X|Y)+I(X;Y) X Y條件熵H(X|Y)H(X|Y)=H(XY)-H(Y) =H(X)-I(X;

5、Y) X Y聯(lián)合熵H(XY)=H(YX)H(XY)=H(X)+H(Y|X)=H(X|Y)+H(Y|X)+I(X;Y) X Y平均互信息I(X;Y)=I(Y;X)I(X;Y)=H(X)-H(X|Y) =H(X)+H(Y)-H(X,Y) X Y平均互信息和熵的關(guān)系13數(shù)據(jù)處理定理（信息不增原理）當(dāng)消息通過多級處理器時(shí),隨著處理器數(shù)目的增多,輸入消息和輸出消息之間的平均互信息量趨于變小。信息不增I(X;Z) I(X;f(Z)=I(X;Y) H(X|Z) H(X|f(Z)=H(X|Y)14最大離散熵定理 (極值性) ：離散無記憶信源輸出 n 個(gè)不同的信息符號，當(dāng)且僅當(dāng)各個(gè)符號出現(xiàn)概率相等時(shí) (即p(x

6、i)=1/n)，熵最大。Hp(x1),p(x2),p(xn)logn15二進(jìn)制信源的熵函數(shù) H(p) 為16BSC信道的平均互信息量 設(shè)二進(jìn)制對稱信道的輸入概率空間為1718連續(xù)信源的熵為定義的熵在形式上和離散信源相似。連續(xù)信源熵并不是實(shí)際信源輸出的信息量(絕對熵)； Hc(X) 也稱為相對熵連續(xù)信源的信息量為無限大；Hc(X) 已不能代表信源的平均不確定度，也不能代表連續(xù)信源輸出的信息量。19限峰值的最大熵定理:若信源的N維隨機(jī)變量的取值在一定的范圍之內(nèi)，則在有限的定義域內(nèi)，均勻分布的連續(xù)信源具有最大熵。限平均功率的最大熵定理：若信源輸出信號的平均功率P或方差受限，則其輸出信號幅度的概率密度

7、函數(shù)為高斯分布時(shí)，信源具有最大熵值。限均值的最大連續(xù)熵定理：若連續(xù)信源X輸出非負(fù)信號的均值受限，則其輸出信號幅度呈指數(shù)分布時(shí)，連續(xù)信源X具有最大熵值。20 離散信源的無失真編碼實(shí)質(zhì)上是一種統(tǒng)計(jì)匹配編碼。信息論指出信源中的統(tǒng)計(jì)多余度主要決定于以下兩個(gè)主要因素： 一是消息概率分布的非均勻性，另一個(gè)是消息間的相關(guān)性。對無記憶信源主要決定于概率分布的非均勻性，但是，對于有記憶信源，兩者都起作用，且后者相關(guān)性更加重要。第3章 信源編碼21Def. 可達(dá)速率：對于給定的信源和編碼速率R及任意0，若存在L0、()、D()，使當(dāng)碼長LL0時(shí)，PeH(U)，則R是可達(dá)的；若RH(U)契比雪夫不等式的右邊是理論上

8、的誤碼率的上限，必須小于給定的誤碼率才能保證到達(dá)編碼性能要求24定長編碼定理 其中差錯(cuò)率滿足如下式子25 凡是能載荷一定的信息量,且碼字的平均長度最短,可分離的變長碼的碼字集合就稱為最佳變長碼. 必須將概率大的信息符號以短的碼字, 將概率小的信息符號以長的碼字.主要有:香農(nóng)-費(fèi)諾(Shannon-Fano),哈夫曼(Huffman)編碼等唯一可譯性的兩種解決方法Def.逗點(diǎn)碼Def.異字頭碼262香農(nóng)費(fèi)諾編碼費(fèi)諾編碼步驟如下：a.將概率按從大到小的順序排列，令b.按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接近或相等。c.給每一組分配一位碼元。d.將每一分組再按同樣原則劃分，重復(fù)步驟b和c，直至概

9、率不再可分為止。273 哈夫曼編碼a.將信源符號按概率從大到小的順序排列，令b.給兩個(gè)概率最小的信源符號p(xn-1)和p(xn)各分配一個(gè)碼位0和1，將這兩個(gè)符號合并成一個(gè)新符號，其概率之和作為新符號的概率，得到(n1)個(gè)符號。c.將縮減信源符號按概率排列，重復(fù)步驟a,b。直至縮減信源只剩兩個(gè)符號為止。d.從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應(yīng)的碼字。注意3進(jìn)制編碼？284 算術(shù)編碼算術(shù)編碼是計(jì)算序列的累計(jì)分布，用累計(jì)分布值表示序列，所以稱為算術(shù)編碼以二元信源輸出序列的編碼為例01110P(0) P(1)F(0)F(1)P(00)P(01)F(01)P(010)P

10、(011)F(011)P(0110)P(0111)F(0111)P(01110)P(01111)F(01111)u對應(yīng)區(qū)間的寬度等于符號序列的概率29算術(shù)編碼遞推公式編碼P(u=bbbbbbaa)=0.7560.252=F(a)=0, F(b)=0.25序號uiP(ui)=HF(ui)=Gn(ui)S01001b3/41/4 =0+1*1/410.12b9/167/16 = 1/4 + 3/4 *1/410.13b27/6437/64 = 7/16 + 9/16 * 1/420.114b81/256175/256 = 37/64 + 27/64 *1/420.115b243/1024781/1

11、024=30.1116b729/40963367/4096=30.1117a729/163843367/4096=50.110118a729/655363367/4096=70.1101010H=HP(ul+1),G=G+HF(al+1)30LZ編碼利用字典編碼方法信源符號A=(a1aK)將序列分為不同的段取最短長度的連續(xù)符號構(gòu)成段，保證互不相同。先取一個(gè)符號分段，若與前面段相同，就再取一個(gè)符號，直至序列結(jié)束得到字典表，碼字由段號加后一個(gè)符號組成。單符號的碼字，段號為031LZ編碼的特點(diǎn)特點(diǎn)一 編碼效率可以接近信息熵的上限。特點(diǎn)二 不需要事先知道信源的概率分布。特點(diǎn)三 用一種巧妙的方式使用字典

12、技術(shù)。特點(diǎn)四 文件越小，壓縮比例越??；文件越大，壓縮比例越大。LZ編碼的應(yīng)用領(lǐng)域幾乎壟斷了整個(gè)通用數(shù)據(jù)壓縮領(lǐng)域，如PKZIP、WinZIP、WinRAR、gzip等壓縮工具以及ZIP、GIF、PNG等文件格式都是LZ系列算法的受益者。32 我們學(xué)習(xí)了幾種信源編碼：香農(nóng)費(fèi)諾編碼、哈夫曼編碼、游程編碼、算術(shù)編碼、LZ編碼等。 游程編碼和算術(shù)編碼是非分組編碼；游程編碼是限失真信源編碼。本章介紹的都是離散信源變長編碼。 優(yōu)點(diǎn)：提高編碼效率； 缺點(diǎn)：需要大量緩沖設(shè)備來存儲(chǔ)這些變長碼，然后再以恒定的碼率進(jìn)行傳送；如果出現(xiàn)了誤碼，容易引起錯(cuò)誤擴(kuò)散，所以要求有優(yōu)質(zhì)的信道。33信道容量 C：在信道中最大的信息傳

13、輸速率，單位是比特/符號。單位時(shí)間的信道容量 Ct：若信道平均傳輸一個(gè)符號需要 t 秒鐘，則單位時(shí)間的信道容量為 Ct 實(shí)際是信道的最大信息傳輸速率。第3章 信道容量34根據(jù)信道中所受噪聲種類的不同,可分為隨機(jī)差錯(cuò)信道和突發(fā)差錯(cuò)信道.在有記憶信道中，噪聲干擾的影響往往是前后相關(guān)的，錯(cuò)誤是成串出現(xiàn)的，一般在編碼中我們稱這類信道為突發(fā)差錯(cuò)信道。實(shí)際的衰落信道、碼間干擾信道均屬于這類信道。有些實(shí)際信道既有獨(dú)立隨機(jī)差錯(cuò),也有突發(fā)性成串差錯(cuò)，我們稱它為混合信道。35求信道容量的方法當(dāng)信道特性 p(yj|xi) 固定后，I(X;Y)隨信源概率分布 p(xi)的變化而變化。調(diào)整 p(xi)，在接收端就能獲得

14、不同的信息量。由平均互信息的性質(zhì)已知，I(X;Y) 是 p(xi) 的上凸函數(shù)，因此總能找到一種概率分布 p(xi)（即某一種信源），使信道所能傳送的信息率為最大。C 和 Ct 都是求平均互信息 I(X;Y) 的條件極大值問題，當(dāng)輸入信源概率分布 p(xi) 調(diào)整好以后， C 和 Ct 已與 p(xi) 無關(guān)，而僅僅是信道轉(zhuǎn)移概率的函數(shù)，只與信道統(tǒng)計(jì)特性有關(guān)；信道容量是完全描述信道特性的參量；信道容量是信道能夠傳送的最大信息量。36當(dāng) n=2 時(shí)的強(qiáng)對稱離散信道就是二進(jìn)制均勻信道。二進(jìn)制均勻信道 的信道容量為：二進(jìn)制均勻信道容量 曲線如圖3.2.5所示。37對稱DMC容量的計(jì)算結(jié)論 實(shí)現(xiàn)對稱D

15、MC信道容量的輸入分布為等概分布信道只關(guān)于輸入對稱的話（輸入分布為等概分布）38一般DMC的容量計(jì)算39一般DMC的容量計(jì)算這是K個(gè)未知量0, 1, , K-1 =C+logw(0), C+logw(1), , C+logw(K-1)的線性方程組，系數(shù)矩陣是可逆方陣，因此唯一解出0, 1, , K-1 40一般DMC的容量計(jì)算另一個(gè)等式： w(0)+w(1)+w(K-1)=1。于是i=C+logw(i)41積信道或獨(dú)立并行信道 C1maxI(X1,Y1)， C2maxI(X2,Y2)信道1和信道2同時(shí)傳遞消息，輸入集X=X1X2，輸出集Y=Y1Y2，轉(zhuǎn)移概率p(jj|kk)=p(j|k)p(j

16、|k)稱這樣組合成的信道為1和2的積信道或獨(dú)立并行信道信道1P(j|k)X1Y1信道2P(j|k)X2Y2積信道的容量 C=C1+C242和信道或并信道單位時(shí)間內(nèi)可以且只能隨機(jī)選用信道1和信道2中的一個(gè)，選用信道1的概率為p1，選用信道2的概率為p2， p1p21輸入空間X=X1+X2， Y=Y1+Y2，43級聯(lián)信道或串行信道信道1的輸出作為信道2的輸入（3）令自級連的次數(shù)N+，則級連信道的轉(zhuǎn)移概率矩陣趨向于信道容量趨向于0。44香農(nóng)公式當(dāng)信道容量一定時(shí)，增大信道帶寬，可以降低對信噪功率比的要求；反之，當(dāng)信道頻帶較窄時(shí)，可以通過提高信噪功率比來補(bǔ)償。當(dāng)信道頻帶無限時(shí)，其信道容量與信號功率成正比

17、。45差錯(cuò)控制的基本方式前向糾錯(cuò)(FEC)：發(fā)送端的信道編碼器將信息碼組編成具有一定糾錯(cuò)能力的碼。接收端信道譯碼器對接收碼字進(jìn)行譯碼，若傳輸中產(chǎn)生的差錯(cuò)數(shù)目在碼的糾錯(cuò)能力之內(nèi)時(shí)，譯碼器對差錯(cuò)進(jìn)行定位并加以糾正。自動(dòng)請求重發(fā)(ARQ)：用于檢測的糾錯(cuò)碼在譯碼器輸出端只給出當(dāng)前碼字傳輸是否可能出錯(cuò)的指示，當(dāng)有錯(cuò)時(shí)按某種協(xié)議通過一個(gè)反向信道請求發(fā)送端重傳已發(fā)送的碼字全部或部分。第6章 信道編碼46混合糾錯(cuò)(HEC)：是 FEC 與 ARQ 方式的結(jié)合。發(fā)端發(fā)送同時(shí)具有自動(dòng)糾錯(cuò)和檢測能力的碼組，收端收到碼組后，檢查差錯(cuò)情況，如果差錯(cuò)在碼的糾錯(cuò)能力以內(nèi)，則自動(dòng)進(jìn)行糾正。如果信道干擾很嚴(yán)重，錯(cuò)誤很多，超過

18、了碼的糾錯(cuò)能力，但能檢測出來，則經(jīng)反饋信道請求發(fā)端重發(fā)這組數(shù)據(jù)。47最佳譯碼準(zhǔn)則（最大似然譯碼）通信是一個(gè)統(tǒng)計(jì)過程，糾、檢錯(cuò)能力最終要反映到差錯(cuò)概率上。對于FEC方式，采用糾錯(cuò)碼后的碼字差錯(cuò)概率為pwe，p(C)：發(fā)送碼字C 的先驗(yàn)概率p(C/R)：后驗(yàn)概率若碼字?jǐn)?shù)為 2k，對充分隨機(jī)的消息源有p(C)=1/ 2k，所以最小化的pwe等價(jià)為最小化p(CCR )，又等價(jià)為最大化p(C=CR)；48對于 BSC 信道：最大化的 p(C=CR) 等價(jià)于最大化的 p(RC) ，最大化的p(RC) 又等價(jià)于最小化 d(R,C)，所以使差錯(cuò)概率最小的譯碼是使接收向量 R 與輸出碼字 C 距離最小的譯碼。49對給定離散無記憶信道和任意e 0，若有一種編碼速率為R 的碼，在N足夠大時(shí)，能使pee，就稱R 是可達(dá)的。 定理(Shann