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

バーレカンプ–ウェルチアルゴリズム, または ウェルチ–バーレカンプアルゴリズムは，エルウィン・バーレカンプと 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