BCH碼

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

## 構建

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

要構建一個能夠檢測、校正兩個錯誤的 BCH 碼，我們要使用有限域 GF (16) 或者 **Z**2[_x_]／<_x_4 + _x_ + 1>。如果 α 是 _m_1(_x_) = _x_4 + _x_ + 1 的一個根，那麼 _m_1 就是 α 的極小多項式，這是因為

　
: _m_1(_x_) = (_x_ - α)(_x_ - α2)(_x_ - α4)(_x_ - α8)=_x_4 + _x_ + 1。

如果要構建一個能夠糾正一個錯誤的 BCH 碼，那麼就使用 _m_1(_x_)，這個代碼就是所有滿足

　
: _C_(_x_) ≡ 0（mod _m_1(_x_)）且根為 α, α2, α4, α8 的多項式 _C_(_x_)。

## 編碼

構建碼字為

　
: (_c_14, _c_13, ..., _c_8)

這樣多項式為

　
: _c_14+_c_13+...+_c_8

我們將它稱為 _C_I。

然後就要找出 _C_R 滿足 _C_R=_C_I (mod _m_1,3(_x_))=_c_7+_c_6+...+_c_0

這樣就得到待發的碼字 _C_(_x_) = _C_I+_C_R (mod _m_1,3(_x_)) = 0 

例如，如果我們要對 (1,1,0,0,1,1,0) 進行編碼

　
: _C_I=_x_14+_x_13+_x_10+_x_9

然後用 _m_1,3(_x_) 除以（這裡的除法是多項式除法）_C_I ，得到結果為 _C_R(_x_)，在 **Z**2 域中，我們可以算出 _C_R 為

　
: _x_3+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 (α3)=0

如果有一個錯誤，例如 **r**=**c**+**e**i，其中 **e**i 表示 **R**14 的第 _i_ 個基向量
於是

　
: _S_1=_R_(α)=_C_(α)+αi=αi

　
: _S_3=_R_(α3)=C(α3)+(α3)i
　
: =(αi)3=_S_13

這樣就可以糾正錯誤。α 的指數顯示的數據位變化可以幫助我們校正錯誤。

如果有兩個錯誤

　
: **r**=**c**+**e**i+**e**j

那麼

　
: _S_1=_R_(α)=_C_(α)+αi+αj

　
: _S_3=_R_(α3)=C(α3)+(α3)i+(α3)j
　
: = (α3)i+(α3)j

這與 _S_13 不同，所以我們認為有兩個錯誤。更進一步的代數方法可以幫助校正著兩個錯誤。

_開頭兩段內容出自 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 算法計算多項式 $\Lambda (x)=1+\lambda _{1}X+\lambda _{2}X^{2}+...+\lambda _{2t}X^{2t}$ 的錯誤定位多項式係數 $\lambda _{1},\lambda _{2}...\lambda _{2t}$

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

### 算法

* 首先生成 $2t$ 伴隨矩陣
* 然後生成元素為

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

* 生成元素為

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

* 讓 $\Lambda $ 表示未知的多項式係數，用

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

* 這樣就得到矩陣方程

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

* 如果矩陣 $S_{t\times t}$ 存在行列式，那麼我們就可以找到這個矩陣的逆，然後就可以得到 $\Lambda $ 的值
* 如果 $det(S_{t\times t})=0$ ，那麼按照

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

```

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

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

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

## 錯誤校正

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

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

## 參考文獻

## 延伸閱讀

## 外部連接參考文獻