Frage

In letzter Zeit stieß ich immer wieder in das Konzept der LFSR, dass ich wegen ihrer Verbindungen zu verschiedenen Bereichen ganz interessant finden und auch faszinierend an sich. Es hat mich einige Mühe zu verstehen, die letzte Hilfe war wirklich gut , viel besser als die (zunächst) kryptische wikipedia Eintrag . Also wollte ich einen kleinen Code für ein Programm schreiben, das wie ein LFSR gearbeitet. Um genauer zu sein, dass irgendwie gezeigt, wie ein LFSR funktioniert. Hier ist die sauberste Sache, die ich mit nach einigen lenghtier Versuche kommen konnte (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

I „xor“ der Ausgang der XOR-Funktion mit dem Namen, nicht sehr korrekt. Allerdings ist dies nur zu zeigen, wie sie Kreise durch seine möglichen Zustände in der Tat bemerkt, dass Sie das Register durch eine Zeichenkette dargestellt wird. Nicht viel logische Kohärenz.

Dies kann leicht in ein schönes Spielzeug gedreht werden Sie stundenlang zuschauen können (zumindest ich konnte: -) 

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)

Dann fiel mir auf, was den Einsatz dieser Software in schriftlicher Form ist? Ich hörte es Zufallszahlen erzeugen kann; ist es wahr? Wie? So wäre es schön, wenn jemand könnte:

  • erklären, wie ein solches Gerät verwenden, bei der Software-Entwicklung
  • kommt mit einigem Code auf, den Punkt über oder genau wie meine zu unterstützen verschiedene Möglichkeiten, um zu zeigen, es zu tun, in jeder Sprache

Auch als Theres nicht viel didaktisches Material um über dieses Stück von Logik und digitalen Schaltungen, wäre es schön, wenn dies ein Ort für noobies sein könnte (wie ich) ein besseres Verständnis für dieses , was zu bekommen oder besser zu verstehen, was es ist und wie kann es sinnvoll sein, wenn das Schreiben von Software. Sollte haben sie ein Community Wiki gemacht?

sagte, dass, wenn jemand fühlt sich an wie Golf ... Nichts zu danken.

War es hilfreich?

Lösung

Eigentlich Algorithmen basierend auf LFSR sind sehr häufig. CRC ist eigentlich direkt basierend auf LFSR. Natürlich in Computern sprechen Wissenschaft Klassen Menschen über Polynome, wenn sie redet, wie der Eingangswert sollte mit dem akkumulierten Wert zu XOR-verknüpft, in electornics Engineering wir über Taps statt reden. Es sind die gleichen nur eine andere Terminologie.

ist CRC32 ein sehr allgemein. Es wird verwendet, um Fehler in Ethernet-Frames zu erfassen. Das bedeutet, dass, wenn ich diese Antwort hätte mein PC einen LFSR-basierten Algorithmus verwendet, um einen Hash-Wert des IP-Pakets zu erzeugen, so dass mein Router kann überprüfen, dass das, was er die Sende nicht beschädigt ist.

Zip und gzip-Dateien sind ein weiteres Beispiel. Beide verwenden CRC zur Fehlererkennung. Zip Anwendungen CRC32 und gzip verwendet sowohl CRC16 und CRC32.

CRCs sind grundsätzlich Hash-Funktionen. Und es ist gut genug, um die Internet-Arbeit zu machen. Welche Mittel LFSRs sind ziemlich gute Hash-Funktionen. Ich bin mir nicht sicher, ob Sie das wissen, aber im Allgemeinen guten Hash-Funktionen in Betracht gezogen werden gute Zufallszahlen-Generatoren. Aber die Sache mit LFSR ist, dass die richtigen Taps Auswahl (Polynome) ist sehr wichtig für die Qualität der Hash / Zufallszahl.

Der Code ist in der Regel Code Spielzeug, da sie auf einer Reihe von Einsen und Nullen arbeiten. In der realen Welt LFSR Arbeit an Bits in einem Byte. Jedes Byte Sie das LFSR durchsetzen ändert den akkumulierten Wert des Registers. Dieser Wert ist in Wirklichkeit eine Prüfsumme aller Sie haben Push durch das Register-Bytes. Zwei gängige Möglichkeiten der Verwendung dieses Wertes als eine Zufallszahl, um entweder einen Zähler verwendet werden, und eine Folge von Zahlen durch das Register schieben, um dadurch die Umwandlung der lineare Folge 1,2,3,4 bis zu einem gewissen gehashten Sequenz wie 15306,22,5587, 994, oder den aktuellen Wert in das Register rückzukoppeln eine neue Nummer in scheinbar zufälliger Reihenfolge zu erzeugen.

Es sollte beachtet werden, dass diese naiv mit Bit-Hantieren tun LFSR ziemlich langsam ist, da Sie zu einem Zeitpunkt, zu verarbeiten Bits haben. So haben Menschen mit Möglichkeiten, mit vorausberechneten Tabellen kommen sie acht Bits auf einmal oder sogar 32 Bits gleichzeitig zu tun. Aus diesem Grunde ist man so gut wie nie LFSR Code in freier Natur zu sehen. In den meisten Produktionscode tarnt es als etwas anderes.

Aber manchmal ein einfaches Bit-twiddling LFSR kann nützlich sein. Ich schrieb einmal ein Modbus Treiber für ein PIC Mikro und das verwendete Protokoll CRC16. Eine vorberechnete Tabelle erfordert 256 Byte Speicher und meine CPU hatte nur 68 Byte ( Ich bin nicht kidding ). So hatte ich ein LFSR zu verwenden.

Andere Tipps

Da ich war auf der Suche nach einer LFSR-Implementierung in Python, stolperte ich über dieses Thema. Ich fand jedoch, dass die folgenden etwas genauer nach meinen Bedürfnissen war: 

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

Die obige LFSR-Generator basiert auf GF (2 K ) Modulus Calculus (GF = Galois-Feld ). gerade abgeschlossen, die eine Algebra natürlich, ich werde diese die mathematische Art und Weise erklären.

Beginnen wir, indem zum Beispiel GF (2 4 ), die gleich {a 4 x 4 + a 3 x 3 + a 2 x 2 + a 1 x 1 + a 0 x 0 | a 0 a 1 , ..., a 4 ? Z 2 } (zu klären, Z < sub> n = {0,1, ..., n-1} und daher Z 2 = {0,1}, das heißt ein Bit). Dies bedeutet, dass das ist die Menge aller Polynome des vierten Grades mit der alle Faktoren entweder vorhanden sein oder nicht, aber keine Vielfachen dieser Faktoren (z.B. gibt es keine 2x K ). x 3 , x 4 + x 3 , 1 und x 4 + x 3 + x 2 + x + 1 sind Beispiele für Mitglieder dieser Gruppe.

Wir nehmen diese Soll Modul ein Polynom vierten Grades (das heißt, P (x) ? GF (2 4 )), z.B. P (x) = x 4 + x 1 + x 0 . Dieser Modul Betrieb auf einer Gruppe wird auch als GF (2 4 ) / P (x) bezeichnet. Zu Ihrer Information, P (x) beschreibt die 'Taps' im LFSR.

Wir nehmen auch ein zufälliges Polynom vom Grad 3 oder senken (so dass sie nicht von unserem Modul betroffen ist, sonst könnten wir genauso gut den Modul-Vorgang durchführen direkt auf sie), z.B. A 0 (x) = x 0 . A i (x) = A i-1 (x): Jetzt kann jeder nachfolgenden A i (x) wird durch Multiplikation mit x berechnet * x mod P (x).

Da wir in einem begrenzten Bereich sind, kann die Modulo-Operation eine Wirkung hat, sondern nur, wenn die resultierenden A i (x) mindestens einen Faktor x 4 (unser höchster Faktor in P (x)). Beachten Sie, dass, da wir mit den Zahlen in Z arbeiten 2 , selbst die Modul-Operation ist nichts anderes als die Bestimmung, ob jeder eine i ein 0 oder 1 wird durch die zwei Hinzufügen Werte von P (x) und A i (x) zusammen (dh 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0 ist, oder 'XOR-Verknüpfung' diese zwei).

Jedes Polynom kann als ein Satz von Bits geschrieben werden, zum Beispiel x 4 + x 1 + x 0 ~ 10011. Die A 0 (x) als Samen zu sehen. Die ‚mal x‘ Operation ist zu sehen, wie ein Schaltvorgang verlassen. Die Modul Operation kann als Bit-Maskierungsoperation zu sehen ist, mit dem Maske unserem P (x).

Der obigen Algorithmus daher dargestellt erzeugt (ein unendlichen Strom) gültig Vier-Bit-LFSR Muster. Zum Beispiel für unser definierten A 0 (x) (x 0 ) und P (x) (x 4 + x 1 + x 0 ) , können wir die folgenden ersten lieferte Ergebnisse in GF definieren (2 4 ) (Man beachte, daß A 0 ergeben sich nicht am Ende der ersten Runde bis - Mathematiker allgemeine Zählung bei '1') starten: 

 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)

Beachten Sie, dass Ihre Maske muss eine ‚1‘ enthalten in der vierten Position, um sicherzustellen, dass Ihre LFSR Vier-Bit-Ergebnisse erzeugt. Beachten Sie auch, dass eine ‚1‘ in der nullten Position vorhanden sein müssen, um sicherzustellen, dass Ihre Bitstrom nicht mit einem 0000-Bit-Muster enden würde, oder dass das letzte Bit würde ungenutzt (wenn alle Bits nach links verschoben werden, würden Sie am Ende auch mit einer Null an der 0-ten Position, nachdem eine Schicht).

Nicht alle P (x) 's notwendigerweise sind Generatoren für GF (2 k ) (dh nicht alle Masken von k Bits erzeugen alle 2 k-1 - 1-Nummern). Zum Beispiel x 4 + x 3 + x 2 + x 1 + x 0 erzeugt 3 Gruppen von 5 verschiedenen polynomals jeweils oder „3 Zyklen der Periode 5“: 0001,0010,0100,1000,1111; 0011,0110,1100,0111,1110; und 0101,1010,1011,1001,1101. Beachten Sie, dass 0000 niemals erzeugt werden, und eine andere Zahl nicht erzeugen kann.

die Ausgabe eines LFSR Üblicherweise ist das Bit, das ‚verschoben‘ aus, das eine ‚1‘, wenn der Modulo-Operation wird durchgeführt, und eine ‚0‘, wenn es nicht ist. LFSRs mit einer Periode von 2 k-1 -1, auch als Pseudo-Rauschen oder PN-LFSRs, sich an Golomb der Zufälligkeit Postulate, die so viel sagt wie, dass dieser Ausgang Bit zufällig ist ‚genug‘.

Die Sequenzen dieser Bits haben daher ihre Verwendung in der Kryptographie, zum Beispiel in der A5 / 1 und A5 / 2 mobilen Verschlüsselungsstandards oder dem E0 Bluetooth-Standard. Allerdings sind sie nicht so sicher, wie man möchte: die Berlekamp-Massey-Algorithmus kann das charakteristische Polynom (P (x)) des LFSR Reverse-Engineering eingesetzt werden. Starke Verschlüsselungsstandards deshalb verwenden nichtlineare FSR 's oder ähnliche nicht-lineare Funktionen. Ein verwandtes Thema hierfür ist das S-Box verwendet in AES.

Beachten Sie, dass ich verwendet habe, den int.bit_length() Betrieb . Dies wurde erst Python 2.7 implementiert.
Wenn Sie es nur wie eine endliche Bitmuster, können Sie prüfen, ob der Samen das Ergebnis ist gleich und dann brechen Sie Ihre Schleife.
Sie können mein LFSR-Verfahren in einem for-Schleife (z for xor, pattern in lfsr(0b001,0b10011)) oder Sie können auf dem Ergebnis des Verfahrens den .next() Betrieb wiederholt verwenden nennen, ein neues (xor, result)-Paar jedes Mal zurück.

Es gibt viele Anwendungen von LFSRs. Einer von ihnen erzeugt Lärm, beispielsweise die SN76489 und Varianten (verwendet auf dem Master System, Game Gear, Mega Drive, NeoGeo-Tasche, ...) ein LFSR verwenden weiß / periodisches Rauschen zu erzeugen. Es ist eine wirklich gute Beschreibung von SN76489 der LFSR auf dieser Seite .

Um es wirklich elegant und Pythonic, versucht, einen Generator, yield-ing aufeinanderfolgende Werte aus dem LFSR zu erstellen. Auch zu einer Gleitkomma 0.0 Vergleich ist unnötig und verwirrend.

Ein LFSR ist nur eine von vielen Möglichkeiten, Pseudozufallszahl in Computern zu erstellen. Pseudo-zufällig, weil es Zahlen sind nicht wirklich random - Sie können sie leicht wiederholen, indem Sie mit dem Samen (Anfangswert) und Verfahren mit den gleichen mathematischen Operationen beginnen.

Hier ist eine Variation auf Ihrem Code ganze Zahlen und binäre Operatoren anstelle von Strings. Es nutzt auch die Ausbeute als jemand vorgeschlagen. 

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:]

Wenn wir das Saatgut übernehmen Sie eine Liste von ints anstelle einer Zeichenfolge (oder es umwandeln, wenn dies nicht der Fall), dann sollte die folgende tun, was Sie mit ein bisschen mehr Eleganz wollen: 

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

Beispiel: 

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
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top