BCH碼

BCH碼（BCH codes、Bose–Chaudhuri–Hocquenghem codes）為取自Bose、Ray-Chaudhuri與Hocquenghem的縮寫，是編碼理論尤其是糾錯碼中研究得比較多的一種編碼方法。用術語來說，BCH碼是用於校正多個隨機錯誤模式的多級、循環、錯誤校正、變長數字編碼。BCH碼也可以用於質數級或者質數的冪級的多級相移鍵控。11級的BCH碼已經用於表示10進制數外加一個符號位。

構建

BCH 碼使用有限域上的域論與多項式。為了檢測錯誤可以構建一個檢測多項式，這樣接收端就可以檢測是否有錯誤發生。

要構建一個能夠檢測、校正兩個錯誤的 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)。

編碼

構建碼字為

(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⁹

然後用 m_1,3(x) 除以（這裡的除法是多項式除法）C_I ，得到結果為 C_R(x)，在Z₂域中，我們可以算出 C_R為

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

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

BCH 解碼算法

流行的解碼算法有，

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

Peterson Gorenstein Zierler 算法

假設

Peterson 算法是普通 BCH 解碼過程的第二步，在這裡使用 Peterson 算法計算多項式 ${\displaystyle \Lambda (x)=1+\lambda _{1}X+\lambda _{2}X^{2}+...+\lambda _{2t}X^{2t}}$ 的錯誤定位多項式係數 ${\displaystyle \lambda _{1},\lambda _{2}...\lambda _{2t}}$

這樣給定 BCH 碼 ${\displaystyle (n,k,d_{min})}$，可以校正 ${\displaystyle [t={\frac {d_{min}-1}{2}}]}$ 個錯誤的 Peterson Gorenstein Zierler 算法就是

算法

• 首先生成 ${\displaystyle 2t}$ 伴隨矩陣
• 然後生成元素為

${\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}}}$ 的矩陣 ${\displaystyle S_{txt}}$

• 生成元素為

${\displaystyle C_{t\times 1}={\begin{bmatrix}s_{t+1}\\s_{t+2}\\...\\...\\s_{2t}\end{bmatrix}}}$ 的矩陣 ${\displaystyle c_{tx1}}$

• 讓 ${\displaystyle \Lambda }$ 表示未知的多項式係數，用

${\displaystyle \Lambda _{t\times 1}={\begin{bmatrix}\lambda _{t}\\\lambda _{t-1}\\...\\\lambda _{3}\\\lambda _{2}\\\lambda _{1}\end{bmatrix}}}$ 表示

• 這樣就得到矩陣方程

${\displaystyle S_{t\times t}\Lambda _{t\times 1}=C_{t\times 1}}$

• 如果矩陣 ${\displaystyle S_{t\times t}}$ 存在行列式，那麼我們就可以找到這個矩陣的逆，然後就可以得到 ${\displaystyle \Lambda }$ 的值

• 如果 ${\displaystyle det(S_{t\times t})=0}$，那麼按照

       if ${\displaystyle t=0}$
       then
             declare an empty error locator polynomial
             stop Peterson procedure.
       end
       set ${\displaystyle t\leftarrow t-1}$
       continue from the beginning of Peterson's decoding

• 在 ${\displaystyle \Lambda }$ 的值確定之後，自然就得到錯誤定位多項式
• 結束 Peterson procedure。

錯誤定位多項式的因式分解

在得到 ${\displaystyle \Lambda (x)}$ 多項式之後，用 Chiens search 算法就可以得到它的解 ${\displaystyle \Lambda (x)=(\alpha ^{i}X+1)(\alpha ^{j}X+1)...(\alpha ^{k}X+1)}$。根據素元 ${\displaystyle \alpha }$ 的指數冪就能得到接收到的碼字中錯誤的位置，這也就是誤差定位多項式名稱的由來。

錯誤校正

對於二進制的BCH碼，可以直接根據錯誤定位多項式因數素元指數的位置校正接收到的向量。最後，對這些位置接收到的數值取反，就可以得到正確的BCH解碼碼字。

另外也可以使用Berlekamp-Massey 算法確定錯誤定位多項式，從而解決BCH解碼的問題。

參考文獻

主要參考

• Hocquenghem, A., Codes correcteurs d'erreurs, Chiffres (Paris), September 1959, 2: 147–156 （法語）
• Bose, R. C.; Ray-Chaudhuri, D. K., On A Class of Error Correcting Binary Group Codes, Information and Control, March 1960, 3 (1): 68–79, ISSN 0890-5401, doi:10.1016/s0019-9958(60)90287-4

次要參考

• Gill, John, EE387 Notes #7, Handout #28 (PDF), Stanford University: 42–45, n.d. [April 21, 2010], （原始內容 (PDF)存檔於2014年6月30日） Course notes are apparently being redone for 2012: http://www.stanford.edu/class/ee387/（頁面存檔備份，存於網際網路檔案館）
• Gorenstein, Daniel; Peterson, W. Wesley; Zierler, Neal, Two-Error Correcting Bose-Chaudhuri Codes are Quasi-Perfect, Information and Control, 1960, 3 (3): 291–294, doi:10.1016/s0019-9958(60)90877-9
• Lidl, Rudolf; Pilz, Günter, Applied Abstract Algebra 2nd, John Wiley, 1999
• Reed, Irving S.; Chen, Xuemin, Error-Control Coding for Data Networks, Boston, MA: Kluwer Academic Publishers, 1999, ISBN 0-7923-8528-4

延伸閱讀

• Blahut, Richard E., Algebraic Codes for Data Transmission 2nd, Cambridge University Press, 2003, ISBN 0-521-55374-1
• Gilbert, W. J.; Nicholson, W. K., Modern Algebra with Applications 2nd, John Wiley, 2004
• Lin, S.; Costello, D., Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ: Prentice-Hall, 2004
• MacWilliams, F. J.; Sloane, N. J. A., The Theory of Error-Correcting Codes, New York, NY: North-Holland Publishing Company, 1977
• Rudra, Atri, CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications, University at Buffalo, [April 21, 2010], （原始內容存檔於2010-07-02）

外部連接參考文獻

• 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: 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^{[永久失效連結]}
• Source code for BCH channel simulation: http://students.uta.edu/mx/mxa6471/research/ecc-code.tgz^{[永久失效連結]}