Berlekamp–Masseyアルゴリズム

体 ${\displaystyle \mathbb {F} }$ 上の有限長数列

${\displaystyle s_{0},s_{1},\ldots ,s_{N-1}\in \mathbb {F} }$

について、係数${\displaystyle c_{1},\ldots ,c_{L}\in \mathbb {F} }$を用いて

${\displaystyle s_{k}=-(c_{1}s_{k-1}+c_{2}s_{k-2}+\cdots +c_{L}s_{k-L})}$

が${\displaystyle k=L,L+1,\ldots ,N-1}$で成り立つとき、この関係式を次数 ${\displaystyle L}$ の線形漸化式という。

これは

${\displaystyle s_{k}+c_{1}s_{k-1}+c_{2}s_{k-2}+\cdots +c_{L}s_{k-L}=0}$

と同値であり、多項式

${\displaystyle C(x)=1+c_{1}x+c_{2}x^{2}+\cdots +c_{L}x^{L}}$

を、この数列に対する接続多項式(connection polynomial)という。

有限列に対して線形漸化式(あるいは接続多項式)のうち次数が最小となるものは一意に定まることが知られており、Berlekamp–Masseyアルゴリズムはこの最小次数の接続多項式を逐次的に構成する効率的な方法を与える。

なお接続多項式は定数倍の自由度を持つが、ここでは定数項を ${\displaystyle 1}$ に規格化することで一意に定まるものとして扱う。

Summarize Timeline Top Qs Fact Check

Berlekamp–Masseyアルゴリズムでは、数列を先頭から順に処理しながら、現在までの部分列を説明できるように漸化式を更新していく。

現在の接続多項式を

${\displaystyle C(x)=1+c_{1}x+c_{2}x^{2}+\cdots +c_{L}x^{L}}$

とする。このとき、

${\displaystyle d_{n}:=s_{n}+c_{1}s_{n-1}+c_{2}s_{n-2}+\cdots +c_{L}s_{n-L}}$

を時刻 ${\displaystyle n}$ における不一致量(discrepancy)と呼ぶ。

${\displaystyle d_{n}=0}$ の場合、現在の漸化式は ${\displaystyle s_{n}}$ を正しく説明できているため更新する必要はない。

${\displaystyle d_{n}\neq 0}$ の場合は、過去に不一致が生じたときに保存しておいた接続多項式

${\displaystyle B(x)=1+b_{1}x+b_{2}x^{2}+\cdots +b_{L'}x^{L'}}$

を用いて、次のように接続多項式を更新する:

${\displaystyle C(x)\leftarrow C(x)-{\frac {d_{n}}{d_{n'}}}x^{n-n'}B(x)}$

ここで、${\displaystyle n'}$ は過去に不一致が生じた時刻、${\displaystyle d_{n'}}$ はそのときの不一致量である。 (これは、時刻 ${\displaystyle n'}$ で生じた不一致を ${\displaystyle n-n'}$ だけ未来にずらし、時刻 ${\displaystyle n}$ での不一致量を打ち消すように接続多項式を修正している。)

接続多項式の更新時、現在の次数 ${\displaystyle L}$ がこれまでに観測された数列の長さ ${\displaystyle n+1}$ に対して十分であるかを判定する必要がある。

次数 ${\displaystyle L}$ の漸化式の未知数は ${\displaystyle L}$ 個、制約条件は ${\displaystyle s_{L},...,s_{n}}$ に対する ${\displaystyle n-L+1}$ 本の線形方程式である。

したがって ${\displaystyle L<n-L+1\Leftrightarrow 2L\leq n}$ であれば制約に対して未知数が不足していることになる。この場合、更新後の接続多項式の次数を

${\displaystyle L\leftarrow n-L+1}$

に増やし、自由度が不足した時刻の情報として ${\displaystyle C(x)}$ と ${\displaystyle d_{n}}$ を ${\displaystyle B(x)}$ と ${\displaystyle d_{n'}}$ に保存する。

一方、${\displaystyle 2L>n}$ であれば制約に対して十分な自由度があり、係数を調整することで不一致を解消できるため、次数 ${\displaystyle L}$ は更新しなくてよい。 実際、 ${\displaystyle B(x)}$ は時刻 ${\displaystyle n'}$ での接続多項式で、次数を${\displaystyle L'}$とすると、この時刻に${\displaystyle L\leftarrow n'-L'+1}$と更新したので、

${\displaystyle {\begin{aligned}\deg(x^{n-n'}B(x))&=n-n'+L'\\&=n-n'+(n'-L+1)\\&=n-L+1\\&<L+1\quad (\because 2L>n)\\\end{aligned}}}$

となり、更新後の接続多項式の次数は ${\displaystyle L}$ のままであることが分かる。

長さ ${\displaystyle N}$ の数列 ${\displaystyle s_{0},s_{1},\ldots ,s_{N-1}\in \mathbb {F} }$ から、最小接続多項式 ${\displaystyle C(x)}$ を求めるBerlekamp–Massey アルゴリズムの疑似コードを以下に示す。

/* 初期化 */
C(x) ← 1      // 現在の接続多項式(係数は cj)
L ← 0         // C(x)の次数
B(x) ← 1      // 不一致があった時点(${\displaystyle n'}$)の接続多項式
b ← 1         // B(x) の不一致量(${\displaystyle d_{n'}}$)
m ← 1         // B(x) のシフト量(${\displaystyle n-n'}$)

for n = 0, 1, …, N-1 do
    d ← sn + ∑L
i=1 ci sn - i  // 不一致量を計算
    
    if d = 0 then
        /* 不一致がなければそのまま継続 */
        m ← m + 1
    else
        /* 不一致があれば接続多項式を更新 */
        T(x) ← C(x) // 一時保存
        C(x) ← C(x) - d b-1 xm B(x)
        
        if 2L ≤ n then
            /* 次数が足りなければ更新 */
            L ← n + 1 - L
            B(x) ← T(x)
            b ← d
            m ← 1
        else
            m ← m + 1
        end if
    end if
end for

return C(x)

Berlekamp–Masseyアルゴリズムは、以下のような分野で実際に利用されている。

BCH符号やリード・ソロモン符号の復号では、受信語から得られるシンドローム列

${\displaystyle s_{0},s_{1},\ldots ,s_{N-1}}$

に対し、その最小漸化式を求めることで誤り位置多項式を計算する。 この処理はBerlekamp–Masseyアルゴリズムを用いて効率的に実行できるため、これらの符号の復号アルゴリズムの中心的な役割を果たしている。

実装例として、LinuxカーネルのBCH符号復号処理では誤り位置多項式の計算にBerlekamp–Masseyアルゴリズムを用いている^[3]。また、libcorrectのリード・ソロモン符号復号実装にもBerlekamp–Masseyアルゴリズムが含まれている^[4]。

ビット列

${\displaystyle s_{0},s_{1},s_{2},\ldots \in \mathbb {F} _{2}}$

について、その列を生成できる最小の線形帰還シフトレジスタ(LFSR)の長さ(すなわち最小接続多項式の次数)を線形複雑度といい、暗号理論や疑似乱数生成器の解析において重要な指標となっている。

Berlekamp–Masseyアルゴリズムは、与えられたビット列から最小のLFSRを復元するアルゴリズムであり、線形複雑度が低いビット列から次のビットを予測したり、線形性を検出する手法として利用されている。

例えば、乱数列の統計的性質をテストするNIST STS^[5]では、線形複雑度のテストにBerlekamp–Masseyアルゴリズムを用いている ^[6]。