【正文】 的后半段上， 形成完整的編碼。 （ 4） 若 S(x) ≠ 0， 表明接收碼有誤 ， 此時(shí)應(yīng) 將糾錯(cuò)能力 t 位以內(nèi)的各種錯(cuò)誤格式 E(x)除以 g(x) 的余式都計(jì)算出來 ， 列成一張 S(x)E(x) 對(duì)照表 。當(dāng)然，它無法糾正，只能要求系統(tǒng)重發(fā)。 例如信息為 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) 同理得到其它共厄類： 共厄類 根 根的個(gè)數(shù) i=1類 α1,α2,α4,α8 4個(gè) i=3類 α3,α6,α12,α24 =α9 4個(gè) i=5類 α5,α10 2個(gè) i=7類 α7,α14,α28 =α13 ,α56 =α11 4個(gè) i=0類 α0=1 1個(gè) 結(jié)論： x151=0 有 5個(gè)共厄類，各個(gè)類互不重復(fù)，且恰巧取盡了全部 15個(gè)根。 這樣就把 xn1分解得到的因式也分成了本原與非本原兩種。 xn 1既然可分解為多個(gè)因式，我們不妨取幾個(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ù)碼 。 表 某些非本原 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)造碼長為 21， 分別能糾正 1位 、 2位和 5位錯(cuò)的非本原 BCH碼生成多項(xiàng)式 。 冗余利用率 t/r達(dá)到 1/4，可糾錯(cuò)比值 t/n達(dá)到 2/17， 編碼效率 k/n超過 50%。 [例 1] 構(gòu)造碼長為 15， 分別能糾正 1位 、 2位 、 3位和 4位錯(cuò)的本原 BCH碼生成多項(xiàng)式 。 i ) 二元本原 BCH碼 因式分解的數(shù)學(xué)理論解決了循環(huán)碼的存在問題，并為它奠定了堅(jiān)實(shí)的基礎(chǔ)。 因此， 本原根構(gòu)成的類是本原類，非 本原根構(gòu)成的類是非本原類。 α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 …… ； 可以 分成若干類。 在數(shù)據(jù)通信和軟盤 、 光盤存儲(chǔ)器中 ， 常常需要對(duì)較多信息 （ 一個(gè)數(shù)據(jù)幀或一個(gè)記錄軌道中的數(shù)據(jù) ）進(jìn)行差錯(cuò)監(jiān)督 。如果給它的每一個(gè)許用碼字增加一位奇偶校驗(yàn)位，使其成為 (n+1, k) 碼，其編碼效率降低不多，但監(jiān)督能力卻得到提高，不僅能糾正 1位錯(cuò)，還能發(fā)現(xiàn)第 2位錯(cuò)。 E(x)為 1的碼位進(jìn)入運(yùn)算器的同時(shí)也進(jìn)入 緩沖器，經(jīng)過 7步才能緩沖才能輸出，這時(shí)正好與門打開，將其糾正。 然后 P置向下 ， Q開啟 ， 繼續(xù)將寄存器中的余數(shù)輸出；就是接在后面的監(jiān)督 。 筆算時(shí)是從被除數(shù)的高位開始，依次對(duì)除數(shù)求商、求積、求余，然后右移一位，繼續(xù)前述過程，直至到被除數(shù)末尾 。 k (x) mod g(x) (2) 再由公式 (1)就得到了相應(yīng)的碼字。 果然如此簡單嗎？ 實(shí)際上，通過循環(huán)移位最多可寫出 n個(gè)碼字，得不到全部碼字，因?yàn)? (n,k)碼應(yīng)當(dāng)共有 2k個(gè)許用碼字。可 根據(jù)設(shè)定的碼長 n和監(jiān)督位 r， 將 xn1因式分解，從中選擇一個(gè) r次的因子作為 g(x)。 否則，通過循環(huán)移位還能繼續(xù)降低冪次，它就不是冪次最低的多項(xiàng)式了。 循環(huán)碼與近代數(shù)學(xué)有密切聯(lián)系。 C3=(0111010)。一般 H具有 [P Ir] 的形式， Ir 是 r行 r列單位方陣， P是 r行 k列的矩陣， P與Q互為轉(zhuǎn)置關(guān)系 。HT = E 不難發(fā)現(xiàn)它們具 有循環(huán)移位特性： C0=(0000000)。x4 +0G = (12……k) （ 2）不論 n取何值， xn1總有一個(gè) m0(x)=x+1的因式。 比如： (0100)?G1=(0101100)。 根據(jù)信息 K， 由 r (x) = x r 編、譯碼的電路實(shí)現(xiàn) 1. 除法求余電路 ： 設(shè)被除數(shù)是 x r 譯碼電路 ： 首先斷開 K2，接通 K1，利用除法求余電路，把接收碼字 R(x) 除以 g(x) 的余式，即伴隨子 S (x)計(jì)算出來，存于 D0D1D2中；與此同時(shí)， R(x) 也被緩存在 R0~R6中。 （ 5）由 S (x) 直接查表得到 E (x)。 截短循環(huán)碼 求生成多項(xiàng)式，需要分解 xn1，但只有 n=2m1的數(shù)才能查表分解，這就限制了 n的取值。(x16+x2+x+1) 循環(huán)冗余校驗(yàn)碼不僅實(shí)現(xiàn)起來比較簡單，而且具有很強(qiáng)的檢測(cè)能力。 GF(2)域中的分解： 因式分解與定義域是密切關(guān)聯(lián)的。 (5)非本原多項(xiàng)式的一個(gè)性質(zhì)： 以 x15=1為例， 設(shè)： θ =2π/15， α=e jθ； 則 i=3類的 4個(gè)非本原根為： α3 的輻角 θ =6π/15= 2π/5， α6 的輻角 θ =12π/15= 4π/5， α9 的輻角 θ =18π/15= 6π/5， α12 的輻角 θ =24π/15= 8π/5 連同 α0 =1, 它們五等份單位圓 , 構(gòu)成 x5=1的 5個(gè)根。而幾個(gè)因子的乘積仍然還是 xn1的因式。 二元非本原 BCH碼 本原 BCH碼在碼長 n給定的條件下，通過增大監(jiān)督位數(shù) r 來提高糾錯(cuò)能力。 解： 21不是 2m1的數(shù) ， 但它是 261=63的因子 ， 與 63有公因子 3。 由糾錯(cuò)不等式 2r=256大于 C017+C117+C217=154不難知道 ， 線性分組循環(huán)碼 (17,9)可糾正兩位錯(cuò) 。 ?P195頁表 5給出了 n≤255 的所有本原 BCH碼的碼長、信息位、糾錯(cuò)位數(shù)，并以 8進(jìn)制方式給出了生成多項(xiàng)式。 本原多項(xiàng)式與非本原多項(xiàng)式都是 xn1的因式，但是非本原多項(xiàng)式還是 xm1的因式，這里 m是 n的因子 ( m=n247。 類 根 循環(huán)級(jí) 是否本原 最小多項(xiàng)式 i=1 α1,α2,α4,α8 15 是 x4 + x+1 i=3 α3,α6,α9 , α12 5 非 x4 +x3 +x2 + x+1 i=5 α5,α10 3 非 x2 + x+1 i=7α7,α11, α13 , α14 15 是 x4 +x3 +1 i=0 α0=1 1 非 x+1 x151的根、共厄類及其最小多項(xiàng)式 注意： 各 既 約因式冪次 r 等于該類中根的個(gè)數(shù)，它 與該共厄類的循環(huán)級(jí) m的關(guān)系是： 2r mod m=1 (3)本原類與非本原類： 共厄類是以根的平方（即自乘）關(guān)系劃分的，自乘不會(huì)改變冪次與 n互素或可約的本性，所以 同一共厄類中的根，本原屬性相同。 令： α= e j 2π/n ； 則： xk = αk ( k=0,1,…… ， n1 ) 于是： 結(jié)論：復(fù)數(shù)域中 xn1分解為 n個(gè) 1次因式的乘積。 循環(huán)冗余校驗(yàn)碼 (CRC) Cyclic Redundancy Cheek 循環(huán)冗余校驗(yàn)碼是截短循環(huán)碼的一個(gè)典型應(yīng)用。 k (x) + r (x)； 循環(huán)碼的譯碼： （ 1） 根據(jù) S(x) = E(x) mod g(x)； 算出糾錯(cuò)能力 t 位 以內(nèi)的各種錯(cuò)誤格式 E(x) 的 S (x) 對(duì)照表； （ 2） 求接收碼的伴隨子向量 S*(x) = R(x) mod g(x)； （ 3）從對(duì)照表中查出 S*(x) 對(duì)應(yīng)的 E*(x) （ 4） C (x) = R (x) + E*(x) 增余漢明碼 漢明碼是能糾正一位錯(cuò)的完備碼，具有較高的編碼效率。 當(dāng) R(x)有一位不正確時(shí)， E(x)的相應(yīng)位是 1，其它全 0；除法器求余邏輯是按照 x3+x+1設(shè)計(jì)的 ,初值為 000,當(dāng)有 1輸入時(shí)才變?yōu)?100,此后由于輸入全為 0,寄存器則按照100→010 →001→110→011→111→101 的規(guī)律變化 ,共 7步變到 101。 P D0 ⊕ D1 D2 ⊕ 輸出 Q 輸入 K K(x) 輸入 D0D1D2 輸出 x3位 0 0 0 0 0 x2位 1 1 1 0 1 x1位 0 0 1 1 0 x0位 0 1 1 1 0 1 1 1