はじめに M 系列について考える必要に迫られたので、理解したことをここに記しておく。本記事では周期の導出，論理回路による並列計算について記す。本記事は拙著「LFSRによる擬似ランダムビット列生成 」（☆1）とは異なるアプローチをとる。☆1 ではビット列の生成を、 Laurent 級数を求める為の無限に続く割り算の商と結び付けたが、本記事では余りに結び付ける。
\[
% general purpose
\newcommand{\ctext}[1]{\raise0.2ex\hbox{\textcircled{\scriptsize{#1}}}}
% mathematics
% general purpose
\DeclarePairedDelimiterX{\parens}[1]{\lparen}{\rparen}{#1}
\DeclarePairedDelimiterX{\braces}[1]{\lbrace}{\rbrace}{#1}
\DeclarePairedDelimiterX{\bracks}[1]{\lbrack}{\rbrack}{#1}
\DeclarePairedDelimiterX{\verts}[1]{|}{|}{#1}
\DeclarePairedDelimiterX{\Verts}[1]{\|}{\|}{#1}
\newcommand{\as}{{\quad\textrm{as}\quad}}
\newcommand{\st}{{\textrm{ s.t. }}}
\DeclarePairedDelimiterX{\setComprehension}[2]{\lbrace}{\rbrace}{#1\,\delimsize\vert\,#2}
\newcommand{\naturalNumbers}{\mathbb{N}}
\newcommand{\integers}{\mathbb{Z}}
\newcommand{\rationalNumbers}{\mathbb{Q}}
\newcommand{\realNumbers}{\mathbb{R}}
\newcommand{\complexNumbers}{\mathbb{C}}
\newcommand{\field}{\mathbb{F}}
\newcommand{\func}[2]{{#1}\parens*{#2}}
\newcommand*{\argmax}{\operatorname*{arg~max}}
\newcommand*{\argmin}{\operatorname*{arg~min}}
% set theory
\newcommand{\range}[2]{\braces*{#1,\dotsc,#2}}
\providecommand{\complement}{}\renewcommand{\complement}{\mathrm{c}}
\newcommand{\ind}[2]{\mathbbm{1}_{#1}\parens*{#2}}
\newcommand{\indII}[1]{\mathbbm{1}\braces*{#1}}
% number theory
\newcommand{\abs}[1]{\verts*{#1}}
\newcommand{\combi}[2]{{_{#1}\mathrm{C}_{#2}}}
\newcommand{\perm}[2]{{_{#1}\mathrm{P}_{#2}}}
\newcommand{\GaloisField}[1]{\mathrm{GF}\parens*{#1}}
% analysis
\newcommand{\NapierE}{\mathrm{e}}
\newcommand{\sgn}[1]{\operatorname{sgn}\parens*{#1}}
\newcommand*{\rect}{\operatorname{rect}}
\newcommand{\cl}[1]{\operatorname{cl}#1}
\newcommand{\Img}[1]{\operatorname{Img}\parens*{#1}}
\newcommand{\dom}[1]{\operatorname{dom}\parens*{#1}}
\newcommand{\norm}[1]{\Verts*{#1}}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\expo}[1]{\exp\parens*{#1}}
\newcommand{\sinc}{\operatorname{sinc}}
\newcommand{\nsinc}{\operatorname{nsinc}}
\newcommand{\GammaFunc}[1]{\Gamma\parens*{#1}}
\newcommand*{\erf}{\operatorname{erf}}
% inverse trigonometric functions
\newcommand{\asin}[1]{\operatorname{Sin}^{-1}{#1}}
\newcommand{\acos}[1]{\operatorname{Cos}^{-1}{#1}}
\newcommand{\atan}[1]{\operatorname{{Tan}^{-1}}{#1}}
\newcommand{\atanEx}[2]{\atan{\parens*{#1,#2}}}
% convolution
\newcommand{\cycConv}[2]{{#1}\underset{\text{cyc}}{*}{#2}}
% derivative
\newcommand{\deriv}[3]{\frac{\operatorname{d}^{#3}#1}{\operatorname{d}{#2}^{#3}}}
\newcommand{\derivLong}[3]{\frac{\operatorname{d}^{#3}}{\operatorname{d}{#2}^{#3}}#1}
\newcommand{\partDeriv}[3]{\frac{\operatorname{\partial}^{#3}#1}{\operatorname{\partial}{#2}^{#3}}}
\newcommand{\partDerivLong}[3]{\frac{\operatorname{\partial}^{#3}}{\operatorname{\partial}{#2}^{#3}}#1}
\newcommand{\partDerivIIHetero}[3]{\frac{\operatorname{\partial}^2#1}{\partial#2\operatorname{\partial}#3}}
\newcommand{\partDerivIIHeteroLong}[3]{{\frac{\operatorname{\partial}^2}{\partial#2\operatorname{\partial}#3}#1}}
% integral
\newcommand{\integrate}[5]{\int_{#1}^{#2}{#3}{\mathrm{d}^{#4}}#5}
\newcommand{\LebInteg}[4]{\int_{#1} {#2} {#3}\parens*{\mathrm{d}#4}}
% complex analysis
\newcommand{\conj}[1]{\overline{#1}}
\providecommand{\Re}{}\renewcommand{\Re}[1]{{\operatorname{Re}{\parens*{#1}}}}
\providecommand{\Im}{}\renewcommand{\Im}[1]{{\operatorname{Im}{\parens*{#1}}}}
\newcommand{\Arg}{\operatorname{Arg}}
\newcommand{\Log}{\operatorname{Log}}
% Laplace transform
\newcommand{\LPLC}[1]{\operatorname{\mathcal{L}}\parens*{#1}}
\newcommand{\ILPLC}[1]{\operatorname{\mathcal{L}}^{-1}\parens*{#1}}
% Discrete Fourier Transform
\newcommand{\DFT}[1]{\mathrm{DFT}\parens*{#1}}
% Z transform
\newcommand{\ZTrans}[1]{\operatorname{\mathcal{Z}}\parens*{#1}}
\newcommand{\IZTrans}[1]{\operatorname{\mathcal{Z}}^{-1}\parens*{#1}}
% linear algebra
\newcommand{\bm}[1]{{\boldsymbol{#1}}}
\newcommand{\matEntry}[3]{#1\bracks*{#2}\bracks*{#3}}
\newcommand{\matPart}[5]{\matEntry{#1}{#2:#3}{#4:#5}}
\newcommand{\diag}[1]{\operatorname{diag}\parens*{#1}}
\newcommand{\tr}[1]{\operatorname{tr}{\parens*{#1}}}
\newcommand{\inprod}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\HadamardProd}{\odot}
\newcommand{\HadamardDiv}{\oslash}
\newcommand{\Span}[1]{\operatorname{span}\bracks*{#1}}
\newcommand{\Ker}[1]{\operatorname{Ker}\parens*{#1}}
\newcommand{\rank}[1]{\operatorname{rank}\parens*{#1}}
% vector
% unit vector
\newcommand{\vix}{\bm{i}_x}
\newcommand{\viy}{\bm{i}_y}
\newcommand{\viz}{\bm{i}_z}
% probability theory
\newcommand{\PDF}[2]{\operatorname{PDF}\bracks*{#1,\;#2}}
\newcommand{\Ber}[1]{\operatorname{Ber}\parens*{#1}}
\newcommand{\Beta}[2]{\operatorname{Beta}\parens*{#1,#2}}
\newcommand{\ExpDist}[1]{\operatorname{ExpDist}\parens*{#1}}
\newcommand{\ErlangDist}[2]{\operatorname{ErlangDist}\parens*{#1,#2}}
\newcommand{\PoissonDist}[1]{\operatorname{PoissonDist}\parens*{#1}}
\newcommand{\GammaDist}[2]{\operatorname{Gamma}\parens*{#1,#2}}
\newcommand{\cind}[2]{\ind{#1\left| #2\right.}} % conditional indicator function
\providecommand{\Pr}{}\renewcommand{\Pr}[1]{\operatorname{Pr}\parens*{#1}}
\DeclarePairedDelimiterX{\cPrParens}[2]{(}{)}{#1\,\delimsize\vert\,#2}
\newcommand{\cPr}[2]{\operatorname{Pr}\cPrParens{#1}{#2}}
\newcommand{\E}[2]{\operatorname{E}_{#1}\bracks*{#2}}
\newcommand{\cE}[3]{\E{#1}{\left.#2\right|#3}}
\newcommand{\Var}[2]{\operatorname{Var}_{#1}\bracks*{#2}}
\newcommand{\Cov}[2]{\operatorname{Cov}\bracks*{#1,#2}}
\newcommand{\CovMat}[1]{\operatorname{Cov}\bracks*{#1}}
% graph theory
\newcommand{\neighborhood}{\mathcal{N}}
% programming
\newcommand{\plpl}{\mathrel{++}}
\newcommand{\pleq}{\mathrel{+}=}
\newcommand{\asteq}{\mathrel{*}=}
\]
M 系列の構成 準備 以下では素数位数の有限体の拡大体の表現として多項式表現を用い、不定元を $x$ とする。
ℹ️ 拡大体の表現には 2 通りの方法がある。これについては「Wolfram 言語＆システム・ドキュメント・センター＞ FiniteField ＞詳細 」が参考になる。
以下では素数位数として 2 を選び、多項式の係数の四則演算は $\GaloisField{2}$ 上で行う。
$N$ を自然数とする。$\GaloisField{2}$ 上の $N$ 次の原始多項式 $p(x)$ を考える（参考：原始多項式の定数項は必ず 1 である）。$N-1$ 次多項式の列 $f_n(x)\;(n=0,1,2,\dots)$ を次の規則で定める。
初期値：$f_0(x)$：恒等的に 0 であるものを除く、任意の $N-1$ 次以下の多項式
漸化式：$f_{n+1}(x) = (x f_n(x))\%p(x)$
合同式の性質を用いると $f_n(x)\equiv x f_{n-1}(x)\equiv x^2 f_{n-2}(x)\equiv\dots\equiv x^n f_0(x)\equiv (x^n f_0(x))\%p(x)$ である。
とくに初期値が 1 であるときは $f_n(x)\equiv x^n\;\%p(x)$ である。$p(x)$ は原始多項式であるから $x$ は $\GaloisField{2^N}$ の原始元である。つまり $f_n(x)\;(n=0,1,2,\dots,2^N-2)$ は全て異なり、周期は $2^N-1$ である（$x^{2^N-1}\equiv 1$）。
初期値が 1 でない場合も周期は $2^N-1$ である。なぜならば $x^n\;(n=0,1,\dots)$ は「恒等的に 0 であるものを除く、任意の $N$ 次以下の多項式」の集合上を $2^N-1$ 周期で隈なく動くから、ある時点で前記の初期値と一致し、そこを起点として漸化式に従って $2^N-1$ 周期が見出されるからである。
本題 $a_{N-1}(n)\;(n=0,1,\dots)$ を M 系列と呼ぶ。M 系列の周期は $2^N-1$ である。これは次のようにして示される。$p(x)$ の定数項が 1 であることと、「準備 」で示した漸化式から $a_{N-1}(n+k)\;(k=0,1,\dots,N-1)$ によって $a_{N-1}(n+N)$ が一意に定まる（多項式の除算の筆算を考えれば解る）。よって仮に $a_{N-1}(n)$ の周期が $2^N-1$ 未満であると $f_n(x)$ の周期も $2^N-1$ 未満となり、事実に矛盾する。故に $a_{N-1}(n)$ の周期 は $2^N-1$ 以上である。さらに $f_n(x)$ の周期 $2^N-1$ を超えることもないから、結局 $a_{N-1}(n)$ の周期は $2^N-1$ である。
線形変換表現 \[\newcommand{\Mt}{M_\text{t}}\]
$f_n(x)$ の $i$ 次の項の係数を $a_i(n)$ とし、 $\bm{a}(n)\coloneqq[a_0(n),a_1(n),\dots,a_{N-1}(n)]^\top$ とする。これを「状態ベクトル」と呼ぶことにする。これは $f_n(x)$ と一対一対応する。
$p(x)$ と一対一対応する $\Mt\in\GaloisField{2}^{N\times N}$ が必ず存在し（多項式の除算の筆算を考えれば解る）、$\bm{a}(n+1)=\Mt\bm{a}(n)$ が成り立つ。この行列を「状態遷移行列」と呼ぶことにする。$p(x)$ の定数項が 1 であることと、「準備 」で示した漸化式から、$\Mt$ は次の形をしている。
\[
\Mt = \begin{bmatrix}
\bm{0}_{N-1}^\top & 1 \\
\bm{I}_{N-1} & \bm{*}_{N-1}
\end{bmatrix}
\]
ここに、$\bm{0}_{N-1}$ は $N-1$ 次の零ベクトル、$\bm{I}_{N-1}$ は $(N-1)\times(N-1)$ の単位行列、$\bm{*}_{N-1}$ は $N-1$ 次の任意のベクトルである。
具体例 $p(x)=x^4+x+1,\;f_0(x)=1$ を例にとる。周期は $2^4-1=15$ であり、状態遷移行列は次式である。
\[
\Mt = \begin{bmatrix}
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 1 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{bmatrix}
\]
1 周期分の状態を示す。
$n$ $f_n(x)$ $\bm{a}(n)$ 0 1 $[1,0,0,0]^\top$ 1 $x$ $[0,1,0,0]^\top$ 2 $x^2$ $[0,0,1,0]^\top$ 3 $x^3$ $[0,0,0,1]^\top$ 4 $x+1$ $[1,1,0,0]^\top$ 5 $x^2+x$ $[0,1,1,0]^\top$ 6 $x^3+x^2$ $[0,0,1,1]^\top$ 7 $x^3+x+1$ $[1,1,0,1]^\top$ 8 $x^2+1$ $[1,0,1,0]^\top$ 9 $x^3+x$ $[0,1,0,1]^\top$ 10 $x^2+x+1$ $[1,1,1,0]^\top$ 11 $x^3+x^2+x$ $[0,1,1,1]^\top$ 12 $x^3+x^2+x+1$ $[1,1,1,1]^\top$ 13 $x^3+x^2+1$ $[1,0,1,1]^\top$ 14 $x^3+1$ $[1,0,0,1]^\top$
1 周期分の状態 順序回路による実装の模式図を示す。矩形はレジスタを表す。
Galois LFSR with p(x)=x^4+x+1
「線形変換表現 」で述べた $\Mt$ の性質により、$p(x)$ の具体的な形に依らず $a_1(n+1) = a_{N-1}(n)$ であり、$a_i(n+1)\;(i=1,2,\dots,N-1)$ は $a_{i-1}(n)$ または $a_{i-1}(n)\oplus a_{N-1}(n)$ の何れかである。このような構造を Galois LFSR (Linear Feedback Shift Register) と呼ぶ。
並列計算 方法 \[\newcommand{\vap}{\bm{a}_\text{p}}\]
M 系列を順序回路、例えば ASIC や FPGA で生成することを考える。前掲の順序回路の図 に示したような Galois LFSR は 1 クロック・サイクルにつき 1 bit しか生成できない。FPGA の動作周波数は 2025 年現在、ハイエンド製品でも 500 MHz が精々である。これを超えるスループットで生成するためには、1 クロック・サイクルにつき複数 bit を生成する必要がある。
FIFO と back pressure を利用し、生成回路では 1 クロック・サイクルで $P(>1)$ 個または 0 個（休みのサイクル。クロックを止める）の bit を生成する構成をとる。状態ベクトルの初期値を最初の $P$ ステップ分まとめて用意し、その後は 1 クロック・サイクルにつき $P$ ステップ先を求めるように更新する。
初期化：$\vap(0)\coloneqq\begin{bmatrix}\bm{a}(0),\bm{a}(1),\dots,\bm{a}(P-1)\in\GaloisField{2}^{N\times P}\end{bmatrix}$
更新：$\vap(n+1) = \Mt^P\vap(n)$
$\vap(n)$ の第 $N-1$ 行が M 系列である。
具体例 $p(x)=x^4+x+1,\;f_0(x)=1$ の例を示す。
