【正文】 本節(jié)要點(diǎn) BCH碼 BCH碼 思考 ： 計(jì)算本原 BCH碼的生成多項(xiàng)式的公式為什么用最小公倍數(shù)？為什么式中的共厄類只有奇數(shù)？ P114頁： 1 1 18題 。 （ 1） 取 g(x) =m3(x) = x6+x4+x2+x+1； 得到 (21,15)碼 ， 由糾錯(cuò)能力不等式知它只可糾 1位錯(cuò)： 26=64 1+21 （ 2） 取 g(x) =m3(x) m9(x) = =(x6+x4+x2+x+1)(x3+x2+1)=x9+x8+x7+x5+ x4+x+1； 得到 （ 21,12） 碼 ， 由糾錯(cuò)能力不等式知它可糾 2位錯(cuò)： 29=512 1+21+210 （ 3） 取 g(x)=m3(x)m9(x)m15(x) =(x6+x4+x2+x+1)(x3+x2+1) (x6+x5+x4+x2+1) = = x15+x13+x11+ x10+x7+x6+ x5+x3+x2 +x+1； 得到 (21,6)碼 。 解： 21不是 2m1的數(shù) ， 但它是 261=63的因子 ， 與 63有公因子 3。 特別是 (23,12)叫 Golay碼 ， 是迄今為止人們所找到 的少有的能糾正多個(gè)錯(cuò)誤的完備碼 。 利用非本原 BCH碼 ， 人們構(gòu)造了不少好碼 。 由糾錯(cuò)不等式 2r=256大于 C017+C117+C217=154不難知道 ， 線性分組循環(huán)碼 (17,9)可糾正兩位錯(cuò) 。 因?yàn)?n/i =255/15=17， 所以 x171中會(huì)包含這個(gè) 8次的因子 。 m5(x)= x2+x+1也是非本原多項(xiàng)式 ， 因 15/5=3，所以它是 x31的因式；作為生成多項(xiàng)式 ， 得到（ 3,1） 碼 。以此非本原多項(xiàng)式為生成多項(xiàng)式，可得到的碼長為 m循環(huán)碼， r 沒變， 碼長 m卻比 n小多了，使效率大大提高。 如果在糾錯(cuò)能力不變（即 r不變）的條件下減小 n值，是否有可能得到編碼效率較高且能糾多位錯(cuò)的編碼呢？非本原的 BCH碼就是這樣的編碼。 二元非本原 BCH碼 本原 BCH碼在碼長 n給定的條件下，通過增大監(jiān)督位數(shù) r 來提高糾錯(cuò)能力。 （ 3） t =3時(shí)： 2t1=5， g(x)=LCM [m1(x)m3(x)m5(x)] =(x4+x+1)(x4+x3+x2+x+1)(x2+x+1) =x10+x8+x5+ x4+x2 +x+1； 得到 （ 15,5） 碼 。 解：查最小多項(xiàng)式系數(shù)表 （ 參見附錄二表 4)知： x151= m0(x)m1(x) m3(x) m5(x) m7(x) =(x+1) (x4+x+1) (x4+x3+x2+x+1) (x2+x+1)(x4+x3+1) （ 1） t =1時(shí)： 2t1=1， g(x) = LCM [m1(x)] = (x4+x+1) ；得到 (15,11)碼 。 ?P195頁表 5給出了 n≤255 的所有本原 BCH碼的碼長、信息位、糾錯(cuò)位數(shù)，并以 8進(jìn)制方式給出了生成多項(xiàng)式。 這種碼長為 n = 2m1，生成多項(xiàng)式由上述公式定義的循環(huán)碼，叫做本原 BCH碼。 設(shè) t 是所設(shè)計(jì)的糾錯(cuò)位數(shù)， mi(x) 是 xn1的因式，這里 i =1,3,5,7 ??， 則生成多項(xiàng)式： 式中： LCM [ BCH是能糾正多位錯(cuò)的循環(huán)碼。 ?又如 x151=(x+1)(x4+x+1)(x4+x3+x2+x+1) (x2+x+1)( x4+x3+1) 取生成多項(xiàng)式： g(x)=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1) =x10+x8+x5+x4+x2+x+1 現(xiàn)在監(jiān)督位增加到 r=10，就能構(gòu)成（ 15, 5）碼， 它可以糾正 3位錯(cuò)。而幾個(gè)因子的乘積仍然還是 xn1的因式。 例如， r =3,4,5,6 時(shí)： n=231=7： x71有 3次本原因式 x3+x+1，得到 (7,4)碼 n=241=15： x151有 4次本原因式 x4+x+1，得到 (15,11)碼 n=251=31： x311有 5次本原因式 x5+x2+1，得到 (31,26)碼 n=261=63： x631有 6次本原因式 x6+x+1，得到 (63,57)碼 ？ 理論上線性分組碼糾錯(cuò)位數(shù) t與冗余位 r的關(guān)系是 t≦ r/2，為了糾錯(cuò)位數(shù)更多一些，監(jiān)督位數(shù) r 就得更大一些 ,也就是說生成多項(xiàng)式的冪次 r 需要更大一些。 ？ 根據(jù)因式冪次與循環(huán)級的關(guān)系 ，當(dāng) n=2r – 1時(shí)， x n1 必存在最高冪次為 r 的本原多項(xiàng)式。 本原多項(xiàng)式與非本原多項(xiàng)式都是 xn1的因式，但是非本原多項(xiàng)式還是 xm1的因式，這里 m是 n的因子 ( m=n247。 本原根所在共厄類的 既 約因式叫做本原多項(xiàng)式，非本原根所在共厄類的既約因式叫做非本原多項(xiàng)式。 同一個(gè)共厄類的根有相同的循環(huán)級。 同一個(gè)共厄類的諸根的 1次因式相乘，得到 GF(2)域的一個(gè)既約因式。 結(jié)論：非本原多項(xiàng)式是不僅是 xn 1的因式，也 xm 1的因式。 (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è)根。 因此， 本原類的最小多項(xiàng)式是本原多項(xiàng)式，非本原類的最小多項(xiàng)式是非本原多項(xiàng)式 。 本原類的類序號(hào) i與 n互素，非本原類的類序號(hào) i與 n可約。 類 根 循環(huán)級 是否本原 最小多項(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)級 m的關(guān)系是： 2r mod m=1 (3)本原類與非本原類： 共厄類是以根的平方（即自乘）關(guān)系劃分的，自乘不會(huì)改變冪次與 n互素或可約的本性，所以 同一共厄類中的根，本原屬性相同。我們 把通過自乘能回到 α0 =1 的最小自乘次數(shù) m叫做該類元素的循環(huán)級。 (2)本原根與非本原根的循環(huán)性： 因?yàn)?αk是 xn=1的根，所以 (αk)n =1，不論本原與非非本原，任何一個(gè)根自乘 n次必然等于 1。 我們把它 叫做 i=5類對應(yīng)的最小多項(xiàng)式，記作： m5(x)= x2 + x+1； 同理，屬于每個(gè)共厄類的各 1次因式相乘，都可得到 GF(2) 域中一個(gè) 相應(yīng) 的 最小多項(xiàng)式 ，其冪次等于 共厄類中根的個(gè)數(shù)： m1(x)=(x α)(x –α2 )(x –α4)(x –α8 )= x4 + x+1； m3(x)=(x –α3)(x –α6 )(x –α9)(x –α12 )= x4 +x3 +x2 + x+1； m5(x)=(x α5)(x α10 )=x2 + x+1； m7(x)=(x –α7)(x –α11 )(x –α13)(x –α14 )= x4 +x3 +1； m0(x)= (x –α0) = x+1 于是： x151=m0(x)m1(x)m3(x)m5(x)m7(x)= =(x+1)(x4 + x+1)(x4 +x3 +x2 + x+1)(x2 + x+1)(x4 +x3 +1) ： (1)本原根與非本原根： xn=1的 n個(gè)根 α0 =1 ,α,α2, ……,α n1 可分為 本原根與非 本原根兩種，二者 的 區(qū)別是看 能否由 αk 的一切冪次生成 xn=1 的全部根。 GF(2)域只有 0和 1兩個(gè)數(shù)字，其它數(shù)是不存在的。 GF(2)域中的分解： 因式分解與定義域是密切關(guān)聯(lián)的。 i=3的類包含： α3， α6， α12， α24 =α9這 4個(gè)根； α48 =α3， α96 =α6， …… 又會(huì)重復(fù)出現(xiàn) 這 4個(gè)根。 不妨以 n=15, x151=0的 15個(gè)根為例。 令： α= e j 2π/n ； 則： xk = αk ( k=0,1,…… ， n1 ) 于是： 結(jié)論：復(fù)數(shù)域中 xn1分解為 n個(gè) 1次因式的乘積。e j ： 分解 xn1， 相當(dāng)于求方程 xn1=0的根 ； 如 x21=0的根是 x=1和 x=1， 則 x21=(x1)(x+1) 同理若 xn1=0的 n個(gè)根是 x = x1 ,x2 ,… ,xn， 則： xn1= (x x1)(x x2)…… (x –xn)； 顯然，由 xn = 1知 ， 這 n個(gè)根應(yīng)當(dāng)是 1的 n次方根。 （ 4）所有奇數(shù)個(gè)錯(cuò)位。 （ 2）相當(dāng)一部分連續(xù)長度大于 nk+1的突發(fā)錯(cuò)誤。(x16+x2+x+1) 循環(huán)冗余校驗(yàn)碼不僅實(shí)現(xiàn)起來比較簡單，而且具有很強(qiáng)的檢測能力。 常取 r =16 ，這時(shí) g (x) = x16+x12+x5+1 =10001000000100001(B)=11021(H) g (x)作為最輕的碼字，它的重量為 4，表明該碼組中最小漢明距離 d 0= 4，能糾正 1位差錯(cuò)同時(shí)還能檢查到第 2位差錯(cuò)。 數(shù)據(jù)的長短往往不確定 ， 但校驗(yàn)位的長度 r卻是固定的 。 循環(huán)冗余校驗(yàn)碼 (CRC) Cyclic Redundancy Cheek 循環(huán)冗余校驗(yàn)碼是截短循環(huán)碼的一個(gè)典型應(yīng)用。 截短循環(huán)碼具有循環(huán)碼的許多結(jié)構(gòu)特點(diǎn) ， 監(jiān)督位沒有變 ， 糾錯(cuò)能力不變 ， 糾錯(cuò)方法不變等 。 截短循環(huán)碼的普遍表達(dá)是 (ni, ki)， i是截短位數(shù)，監(jiān)督位長度 r=(ni)(ki)=nk不變。 相對于原來的循環(huán)碼， 信息位與碼長被同步地減小了 。比如 x 51 中就不含 r=2和r=3的因子，難以構(gòu)造 (5,2)碼。 截短循環(huán)碼 求生成多項(xiàng)式，需要分解 xn1，但只有 n=2m1的數(shù)才能查表分解，這就限制了 n的取值。 如果出現(xiàn)兩位錯(cuò)時(shí)，由 S=RHT=EHT ，而 E中有兩列為 1， 致使 s4=e7+e6+e5+e4+e3+e2 +e1 +e0 必然為 0，就表明有兩個(gè)錯(cuò)。 如 (7, 4)碼改為 (8, 4)碼，第 8列的碼元滿足偶校驗(yàn)關(guān)系： c7= c6+c5+c4+c3+c2+c1+c0； 一致監(jiān)督矩陣由 H(7,3)變?yōu)?H(8,4) ： 校驗(yàn)矩陣增加全 1的一行，當(dāng)計(jì)算 S=RHT時(shí)，該列的計(jì)算是 s4= c7+c6+c5+c4+c3+c2+c1+c0,對于偶校驗(yàn)，如果是正確碼字結(jié)果必然為 0。 k (x) + r (x)； 循環(huán)碼的譯碼： （ 1） 根據(jù) S(x) = E(x) mod g(x)； 算出糾錯(cuò)能力 t 位