BCH码
纠错码
数字信息传输过程中可能受干扰导致出错,为了正确传送信息,采用抗干扰编码的方法,在信息传输之前进行一次抗干扰编码然后再发送编码后的信息,收信者收信后可根据编码的功能进行检错和纠错,该编码称为纠错码
线性码
线性码是最常用的一类纠错码
一个线性码
即
上n维向量空间
中一个)
维子空间,也可用一般的有限域
代替,但数字通信中常用
中的每个向量称为码字,设(c_i%5Cin%20F_2))
是中的一个码字,它的非零分量根叔定义为重量,记作)
,即%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)
,)
也称为的最小距离
是决定的纠错功能的重要参数,越大,的纠错功能越强
设计线性码时,希望它的最小重量能达到一定要求
利用有限域设计BCH码
BCH码是一类线性码
令
,上任一n维向量%2Cc_i%5Cin%20F_2)
,对应上一个次数不超过
的多项式![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)
故一个码字也可用一个多项式表示
设
为
的一个本原元,
定义![\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)
,对应中的一个线性子空间,是一个线性码
定义上一个%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的转置矩阵
是本原元,故)
互不相同
H的任意d-1列所决定的子矩阵的行列式是一个非取零值的Vandermonde行列式
故
的任意d-1列都线性无关
故
,有%5Cge%20d)
故的最小重量%5Cge%20d)
,d称为的设计距离
令)
为
在上的极小多项式,)
为%2Cg_2(x)%2C%5Ccdots%2Cg_%7Bd-1%7D(x))
的最小公倍式
%7Cx%5En-1)
,
无重根,n为奇数,故%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)
理解为在环![F_2[x]/(x^n-1)](https://math.jianshu.com/math?formula=F_2%5Bx%5D%2F(x%5En-1))
中生成的理想
设)
为的一个码字
%3Dx(c_0%2Bc_1x%2B%5Ccdots%2Bc_%7Bn-1%7Dx%5E%7Bn-1%7D))
)
故)
也是的一个码字
具有该性质的纠错码称为循环码,BCH码是循环码
例：设
,令是
的一个本原元,定义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)
码的设计距离为8,令(1%5Cle%20i%5Cle%207))
为在上的极小多项式
为%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
网友评论