近世代数理论基础40：BCH码

2019-03-18 本文已影响4人溺于恐

BCH码

纠错码

数字信息传输过程中可能受干扰导致出错,为了正确传送信息,采用抗干扰编码的方法,在信息传输之前进行一次抗干扰编码然后再发送编码后的信息,收信者收信后可根据编码的功能进行检错和纠错,该编码称为纠错码

线性码

线性码是最常用的一类纠错码

一个线性码 $\mathcal{C}$ 即 $F_2$ 上n维向量空间 $F_2^n$ 中一个 $k(\lt n)$ 维子空间,也可用一般的有限域 $F_q$ 代替 $F_2$ ,但数字通信中常用 $F_2$

$\mathcal{C}$ 中的每个向量称为码字,设 $c=(c_0,c_1,\cdots,c_{n-1})(c_i\in F_2)$ 是 $\mathcal{C}$ 中的一个码字,它的非零分量根叔定义为重量,记作 $w(c)$ ,即 $w(c)=\#\{c_i|c_i\neq 0,0\le i\le n-1\}$

定义 $\mathcal{C}$ 的最小重量维 $d(\mathcal{C})=min\{w(c)|c\in \mathcal{C},c\neq 0\}$ , $\forall c,c’\in \mathcal{C}$ ,定义 $c,c’$ 的距离为 $d(c,c’)=w(c-c’)$

$\mathcal{C}$ 是线性码,故 $d(\mathcal{C})=min\{w(c-c’)|c,c’\in\mathcal{C},c\neq c’\}$ , $d(\mathcal{C})$ 也称为 $\mathcal{C}$ 的最小距离

$d(\mathcal{C})$ 是决定 $\mathcal{C}$ 的纠错功能的重要参数, $d(\mathcal{C})$ 越大, $\mathcal{C}$ 的纠错功能越强

设计线性码时,希望它的最小重量能达到一定要求

利用有限域设计BCH码

BCH码是一类线性码

令 $n=2^m-1$ , $F_2$ 上任一n维向量 $c=(c_0,c_1,\cdots,c_{n-1}),c_i\in F_2$ ,对应 $F_2$ 上一个次数不超过 $n-1$ 的多项式 $c(x)=c_0+c_1x+\cdots+c_{n-1}x^{n-1}\in F_2[x]$

故一个码字也可用一个多项式表示

设 $\beta$ 为 $F_{2^m}$ 的一个本原元, $d\in Z_+,d\le n$

定义 $\mathcal{C}=\{c(x)\in F_2[x]|deg c(x)\le n-1,c(\beta^i)=0,1\le i\le d-1\}$

若 $c(x),c’(x)\in \mathcal{C}$ ,则显然 $c(x)+c’(x)\in \mathcal{C}$ , $\mathcal{C}$ 对应 $F_2^n$ 中的一个线性子空间,是一个线性码

定义 $F_{2^m}$ 上一个 $(d-1)\times n$ 矩阵

$H=\begin{pmatrix}1&\beta&\beta^2&\cdots&\beta^{n-1}\\ 1&\beta^2&\beta^{2\cdot 2}&\cdots&\beta^{2\cdot(n-1)}\\ \vdots&\vdots&\vdots& &\vdots\\ 1&\beta^{d-1}&\beta^{(d-1)\cdot 2}&\cdots&\beta^{(d-1)\cdot(n-1)}\end{pmatrix}$