查看“︁BCH码”︁的源代码

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

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

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

如果要构建一个能够纠正一个错误的 BCH 码，那么就使用 ''m''<sub>1</sub>(''x'')，这个代码就是所有满足
: ''C''(''x'') ≡ 0（mod ''m''<sub>1</sub>(''x'')）且根为 α, α<sup>2</sup>, α<sup>4</sup>, α<sup>8</sup> 的多项式 ''C''(''x'')。

== 编码 ==
构建码字为 
: (''c''<sub>14</sub>, ''c''<sub>13</sub>, ..., ''c''<sub>8</sub>)
这样多项式为
: ''c''<sub>14</sub>+''c''<sub>13</sub>+...+''c''<sub>8</sub>
我们将它称为 ''C''<sub>I</sub>。

然后就要找出 ''C''<sub>R</sub> 满足
''C''<sub>R</sub>=''C''<sub>I</sub> (mod ''m''<sub>1,3</sub>(''x''))=''c''<sub>7</sub>+''c''<sub>6</sub>+...+''c''<sub>0</sub>

这样就得到待发的码字
''C''(''x'') = ''C''<sub>I</sub>+''C''<sub>R</sub> (mod ''m''<sub>1,3</sub>(''x'')) = 0 

例如，如果我们要对 (1,1,0,0,1,1,0) 进行编码
: ''C''<sub>I</sub>=''x''<sup>14</sup>+''x''<sup>13</sup>+''x''<sup>10</sup>+''x''<sup>9</sup>
然后用 ''m''<sub>1,3</sub>(''x'') 除以（这里的除法是[[多项式除法]]）''C''<sub>I</sub> ，得到结果为 ''C''<sub>R</sub>(''x'')，在'''Z'''<sub>2</sub>域中，我们可以算出 ''C''<sub>R</sub>为
: ''x''<sup>3</sup>+1
这样，待发的码字为
:(1,1,0,0,1,1,0, 0,0,0,0,1,0,0,1)

== 解码 ==
BCH 的解码过程可以分为以下四步
# 计算接收到的向量 R 的 2t 伴随矩阵
# 计算错误定位多项式
# 解多项式，得到错误位置
# 如果不是二进制 BCH 码，就计算错误位置的误差值

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

如果没有错误，那么 R(α)=R(α<sup>3</sup>)=0

如果有一个错误，例如 '''r'''='''c'''+'''e'''<sub>i</sub>，其中 '''e'''<sub>''i''</sub> 表示 '''R'''<sup>14</sup> 的第 ''i''个基向量
于是
:''S''<sub>1</sub>=''R''(α)=''C''(α)+α<sup>''i''</sup>=α<sup>i</sup>
:''S''<sub>3</sub>=''R''(α<sup>3</sup>)=C(α<sup>3</sup>)+(α<sup>3</sup>)<sup>i</sup>
:: =(α<sup>i</sup>)<sup>3</sup>=''S''<sub>1</sub><sup>3</sup>
这样就可以纠正错误。α 的指数显示的数据位变化可以帮助我们校正错误。

如果有两个错误
:'''r'''='''c'''+'''e'''<sub>''i''</sub>+'''e'''<sub>''j''</sub> 
那么
:''S''<sub>1</sub>=''R''(α)=''C''(α)+α<sup>''i''</sup>+α<sup>''j''</sup>
:''S''<sub>3</sub>=''R''(α<sup>3</sup>)=C(α<sup>3</sup>)+(α<sup>3</sup>)<sup>''i''</sup>+(α<sup>3</sup>)<sup>''j''</sup>
:: = (α<sup>3</sup>)<sup>''i''</sup>+(α<sup>3</sup>)<sup>''j''</sup>
这与 ''S''<sub>1</sub><sup>3</sup> 不同，所以我们认为有两个错误。更进一步的代数方法可以帮助校正着两个错误。

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

上面的文字摘自：https://web.archive.org/web/20070213013106/http://bch-code.foosquare.com/

== BCH 解码算法 ==
流行的解码算法有，
# Peterson Gorenstein Zierler算法
# Berlekamp-Massey算法

== Peterson Gorenstein Zierler 算法 ==
=== 假设 ===
Peterson 算法是普通 BCH 解码过程的第二步，在这里使用 Peterson 算法计算多项式 <math> \Lambda(x) = 1 + \lambda_1 X + \lambda_2 X^2 + ... + \lambda_{2t}X^{2t} </math> 的错误定位多项式系数 <math> \lambda_1 , \lambda_2  ... \lambda_{2t} </math>

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

=== 算法 ===
* 首先生成 <math>2t</math> 伴随矩阵
* 然后生成元素为 
<math>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}</math>
的矩阵 <math>S_{txt}</math>

* 生成元素为 
<math>C_{t \times 1}=\begin{bmatrix}s_{t+1}\\
s_{t+2}\\
...\\
...\\
s_{2t}\end{bmatrix}
</math>
的矩阵 <math>c_{tx1}</math>
* 让 <math>\Lambda</math> 表示未知的多项式系数，用
<math>\Lambda_{t \times 1} = \begin{bmatrix}\lambda_{t}\\
\lambda_{t-1}\\
...\\
\lambda_{3}\\
\lambda_{2}\\
\lambda_{1}\end{bmatrix}
</math>
表示
* 这样就得到矩阵方程 
<math>S_{t \times t} \Lambda_{t \times 1}  = C_{t \times 1} </math>

* 如果矩阵 <math>S_{t \times t}</math> 存在行列式，那么我们就可以找到这个矩阵的逆，然后就可以得到 <math>\Lambda</math> 的值

* 如果 <math> det(S_{t \times t}) = 0 </math>，那么按照
        if <math>t = 0</math>
        then
              declare an empty error locator polynomial
              stop Peterson procedure.
        end
        set <math> t \leftarrow t -1</math>
        continue from the beginning of Peterson's decoding
 
* 在 <math>\Lambda</math> 的值确定之后，自然就得到错误定位多项式
* 结束 Peterson procedure。

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

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

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

== 參考文獻 ==
{{refbegin|2}}
===主要參考===
* {{Citation
 |first= A.
 |last= Hocquenghem
 |author-link= Alexis Hocquenghem
 |title=Codes correcteurs d'erreurs
 |language= fr
 |journal= Chiffres
 |location= Paris
 |volume=2
 |pages= 147–156
 |date= September 1959
 |issn=
 |doi=}}
* {{Citation
 |first= R. C.
 |last= Bose
 |author-link= R. C. Bose
 |first2= D. K.
 |last2= Ray-Chaudhuri
 |author2-link= D. K. Ray-Chaudhuri
 |title= On A Class of Error Correcting Binary Group Codes
 |journal= [[Information and Control]]
 |volume= 3
 |issue=1
 |pages= 68–79
 |date= March 1960
 |issn= 0890-5401
 |doi=10.1016/s0019-9958(60)90287-4}}

===次要參考===
* {{Citation |last=Gill |first=John |title=EE387 Notes #7, Handout #28 |date=n.d. |accessdate=April 21, 2010 |pages=42–45 |publisher=Stanford University |url=http://www.stanford.edu/class/ee387/handouts/notes7.pdf |doi= |deadurl=yes |archiveurl=https://web.archive.org/web/20140630172526/http://web.stanford.edu/class/ee387/handouts/notes7.pdf |archivedate=2014年6月30日 |df= }}{{cbignore|bot=medic}} Course notes are apparently being redone for 2012: http://www.stanford.edu/class/ee387/{{Wayback|url=http://www.stanford.edu/class/ee387/ |date=20130605170343 }}
* {{Citation
 |last= Gorenstein
 |first= Daniel
 |authorlink= Daniel Gorenstein
 |last2= Peterson
 |first2= W. Wesley
 |authorlink2= W. Wesley Peterson
 |last3= Zierler
 |first3 = Neal
 |authorlink3= Neal Zierler
 |title= Two-Error Correcting Bose-Chaudhuri Codes are Quasi-Perfect
 |journal= Information and Control
 |volume= 3
 |issue= 3
 |pages= 291–294
 |year= 1960
 |doi= 10.1016/s0019-9958(60)90877-9}}
* {{Citation
 |first= Rudolf
 |last= Lidl
 |first2= Günter
 |last2= Pilz
 |title= Applied Abstract Algebra
 |edition= 2nd
 |publisher= John Wiley
 |year= 1999
 |url=
 |isbn=
 |doi=}}
* {{Citation
 |first= Irving S.
 |last= Reed
 |authorlink= Irving S. Reed
 |first2= Xuemin
 |last2= Chen
 |title= Error-Control Coding for Data Networks
 |location= Boston, MA
 |publisher= [[Kluwer Academic Publishers]]
 |year= 1999
 |isbn= 0-7923-8528-4
 |doi=}}
{{refend}}

==延伸閱讀==
{{refbegin|2}}
* {{Citation |last1=Blahut |first1=Richard E. |author-link1=Richard Blahut |title=Algebraic Codes for Data Transmission |edition=2nd |publisher=[[Cambridge University Press]] |year=2003 |isbn=0-521-55374-1}}
* {{Citation
 |first= W. J.
 |last= Gilbert
 |first2= W. K.
 |last2= Nicholson
 |title= Modern Algebra with Applications
 |edition= 2nd
 |publisher= John Wiley
 |year= 2004
 |url=
 |isbn=
 |doi=}}
* {{Citation
 |first= S.
 |last= Lin
 |first2= D.
 |last2= Costello
 |title= Error Control Coding: Fundamentals and Applications
 |publisher= Prentice-Hall
 |location= Englewood Cliffs, NJ
 |year= 2004
 |isbn=
 |doi= }}
* {{Citation
 |first= F. J.
 |last=MacWilliams
 |first2= N. J. A.
 |last2= Sloane
 |authorlink2= N. J. A. Sloane
 |title= The Theory of Error-Correcting Codes
 |location= New York, NY
 |publisher= North-Holland Publishing Company
 |year= 1977
 |isbn=
 |doi=}}
* {{Citation
 |first        = Atri
 |last         = Rudra
 |title        = CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications
 |publisher    = University at Buffalo
 |url          = http://www.cse.buffalo.edu/~atri/courses/coding-theory/
 |accessdate   = April 21, 2010
 |doi          = 
 |archive-url  = https://web.archive.org/web/20100702120650/http://www.cse.buffalo.edu/~atri/courses/coding-theory/
 |archive-date = 2010-07-02
 |dead-url     = yes
}}
{{refend}}

==外部連接参考文献 ==
{{refbegin}}
* S. Lin and D. Costello. Error Control Coding: Fundamentals and Applications. Prentice-Hall, Englewood Cliffs, NJ, 2004.
* [https://web.archive.org/web/20070107163035/http://ietfec.oxfordjournals.org/cgi/reprint/E88-A/8/2236.pdf Step by step decoding instructions] (pdf file).
*'''Federal Standard 1037c:''' https://web.archive.org/web/20060820191527/http://federal-standard-1037c.foosquare.com/
*Galois Field Calculator: https://web.archive.org/web/20060212215733/http://www.geocities.com/myopic_stargazer/gf_calc.zip
* Decoding Algorithms for BCH codes: http://students.uta.edu/mx/mxa6471/research/ecc-report.pdf{{dead link|date=2017年11月 |bot=InternetArchiveBot |fix-attempted=yes }}
* Source code for BCH channel simulation: http://students.uta.edu/mx/mxa6471/research/ecc-code.tgz{{dead link|date=2017年11月 |bot=InternetArchiveBot |fix-attempted=yes }}
{{refend}}

[[Category:错误检测与校正]]
[[Category:有限域]]