バーレカンプ–ウェルチアルゴリズムとは？わかりやすく解説

バーレカンプ–ウェルチアルゴリズム, または ウェルチ–バーレカンプアルゴリズムは，エルウィン・バーレカンプと 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_{i}^{j}$ )。この $n$ 元連立方程式を直接解くことはできないが，関数 $Q$ を

Q(a_{i}):=E(a_{i})F(a_{i})

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

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 {Q}{E}}$ であり， $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})=3a_{i}^{4}+a_{i}^{3}+3a_{i}^{2}+3a_{i}+4$

$E(a_{i})=a_{i}^{2}+2a_{i}+4$

$Q\left(a_{i}\right)=\left(3a_{i}^{2}+2a_{i}+1\right)E\left(a_{i}\right)$ となって割り切れる。

∴ $F\left(a_{i}\right)=3a_{i}^{2}+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
US 4,633,470, Welch, Lloyd R. & Elwyn R. Berlekamp, "Error Correction for Algebraic Block Codes", published September 27, 1983, issued December 30, 1986 – The patent by Lloyd R. Welch and Elewyn R. Berlekamp

バーレカンプ–ウェルチアルゴリズムとは？ わかりやすく解説