BCH码

维基百科，自由的百科全书

BCH 码取自 Bose、Ray-Chaudhuri 与 Hocquenghem 的缩写，是编码理论尤其是纠错码中研究得比较多的一种编码方法。用技术的术语来说，BCH 码是用于校正多个随机错误模式的多级、循环、错误校正、变长数字编码。BCH 码也可以用于质数级或者质数的幂级的多级相移键控。11 级的 BCH 码已经用于表示 10 进制数外加一个符号位。

目录 1 构建 2 编码 3 解码 4 BCH 解码算法 5 Peterson Gorenstein Zierler 算法 5.1 假设 5.2 算法 6 错误定位多项式的因式分解 7 错误校正 8 参考文献

[编辑] 构建

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

The BCH code with designed distance δ over the field GF(q^m) is constructed by first finding a polynomial over GF(q) whose roots include δ consecutive powers of γ, some root of unity.

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

m₁(x) = (x - α)(x - α²)(x - α⁴)(x - α⁸)=x⁴ + x + 1。

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

C(x) ≡ 0 (mod m₁(x))

且根为 α, α², α⁴, α⁸ 的多项式 C(x)。

This does not allow us to choose many codewords - so we look for the minimal polynomial for the missing power of α from above - α³, and then the minimal polynomial for this is

m₃(x) = x⁴ + x³ + x² + x + 1.

which has roots α³, α⁶, α¹², α²⁴=α⁹.

We take codewords having all of these as roots, so we form the polynomial

m_1,3(x) = m₁(x)m₃(x) = x⁸ + x⁷ + x⁶ + x⁴+1

and take codewords corresponding to polynomials of degree 14 such that

C(x) ≡ 0 (mod m_1,3(x))

So now C(α) = C(α²) = ... = C(α⁸) = 0. (*)

Now in GF(16) we have 15 nonzero elements, and thus our polynomial will be of degree 14 with 8 check and 7 information bits - we have 8 check bits since we have (*).

[编辑] 编码

构建码字为

(c₁₄, c₁₃, ..., c₈)

这样多项式为

c₁₄+c₁₃+...+c₈

我们将它称为 C_I。

然后就要找出 C_R 满足 C_R=C_I (mod m_1,3(x))=c₇+c₆+...+c₀

这样就得到待发的码字 C(x) = C_I+C_R (mod m_1,3(x)) = 0

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

C_I=x¹⁴+x¹³+x¹⁰+x⁹

and using polynomial long division of m_1,3(x) and C_I to get C_R(x), in Z₂ we obtain C_R to be

x³+1

这样，待发的码字为

(1,1,0,0,1,1,0, 0,0,0,0,1,0,0,1)

[编辑] 解码

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

1. 计算接收到的向量 R 的 2t 伴随矩阵
2. 计算错误定位多项式
3. 解多项式，得到错误位置
4. 如果不是二进制 BCH 码，就计算错误位置的误差值

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

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

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

S₁=R(α)=C(α)+αⁱ=αⁱ

S₃=R(α³)=C(α³)+(α³)ⁱ

=(αⁱ)³=S₁³

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

如果有两个错误

r=c+e_i+e_j

那么

S₁=R(α)=C(α)+αⁱ+α^j

S₃=R(α³)=C(α³)+(α³)ⁱ+(α³)^j

= (α³)ⁱ+(α³)^j

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

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

上面的文字摘自：http://bch-code.foosquare.com/

[编辑] BCH 解码算法

流行的解码算法有，

1. Peterson Gorenstein Zierler 算法
2. Berlekamp-Massey 算法

[编辑] Peterson Gorenstein Zierler 算法

[编辑] 假设

Peterson 算法是普通 BCH 解码过程的第二步，这这里使用 Peterson 算法计算多项式 Λ(x) = 1 + λ₁X + λ₂X² + ... + λ_2tX^2t 的错误定位多项式系数 λ₁,λ₂...λ_2t

这样给定 BCH 码 (n,k,d_min)，可以校正 个错误的 Peterson Gorenstein Zierler 算法就是

[编辑] 算法

• 首先生成 2t 伴随矩阵
• 然后生成元素为

的矩阵 S_txt

• 生成元素为

的矩阵 c_tx1

• 让 Λ 表示未知的多项式系数，用

表示

• 这样就得到矩阵方程

• 如果矩阵 存在行列式，那么我们就可以找到这个矩阵的逆，然后就可以得到 Λ 的值

• 如果 , 那么按照

       if t = 0
       then
             declare an empty error locator polynomial
             stop Peterson procedure.
       end
       set 
       continue from the beginning of Peterson's decoding

• 在 Λ 的值确定之后，自然就得到错误定位多项式
• 结束 Peterson procedure。

[编辑] 错误定位多项式的因式分解

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

[编辑] 错误校正

对于二进制的 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: http://federal-standard-1037c.foosquare.com/
• Galois Field Calculator: http://www.geocities.com/myopic_stargazer/gf_calc.zip
• Decoding Algorithms for BCH codes: http://students.uta.edu/mx/mxa6471/research/ecc-report.pdf
• Source code for BCH channel simulation: http://students.uta.edu/mx/mxa6471/research/ecc-code.tgz