BCH碼
糾錯(cuò)碼
數(shù)字信息傳輸過(guò)程中可能受干擾導(dǎo)致出錯(cuò),為了正確傳送信息,采用抗干擾編碼的方法,在信息傳輸之前進(jìn)行一次抗干擾編碼然后再發(fā)送編碼后的信息,收信者收信后可根據(jù)編碼的功能進(jìn)行檢錯(cuò)和糾錯(cuò),該編碼稱為糾錯(cuò)碼
線性碼
線性碼是最常用的一類糾錯(cuò)碼
一個(gè)線性碼
即
上n維向量空間
中一個(gè))
維子空間,也可用一般的有限域
代替,但數(shù)字通信中常用
中的每個(gè)向量稱為碼字,設(shè)(c_i%5Cin%20F_2))
是中的一個(gè)碼字,它的非零分量根叔定義為重量,記作)
,即%3D%5C%23%5C%7Bc_i%7Cc_i%5Cneq%200%2C0%5Cle%20i%5Cle%20n-1%5C%7D)
定義的最小重量維%3Dmin%5C%7Bw(c)%7Cc%5Cin%20%5Cmathcal%7BC%7D%2Cc%5Cneq%200%5C%7D)
,
,定義
的距離為%3Dw(c-c%E2%80%99))
是線性碼,故%3Dmin%5C%7Bw(c-c%E2%80%99)%7Cc%2Cc%E2%80%99%5Cin%5Cmathcal%7BC%7D%2Cc%5Cneq%20c%E2%80%99%5C%7D)
,)
也稱為的最小距離
是決定的糾錯(cuò)功能的重要參數(shù),越大,的糾錯(cuò)功能越強(qiáng)
設(shè)計(jì)線性碼時(shí),希望它的最小重量能達(dá)到一定要求
利用有限域設(shè)計(jì)BCH碼
BCH碼是一類線性碼
令
,上任一n維向量%2Cc_i%5Cin%20F_2)
,對(duì)應(yīng)上一個(gè)次數(shù)不超過(guò)
的多項(xiàng)式![c(x)=c_0+c_1x+\cdots+c_{n-1}x^{n-1}\in F_2[x]](https://math.jianshu.com/math?formula=c(x)%3Dc_0%2Bc_1x%2B%5Ccdots%2Bc_%7Bn-1%7Dx%5E%7Bn-1%7D%5Cin%20F_2%5Bx%5D)
故一個(gè)碼字也可用一個(gè)多項(xiàng)式表示
設(shè)
為
的一個(gè)本原元,
定義![\mathcal{C}=\{c(x)\in F_2[x]|deg c(x)\le n-1,c(\beta^i)=0,1\le i\le d-1\}](https://math.jianshu.com/math?formula=%5Cmathcal%7BC%7D%3D%5C%7Bc(x)%5Cin%20F_2%5Bx%5D%7Cdeg%20c(x)%5Cle%20n-1%2Cc(%5Cbeta%5Ei)%3D0%2C1%5Cle%20i%5Cle%20d-1%5C%7D)
若%2Cc%E2%80%99(x)%5Cin%20%5Cmathcal%7BC%7D)
,則顯然%2Bc%E2%80%99(x)%5Cin%20%5Cmathcal%7BC%7D)
,對(duì)應(yīng)中的一個(gè)線性子空間,是一個(gè)線性碼
定義上一個(gè)%5Ctimes%20n)
矩陣
%7D%5C%5C%20%5Cvdots%26%5Cvdots%26%5Cvdots%26%20%26%5Cvdots%5C%5C%201%26%5Cbeta%5E%7Bd-1%7D%26%5Cbeta%5E%7B(d-1)%5Ccdot%202%7D%26%5Ccdots%26%5Cbeta%5E%7B(d-1)%5Ccdot(n-1)%7D%5Cend%7Bpmatrix%7D)
則%3Dc_0%2Bc_1x%2B%5Ccdots%2Bc_%7Bn-1%7Dx%5E%7Bn-1%7D%5Cin%20%5Cmathcal%7BC%7D%5CLeftrightarrow%20(c_0%2Cc_1%2C%5Ccdots%2Cc_%7Bn-1%7D)%5Ccdot%20H%5ET%3D0)
其中
表示H的轉(zhuǎn)置矩陣
是本原元,故)
互不相同
H的任意d-1列所決定的子矩陣的行列式是一個(gè)非取零值的Vandermonde行列式
故
的任意d-1列都線性無(wú)關(guān)
故
,有%5Cge%20d)
故的最小重量%5Cge%20d)
,d稱為的設(shè)計(jì)距離
令)
為
在上的極小多項(xiàng)式,)
為%2Cg_2(x)%2C%5Ccdots%2Cg_%7Bd-1%7D(x))
的最小公倍式
%7Cx%5En-1)
,
無(wú)重根,n為奇數(shù),故%7Cx%5En-1)
線性碼也可定義為![\mathcal{C}=\{f(x)g(x)(mod\;x^n-1)|f(x)\in F_2[x]\}\\=\{f(x)g(x)|deg\;f(x)\lt n-deg\;g(x),f(x)\in F_2[x]\}](https://math.jianshu.com/math?formula=%5Cmathcal%7BC%7D%3D%5C%7Bf(x)g(x)(mod%5C%3Bx%5En-1)%7Cf(x)%5Cin%20F_2%5Bx%5D%5C%7D%5C%5C%3D%5C%7Bf(x)g(x)%7Cdeg%5C%3Bf(x)%5Clt%20n-deg%5C%3Bg(x)%2Cf(x)%5Cin%20F_2%5Bx%5D%5C%7D)
理解為在環(huán)![F_2[x]/(x^n-1)](https://math.jianshu.com/math?formula=F_2%5Bx%5D%2F(x%5En-1))
中生成的理想
設(shè))
為的一個(gè)碼字
%3Dx(c_0%2Bc_1x%2B%5Ccdots%2Bc_%7Bn-1%7Dx%5E%7Bn-1%7D))
)
故)
也是的一個(gè)碼字
具有該性質(zhì)的糾錯(cuò)碼稱為循環(huán)碼,BCH碼是循環(huán)碼
例：設(shè)
,令是
的一個(gè)本原元,定義BCH碼![\mathcal{C}=\{c(x)\in F_2[x]|deg\;c(x)\le 30,c(\beta^i)=0,1\le i\le 7\}](https://math.jianshu.com/math?formula=%5Cmathcal%7BC%7D%3D%5C%7Bc(x)%5Cin%20F_2%5Bx%5D%7Cdeg%5C%3Bc(x)%5Cle%2030%2Cc(%5Cbeta%5Ei)%3D0%2C1%5Cle%20i%5Cle%207%5C%7D)
碼的設(shè)計(jì)距離為8,令(1%5Cle%20i%5Cle%207))
為在上的極小多項(xiàng)式
為%2Cg_2(x)%2C%5Ccdots%2Cg_7(x))
的最小公倍式,則
%3D(x-%5Cbeta)(x-%5Cbeta%5E2)(x-%5Cbeta%5E4)(x-%5Cbeta%5E8)(x-%5Cbeta%5E%7B16%7D))
%3D(x-%5Cbeta%5E3)(x-%5Cbeta%5E6)(x-%5Cbeta%5E%7B12%7D)(x-%5Cbeta%5E%7B24%7D)(x-%5Cbeta%5E%7B17%7D))
%3D(x-%5Cbeta%5E5)(x-%5Cbeta%5E%7B10%7D)(x-%5Cbeta%5E%7B20%7D)(x-%5Cbeta%5E9)(x-%5Cbeta%5E%7B18%7D))
%3D(x-%5Cbeta%5E7)(x-%5Cbeta%5E%7B14%7D)(x-%5Cbeta%5E%7B28%7D)(x-%5Cbeta%5E%7B25%7D)(x-%5Cbeta%5E%7B19%7D))
故%3D0%2C1%5Cle%20i%5Cle%2010)
,故碼的最小距離至少為11
