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

1、2022-7-512022-7-521012101( )1( )1/101/101/10iiiXaaap ap a2()log 103.32/H Xbit pixel562()()5 10 log 101.66 10/NH XNH Xbitframe7130()4.98 10/NRH Xbit s2022-7-533012301()1()1/301/301/30jjjYbbbp bp b2( )log 304.91/H Ybit pixel()()( )8.23/H XYH XH Ybit pixel2212log 300()2.5()log 10RH XYRH X2022-7-542.18.

2、設(shè)有一個(gè)信源，它產(chǎn)生設(shè)有一個(gè)信源，它產(chǎn)生0,1序列的信息。它在任序列的信息。它在任意時(shí)間而且不論以前發(fā)生過什么符號(hào)，均按意時(shí)間而且不論以前發(fā)生過什么符號(hào)，均按P(0)=0.4，P(1)=0.6的概率發(fā)出符號(hào)。的概率發(fā)出符號(hào)。 (1)試問這個(gè)信源是否是平穩(wěn)的？試問這個(gè)信源是否是平穩(wěn)的？ (2)試計(jì)算試計(jì)算 (3)試計(jì)算試計(jì)算 H(x4)并寫出并寫出x4信源中可能有的所有符號(hào)。信源中可能有的所有符號(hào)。；及)(lim)/(),(2132XHXXXHXHNN2022-7-55解答：解答： (1)信源發(fā)出符號(hào)的概率分布與時(shí)間平移無關(guān)，信源發(fā)出符號(hào)的概率分布與時(shí)間平移無關(guān)，而且信源發(fā)出的序列之間也是彼此無

3、依賴的，因此而且信源發(fā)出的序列之間也是彼此無依賴的，因此該信源是平穩(wěn)的，而且是離散無記憶信源。該信源是平穩(wěn)的，而且是離散無記憶信源。 (2)/(97. 0)()()()/(lim)(lim)/(97. 0)()(2)(3)()()/()/(94. 16 . 0log6 . 04 . 0log4 . 02)(2)(1212112121321213222symbolbitXHXXXHXXXHXXXXHXHsymbolbitXHXHXHXXHXXXHXXXHsymbolbitXHXHNNNNNNN2022-7-56 (3)111111101101110010111010100110000111011

4、0010101000011001000010000)/(88. 3)(4)(4符號(hào)：symbolbitXHXH2022-7-572.22.一階馬爾可夫信源的狀態(tài)圖如圖一階馬爾可夫信源的狀態(tài)圖如圖2.8所示。信源所示。信源X的符號(hào)集為的符號(hào)集為0,1,2。 (1)求信源平穩(wěn)后的概率分布求信源平穩(wěn)后的概率分布P(0),P(1),P(2)； (2)求信源的熵求信源的熵H。 (3)近似認(rèn)為此信源為無記憶時(shí)，近似認(rèn)為此信源為無記憶時(shí)， 符號(hào)的概率分布為平穩(wěn)分布，符號(hào)的概率分布為平穩(wěn)分布， 求近似信源的熵求近似信源的熵H(X), 并與并與H進(jìn)行比較。進(jìn)行比較。 (4)對(duì)一階對(duì)一階馬爾可夫信源馬爾可夫信源p

5、取何值時(shí)取何值時(shí)H最大，最大， 當(dāng)當(dāng)p=0和和p=1時(shí)結(jié)果又如何。時(shí)結(jié)果又如何。2022-7-581231121311222321323331231 2 3(1)0121(/)(/)/2(/)/2(/)/2(/)(/)/2(/)/2(/)/2(/)0,1,2 ,(eeeppp eepp eepp eepp eepp eepp eepp eepp eepp eepXe e eee ep解：設(shè)由圖知一步轉(zhuǎn)移概率為這樣由三元信源得到的狀態(tài)空間和相應(yīng)的一步轉(zhuǎn)移概率構(gòu)成的一階馬爾可夫信源模型為31,1,2,3(/)1(0)/)jiijjii jeep eee且2022-7-593111112123132

6、12122232331312323331()( ) (/)1,2,3( )( ) (/)() (/)( ) (/)()( ) (/)() (/)( ) (/)( )( ) (/)() (/)( ) (/)(jijiip ep e p eejp ep e p eep ep eep ep eep ep e p eep ep eep ep eep ep e p eep ep eep ep eep e由求狀態(tài)極限概率將一步轉(zhuǎn)移概率代入上式得解方程有23331 12211221)()( )3(2)( ) (/)log(/)loglog/ijijiijp ep eHHHp e p eep eepppppb

7、it symbol 2022-7-51022(3)012( )1/3 1/3 1/3()( )log( )log 31.585()iiiXp aH Xp ap aH XH3i=1信源近似為平穩(wěn)信源，符號(hào)的概率分布趨于平穩(wěn)分布則此信源為：得-可見：2022-7-5112222(4)loglog2(1)log2(1)012/3log 31.585/00/11/HpppppHpppHppppHbit symbolpHbit symbolpHbit symbol 令，得此時(shí)，最大，且等于2022-7-5122.23.一階馬爾可夫信源的狀態(tài)圖如圖一階馬爾可夫信源的狀態(tài)圖如圖2.9所示。信源所示。信源X的

8、符號(hào)集為的符號(hào)集為0,1,2。 (1)求平穩(wěn)后信源的概率分布；求平穩(wěn)后信源的概率分布； (2)求信源的熵求信源的熵H。 (3)求當(dāng)求當(dāng)p=0和和p=1時(shí)信源的熵，時(shí)信源的熵， 并說明理由。并說明理由。2022-7-513)0(1)/(3 , 2 , 1,)/(,2 , 1 , 0)/()/(0)/(0)/()/()/()/(0)/()/(1210) 1 (31321321333231232221131211321ijijijepeejieepeeeeeeXpeeppeepeepeeppeeppeeppeepeeppeepppeee且模型為成的一階馬爾可夫信源相應(yīng)的一步轉(zhuǎn)移概率構(gòu)和得到的狀態(tài)空間

9、這樣由三元信源由圖知一步轉(zhuǎn)移概率為設(shè)解：2022-7-51431111121212222232323333313131()( ) (/)1,2,3( )( ) (/)() (/)( )()()() (/)( ) (/)()( )( )( ) (/)( ) (/)( )( )jijiip ep e p eejp ep e p eep ep eep p ep p ep ep ep eep ep eep p ep p ep ep ep eep e p eep p ep p e由求狀態(tài)極限概率將一步轉(zhuǎn)移概率代入上式得解方123331 1221111121113123121221222222232322

10、1( )()( )3(2)( ) (/)log(/)( ) (/)log(/)( ) (/)log(/)() (/)log(/)() (/)log(/)( ) (/)log(/ijijiijp ep ep eHHHp e p eep eep e p eep eep e p eep eep ep eep eep ep eep eep ep eep e 程有333323322)( ) (/)log(/)loglog( )(3)00;10;ep ep eep eeppppH ppHpH 必然事件和完全不可能事件的熵均為0，不包含任何信息2022-7-5152.25.一黑白氣象傳真圖的消息只有黑色和白

11、色兩種，一黑白氣象傳真圖的消息只有黑色和白色兩種，即信源即信源X=黑黑,白白。設(shè)黑色出現(xiàn)的概率為。設(shè)黑色出現(xiàn)的概率為P(黑黑)=0.3，白色的出現(xiàn)概率白色的出現(xiàn)概率P(白白)=0.7。 (1) 假設(shè)圖上黑白消息出現(xiàn)前后沒有關(guān)聯(lián)，求熵假設(shè)圖上黑白消息出現(xiàn)前后沒有關(guān)聯(lián)，求熵H(X)； (2) 假設(shè)消息前后有關(guān)聯(lián)，其依賴關(guān)系為假設(shè)消息前后有關(guān)聯(lián)，其依賴關(guān)系為P(白白/白白)=0.9，P(黑黑/白白)=0.1， P(白白/黑黑)=0.2，P(黑黑/黑黑)=0.8，求此一階馬爾可夫信源的熵求此一階馬爾可夫信源的熵H2 (X)； (3) 分別求上述兩種信源的剩余度，比較和的大小，分別求上述兩種信源的剩余度

12、，比較和的大小，并說明其物理意義。并說明其物理意義。2022-7-516)/(88. 07 . 0log7 . 03 . 0log3 . 0)(log)()(7 . 0)(, 3 . 0)(,) 1 (22212212121symbolbitepepXHepepeeXeeiii則”代表“白”，”代表“黑”，“設(shè)“解：2022-7-517 (2) 32)(,31)()(9 . 0)(2 . 0)/()()/()()()(1 . 0)(8 . 0)/()()/()()(2 , 1)/()()()(0)(1)/(2 , 1,)/(9 . 0)/(1 . 0)/(2 . 0)/(8 . 0)/(212

13、1222121221212111121212122211211epepepepeepepeepepepepepeepepeepepepjeepepepepepeepjieepeeeepeepeepeepjijijjijijij解方程得：則有：的狀態(tài)極限概率求數(shù)學(xué)模型)/(553. 0)/(log)/()()/(log)/()()/(log)/()()/(log)/()()/(log)/()()(222222212212122121112111221212symbolbiteepeepepeepeepepeepeepepeepeepepeepeepepXHijijiji2022-7-518 (3

14、) 度越大。平均信息量越小，冗余相關(guān)性越強(qiáng)，所提供的物理意義：信源符號(hào)的45. 0155. 01)()(112. 0188. 01)()(1112loglog)(02022001100220HXHXHHXHXHHHHnXHCh312( )0.60.4XxxP x解答：121222221121122222(1) ()log()log 0.60.737()log()log 0.41.32(/)5/6, (/)1/6, (/)3/4, (/)1/4(/)(/)( ;)loglog( )()ijjiijijI xp xbitI xp xitp yxp yxp yxp yxp xyp yxI x yp

15、xp y 可見，概率越小的事件含有的自信息越大。(2)由互信息公式： 計(jì)53164112126411212221222()()( ) (/)0.60.40.8()0.60.40.2;()()1255( ;)log0.059; ( ;)log0.26324615(;)log0.093; (;)l16jijiXp yp yp x p yxp yp yp yI x ybit I x ybitI xybit I xy 算互信息一般取第二個(gè)等式，必須先計(jì)算出滿足歸一性即+可算得：25og0.3224bit解答：222211211222111(3)()0.6log 0.60.4log 0.40.971/(

16、 )0.8log 0.80.2log 0.20.722/(/)5/6, (/)1/6, (/)3/4, (/)1/4( ) (/)(/)()(/)5/8, (ijiijjH Xbit symbolH Ybit symbolp yxp yxp yxp yxp x p yxp xyp yp xyp x (4)由公式： 可得：221222221122211/)1/2, (/)3/8, (/)1/2(/)( ) (/)log(/)0.9635/( /)( ) (/)log(/)0.7145/ijiijijijijiijyp xyp xyH X Yp x p yxp xybit symbolH YXp

17、x p yxp yxbit symbol 信道疑義度：噪聲熵：(5)接收到Y(jié)后獲得的平均互信息I(X;Y)I(X;Y)=H(X)-H(X/Y)=H(Y)-H(Y/X) 0.0075bit/symbol21331233解答：(1)已知二元對(duì)稱信道的傳遞矩陣和輸入信源的概率分布，可求出輸出Y的概率分布和后驗(yàn)概率p(y=0)=7/12;p(y=1)=5/12;p(x=0/y=0)=6/7;p(x=1/y=0)=1/7p(x=0/y=1)=3/5;p(x=1/y=1)=2/5進(jìn)一步可算得：H(X) 0.811bit/symbolH(Y/X) 0.918bit/symbol;H(X/Y) 0.749bi

18、t/symbol231( )1( )0.082CH pH 因此，I(X;Y)=H(X)-H(X/Y) 0.062bit/symbol(2)此信道為二元對(duì)稱信道，所以信道容量為bit/symbol當(dāng)輸入符號(hào)為等概率分布時(shí)信道的信息傳輸率才能達(dá)到該值。0.980.020.020.98P重要知識(shí)點(diǎn)重要知識(shí)點(diǎn)自信息的定義 根據(jù)上述條件可以從數(shù)學(xué)上證明這種函數(shù)形式是對(duì)數(shù)函數(shù)，即：1( )loglog( )( )iiiI aP aP a 自信息的含義 當(dāng)事件發(fā)生前，表示事件（符號(hào)、消息）發(fā)生的不確定性 當(dāng)事件發(fā)生后，表示該事件所提供的信息量例：求離散信源的自信息量 一次擲兩個(gè)色子，作為一個(gè)離散信源，求下列

19、事件產(chǎn)生后提供的信息量：a.僅有一個(gè)為3； b.至少有一個(gè)為4； c.兩個(gè)之和為偶數(shù)。 解：一個(gè)色子有6個(gè)符號(hào)，兩個(gè)色子的總數(shù)（信源消息數(shù)）為36。 p(a)=10/36=5/18; p(b)=11/36; p(c)=18/36=1/2; 所以I(a)=log(18/5)=1.848 (bit); I(b)=log(36/11)=1.7105 (bit); I(c)=log2=1 (bit)。離散信源數(shù)學(xué)模型 離散型的概率空間 集合X中，包含該信源所有可能輸出的消息，集合P中包含對(duì)應(yīng)消息的概率，各個(gè)消息的輸出概率總和應(yīng)該為1。 qqpppaaaxpX.)(212111 qiip信息熵的定義 對(duì)

20、消息的自信息取統(tǒng)計(jì)平均 信息熵：信源一個(gè)消息狀態(tài)所具有的平均信息量。)()(0iqiiaIap )()(iaIEXH )(log)(0iqiiapap 信息熵的含義 信源的平均不確定性 信源每個(gè)符號(hào)所攜帶的平均信息量 H(X)表示隨機(jī)變量X的隨機(jī)性 在無噪聲條件下，接受者收到一個(gè)消息所獲得的平均信息量二元信源X，其概率空間 ppxpX110)()1log()1(log)(log)()(10ppppapapXHiii 0)(, 11, 0 XHpp則則0)(, 01, 1 XHpp則則symbolbitXHpp/1)(,211,21 則則H(X)01/21p例例 3l離散隨機(jī)變量離散隨機(jī)變量X

21、X的概率空間為的概率空間為1212( )()()()nnxxxXp xp xp xP X10( )1( )1niiip xp x，記記 pi=p(xi)，則，則121()log(,.,)( )niiniH XppH p ppH pl 由于概率的完備性，即由于概率的完備性，即 ，所以，所以 實(shí)際上是實(shí)際上是 元函數(shù)。元函數(shù)。11niip( )H p(1)n 熵函數(shù)的數(shù)學(xué)特性包括熵函數(shù)的數(shù)學(xué)特性包括:(1)對(duì)稱性對(duì)稱性 （9）可加性可加性(2)確定性確定性(3)非負(fù)性非負(fù)性(4)擴(kuò)展性擴(kuò)展性(5)連續(xù)性連續(xù)性(6)遞增性遞增性(7)極值性極值性(8)上凸性上凸性定理定理： 離散無記憶信源輸出離散無

22、記憶信源輸出n個(gè)不同的信息符號(hào)，個(gè)不同的信息符號(hào)，當(dāng)且僅當(dāng)各個(gè)符號(hào)出現(xiàn)概率相等時(shí)當(dāng)且僅當(dāng)各個(gè)符號(hào)出現(xiàn)概率相等時(shí)(即即 )，熵，熵最大，即最大，即 1ipn121 11(,.,)( ,., )lognH p ppHnn nn概率的基本關(guān)系 當(dāng)X，Y獨(dú)立時(shí)，有p(x,y)=p(x)p(y)。p xyp xp yxp yp xyijijijij(,)() (/)() (/)p yp xyp xp yxjijijiinin()(,)() (/)11p xp xyp yp xyiijjmjijjm()(,)()(/)11pxyijjmin(,) 111pyxjijm(/) 11概率的基本關(guān)系p xyij

23、in(/) 11p xyp xyp xp yxijijijiin(/)(,)() (/)1 mjjijjiijyxpypyxpxyp1)/()(),()/(定義定義2.4 隨機(jī)變量隨機(jī)變量X和和Y的聯(lián)合分布為的聯(lián)合分布為p(xiyj)，則這兩，則這兩個(gè)隨機(jī)變量的聯(lián)合熵定義為：個(gè)隨機(jī)變量的聯(lián)合熵定義為： 聯(lián)合熵表示聯(lián)合熵表示對(duì)于二維隨機(jī)變量的平均不確定性。對(duì)于二維隨機(jī)變量的平均不確定性。nimjjijiyxpyxpXYH11)(log)()(定義定義2.5 隨機(jī)變量隨機(jī)變量X和和Y的條件熵定義為：的條件熵定義為：條件熵表示已知一個(gè)條件熵表示已知一個(gè)隨機(jī)變量時(shí)，對(duì)另一個(gè)隨機(jī)變隨機(jī)變量時(shí)，對(duì)另一個(gè)隨

24、機(jī)變量的平均不確定性。量的平均不確定性。ijijjiyxpyxpYXH)|(log)()|(iijjjixypyxpXYH)|(log)()|(各種熵之間的關(guān)系各種熵之間的關(guān)系 H(XY)=H(X)+H(Y|X)=H(Y)+H(X|Y) H(X|Y)H(X)，H(Y|X)H(Y) H(XY)H(X)+H(Y) 若X與Y統(tǒng)計(jì)獨(dú)立，則H(XY)=H(X)+H(Y)例例: 離散無記憶信源的離散無記憶信源的N次擴(kuò)展信源次擴(kuò)展信源離散無記憶信源為：離散無記憶信源為：X:a1,a2,a3; P(X):1/4, 1/2, 1/42次擴(kuò)展信源為：次擴(kuò)展信源為：2X:A1A9信源的信源的9個(gè)符號(hào)為：個(gè)符號(hào)為：A

25、1=a1a1A2=a1a2A3=a1a3A4=a2a1A5=a2a2A6=a2a3A7=a3a1A8=a3a2A9=a3a3第四節(jié)第四節(jié) 離散無記憶的擴(kuò)展信源離散無記憶的擴(kuò)展信源第四節(jié)第四節(jié) 離散無記憶的擴(kuò)展信源離散無記憶的擴(kuò)展信源其概率關(guān)系為其概率關(guān)系為 :A1A2A3A4A5A6A7A8A91/161/81/161/81/41/81/161/81/16計(jì)算可知計(jì)算可知2()3H Xbit()1.5H Xbit2()2()H XH X例例2-15 設(shè)某二維離散信源的原始信源的信源空間設(shè)某二維離散信源的原始信源的信源空間X=x1,x2,x3; P(X)=1/4, 1/4, 1/2, 一維條件概

26、一維條件概率為：率為：p(x1/x1)=1/2; p(x2/x1)=1/2; p(x3/x1)=0;p(x1/x2)=1/8; p(x2/x2)=3/4; p(x3/x2)=1/8;p(x1/x3)=0; p(x2/x3)=1/4; p(x3/x3)=3/4;原始信源的熵為：原始信源的熵為： H(X)=1.5 bit/符號(hào)符號(hào)條件熵：條件熵： H(X2/X1)=1.4 bit/符號(hào)符號(hào)可見：可見： H(X2/X1)p(xi=M)=1/2 I(S,S)=0.585 bit; p(xi=S/yj=S)=3/4p(xi=S)=1/2 I(S,M)=-0.415 bit; p(xi=S/yj=M)=3

27、/8P(xi=S)=1/2 I(M,S)=-1 bit p(xi=M/yj=S)=1/4C（即（即 ）時(shí)，則無論碼）時(shí)，則無論碼長(zhǎng)長(zhǎng)n多長(zhǎng)，總找不到一種編碼多長(zhǎng)，總找不到一種編碼 使信道輸出使信道輸出端的平均錯(cuò)誤譯碼概率達(dá)到任意小。端的平均錯(cuò)誤譯碼概率達(dá)到任意小。(2, )nRn6.4 有噪信道編碼定理有噪信道編碼定理2nCM log MRn 比特/碼符號(hào)比特/碼符號(hào)定理指出：定理指出：信道容量是在信道中可靠傳輸信道容量是在信道中可靠傳輸信息的最大信息傳輸率。信息的最大信息傳輸率。定理是一個(gè)存在定理，沒有給出具體的編定理是一個(gè)存在定理，沒有給出具體的編碼方法，但它有助于指導(dǎo)各種通信系統(tǒng)的設(shè)碼方

28、法，但它有助于指導(dǎo)各種通信系統(tǒng)的設(shè)計(jì)，有助于評(píng)價(jià)各種系統(tǒng)及編碼的效率。計(jì)，有助于評(píng)價(jià)各種系統(tǒng)及編碼的效率。6.4 有噪信道編碼定理有噪信道編碼定理糾錯(cuò)碼的基本思想和漢明碼糾錯(cuò)碼的基本思想和漢明碼糾錯(cuò)編碼信道編碼Ch9 Ch9 信道的糾錯(cuò)編碼信道的糾錯(cuò)編碼線性分組碼的編碼過程分為兩步：線性分組碼的編碼過程分為兩步：l把信息序列以每把信息序列以每k個(gè)碼元分組，得到信息碼組個(gè)碼元分組，得到信息碼組l編碼器按照預(yù)定的線性規(guī)則編碼器按照預(yù)定的線性規(guī)則(可由線性方程組可由線性方程組規(guī)定規(guī)定)，把信息碼組變換成，把信息碼組變換成 n 長(zhǎng)碼字。其中長(zhǎng)碼字。其中 (nk) 個(gè)監(jiān)督碼元由個(gè)監(jiān)督碼元由k個(gè)信息碼元的

29、線性運(yùn)個(gè)信息碼元的線性運(yùn)算產(chǎn)生。算產(chǎn)生。信息位信息位 k個(gè)，有個(gè)，有 2k 個(gè)不同的信息碼組，則有個(gè)不同的信息碼組，則有 2k 個(gè)碼字與它們一一對(duì)應(yīng)。個(gè)碼字與它們一一對(duì)應(yīng)。線性分組碼的編碼過程線性分組碼的編碼過程 2、線性分組碼、線性分組碼-編碼過程編碼過程cmG編碼規(guī)則的矩陣表示：編碼規(guī)則的矩陣表示： 12345121011101101cccccmm生成矩陣生成矩陣G G31211221241151212: cmmcccmccmmcmcmfcc編碼規(guī)則：編碼規(guī)則：線性分組碼的生成矩陣線性分組碼的生成矩陣監(jiān)督方程監(jiān)督方程 2、線性分組碼、線性分組碼-編碼過程編碼過程12345001110010

30、010110010ccccc T 0cHT 0Hc12314125000cccccccc3121241151212cmmcccmccmmcc監(jiān)督方程的矩陣表示：監(jiān)督方程的矩陣表示：線性分組碼的校驗(yàn)矩陣線性分組碼的校驗(yàn)矩陣 一致監(jiān)督矩陣一致監(jiān)督矩陣H 2、線性分組碼、線性分組碼-編碼過程編碼過程 1312312245637CCCCCCCCCCCCC 13123124527360000CCCCCCCCCCCCC 4561273CC CCCCCC監(jiān)督元可按下面方程組計(jì)算，求一致監(jiān)督矩陣監(jiān)督元可按下面方程組計(jì)算，求一致監(jiān)督矩陣HH、生成的生成的碼字及生成矩陣碼字及生成矩陣GG(7,3) (7,3) 線

31、性分組碼例線性分組碼例 設(shè)碼字為設(shè)碼字為C C1 1, ,C C2 2, ,C C3 3為信息元，為信息元，C C4 4 ,C C5 5 ,C C6 6 ,C C7 7為監(jiān)督元，每個(gè)碼元取為監(jiān)督元，每個(gè)碼元取0 0或或1 1 2、線性分組碼、線性分組碼-編碼舉例編碼舉例 123456710110000111010001100010001100010CCCCCCCTT0HC0CHTIQH (7,3) (7,3) 線性分組碼線性分組碼 監(jiān)督方程監(jiān)督方程 13123124527360000CCCCCCCCCCCCC 2、線性分組碼、線性分組碼-編碼舉例編碼舉例 信息碼組信息碼組 (101)(101)

32、即即C C1 1=1,=1,C C2 2=0,=0,C C3 3=1=1 代入監(jiān)督方程得：代入監(jiān)督方程得：C C4 4=0,=0,C C5 5=0,=0,C C6 6=1, =1, C C7 7=1=1 由信息碼組由信息碼組 ( (101101) ) 編出的碼字為編出的碼字為 ( (10110100110011) )。其它。其它7 7個(gè)碼字如右表。個(gè)碼字如右表。(7,3) (7,3) 線性分組碼線性分組碼 監(jiān)監(jiān)督督方方程程 1312312245637CCCCCCCCCCCCC 2、線性分組碼、線性分組碼-編碼舉例編碼舉例 4135123612711222333CCCCCCCCCCCCCCCCC

33、CC(7,3) (7,3) 線性分組碼線性分組碼 101110011100100111001321CCCC監(jiān)監(jiān)督督方方程程 1312312245637CCCCCCCCCCCCC 2、線性分組碼、線性分組碼-編碼舉例編碼舉例101110011100100111001321CCCCl令令123 ,c c cm100111001001110011101GCmG(7,3) (7,3) 線性分組碼線性分組碼 IQ 2、線性分組碼、線性分組碼-編碼舉例編碼舉例線性系統(tǒng)碼生成碼字例線性系統(tǒng)碼生成碼字例 4 710001010100111G00101100001011 1 71 44 710001010100

34、111CmG1010(1010011)00101100001011(7,4)系統(tǒng)線性碼的生成矩陣為系統(tǒng)線性碼的生成矩陣為 1 4m(1010)若，若，則則 2、線性分組碼、線性分組碼-系統(tǒng)碼系統(tǒng)碼系統(tǒng)碼的生成矩陣與校驗(yàn)矩陣系統(tǒng)碼的生成矩陣與校驗(yàn)矩陣l對(duì)于系統(tǒng)碼，對(duì)于系統(tǒng)碼，生成矩陣生成矩陣可以表示為可以表示為其中其中 為為 維矩陣，維矩陣， 為為 維單位矩陣。維單位矩陣。P()knkkkGIQIl校驗(yàn)矩陣校驗(yàn)矩陣可以表示為可以表示為=HPIQ()nkk()()nknkI其中其中 為為 維矩陣，維矩陣， 為為 維單維單位矩陣，且位矩陣，且TPQl由監(jiān)督矩陣可直接寫出它的生成矩陣由監(jiān)督矩陣可直接寫

35、出它的生成矩陣HGHGT T=0=0 2、線性分組碼、線性分組碼-系統(tǒng)碼系統(tǒng)碼系統(tǒng)碼的生成矩陣與校驗(yàn)矩陣?yán)到y(tǒng)碼的生成矩陣與校驗(yàn)矩陣?yán)阎阎?7,4)線性系統(tǒng)碼的監(jiān)督矩陣為線性系統(tǒng)碼的監(jiān)督矩陣為H (7,4)111010001110101101001 (7,4)10001010100111G00101100001011可直接寫出它的生成矩陣可直接寫出它的生成矩陣 2、線性分組碼、線性分組碼-系統(tǒng)碼系統(tǒng)碼關(guān)于碼的最小距離與糾、檢錯(cuò)能力的關(guān)系有以下結(jié)論：對(duì)關(guān)于碼的最小距離與糾、檢錯(cuò)能力的關(guān)系有以下結(jié)論：對(duì)于（于（n，k）線性分組碼，設(shè)）線性分組碼，設(shè) 為最小漢明距離，則為最小漢明距離，則mind

36、d min2e1ee2 e +1線性分組碼的糾、檢錯(cuò)能力線性分組碼的糾、檢錯(cuò)能力（）這組碼有（）這組碼有糾正糾正 e 個(gè)錯(cuò)誤的充要條件是個(gè)錯(cuò)誤的充要條件是 2、線性分組碼、線性分組碼-碼的糾檢錯(cuò)能力碼的糾檢錯(cuò)能力C1C2（）具有（）具有檢測(cè)檢測(cè)f個(gè)錯(cuò)誤的充要條件是個(gè)錯(cuò)誤的充要條件是df min1fff+1線性分組碼的糾、檢錯(cuò)能力線性分組碼的糾、檢錯(cuò)能力 2、線性分組碼、線性分組碼-碼的糾檢錯(cuò)能力碼的糾檢錯(cuò)能力C1C2（）具有（）具有糾正糾正 e個(gè)錯(cuò)誤，同時(shí)可以個(gè)錯(cuò)誤，同時(shí)可以發(fā)現(xiàn)發(fā)現(xiàn) f個(gè)錯(cuò)誤的充分個(gè)錯(cuò)誤的充分必要條件為必要條件為defmin1efe+f+1線性分組碼的糾、檢錯(cuò)能力線性分組碼的

37、糾、檢錯(cuò)能力 2、線性分組碼、線性分組碼-碼的糾檢錯(cuò)能力碼的糾檢錯(cuò)能力C1C20CHT錯(cuò)誤圖樣錯(cuò)誤圖樣 E=e1 e2 en TTTTTEHCHEHHCERHS)(2) 2) ，說明，說明R 不是碼字，傳輸過程產(chǎn)生了誤碼，并不是碼字，傳輸過程產(chǎn)生了誤碼，并且，在糾錯(cuò)范圍內(nèi)，可確定哪個(gè)碼元傳輸錯(cuò)誤。且，在糾錯(cuò)范圍內(nèi)，可確定哪個(gè)碼元傳輸錯(cuò)誤。0S S0S S錯(cuò)誤圖樣和伴隨式譯碼錯(cuò)誤圖樣和伴隨式譯碼接受序列接受序列R=C+E,其中其中C為正確的碼字為正確的碼字伴隨式伴隨式1) 1) ，說明，說明R 是一個(gè)碼字是一個(gè)碼字;ERCEEHST 2、線性分組碼、線性分組碼 2、線性分組碼、線性分組碼-譯碼過

38、程譯碼過程例例： 設(shè)設(shè)(7,3)線性分組碼的校驗(yàn)矩陣為線性分組碼的校驗(yàn)矩陣為1011000111010011000100110001Hmin3 1d 2、線性分組碼、線性分組碼譯碼例譯碼例 2、線性分組碼、線性分組碼-譯碼舉例譯碼舉例（1）正確碼字為）正確碼字為C C=(1010011) 接收序列接收序列R R=(1010011)TT101011000011110100001100010000110001011 S = HR傳輸過程中沒有誤碼，傳輸過程中沒有誤碼，=CRCR1011000111010011000100110001H 2、線性分組碼、線性分組碼譯碼例譯碼例 2、線性分組碼、線性分

39、組碼-譯碼舉例譯碼舉例（2）正確碼字為正確碼字為C C=(1010011) 接收碼字接收碼字R R=(1110011)TT111011000011110100101100010100110001111 S = HR ，第，第2位出錯(cuò)，位出錯(cuò)，= (1010011)=+CRECRET2SH(0100000)=E E1011000111010011000100110001H 2、線性分組碼、線性分組碼譯碼例譯碼例 2、線性分組碼、線性分組碼-譯碼舉例譯碼舉例（3）正確碼字為正確碼字為C C=(1010011) 接收碼字接收碼字R R=(0011011)TT001011000011110100111

40、100010100110001011 S = HR與與 中的任一列都不相同，中的任一列都不相同，TSHT142756SHHHHHH不能確定到底是哪兩位出錯(cuò)，不能正確譯碼。不能確定到底是哪兩位出錯(cuò)，不能正確譯碼。1011000111010011000100110001H 2、線性分組碼、線性分組碼譯碼例譯碼例 2、線性分組碼、線性分組碼-譯碼舉例譯碼舉例編碼C=mG計(jì)算Em輸出CER0RH TCRECnoyes輸出RERCEEHST伴隨式譯碼總結(jié)伴隨式譯碼總結(jié) 2、線性分組碼、線性分組碼 2、線性分組碼、線性分組碼-譯碼舉例譯碼舉例例例 已知生成矩陣為已知生成矩陣為GG求生成的線性分組碼及求生成的線性分組碼及一致監(jiān)督矩陣一致監(jiān)督矩陣HH 。 101110011100100111001G11101001111101001110101001110110011101000