构建

BCH 码使用有限域上的域论与多项式。为了检测错误可以构建一个检测多项式，这样接收端就可以检测是否有错误发生。

要构建一个能够检测、校正两个错误的 BCH 码，我们要使用有限域GF(16) 或者 Z2[x]／。如果 α 是 m1(x) = x + x + 1 的一个根，那么 m1 就是 α 的极小多项式，这是因为

如果要构建一个能够纠正一个错误的 BCH 码，那么就使用 m1(x)，这个代码就是所有满足

编码

构建码字为

这样多项式为

我们将它称为 CI。

然后就要找出 CR 满足 CR=CI (mod m1,3(x))=c7+c6+...+c0

这样就得到待发的码字 C(x) = CI+CR (mod m1,3(x)) = 0

例如，如果我们要对 (1,1,0,0,1,1,0) 进行编码

然后用 m1,3(x) 除以（这里的除法是多项式除法）CI ，得到结果为 CR(x)，在Z2域中，我们可以算出 CR为

这样，待发的码字为

解码

BCH 的解码过程可以分为以下四步

计算接收到的向量 R 的 2t 伴随矩阵

计算错误定位多项式

解多项式，得到错误位置

如果不是二进制 BCH 码，就计算错误位置的误差值

假设我们收到一个码字向量 r，即多项式 R(x)）。

如果没有错误，那么 R(α)=R(α)=0

如果有一个错误，例如 r=c+ei，其中 ei 表示 R 的第 i个基向量 于是

这样就可以纠正错误。α 的指数显示的数据位变化可以帮助我们校正错误。

如果有两个错误

那么

这与 S1 不同，所以我们认为有两个错误。更进一步的代数方法可以帮助校正着两个错误。

开头两段内容出自 Federal Standard 1037C

上面的文字摘自：/

BCH 解码算法

流行的解码算法有，

Peterson Gorenstein Zierler 算法

Berlekamp-Massey 算法

Peterson Gorenstein Zierler 算法

假设

Peterson 算法是普通 BCH 解码过程的第二步，在这里使用 Peterson 算法计算多项式 Λ Λ -->(x)=1+λ λ -->1X+λ λ -->2X2+...+λ λ -->2tX2t{\displaystyle \Lambda (x)=1+\lambda _{1}X+\lambda _{2}X^{2}+...+\lambda _{2t}X^{2t}} 的错误定位多项式系数 λ λ -->1,λ λ -->2...λ λ -->2t{\displaystyle \lambda _{1},\lambda _{2}...\lambda _{2t}}

这样给定 BCH 码 (n,k,dmin){\displaystyle (n,k,d_{min})}，可以校正 [t=dmin− − -->12]{\displaystyle [t={\frac {d_{min}-1}{2}}]} 个错误的 Peterson Gorenstein Zierler 算法就是

算法

首先生成 2t{\displaystyle 2t} 伴随矩阵

然后生成元素为

St× × -->t=[s2s3...sts2s3s4......st+3s4s5...st+2...............stst+t+2...s2t− − -->1]{\displaystyle S_{t\times t}={\begin{bmatrix}s_{1}&s_{2}&s_{3}&...&s_{t}\\s_{2}&s_{3}&s_{4}...&...&s_{t+1}\\s_{3}&s_{4}&s_{5}&...&s_{t+2}\\...&...&...&...&...\\s_{t}&s_{t+1}&s_{t+2}&...&s_{2t-1}\end{bmatrix}}} 的矩阵 Stxt{\displaystyle S_{txt}}

生成元素为

Ct× × -->1=[st+t+2......s2t]{\displaystyle C_{t\times 1}={\begin{bmatrix}s_{t+1}\\s_{t+2}\\...\\...\\s_{2t}\end{bmatrix}}} 的矩阵 ctx1{\displaystyle c_{tx1}}

让 Λ Λ -->{\displaystyle \Lambda } 表示未知的多项式系数，用

Λ Λ -->t× × -->1=[λ λ -->tλ λ -->t− − -->1...λ λ -->3λ λ -->2λ λ -->1]{\displaystyle \Lambda _{t\times 1}={\begin{bmatrix}\lambda _{t}\\\lambda _{t-1}\\...\\\lambda _{3}\\\lambda _{2}\\\lambda _{1}\end{bmatrix}}} 表示

这样就得到矩阵方程

St× × -->tΛ Λ -->t× × -->1=Ct× × -->1{\displaystyle S_{t\times t}\Lambda _{t\times 1}=C_{t\times 1}}

如果矩阵 St× × -->t{\displaystyle S_{t\times t}} 存在行列式，那么我们就可以找到这个矩阵的逆，然后就可以得到 Λ Λ -->{\displaystyle \Lambda } 的值

如果 det(St× × -->t)=0{\displaystyle det(S_{t\times t})=0}，那么按照

在 Λ Λ -->{\displaystyle \Lambda } 的值确定之后，自然就得到错误定位多项式

结束 Peterson procedure。

错误定位多项式的因式分解

在得到 Λ Λ -->(x){\displaystyle \Lambda (x)} 多项式之后，用 Chiens search 算法就可以得到它的解 Λ Λ -->(x)=(α α -->iX+1)(α α -->jX+1)...(α α -->kX+1){\displaystyle \Lambda (x)=(\alpha ^{i}X+1)(\alpha ^{j}X+1)...(\alpha ^{k}X+1)}。根据素元 α α -->{\displaystyle \alpha } 的指数幂就能得到接收到的码字中错误的位置，这也就是误差定位多项式名称的由来。

错误校正

对于二进制的 BCH 码，可以直接根据错误定位多项式因数素元指数的位置校正接收到的向量。最后，对这些位置接收到的数值取反，就可以得到正确的 BCH 解码码字。

另外也可以使用 Berlekamp-Massey 算法确定错误定位多项式，从而解决 BCH 解码的问题。

参考文献

S. Lin and D. Costello. Error Control Coding: Fundamentals and Applications. Prentice-Hall, Englewood Cliffs, NJ, 2004.

Step by step decoding instructions(pdf file).

Federal Standard 1037c:/

Galois Field Calculator:tp_calc.zip

Decoding Algorithms for BCH codes:port.pdf

Source code for BCH channel simulation:z

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。