檢視 BCH碼的原始碼

'''BCH 碼'''（BCH codes、Bose–Chaudhuri–Hocquenghem codes）為著取自 Bose、Ray-Chaudhuri 佮 Hocquenghem 的縮寫，是編碼理論尤其是糾錯碼中研究閣較濟的一種編碼方法。用術語來講，BCH 碼是用佇校正濟的隨機錯誤模式的多級、循環、錯誤學校正、變長數字編碼。BCH 碼嘛會當用佇質數級或者質數的冪級的多級相移鍵控。十一級的 BCH 碼已經用佇咧表示十進位數外加一个符號位。

==構建==

BCH 碼使用有限域上的域論佮濟項式。為著檢測錯誤會當構建一个檢測濟項式，按呢接收端就會當檢測敢有錯誤發生。

愛構建一个會當檢測、正兩个錯誤的 BCH 碼，阮欲使用有限域 GF ( 十六 ) 抑是講'''Z'''二 [_ x _]／< _ x _ 四 + _ x _ + 一 >。若是 α 是 _ m _ 一 ( _ x _ )=_ x _ 四 + _ x _ + 一的一个根，遐爾 _ m _ 一就是 α 足細項的項式，這是因為


: _ m _ 一 ( _ x _ )=( _ x _-α ) ( _ x _-α 二 ) ( _ x _-α 四 ) ( _ x _-α 八 )=_ x _ 四 + _ x _ + 一。

若是欲構建一个會當糾正一个錯誤的 BCH 碼，就使用 _ m _ 一 ( _ x _ )，這个代碼就是所有滿足


: _ C _ ( _ x _ ) ≡ 零（mod _ m _ 一 ( _ x _ )）而且根為 α , α 二 , α 四 , α 八的多項式 _ C _ ( _ x _ )。

==編碼==

構建碼字為


: ( _ c _ 十四 , _ c _ 十三 , . . . , _ c _ 八 )

按呢足濟項為


: _ c _ 十四 + _ c _ 十三 + . . . + _ c _ 八阮共稱做 _ C _ I。

然後就愛揣出 _ C _ R 滿足 _ C _ R=_ C _ I ( mod _ m _ 一 , 三 ( _ x _ ) )=_ c _ 七 + _ c _ 六 + . . . + _ c _ 零按呢就得著待發的碼字 _ C _ ( _ x _ )=_ C _ I + _ C _ R ( mod _ m _ 一 , 三 ( _ x _ ) )=零比如講，若是咱欲對 ( 一 , 一 , 零 , 零 , 一 , 一 , 零 ) 進行編碼


: _ C _ I=_ x _ 十四 + _ x _ 十三 + _ x _ 十 + _ x _ 九然後用 _ m _ 一 , 三 ( _ x _ ) 除以（遮的除法是多項式除法）_ C _ I，得著結果為 _ C _ R ( _ x _ )，佇咧'''Z'''二域中，咱會當算講出 _ C _ R 為


: _ x _ 三 + 一下按呢，蹛的碼字為著


: ( 一 , 一 , 零 , 零 , 一 , 一 , 零 , 零 , 零 , 零 , 零 , 一 , 零 , 零 , 一 )

==解碼==

BCH 的解碼過程會當分做以下四步一 . 計算接收著的向量 R 的二 t 伴隨矩陣二 . 計算是錯誤定位的多項式三 . 解多項式，得著錯誤位置四 . 若毋是二進位 BCH 碼，就算講是錯誤位置的精差值假使咱收著一个碼字向量'''r'''，即多項式 _ R _ ( _ x _ )）。

若是無錯誤，遐爾 R ( α )=R ( α 三 )=零若有一个錯誤，比如講'''r'''='''c'''+'''e'''i，其中'''e'''i 表示'''R'''十四的第 _ i _ 個基向量於是


: _ S _ 一=_ R _ ( α )=_ C _ ( α ) + αi=αi


: _ S _ 三=_ R _ ( α 三 )=C ( α 三 ) + ( α 三 ) i

:=( αi ) 三=_ S _ 十三按呢就會當糾正錯誤。α 的指數顯示的數據位變化會當幫助阮學校當錯誤。

若是有兩个錯誤


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

遐爾


: _ S _ 一=_ R _ ( α )=_ C _ ( α ) + αi + αj


: _ S _ 三=_ R _ ( α 三 )=C ( α 三 ) + ( α 三 ) i + ( α 三 ) j

:=( α 三 ) i + ( α 三 ) j

這佮 _ S _ 十三無仝，所以咱認為講有兩个錯誤。較精傱的代數方法會當幫助學校當兩个錯誤。

_ 開頭兩段內容出自 Federal Standard 一千空三十七 C _

頂懸的文字挽自：https : / / web . archive . org / web / 二十五空七百空二五一千三百空一知三千一百空六 / http : / / bch-code . foosquare . com /

==BCH 解碼算法==

時行的解碼算法有，

一 . Peterson Gorenstein Zierler 算法二 . Berlekamp-Massey 算法

==Peterson Gorenstein Zierler 算法==

===準講===

Peterson 算法是普通 BCH 解碼過程的第二步，佇遮咧用 Peterson 算法計算濟項式 $ \ Lambda ( x )=一 + \ lambda _ { 一 } X + \ lambda _ { 二 } X ^ { 二 } + . . . + \ lambda _ { 二 t } X ^ { 二 t } $ 的錯誤定位多項式係數 $ \ lambda _ { 一 } , \ lambda _ { 二 } . . . \ lambda _ { 二 t } $

按呢予定 BCH 碼 $ ( n , k , d _ { min } ) $，攏會使學校當 $ [t={ \ frac { d _ { min } 影一 } { 二 } }] $ 一个錯誤的 Peterson Gorenstein Zierler 算法就是

===算法===

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

$ $
S _ { t \ times t }={ \ begin { bmatrix } s _ { 一 } & s _ { 二 } & s _ { 三 } & . . . & s _ { t } \ \ s _ { 二 } & s _ { 三 } & s _ { 四 } & . . . & s _ { t + 一 } \ \ s _ { 三 } & s _ { 四 } & s _ { 五 } & . . . & s _ { t + 二 } \ \ . . . & . . . & . . . & . . . & . . . \ \ s _ { t } & s _ { t + 一 } & s _ { t + 二 } & . . . & s _ { 二 t 影一 } \ end { bmatrix } } $ 矩陣 $ S _ { txt }
$ $

* 生做元素為

$ $
C _ { t \ times 一 }={ \ begin { bmatrix } s _ { t + 一 } \ \ s _ { t + 二 } \ \ . . . \ \ . . . \ \ s _ { 二 t } \ end { bmatrix } } $ 矩陣 $ c _ { tx 一 }
$ $

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

$ \ Lambda _ { t \ times 一 }={ \ begin { bmatrix } \ lambda _ { t } \ \ \ lambda _ { t 影一 } \ \ . . . \ \ \ lambda _ { 三 } \ \ \ lambda _ { 二 } \ \ \ lambda _ { 一 } \ end { bmatrix } } $ 表示

* 按呢就得著矩陣方程

$ $
S _ { t \ times t } \ Lambda _ { t \ times 一 }=C _ { t \ times 一 }
$ $

* 如果矩陣 $ S _ { t \ times t } $ 存在行列式，啊咱就會當揣著這个矩陣的湖，然後就會當得著 $ \ Lambda $ 的值
* 若是 $ det ( S _ { t \ times t } )=零 $，遐爾仔照顧

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

` ` `

* 佇咧 $ \ Lambda $ 的值確定了後，自然就得著錯誤定位多項式
* 結束 Peterson procedure。

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

咧得著 $ \ Lambda ( x ) $ 多項式了後，用 _ Chiens search _ 算法就會當得著伊的解 $ \ Lambda ( x )=( \ alpha ^ { i } X + 一 ) ( \ alpha ^ { j } X + 一 ) . . . ( \ alpha ^ { k } X + 一 ) $。根據素元 $ \ alpha $ 的指數冪就會當得著接收著的碼字中錯誤的位置，這也就是精差定位有偌項式名稱的由來。

==錯誤學校正==

對兩進位的 BCH 碼，會當直接根據錯誤定位多項式因數素元指數的位置校正接收著的向量。最後咧，對遮的位置接收著的數值取反，就會當得著正確的彼號 BCH 解碼字。

另外嘛會使用 Berlekamp-Massey 算法確定毋著定位濟項式，從而解決 BCH 解碼的問題。

==參考文獻==

==延伸閱讀==

==外部連接參考文獻==

[[分類: 待校正]]