總復習1概論2信源及信息熵3信源編碼4信道及信道容量5信道編碼6信息率失真函數(shù)7考試情況1信息論總復習_new信息與消息和信號的區(qū)別消息：是指包含有信息的語言、文字和圖像等，可表達客觀物質運動和主觀思維活動的狀態(tài)。信號：把消息變換成適合信道傳輸?shù)奈锢砹?，這種物理量稱為信號（如電信號、光信號、聲音信號等）。信息是事物運動狀態(tài)和狀態(tài)改變的方式。第1章概論2信息論總復習_new信息信息是事物運動狀態(tài)和狀態(tài)改變的方式。研究信息論的目的：它的主要目的是提高信息系統(tǒng)的可靠性、有效性和安全性以便達到系統(tǒng)最優(yōu)化。在通信系統(tǒng)中形式上傳輸?shù)氖窍?，但實質上傳輸?shù)氖切畔ⅰＯ⒅皇潜磉_信息的工具，載荷信息的客體。3信息論總復習_new編碼器信宿信道消息干擾消息通信系統(tǒng)模型信源信號解碼器信號+干擾噪聲源信息論的研究對象:通信系統(tǒng)模型.信源信道加密信源信道解密通信系統(tǒng)的基本任務要求可靠:要使信源發(fā)出的消息經(jīng)過傳輸后，盡可能準確地、不失真或限定失真地再現(xiàn)在接收端有效:用盡可能短的時間和盡可能少的設備來傳輸最大的消息4信息論總復習_new單符號離散信源自信息量用概率測度定義信息量，設離散信源X，其概率空間為如果知道事件xi已發(fā)生，則該事件所含有的自信息定義為第2章信源熵5信息論總復習_new聯(lián)合自信息量當X和Y相互獨立時，p(xiyj)=p(xi)p(yj)6信息論總復習_new條件自信息量：已知yj

的條件下xi

仍然存在的不確定度。自信息量、條件自信息量和聯(lián)合自信息量之間的關系7信息論總復習_new互信息量：yj對xi的互信息量定義為的后驗概率與先驗概率比值的對數(shù)。兩個不確定度之差是不確定度被消除的部分，即等于自信息量減去條件自信息量。8信息論總復習_new平均信息量—信源熵：自信息的數(shù)學期望。也稱為信源的信息熵/信源熵/熵。信息熵的意義：信源的信息熵H是從整個信源的統(tǒng)計特性來考慮的。它是從平均意義上來表征信源的總體特性的。對于某特定的信源，其信息熵是唯一的。不同的信源因統(tǒng)計特性不同，其熵也不同。9信息論總復習_new條件熵：是在聯(lián)合符號集合XY上的條件自信息的數(shù)學期望。聯(lián)合熵H(XY)：表示輸入隨機變量X，經(jīng)信道傳輸?shù)竭_信宿，輸出隨機變量Y。即收、發(fā)雙方通信后，整個系統(tǒng)仍然存在的不確定度。10信息論總復習_new信道疑義度—H(X|Y)：表示信宿在收到Y后，信源X仍然存在的不確定度。是通過有噪信道傳輸后引起的信息量的損失，故也可稱為損失熵。噪聲熵—H(Y|X)：表示在已知X的條件下，對于符號集Y尚存在的不確定性，這完全是由于信道中噪聲引起的。唯一確定信道噪聲所需要的平均信息量。11信息論總復習_new平均互信息量定義：互信息量I(xi;yj)在聯(lián)合概率空間P(XY)中的統(tǒng)計平均值。從一個事件獲得另一個事件的平均互信息需要消除不確定度，一旦消除了不確定度，就獲得了信息。12信息論總復習_new熵H(X)H(X)>=H(X|Y)H(X)=H(X|Y)+I(X;Y)XY條件熵H(X|Y)H(X|Y)=H(XY)-H(Y)=H(X)-I(X;Y)XY聯(lián)合熵H(XY)=H(YX)H(XY)=H(X)+H(Y|X)=H(X|Y)+H(Y|X)+I(X;Y)XY平均互信息I(X;Y)=I(Y;X)I(X;Y)=H(X)-H(X|Y)=H(X)+H(Y)-H(X,Y)XY平均互信息和熵的關系13信息論總復習_new數(shù)據(jù)處理定理（信息不增原理）當消息通過多級處理器時,隨著處理器數(shù)目的增多,輸入消息和輸出消息之間的平均互信息量趨于變小。信息不增I(X;Z)≥I(X;f(Z))=I(X;Y)H(X|Z)≤H(X|f(Z))=H(X|Y)14信息論總復習_new最大離散熵定理(極值性)：離散無記憶信源輸出n個不同的信息符號，當且僅當各個符號出現(xiàn)概率相等時(即p(xi)=1/n)，熵最大。H[p(x1),p(x2),…,p(xn)]≤logn15信息論總復習_new二進制信源的熵函數(shù)H(p)為16信息論總復習_newBSC信道的平均互信息量設二進制對稱信道的輸入概率空間為17信息論總復習_new18信息論總復習_new連續(xù)信源的熵為定義的熵在形式上和離散信源相似。連續(xù)信源熵并不是實際信源輸出的信息量(絕對熵)；Hc(X)也稱為相對熵連續(xù)信源的信息量為無限大；Hc(X)已不能代表信源的平均不確定度，也不能代表連續(xù)信源輸出的信息量。19信息論總復習_new限峰值的最大熵定理:若信源的N維隨機變量的取值在一定的范圍之內(nèi)，則在有限的定義域內(nèi)，均勻分布的連續(xù)信源具有最大熵。限平均功率的最大熵定理：若信源輸出信號的平均功率P或方差受限，則其輸出信號幅度的概率密度函數(shù)為高斯分布時，信源具有最大熵值。限均值的最大連續(xù)熵定理：若連續(xù)信源X輸出非負信號的均值受限，則其輸出信號幅度呈指數(shù)分布時，連續(xù)信源X具有最大熵值。20信息論總復習_new離散信源的無失真編碼實質上是一種統(tǒng)計匹配編碼。信息論指出信源中的統(tǒng)計多余度主要決定于以下兩個主要因素：一是消息概率分布的非均勻性，另一個是消息間的相關性。對無記憶信源主要決定于概率分布的非均勻性，但是，對于有記憶信源，兩者都起作用，且后者相關性更加重要。第3章信源編碼21信息論總復習_newDef.可達速率：對于給定的信源和編碼速率R及任意δ>0，若存在L0、ξ(

)、D(

)，使當碼長L>L0時，Pe<δ，就稱R是可達的，否則R是不可達的。22信息論總復習_newTh.若R>H(U)，則R是可達的；若R<H(U)，則R是不可達的。對于給定的離散無記憶信源，若D元碼的速率R超過信源的熵，即NlogD/L≥H（U）+ε，則存在編碼方法，當L足夠大時能使譯碼錯誤概率任意小。logD：一個碼符號所能載荷的最大信息量。

H(U)：信源輸出一個符號所給出的信息量。

H(U)/logD：每個信源符號所需的最小的碼符號數(shù)——以等長碼實現(xiàn)源編碼時的理論極限。23信息論總復習_new離散無記憶信源的等長編碼譯碼錯誤概率

pe契比雪夫不等式信源序列中每個符號含有信息量的算術平均值I(ak)的方差I(ak)的數(shù)學期望無擾編碼定理的含義R>H(U)契比雪夫不等式的右邊是理論上的誤碼率的上限，必須小于給定的誤碼率才能保證到達編碼性能要求24信息論總復習_new定長編碼定理其中差錯率滿足如下式子25信息論總復習_new凡是能載荷一定的信息量,且碼字的平均長度最短,可分離的變長碼的碼字集合就稱為最佳變長碼.

必須將概率大的信息符號以短的碼字,將概率小的信息符號以長的碼字.主要有:香農(nóng)-費諾(Shannon-Fano),哈夫曼(Huffman)編碼等唯一可譯性的兩種解決方法Def.逗點碼Def.異字頭碼26信息論總復習_new2香農(nóng)費諾編碼費諾編碼步驟如下：a.將概率按從大到小的順序排列，令b.按編碼進制數(shù)將概率分組，使每組概率盡可能接近或相等。c.給每一組分配一位碼元。d.將每一分組再按同樣原則劃分，重復步驟b和c，直至概率不再可分為止。27信息論總復習_new3哈夫曼編碼a.將信源符號按概率從大到小的順序排列，令b.給兩個概率最小的信源符號p(xn-1)和p(xn)各分配一個碼位0和1，將這兩個符號合并成一個新符號，其概率之和作為新符號的概率，得到(n－1)個符號。c.將縮減信源符號按概率排列，重復步驟a,b。直至縮減信源只剩兩個符號為止。d.從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應的碼字。注意3進制編碼？28信息論總復習_new4算術編碼算術編碼是計算序列的累計分布，用累計分布值表示序列，所以稱為算術編碼以二元信源輸出序列的編碼為例01110P(0)P(1)F(0)F(1)P(00)P(01)F(01)P(010)P(011)F(011)P(0110)P(0111)F(0111)P(01110)P(01111)F(01111)u對應區(qū)間的寬度等于符號序列的概率29信息論總復習_new算術編碼遞推公式編碼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/1024=…30.1116b729/40963367/4096=…30.1117a729/163843367/4096=…50.110118a729/655363367/4096=…70.1101010H=HP(ul+1),G=G+HF(al+1)30信息論總復習_newLZ編碼利用字典編碼方法信源符號A=(a1…aK)將序列分為不同的段取最短長度的連續(xù)符號構成段，保證互不相同。先取一個符號分段，若與前面段相同，就再取一個符號，直至序列結束得到字典表，碼字由段號加后一個符號組成。單符號的碼字，段號為031信息論總復習_newLZ編碼的特點特點一編碼效率可以接近信息熵的上限。特點二不需要事先知道信源的概率分布。特點三用一種巧妙的方式使用字典技術。特點四文件越小，壓縮比例越??；文件越大，壓縮比例越大。LZ編碼的應用領域幾乎壟斷了整個通用數(shù)據(jù)壓縮領域，如PKZIP、WinZIP、WinRAR、gzip等壓縮工具以及ZIP、GIF、PNG等文件格式都是LZ系列算法的受益者。32信息論總復習_new我們學習了幾種信源編碼：香農(nóng)費諾編碼、哈夫曼編碼、游程編碼、算術編碼、LZ編碼等。游程編碼和算術編碼是非分組編碼；游程編碼是限失真信源編碼。本章介紹的都是離散信源變長編碼。

優(yōu)點：提高編碼效率；

缺點：需要大量緩沖設備來存儲這些變長碼，然后再以恒定的碼率進行傳送；如果出現(xiàn)了誤碼，容易引起錯誤擴散，所以要求有優(yōu)質的信道。33信息論總復習_new信道容量C：在信道中最大的信息傳輸速率，單位是比特/符號。單位時間的信道容量Ct：若信道平均傳輸一個符號需要t秒鐘，則單位時間的信道容量為

Ct實際是信道的最大信息傳輸速率。第3章信道容量34信息論總復習_new根據(jù)信道中所受噪聲種類的不同,可分為隨機差錯信道和突發(fā)差錯信道.在有記憶信道中，噪聲干擾的影響往往是前后相關的，錯誤是成串出現(xiàn)的，一般在編碼中我們稱這類信道為突發(fā)差錯信道。實際的衰落信道、碼間干擾信道均屬于這類信道。有些實際信道既有獨立隨機差錯,也有突發(fā)性成串差錯，我們稱它為混合信道。35信息論總復習_new求信道容量的方法當信道特性p(yj|xi)固定后，I(X;Y)隨信源概率分布p(xi)的變化而變化。調(diào)整p(xi)，在接收端就能獲得不同的信息量。由平均互信息的性質已知，I(X;Y)是p(xi)的上凸函數(shù)，因此總能找到一種概率分布p(xi)（即某一種信源），使信道所能傳送的信息率為最大。C和Ct都是求平均互信息I(X;Y)的條件極大值問題，當輸入信源概率分布p(xi)調(diào)整好以后，C和Ct已與p(xi)無關，而僅僅是信道轉移概率的函數(shù)，只與信道統(tǒng)計特性有關；信道容量是完全描述信道特性的參量；信道容量是信道能夠傳送的最大信息量。36信息論總復習_new當n=2時的強對稱離散信道就是二進制均勻信道。二進制均勻信道的信道容量為：二進制均勻信道容量曲線如圖3.2.5所示。37信息論總復習_new對稱DMC容量的計算結論

實現(xiàn)對稱DMC信道容量的輸入分布為等概分布信道只關于輸入對稱的話（輸入分布為等概分布）38信息論總復習_new一般DMC的容量計算39信息論總復習_new一般DMC的容量計算這是K個未知量{β0,β1,…,βK-1}={C+logw(0),C+logw(1),…,C+logw(K-1)}的線性方程組，系數(shù)矩陣是可逆方陣，因此唯一解出{β0,β1,…,βK-1}40信息論總復習_new一般DMC的容量計算另一個等式：

w(0)+w(1)+…+w(K-1)=1。于是βi=C+logw(i)41信息論總復習_new積信道或獨立并行信道C1＝maxI(X1,Y1)，C2＝maxI(X2,Y2)信道1和信道2同時傳遞消息，輸入集X=X1×X2，輸出集Y=Y1×Y2，轉移概率p(jj’|kk’)=p(j|k)p(j’|k’)稱這樣組合成的信道為1和2的積信道或獨立并行信道信道1P(j|k)X1Y1信道2P(j‘|k’)X2Y2積信道的容量C=C1+C242信息論總復習_new和信道或并信道單位時間內(nèi)可以且只能隨機選用信道1和信道2中的一個，選用信道1的概率為p1，選用信道2的概率為p2，p1＋p2＝1輸入空間X=X1+X2，Y=Y1+Y2，43信息論總復習_new級聯(lián)信道或串行信道信道1的輸出作為信道2的輸入（3）令自級連的次數(shù)N→+∞，則級連信道的轉移概率矩陣趨向于信道容量趨向于0。44信息論總復習_new香農(nóng)公式當信道容量一定時，增大信道帶寬，可以降低對信噪功率比的要求；反之，當信道頻帶較窄時，可以通過提高信噪功率比來補償。當信道頻帶無限時，其信道容量與信號功率成正比。45信息論總復習_new差錯控制的基本方式前向糾錯(FEC)：發(fā)送端的信道編碼器將信息碼組編成具有一定糾錯能力的碼。接收端信道譯碼器對接收碼字進行譯碼，若傳輸中產(chǎn)生的差錯數(shù)目在碼的糾錯能力之內(nèi)時，譯碼器對差錯進行定位并加以糾正。自動請求重發(fā)(ARQ)：用于檢測的糾錯碼在譯碼器輸出端只給出當前碼字傳輸是否可能出錯的指示，當有錯時按某種協(xié)議通過一個反向信道請求發(fā)送端重傳已發(fā)送的碼字全部或部分。第6章信道編碼46信息論總復習_new混合糾錯(HEC)：是FEC與ARQ方式的結合。發(fā)端發(fā)送同時具有自動糾錯和檢測能力的碼組，收端收到碼組后，檢查差錯情況，如果差錯在碼的糾錯能力以內(nèi)，則自動進行糾正。如果信道干擾很嚴重，錯誤很多，超過了碼的糾錯能力，但能檢測出來，則經(jīng)反饋信道請求發(fā)端重發(fā)這組數(shù)據(jù)。47信息論總復習_new最佳譯碼準則（最大似然譯碼）通信是一個統(tǒng)計過程，糾、檢錯能力最終要反映到差錯概率上。對于FEC方式，采用糾錯碼后的碼字差錯概率為pwe，p(C)：發(fā)送碼字C的先驗概率p(C/R)：后驗概率若碼字數(shù)為2k，對充分隨機的消息源有p(C)=1/2k，所以最小化的pwe等價為最小化p(C’≠C│R)，又等價為最大化p(C’=C│R)；48信息論總復習_new對于BSC信道：最大化的p(C’=C│R)等價于最大化的p(R│C)，最大化的p(R│C)又等價于最小化d(R,C)，所以使差錯概率最小的譯碼是使接收向量R與輸出碼字C’距離最小的譯碼。49信息論總復習_new對給定離散無記憶信道和任意e>0，若有一種編碼速率為R的碼，在N足夠大時，能使pe<e，就稱R是可達的。定理(Shannon信道編碼定理)，給定容量為C的離散無記憶信道{X，p(x|y)，Y}，若編碼速率R<C，則R是可達的。50信息論總復習_new線性分組碼碼字重量：碼字中非0碼元符號的個數(shù)，漢明重量。在二元線性碼中，碼字重量是碼字中含“1”的個數(shù)。漢明距離：在(n,k)分組碼中，兩個碼字U、V之間對應碼元位上符號取值不同的個數(shù)。最小距離dmin：任意兩個碼字間距離最小值.線性分組碼：ci,cj是GF(q)上(n,k)分組碼中的兩個碼字,a,bGF(q)上兩個元素,如果aci+bcj也是一個碼字,稱碼為線性分組碼。(包含全0碼字)51信息論總復習_new生成矩陣線性系統(tǒng)分組碼:通過行初等變換，將G化為前k列是單位子陣的標準形式

線性系統(tǒng)分組碼：用標準生成矩陣Gk×n編成的碼字，這種信息數(shù)字(k位)在前,校驗數(shù)字(r=n－k位)在后的線性分組碼稱為線性系統(tǒng)分組碼。kbit信息位(n-k)bit校驗位52信息論總復習_new校驗矩陣53信息論總復習_new1.最小距離與糾錯能力：(n,k)線性碼能糾t個錯誤的充要條件是碼的最小距離為54信息論總復習_new伴隨式和錯誤檢測①用監(jiān)督矩陣編碼，也用監(jiān)督矩陣譯碼：接收到一個接收字R后，校驗H

RT=0T是否成立：若關系成立，則認為R是一個碼字；否則判為碼字在傳輸中發(fā)生了錯誤；②伴隨式/監(jiān)督子/校驗子：S=R

HT或ST=H

RT。③如何糾錯？設發(fā)送碼矢C=(Cn－1,Cn－2,…,C0)信道錯誤圖樣為E=(En－1,En－2,…,E0)，其中Ei=0，表示第i位無錯；Ei=1，表示第i位有錯。i=n－1,n－2,…,0。55信息論總復習_new接收字R為

R=(Rn-1,Rn-2,…,R0)=C+E=(Cn-1+En-1,Cn-2+En-2,…,C0+E0)求接收字的伴隨式（接收字用監(jiān)督矩陣進行檢驗ST=H

RT=H

(C+E)T=H

CT+H

ET

由于H

CT=0T，所以ST=H

ET設H=(h1,h2,…,hn)，其中hi表示H的列。代入式得到56信息論總復習_new④總結伴隨式僅與錯誤圖樣有關，而與發(fā)送的具體碼字無關，即伴隨式僅由錯誤圖樣決定；伴隨式是錯誤的判別式：若S=0，則判為沒有出錯，接收字是一個碼字；若S≠0，則判為有錯。不同的錯誤圖樣具有不同的伴隨式，它們是一一對應的。對二元碼，伴隨式是H陣中與錯誤碼元對應列之和。57信息論總復習_new(1)循環(huán)碼的定義循環(huán)碼：如果(n,k)線性分組碼的任意碼矢C=(C0,C1,…,Cn-1)

的1次循環(huán)移位，所得矢量C(1)=(Cn-1,C0,…,Cn-2)

仍是一個碼字，則稱此線性碼為(n,k)循環(huán)碼。

碼多項式：為了運算的方便，將碼字的各分量作為多項式的系數(shù)，把碼矢表示成多項式，稱為碼多項式C(x)=C0+C1x+…+Cn－1xn－158信息論總復習_new定理：在(n,k)循環(huán)碼中，每個碼多項式c(x)都是生成多項式g(x)的倍式；而每個為g(x)倍式且次數(shù)小于或等于(n－1)的多項式，必是一個碼多項式。定理：循環(huán)碼的生成多項式g(x)是(xn-1)的因式，即xn-1=h(x)g(x)。反之若循環(huán)碼的多項式g(x)是(xn-1)的因式，則g(x)是生成多項式。59信息論總復習_new系統(tǒng)循環(huán)碼待編碼的消息序列表示為多項式60信息論總復習_new系統(tǒng)循環(huán)碼的編碼步驟：設g(x)為(n,k)循環(huán)碼的生成多項式，則有xn-1=h(x)g(x)，式中h(x)為k次多項式，稱h(x)的反多項式h*(x)為(n,k)循環(huán)碼的校驗多項式。61信息論總復習_new第4章信息率失真函數(shù)平均失真度信息率失真函數(shù)離散信息X：概率分布為P(X)，失真度為d(xi,yj)62信息論總復習_new信息率失真函數(shù)的性質定義域(Dmin,Dmax)：Dmin是最小允許失真度，Dmax是最大允許失真度信息率失真函數(shù)的物理意義是：對于給定信源，在平均失真不超過失真限度D的條件下，信息率容許壓縮的最小值為R(D)函數(shù)特點:下凸性,單調(diào)遞減和連續(xù)性.63信息論總復習_new對偶問題：信道容量和信息率失真函數(shù)的