編碼chapter3

1、第三章 線性分組碼陸以勤2005年3月一、線性分組碼的一般性定義定義：通過預(yù)定的線性運(yùn)算將定義：通過預(yù)定的線性運(yùn)算將k維維q元（元（q為素?cái)?shù)冪）信息數(shù)組變換成為素?cái)?shù)冪）信息數(shù)組變換成n維維（nk)碼數(shù)組（稱碼字），由碼數(shù)組（稱碼字），由qk個(gè)碼字所成的集合，稱為個(gè)碼字所成的集合，稱為n,k線性分組碼，線性分組碼，簡(jiǎn)稱分組碼。簡(jiǎn)稱分組碼。碼字用碼字用 （cn-1, cn-2, , cn-k, cn-k-1, , c1, c0)表示。表示。碼率（傳信率，信道利用率）碼率（傳信率，信道利用率）R=k/n表示信息位所占的比重。表示信息位所占的比重。最簡(jiǎn)單的情況：在后面添加最簡(jiǎn)單的情況：在后面添加n-k

2、個(gè)監(jiān)督元，叫系統(tǒng)碼（定義個(gè)監(jiān)督元，叫系統(tǒng)碼（定義3.2.2)。cn-k-1= h1,n-1cn-1+h1,n-2cn-2+h1,n-kcn-1cn-k-2= h2,n-1cn-1+h2,n-2cn-2+h2,n-kcn-1.c0= hn-k,n-1cn-1+hn-k,n-2cn-2+hn-k,n-kcn-1h1,n-1 h1,n-2 h1,n-k 10 0 cn-1h2,n-1 h2,n-2 h2,n-k 01 0 cn-2 =0.hn-k,n-1hn-k,n-2 hn-k,n-k001 c0 HcT=0T二、線性分組碼的嚴(yán)格數(shù)學(xué)定義1.定義定義GF(q)中的元素（中的元素（q為素?cái)?shù)冪）組成的

3、為素?cái)?shù)冪）組成的(n-k) n矩陣，其秩為矩陣，其秩為n-k。滿足方程滿足方程HcT=0T的矢量的矢量c=(cn-1, cn-2, ci, ,c0) （ ci GF(q) )的集合稱為的集合稱為n,k線性分組線性分組碼。碼。H稱為監(jiān)督（檢驗(yàn)稱為監(jiān)督（檢驗(yàn))矩陣。矩陣。 HcT=0T稱為（一致）監(jiān)督矩陣。稱為（一致）監(jiān)督矩陣。為什么秩為n-k？一致：同一規(guī)則對(duì)H進(jìn)行初等變換，化為h1,n-1 h1,n-2 h1,n-k 10 0 h2,n-1 h2,n-2 h2,n-k 01 0 .hn-k,n-1hn-k,n-2 hn-k,n-k001 =Q In-k的形式，稱為H的標(biāo)準(zhǔn)形式。H稱為典型監(jiān)督矩

4、陣。二、線性分組碼的嚴(yán)格數(shù)學(xué)定義22. 定理1 (碼的封閉性）設(shè)CH為由監(jiān)督矩陣H定義的分組碼，則c1,c2CH : c1+c2CH證明： 由c1CH，得Hc1T=0T;由c2CH，得Hc2T=0T;所以 H(c1+c2)T=H(c1T+c2T) =Hc1T+Hc2T=0Tc1+c2滿足HcT=0T，所以c1+c2 CH3. 定理2n,k線性分組碼對(duì)矢量相加構(gòu)成阿貝爾群。封閉性（定理1），結(jié)合律，有恒等元和逆元。二、線性分組碼的嚴(yán)格數(shù)學(xué)定義33. 定理3n,k線性分組碼是GF(q)上的n維線性空間Vn中的一個(gè)k維子空間。證：設(shè)CH是由監(jiān)督矩陣H定義的n,k線性碼。1.先證CH為子空間。(1)C

5、H是阿貝爾群(定理2);(2)aGF(q),cCH: a c CH;(3) 分配律: c1, c2 CH, a,bGF(q): a (c1+c2)=ac1+ac2且且(a+b)c1=ac1+bc1;(4) 結(jié)合律成立: a1, a2 GF(q), cCH: (a1a2)c=a1 (a2c).2.再證維數(shù)為再證維數(shù)為k設(shè)設(shè)cCH, 則HcT=0T. c與H的每一行矢量正交, 故c在由H的行矢量張成的n-k維線性子空間Vn,n-k的零空間中(第2章定理17, 定理2.6.9), CH中每個(gè)碼字和H張成的子空間的矢量正交, 所以CH為H張成的子空間的零空間(第2章定理16, 定理2.6.8), 維數(shù)

6、為k (第2章定理18, 定理2.6.10)。二、線性分組碼的嚴(yán)格數(shù)學(xué)定義4由第2章定理3可知，必存在k個(gè)線性獨(dú)立的碼字g1, g2, , gk, 使cCH:c=mn-1g1+mn-2g2+ + mn-kgk =m Gg1,n-1 g1,n-2 g1,0 g2,n-1 g2,n-2 g2,0.gk,n-1 gk,n-2 gk,0G=G稱為n,k碼的生成矩陣。G的標(biāo)準(zhǔn)形式IkP, 稱為典型生成矩陣。基不同，G不同，但生成的空間是一樣的，不同的G的意義是什么？秩是多少？三、G與H的關(guān)系G G的行矢量是碼字，的行矢量是碼字， HgiT=0T, 有有HGT= 0T, H與與G所張成的空間互為零空間。所

7、張成的空間互為零空間。CH: H校驗(yàn)，校驗(yàn)，G生成。生成。CG: G校驗(yàn)，校驗(yàn)，H生成。生成。互為對(duì)偶碼，若互為對(duì)偶碼，若CH=CG, 則稱為自對(duì)偶碼（則稱為自對(duì)偶碼（P62)Q In-k IkPT= QIn-k IkT PTT= Q + PT = 0所以所以 P= - QT 或或 Q = -PT由此得由此得 G=Ik P = Ik QTH=Q In-k= -PT In-k三、G與H的關(guān)系2例：例： 已知已知77，33碼（碼（p52, p52, 例例3.1)3.1)1 0 1 | 1 0 0 01 1 1 | 0 1 0 01 1 0 | 0 0 1 00 1 1 | 0 0 0 1H=c=(

8、c6c5c4c3c2c1c0)由HcT=0T得c3=c6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c41 1 1 00 1 1 11 1 0 1P= -QT=G=Ik P =1 0 0 | 1 1 1 0 0 1 0 | 0 1 1 10 0 1 | 1 1 0 1三、G與H的關(guān)系3設(shè)信息組m = (m6m5m4)c6=m6c5=m5c4=m4c3=m6+m4=c6+c4c2=m6+m5+m4=c6+c5+c4c1=m6+m5=c6+c5c0=m5+m4=c5+c4考慮如何用串行方式？考慮如何用串行方式？三、G與H的關(guān)系4m4m5m6m4m5m5m6m6m6+m5m6m6m4m4

9、m5m6m6m6m6+m5m6+m5+m6=m5m6+m5m6m5+m4m5+m4m6+m5m6+m5+m4m6+m4設(shè)信息組m = (m6m5m4)c6=m6c5=m5c4=m4c3=m6+m4=c6+c4c2=m6+m5+m4=c6+c5+c4c1=m6+m5=c6+c5c0=m5+m4=c5+c4三、G與H的關(guān)系5G=1 0 0 | 1 1 1 0 0 1 0 | 0 1 1 10 0 1 | 1 1 0 1寫成多項(xiàng)式寫成多項(xiàng)式g1(x)=x6+x3+x2+x=x(x5+x2+x+1) =x(x+1)(x4+x3+x2+1)g2(x)=x5+x2+x+1=(x+1)(x4+x3+x2+1

10、)g3(x)= x4+x3+x2+1g1(x)=x6+x3+x2+x= x(x+1)(x4+x3+x2+1) =x(x+1)g3(x)g2(x)=x5+x2+x+1=(x+1)(x4+x3+x2+1) =(x+1)g3(x)c(x) =m6g1(x)+m5g2(x)+m4g3(x) =m6g1(x)+m5g2(x)+m4g3(x)=m6x(x+1)g3(x)+m5(x+1)g3+m4g3(x)=(m6x2+m6x+m5x+m5+m4)g3(x)=m(x)g3(x)所有碼字多項(xiàng)式都是所有碼字多項(xiàng)式都是g3(x)的倍式的倍式又因?yàn)槭窍到y(tǒng)碼又因?yàn)槭窍到y(tǒng)碼c(x)=m(x)xn-k + r(x) 0

11、(mod g3(x) (信息位左移信息位左移n-k位位 加上監(jiān)督位）加上監(jiān)督位）r(x) - m(x)xn-k (mod g3(x) 除法電路除法電路 （見（見168頁）頁）x6 x5x4 x3 x2x四、線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力檢、糾錯(cuò)的必要條件：碼字在一些碼元發(fā)生錯(cuò)誤后，還沒有變成其它碼字。檢、糾錯(cuò)的必要條件：碼字在一些碼元發(fā)生錯(cuò)誤后，還沒有變成其它碼字。為使碼具有強(qiáng)的檢錯(cuò)、糾錯(cuò)能力，各碼字的距離差別（漢明距離）足夠大。為使碼具有強(qiáng)的檢錯(cuò)、糾錯(cuò)能力，各碼字的距離差別（漢明距離）足夠大。線性分組碼的最小距離線性分組碼的最小距離d(最小漢明距離）最小漢明距離）若若n,k線性分組碼的

12、最小距離為線性分組碼的最小距離為d, 記為記為n,k,d定理定理4：n,k分組碼的最小距離分組碼的最小距離d滿足滿足,)(minknccwdd(c1,c2)=w(c1+c2)=w(c3)定理定理5：GF(2)上的上的n,k,d分組碼中任何碼字分組碼中任何碼字c1,c2滿足滿足: w(c1+c2) = w(c1)+w(c2)- 2(c1 c2) 內(nèi)積內(nèi)積 或或 d(c1,c2) w(c1)+w(c2)推論推論1：GF(2)上的上的n,k分組碼滿足分組碼滿足: c1,c2,c3 n,k: d(c1,c2)+d(c2,c3) d(c1,c3) c1c2c3d(c1,c2)d(c1,c3)d(c2,c

13、3)四、線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力2定理定理6：(p12定理定理1.3.1) 任一任一n,k,d，若要，若要: (1) 檢測(cè)檢測(cè)e個(gè)錯(cuò)誤，則個(gè)錯(cuò)誤，則要求要求d e+1(2) 糾正糾正t個(gè)錯(cuò)誤，則要求個(gè)錯(cuò)誤，則要求d 2t+1(3) 糾正糾正t個(gè)錯(cuò)誤，或檢測(cè)個(gè)錯(cuò)誤，或檢測(cè)e( t) 個(gè)錯(cuò)誤，個(gè)錯(cuò)誤，則要求則要求d t+e+1(4) 糾正糾正t個(gè)錯(cuò)誤和個(gè)錯(cuò)誤和 個(gè)刪除個(gè)刪除，則要求，則要求d 2t+ +1ee1tt1tttt1eett tt五、線性分組碼的譯碼1. 伴隨式伴隨式+cr=c+eeHcT=0THrT= H(c+e)T= HcT+HeT= HeT定義定義s rHT 稱為接收字

14、稱為接收字r 的伴隨式（校正子）的伴隨式（校正子）h1,n-1 h1,n-2 h1,0h2,n-1 h2,n-2 h2,0.hn-k,n-1hn-k,n-2 hn-k,0H= (hn-1, hn-2, , h1,h0 )設(shè)e = (en-1, en-2, , e1, e0 ) = (0, , ei1, , ei2, , eit , ,0 )s = eHT=0, , ei1, , ei2, , eit , ,0 hn-1Thn-2T.h1Th0T= ei1 hi1T+ +ei2 hi2T+ eit hi tT發(fā)生錯(cuò)誤的位所對(duì)應(yīng)的列發(fā)生錯(cuò)誤的位所對(duì)應(yīng)的列向量的線性組合向量的線性組合五、線性分組碼的

15、譯碼2例：7，3碼， H=101 | 1000111 | 0100110 | 0010011 | 0001s = r HT= ( r6 r5 r4 r3 r2 r1 r0 ) 101 | 1000111 | 0100110 | 0010011 | 0001Tr6 + r4 + r3r6 + r5 + r4 + r2r6 + r5 + r1r5 + r4 + r0=T= （s3 s2 s1 s0) 五、線性分組碼的譯碼3c =(1010011)e =(0100000)r =(1110011)s = r HT = e HT = (0100000) 101 | 1000111 | 0100110 |

16、 0010011 | 0001T=0111Tc =(1010011)e =(1001000)r = (0011011)s = r HT = e HT = (1001000) 101 | 1000111 | 0100110 | 0010011 | 0001T=1110T+T1000=(0110)五、線性分組碼的譯碼4若若e = (0, ,0, ei, 0, 0)s=eihiT 若為二進(jìn)制，則若為二進(jìn)制，則s =hiT 若要各列彼此區(qū)分，各列互不相同，即任意兩列線性無關(guān)若要各列彼此區(qū)分，各列互不相同，即任意兩列線性無關(guān)H(n-k)n n最多可構(gòu)成最多可構(gòu)成2 2n-kn-k-1-1個(gè)互不相同的非零

17、列，即必須保證個(gè)互不相同的非零列，即必須保證 2 2n-kn-k-1-1 n n取下限，得取下限，得2 2n-kn-k-1 -1 = n= n，即為漢明碼。，即為漢明碼。2. 漢明碼漢明碼定義定義（定義（定義3.3.1)：GF(2)上的線性分組碼上的線性分組碼n,k,d稱為漢明碼，若滿足下列條件：稱為漢明碼，若滿足下列條件： (1) n = 2 2m m-1 (m-1 (m N,N,且且m m 3)3)； (2 2) k=2k=2m m-m-1 -m-1 (3)3)n-k = m; (4) d=3。五、線性分組碼的譯碼5構(gòu)造辦法：構(gòu)造辦法：a.按按H的二進(jìn)制數(shù)的順序排列。的二進(jìn)制數(shù)的順序排列。

18、例GF(2)上的7,4,3的漢明碼，m=3， 23-1=7個(gè)非零列，3維矢量按07的二進(jìn)制數(shù)排列1 1 1 1 0 0 0 1 1 0 0 1 1 01 0 1 0 1 0 1H=b. 系統(tǒng)碼系統(tǒng)碼1 1 1 0 1 0 0 1 1 0 1 0 1 01 0 1 1 0 0 1H=五、線性分組碼的譯碼6定理定理7：若若n,k線性碼的監(jiān)督矩陣線性碼的監(jiān)督矩陣H任意任意s列線性無關(guān)，而存在列線性無關(guān)，而存在s+1列線性相列線性相關(guān)，則關(guān)，則d=s+1。反之，若。反之，若d=s+1, 則則H的任意的任意s列線性無關(guān)，而必存在有相關(guān)列線性無關(guān)，而必存在有相關(guān)的的s+1列。列。e1s1=e1 HTe2s

19、2=e2 HT若e1e2，希望，希望s1s2 .即保證e與s有一一對(duì)應(yīng)關(guān)系。設(shè)設(shè)e1= (0ei1.ei2eit) e2= (0ej1.ej2ejt) s1=ei1hi1T+ei2hi2T+eithitT s2=ej1hi1T+ej2hj2T+ejthjtT 若要若要s1s2 ，則s1-s2 =ei1hi1T+ei2hi2T+eithitT-ej1hi1T-ej2hj2T-ejthjtT 0任任2t列線性無關(guān)。列線性無關(guān)。d 2t+13. 線性分組碼的最小距離與線性分組碼的最小距離與H的關(guān)系的關(guān)系問題：?jiǎn)栴}：d=2t+1越大越好，能大到什么程度？越大越好，能大到什么程度？五、線性分組碼的譯碼6

20、問題：?jiǎn)栴}：d=2t+1越大越好，能大到什么程度？越大越好，能大到什么程度？H的秩為的秩為n-k, 有有n-k列線性無關(guān)，但任列線性無關(guān)，但任n-k+1列線性相關(guān)。列線性相關(guān)。所以所以d n-k+1 (推論推論3.3.1)取上限，得取上限，得d=n-k+1, 稱為稱為Singleton限。達(dá)到限。達(dá)到Singleton限的碼稱為極大最小限的碼稱為極大最小距離可分碼（距離可分碼（MDS)。RS碼達(dá)到此限。碼達(dá)到此限。五、線性分組碼的譯碼7由于線性分組碼由于線性分組碼n,k,d是方程是方程 HcT = 0T的解空間的解空間, 任一碼字任一碼字c滿足滿足cTH=0. 若若c經(jīng)過信道到達(dá)終端變?yōu)榻?jīng)過信

21、道到達(dá)終端變?yōu)閞 = c+e. 如沒有發(fā)生錯(cuò)誤如沒有發(fā)生錯(cuò)誤(e = 0), 則則rTH=0; 如果如果發(fā)生錯(cuò)誤即發(fā)生錯(cuò)誤即e 0, 這時(shí)有兩種情況這時(shí)有兩種情況: e n,k,d, 這時(shí)這時(shí)r n,k,d, 也就是也就是r變成了另外一個(gè)碼字變成了另外一個(gè)碼字, rTH仍等于仍等于0; e n,k,d, 這時(shí)這時(shí)rTH = cTH + eTH = eTH 0, 只與只與e有關(guān)有關(guān). 由此可見由此可見, 如果碼字間的距離足夠大以至發(fā)生了錯(cuò)誤也不會(huì)變成另一個(gè)碼如果碼字間的距離足夠大以至發(fā)生了錯(cuò)誤也不會(huì)變成另一個(gè)碼字字, 則可從則可從S = rTH判斷碼字在傳輸中是否有錯(cuò)判斷碼字在傳輸中是否有錯(cuò),錯(cuò)

22、誤的圖樣是什么錯(cuò)誤的圖樣是什么. s 稱為稱為伴隨式伴隨式. 通過伴隨式與錯(cuò)誤的圖樣的一一對(duì)應(yīng)關(guān)系來譯碼叫伴隨式譯碼通過伴隨式與錯(cuò)誤的圖樣的一一對(duì)應(yīng)關(guān)系來譯碼叫伴隨式譯碼。4. 4. 伴隨式譯碼伴隨式譯碼s計(jì)算電路計(jì)算電路se組合邏輯電路組合邏輯電路r-e電路電路rsc五、線性分組碼的譯碼85、標(biāo)準(zhǔn)陣列譯碼、標(biāo)準(zhǔn)陣列譯碼c1=0c2.ci.cj .c2ke2c2+e2.ci+e2.cj +e2.c2k+e2e3c2+e3.ci+e3.cj +e3.c2k+e3 . . . emc2+em.ci+em.cj +em.c2k+em . . . e2n-kc2+ e2n-k .ci+ e2n-k .

23、cj + e2n-k .c2k+ e2n-k最佳碼：使最佳碼：使w=w(e2)+w(e3)+w(em)+w(e2n-k) 為最小的碼為最小的碼不是唯一，不是唯一，p64表表3-3，p15表表1-2。由于由于Fq上線性碼上線性碼C= n, k是是n維矢量線性空間維矢量線性空間V的的qk階加法子群階加法子群, 故故V可劃分為可劃分為qn/qk=qn-k個(gè)個(gè)C的不同陪集的不同陪集(包括包括C). 如果第一個(gè)陪集如果第一個(gè)陪集C+e2的陪集首的陪集首e2取取V-C中重量最小者中重量最小者, 第二個(gè)陪集第二個(gè)陪集C+e3的陪集首的陪集首e3取取V-C-( C+e2)中重量最小者中重量最小者, 依次類推可

24、得依次類推可得C的各個(gè)陪集的各個(gè)陪集, 由它們排列成由它們排列成譯碼的標(biāo)準(zhǔn)陣列譯碼的標(biāo)準(zhǔn)陣列. 群碼 C 譯為cj 錯(cuò)誤圖樣 em的陪集以剩余矢量中重量最小者為陪集首五、線性分組碼的譯碼9c1=0c2.ci.cj .c2ke2c2+e2.ci+e2.cj +e2.c2k+e2e3c2+e3.ci+e3.cj +e3.c2k+e3 . . . emc2+em.ci+em.cj +em.c2k+em . . . e2n-kc2+ e2n-k .ci+ e2n-k .cj + e2n-k .c2k+ e2n-k證明標(biāo)準(zhǔn)陣列譯碼符合最小距離譯碼準(zhǔn)則證明標(biāo)準(zhǔn)陣列譯碼符合最小距離譯碼準(zhǔn)則, 即證：即證：d

25、(ci+em,ci)d(ci+em,cj) 證明：證明： d(ci+em,ci) = w(em)d(ci+em,cj) =w(ci+cj+em) = w(cq+em)由標(biāo)準(zhǔn)陣列的生成規(guī)則，得由標(biāo)準(zhǔn)陣列的生成規(guī)則，得w(em) w(cq+em)下證不相等。下證不相等。由由d(cq,em)+d(cq+em,cq) d(cq+em,em), 得得w(cq+em)+w(em) w(cq)w(cq+em) w(cq) -w(em) 又若又若 d(cq,0) 2 w(em) +1 ，則，則 w(cq) 2 w(em) +1,所以所以w(cq+em) 2w(em) +1-w(em) =w(em) +1w(e

26、m) w(cq+em)cq+emcqem五、線性分組碼的譯碼10tiintnnnnnCCCCCC01211.1 糾t個(gè)錯(cuò)誤：.1 糾2個(gè)錯(cuò)誤：1 個(gè)錯(cuò)1糾：誤最佳碼：使最佳碼：使w=w(e0)+w(e1)+.+w(e2n-k)為最小的碼。為最小的碼。不是唯一，表不是唯一，表3-3，表，表1-2。5. 完備碼完備碼定理定理8 8：GF(2)GF(2)上的上的(n,k)(n,k)線性碼能糾線性碼能糾2 2n-kn-k個(gè)錯(cuò)誤圖樣個(gè)錯(cuò)誤圖樣錯(cuò)誤圖樣數(shù)錯(cuò)誤圖樣數(shù)所以所以 2 2n-kn-k tiinC0n-k :監(jiān)督元數(shù)目t :糾錯(cuò)能力取下限，得2 2n-k n-k = =tiinC0滿足這個(gè)條件的叫完

27、備碼（定義滿足這個(gè)條件的叫完備碼（定義3.3.2)?？梢?，完備碼的糾錯(cuò)能力達(dá)到極限?？梢?，完備碼的糾錯(cuò)能力達(dá)到極限。問題：如果是多元碼，問題：如果是多元碼，情況會(huì)怎樣？情況會(huì)怎樣？五、線性分組碼的譯碼11漢明碼漢明碼2m-1,2m-1-m,3是能糾一個(gè)錯(cuò)的是能糾一個(gè)錯(cuò)的2元完備碼元完備碼(=1+2m-1=2m). 定義定義（定義（定義3.3.1)：GF(2)上的線性分組碼上的線性分組碼n,k,d稱為漢明碼，若滿足稱為漢明碼，若滿足下列條件：下列條件： (1) n = 2 2m m-1 (m-1 (m N,N,且且m m 3)3)； (2 2) k=2k=2m m-m-1 -m-1 (3)3)n

28、-k = m; (4) d=3。戈萊戈萊(Golay)碼碼23,12,7 （P202-203)是目前唯一已知能糾多個(gè)錯(cuò)誤的是目前唯一已知能糾多個(gè)錯(cuò)誤的2元完元完備碼備碼六、由一個(gè)已知碼構(gòu)造新碼的簡(jiǎn)單方法擴(kuò)展碼：擴(kuò)展碼：增加一個(gè)檢驗(yàn)位增加一個(gè)檢驗(yàn)位n,k n+1,k加奇偶校驗(yàn)位，一般為偶校驗(yàn)。加奇偶校驗(yàn)位，一般為偶校驗(yàn)。H=11100|H 對(duì)于漢明碼2m-1, 2m-1-m, 3, 由于d = 3, H任兩列線性無關(guān)同時(shí)存在線性相關(guān)的3列, 而在H中, 任三列線性無關(guān)(最后一位3個(gè)1相加不為0), 但存在線性相關(guān)的4列(原在H中線性相關(guān)的3列加上H的最后一列),所以H確定了擴(kuò)展?jié)h明碼2m, 2m

29、-1-m, 4.2. 刪除碼刪除碼：刪去一個(gè)檢驗(yàn)位（和擴(kuò)展碼相反）：刪去一個(gè)檢驗(yàn)位（和擴(kuò)展碼相反）n,k n-1,k六、由一個(gè)已知碼構(gòu)造新碼的簡(jiǎn)單方法23. 增廣碼增廣碼：（增信刪余碼）：（增信刪余碼）增加一個(gè)信息元，刪去一個(gè)校驗(yàn)元增加一個(gè)信息元，刪去一個(gè)校驗(yàn)元n,k n,k+14. 增余刪信碼增余刪信碼刪去一個(gè)信息元，增加一個(gè)校驗(yàn)元?jiǎng)h去一個(gè)信息元，增加一個(gè)校驗(yàn)元 n,k n,k-15. 延長(zhǎng)碼延長(zhǎng)碼先增廣，后擴(kuò)展先增廣，后擴(kuò)展n,k n,k+1 n+1,k+1擴(kuò)展擴(kuò)展原碼原碼增余刪信增余刪信擴(kuò)展擴(kuò)展刪除刪除縮短縮短n,kn+1,kn,k-1延長(zhǎng)延長(zhǎng)增余刪信增余刪信增信刪余增信刪余6. 縮短碼

30、縮短碼刪去一個(gè)信息元?jiǎng)h去一個(gè)信息元 縮短循環(huán)碼（縮短循環(huán)碼（p157, 5.4節(jié)）節(jié)）n,k n-1,k-1七、線性碼的不可檢測(cè)錯(cuò)誤概率Pu(e)當(dāng)錯(cuò)誤圖樣是一個(gè)非零碼字時(shí)，當(dāng)錯(cuò)誤圖樣是一個(gè)非零碼字時(shí)，s=0，這時(shí)無法檢測(cè)錯(cuò)誤。，這時(shí)無法檢測(cè)錯(cuò)誤。共有共有2k-1個(gè)非零碼字個(gè)非零碼字1. 根據(jù)根據(jù)n和和d求求Pu(e)01011- ppp對(duì)于2進(jìn)制對(duì)稱信道(BSC)1- pndiiniuppinePmin)1 ()(2. 由由(n,k)的重量分布的重量分布A0,A1,Ai,An求求Pu(e)Ai表示重量為i的碼字的個(gè)數(shù)niiniiuppAeP1)1 ()(七、線性碼的不可檢測(cè)錯(cuò)誤概率Pu(e)（2）3. 由由(n,k)的對(duì)偶碼的重量分布的對(duì)偶碼的重量分布B0,B1,Bi,Bn求求Pu(e)nknnuniiiniiinniiniiunknniiiniiip