🛅線形フィードバックシフトレジスタ

1696868916147

線形フィードバックシフトレジスタ（LFSR）は、疑似乱数コードを生成するための線形ドライバ部分として数学的に最適な解であり、自己相関関数は主ピーク以外に最大のフラットさを持っています。

LFSR の導入#

いくつかのレジスタが行に並べられ、各レジスタには 2 進数が格納されています。シフトレジスタは、最も右端（末尾）の数字を出力し、全体を右にシフトします。同時に、フィードバック関数があり、レジスタ内の一部のシーケンスをフィードバック関数の入力として使用し、フィードバック関数の出力をシフトレジスタの最も左端に埋め込みます。このような、フィードバック関数を持つシフトレジスタをフィードバックシフトレジスタと呼びます。

フィードバック関数#

LFSR のフィードバック関数は、シフトレジスタの特定のビットを単純に排他的論理和（XOR）で結合し、その結果を LFSR の最も左端に埋め込みます。 LFSR の各ビットのデータには、XOR に参加するかどうかを選択できます。その中で、XOR に参加するビットをタップと呼びます。

b_{n+1} = c_1b_1 \oplus c_2b_2 \oplus \ldots \oplus c_nb_n

次数#

LFSR の次数は、レジスタの数です。n ビットの LFSR は最大 $2^n-1$ の状態を保存できます。なぜ最大で $2^n-1$ の状態を遍歴できるのかは、後で説明します。n ビットの LFSR の最大周期は $2^n-1$ であり、 $m$ シーケンスと呼ばれる周期 $2^n-1$ で生成されるシーケンスです。

特性多項式#

上記の式から、LFSR の再帰関係式が得られます。この再帰関係は、特性多項式に対応することができます。

f(x) = c_nx^n + c_{n-1} + \ldots + c_2x^2 + c_1x + 1

ここでの $c_i$ は以前の定義と同じであり、タップかどうかを示します。最終的に得られる特性多項式は、タップの次数項のみを保持し、1 を加えます。これは、LFSR の異なる特性多項式が異なるフィードバック関数に対応していることを理解するためです。

原始多項式#

まず、次の結論を示します。

n ビットの LFSR が m シーケンスを生成できるための必要十分条件は、その特性多項式が原始多項式であることです。

次に、既約多項式と原始多項式を紹介します。

Irreducible Polynomial. 多項式が指定された体上で分解できない場合、それは既約多項式と呼ばれます。つまり、より小さい次数の多項式の積と等しくすることはできません。

LFSR で使用される有限体は $GF(2^n)$ であり、多項式の係数は 0 または 1 でなければならず、多項式の最高次数は $n$ 未満でなければなりません。たとえば、 $GF(2^3)$ では、多項式は $0, 1, x, x+1$ です。

Primitive Polynomial. 原始多項式自体も既約多項式ですが、次の 3 つの条件を満たす必要があります：n 次の原始多項式 $F(x)$ に対して

$F(x)$ は既約であり、多項式を分解できません

$F(x)$ は $x^p+1$ で割り切れますが、ここで $p = 2^n-1$ です

$F(x)$ は $x^q+1$ で割り切れませんが、ここで $q<p$ です

原始多項式からは、 $m$ シーケンスを生成するためのフィードバック関数が得られます。たとえば、 $n=10$ の場合、原始多項式は

F(x) = x^{10} + x^3 + 1

となります。したがって、フィードバック関数は[0,0,1,0,0,0,0,0,0,1]となり、3 番目のレジスタと 10 番目のレジスタの値の XOR を取り、その結果を最も左のレジスタに代入することでシフトフィードバックを実現します。

MATLAB のprimpoly関数を使用すると、任意の次数の原始多項式を表示できます。

$m$ シーケンスの特性#

$m$ シーケンスは、疑似乱数コードまたはスプレッドスペクトラムコードと呼ばれます。

バランス性#

$m$ シーケンスの 1 つの周期では、0 と 1 の数はほぼ同じですが、1 の数が 0 よりも 1 つ多くなります。

シフト加算性#

$m$ シーケンス $m_1$ と、任意の遅延シフトによって生成される別のシーケンス $m_2$ をモジュロ 2 で加算（XOR）すると、結果は $m_1$ のある遅延シフトシーケンス $m_3$ になります。

自己相関性#

1 の数が常に 0 よりも 1 つ多いため、自己相関を行うと常に - 1 の値が得られます。これは完全なランダム信号とは大きく異なります。

R(\tau) = \left\{ \begin{align*} &1, &\tau = 0\\ &-\frac{1}{N}, &\mathrm{else} \end{align*}\right.

ラン長分布#

$m$ シーケンス内の同じ値の連続する要素を「ラン」と呼び、ラン内の要素の数をランの長さと呼びます。n ビットの LFSR で生成される $m$ シーケンスには、合計 $2^{n-1}$ 個のランがあり、長さ 1 のランは全体のランの数の 1/2 を占め、長さ 2 のランは全体のランの数の 1/4 を占め、長さ k のランは全体のランの $2^{-k}$ を占めます。また、長さ k のランでは、0 と 1 のランの数が半分ずつです。ランの分布は非常に均衡しています。

たとえば、シーケンス1000010010110011111000110111010では、総ラン数は $2^{5-1}=16$ であり、各長さのランの分布は次のようになります：

長さ 1 のランの数は 8 で、1 のランと 0 のランが 4 つずつあります。
長さ 2 のランの数は 4 で、11 のランと 00 のランが 2 つずつあります。
長さ 3 のランの数は 2 で、111 のランと 000 のランがそれぞれ 1 つずつあります。
長さ 4 の連続する 0 のランの数は 1 つです。
長さ 5 の連続する 1 のランの数は 1 つです。

付録#

時間の都合上、以前の原始多項式の生成と証明については省略しています。将来的には、他の文献を参照して調査することができます。