線形フィードバックシフトレジスタLFSR,一般フィードバックシフトレジスタGFSRのメモ
線形フィードバックシフトレジスタLFSR,一般フィードバックシフトレジスタGFSRのメモ
前回はざっくりM系列法のメモだったが，今回はM系列を利用している線形フィードバックシフトレジスタLFSRと一般フィードバックシフトレジスタGFSRのメモ．
かんたんな流れとしては
- LFSR：1bitのみ
- GFSR: ベクトル化して複数bitに対応できるように拡張
- 3項GFSR
- 5項GFSR：項を増やしてランダム性を改善
2元体の定義
二元体$\mathbb{F}_{2}:= {0, 1}$ とおく．
0,1の掛け算は普通に定義しても、$\mathbb{F}_{2}$から，はみ出ない。
足し算は1 + 1 = 2だけが$\mathbb{F}_{2}$からはみ出してしまうので、
$$ 1 + 1 = 0 $$
と定義する（つまり，2で割った余りを見ている）.
Tausworthe法あるいはLinear Feedbacked Shift Register法（LFSR法）と言う (Tausworthe, 1965)
参考：http://www.math.sci.hiroshima-u.ac.jp/~m-mat/TEACH/ichimura-sho-koen.pdf
LFSR
この2元体$\mathbb{F}_{2}$での漸化式
このような$\mathbb{F}_{2}$上の高階線形漸化式を用いて0-1列を生成、擬似乱数として用いる方法を Tausworthe法あるいはLinear Feedbacked Shift Register法（LFSR法） という．
例1
0b100を初期seedとする．
| n=8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| - | - | - | - | - | 1 | 1 | 0 | 0 |
| - | - | - | - | 1 | 1 | 1 | 0 | 0 |
| - | - | - | 0 | 1 | 1 | 1 | 0 | 0 |
| - | - | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| - | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
例2
で数列を作ると周期が$2^{607} − 1 = 5.3 \times 10^{182}$となることが示せる．
LFSRの特徴
メリット：
実験ではなく、数学的証明によってのみ周期を示せる．
「2か所見て($x_{n}, x_{n+q}$)、足して、1か所に書く($x_{n+p}$)」という動作のため，周期を長くしても、生成速度が遅くならない．
周期が極大なので、「全て0」以外のビットパターンが $(x_{n-1}, \cdots , x_{n+p-1}), (n = 1, 2, \cdots , 2^{p} − 1)$ のなかにちょうど一度だけ現れる（p次元均等分布性）
1ペタFlopsのコンピュータは、1秒に$10^{15}$回の計算しかできないので，p=607にでもすれば，1周期すべてを求めることはできない．
GFSR
GFSR(Lewis-Payne, 1973)： LFSRをベクトル化して複数ビットの整数をそのまま扱えるようにしたもの
計算機ワード長の$\mathbb{F}_{2}$ベクトル列を
で生成(+は$\mathbb{F}_{2}$ベクトルとしての和)する．
※ベクトルで表現されているが，bitを複数にしただけなので，ただの2進整数になる．
例： 4ビットコンピュータなら4ビット同時に作る
例：4bit
$p=3, q=2$ とすると，
- $\vec{x}_{0} = \mathrm{0b}0101$
- $\vec{x}_{1} = \mathrm{0b}0110$
- $\vec{x}_{2} = \mathrm{0b}1111$
| $\vec{x}$ | 3 | 2 | 1 | 0 |
|---|---|---|---|---|
| $\vec{x}_{0}$ | 0 | 1 | 0 | 1 |
| $\vec{x}_{2}$ | 1 | 1 | 1 | 1 |
| $\vec{x}_{3}$ | 1 | 0 | 1 | 0 |
| $\vec{x}$ | 3 | 2 | 1 | 0 |
|---|---|---|---|---|
| $\vec{x}_{1}$ | 0 | 1 | 1 | 0 |
| $\vec{x}_{3}$ | 1 | 0 | 1 | 0 |
| $\vec{x}_{4}$ | 1 | 1 | 0 | 0 |
| $\vec{x}$ | 3 | 2 | 1 | 0 |
|---|---|---|---|---|
| $\vec{x}_{2}$ | 1 | 1 | 1 | 1 |
| $\vec{x}_{4}$ | 1 | 1 | 0 | 0 |
| $\vec{x}_{5}$ | 0 | 0 | 1 | 1 |
特徴
GFSRの特徴：
- 整定数$p, q$をうまく選ぶと周期$2^{p} − 1$にできる.
- $p$として31～607が良く使われていた
- 各桁はLFSRで生成される数列に一致）
3項GFSR
特に，2項を使って3項目を求めるのは3項GFSRという．
JIS規格Z9031 5.4.2節でも記述されている．
- 整数定数：$p>q$
- $\vec{x}_{n}$：wビット二進整数である
- パラメータは$(p, q, w)$であり，seedは$(\vec{x}_{0}，\cdots，\vec{x}_{p-1})$である
- 特性多項式：$t^{p}＋t^{q}＋1 $
メリット：
- 2項のみ使うので高速
- 周期が長い，よく使われる周期として， $2^{89}−1$ から $2^{9689}−1$ までの間となる。
デメリット：
- seed依存性：seedとして $\vec{x}_{0}，\vec{x}_{1}, \cdots，\vec{x}_{p-1}$の p 個の値を与える必要があるが，生成される数列の乱数性はこれらのseedに強く依存するので，ユーザが勝手に与えるのは危険
- $p$ を超えた個数の連続する疑似乱数の組を見ると，各ビットに現れる 0 の数及び 1 の数は対称的に分布しない。特に，ランダムウォークなど，過去の長い（p 以上の）履歴に依存する高次元分布が問題となるシミュレーションに使うのは危険.
5項 GFSR 法
これは，4項を利用して5項目を求める．
5項の特性多項式を使用するものであり，以下の漸化式でwビットの2進整数の列を生成する．
ある。
特徴：
- 3項GFSR法に比べ，1，0の偏りは小さくなっている。
- 最大周期：$2^{p}−1$
- パラメータ：$(p, q_{1}, q_{2}, q_{3}, w)$
- seed: $\vec{x}_{0}, \cdots , \vec{x}_{p-1}$
JIS Z9031 5.4.3節で示されている 最大周期を与える$p，q_{1}，q_{2}，q_{3}$の組合せの例を表に示す。
| p | q1 | q2 | q3 |
|---|---|---|---|
| 89 | 20 | 40 | 69 |
| 107 | 31 | 57 | 82 |
| 127 | 22 | 63 | 83 |
| 521 | 86 | 197 | 447 |
| 607 | 167 | 307 | 461 |
| 1279 | 339 | 630 | 988 |
| 2203 | 585 | 1197 | 1656 |
| 2281 | 577 | 1109 | 1709 |
| 3217 | 809 | 1621 | 2381 |
| 4253 | 1093 | 2254 | 3297 |
| 4423 | 1171 | 2273 | 3299 |
| 9689 | 2799 | 5463 | 7712 |
