バーレカンプ–ウェルチアルゴリズム

バーレカンプ–ウェルチアルゴリズム, または ウェルチ–バーレカンプアルゴリズムは，エルウィン・バーレカンプと Lloyd R. Welch から命名された復号アルゴリズムで，メッセージ  を多項式  の係数として使用するか，ラグランジュ補間に用いるかの何れかによって  を入力とする  次未満の多項式  を生成し，次に  に  を代入して符号語  を生成するという，元来のリード・ソロモン符号における誤り訂正において効果的である。

復号アルゴリズムの目的は，分かっている入力  と，誤りを含む可能性のある受信した符号語  を用いて，もともとの符号化多項式  を復元することである。また， に対応する符号語に誤りがあると  となるような多項式  も算出する (後述)。

 タネとなる方程式 
誤りが  個含まれるとすると， 以上  以下のすべての自然数  について以下の方程式



が成り立つ，という  元連立方程式が主人公である。ここで  は， である (つまり誤りがある) ような  通りの場合に  となり (つまり  は  の根になる)，それ以外の  通りの場合 (すなわち誤りがなく， であるような場合) に  となる  次多項式とし，その  次の係数を  とする (すなわち，)。この  元連立方程式を直接解くことはできないが，関数  を



と定義し， がモニックである (つまり ) という制約を付加すると，結果的に連立方程式が  次方程式によって解けるようになる。





ここで  である。また，制約により  であるから，方程式は以下のようにできる。



これは線型代数によって，計算量  で解決できる連立方程式である。

このアルゴリズムは，誤りの最大数を と仮定し，これに基づいて処理を開始する。もし冗長性が原因で方程式が解けない (すなわち同じ式が重複している) のであれば  を  減らし，以後方程式が解けるようになる，または  が  に達する (これは誤りが  つも含まれないというたいへんめでたい状況を意味する) までこの処理を繰り返す。もし  が  で割り切れるのであれば， であり， となる  について符号語  を計算し，元の符号語を修復する。また， を  で割って  でない余りが生じるのであれば，それは修復不能な誤りが検出されたということである。

 例 
ガロア体 GF に定義されるリード・ソロモン符号 RS を考える。添字  に対応する入力値を  とし，送信したいメッセージが  であるとする。ラグランジュ補間により，符号化多項式は  であり， から  を代入して符号語  を得る。ところが残念ながら  と  で誤りが起こってしまい，符号語  を受信したとする。 から始めて上の  次方程式を解く。







右辺の行列の下 (第  行) から始まって上に行き，また制約  を考慮して

 となって割り切れる。

∴ 

 となるのは  及び  である。これらを  に代入して，符号語を  に訂正する。

 関連項目 

 リード・ソロモン符号

 外部リンク 
 MIT Lecture Notes on Essential Coding Theory – Dr. Madhu Sudan
 University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra
 Algebraic Codes on Lines, Planes and Curves, An Engineering Approach – Richard E. Blahut
 Welch Berlekamp Decoding of Reed–Solomon Codes – L. R. Welch
  – The patent by Lloyd R. Welch and Elewyn R. Berlekamp

Category:誤り検出訂正
Category:情報理論
Category:符号理論
Category:有限体