10

最近、私は 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)

それから、ソフトウェアを書く上でこれが何の役に立つのだろうと思いました。乱数を生成できると聞きました。それは本当ですか？どうやって？だから、誰かができればいいです：

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

また、このロジックとデジタル回路の部分についてはあまり教訓的なものがないので、これが（私のような）初心者がこのことをよりよく理解するための場所、またはそれが何であるかをよりよく理解するための場所になるといいでしょう.ソフトウェアを作成するときにどのように役立つかを説明します。コミュニティ wiki にするべきでしたか?

とは言っても、誰かがゴルフをしたいなら...大歓迎です。

4

9 に答える 9

13

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

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ジェネレーターは、GF（2 k）モジュラス計算（GF =ガロア体）に基づいています。代数コースを修了したばかりなので、これを数学的に説明します。

たとえば、GF（2 4 ）を例にとってみましょう。これは、{a 4 x 4 + a 3 x 3 + a 2 x 2 + a 1 x 1 + a 0 x 0 | a 0、a 1、...、a4∈Z2 }（明確にするために、Z n = {0,1、...、n-1}、したがってZ 2 = { 0,1}、つまり1ビット）。これは、これが4次のすべての多項式のセットであり、すべての因子が存在するかどうかにかかわらず、これらの因子の倍数がないことを意味します（たとえば、2x kはありません）。バツ3、x 4 + x 3、1およびx 4 + x 3 + x 2 + x + 1は、すべてこのグループのメンバーの例です。

この設定されたモジュラスを4次の多項式（つまり、P（x）∈GF（2 4））とします。たとえば、P（x）= x 4 + x 1 +x0です。グループに対するこのモジュラス演算は、GF（2 4）/ P（x）としても表されます。参考までに、P（x）はLFSR内の「タップ」を表します。

また、次数3以下のランダム多項式を使用します（モジュラスの影響を受けないようにするため、モジュラス演算を直接実行することもできます）。たとえば、A 0（x）=x0です。これで、後続のすべてのA i（x）は、xを乗算して計算されます。Ai （x）= A i -1（x）* x mod P（x）。

私たちは限られた分野にいるので、モジュラス演算が効果を発揮する可能性がありますが、結果として得られるA i（x）が少なくとも係数x 4（P（x）で最も高い係数）を持つ場合に限ります。Z 2の数値を処理しているため、モジュラス演算自体を実行することは、P（x）とA i（x）の2つの値を足し合わせて、すべてのaiが0になるか1になるかを判断することに他なりません（つまり、0 + 0 = 0、0 + 1 = 1、1 + 1 = 0、またはこれら2つを「xoring」します。

すべての多項式は、ビットのセットとして記述できます。たとえば、x 4 + x 1 + x 0〜10011です。A0 （ x）はシードと見なすことができます。'times x'操作は、左シフト操作と見なすことができます。モジュラス演算はビットマスキング演算と見なすことができ、マスクはP（x）です。

したがって、上記のアルゴリズムは、有効な4ビットLFSRパターン（の無限ストリーム）を生成します。たとえば、定義したA 0（x）（x 0）およびP（x）（x 4 + x 1 + x 0）の場合、次の最初に生成された結果をGF（2 4 ）で定義できます（A 0に注意してください） 。最初のラウンドが終了するまで生成されません-数学者は通常「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)

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

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

通常、LFSRの出力は、「シフトアウト」されたビットです。これは、モジュラス演算が実行された場合は「1」であり、実行されていない場合は「0」です。周期が2k- 1-1のLFSRは、疑似ノイズまたはPN-LFSRとも呼ばれ、Golombのランダム性の仮定に準拠しています。これは、この出力ビットが「十分に」ランダムであると言っています。

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

int.bit_length()操作を使用したことに注意してください。これはPython2.7まで実装されていませんでした。
有限ビットパターンのみが必要な場合は、シードが結果と等しいかどうかを確認してから、ループを中断できます。
私のLFSRメソッドをforループ（例for xor, pattern in lfsr(0b001,0b10011)）で使用するか、メソッドの結果に対して操作を繰り返し呼び出して、毎回.next()新しいペアを返すことができます。(xor, result)

于 2012-03-26T17:26:12.163 に答える
5

実際、LFSR に基づくアルゴリズムは非常に一般的です。CRC は、実際には LFSR に直接基づいています。もちろん、コンピュータ サイエンスの授業では、入力値が累積値と XOR される方法について話しているときに多項式について話しますが、電子工学では代わりにタップについて話します。それらは用語が異なるだけで同じです。

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

Zip および Gzip ファイルは別の例です。どちらもエラー検出に CRC を使用します。Zip は CRC32 を使用し、Gzip は CRC16 と CRC32 の両方を使用します。

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

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

一度にビットを処理する必要があるため、ビットをいじる LFSR を単純に使用してこれを行うと非常に遅くなることに注意してください。そのため、事前に計算されたテーブルを使用して、一度に 8 ビットまたは一度に 32 ビットでさえ行う方法を考え出しました。これが、実際に LFSR コードを目にすることがほとんどない理由です。ほとんどの製品コードでは、別のものになりすます。

しかし、単純なビット操作の LFSR が役立つ場合もあります。私はかつてPICマイクロ用のModbusドライバーを書きましたが、そのプロトコルはCRC16を使用していました。事前に計算されたテーブルには 256 バイトのメモリが必要ですが、私の CPU には 68 バイトしかありませんでした (冗談ではありません)。そのため、LFSR を使用する必要がありました。

于 2010-09-17T14:46:00.670 に答える
2

LFSR には多くのアプリケーションがあります。それらの 1 つはノイズを生成しています。たとえば、SN76489 とその亜種 (Master System、Game Gear、MegaDrive、NeoGeo Pocket などで使用) は、LFSR を使用してホワイト/周期ノイズを生成します。このページには、SN76489 の LFSR に関する非常に適切な説明があります。

于 2010-09-17T21:32:02.467 に答える
2

これが私のpythonライブラリの1つです-LFSRを実装するpylfsrです。任意の長さの LFSR を処理してバイナリ シーケンスを生成できる効率的なものにしようとしました。

import numpy as np
from pylfsr import LFSR

#for 5-bit LFSR with polynomial  x^5 + x^4 +  x^3 + x^2 +1
seed = [0,0,0,1,0]
fpoly = [5,4,3,2]
L = LFSR(fpoly=fpoly,initstate =seed)
seq = L.runKCycle(10)

ステップですべての情報を表示することもできます。

state = [1,1,1]
fpoly = [3,2]
L = LFSR(initstate=state,fpoly=fpoly,counter_start_zero=False)
print('count \t state \t\toutbit \t seq')
print('-'*50)
for _ in range(15):
    print(L.count,L.state,'',L.outbit,L.seq,sep='\t')
    L.next()
print('-'*50)
print('Output: ',L.seq)

出力

count    state      outbit   seq
--------------------------------------------------
1   [1 1 1]     1   [1]
2   [0 1 1]     1   [1 1]
3   [0 0 1]     1   [1 1 1]
4   [1 0 0]     0   [1 1 1 0]
5   [0 1 0]     0   [1 1 1 0 0]
6   [1 0 1]     1   [1 1 1 0 0 1]
7   [1 1 0]     0   [1 1 1 0 0 1 0]
8   [1 1 1]     1   [1 1 1 0 0 1 0 1]
9   [0 1 1]     1   [1 1 1 0 0 1 0 1 1]
10  [0 0 1]     1   [1 1 1 0 0 1 0 1 1 1]
11  [1 0 0]     0   [1 1 1 0 0 1 0 1 1 1 0]
12  [0 1 0]     0   [1 1 1 0 0 1 0 1 1 1 0 0]
13  [1 0 1]     1   [1 1 1 0 0 1 0 1 1 1 0 0 1]
14  [1 1 0]     0   [1 1 1 0 0 1 0 1 1 1 0 0 1 0]
--------------------------------------------------
Output:  [1 1 1 0 0 1 0 1 1 1 0 0 1 0 1]

このように視覚化することもできます

ここに画像の説明を入力

ここでドキュメントをチェックしてください

于 2021-04-30T23:21:42.370 に答える
1

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

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:]
于 2010-09-17T15:55:13.580 に答える
1

本当にエレガントで Pythonic にするためにyield、LFSR から連続する値を -ing するジェネレータを作成してみてください。また、浮動小数点との比較0.0は不必要で混乱を招きます。

LFSR は、コンピューターで疑似乱数を作成する多くの方法の 1 つにすぎません。数値は実際にはランダムではないため、疑似ランダム - シード (初期値) から始めて同じ数学演算を進めることで、簡単に繰り返すことができます。

于 2010-09-17T12:31:29.107 に答える
0

シードが文字列ではなく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
于 2010-09-17T21:48:49.537 に答える
0 
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
于 2014-12-04T09:29:59.790 に答える