フィボナッチ LFSR
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 23:00 UTC 版)
「線形帰還シフトレジスタ」の記事における「フィボナッチ LFSR」の解説
LFSRで、次の入力ビットに影響を与えるビットを「タップ (tap)」と呼び、それらの位置を列挙したものをタップシーケンスと呼ぶ。図では、タップシーケンスが [16, 14, 13, 11, 0] である。タップは順次XORされ、その結果が左端にフィードバックされる。 入力に影響する出力を「タップ」と呼ぶ（図では黒）。 最長LFSRはM系列を生成する。最長LFSRとは、全ビットがゼロという状態以外の全てのとりうる状態（ 2 n − 1 {\displaystyle 2^{n}-1} ）が周期に現れるLFSRである。（全ビットがゼロの場合、全く変化しない。初期状態として設定しない限り、最長LFSRにおいて自然にそうなることはない） LFSRの生成するビット列は、2進数やグレイコードと見なすことができる。 LFSRのタップシーケンスは2を法とする多項式で表せる。つまり、多項式の各項の係数は1か0である。これを帰還多項式あるいは特性多項式と呼ぶ。例えば、図のようにタップが16番目、14番目、13番目、11番目にあるとき、帰還多項式は次のようになる。 x 16 + x 14 + x 13 + x 11 + 1 {\displaystyle x^{16}+x^{14}+x^{13}+x^{11}+1\,} 最後に1があるが、これはタップとは対応していない。これは、最初のビットへの入力に対応している（つまり、x0 であり、1と等価である）。各項のべき乗部分はタップ位置を表していて、左端から何番目かに対応している。左端は常に入力、右端は常にタップとして連結する。 LFSRは、帰還多項式が（タップシーケンス）は原始多項式であるならば最長LFSRとなる。よって、次の性質を持つ。 最長LFSRのタップ数は必ず偶数。非常に長いレジスタであっても2個や4個のタップで十分である。 最長LFSRのタップ集合は互いに素でなければならない。つまり、全タップ間の1以外の公約数が存在してはならない。 最大LFSRを構築することができる原始多項式のリストを、下の表と参考文献に示す。 LFSRの長さによっては、最長となる複数の多項式が存在する。この場合、最長となるタップシーケンスが1つ見つかると、他は自動的に得られる。nビットのLFSRで、タップシーケンス [n,A,B,C,0] が見つかったとき（0は x 0 = 1 {\displaystyle x^{0}=1} に対応）、もう1つのタップシーケンスは [n,n-C,n-B,n-A,0] である。例えば、[32,3,2,0] に対応するのは [32,30,29,0] である。どちらも最長である。 C/C++ のコーディング例を以下に示す。 uint16_t reg = 0xACE1; uint16_t bit; while(1) { bit = (reg & 0x0001) ^ ((reg & 0x0004) >> 2) ^ ((reg & 0x0008) >> 3) ^ ((reg & 0x0020) >> 5); reg = (reg >> 1) | (bit << 15); printf("%04X\n",reg); } このコードでは、左端ビットが1番目の位置である。
※この「フィボナッチ LFSR」の解説は、「線形帰還シフトレジスタ」の解説の一部です。
「フィボナッチ LFSR」を含む「線形帰還シフトレジスタ」の記事については、「線形帰還シフトレジスタ」の概要を参照ください。
- フィボナッチ LFSRのページへのリンク
