【正文】 ┇ ┇ 16 1 1 1 1 1 1 1 兩條碼組模 2加后，循環(huán)左移 1位，得到前 (k1)=3位皆為 “ 0” 的碼組 “ 0001011”，對應(yīng) g(x)= x3 + x + 1 如何尋找 g(x) ？ 第十一章 差錯控制編碼 1011000 0101100 0010110 0001011 G = 線性變換典型化 1000101 0100111 0010110 0001011 G = 1000 101 0100 111 0010 110 0001 011 Ik┊ Q 通信原理 內(nèi)容簡介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章 循環(huán)碼 循環(huán)碼原理 (n,k)碼的生成多項式 ■ 無已知條件下，求 (n,k) 循環(huán)碼的 g(x) 如何尋找 g(x) ？ 可以證明 (見教材 )，生成多項式 g(x) 是 (xn + 1)的一個因式。 上述結(jié)論告訴我們，可以通過對 (xn + 1)分解因式獲得 g(x) 。 (xn + 1)的因式可能有多個，只有那些常數(shù)項不為零的 nk次因式才可作為 (n , k)循環(huán)碼的生成多項式 g(x) 。 例如：為獲得 (7, 4) 循環(huán)碼的生成多項式 g(x) ，分解 (x7 + 1)得 (x7 + 1) = ( x + 1) ( x3 + x2 + 1) ( x3 + x + 1) g1(x)和 g2(x)都可作為 (7 , 4)循環(huán)碼的生成多項式 。 g1(x) g2(x) () 同理 , (7 , 3)循環(huán)碼的生成多項式也是分解 (x7 + 1)所得 g2(x) = x4 + x3 + x2+ 1 () g1(x) = x4 + x2 + x + 1 () ( x + 1) ( x3 + x2 + 1) ( x + 1) ( x3 + x + 1) 第十一章 差錯控制編碼 通信原理 內(nèi)容簡介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章 循環(huán)碼 循環(huán)碼的編解碼方法 ■ 編碼步驟 (1) 用信息碼多項式 m(x)乘以 xnk ，該運(yùn)算相當(dāng)于給信息碼后加(n k)個“ 0”。 例如，信息碼為“ 110”, 相當(dāng)于 m(x)= x2 + x 。當(dāng) n k=73=4 時， xnk m(x) = x4 (x2 + x ) = x6 + x5，相當(dāng)于“ 1100000” 。 (2) 用 xnk m(x)除以 g(x) , 得到商 Q(x)和余式 r(x) , 既 xnk m(x) = g(x) Q(x) + R(x) () 若取 g(x)= x4 + x2 + x +1 ，對于上例可得 相當(dāng)于 11)1(1)()(24222456??????????????xxxxxxxxxxxxgxmx kn1100000 10111 101 10111 = 111 + () () 第十一章 差錯控制編碼 通信原理 內(nèi)容簡介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章 循環(huán)碼 循環(huán)碼的編解碼方法 ■ 編碼步驟 (3) 編出碼組 T(x)為 T(x) = xnk m(x) + r(x) () 在上例中 T(x) = 1100000 + 101 = 1100101 正是表 116中第 7條碼組。 a b c d ⊕ ⊕ ⊕ S e f m 信息碼輸入 編碼輸出 圖 116 (7, 3) 循環(huán)碼編碼器 第十一章 差錯控制編碼 通信原理 內(nèi)容簡介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章 循環(huán)碼 循環(huán)碼的編解碼方法 ■ 解碼步驟 (1) 用接收碼組 R(x) = T(x) + E(x)除以生成多項式 g(x) , 得到余式 r(x) 。 (2) 根據(jù)余式 r(x)用查表方法或運(yùn)算得到錯誤圖樣 E(x) , 就可確定誤碼位置。 (3) 從 R(x)中減去 E(x) , 就可得到已經(jīng)糾正錯誤的原始發(fā)送碼組T(x) 。 解碼 信息輸出 圖 117b (7, 3) 循環(huán)碼糾錯解碼器 ⊕ a b c d ⊕ ⊕ ⊕ 與 門 ⊕ 緩沖移位寄存器 接收 編碼輸入 第十一章 差錯控制編碼 通信原理 內(nèi)容簡介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章 循環(huán)碼 縮短循環(huán)碼 研究表明，并不是任意碼組長度 n 和信息位 k 都可以找到滿足某糾錯能力的循環(huán)碼。但若將某已知循環(huán)碼縮短，就可能滿足碼長 n 、信息位長度 k 和糾錯能力要求。 給定已知 (n, k)循環(huán)碼集合，使前 i (0 i k)個高階信息位數(shù)字全為“ 0”, 于是得到有 2ki個碼組的集合 , 然后從這些碼組中刪去這 i 個零信息位數(shù)字，最終得到一組新的 (ni, ki)線性分組碼，就是 縮短循環(huán)碼 。 例如，若欲構(gòu)造具有 1 位誤碼糾正能力的 (13, 9)碼，則可以由(15, 11)漢明碼的全部 211條碼組中，挑選出前兩位皆為“ 0”的碼組 29 ，構(gòu)成一個新的碼組集合。而在傳輸時，兩個零信息位不發(fā)送，即發(fā)送的是 (13, 9)縮短循環(huán)碼。 縮短循環(huán)碼 和原始循環(huán)碼相比，縮短的是信息位，監(jiān)督位并沒減少，因此檢錯糾錯能力不會減少。 第十一章 差錯控制編碼 通信原理 內(nèi)容簡介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章 循環(huán)碼 BCH ( BoseChaudhuriHocguenghem)碼 在系統(tǒng)設(shè)計中，通常是在給定糾正隨機(jī)誤碼的個數(shù)條件下尋找碼生成多項式 g(x)，從而得到滿足一定抗干擾性能要求的編碼。 BCH碼就是為解決這一問題研究發(fā)展起來的一類糾正多個隨機(jī)錯誤的循環(huán)碼。 ■ 本原 BCH碼 本原 BCH碼的碼長為 n=2m1 (m是大于或等于 3的整數(shù) ) , 其生成多項式 g(x)中含有最高次數(shù)為 m次的本原多項式。 ■ 非本原 BCH碼 本原 BCH碼的碼長 n為 ( 2m1 ) 的一個因子，其生成多項式g(x)中不含有最高次數(shù)為 m次的本原多項式。 可以證明： 對于正整數(shù) m (m≧ 3) 和 t (t m/2) , 必存在 “ 碼長n=2m1，監(jiān)督位數(shù)目 r ≦ mt , 能夠糾正不大于 t 個的隨機(jī)誤碼 ”的 BCH碼。 第十一章 差錯控制編碼 通信原理 內(nèi)容簡介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章 循環(huán)碼 BCH ( BoseChaudhuriHocguenghem)碼 表 118 二進(jìn)制本原 BCH碼參數(shù) —— n、 k、 t、 g(x) n k t g(x) n k t g(x) 7 4 1 13 63 57 1 103 1 3 77 51 2 12471 15 11 1 23 45 3 1701317 7 2 721 39 4 166623567 5 3 2467 36 5 1033500423 1 7 77777 30 6 157464165347 31 26 1 45 24 7 17323260404441 21 2 3551 18 10 1363026512351725 16 3 107657 11 5 5423325 127 120 1 211 6 7 313365047 113 2 41567 1 15 17777777777 多項式系數(shù) (八進(jìn)制 ) 111010001 g(x) = x8+x7+x6+ x4+1 第十一章 差錯控制編碼 通信原理 內(nèi)容簡介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章 循環(huán)碼 BCH ( BoseChaudhuriHocguenghem)碼 循環(huán)碼 里德 索洛蒙 (ReedSolomon)碼見講義（略） 表 119 部分非本原 BCH碼參數(shù) n k t g(x) 17 9 2 727 21 12 2 1663 23 12 3 5343 33 22 2 5145 41 21 4 6647133 47 24 5 43073357 65 53 2 10761 65 40 4 354300067 73 46 4 1717773537 多項式系數(shù) (八進(jìn)制 ) 101001100101 g(x) = x11+x9+x6+ x5 + x2 +1 255=17 15 2047=23 89 第十一章 差錯控制編碼 通信原理 內(nèi)容簡介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章 卷積碼 (連環(huán)碼 ) 前述的 分組碼 在編碼時，各長度為 n的碼組進(jìn)行分別編碼。即對于給定的 k個信息位，附加上僅僅與這 k個信息位有關(guān)的 r個監(jiān)督位，形成長度為 n的碼組。 各個碼組之間沒有任何約束關(guān)系 ，因此在譯碼時各個碼組也是分別獨(dú)立地進(jìn)行。 卷積碼 在編碼時，長度為 n的碼組由 k個信息位附加上 r個監(jiān)督位，形成長度為 n的碼組。但是這 r個監(jiān)督位不僅僅與當(dāng)前的 k個信息位有關(guān)，還和前面的 (N1)個碼組中的信息位有關(guān)。這樣若干個 (N)碼組形成一種約束關(guān)系。 卷積碼 的約束長度 :以碼組為單位時為 N, 以碼元為單位時為 nN 。 碼組長度為 n , 信息位組長度為 k , 約束長度為 N個碼組的卷積碼記為 (n , k , N)卷積碼 , 卷積碼的編碼效率為 Rc=k/n。 第十一章 差錯控制編碼 通信原理 內(nèi)容簡介 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章 卷積碼 卷積碼的圖形表示 M3 M2 M1 ⊕ ⊕ 輸入序列 m1, m2 , …, mj ,