BCH碼

出自Local Chinese Wikipedia
跳至導覽 跳至搜尋

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

構建[編輯]

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

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

m1(x) = (x - α)(x - α2)(x - α4)(x - α8)=x4 + x + 1。

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

C(x) ≡ 0（mod m1(x)）且根為 α, α2, α4, α8 的多項式 C(x)。

編碼[編輯]

構建碼字為

(c14, c13, ..., c8)

這樣多項式為

c14+c13+...+c8

我們將它稱為 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) 進行編碼

CI=x14+x13+x10+x9

然後用 m1,3(x) 除以（這裏的除法是多項式除法）CI ，得到結果為 CR(x)，在Z2域中，我們可以算出 CR為

x3+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+ei，其中 ei 表示 R14 的第 i個基向量 於是

S1=R(α)=C(α)+αi=αi
S3=R(α3)=C(α3)+(α3)i
=(αi)3=S13

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

如果有兩個錯誤

r=c+ei+ej

那麼

S1=R(α)=C(α)+αi+αj
S3=R(α3)=C(α3)+(α3)i+(α3)j
= (α3)i+(α3)j

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

開頭兩段內容出自 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 算法計算多項式 <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解碼的問題。

參考文獻[編輯]

主要參考[編輯]

  • Hocquenghem, A., Codes correcteurs d'erreurs, Chiffres (Paris), September 1959, 2: 147–156 （français） 
  • 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 

次要參考[編輯]

延伸閱讀[編輯]

外部連接參考文獻[編輯]

取自 "https://arolstar52-zhtest.hf.space/index.php?title=BCH码&oldid=158969"