LFSR（線形帰還シフトレジスタ）計算機

LFSR（線形帰還シフトレジスタ）とは？

**線形帰還シフトレジスタ（LFSR: Linear Feedback Shift Register）**は、入力ビットが直前の状態の線形関数（主に排他的論理和：XOR）によって決定されるシフトレジスタです。

構造は非常に単純ですが、適切な「タップ（帰還させるビット位置）」を選択することで、レジスタが取りうるすべての状態（すべて0の状態を除く $2^n - 1$ 通り）を循環する**M系列（最長周期系列）**と呼ばれる高度な擬似乱数シーケンスを生成できます。

LFSRの動作原理：フィボナッチ構成

もっとも一般的な「フィボナッチ(Fibonacci)構成」では、以下のプロセスを繰り返します。

1. 特定のビット位置（タップ）から値を取り出す。
2. 取り出したビット同士で**XOR（排他的論理和）**演算を行う。
3. レジスタ全体を1ビット右にシフトする。
4. XORの結果を一番左の空いたスロット（MSB）に挿入する。

なぜLFSRが重要なのか？：現代社会を支える技術

1. 擬似乱数生成器 (PRNG)

LFSRはハードウェア実装が極めて容易（フリップフロップとXORゲート数個で構成可能）なため、FPGAやASICなどのデジタル回路における乱数生成に広く使われています。

2. ストリーム暗号

生成されるビット列が非常に長い周期を持つため、暗号化の鍵ストリームとして利用されます。古典的なGSM携帯電話の暗号化方式「A5/1」なども、複数のLFSRを組み合わせた構造を持っています。

3. 通信の誤り検出 (CRC)

データ通信でノイズによるエラーがないかチェックする**CRC（巡回冗長判定）**は、実質的にLFSR回路による多項式除算を行っているのと同義です。EthernetやUSB、Wi-Fiなど、身近な通信規格のすべてにこの技術が組み込まれています。

M系列（最長周期系列）と原始多項式

nビットのレジスタで、周期が最大の $2^n - 1$ になるためには、タップの選び方が**原始多項式（Primitive Polynomial）**になっていなければなりません。

• 4-bitの場合: タップ [4, 3] で周期 15
• 8-bitの場合: タップ [8, 6, 5, 4] で周期 255
• 16-bitの場合: タップ [16, 14, 13, 11] で周期 65,535

本計算機では、これらの推奨タップ値を設定して、実際にどのようにビットが循環するかをリアルタイムに確認できます。

まとめ

LFSRは、数学的な美しさと実務的な効率性を兼ね備えた、知る人ぞ知るデジタル界の「名脇役」です。一見ランダムに見えるビットの羅列が、実は厳密な論理式に基づいて踊っている様子を、本プログラムを通じて感じ取ってみてください。

よくある質問 (FAQ)