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

https://stackoverflow.com/questions/3735217

03-10-2019
|

質問

最近、私はLFSRの概念に繰り返しぶつかりました。それは、異なる分野とのリンクとそれ自体が魅力的であるため、非常に興味深いと思います。理解するためにいくらかの努力が必要でした、最後の助けはこれが本当に良いことでしたページ, 、（最初は）謎めいたよりもはるかに優れていますウィキペディアエントリ. 。そこで、LFSRのように機能するプログラムの小さなコードを書きたかったのです。より正確に言うと、それはどういうわけかLFSRがどのように機能するかを示しました。これが、いくつかのレンガティアの試み（Python）の後に思いつくことができる最もきれいなものです。

def lfsr(seed, taps):
    sr, xor = seed, 0
    while 1:
        for t in taps:
            xor += int(sr[t-1])
        if xor%2 == 0.0:
            xor = 0
        else:
            xor = 1
        print xor
        sr, xor = str(xor) + sr[:-1], 0
        print sr
        if sr == seed:
            break

lfsr('11001001', (8,7,6,1))      #example

XOR関数の出力を「XOR」と名付けましたが、あまり正しくありません。ただし、これは、可能性のある状態をどのように囲んでいるかを示すことを目的としています。実際、レジスタが文字列で表されていることに気付きました。それほど論理的な一貫性はありません。

これはあなたが何時間も見ることができる素敵なおもちゃに簡単に変えることができます（少なくとも私はできます:-)

def lfsr(seed, taps):
    import time
    sr, xor = seed, 0
    while 1:
        for t in taps:
            xor += int(sr[t-1])
        if xor%2 == 0.0:
            xor = 0
        else:
            xor = 1
        print xor
        print
        time.sleep(0.75)
        sr, xor = str(xor) + sr[:-1], 0
        print sr
        print
        time.sleep(0.75)

それから、それは私を襲った、これは書面でどのような用途ですか？乱数を生成できると聞きました。それは本当ですか？どうやって？だから、誰かができればいいでしょう：

ソフトウェア開発でそのようなデバイスの使用方法を説明する
いくつかのコードを考え出し、上記のポイントをサポートするか、私のように、あらゆる言語でそれを行うためのさまざまな方法を示すために

また、このロジックとデジタル回路についてはあまり教訓的なものではないので、これを（私のような）ヌービーがこれをよりよく理解する場所になるのはいいことですもの, 、またはそれが何であり、ソフトウェアを作成するときにどのように役立つかを理解するために。コミュニティウィキにする必要がありましたか？

とはいえ、誰かがゴルフのように感じたら...どういたしまして。

解決

実際、LFSRに基づくアルゴリズムは非常に一般的です。 CRCは実際にはLFSRに直接基づいています。もちろん、コンピューターサイエンスのクラスでは、人々は、入力値が蓄積された値でどのようにXoredであるかについて話しているときに多項式について話します。それらは同じ異なる用語です。

CRC32は非常に一般的なものです。イーサネットフレームのエラーを検出するために使用されます。つまり、この回答を投稿したとき、私のPCはLFSRベースのアルゴリズムを使用してIPパケットのハッシュを生成し、ルーターが送信されているものが破損していないことを確認できるようにします。

zipファイルとgzipファイルも別の例です。どちらもエラー検出にCRCを使用します。 ZIPはCRC32を使用し、GZIPはCRC16とCRC32の両方を使用します。

CRCは基本的にハッシュ関数です。そして、それはインターネットを機能させるのに十分です。つまり、LFSRはかなり良いハッシュ関数です。あなたがこれを知っているかどうかはわかりませんが、一般的に良いハッシュ関数は良好な乱数ジェネレーターと見なされます。しかし、LFSRを使用しているのは、正しいタップ（多項式）を選択することは、ハッシュ/乱数の品質にとって非常に重要であることです。

コードは一般的に、Zerosの文字列で動作するため、玩具コードです。現実の世界では、LFSRはバイトのビットで動作します。 LFSRを押してプッシュする各バイトは、レジスタの蓄積された値を変更します。その値は、事実上、レジスタを押してプッシュするすべてのバイトのチェックサムです。その値を乱数として使用する2つの一般的な方法は、カウンターを使用してレジスタを介して一連の数値をプッシュし、それによって線形シーケンス1,2,3,4を15306,22,5587のようなハッシュされたシーケンスに変換することです。 994、または現在の値をレジスタにフィードバックして、一見ランダムなシーケンスで新しい数値を生成します。

一度にビットを処理する必要があるため、ビットフィッドリングLFSRを使用してこれを素朴に使用することは非常に遅いことに注意する必要があります。したがって、人々は、事前に計算されたテーブルを使用して、一度に8ビットまたは32ビットずつさえ行う方法を考え出しました。これが、WildでLFSRコードをほとんど見ない理由です。ほとんどの生産コードでは、他の何かを装っています。

しかし、時には、平凡なLFSRが役立つことがあります。私はかつて書いた modbus PIC MicroとそのプロトコルのドライバーはCRC16を使用しました。事前に計算されたテーブルには256バイトのメモリが必要で、私のCPUには68バイトしかありませんでした（冗談じゃないよ）。だから私はLFSRを使用する必要がありました。

他のヒント

私はPythonでLFSR-Implementationを探していたので、このトピックに出くわしました。しかし、私のニーズに応じて、以下はもう少し正確であることがわかりました。

def lfsr(seed, mask):
    result = seed
    nbits = mask.bit_length()-1
    while True:
        result = (result << 1)
        xor = result >> nbits
        if xor != 0:
            result ^= mask

        yield xor, result

上記のLFSR-GeneratorはGFに基づいています（2^k）弾性計算（GF = ガロワフィールド）。代数コースを完了したばかりで、これを数学的な方法で説明します。

たとえば、GF（2を取ることから始めましょう⁴）、{a₄バツ⁴ + a₃バツ³ + a₂バツ² + a₁バツ¹ + a₀バツ⁰ | a₀, 、a₁, 、...、a₄ ∈Z₂}（明確にするために、z_n = {0,1、...、n-1}、したがってz₂ = {0,1}、つまり1つのビット）。これは、これが4度のすべての多項式のセットであり、すべての要因が存在するかどうかにかかわらず、これらの要因の倍数がないことを意味します（例えば2xはありません^k）。バツ³, 、バツ⁴ + x³, 、1とx⁴ + x³ + x² + x + 1はすべて、このグループのメンバーの例です。

このセットモジュラスは、4度目の多項式を採用します（すなわち、p（x）∈Gf（2）⁴）、例：p（x）= x⁴+x¹+x⁰. 。グループでのこのモジュラス操作は、GFとしても示されます（2⁴） / p（x）。参照のために、p（x）はLFSR内の「タップ」を記述します。

また、次数3以下のランダム多項式を採用します（モジュラスの影響を受けないように、それ以外の場合は、モジュラス操作を直接実行することもできます）。₀（x）= x⁰. 。今、すべての後のa_私（x）は、xを乗算することによって計算されます。_私（x）= a_I-1（x） * x mod p（x）。

私たちは限られた分野にいるので、弾性操作は効果があるかもしれませんが、結果として生じる場合にのみ_私（x）少なくとも係数xがあります⁴ （P（x）の最高因子）。 zで数字を使用しているので、₂, 、モジュラス操作自体を実行することは、すべてが_私 p（x）とaから2つの値を追加することにより、0または1になります_私（x）一緒に（つまり、0+0 = 0、0+1 = 1、1+1 = 0、またはこれら2つを「Xoring」）。

すべての多項式は、たとえばxなどのビットのセットとして書くことができます⁴+x¹+x⁰ 〜10011. a₀（x）は種と見なすことができます。「Times X」操作は、シフト左操作と見なすことができます。弾性操作は、マスク操作と見なすことができ、マスクはP（x）です。

したがって、上記のアルゴリズムは、有効な4ビットLFSRパターンを（無限のストリーム）生成します。たとえば、定義されたaの場合₀（バツ） （バツ⁰) およびp（x） （バツ⁴+x¹+x⁰), 、GFで最初に得られた結果を定義できます（2⁴）（aに注意してください₀ 最初のラウンドの終わりまでは得られません - 数学者は一般に「1」でカウントを開始し始めます）：

 i   Ai(x)                   'x⁴'  bit pattern
 0   0x³ + 0x² + 0x¹ + 1x⁰   0     0001        (not yielded)
 1   0x³ + 0x² + 1x¹ + 0x⁰   0     0010
 2   0x³ + 1x² + 0x¹ + 0x⁰   0     0100
 3   1x³ + 0x² + 0x¹ + 0x⁰   0     1000
 4   0x³ + 0x² + 1x¹ + 1x⁰   1     0011        (first time we 'overflow')
 5   0x³ + 1x² + 1x¹ + 0x⁰   0     0110
 6   1x³ + 1x² + 0x¹ + 0x⁰   0     1100
 7   1x³ + 0x² + 1x¹ + 1x⁰   1     1011
 8   0x³ + 1x² + 0x¹ + 1x⁰   1     0101
 9   1x³ + 0x² + 1x¹ + 0x⁰   0     1010
10   0x³ + 1x² + 1x¹ + 1x⁰   1     0111
11   1x³ + 1x² + 1x¹ + 0x⁰   0     1110
12   1x³ + 1x² + 1x¹ + 1x⁰   1     1111
13   1x³ + 1x² + 0x¹ + 1x⁰   1     1101
14   1x³ + 0x² + 0x¹ + 1x⁰   1     1001
15   0x³ + 0x² + 0x¹ + 1x⁰   1     0001        (same as i=0)

4番目の位置にマスクが「1」を含める必要があることに注意して、LFSRが4ビットの結果を生成することを確認する必要があります。また、ビットストリームが0000ビットパターンになっていないことを確認するために、「1」がゼロの位置に存在する必要があること、または最終ビットが未使用になることを確認する必要があることに注意してください（すべてのビットが左にシフトすると、また、1つのシフトの後、0番目の位置でゼロになります）。

すべてのp（x）が必ずしもGFのジェネレーターであるわけではありません（2^k）（つまり、kビットのすべてのマスクが2つすべてを生成するわけではありません^K-1-1番号）。たとえば、x⁴ + x³ + x² + x¹ + x⁰ それぞれ5つの異なるポリノームの3つのグループ、または「期間5の3サイクル」：0001,0010,0100,1000,1111を生成します。 0011,0110,1100,0111,1110;および0101,1010,1011,1001,1101。 0000を生成することはできず、他の数値を生成できないことに注意してください。

通常、LFSRの出力は「シフト」されたビットです。これは、モジュラス操作が実行された場合は「1」、そうでない場合は「0」です。 2の期間のLFSR^K-1-1は、Pseudo-NoiseまたはPN-LFSRとも呼ばれ、Golombのランダム性の仮定を順守しています。

したがって、これらのビットのシーケンスは、たとえばA5/1およびA5/2モバイル暗号化標準、またはE0 Bluetooth標準など、暗号化で使用されています。しかし、彼らは望むほど安全ではありません： Berlekamp-Masseyアルゴリズム LFSRの特徴的なポリノマル（p（x））をリバースエンジニアリングするために使用できます。したがって、強力な暗号化標準が使用されます非線形FSRと同様の非線形関数。これに関連するトピックはです Sボックス AESで使用されます。

私が使用したことに注意してください int.bit_length() 手術. 。これは、Python 2.7まで実装されませんでした。
有限のビットパターンのみが必要な場合は、シードが結果に等しいかどうかを確認し、ループを破ることができます。
私のLFSR-MethodをFor-Loopで使用できます（例： for xor, pattern in lfsr(0b001,0b10011)）またはあなたは繰り返し電話することができます .next() メソッドの結果で操作、新しいものを返します (xor, result)- 毎回ペア。

LFSRには多くのアプリケーションがあります。そのうちの1つはノイズを生成することです。たとえば、SN76489とバリアント（マスターシステム、ゲームギア、メガドライブ、ネオジオポケットなどで使用されます）がLFSRを使用して白/周期ノイズを生成します。 SN76489のLFSRには本当に良い説明がありますこのページで.

それを本当にエレガントでpythonicにするために、ジェネレーターを作成してみてください、 yield-LFSRからの連続した値のまた、フローティングポイントと比較して 0.0 不必要で混乱しています。

LFSRは、コンピューターに擬似ランダム数を作成する多くの方法の1つにすぎません。数字がないので、擬似ランダム本当ランダム - シード（初期値）から始めて、同じ数学操作を進めることで簡単に繰り返すことができます。

以下は、文字列の代わりに整数とバイナリ演算子を使用したコードのバリエーションです。また、誰かが提案したように利回りを使用します。

def lfsr2(seed, taps):
    sr = seed
    nbits = 8
    while 1:
        xor = 1
        for t in taps:
            if (sr & (1<<(t-1))) != 0:
                xor ^= 1
        sr = (xor << nbits-1) + (sr >> 1)
        yield xor, sr
        if sr == seed:
            break

nbits = 8
for xor, sr in lfsr2(0b11001001, (8,7,6,1)):
    print xor, bin(2**nbits+sr)[3:]

種子が文字列ではなく（またはそうでない場合は変換する）INTのリストであると仮定した場合、以下はもう少し優雅に必要なことを行う必要があります。

def lfsr(seed, taps) :
  while True:
    nxt = sum([ seed[x] for x in taps]) % 2
    yield nxt
    seed = ([nxt] + seed)[:max(taps)+1]

例：

for x in lfsr([1,0,1,1,1,0,1,0,0],[1,5,6]) :
  print x

list_init=[1,0,1,1]
list_coeff=[1,1,0,0]
out=[]
for i in range(15):
    list_init.append(sum([list_init[i]*list_coeff[i] for i in range(len(list_init))])%2)
    out.append(list_init.pop(0))
print(out)

#https://www.rocq.inria.fr/secret/Anne.Canteaut/encyclopedia.pdf

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow