線形帰還シフトレジスタのソースを表示

'''線形帰還シフトレジスタ'''（せんけいきかんシフトレジスタ、{{lang-en-short|linear feedback shift register, LFSR}}）は、入力ビットが直前の状態の[[線型写像|線形写像]]になっている[[シフトレジスタ]]である。

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

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

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

== フィボナッチ LFSR ==
[[ファイル:LFSR-F16.png|thumb|right|350px|16ビットのフィボナッチLFSR。タップ番号を黒で示しており、それが多項式の項に対応する。これは最長LFSRであり、全て0の状態以外の65535個の状態遷移をする。図示されている状態 ACE1（[[十六進法|16進]]）の後は 5670 となる。]]
LFSRで、次の入力ビットに影響を与えるビットを「タップ (tap)」と呼び、それらの位置を列挙したものをタップシーケンスと呼ぶ。図では、タップシーケンスが [16, 14, 13, 11, 0] である。タップは順次XORされ、その結果が左端にフィードバックされる。

* 入力に影響する出力を「タップ」と呼ぶ（図では黒）。
* 最長LFSRは[[M系列]]を生成する。最長LFSRとは、全ビットがゼロという状態以外の全てのとりうる状態（<math>2^n-1</math>）が周期に現れるLFSRである。（全ビットがゼロの場合、全く変化しない。初期状態として設定しない限り、最長LFSRにおいて自然にそうなることはない）

LFSRの生成するビット列は、[[二進法|2進数]]や[[グレイコード]]と見なすことができる。

LFSRのタップシーケンスは2を[[合同式|法とする]][[多項式]]で表せる。つまり、多項式の各項の係数は1か0である。これを帰還多項式あるいは特性多項式と呼ぶ。例えば、図のようにタップが16番目、14番目、13番目、11番目にあるとき、帰還多項式は次のようになる。
::<math>x^{16} + x^{14} + x^{13} + x^{11} + 1\,</math>

最後に1があるが、これはタップとは対応していない。これは、最初のビットへの入力に対応している（つまり、''x<sup>0</sup>'' であり、1と等価である）。各項のべき乗部分はタップ位置を表していて、左端から何番目かに対応している。左端は常に入力、右端は常にタップとして連結する。

LFSRは、帰還多項式が（タップシーケンス）は[[原始多項式]]であるならば最長LFSRとなる。よって、次の性質を持つ。
* 最長LFSRのタップ数は必ず[[偶数]]。非常に長いレジスタであっても2個や4個のタップで十分である。
* 最長LFSRのタップ集合は[[互いに素 (整数論)|互いに素]]でなければならない。つまり、全タップ間の1以外の公約数が存在してはならない。
最大LFSRを構築することができる原始多項式のリストを、下の表と参考文献に示す。

LFSRの長さによっては、最長となる複数の多項式が存在する。この場合、最長となるタップシーケンスが1つ見つかると、他は自動的に得られる。''n''ビットのLFSRで、タップシーケンス [n,A,B,C,0] が見つかったとき（0は <math>x^0=1</math> に対応）、もう1つのタップシーケンスは [n,n-C,n-B,n-A,0] である。例えば、[32,3,2,0] に対応するのは [32,30,29,0] である。どちらも最長である。

C/C++ のコーディング例を以下に示す。
<syntaxhighlight lang="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);
        }
</syntaxhighlight>
このコードでは、左端ビットが1番目の位置である。

== ガロア LFSR ==
フランス人数学者[[エヴァリスト・ガロア]]の名を冠したガロアLFSRは、通常のLFSRと同じビット列を生成できる別の構成である{{要出典|date=2008年9月}}。ガロアLFSRでは、タップでないビットはクロック毎に次の[[フリップフロップ]]にシフトされる（普通のLFSRと同じ）。タップの場合、新たな出力と前のビットの値をXORしたものを格納する。

[[ファイル:LFSR-G16.png|thumb|right|393 px|16ビットのガロアLFSR。黒い番号は上のフィボナッチLFSRと同じ多項式の項に対応しているが、シフト方向が逆である点に注意。このレジスタも全て0状態以外の65535個の最長の状態遷移をする。図に示されている ACE1 の状態の次は E270 となる（16進）。]]

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

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

以下は32ビットの最長ガロアLFSRを[[C言語]]および[[C++]]で実装したものである（unsigned int は32ビットと仮定）。
<syntaxhighlight lang="C++">
        unsigned int lfsr = 1;
        unsigned int period = 0; 
        do {
                lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0xd0000001u); /* taps 32 31 29 1 */
                ++period;
        } while(lfsr != 1u);
</syntaxhighlight>

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

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

== 最長LFSRとなる多項式の例 ==
{|class="wikitable"
|-
!ビット数
!帰還多項式
!周期
|-
!''n''
!
!<math>2^{n}-1</math>
|-
! 4 
!<math>x^{ 4 }+x^{ 3 }+1</math>
! 15 
|-
! 5 
!<math>x^{ 5 }+x^{ 3 }+1</math>
! 31 
|-
! 6 
!<math>x^{ 6 }+x^{ 5 }+1</math>
! 63 
|-
! 7 
!<math>x^{ 7 }+x^{ 6 }+1</math>
! 127 
|-
! 8 
!<math>x^{ 8 }+x^{ 6 }+x^{ 5 }+x^{ 4 }+1</math>
! 255 
|-
! 9 
!<math>x^{ 9 }+x^{ 5 }+1</math>
! 511 
|-
! 10 
!<math>x^{ 10 }+x^{ 7 }+1</math>
! 1023 
|-
! 11 
!<math>x^{ 11 }+x^{ 9 }+1</math>
! 2047 
|-
! 12 
!<math>x^{ 12 }+x^{ 11 }+x^{ 10 }+x^{ 4 }+1</math>
! 4095 
|-
! 13 
!<math>x^{ 13 }+x^{ 12 }+x^{ 11 }+x^{ 8 }+1</math>
! 8191 
|-
! 14 
!<math>x^{ 14 }+x^{ 13 }+x^{ 12 }+x^{ 2 }+1</math>
! 16383 
|-
! 15 
!<math>x^{ 15 }+x^{ 14 }+1</math>
! 32767 
|-
! 16 
!<math>x^{ 16 }+x^{ 14 }+x^{ 13 }+x^{ 11 }+1</math>
! 65535 
|-
! 17 
!<math>x^{ 17 }+x^{ 14 }+1</math>
! 131071 
|-
! 18 
!<math>x^{ 18 }+x^{ 11 }+1</math>
! 262143 
|-
! 19 
!<math>x^{ 19 }+x^{ 18 }+x^{ 17 }+x^{ 14 }+1</math>
! 524287
|-
!25 to 168
![http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf]
! 
|}

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

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

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

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

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

LFSRに基づく暗号におけるこのような問題への対策として、一般に以下の3つの手法がある。
* LFSRの状態のうち、一部の[[ビット]]を[[非線形システム論|非線形]]に組み合わせて使う。
* 2つ以上のLFSRの出力を非線形に組み合わせて使う。
* LFSRのクロックを不定間隔で進める（[[:en:Alternating step generator|alternating step generator]]）。

LFSRに基づくストリーム暗号としては、[[GSM]]携帯電話で使っている [[A5/1]] や [[A5/2]]、[[Bluetooth]] で使っている [[E0 (暗号)|E0]]、[[:en:shrinking generator|shrinking generator]] などがある。A5/2 は既に破られており、A5/1 と E0 も非常に弱いと言われている。LTEの暗号アルゴリズムUEA2,UIA2で使用されているストリーム暗号 [[:en:SNOW|SNOW 3G]]も、LFSRを利用している。<ref>[https://portal.3gpp.org/desktopmodules/Specifications/SpecificationDetails.aspx?specificationId=2396 Specification of the 3GPP Confidentiality and Integrity Algorithms UEA2 & UIA2; Document 2: SNOW 3G specification]</ref>

=== デジタル放送/通信での利用 ===
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]]携帯電話
* [[100メガビット・イーサネット#100BASE-T2|100BASE-T2 高速イーサネット]]では、LFSRでビットのスクランブルを行う。
* [[ギガビット・イーサネット#1000BASE-T|1000BASE-T イーサネット]]でも、LFSRでビットのスクランブルを行う。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 関連項目 ==
* [[メルセンヌ・ツイスタ]]

== 外部リンク ==
* [http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm LFSR Reference] LFSRの理論と実装
* [https://www.itu.int/rec/T-REC-O.151-199210-I/en International Telecommunications Union Recommendation O.151] （1992年8月）
* [http://www.xilinx.com/bvdocs/appnotes/xapp052.pdf Maximal Length LFSR table] 3から168までの長さのLFSRの最長タップシーケンスがある。
* [http://www.physics.otago.ac.nz/px/research/electronics/papers/technical-reports/lfsr_table.pdf Maximal Length LFSR table] 長さ 1 から 786 までと、1024 と 2048 と 4096。
* [http://www.maxim-ic.com/appnotes.cfm?appnote_number=1743&CMP=WP-9 Pseudo-Random Number Generation Routine]
* [http://www.ee.ualberta.ca/~elliott/ee552/studentAppNotes/1999f/Drivers_Ed/lfsr.html Linear Feedback Shift Register]
* [http://www.quadibloc.com/crypto/co040801.htm Shift-Register Stream Ciphers]
* [http://www.yikes.com/~ptolemy/lfsr_web/index.htm Simple explanation of LFSRs for Engineers]
* [http://www.ece.cmu.edu/~koopman/lfsr/index.html Feedback terms]
* [https://web.archive.org/web/20010605005727/homepage.mac.com/afj/lfsr.html General LFSR Theory]
* [https://web.archive.org/web/20010620003044/homepage.mac.com/afj/taplist.html Table of Maximal Tap Sequences]
* [http://www-rocq.inria.fr/codes/LFSR/index.html Shift register code generator]

{{DEFAULTSORT:せんけいきかんしふとれしすた}}
[[Category:デジタル回路]]
[[Category:乱数]]
[[Category:暗号アルゴリズム]]
[[Category:数学に関する記事]]