【正文】 () 將式 ()代入式 ()，得到 于是，得到 P=QT () ? ?TT T,0knk? ?? ??? ? ? ??? ????IH G P I P 第 3章 分組碼 4. 系統(tǒng) (n， k)線性分組碼的編碼實現(xiàn)電路 例 實現(xiàn)系統(tǒng) (7， 3)線性分組碼。 又因 (n， k)線性分組碼 C是線性空間 Vn的 k維線性子空間，所以存在一個與 C正交的線性子空間 (記為 C⊥ )，使 () ”表示直和。 1) HGT=0 將式 ()代入式 ()，有 HGTmT=0T () 式 ()對 Xk中全部字符 m都成立，所以一定有 () T()00n k k???HG 　 　 　簡記 第 3章 分組碼 式 ()中 0(n－ k) k表示階為 (n－ k) k的零矩陣，為簡便，在意義明確時略去下標(biāo)。于是，任意 (n， k)線性分組碼 C中碼字可以簡記為 c=mG () 111 12 1221 22 2112nnkk k k nkg g gg g gg g gaaaa???????????????????????????G第 3章 分組碼 經(jīng)過矩陣的行初等變換，生成矩陣 G一定能等價于 即生成矩陣的分塊矩陣為 G=［ Ik， Q］ () ? ?? ?? ?11 12 121 22 2121 0 0 00 1 0 00 0 0 1nknkkk k n kq q qq q qq q q????????????G () 第 3章 分組碼 式中： Ik是 k階單位矩陣， 這樣， (n， k)線性分組碼 C中的任意碼字可以表示成 這樣的 (n， k)線性分組碼 C剛好是系統(tǒng)碼。設(shè)碼 C中的一組基為 a1=(g11， g12， … ， g1n) a2=(g21， g22， … ， g2n) … ak=(gk1， gk2， … ， gkn) 那么，碼 C中任意一個碼字 c可以表示為 第 3章 分組碼 () ? ?121 1 2 2 1 1 0 1 2 3 1 01, , , , ,k k k k k k kkkm m m m m m m m m? ? ? ? ? ??????????? ? ? ? ? ?????????caaa a a aaa第 3章 分組碼 定義 稱矩陣 為 (n， k)線性分組碼的生成矩陣。 ? ? ? ? ? ?? ?11 12 121 22 212de f1 0 00 1 000 0 1,kkn k n k n k knkp p pp p pp p p? ? ????????????HPI　 　() 第 3章 分組碼 2. (n， k)線性分組碼的生成矩陣 G 從線性空間的角度來看，一個 (n， k)線性分組碼 C是 n維線性空間 Vn的一個 k維子空間。 () 1 0 1 1 0 0 01 1 1 0 1 0 01 1 0 0 0 1 00 1 1 0 0 0 1?????????H第 3章 分組碼 一般地， (n， k)線性分組碼是通過下面的方程來獲得校驗元的，即 將其寫成矩陣形式，有 HcT=0T () () ? ?? ?? ? ? ? ? ? ? ? ? ?11 1 12 2 1 1 01121 1 22 2 1 2 0211 2 1 01 2 1000n n nnn n nnnnn k n k n k n n k nh c h c h c h ch c h c h c h ch c h c h c h c?? ??? ???? ? ? ? ?? ? ? ? ???? ? ? ? ????? ? ? ? ? ??第 3章 分組碼 式中： () ? ?? ?? ? ? ? ? ? ? ? ? ?11 12 11121 22 2211 2 1nnnnn k n k n k n n k nh h h hh h h hh h h h??? ? ? ? ??????????H? ?1 2 1 0, , , ,nnc c c c???c第 3章 分組碼 定義 稱式 ()為校驗方程，稱矩陣 H為校驗矩陣。 6 4 36 5 4 26 5 15400000c c cc c c cc c cc c c? ? ???? ? ? ???? ? ??? ? ? ??() 第 3章 分組碼 為了便于討論，將式 ()寫成矩陣形式： 簡記為 HcT=0T () () 65432101 0 1 1 0 0 0 01 1 1 0 1 0 0 01 1 0 0 0 1 0 00 1 1 0 0 0 1 0ccccccc??????? ? ? ???? ? ? ???? ? ? ????? ? ? ???? ? ? ???? ? ? ???????第 3章 分組碼 式中： c=(c6， c5， c4， c3， c2， c1， c0) 0=(0， 0， 0， 0) 式 ()是重要的，一個長度為 7的矢量是 (7， 3)線性分組碼的碼字的充要條件是滿足式 ()。取矢量 y=(y1， y2， … ，yn)，式中： 于是 ，由 r′≤t－ 1得到 dist(x， y)=r′+1≤t 且 dist(z， y)=r′≤t－ 1 () jjiixz?? ?, 1 , 2 , , 1 , , 2 , 2 1, 1 , 2 , , , 1 , 2 , , 2 1jjjjiiiik k k jy x j ry z j r r ry x z k n k i j r? ?????? ? ?? ? ? ????? ? ? ? ? ??? 且第 3章 分組碼 線 性 分 組 碼 線性分組碼的編碼方法 1. (n， k)線性分組碼的校驗矩陣 H 構(gòu)造線性分組碼的關(guān)鍵在于校驗元的選取規(guī)則，雖然有相同的信息碼和相同的校驗元數(shù)目，但不同校驗元的選取規(guī)則所產(chǎn)生的線性分組碼的糾、檢錯能力是不同的。取矢量 y=(y1， y2， … ， yn)，式中： jjiixz?第 3章 分組碼 于是 ，由 r′≤t得到 dist(x， y)=r′≤t 且 dist(z， y)=r′≤t () ? ?, 1 , 2 , , 1 , , 2, 1 , 2 , , , 1 , 2 , , 2jjjjiiiik k k jy x j ry z j r ry x z k n k i j r? ???????? ? ????? ? ? ? ??? 且第 3章 分組碼 情況 2：設(shè) x與 z間有 2r′+1(2t+1)個碼元對應(yīng)不同。 情況 1：設(shè) x與 z間有 2r′(2t+1)個碼元對應(yīng)不同。假設(shè) dist(C)2t+1，那么必定存在兩個不同的碼字 x=(x1， x2， … ， xn)和 z=(z1， z2， … ， zn)滿足 dist(x， z)2t+1。 ② 充分性。 ① 必要性。 證明 只證結(jié)論 (1)，其余省略。 111kRkn? ? ??第 3章 分組碼 定理 在一個線性分組碼中，碼的最小漢明距離等于碼的最小漢明重量。 第 3章 分組碼 如果是偶數(shù)個錯誤，則有 y1+y2+…+ yk+yk+1=2r+(x1+x2+…+ xk+xk+1)=2r=0 (mod2) 說明滿足式 ()，因而無法檢出錯誤。 ? ? ? ?1 2 1 2 1k k kx x x x x x x ??第 3章 分組碼 解 僅討論偶校驗，所得結(jié)論適合于奇校驗。對 X={0， 1}的 k維擴展信源Xk添加一位校驗位形成一個長為 k+1的碼字，即 且滿足關(guān)系： x1+x2+…+ xk+xk+1=0 (偶校驗 ) () 即信息碼 (x1x2… xk)中如有偶數(shù)個 1，則 xk+1=0，如有奇數(shù)個 1，則 xk+1=1。 定義 稱 (n， k)線性分組碼的 為碼率。須注意一點， n－ k個校驗元可以放在碼字中的任何位置，如果碼字前k位固定為信息碼，則這種分組碼稱為系統(tǒng)分組碼，如圖 所示。 解 dist(a2， a4)=4， dist(a3， a7)=4， wt(a8)=4， dist(C2)=4， wt(C2)=4 第 3章 分組碼 定義 設(shè)有碼 C，如果 ，有 x+y∈ C，則稱碼 C是線性碼。 定義 設(shè)有碼 C， 0 =(0， … ， 0) wt(C)=min{wt(x)|x∈ C， x≠0} () 為碼 C的最小漢明重量。 在一個碼中，碼字中非零碼元的數(shù)目也是一個重要的參數(shù)，這個參數(shù)通常稱為碼字的漢明重量。 碼字間的漢明距離滿足下列三角不等式： dist(x， y)≤dist(x， z)+dist(z， y) () 在一個碼中，任意兩個不同碼字間漢明距離的最小者稱為這個碼的最小漢明距離。消息的編碼、譯碼關(guān)系見表 。接收端按選大原則進行譯碼，在接收的 5比特矢量中，哪個符號多就譯為哪個。第 3章 分組碼 第 3章 分組碼 糾、檢錯編碼的基本概念 線性分組碼 循環(huán)碼 BCH碼 習(xí)題 第 3章 分組碼 糾、檢錯編碼的基本概念 為了降低錯誤概率 pe及使接收端具備檢錯、糾錯能力，我們這樣來對待傳消息進行編碼。選碼 C1={00000， 11111}，作映射： 即消息中的每一符號比特按其重復(fù)的 5比特碼字來表示，并由發(fā)送端傳送。例如接收為 10110，則譯為 11111。 0 00 00 0 , 1 11 11 1??第 3章 分組碼 表 消息的編碼、譯碼關(guān)系 第 3章 分組碼 定義 ， x=(x1， x2， … ， xn)， y=(y1，y2， … ， yn)，稱 dist(x， y)=|{i|xi≠yi， i=1， 2， … ， n}| () 為碼字 x與 y的漢明距離。 C??x, y()C??x, y , z第 3章 分組碼 定義 設(shè)有碼 C，稱 () 為碼 C的最小漢明距離。 ? ?? ?dis t( ) m in dis t | ,CC? ? ? ?x, y x, y x y　第 3章 分組碼 定義 設(shè)有碼 C， ，稱 wt(x)=|{i|xi≠0， i=1， 2， … ， n}| () 為碼字 x的漢明重量。 ? ?12, , , , nC x x x? ? ?xx第 3章 分組碼 例 設(shè)有碼 C2=(a1， a2， a3， a4， a5， a6， a7， a8)，式中 a1=(0000000) a2=(0011101) a3=(0100111) a4=(0111010) a5=(1001110) a6=(1010011) a7=(1101001) a8=(1110100) 求 dist(a2， a4)， dist(a3， a7)， wt(a8)， dist(C2)， wt(C2)。 所有的這樣 2k個碼字構(gòu)成的集合稱為分組碼。 圖 系統(tǒng) (n， k)分組碼碼字結(jié)構(gòu) , C??xy第 3章 分組碼 定義 將 k位信息碼通過一定的規(guī)則添加 n－ k個校驗元而形成長為 n的碼字，如果所有這樣的碼字組成一個線性碼