線形フィードバックシフトレジスタ

コンピューターにおいて、線形フィードバック シフト レジスタ( LFSR ) は、入力ビットが前の状態の 線形関数であるシフト レジスタです。

単一ビットの線形関数として最も一般的に使用されるのは排他的論理和（XOR）です。したがって、LFSRは、入力ビットがシフトレジスタ全体の値の一部のビットのXORによって駆動されるシフトレジスタであることがほとんどです。

LFSRの初期値はシードと呼ばれ、レジスタの動作は決定論的であるため、レジスタによって生成される値のストリームは、現在の（または以前の）状態によって完全に決定されます。同様に、レジスタの取り得る状態は有限であるため、最終的には繰り返しサイクルに入る必要があります。しかし、適切に選択されたフィードバック関数を持つLFSRは、ランダムに見えるビットシーケンスを生成し、非常に長いサイクルを持つことがあります。

LFSRの応用としては、疑似乱数、疑似ノイズシーケンス、高速デジタルカウンタ、ホワイトニングシーケンスの生成などが挙げられます。LFSRはハードウェアとソフトウェアの両方で実装されており、広く利用されています。

伝送エラーの迅速なチェックに使用される巡回冗長検査（CRC）の数学は、LFSRの数学と密接に関連しています。[ 1 ]一般的に、LFSRの背後にある算術は、研究および実装の対象として非常に洗練されています。単純な構成要素を用いて、比較的複雑なロジックを構築することも可能です。しかし、LFSRほど洗練されていないものの、より優れた性能を発揮する他の手法も検討する必要があります。

フィボナッチLFSR

16ビットのフィボナッチLFSR。示されているフィードバックタップ番号は表の原始多項式に対応しており、レジスタは全ゼロ状態を除く最大65535の状態を循環します。示されている状態、0xACE1（16進数）の後に0x5670が続きます。
フィボナッチ 31 ビット線形フィードバック シフト レジスタ。位置 28 と 31 (黄色の LED で表示) にタップがあり、この速度での最大サイクルと周期は約 8 年になります。

次の状態に影響を与えるビット位置はタップと呼ばれます。図ではタップは[16,14,13,11]です。LFSRの右端のビットは出力ビットと呼ばれ、常にタップでもあります。次の状態を取得するには、タップビットのXOR演算を順に行います。次に、すべてのビットを1つ右にシフトし、右端のビットを破棄します。そして、タップビットのXOR演算結果を、空になった左端のビットにフィードバックします。擬似乱数出力ストリームを取得するには、各状態遷移の後に右端のビットを読み取ります。

  • 最大長 LFSR は、 m シーケンスを生成します (つまり、すべてのビットがゼロである状態を除いて、シフト レジスタ内のすべての可能な 2 m − 1 状態を循環します )。ただし、すべてのビットがゼロである場合には、シーケンスは変化しません。
  • LFSR の XOR ベースのフィードバックの代わりに、XNOR を使用することもできます。[ 2 ]この関数はアフィン マップであり、厳密には線形マップではありませんが、LFSR の状態の補数となる等価な多項式カウンターになります。XNOR フィードバックを使用する場合、すべて 1 の状態は不正であり、これは XOR を使用する場合にすべて 0 の状態が不正であるのと同じです。この状態ではカウンターが「ロックアップ」したままになるため、この状態は不正であると判断されます。この方法は、ゼロ状態から始まるフリップフロップを使用するハードウェア LFSR では有利です。ロックアップ状態から開始しないため、動作を開始するためにレジスタにシードを設定する必要がないからです。

LFSR またはその XNOR 対応物によって生成される数値のシーケンスは、グレイ コードや自然 2 進コード と同様に有効な2 進数値システムと見なすことができます。

LFSRにおけるフィードバックタップの配置は、有限体演算において2を法とする多項式 として表すことができます。これは、多項式の係数が1または0でなければならないことを意味します。これはフィードバック多項式または逆特性多項式と呼ばれます。例えば、タップが16、14、13、11ビット目（図参照）にある場合、フィードバック多項式は次のようになります。

×16+×14+×13+×11+1.{\displaystyle x^{16}+x^{14}+x^{13}+x^{11}+1.}

多項式中の「1」はタップではなく、最初のビットへの入力（つまりx 0、つまり1に相当）に対応します。項のべき乗は、左から数えてタップされたビットを表します。最初のビットと最後のビットは、常にそれぞれ入力タップと出力タップとして接続されます。

LFSRが最大長であるためには、対応するフィードバック多項式がガロア体GF(2)上で原始的である必要があります。 [ 3 ] [ 4 ]これは、以下の条件が必要であることを意味します（ただし十分ではありません）。

  • タップの数は偶数です。
  • タップの集合は互いに素です。つまり、すべてのタップに共通する 1 以外の約数は存在しません。

最大長 LFSR を構築できる原始多項式の表は、以下および参考文献に記載されています。

与えられたLFSR長に対して、最大長タップシーケンスは複数存在する可能性があります。また、最大長タップシーケンスが1つ見つかると、自動的に別のタップシーケンスが続きます。nビットLFSRのタップシーケンスが[ n , A , B , C , 0]（0はx 0  = 1 の項に対応）である場合、対応する「ミラー」シーケンスは[ n , n − C , n − B , n − A , 0]です。したがって、タップシーケンス[32, 22, 2, 1, 0] には、対応する[32, 31, 30, 10, 0]があります。どちらも最大長タップシーケンスとなります。

Cの例を以下に示します。 

#include <stdint.h> unsigned lfsr_fib ( void ) { uint16_t start_state = 0xACE1u ; /* ゼロ以外の開始状態であればどれでも動作します。 */ uint16_t lfsr = start_state ; uint16_t bit ; /* コードの後半で bit<<15 を可能にするには 16 ビットである必要があります */ unsigned period = 0 ;do { /* タップ: 16 14 13 11; フィードバック多項式: x^16 + x^14 + x^13 + x^11 + 1 */ bit = (( lfsr >> 0 ) ^ ( lfsr >> 2 ) ^ ( lfsr >> 3 ) ^ ( lfsr >> 5 )) & 1u ; lfsr = ( lfsr >> 1 ) | ( bit << 15 ); ++期間; } while ( lfsr != start_state );返品期間; }

高速パリティまたはポップカウント操作が利用可能な場合、フィードバック ビットは、特性多項式を持つレジスタの ドット積としてより効率的に計算できます。

  • bit=parity(lfsr&0x002Du);、または同等
  • bit=popcnt(lfsr&0x002Du)/* & 1u */;（& 1upopcnt は真のパリティ関数になりますが、後のビットシフトによりbit << 15上位ビットは無関係になります。）

回転操作が利用可能な場合、新しい状態は次のように計算できる。

  • lfsr=rotateright((lfsr&~1u)|(bit&1u),1);、または同等
  • lfsr=rotateright(((bit^lfsr)&1u)^lfsr,1);

このLFSR構成は、標準、多対一、または外部XORゲートとも呼ばれます。代替のガロア構成については、次のセクションで説明します。

Pythonの例

同様の（[16,15,13,​​4]の16ビットタップ）フィボナッチLFSRのサンプルPython実装は次のようになります。 

start_state = 1 << 15 | 1 lfsr = start_state period = 0True の場合:タップ数: 16 15 13 4; フィードバック多項式: x^16 + x^15 + x^13 + x^4 + 1 bit = ( lfsr ^ ( lfsr >> 1 ) ^ ( lfsr >> 3 ) ^ ( lfsr >> 12 )) & 1 lfsr = ( lfsr >> 1 ) | ( bit << 15 ) period += 1 if lfsr == start_state : print ( period ) break

16 ビットのレジスタが使用され、4 番目、13 番目、15 番目、および 16 番目のビットの XOR タップによって最大シーケンス長が確立されます。

ガロアLFSR

16ビットのガロアLFSR。上記のレジスタ番号はフィボナッチの例と同じ原始多項式に対応していますが、シフト方向とは逆にカウントされます。このレジスタも、すべてゼロの状態を除いて、最大65535の状態を循環します。示されている状態ACE1（16進数）の次にはE270（16進数）が続きます。

フランスの数学者エヴァリスト・ガロアにちなんで名付けられたガロア構成の LFSR は、モジュラー LFSR、内部 XOR LFSR 、または1 対多 LFSRとも呼ばれ、従来の LFSR と同じ出力ストリームを生成できる (ただし時間的にオフセットがある) 代替構造です。[ 5 ]ガロア構成では、システムがクロックされると、タップでないビットは変更されずに 1 つ右にシフトされます。一方、タップは、次の位置に格納される前に出力ビットと XOR されます。新しい出力ビットは次の入力ビットになります。この効果として、出力ビットが 0 の場合、レジスタ内のすべてのビットが変更されずに右にシフトし、入力ビットが 0 になります。出力ビットが 1 の場合、タップ位置のビットがすべて反転し (0 の場合は 1 になり、1 の場合は 0 になります)、次にレジスタ全体が右にシフトされ、入力ビットが 1 になります。

同じ出力ストリームを生成するには、タップの順序が従来のLFSRの順序と対応している必要があります（上記参照）。そうでない場合、ストリームは逆になります。LFSRの内部状態は必ずしも同じではないことに注意してください。図示されているガロアレジスタは、最初のセクションのフィボナッチレジスタと同じ出力ストリームを持ちます。ストリーム間には時間オフセットが存在するため、各サイクルで同じ出力を得るには異なる開始点が必要になります。

  • ガロア LFSR は、新しい入力を生成するためにすべてのタップを連結しません (XOR は LFSR 内で実行され、XOR ゲートはシリアルで実行されないため、伝播時間はチェーン全体ではなく 1 つの XOR に短縮されます)。そのため、各タップを並列に計算することができ、実行速度が向上します。
  • LFSR のソフトウェア実装では、XOR 演算を 1 ワードずつ実装できるため、ガロア形式の方が効率的です。つまり、出力ビットのみを個別に検査する必要があります。

以下は、図の 16 ビット最大周期ガロア LFSR の例の Cコード例です。

#include <stdint.h> unsigned lfsr_galois ( void ) { uint16_t start_state = 0xACE1u ; /* ゼロ以外の開始状態であればどれでも動作します。 */ uint16_t lfsr = start_state ; unsigned period = 0 ;do { #ifndef LEFT unsigned lsb = lfsr & 1u ; /* LSB（つまり、出力ビット）を取得します。 */ lfsr >>= 1 ; /* シフトレジスタ */ if ( lsb ) /* 出力ビットが 1 の場合、 */ lfsr ^= 0xB400u ; /* トグルマスクを適用します。 */ #else unsigned msb = ( int16_t ) lfsr < 0 ; /* MSB（つまり、出力ビット）を取得します。 */ lfsr <<= 1 ; /* シフトレジスタ */ if ( msb ) /* 出力ビットが 1 の場合、 */ lfsr ^= 0x002Du ; /* トグルマスクを適用します。 */ #endif ++ period ; } while ( lfsr != start_state );返品期間; }

この分岐はと書くこともできます。一部のコンパイラでは、より効率的なコードが生成される場合があります。さらに、左シフトの変種では、MSBが自身への加算による繰り上がりとなるため、さらに優れたコードが生成される場合があります。 if(lsb)lfsr^=0xB400u;lfsr^=(-lsb)&0xB400u;lfsr

ガロア LFSR 並列計算

状態と結果のビットを組み合わせて並列計算することもできます。次の関数は、63ビットの多項式を用いて次の64ビットを計算します。 x63+x62+1{\displaystyle x^{63}+x^{62}+1}

#include <stdint.h>uint64_t prsg63 ( uint64_t lfsr ) { lfsr = lfsr << 32 | ( lfsr << 1 ^ lfsr << 2 ) >> 32 ; lfsr = lfsr << 32 | ( lfsr << 1 ^ lfsr << 2 ) >> 32 ; lfsrを返します; }

非バイナリガロアLFSR

上記のような 2 進ガロア LFSR は、任意のq元アルファベット {0, 1, ..., q  − 1} に一般化できます (たとえば、2 進の場合、q = 2 で、アルファベットは単に {0, 1} です)。この場合、排他的論理和コンポーネントは、- qを法とする加算に一般化され(XOR は 2 を法とする加算であることに注意してください)、フィードバック ビット (出力ビット) は、特定のタップ ポイントごとに定数であるq元値で ( qを法として)乗算されます。これは、フィードバックに 0 (フィードバックなし、つまりタップなし) または 1 (フィードバックあり) が乗算される 2 進の場合の一般化でもあることに注意してください。適切なタップ構成があれば、このような LFSR を使用して、qの任意の素数値のガロア体を生成することができます。

Xorshift LFSR

George Marsaglia [ 6 ]によって示され、Richard P. Brent [ 7 ] によってさらに分析されたように、線形フィードバックシフトレジスタはXOR演算とシフト演算を用いて実装できます。このアプローチは、これらの演算が一般的に最新のプロセッサ命令に効率的にマッピングされるため、ソフトウェアによる高速実行に適しています。

以下はジョン・メトカーフの7,9,13トリプレットを使用した16ビット最大周期Xorshift LFSRのCコード例である: [ 8 ]

#include <stdint.h> unsigned lfsr_xorshift ( void ) { uint16_t start_state = 0xACE1u ; /* ゼロ以外の開始状態であればどれでも動作します。 */ uint16_t lfsr = start_state ; unsigned period = 0 ;do { // http://www.retroprogramming.com/2017/07/xorshift-pseudorandom-numbers-in-z80.html からの 7,9,13 トリプレット lfsr ^= lfsr >> 7 ; lfsr ^= lfsr << 9 ; lfsr ^= lfsr >> 13 ; ++ピリオド; } while ( lfsr != start_state );返品期間; }

マトリックス形式

フィボナッチ構成とガロア構成の両方の2値LFSRは、行列を用いた線形関数として表現できる（GF(2)を参照）。[ 9 ] LFSRの特性多項式のコンパニオン行列を用い、シードを列ベクトルとして表すと、ステップ後のフィボナッチ構成のレジスタの状態は次のように表される。 F2{\displaystyle \mathbb {F} _{2}}(a0,a1,…,an−1)T{\displaystyle (a_{0},a_{1},\dots ,a_{n-1})^{\mathrm {T} }}k{\displaystyle k}

(akak+1ak+2⋮ak+n−1)=(010⋯0001⋱⋮⋮⋮⋱⋱000⋯01c0c1⋯⋯cn−1)(ak−1akak+1⋮ak+n−2)=(010⋯0001⋱⋮⋮⋮⋱⋱000⋯01c0c1⋯⋯cn−1)k(a0a1a2⋮an−1){\displaystyle {\begin{pmatrix}a_{k}\\a_{k+1}\\a_{k+2}\\\vdots \\a_{k+n-1}\end{pmatrix}}={\begin{pmatrix}0&1&0&\cdots &0\\0&0&1&\ddots &\vdots \\\vdots &\vdots &\ddots &\ddots &0\\0&0&\cdots &0&1\\c_{0}&c_{1}&\cdots &\cdots &c_{n-1}\end{pmatrix}}{\begin{pmatrix}a_{k-1}\\a_{k}\\a_{k+1}\\\vdots \\a_{k+n-2}\end{pmatrix}}={\begin{pmatrix}0&1&0&\cdots &0\\0&0&1&\ddots &\vdots \\\vdots &\vdots &\ddots &\ddots &0\\0&0&\cdots &0&1\\c_{0}&c_{1}&\cdots &\cdots &c_{n-1}\end{pmatrix}}^{k}{\begin{pmatrix}a_{0}\\a_{1}\\a_{2}\\\vdots \\a_{n-1}\end{pmatrix}}}

対応するガロア形式の行列は次の通りである。

(cn−110⋯0cn−201⋱⋮⋮⋮⋱⋱0c10⋯01c00⋯⋯0){\displaystyle {\begin{pmatrix}c_{n-1}&1&0&\cdots &0\\c_{n-2}&0&1&\ddots &\vdots \\\vdots &\vdots &\ddots &\ddots &0\\c_{1}&0&\cdots &0&1\\c_{0}&0&\cdots &\cdots &0\end{pmatrix}}}

適切な初期化を行うには、

ai′=∑j=0iai−jci, 0≤i<n{\displaystyle a'_{i}=\sum _{j=0}^{i}a_{i-j}c_{i},\ 0\leq i<n}

列ベクトルの上の係数:

(cn−110⋯0cn−201⋱⋮⋮⋮⋱⋱0c10⋯01c00⋯⋯0)k(a0′a1′a2′⋮an−1′){\displaystyle {\begin{pmatrix}c_{n-1}&1&0&\cdots &0\\c_{n-2}&0&1&\ddots &\vdots \\\vdots &\vdots &\ddots &\ddots &0\\c_{1}&0&\cdots &0&1\\c_{0}&0&\cdots &\cdots &0\end{pmatrix}}^{k}{\begin{pmatrix}a'_{0}\\a'_{1}\\a'_{2}\\\vdots \\a'_{n-1}\end{pmatrix}}}

元のシーケンスの 項a kを与えます。

これらの形式は任意の分野に自然に一般化されます。

最大LFSRの多項式の例

次の表は、シフトレジスタの長さが最大24の場合の最大長フィードバック多項式（原始多項式）の例を示しています。最大長LFSRの形式は、ソロモン・W・ゴロムが1967年の著書で開発しました。[ 10 ]異なる原始多項式の数はシフトレジスタの長さとともに指数的に増加し、オイラーのトーシェント関数[ 11 ]（OEISのシーケンスA011260 ）を使用して正確に計算できます。

ビット (n) フィードバック多項式 タップ タップ（六角） 期間 （） 2n−1{\displaystyle 2^{n}-1}
2 x2+x+1{\displaystyle x^{2}+x+1}11 0x3 3
3 x3+x2+1{\displaystyle x^{3}+x^{2}+1}110 0x6 7
4 x4+x3+1{\displaystyle x^{4}+x^{3}+1}1100 0xC 15
5 x5+x3+1{\displaystyle x^{5}+x^{3}+1}10100 0x14 31
6 x6+x5+1{\displaystyle x^{6}+x^{5}+1}110000 0x30 63
7 x7+x6+1{\displaystyle x^{7}+x^{6}+1}110万 0x60 127
8 x8+x6+x5+x4+1{\displaystyle x^{8}+x^{6}+x^{5}+x^{4}+1}10111000 0xB8 255
9 x9+x5+1{\displaystyle x^{9}+x^{5}+1}100010000 0x110 511
10 x10+x7+1{\displaystyle x^{10}+x^{7}+1}1001000000 0x240 1,023
11 x11+x9+1{\displaystyle x^{11}+x^{9}+1}10100000000 0x500 2,047
12 x12+x11+x10+x4+1{\displaystyle x^{12}+x^{11}+x^{10}+x^{4}+1}111000001000 0xE08 4,095
13 x13+x12+x11+x8+1{\displaystyle x^{13}+x^{12}+x^{11}+x^{8}+1}1110010000000 0x1C80 8,191
14 x14+x13+x12+x2+1{\displaystyle x^{14}+x^{13}+x^{12}+x^{2}+1}11100000000010 0x3802 16,383
15 x15+x14+1{\displaystyle x^{15}+x^{14}+1}110000000000000 0x6000 32,767
16 x16+x15+x13+x4+1{\displaystyle x^{16}+x^{15}+x^{13}+x^{4}+1}1101000000001000 0xD008 65,535
17 x17+x14+1{\displaystyle x^{17}+x^{14}+1}10010000000000000 0x12000 131,071
18 x18+x11+1{\displaystyle x^{18}+x^{11}+1}100000010000000000 0x20400 262,143
19 x19+x18+x17+x14+1{\displaystyle x^{19}+x^{18}+x^{17}+x^{14}+1}1110010000000000000 0x72000 524,287
20 x20+x17+1{\displaystyle x^{20}+x^{17}+1}10010000000000000000 0x90000 1,048,575
21 x21+x19+1{\displaystyle x^{21}+x^{19}+1}101000000000000000000 0x140000 2,097,151
22 x22+x21+1{\displaystyle x^{22}+x^{21}+1}1100000000000000000000 0x300000 4,194,303
23 x23+x18+1{\displaystyle x^{23}+x^{18}+1}10000100000000000000000 0x420000 8,388,607
24 x24+x23+x22+x17+1{\displaystyle x^{24}+x^{23}+x^{22}+x^{17}+1}111000010000000000000000 0xE10000 16,777,215

出力ストリームのプロパティ

  • 1と0は「連」として出現します。例えば、出力ストリーム1110010は、長さが3、2、1、1の4つの連から構成されます。最大LFSRの1周期には、2 n −1個の連が発生します（上記の例では、3ビットのLFSRには4個の連があります）。これらの連のちょうど半分は1ビット長、4分の1は2ビット長で、最大でn − 1ビット長の0の連が1個、 nビット長 の1の連が1個あります。この分布は、真にランダムなシーケンスの統計的期待値とほぼ等しくなります。しかし、真にランダムなシーケンスのサンプルでこの分布と全く同じ分布が見つかる確率はかなり低いです。
  • LFSRの出力ストリームは決定論的です。現在の状態とLFSR内のXORゲートの位置が分かれば、次の状態を予測できます。[ 12 ]これは、真にランダムなイベントでは不可能です。最大長のLFSRでは、長さごとにLFSRの数が容易に制限されるため、次の状態を計算するのがはるかに容易です。
  • 出力ストリームは可逆的です。ミラーリングされたタップを持つ LFSR は、出力シーケンスを逆の順序で循環します。
  • すべてゼロで構成される値は出現しません。したがって、長さnの LFSRを使用して 2 n 個の値すべてを生成することはできません。

アプリケーション

LFSRはハードウェアで実装できるため、直接拡散スペクトル無線など、疑似乱数シーケンスを非常に高速に生成する必要があるアプリケーションで役立ちます。LFSRは、さまざまなプログラマブルサウンドジェネレータでホワイトノイズの近似値を生成するためにも使用されています。

カウンターとして使う

LFSRの状態の繰り返しシーケンスは、クロック分周器として使用したり、非バイナリシーケンスが許容される場合のカウンタとして使用したりできます。これは、コンピュータのインデックスやフレーミング位置を機械可読にする必要がある場合によく見られます。[ 12 ] LFSRカウンタは、自然バイナリカウンタやグレイコードカウンタよりもフィードバックロジックが単純なため、より高いクロックレートで動作できます。ただし、LFSRがロックアップ状態（XORベースのLFSRの場合はすべて0、XNORベースのLFSRの場合はすべて1）にならないようにする必要があります。たとえば、起動時にシーケンス内の他の状態にプリセットします。LFSRでカウントアップとカウントダウンが可能です。LFSRはCPUのプログラムカウンタとしても使用されていますが、これにはプログラム自体を「スクランブル」する必要があり、ゲートが貴重な場合にゲートを節約するため（加算器よりも少ないゲートを使用）と速度向上のため（LFSRは長いキャリーチェーンを必要としないため）に行われます。

原始多項式の表は、LFSRをフィボナッチ形式またはガロア形式で配置することで最大周期が得られることを示しています。より長い周期を持つLFSRに、いくつかの状態をスキップしてシーケンスを短縮するロジックを追加することで、任意の周期を得ることができます。

暗号技術における用途

LFSR は、単純な電気機械回路や電子回路から簡単に構築できること、周期が長いこと、出力ストリームが非常に均一に分散していることから、ストリーム暗号用の疑似乱数生成器として長い間使用されてきました。しかし、LFSR は線形システムであるため、暗号解読がかなり容易です。たとえば、既知の平文とそれに対応する暗号文があれば、攻撃者は前述のシステムで使用されている LFSR 出力ストリームの一部を傍受して復元し、その出力ストリームの一部からBerlekamp-Massey アルゴリズムを使用して、意図した受信者をシミュレートする最小サイズの LFSR を構築できます。この LFSR に傍受した出力ストリームの一部を入力すると、残りの平文が復元されます。

LFSR ベースのストリーム暗号では、この問題を軽減するために 3 つの一般的な方法が採用されています。

重要なLFSRベースのストリーム暗号には、 GSM携帯電話で使用されるA5/1とA5/2 、 Bluetoothで使用されるE0、そして縮小生成器などがある。A5/2暗号は既に解読されており、A5/1とE0には深刻な脆弱性がある。[ 14 ] [ 15 ]

線形フィードバックシフトレジスタは線形合同型ジェネレータと密接な関係がある。[ 16 ]

回路テストでの使用

LFSR は、テストパターン生成 (徹底的なテスト、疑似ランダム テスト、または疑似徹底的なテスト) およびシグネチャ分析のための回路テストで使用されます。

テストパターン生成

完全LFSRは、 n入力回路のあらゆる入力を網羅するため、網羅的テストのためのパターン生成器として広く用いられます。最大長LFSRと重み付きLFSRは、疑似ランダムテストアプリケーションにおける疑似ランダムテストパターン生成器として広く用いられています。

シグネチャ分析

組み込み自己テスト（BIST）技術では、すべての回路出力をチップ上に保存することはできませんが、回路出力を圧縮してシグネチャを形成し、後に（正常な回路の）ゴールデンシグネチャと比較することで故障を検出することができます。この圧縮にはロスがあるため、故障出力もゴールデンシグネチャと同じシグネチャを生成し、故障を検出できない可能性が常に存在します。この状態はエラーマスキングまたはエイリアシングと呼ばれます。BISTは、LFSRの一種であるマルチ入力シグネチャレジスタ（MISRまたはMSR）によって実現されます。標準的なLFSRは、1つのXORゲートまたはXNORゲートを備えており、ゲートの入力は複数の「タップ」に接続され、出力は最初のフリップフロップの入力に接続されます。MISRも同じ構造ですが、すべてのフリップフロップへの入力はXOR/XNORゲートを介して供給されます。例えば、4ビットMISRは、4ビットの並列出力と4ビットの並列入力を備えています。最初のフリップフロップの入力は、並列入力ビット0と「タップ」とのXOR/XNOR演算です。他のすべてのフリップフロップの入力は、前のフリップフロップの出力と対応する並列入力ビットとのXOR/XNOR演算です。したがって、MISRの次の状態は、現在の状態だけでなく、最後のいくつかの状態に依存します。したがって、入力シーケンスが毎回同じであれば、MISRは常に同じゴールデンシグネチャを生成します。最近のアプリケーション[ 17 ]では、LFSRの「タップ」としてセットリセットフリップフロップが提案されています。セットリセットフリップフロップは初期シードを保存してLFSRからビットストリーム全体を生成することができるため、BISTシステムのストレージを最適化できます。ただし、これはBISTのアーキテクチャの変更を必要とするため、特定のアプリケーションではオプションとなります。

デジタル放送および通信における用途

スクランブリング

短い繰り返しシーケンス (0 または 1 の連続など) がスペクトル線を形成して、受信機でのシンボル追跡を複雑にしたり、他の送信に干渉したりするのを防ぐため、データ ビット シーケンスは、変調および送信の前に線形フィードバック レジスタの出力と結合されます。このスクランブリングは、復調後に受信機で除去されます。LFSR が送信されたシンボル ストリームと同じビット レートで動作する場合、この手法はスクランブリングと呼ばれます。LFSRがシンボル ストリームよりも大幅に高速で動作する場合、LFSR によって生成されたビット シーケンスは チッピング コード と呼ばれます。チッピング コードは、バイナリ位相シフト キーイングまたは同様の変調方式を使用して送信する前に、排他的論理和を使用してデータと結合されます。結果として得られる信号の帯域幅はデータよりも高いため、これは拡散スペクトル通信の方式です。拡散スペクトルの特性のためだけに使われる場合、この手法は直接拡散スペクトルと呼ばれます。

どちらの方式も暗号化や暗号解読と混同すべきではありません。LFSRによるスクランブルと拡散は、盗聴から情報を保護するものではありません。LFSRは、堅牢かつ効率的な変調と復調を可能にする便利なエンジニアリング特性を備えた、同等のストリームを生成するために使用されます。

線形フィードバックレジスタを使用するデジタル放送システム:

  • ATSC規格（北米デジタルテレビ伝送システム）
  • DAB（デジタルオーディオ放送システム - ラジオ用）
  • DVB-T（デジタルテレビ伝送システム - ヨーロッパ、オーストラリア、アジアの一部）
  • NICAM（テレビ用デジタルオーディオシステム）

LFSR を使用するその他のデジタル通信システム:

その他の用途

LFSR は、疑似ランダム ノイズを生成して対象の通信システムのノイズ フロアを上げるために、 無線妨害システムでも使用されます。

ドイツの時刻信号DCF77は、振幅変調に加えて、9段LFSR駆動の位相偏移変調を採用しており、受信時刻の精度とノイズが存在する状況でもデータストリームの堅牢性を高めています。 [ 19 ]

参照

参考文献

  1. ^ Geremia, Patrick. 「巡回冗長検査計算：TMS320C54xを使用した実装」（PDF） . Texas Instruments. p. 6. 2016年10月16日閲覧。
  2. ^ Virtexデバイスの線形フィードバックシフトレジスタ
  3. ^ジェントル、ジェームス E. (2003)。乱数生成とモンテカルロ法(第 2 版)。ニューヨーク：スプリンガー。 p. 38.ISBN​ 0-387-00178-6. OCLC  51534945 .
  4. ^ Tausworthe, Robert C. (1965年4月). 「2を法とする線形回帰法による乱数生成」(PDF) .計算数学. 19 (90): 201– 209. doi : 10.1090/S0025-5718-1965-0184406-1 . S2CID 120804149 . 
  5. ^ウィリアム・プレス、ソール・テウコルスキー、ウィリアム・ヴェタリング、ブライアン・フラナリー (2007). 『数値計算のレシピ：科学計算の芸術』第3版.ケンブリッジ大学出版局. p. 386. ISBN 978-0-521-88407-5。
  6. ^ Marsaglia, George (2003年7月). 「Xorshift RNGs」 . Journal of Statistical Software . 8 (14). doi : 10.18637/jss.v008.i14 .
  7. ^ Brent, Richard P. (2004年8月). 「MarsagliaのXorshift乱数生成器に関する注記」 . Journal of Statistical Software . 11 (5). doi : 10.18637/jss.v011.i05 . hdl : 1885/34049 .
  8. ^ Metcalf, John (2017年7月22日). 「Z80アセンブリ言語における16ビットXORシフト擬似乱数」 Retro Programming . 2022年1月5日閲覧。
  9. ^ Klein, A. (2013). 「線形フィードバックシフトレジスタ」.ストリーム暗号. ロンドン: Springer. pp.  17– 18. doi : 10.1007/978-1-4471-5079-4_2 . ISBN 978-1-4471-5079-4。
  10. ^ゴロム、ソロモン W. (1967).シフトレジスタシーケンス. ラグナヒルズ、カリフォルニア州: エーゲアンパークプレス. ISBN 978-0894120480。
  11. ^ Weisstein, Eric W. 「原始多項式」 . mathworld.wolfram.com . 2021年4月27日閲覧。
  12. ^ a b Alfke, Peter (1996年7月7日). 「効率的なシフトレジスタ、LFSRカウンター、および長周期疑似ランダムシーケンスジェネレータ」(PDF) . Xilinxアプリケーションノート、XAPP 052. AMD技術情報ポータル.
  13. ^ A. Poorghanad, A. Sadr, A. Kashanipour「進化的手法を用いた高品質疑似乱数の生成」IEEE計算知能とセキュリティ会議、第9巻、pp. 331-335、2008年5月[1]
  14. ^ Barkam, Elad; Biham, Eli; Keller, Nathan (2008)、「Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication」（PDF）、Journal of Cryptology、21（3）：392– 429、doi：10.1007/s00145-007-9001-y、S2CID 459117 、 2020年1月25日にオリジナル（PDF）からアーカイブ、 2019年9月15日取得 
  15. ^ Lu, Yi; Willi Meier; Serge Vaudenay (2005). 「条件付き相関攻撃：Bluetooth暗号化に対する実践的な攻撃」. Advances in Cryptology – CRYPTO 2005. Lecture Notes in Computer Science. Vol. 3621. サンタバーバラ, カリフォルニア州, 米国. pp.  97– 117. CiteSeerX 10.1.1.323.9416 . doi : 10.1007/11535218_7 . ISBN  978-3-540-28114-6。{{cite book}}: CS1 maint: location missing publisher (link)
  16. ^ RFC 4086 セクション 6.1.3「従来の疑似ランダムシーケンス」
  17. ^ Martínez LH, Khursheed S, Reddy SM. 高いテストカバレッジと低いハードウェアオーバーヘッドを実現するLFSR生成. IET Computers & Digital Techniques. 2019年8月21日. UoLリポジトリ
  18. ^ SATA仕様書第9.5章、改訂2.6
  19. ^ Hetzel, P. (1988年3月16日).搬送波の疑似ランダム位相シフトキーイングを用いたLF送信機DCF77による時刻配信(PDF) . 第2回欧州周波数・時間フォーラム. ヌーシャテル. pp.  351– 364. 2011年10月11日閲覧.

さらに読む

「 https://en.wikipedia.org/w/index.php?title=Linear-feedback_shift_register&oldid=1334110977」より取得