Berlekamp–Masseyアルゴリズム

Berlekamp–Masseyアルゴリズム(Berlekamp–Massey algorithm)とは、体上の数列が満たす最小次数の線形漸化式を求めるアルゴリズムである。特に、与えられたバイナリ列を出力する最小の線形帰還シフトレジスタ(LFSR)を構成する手法として知られている。

1960年代にエルウィン・バーレカンプによりBCH符号の復号問題の中で原型が導入され、1969年にテンプレート:仮リンクによって一般の数列に対するアルゴリズムとして整理・定式化された。

問題設定

体 $𝔽$ 上の有限長数列

$s_0,s_1,\dots ,s_{N-1}\in 𝔽$

について、係数$c_1,\dots ,c_L\in 𝔽$を用いて

$s_k=-(c_1{s}_{k-1}+c_2{s}_{k-2}+\cdots +c_L{s}_{k-L})$

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

これは

$s_k+c_1{s}_{k-1}+c_2{s}_{k-2}+\cdots +c_L{s}_{k-L}=0$

と同値であり、多項式

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

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

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

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

アルゴリズムの原理

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

漸化式の更新

現在の接続多項式を

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

とする。このとき、

$d_n:=s_n+c_1{s}_{n-1}+c_2{s}_{n-2}+\cdots +c_L{s}_{n-L}$

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

$d_n=0$ の場合、現在の漸化式は $s_n$ を正しく説明できているため更新する必要はない。

$d_n\ne 0$ の場合は、過去に不一致が生じたときに保存しておいた接続多項式

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

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

$C(x)\leftarrow C(x)-\frac{d_n}{d_{n^{\prime }}}{x}^{n-n^{\prime }}B(x)$

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

次数の更新条件

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

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

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

$L\leftarrow n-L+1$

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

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

$\begin{array}{cc}\mathrm{deg}(x^{n-n^{\prime }}B(x))& =n-n^{\prime }+L^{\prime }\\ & =n-n^{\prime }+(n^{\prime }-L+1)\\ & =n-L+1\\ & <L+1(\because 2L>n)\end{array}$

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

疑似コード

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

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

for n = 0, 1, …, N-1 do
    d ← sn + テンプレート:Math  // 不一致量を計算
    
    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符号やリード・ソロモン符号の復号では、受信語から得られるシンドローム列

$s_0,s_1,\dots ,s_{N-1}$

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

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

暗号理論・疑似乱数生成器の解析

ビット列

$s_0,s_1,s_2,\dots \in {𝔽}_2$

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

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

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

関連項目

• 線形帰還シフトレジスタ
• BCH符号
• リード・ソロモン符号
• ストリーム暗号

外部リンク

• Berlekamp–Massey algorithm - Rosetta Code