LFSRとは？ わかりやすく解説

線形帰還シフトレジスタ（せんけいきかんシフトレジスタ、英: linear feedback shift register, LFSR）は、入力ビットが直前の状態の線形写像になっているシフトレジスタである。

値域が単一のビットとなる線形写像は、XORおよびXORの否定だけである。したがって、線形帰還シフトレジスタとは、その値を構成するビット列の一部の排他的論理和を入力ビットとするシフトレジスタである。

LFSR の初期値をシードと呼ぶ。レジスタの動作は決定的であるため、レジスタが生成する値の列はその状態によって完全に決定される。同様に、レジスタの取りうる状態は有限個であるため、最終的に周期的動作になる。しかし、帰還関数をうまく設定したLFSRは乱数のようなビット列を生成し、その周期も非常に長い。

LFSRの用途としては、擬似乱数生成、擬似ノイズ生成、高速デジタルカウンタ、白色化などがある。LFSR にはハードウェアによる実装もソフトウェアによる実装もある。

LFSRで、次の入力ビットに影響を与えるビットを「タップ (tap)」と呼び、それらの位置を列挙したものをタップシーケンスと呼ぶ。図では、タップシーケンスが [16, 14, 13, 11, 0] である。タップは順次XORされ、その結果が左端にフィードバックされる。

• 入力に影響する出力を「タップ」と呼ぶ（図では黒）。
• 最長LFSRはM系列を生成する。最長LFSRとは、全ビットがゼロという状態以外の全てのとりうる状態（ ${\displaystyle 2^{n}-1}$

  通常のLFSRと同じ出力シーケンスを得るには、ビット順序を逆にする（図参照）。そうしないとシーケンスが逆転する。なお、LFSRの内部状態は同じである必要はない。図に示したガロアLFSRは、上の図で示したフィボナッチLFSRと同じ出力となる。

  • ガロアLFSRでは、全タップの値を使って入力を生成するわけではなく、XORは個別に各タップ位置で行われる。つまり、XOR演算を並列に実行でき、高速化が可能である。
  • ソフトウェアで実装すると、ワード全体のビット演算で一度にXORできるので、さらに効率的な実装になる。

  以下は32ビットの最長ガロアLFSRをC言語およびC++で実装したものである（unsigned int は32ビットと仮定）。

          unsigned int lfsr = 1;
          unsigned int period = 0; 
          do {
                  lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0xd0000001u); /* taps 32 31 29 1 */
                  ++period;
          } while(lfsr != 1u);
  

  次のコードは、図にある16ビットの例である。

          unsigned short lfsr = 0xACE1u;
          unsigned int period = 0; 
          do {
                  lfsr = (lfsr >> 1) ^ (-(short)(lfsr & 1u) & 0xB400u); 
                  ++period;
          } while(lfsr != 0xACE1u);
  

  最長LFSRとなる多項式の例

  ビット数	帰還多項式	周期
  n		${\displaystyle 2^{n}-1}$
  4	${\displaystyle x^{4}+x^{3}+1}$	15
  5	${\displaystyle x^{5}+x^{3}+1}$	31
  6	${\displaystyle x^{6}+x^{5}+1}$	63
  7	${\displaystyle x^{7}+x^{6}+1}$	127
  8	${\displaystyle x^{8}+x^{6}+x^{5}+x^{4}+1}$	255
  9	${\displaystyle x^{9}+x^{5}+1}$	511
  10	${\displaystyle x^{10}+x^{7}+1}$	1023
  11	${\displaystyle x^{11}+x^{9}+1}$	2047
  12	${\displaystyle x^{12}+x^{11}+x^{10}+x^{4}+1}$	4095
  13	${\displaystyle x^{13}+x^{12}+x^{11}+x^{8}+1}$	8191
  14	${\displaystyle x^{14}+x^{13}+x^{12}+x^{2}+1}$	16383
  15	${\displaystyle x^{15}+x^{14}+1}$	32767
  16	${\displaystyle x^{16}+x^{14}+x^{13}+x^{11}+1}$	65535
  17	${\displaystyle x^{17}+x^{14}+1}$	131071
  18	${\displaystyle x^{18}+x^{11}+1}$	262143
  19	${\displaystyle x^{19}+x^{18}+x^{17}+x^{14}+1}$	524287
  25 to 168	[1]

  出力ストリームの特性

  • 1と0は連続して出現することがある。例えば、出力ストリーム 0110100 は5つの連続から構成されていると見ることができ、その長さは順に 1,2,1,1,2 である。最長LFSRの1周期には ${\displaystyle 2^{n-1}}$ 個の連続が出現する（例えば、6ビットのLFSRでは32個の連続がある）。そのうち ${\displaystyle 1/2}$ は長さが1、 ${\displaystyle 1/4}$ は長さが2ビットで、0の最長の連続は ${\displaystyle n-1}$ ビットであり、1の最長の連続は ${\displaystyle n}$ ビットが1回だけある。これは真の乱数の統計的特性と全く同じである。
  • LFSRの出力ストリームは決定的である。現在の状態を知っていれば、次の状態を正確に予測できる。これは真に無作為な事象にはない特徴である。
  • 出力ストリームは両方向である。最長LFSRとなるタップシーケンスが2つある場合、両者の状態遷移は逆順序になる。

  用途

  LFSRはハードウェアでも実装できるため、高速な擬似乱数生成が必要な場面で便利である（直接シーケンス・スペクトラム拡散無線通信など）。

  レーダーは、LFSRを使って送信波と受信波の時間差を測定し、反射体までの距離を判定するものがある。グローバル・ポジショニング・システムは、LFSRを使って高精度な相対時間オフセットを示すシーケンスを高速に転送する。ファミリーコンピュータはサウンドシステムの一部としてLFSRを装備している([2])。

  カウンタとしての利用

  コンピュータのインデックスやフレーム指示位置は機械可読である必要がある。そこで順に増えていく2進数でなくてもよい場合、LFSRの周期的シーケンスを分周器やカウンタとして使うことができる。LFSRカウンタは、通常の2進カウンタやグレイコードカウンタよりもフィードバック論理回路が単純で、より高速に動作させることができる。ただし、LFSR全体が0にならないよう保証する必要があり、例えば初期状態のプリセットが必要である。上の表はLFSRの最長周期が記してある。必要な周期よりも長い周期のLFSRに状態をスキップする論理回路を付加することで、任意の周期のカウンタを得ることができる。

  暗号での利用

  LFSRは、（特に軍事用途で）ストリーム暗号の擬似乱数生成器として使われてきた。これは機械式でも電子回路でも構成が簡単で、周期が長く分布が一様なためである。しかし、LFSRは線形システムであるため、暗号解読は比較的容易である。平文と対応する暗号文がわかっているとき、システムの使用するLFSRの出力を再現でき、Berlekamp–Masseyアルゴリズムを使って最小サイズのLFSRを構築でき、容易に暗号文を復号できるようになる。

  LFSRに基づく暗号におけるこのような問題への対策として、一般に以下の3つの手法がある。

  • LFSRの状態のうち、一部のビットを非線形に組み合わせて使う。
  • 2つ以上のLFSRの出力を非線形に組み合わせて使う。
  • LFSRのクロックを不定間隔で進める（alternating step generator）。

  LFSRに基づくストリーム暗号としては、GSM携帯電話で使っている A5/1 や A5/2、Bluetooth で使っている E0、shrinking generator などがある。A5/2 は既に破られており、A5/1 と E0 も非常に弱いと言われている。LTEの暗号アルゴリズムUEA2,UIA2で使用されているストリーム暗号 SNOW 3Gも、LFSRを利用している。^[1]

  デジタル放送/通信での利用

  0や1が連続すると、シンボルの区切りがわからなくなる危険性があるため、線形帰還シフトレジスタを使ってビットストリームを無作為化することが多い。この無作為化は受信側で復調後に除去される。LFSRと転送シンボルストリームが同じレートで動作する場合、この技法をスクランブリングと呼ぶ。LFSRの方がシンボルストリームよりずっと高速に動作し、信号送信時の帯域幅を拡張させる場合、これを直接シーケンス・スペクトラム拡散と呼ぶ。

  LFSRによるスクランブリングは暗号化ではなく、解読には、一般的な暗号において必要な困難は全く無い。

  LFSRを使っているデジタル放送システム:

  • ATSC （北米）
  • DAB （デジタルラジオ）
  • DVB-T （ヨーロッパ、オーストラリア）
  • NICAM （イギリスなどのテレビ用デジタル音声システム）

  その他のLFSRを使っているデジタル通信システム:

  • IBS (INTELSAT business service)
  • IDR (Intermediate Data Rate service)
  • SDI （シリアルデジタルインタフェース）
  • 公衆交換電話網上のデータ転送（ITU-TのVシリーズ勧告）
  • CDMA携帯電話
  • 100BASE-T2 高速イーサネットでは、LFSRでビットのスクランブルを行う。
  • 1000BASE-T イーサネットでも、LFSRでビットのスクランブルを行う。

  脚注

  [脚注の使い方]
  1. ^ Specification of the 3GPP Confidentiality and Integrity Algorithms UEA2 & UIA2; Document 2: SNOW 3G specification

  関連項目

  • メルセンヌ・ツイスタ

  外部リンク

  • LFSR Reference LFSRの理論と実装
  • International Telecommunications Union Recommendation O.151 （1992年8月）
  • Maximal Length LFSR table 3から168までの長さのLFSRの最長タップシーケンスがある。
  • Maximal Length LFSR table 長さ 1 から 786 までと、1024 と 2048 と 4096。
  • Pseudo-Random Number Generation Routine
  • Linear Feedback Shift Register
  • Shift-Register Stream Ciphers
  • Simple explanation of LFSRs for Engineers
  • Feedback terms
  • General LFSR Theory
  • Table of Maximal Tap Sequences
  • Shift register code generator