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

1總復(fù)習(xí)1緒論2信源的信息量3離散信源4離散信源的無失真編碼5離散信道及其編碼定理6連續(xù)信道及其容量8信息率失真理論及其應(yīng)用10線性分組碼2編碼器信宿信道消息干擾消息通信系統(tǒng)模型信源信號解碼器信號+干擾噪聲源信息論的研究對象:通信系統(tǒng)模型.信源信道加密信源信道解密通信系統(tǒng)的基本任務(wù)要求可靠:要使信源發(fā)出的消息經(jīng)過傳輸后，盡可能準確地、不失真或限定失真地再現(xiàn)在接收端有效:用盡可能短的時間和盡可能少的設(shè)備來傳輸最大的消息3單符號離散信源自信息量用概率測度定義信息量，設(shè)離散信源X，其概率空間為如果知道事件xi已發(fā)生，則該事件所含有的自信息定義為信源熵4聯(lián)合自信息量當(dāng)X和Y相互獨立時，p(xiyj)=p(xi)p(yj)5條件自信息量：已知yj

的條件下xi

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

必須將概率大的信息符號以短的碼字,將概率小的信息符號以長的碼字.主要有:香農(nóng)-費諾(Shannon-Fano),哈夫曼(Huffman)編碼等唯一可譯性的兩種解決方法Def.逗點碼Def.異字頭碼212香農(nóng)費諾編碼費諾編碼步驟如下：a.將概率按從大到小的順序排列，令b.按編碼進制數(shù)將概率分組，使每組概率盡可能接近或相等。c.給每一組分配一位碼元。d.將每一分組再按同樣原則劃分，重復(fù)步驟b和c，直至概率不再可分為止。223哈夫曼編碼a.將信源符號按概率從大到小的順序排列，令b.給兩個概率最小的信源符號p(xn-1)和p(xn)各分配一個碼位0和1，將這兩個符號合并成一個新符號，其概率之和作為新符號的概率，得到(n－1)個符號。c.將縮減信源符號按概率排列，重復(fù)步驟a,b。直至縮減信源只剩兩個符號為止。d.從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應(yīng)的碼字。注意3進制編碼？23信道容量C：在信道中最大的信息傳輸速率，單位是比特/符號。單位時間的信道容量Ct：若信道平均傳輸一個符號需要t秒鐘，則單位時間的信道容量為

Ct實際是信道的最大信息傳輸速率。第3章信道容量24求信道容量的方法當(dāng)信道特性p(yj|xi)固定后，I(X;Y)隨信源概率分布p(xi)的變化而變化。調(diào)整p(xi)，在接收端就能獲得不同的信息量。由平均互信息的性質(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)計特性有關(guān)；信道容量是完全描述信道特性的參量；信道容量是信道能夠傳送的最大信息量。25當(dāng)n=2時的強對稱離散信道就是二進制均勻信道。二進制均勻信道的信道容量為：二進制均勻信道容量曲線如圖所示。26對稱DMC容量的計算結(jié)論

實現(xiàn)對稱DMC信道容量的輸入分布為等概分布信道只關(guān)于輸入對稱的話（輸入分布為等概分布）27香農(nóng)公式當(dāng)信道容量一定時，增大信道帶寬，可以降低對信噪功率比的要求；反之，當(dāng)信道頻帶較窄時，可以通過提高信噪功率比來補償。當(dāng)信道頻帶無限時，其信道容量與信號功率成正比。連續(xù)信道的容量28最佳譯碼準則（最大似然譯碼）通信是一個統(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)；信道編碼29對于BSC信道：最大化的p(C’=C│R)等價于最大化的p(R│C)，最大化的p(R│C)又等價于最小化d(R,C)，所以使差錯概率最小的譯碼是使接收向量R與輸出碼字C’距離最小的譯碼。30對給定離散無記憶信道和任意e>0，若有一種編碼速率為R的碼，在N足夠大時，能使pe<e，就稱R是可達的。定理(Shannon信道編碼定理)，給定容量為C的離散無記憶信道{X，p(x|y)，Y}，若編碼速率R<C，則R是可達的。31線性分組碼碼字重量：碼字中非0碼元符號的個數(shù)，漢明重量。在二元線性碼中，碼字重量是碼字中含“1”的個數(shù)。漢明距離：在(n,k)分組碼中，兩個碼字U、V之間對應(yīng)碼元位上符號取值不同的個數(shù)。最小距離dmin：任意兩個碼字間距離最小值.線性分組碼：ci,cj是GF(q)上(n,k)分組碼中的兩個碼字,a,bGF(q)上兩個元素,如果aci+bcj也是一個碼字,稱碼為線性分組碼。(包含全0碼字)32生成矩陣線性系統(tǒng)分組碼:通過行初等變換，將G化為前k列是單位子陣的標準形式

線性系統(tǒng)分組碼：用標準生成矩陣Gk×n編成的碼字，這種信息數(shù)字(k位)在前,校驗數(shù)字(r=n－k位)在后的線性分組碼稱為線性系統(tǒng)分組碼。kbit信息位(n-k)bit校驗位33校驗矩陣341.最小距離與糾錯能力：(n,k)線性碼能糾t個錯誤的充要條件是碼的最小距離為35伴隨式和錯誤檢測①用監(jiān)督矩陣編碼，也用監(jiān)督矩陣譯碼：接收到一個接收字R后，校驗HRT=0T是否成立：若關(guān)系成立，則認為R是一個碼字；否則判為碼字在傳輸中發(fā)生了錯誤；②伴隨式/監(jiān)督子/校驗子：S=RHT或ST=HRT。③如何糾錯？設(shè)發(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。36接收字R為

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

由于HCT=0T，所以ST=HET設(shè)H=(h1,h2,…,hn)，其中hi表示H的列。代入式得到37④總結(jié)伴隨式僅與錯誤圖樣有關(guān)，而與發(fā)送的具體碼字無關(guān)，即伴隨式僅由錯誤圖樣決定；伴隨式是錯誤的判別式：若S=0，則判為沒有出錯，接收字是一個碼字；若S≠0，則判為有錯。不同的錯誤圖樣具有不同的伴隨式，它們是一一對應(yīng)的。對二元碼，伴隨式是H陣中與錯誤碼元對應(yīng)列之和。38伴隨式譯碼(6,3)碼的標準陣陪集首伴隨式39伴隨式譯碼第l個陪集首的重量重量為i的陪集首的數(shù)量BSC下，二元線性碼正確譯碼的概率：40伴隨式譯碼譯碼步驟：計算接收矢量的伴隨式由伴隨式確定陪集首將陪集首作為錯誤圖樣e將v譯為c=v-e例：設(shè)有碼如下所示：信息碼字0000000010110110101111111010(1)找出生成矩陣G與監(jiān)督矩陣H；(2)在二元對稱信道下給出最大似然譯碼的譯碼表；(3)求正確譯碼的概率。41解：(1)42(2)

4344信息率失真函數(shù)平均失真度信息率失真函數(shù)離散信息X：概率分布為P(X)，失真度為d(xi,yj)45信息率失真函數(shù)的性質(zhì)定義域(Dmin,Dmax)：Dmin是最小允許失真度，Dmax是最大允許失真度信息率失真函數(shù)的物理意義是：對于給定信源，在平均失真不超過失真限度D的條件下，信息率容許壓縮的最小值為R(D)函數(shù)特點:下凸性,單調(diào)遞減和連續(xù)性.例：接收符號Y={1/2,1/2}求：Dmax和Dmin及達到Dmax和Dmin時的轉(zhuǎn)移概率矩陣。解：當(dāng)x1→y1,x2→y1/y2,x3→y2時，平均失真取最小值，對應(yīng)的當(dāng)X和Y統(tǒng)計獨立，即p(yj/xi)=p(yj）時，I=0,4647對偶問題：信道容量和信息率失真函數(shù)的問題，都是求平均互信息極值問題。分三個方面說明：求極值問題平均互信息I(X;Y)是信源概率分布p(xi)(i=1,2,…,n)

的上凸函數(shù)，信道容量就是在固定信道情況下，求平均互信息極大值的問題，即I(X;Y)又是信道轉(zhuǎn)移概率分布p(yj|xi)(i=1,2,…,n;j=1,2,…,m)

的