信息論與編碼復(fù)習(xí)

1、課程內(nèi)容 信息論的基本問題信息的度量 無失真信源編碼定理香農(nóng)第一定理 信道編碼定理香農(nóng)第二定理 限失真信源編碼定理香農(nóng)第三定理 信源編碼 信道編碼2緒 論 1、信息論的奠基人香農(nóng)及其重要著作； 2、信息、消息、信號的區(qū)別和聯(lián)系 3、通信系統(tǒng)的模型各主要功能模塊（包括信源、信道、信宿、信源編譯碼器、信道編譯碼器）及其作用4 信息論的奠基人：香農(nóng) 信息時(shí)代的里程碑： 1948年 香農(nóng)通信的數(shù)學(xué)理論(A mathematical theory of communication)。第一次提出了信息量的概念，并應(yīng)用數(shù)理統(tǒng)計(jì)的方法來研究通信系統(tǒng)，創(chuàng)立了信息論。 三大定理 無失真信源編碼定理（第一極限定理）

2、 信道編碼定理（第二極限定理） 限失真信源編定理（第三極限定理） 5（一） 信息論的形成與發(fā)展（二）信息、消息和信號的區(qū)別與聯(lián)系 信息 是事物運(yùn)動(dòng)狀態(tài)或存在方式。6 消息是指包含有信息的語言、文字和圖像等 信號是消息的物理體現(xiàn)。 信號是信息的載荷子或載體，是物理性的。 同一信息，可以采用不同的信號形式 (比如文字、語言、圖象等）來載荷； 同一信號形式，比如 “0”與 “1”可以表達(dá)不同形式的信息，比如無與有、斷與通、低與高 (電平) 等。 在通信系統(tǒng)中，實(shí)際傳輸?shù)氖切盘?，但本質(zhì)內(nèi)容的是信息。信息包含在信號之中，信號是信息的載體。通信的結(jié)果是消除或部分消除不確定性，從而獲得信息。7（三）數(shù)字通信

3、系統(tǒng)模型8信道信源信源編碼加密信道編碼干 擾 源信宿信源解碼解密信道解碼加密密鑰解密密鑰信源、信宿和信道 信源：向通信系統(tǒng)提供消息u的人和機(jī)器。發(fā)送消息的源 信宿：信息歸宿之意，亦即收信者或用戶，是信息傳送的終點(diǎn)或目的地。 信道：傳輸信息的物理媒介 9信源編碼器與譯碼器 信源編碼器 符號轉(zhuǎn)換； 壓縮信源的冗余度,提高通信系統(tǒng)傳輸效率； 包括無失真信源編碼、限失真信源編碼。 信源譯碼器 把信道譯碼器輸出的代碼組變換成信宿所需要的消息形式，它的作用相當(dāng)于信源編碼器的逆過程10信道編碼器與譯碼器 信道編碼 提高信息傳送的可靠性。 在信源編碼器輸出的代碼組上有目的地增加一些監(jiān)督碼元,使之具有檢錯(cuò)或糾錯(cuò)

4、的能力 信道譯碼器 具有檢錯(cuò)或糾錯(cuò)的功能,它能將落在其檢錯(cuò)或糾錯(cuò)范圍內(nèi)的錯(cuò)傳碼元檢出或糾正,以提高傳輸消息的可靠性。 11信源與信息熵 熟練掌握：自信息量、離散信源熵、互信息、信息不增性的定義概念、并能進(jìn)行相關(guān)計(jì)算 熵的性質(zhì)(非負(fù)性、對稱性、確定性、香農(nóng)輔助定理、最大熵定理、條件熵小于無條件熵) p28 掌握互信息量和熵之間的關(guān)系. 離散平穩(wěn)無記憶信源X的N次擴(kuò)展信源的熵等于信源X的熵的N倍 13(一)自信息量設(shè)離散信源X，其概率空間為自信息量：某符號出現(xiàn)后提供給收信者的信息量14)(log)(iixpxI1212()()()nnxxxXp xp xp xP1()0()1iniip xp x自

5、信息量 自信息的單位的確定 在信息論中常用的對數(shù)底是2,信息量的單位為比特(bit)； 若取自然對數(shù)e,則信息量的單位為奈特(nat); 若以10為對數(shù)底,則信息量的單位為笛特(det) 15I(xi)的特性： 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)合自信息量等于它們分別的自信息量之和。1617),(log)(iixpxI)|(log)|(jijiyxpyxI)(log)(jijiyxpyxI(二)離散信源熵 離

6、散信源熵H(X) (平均不確定度/香農(nóng)熵) 定義 信源的平均不確定度，是在總體平均意義上的信源不確定度。18iiiiiixpxpxIxpXH)(log)()()()(單位為比特/符號或比特/符號序列 條件熵條件熵19)|()|()|(jiijijyxIyxpyXH(| )( ) (|)( ) ( |) ( |)( ,) ( |)jjjjijijijijijiH X Yp y H X yp y p x y I x yp x y I x y )|(log),()|(),()|(ijijjiijijjixypyxpxyIyxpXYH20 聯(lián)合熵聯(lián)合熵 聯(lián)合熵是聯(lián)合符號集合(X,Y)上的每個(gè)元素對(x

7、i,yj)的自信息量的概率加權(quán)統(tǒng)計(jì)平均值。21 聯(lián)合熵H(X,Y)表示X 和Y同時(shí)發(fā)生的不確定度。(, )( ,) ( ,)( ,)log( ,)ijijijijijijH X Yp x y I x yp x yp x y H(XY)與H(X)、H(X/Y)之間的關(guān)系 H(X,Y)H(X)H(Y|X) H(X,Y)H(Y)H(X|Y) 當(dāng)X、Y獨(dú)立時(shí)H(X,Y)H(X)H(Y)22(三)、互信息23 定義為 xi的后驗(yàn)概率與先驗(yàn)概率比值的對數(shù))()|(log);(2ijijixpyxpyxI 互信息I(xi;yj)：表示接收到某消息yj后獲得的關(guān)于事件xi的信息量。平均互信息24 互信息= 先

8、驗(yàn)不確定性后驗(yàn)不確定性 = 不確定性減少的量,( ; )()(| )(/)( ,)log( )ijiji jiI X YH XH X Yp xyp x yp x Y未知,X 的不確定度為H(X) Y已知,X 的不確定度變?yōu)镠(X |Y)(四)、平均互信息的性質(zhì)(; )( ;)I X YI Y X(; )0I X Y (; )()()( ;)( )( )I X YH XI XI Y XH YI Y25(; )( ;)I X YI Y X(; )0I X Y (; )()( ;)( )I X YH XI Y XH Yi.對稱性：ii.非負(fù)性：iii.極值性：iv.凸函數(shù)性 （1）平均互信息量I(X

9、;Y)是輸入信源概率分布 p(xi)的上凸函數(shù)研究信道容量的理論基礎(chǔ)。 （2）平均互信息量I(X;Y)是是信道轉(zhuǎn)移概率 p(yj|xi)的下凸函數(shù)研究信源的信息率失真函數(shù)的理論基礎(chǔ)。平均互信息與各類熵的關(guān)系 26)()()()|()()|()();(XYHYHXHXYHYHYXHXHYXI)()()()|()()|()()(YHXHXYHYXHYHXYHXHXYH維拉圖 27H(X|Y)H(X)H(Y)H(XY)H(Y|X)I(X;Y)()()()|()()|()();(XYHYHXHXYHYHYXHXHYXI)|()()|()()()()()|()()|()()(XYHYHYXHXHYHXH

10、XYHYXHYHXYHXHXYH（五）、數(shù)據(jù)處理定理 數(shù)據(jù)處理定理說明： 當(dāng)對信號、數(shù)據(jù)或消息進(jìn)行多級處理時(shí),每處理一次,就有可能損失一部分信息,也就是說數(shù)據(jù)處理會把信號、數(shù)據(jù)或消息變成更有用的形式，但是絕不會創(chuàng)造出新的信息,這就是所謂的信息不增原理。 28(六)、熵的性質(zhì)1.非負(fù)性 H(X)H(p1，p2，pn)0 式中等號只有在pi =1時(shí)成立。2.對稱性 H(p1，p2，pn) = H(p2，p1，pn) 例如下列信源的熵都是相等的：291231/3 1/2 1/6xxxXP 2/ 16/ 13/ 1321yyyPY6 / 13 / 12 / 1321zzzPZ3.確定性 H(X)H(p

11、1，p2，pn)0 只要信源符號中有一個(gè)符號出現(xiàn)概率為1,信源熵就等于零。4.極值性(香農(nóng)輔助定理) 對任意兩個(gè)消息數(shù)相同的信源 30niyqYxpX, 2 , 1,)()(iniiniiinqppppppHloglog),(11215.最大熵定理 離散無記憶信源輸出M個(gè)不同的信息符號,當(dāng)且僅當(dāng)各個(gè)符號出現(xiàn)概率相等時(shí)即( pi1/M)熵最大。31MMMHXH2log1,1)()()()()()|()()|(YHXHXYHYHXYHXHYXH6.條件熵小于無條件熵 信道與信道容量 熟練掌握信道容量的定義以及相關(guān)計(jì)算（包括計(jì)算信道容量以及達(dá)到信道容量時(shí)對應(yīng)的輸入概率分布） 重點(diǎn)：無干擾離散信道、對

12、稱DMC（離散無記憶）信道 33信道容量 信道容量C： 最大的信息傳輸率341)(,0)(),;(max1)(niiiapapapYXICi 單位時(shí)間的信道容量：);(max1)(YXITCiap1、無干擾離散信道 設(shè)信道的輸入X XA=a1 an,輸出YB=b1 bm信道 輸入和輸出符號之間有確定的一一對應(yīng)關(guān)系35) 3 , 2 , 1, (10)|()|(jijijibapabpjiij 由36)|(log),()|(ijijjixypyxpXYH)|(log),()|(jiijjiyxpyxpYXH 噪聲熵H(Y|X) = 0 損失熵H(X|Y) = 0)()()(YHXHYXI；nYX

13、ICiap2)(log);(max信道 多個(gè)輸入變成一個(gè)輸出(nm)3701)|(01)|(或或jijibapabp 噪聲熵H(Y|X) 0 損失熵H(X|Y) 0()( )( )I X YHYH X；)(max);(max)(YHYXICiap信道 一個(gè)輸入對應(yīng)多個(gè)輸出(nm) 接收到符號Y后,對發(fā)送的X符號是完全確定的。 噪聲熵H(Y|X) 0 損失熵H(X|Y) = 038)()(),(YHXHYXI)(max);(max)(XHYXICiap2、對稱DMC信道 對稱離散信道： 對稱性: 每一行都是由同一集q1, q2,qm的諸元素不同排列組成輸入對稱 每一列都是由p1, p2,pn集的

14、諸元素不同排列組成輸出對稱392131616121313161213131616161613131PP對稱DMC信道 若輸入符號和輸出符號個(gè)數(shù)相同,都等于n,且信道矩陣為40pnpnpnppnpnpnppP111111111 此信道稱為強(qiáng)對稱信道 (均勻信道)信道矩陣中各列之和也等于1 對稱離散信道的平均互信息為41)|()()|()()(XYHYHYXHXHYXI；niaYHabpabpabpabpapXYHiijjijijijiji, 2 , 1)|()|(log)|()|(log)|()()|(),()|()|(21mipppHaYHXYH 對稱DMC信道的容量： 42 上式是對稱離散信

15、道能夠傳輸?shù)淖畲蟮钠骄畔⒘?它只與對稱信道矩陣中行矢量p1, p2,pm 和輸出符號集的個(gè)數(shù)m有關(guān)。ijmjijmppmpppHmC121loglog),(log 強(qiáng)對稱信道的信道容量： )1,1,1 (log2npnppHnC信息率失真函數(shù) 1、概念、定義：失真函數(shù)、平均失真、允許失真度、試驗(yàn)信道 2、信息率失真函（注意與信道容量的比較 ) 3、信息率失真函數(shù)的定義域(即Dmin和Dmax）及相應(yīng)的信道轉(zhuǎn)移概率的計(jì)算441、失真函數(shù) 失真函數(shù)在信號空間中可以看作一類“距離”側(cè)度，它有性質(zhì)： 0( ,)0ijijijxyd x yxy45失真函數(shù)定義為：,(1)()0 (2)()0(3) 0

16、()minijijijijuU vVijd u vuvd u vd u v ，當(dāng) 將所有的d(xi,yj)排列起來,用矩陣表示為:46),(),(),(),(1111mnnmbadbadbadbadd失真矩陣2、平均失真 xi和yj都是隨機(jī)變量,所以失真函數(shù)d(xi,yj)也是隨機(jī)變量,限失真時(shí)的失真值只能用數(shù)學(xué)期望表示 將失真函數(shù)的數(shù)學(xué)期望稱為平均失真：( ,) ( ,)ijijijDdp u v d u v47jjiijiibadabpapD),()|()( 允許失真D：平均失真的上界 失真函數(shù)d(xi,yj)(信號空間中某類“距離” )： 描述了某個(gè)信源符號通過傳輸后失真的大小 平均失真

17、 ： 描述某個(gè)信源在某一試驗(yàn)信道傳輸下的失真大小,它對信源和信道進(jìn)行了統(tǒng)計(jì)平均,是從總體上描述整個(gè)系統(tǒng)的失真D483、試驗(yàn)信道 若平均失真度 不大于我們所允許的失真,即49DDD 則稱此為保真度準(zhǔn)則 當(dāng)信源p(xi)給定,單個(gè)符號失真度d(xi,yj) 給定時(shí),選擇不同的信道p(yj|xi), 相當(dāng)于不同的編碼方法,其所得的平均失真度不同。滿足 條件的所有轉(zhuǎn)移概率分布pij ,構(gòu)成了一個(gè)信道集合50DD |(DDabpPijD）： 稱為D失真允許的試驗(yàn)信道：滿足保真度準(zhǔn)則的試驗(yàn)信道。4、信息率失真函數(shù)R(D) R(D)： 在限定失真為D的條件下信源輸出的最小信息速率。 51),(min)(YX

18、IDRDP 在信源給定后,我們希望在滿足一定失真的情況下,使信源必須傳輸給收信者的信息傳輸率R盡可能地小。 若從接收端來著,就是在滿足保真度準(zhǔn)則下,尋找再現(xiàn)信源消息所必須獲得的最低平均信息量。即在滿足保真度準(zhǔn)則的條件下尋找平均互信息I(X,Y)的最小值。 PD是所有滿足保真度準(zhǔn)則的試驗(yàn)信道集合,因而可以在集合PD中尋找某一個(gè)信道pij,使I (X,Y)取極小值。 離散無記憶信源52ijjijijiPpbpabpabpapDRDji)()|(log)|()(min)(R(D)的定義域 率失真的定義域問題就是在信源和失真函數(shù)已知的情況下,討論允許平均失真度D的最小和最大取值問題。 由于平均失真度是

19、非負(fù)實(shí)數(shù)d(xi,yj)的數(shù)學(xué)期望,因此也是非負(fù)的實(shí)數(shù),即 的下界是0。 R(D)=0意味著不需傳輸任何消息，D越大，直至無窮大都能滿足這種情況。 Dmin Dmax為R(D)的定義域。（確界）53DD, 0Dmin 和R(Dmin)的計(jì)算 信源的最小平均失真度：54nijijiyxdxpD1min),(min)( 只有當(dāng)失真矩陣的每一行至少有一個(gè)0元素時(shí),信源的平均失真度才能達(dá)到下限值0。Dmax和R(Dmax) 選擇所有滿足R(D)0中D的最小值，定義為R(D)定義域的上限D(zhuǎn)max，即 由于I(X,Y) = 0的充要條件是X與Y統(tǒng)計(jì)獨(dú)立,即：max() 0minR DDD55)()|(ji

20、jypxypjijiijypjjijiiypyxdxpypyxdypxpDjj),()()(min),()()(min)()(maxnijiimjyxdxpD12 , 1max),()(min 平均互信息I(X;Y)： 信源的概率分布p(xi)的上凸函數(shù)。 信道傳遞概率p(yj|xi)的下凸函數(shù)。56);(max)(YXICixp 信道容量： 信息率失真函數(shù)： );(min)(YXIDRDP 假定信道固定的前提下,選擇一種試驗(yàn)信源使信息傳輸率最大。 它所反映的是信道傳輸信息的能力,是信道可靠傳送的最大信息傳輸率。 一旦找到了信道容量,它就與信源不再有關(guān),而是信道特性的參量,隨信道特性的變化而變

21、化 不同的信道其信道容量不同。57 假定信源給定的情況下,用戶可以容忍的失真度內(nèi)再現(xiàn)信源消息所必須獲得的最小平均信息量。 它反映的是信源可以壓縮的程度,是在滿足一定失真度要求下信源可壓縮的最低值。 率失真函數(shù)一旦找到,就與求極值過程中選擇的試驗(yàn)信道不再有關(guān),而只是信源特性的參量 不同的信源其R(D)不同。58： 充分利用已給信道,使傳輸?shù)男畔⒘孔畲?而發(fā)生錯(cuò)誤的概率任意小。 ： 解決在已知信源和允許失真度D的條件下,使信源必須傳送給信宿的信息率最小。即用盡可能少的碼符號盡快地傳送盡可能多的信源消息,以提高通信的有效性。59第五章 信源編碼 1、編碼的定義和分類：信源編碼、信道編碼、安全編碼 2

22、、信源編碼的目的 3、唯一可譯碼的特殊結(jié)論 4、熟練掌握三種能獲得最佳變長編碼的方法：香農(nóng)編碼、費(fèi)諾編碼、哈夫曼編碼；了解游程編碼60 實(shí)現(xiàn)的信源編碼,要求: 信源符號X1 X2Xl XL 是一一對應(yīng)的 碼字Y1 Y2Yk YK 能夠無失真或無差錯(cuò)地從Y恢復(fù)X,也就是能正確地進(jìn)行反變換或譯碼 ; 傳送Y時(shí)所需要的信息率最小信息率最小61定長編碼 只有當(dāng)K長的碼符號序列數(shù) mK大于或等于信源的符號數(shù)nL時(shí),才可能存在定長非奇異碼定長非奇異碼。 loglogLKKnnmLm或定長編碼定理由L個(gè)符號組成的、每個(gè)符號的熵為HL(X)的無記憶平穩(wěn)信源符號序列X1XlXL,可用 K個(gè)符號Y1YkYK(每個(gè)

23、符號有m種可能值)進(jìn)行定長編碼。對任意0,0,只要 則當(dāng)L足夠大時(shí),必可使譯碼差錯(cuò)小于;反之,當(dāng)時(shí),譯碼差錯(cuò)一定是有限值,而當(dāng)L足夠大時(shí),譯碼幾乎必定出錯(cuò) log(X)LKmHLlog(X)2LKmHL只要碼字所能攜帶的信息量大于信源序列輸出的信息量,則可以使傳輸幾乎無失真,條件是條件是L足夠大足夠大。反之,當(dāng) 時(shí),不可能構(gòu)成無失真的編碼,也就是不可能做一種編碼器,能使收端譯碼時(shí)差錯(cuò)概率趨于零。 時(shí),則為臨界狀態(tài)臨界狀態(tài),可能無失真,也可能有失真。_()LKHX_()LKHX變長編碼定理 單個(gè)符號變長編碼定理：單個(gè)符號變長編碼定理： 若一離散無記憶信源的符號熵為H(X),每個(gè)信源符號用m進(jìn)制碼

24、元進(jìn)行變長編碼,一定存在一種無失真編碼方法,其碼字平均長度滿足下列不等式:()()1 loglogLH XH XKmm變長編碼定理 離散平穩(wěn)無記憶序列變長編碼定理離散平穩(wěn)無記憶序列變長編碼定理 對于平均符號熵為HL(X)的離散平穩(wěn)無記憶信源,必存在一種無失真編碼方法,使平均信息率 滿足不等式 K()(X) LLHXKH 編碼效率的下界下界： ()()log()LLLHXHXmKHXL5.2.3 最佳變長編碼 最佳碼： 對于某一信源和某一碼符號集來說,若有一唯一可譯碼,其平均碼長平均碼長小于所有其他唯一可譯碼的平均長度。 香農(nóng)（Shannon） 費(fèi)諾（Fano） 哈夫曼（Huffma ）哈夫曼編

25、碼的步驟 將信源消息符號按其出現(xiàn)的概率大小依次排列 p(x1)p(x2) p(xn)取兩個(gè)概率最小的字母分別配以0和1兩碼元,并將這兩個(gè)概率相加作為一個(gè)新字母的概率,與未分配的二進(jìn)符號的字母重新排隊(duì)。 對重排后的兩個(gè)概率最小符號重復(fù)步驟的過程。不斷繼續(xù)上述過程,直到最后兩個(gè)符號配以0和1為止。 從最后一級開始,向前返回得到各個(gè)信源符號所對應(yīng)的碼元序列,即相應(yīng)的碼字。哈夫曼的編法并不惟一。每次對縮減信源兩個(gè)概率最小的符號分配“0”和“1”碼元是任意的,所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性,即能得到可分離碼字。不同的碼元分配,得到的具體碼字不同,但碼長Ki不變,平均碼長也

26、不變,所以沒有本質(zhì)區(qū)別；縮減信源時(shí),若合并后的新符號概率與其他符號概率相等,從編碼方法上來說,這幾個(gè)符號的次序可任意排列,編出的碼都是正確的,但得到的碼字不相同。不同的編法得到的碼字長度Ki也不盡相同。 在哈夫曼編碼過程中,對縮減信源符號按概率由大到小的順序重新排列時(shí),應(yīng)使合并后的新符號新符號盡可能排在靠前排在靠前的位置,這樣可使合并后的新符號重復(fù)編碼次數(shù)減少,使短碼得到充分利用。71香農(nóng)碼、費(fèi)諾碼、哈夫曼碼都考慮了信源的統(tǒng)計(jì)特性,使經(jīng)常出現(xiàn)的信源符號對應(yīng)較短的碼字,使信源的平均碼長縮短,從而實(shí)現(xiàn)了對信源的壓縮；香農(nóng)碼有系統(tǒng)的、惟一的編碼方法,但在很多情況下編碼效率不是很高；費(fèi)諾碼和哈夫曼碼的

27、編碼方法都不惟一；費(fèi)諾碼比較適合于對分組概率相等或接近的信源編碼 ；對信源的統(tǒng)計(jì)特性沒有特殊要求,編碼效率比較高,對編碼設(shè)備的要求也比較簡單,因此綜合性能優(yōu)于香農(nóng)碼和費(fèi)諾碼。限失真信源編碼定理 設(shè)離散無記憶信源X的信息率失真函數(shù)為R(D) , 當(dāng)信息率 RR(D)時(shí),只要信源序列長度 L 足夠長,一定存在一種編碼方法,其譯碼失真小于或等于 D+,為任意小的正數(shù)； 反之,若RR(D) ,則無論采用什么樣的編碼方法,其譯碼失真必大于D。常用信源編碼方法 游程編碼 算術(shù)編碼 預(yù)測編碼 變換編碼74第六章 信道編碼 1、信道編碼的目的 2、糾錯(cuò)碼的分類：不同的分類標(biāo)準(zhǔn)，得到不同的分類，3、從編碼定理的

28、公式出發(fā)分析使得差錯(cuò)概率盡可能小可以采取的措施 4、掌握兩種譯碼方法：最優(yōu)譯碼和最大似然譯碼方法 5、了解如下線性分組碼的相關(guān)概念：線性分組碼的生成矩陣、校驗(yàn)矩陣、伴隨式和標(biāo)準(zhǔn)陣列譯碼 6、了解特殊的線性分組碼的特性 循環(huán)碼、漢明碼75第六章 信道編碼 在通信系統(tǒng)中，要提高信息傳輸?shù)挠行杂行?，我們將信源的輸出?jīng)過信源編碼信源編碼用較少的符號來表達(dá)信源消息，這些符號剩余度很小，效率很高，但對噪聲干擾的抵抗能力很弱。 為了提高信息傳輸?shù)臏?zhǔn)確性，使其具有較好的抵抗信道中噪聲干擾的能力，需要進(jìn)行信道編碼信道編碼。信道編碼定理 上界僅與信道有關(guān)，與編碼方式無關(guān)77信道編碼定理 正定理：只要傳信率R小

29、于信道容量C，總存在一種信道碼（及解碼器），可以以所要求的任意小的差錯(cuò)概率實(shí)現(xiàn)可靠的通信。 逆定理：信道容量C是可靠通信系統(tǒng)傳信率R的上邊界，如果R C，就不可能有任何一種編碼能使差錯(cuò)概率任意小。 最佳譯碼，也叫最大后驗(yàn)概率譯碼(MAP) 最大似然譯碼( MLD) cmax (c /r)iiP cmax(r/c )iiP 線性分組碼 c m G 1n 1k kn 碼字 消息 生成矩陣 Ggk-1g1g0T，有k個(gè)(1n)行矢量線性分組碼的形成 c = mk-1 gk-1+ m1 g1+m0 g0 Ggk-1g1g0T 當(dāng)信息元確定后，碼字僅由G矩陣決定，因此我們稱這kn 矩陣G為該(n,k)線性分組碼的生成矩陣。 系統(tǒng)形式(1)(1)(1)1(1)01(1)11100(1)0100100010 ; 0001kn kkkn kn kpppGI Ppppppp 系統(tǒng)形式生成的碼字c前k位由單位矩陣Ik決定，等于把信息組m原封不動(dòng)搬到碼字的前k位；其余的n-k位叫冗余位或一致校驗(yàn)位，是前k個(gè)信息位的線性組合。這樣生成的（n,k）碼叫做系統(tǒng)碼。若生成矩陣G不具備系統(tǒng)形式，則生成的碼叫做非系統(tǒng)碼。系統(tǒng)化不改變碼集，只是改變了映射規(guī)則。 空間構(gòu)成 n維n重空間有相互正交的n個(gè)基底 選擇k個(gè)基底構(gòu)成碼空間C 選擇另外的(n-k)個(gè)基底構(gòu)成空間D C和D是對偶 GHT=0