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

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

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

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

: b_i E(a_i) = E(a_i) F(a_i) 

が成り立つ，という n 元連立方程式が主人公である。ここで E は，b_i \neq F\left(a_i\right) である (つまり誤りがある) ような e 通りの場合に E\left(a_i\right)=0 となり (つまり a_i  は E  の根になる)，それ以外の n-e 通りの場合 (すなわち誤りがなく，b_i=F\left(a_i\right) であるような場合) に E\left(a_i\right)\neq 0 となる e  次多項式とし，その j  次の係数を e_j  とする (すなわち，E\left(a_i\right)=\sum_{0\leq j\leq e}e_j a^j_i )。この n 元連立方程式を直接解くことはできないが，関数 Q を

: Q(a_i) := E(a_i) F(a_i) 

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

: b_i E(a_i) = Q(a_i)
: b_i E(a_i) - Q(a_i) = 0 
: b_i(e_0 + e_1 a_i + e_2 a_i^2 + \cdots + e_e a_i^e) -(q_0 + q_1 a_i + q_2 a_i^2 + \cdots + q_q a_i^q) = 0

ここで q = n - e - 1  である。また，制約により e_e=1  であるから，方程式は以下のようにできる。

: b_i(e_0 + e_1 a_i + e_2 a_i^2 + \cdots + e_{e-1} a_i^{e-1}) -(q_0 + q_1 a_i + q_2 a_i^2 + \cdots + q_q a_i^q) = - b_i a_i^e

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

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

## 例
ガロア体 GF\left(7\right)  に定義されるリード・ソロモン符号 RS\left(7, 3\right)  を考える。添字 i  に対応する入力値を a_i := i-1  とし，送信したいメッセージが \left\{1, 6, 3\right\}  であるとする。ラグランジュ補間により，符号化多項式は F\left(x\right)=3x^2+2x+1  であり，a_4 = 3  から a_7 = 6  を代入して符号語 c_i=\left\{1, 6, 3, 6, 1, 2, 2\right\}  を得る。ところが残念ながら c_2  と c_5  で誤りが起こってしまい，符号語 b_i = \left\{1, 5, 3, 6, 3, 2, 2\right\}  を受信したとする。e=2  から始めて上の 1  次方程式を解く。

: \begin{bmatrix}
 b_1 & b_1 a_1 & -1 & -a_1 & -a_1^2 & -a_1^3 & -a_1^4 \\
 b_2 & b_2 a_2 & -1 & -a_2 & -a_2^2 & -a_2^3 & -a_2^4 \\
 b_3 & b_3 a_3 & -1 & -a_3 & -a_3^2 & -a_3^3 & -a_3^4 \\
 b_4 & b_4 a_4 & -1 & -a_4 & -a_4^2 & -a_4^3 & -a_4^4 \\
 b_5 & b_5 a_5 & -1 & -a_5 & -a_5^2 & -a_5^3 & -a_5^4 \\
 b_6 & b_6 a_6 & -1 & -a_6 & -a_6^2 & -a_6^3 & -a_6^4 \\
 b_7 & b_7 a_7 & -1 & -a_7 & -a_7^2 & -a_7^3 & -a_7^4 \\
\end{bmatrix}
\begin{bmatrix}
e_0 \\ e_1 \\ q_0 \\ q_1 \\ q_2 \\ q_3 \\ q_4 \\
\end{bmatrix}
= 
\begin{bmatrix}
-b_1 a_1^2\\
-b_2 a_2^2\\
-b_3 a_3^2\\
-b_4 a_4^2\\
-b_5 a_5^2\\
-b_6 a_6^2\\
-b_7 a_7^2\\
\end{bmatrix}


: \begin{bmatrix}
 1 & 0 & 6 & 0 & 0 & 0 & 0 \\
 5 & 5 & 6 & 6 & 6 & 6 & 6 \\
 3 & 6 & 6 & 5 & 3 & 6 & 5 \\
 6 & 4 & 6 & 4 & 5 & 1 & 3 \\
 3 & 5 & 6 & 3 & 5 & 6 & 3 \\
 2 & 3 & 6 & 2 & 3 & 1 & 5 \\
 2 & 5 & 6 & 1 & 6 & 1 & 6 \\
\end{bmatrix}
\begin{bmatrix}
e_0 \\ e_1 \\ q_0 \\ q_1 \\ q_2 \\ q_3 \\ q_4 \\
\end{bmatrix}
= 
\begin{bmatrix}
0\\
2\\
2\\
2\\
1\\
6\\
5\\
\end{bmatrix}


: \begin{bmatrix}
 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
e_0 \\ e_1 \\ q_0 \\ q_1 \\ q_2 \\ q_3 \\ q_4 \\
\end{bmatrix}
= 
\begin{bmatrix}
4\\
2\\
4\\
3\\
3\\
1\\
3\\
\end{bmatrix}


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

Q(a_i) = 3 a^4_i + a^3_i + 3 a^2_i + 3a_i + 4

E(a_i) = a^2_i + 2 a_i + 4

Q\left(a_i\right)=\left(3a^2_i+2a_i+1\right)E\left(a_i\right) となって割り切れる。

∴ F\left(a_i\right)=3a^2_i+2a_i+1

E\left(a_i\right)=0 となるのは a_2 = 1 及び a_5 = 4 である。これらを F\left(a_i\right) に代入して，符号語を \left\{1, 6, 3, 6, 1, 2, 2\right\} に訂正する。

## 関連項目

* リード・ソロモン符号

## 外部リンク
* 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