【正文】 由糾錯(cuò)能力不等式知它可糾 5位錯(cuò)： 215=32768 1+21+210+1330+5985+20349=27896 顯然 ， 存在多種設(shè)計(jì)方案 。 表 某些非本原 BCH碼的生成多項(xiàng)式 r i n/i k t d0 以 8進(jìn)數(shù)表示 g (x) 6 3 21 12 2 5 (127)(15) 8 15 17 9 2 5 (727) 9 7 73 46 4 9 (1210)(1027)(1401) 10 31 33 22 2 5 (3043)(3) 10 31 33 13 4 9 (3043)(3777) 11 89 23 12 3 7 (5343) 12 63 65 53 2 5 (10761) 12 63 65 40 4 9 (13535)(10761)(3) 23 178481 47 24 5 11 (43073357) [例 2] 構(gòu)造碼長(zhǎng)為 21， 分別能糾正 1位 、 2位和 5位錯(cuò)的非本原 BCH碼生成多項(xiàng)式 。 冗余利用率 t/r達(dá)到 1/4，可糾錯(cuò)比值 t/n達(dá)到 2/17， 編碼效率 k/n超過(guò) 50%。 又如 ， n=281=255， x2551中有一個(gè) 8次的非本原多項(xiàng)式 m15(x)=x8+x7+x6+x4+x2+x+1。 因?yàn)榉潜驹囗?xiàng)式的共厄類(lèi) i與 n可約， m是它的循環(huán)級(jí) ，根據(jù)數(shù)學(xué)理論， xm1的因式分解中就能包含 共厄類(lèi) i 相應(yīng)的那個(gè)非本原多項(xiàng)式。 （ 4） t =4時(shí)： 2t1=7， g(x) =LCM [m1(x) m3(x) m5(x) m7(x)] =(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)(x4+x3+1) =x14+x13+x12+x11+x10+x9+x8 +x7+x6+x5+x4+x3+x2 +x+1； 得到 （ 15,1） 碼 ， 即 15連重復(fù)碼 。 [例 1] 構(gòu)造碼長(zhǎng)為 15， 分別能糾正 1位 、 2位 、 3位和 4位錯(cuò)的本原 BCH碼生成多項(xiàng)式 。 ] 表示求最小公倍式。 (因?yàn)?2101+15+105+455) 定義： 取 碼長(zhǎng)為 n = 2m –1， 取 包括本原多項(xiàng)式在內(nèi)的若干個(gè)因式之積為生成多項(xiàng)式的循環(huán)碼叫做本原BCH碼。 xn 1既然可分解為多個(gè)因式，我們不妨取幾個(gè)因子的乘積作為生成多項(xiàng)式，就能增加它的冪次。 i ) 二元本原 BCH碼 因式分解的數(shù)學(xué)理論解決了循環(huán)碼的存在問(wèn)題，并為它奠定了堅(jiān)實(shí)的基礎(chǔ)。循環(huán)級(jí) m等于 n的根是本原根，循環(huán)級(jí) m等于 n的某個(gè)因數(shù) (n/i)的根是非本原根。 (這里 m是循環(huán)級(jí)， n是 m的倍數(shù)） α3 α6 α9 α12 小結(jié)： xn1有 n個(gè)復(fù)數(shù)根 αk， 它們按平方關(guān)系分為若干個(gè)共厄類(lèi)。 這樣就把 xn1分解得到的因式也分成了本原與非本原兩種。 因此， 本原根構(gòu)成的類(lèi)是本原類(lèi)，非 本原根構(gòu)成的類(lèi)是非本原類(lèi)。 然而，例中第 i=3類(lèi)中的根 αk (k=3,6,9,12)，因?yàn)?i值是n值的因子，每個(gè)根 αk無(wú)須自乘 n =15次，只要自乘m=n/i=5次，就能回到 α0 =1；同理， 第 i=5類(lèi)中的根 αk， 只要自乘 m=n/i= 3次，就能回到 α0 =1。 我們來(lái)看 x151=0的第 i=5類(lèi)中 α5與 α10 這 2個(gè) 1次因式： ∵ α5= e j (5 2π)/15= e j 2π/3； α10= e j (10 2π)/15= e j 4π/3 = ej 2π/3 ； ∴ (x α5)(x α10 )= (x e j 2π/3)(x ej 2π/3 )= = x2 –(e j 2π/3+ej 2π/3 ) x+1= x2 –2cos (2π/3) x+1 = x2 + x+1 在 GF(2)域 x2 + x+1已經(jīng)最簡(jiǎn)，不能再分解了。 同理得到其它共厄類(lèi)： 共厄類(lèi) 根 根的個(gè)數(shù) i=1類(lèi) α1,α2,α4,α8 4個(gè) i=3類(lèi) α3,α6,α12,α24 =α9 4個(gè) i=5類(lèi) α5,α10 2個(gè) i=7類(lèi) α7,α14,α28 =α13 ,α56 =α11 4個(gè) i=0類(lèi) α0=1 1個(gè) 結(jié)論： x151=0 有 5個(gè)共厄類(lèi)，各個(gè)類(lèi)互不重復(fù)，且恰巧取盡了全部 15個(gè)根。 α1 α0 α2 α3 αn1 α4 ： 當(dāng) n=2m1時(shí)， xn1的 n個(gè)根 αk (k=0,1,2,… ,n1) 按 平方關(guān)系 ： k = i,2i,4i,8i,16i …… ； 可以 分成若干類(lèi)。 寫(xiě) 1=1 （ 3）所有與許用碼字漢明距離不大于 d01的錯(cuò)誤。 例如信息為 K(x)=4D6F746F(H) ， 則可以在信息后面添上 CRC監(jiān)督碼： r (x)=x16K(x) mod g(x) = =4D6F746F0000(H) mod 11021(H)= B944(H) 有時(shí)也取 32位的 CRC校驗(yàn)碼，生成多項(xiàng)式為： g(x)=(x16+x15+x2+1) 在數(shù)據(jù)通信和軟盤(pán) 、 光盤(pán)存儲(chǔ)器中 ， 常常需要對(duì)較多信息 （ 一個(gè)數(shù)據(jù)幀或一個(gè)記錄軌道中的數(shù)據(jù) ）進(jìn)行差錯(cuò)監(jiān)督 。 截短循環(huán)碼的引入，擴(kuò)大了循環(huán)碼的覆蓋范圍，使人們能根據(jù)所需要的 n、 k值靈活地設(shè)計(jì)各種(ni, ki)碼。 可以從效率較高的（ 7,4）漢明碼出發(fā)，在 (7,4) 碼的生成矩陣中去掉前兩行和前兩列，剩下的部分構(gòu)成一個(gè) 5 2的矩陣，可以用它來(lái)生成 (5,2)碼 。當(dāng)然，它無(wú)法糾正，只能要求系統(tǒng)重發(fā)。如果給它的每一個(gè)許用碼字增加一位奇偶校驗(yàn)位，使其成為 (n+1, k) 碼，其編碼效率降低不多，但監(jiān)督能力卻得到提高，不僅能糾正 1位錯(cuò)，還能發(fā)現(xiàn)第 2位錯(cuò)。 （ 4） g(x)是 xn1的一個(gè)因式。 作業(yè)： P114頁(yè)： 1 17題 第三章 信道編碼 循環(huán)碼的擴(kuò)展 本節(jié)的主要內(nèi)容 ?增余漢明碼 ?截短循環(huán)碼 ?循環(huán)冗余校驗(yàn)碼 ?二元本原 BCH碼 ?二元非本原 BCH碼 增余漢明碼： extended Hamming code 截短循環(huán)碼： shortened cyclic code 循環(huán)冗余校驗(yàn)碼： Cyclic Redundancy Check Code (CRC) 本原 BCH碼 ： primitive BCH code 非本原 BCH碼 : nonprimitive BCH code 外語(yǔ)關(guān)鍵詞 上節(jié)回顧：循環(huán)碼 基本概念 ： 循環(huán)碼的特點(diǎn)，碼多項(xiàng)式，循環(huán)移位的數(shù)學(xué)表達(dá)。 （ 4） 若 S(x) ≠ 0， 表明接收碼有誤 ， 此時(shí)應(yīng) 將糾錯(cuò)能力 t 位以?xún)?nèi)的各種錯(cuò)誤格式 E(x)除以 g(x) 的余式都計(jì)算出來(lái) ， 列成一張 S(x)E(x) 對(duì)照表 。 E(x)為 1的碼位進(jìn)入運(yùn)算器的同時(shí)也進(jìn)入 緩沖器，經(jīng)過(guò) 7步才能緩沖才能輸出，這時(shí)正好與門(mén)打開(kāi)，將其糾正。巧就巧在正好輪到 R有錯(cuò)的那一位輸出時(shí) ， 寄存器恰變?yōu)?101， 與門(mén)便輸出糾錯(cuò)信號(hào) “ 1”， 將該位錯(cuò)碼糾正 。若 e6位錯(cuò)，則求余結(jié)果 S = 101，恰使與門(mén)有輸出，正好糾正 R6位。 (3) 無(wú)須移位 7次，只要移位 4次，就可以完成求模 運(yùn)算的工作，接著把 P置下， Q開(kāi)啟，就可以把 D0D1D2中的余數(shù)，順序接在編碼的后半段上， 形成完整的編碼。 然后 P置向下 ， Q開(kāi)啟 ， 繼續(xù)將寄存器中的余數(shù)輸出；就是接在后面的監(jiān)督 。 模 2加等價(jià)于模 2減， 就實(shí)現(xiàn)了與寄存器中原先余數(shù)的相減運(yùn)算。 余數(shù)初值為零，覆蓋值是被除數(shù)減去商與除數(shù)之積。最后 留在寄存器中的就是余數(shù) ,上輪余數(shù)的首位被輸出，它的就是商。 筆算時(shí)是從被除數(shù)的高位開(kāi)始，依次對(duì)除數(shù)求商、求積、求余，然后右移一位，繼續(xù)前述過(guò)程，直至到被除數(shù)末尾 。 因 S(x) = [C(x)+E(x)] mod g(x) = E(x) mod g(x)； 為了找到 S(x) 對(duì)應(yīng)的 E(x)， 我們可以預(yù)先將糾錯(cuò)能力 t 位 以?xún)?nèi)的各種錯(cuò)誤格式 E(x)除以 g(x) 的余式都計(jì)算出來(lái)，列成一張 S (x)E (x) 對(duì)照表，由 S (x) 就能直接查出 E (x)。 [例 2] 求 (7, 3)循環(huán)碼的生成多項(xiàng)式，并為信息 K = (110) 編碼。 小結(jié)：循環(huán)碼的編碼步驟： 確定 (n,k)循環(huán)碼的生成多項(xiàng)式：將 xn1分解因 式 ， 從中選擇一個(gè) r次的因子作為 g(x)。 k (x) mod g(x) (2) 再由公式 (1)就得到了相應(yīng)的碼字。 （ 2）直接計(jì)算系統(tǒng)碼的監(jiān)督元 : 以 (7, 4)碼為例，設(shè)信息位為 k3 k2 k1 k0，對(duì)應(yīng)的多項(xiàng)式為： k(x)=k3x3 +k2x2 +k1x +k0； 設(shè)監(jiān)督位為 r2 r1 r0， 監(jiān)督位對(duì)應(yīng)的多項(xiàng)式為 : r(x) = r2x2 +r1x +r0 ； 系統(tǒng)碼 碼字 C = (k3 k2 k1 k0 r2 r1 r0)對(duì)應(yīng)的碼多項(xiàng)式為 : C(x) = k3x6 +k2x5 +k1 x4 +k0 x3 + r2 x2 + r1 x +r0 ； = x3 (k3x3 +k2x2 +k1x +k0 ) +(r2x2 +r1x +r0 ) = x3 k(x)+ r(x) 推廣到一般 ， 碼多項(xiàng)式可寫(xiě)為為： C(x) = x r 原因是 G1不 具備 G=[Ik Q]的形式，這樣編碼叫 非系統(tǒng)碼，非系統(tǒng)碼在譯碼時(shí)是比較困難的。 從循環(huán)組中隨便取 4個(gè)許用碼字，比如前 4個(gè)，用它們構(gòu)成的生成矩陣為 G1： 再利用 C = K?G1 就能求得全部許用碼字。 果然如此簡(jiǎn)單嗎？ 實(shí)際上，通過(guò)循環(huán)移位最多可寫(xiě)出 n個(gè)碼字，得不到全部碼字，因?yàn)? (n,k)碼應(yīng)當(dāng)共有 2k個(gè)許用碼字。 [例 ]查表分解 x631 因?yàn)?261=63，所以應(yīng)查 P194 頁(yè)表 4中 m=6階 。所謂對(duì)偶指的是將二進(jìn)制自然碼高低位倒置的表達(dá)，如： 與 (100101)2對(duì)稱(chēng)的是 (101001)2，表示 m15(x)=x5+x3+1； 與 (111101)2對(duì)稱(chēng)的是 (101111)2，表示 m7(x)=x5+x3+x2+x+1； 與 (110111)2對(duì)稱(chēng)的是 (111011)2，表示 m11(x)=x5+x4+x3+x+1； 值得注意的是，有的二進(jìn)制自然碼本身就是對(duì)稱(chēng)的，如：(11111)2與 (10001)2，高低位倒置后不變 , 不會(huì)