In letzter Zeit bin ich immer wieder auf das Konzept der LFSR gestoßen, das ich wegen seiner Verbindungen zu verschiedenen Bereichen sehr interessant finde und das auch an sich faszinierend ist. Es hat mich etwas Mühe gekostet zu verstehen, die letzte Hilfe war diese wirklich gute Seite , viel besser als die (zuerst ) kryptischer Wikipedia-Eintrag . Ich wollte also einen kleinen Code für ein Programm schreiben, das wie ein LFSR funktioniert. Um genau zu sein, hat das irgendwie gezeigt, wie ein LFSR funktioniert. Hier ist die sauberste Sache, die ich nach ein paar längeren Versuchen (Python) bekommen konnte:
%Vor%Ich nannte "xor" die Ausgabe der XOR-Funktion, nicht sehr korrekt. Dies soll jedoch nur zeigen, wie es durch seine möglichen Zustände kreist, tatsächlich haben Sie bemerkt, dass das Register durch eine Zeichenkette repräsentiert wird. Nicht viel logische Kohärenz.
Dies kann leicht in ein nettes Spielzeug verwandelt werden, das Sie stundenlang ansehen können (zumindest könnte ich: -)
%Vor%Dann ist mir aufgefallen, welchen Nutzen hat das beim Schreiben von Software? Ich habe gehört, dass es Zufallszahlen erzeugen kann; ist es wahr? Wie? Also wäre es schön, wenn jemand könnte:
Da es nicht viel didaktisches Zeug um dieses Stück Logik und digitale Schaltkreise gibt, wäre es auch schön, wenn dies ein Platz für Anfänger (wie mich) wäre, um ein besseres Verständnis für dieses Ding zu bekommen , oder besser, um zu verstehen, was es ist und wie es beim Schreiben von Software nützlich sein kann. Hättest du es zu einem Community-Wiki machen sollen?
Das heißt, wenn jemand Golf spielen möchte ... bitte.
Tatsächlich sind auf LFSR basierende Algorithmen sehr gebräuchlich. CRC basiert tatsächlich direkt auf LFSR. Natürlich sprechen die Leute im Informatikunterricht von Polynomen, wenn sie darüber reden, wie der Eingangswert mit dem akkumulierten Wert XOR-verknüpft werden soll, im Elektrotechnischen sprechen wir stattdessen von Taps. Sie sind die gleiche nur unterschiedliche Terminologie.
CRC32 ist sehr verbreitet. Es wird verwendet, um Fehler in Ethernet-Frames zu erkennen. Das heißt, als ich diese Antwort gepostet habe, benutzte mein PC einen LFSR-basierten Algorithmus, um einen Hash des IP-Pakets zu generieren, so dass mein Router verifizieren kann, dass das, was übertragen wird, nicht beschädigt ist.
Zip- und Gzip-Dateien sind ein weiteres Beispiel. Beide verwenden CRC zur Fehlererkennung. Zip verwendet CRC32 und Gzip verwendet sowohl CRC16 als auch CRC32.
CRCs sind im Grunde Hash-Funktionen. Und es ist gut genug, um das Internet zum Laufen zu bringen. Was bedeutet, dass LFSRs ziemlich gute Hash-Funktionen sind. Ich bin mir nicht sicher, ob Sie das wissen, aber im Allgemeinen werden gute Hash-Funktionen als gute Zufallsgeneratoren betrachtet. Aber die Sache mit LFSR ist, dass die Auswahl der richtigen Taps (Polynome) sehr wichtig für die Qualität der Hash / Zufallszahl ist.
Ihr Code ist im Allgemeinen ein Spielzeugcode, da er auf einer Reihe von Einsen und Nullen basiert. In der realen Welt arbeiten LFSR an Bits in einem Byte. Jedes Byte, das Sie durch das LFSR drücken, ändert den akkumulierten Wert des Registers. Dieser Wert ist effektiv eine Prüfsumme aller Bytes, die Sie durch das Register geschoben haben. Zwei übliche Wege, diesen Wert als eine Zufallszahl zu verwenden, besteht darin, entweder einen Zähler zu verwenden und eine Folge von Zahlen durch das Register zu schieben, wodurch die lineare Sequenz 1, 2, 3, 4 in eine gehashte Sequenz wie 15306, 22, 5587 umgewandelt wird. 994, oder um den aktuellen Wert in das Register zurückzuführen, um eine neue Zahl in scheinbar zufälliger Reihenfolge zu erzeugen.
Es sollte angemerkt werden, dass es ziemlich langsam ist, dies naiv mit dem bit-fiddling LFSR zu tun, da Sie Bits auf einmal bearbeiten müssen. Also haben die Leute Wege gefunden, mit vorberechneten Tabellen acht Bits gleichzeitig oder sogar 32 Bits gleichzeitig zu machen. Aus diesem Grund sehen Sie den LFSR-Code fast nie in freier Wildbahn. In den meisten Produktionscodes tarnt es sich als etwas anderes.
Aber manchmal kann ein einfaches bit-drehendes LFSR nützlich sein. Ich schrieb einmal einen Modbus -Treiber für ein PIC-Mikro und dieses Protokoll verwendete CRC16. Eine vorberechnete Tabelle benötigt 256 Bytes Speicher und meine CPU hatte nur 68 Bytes ( Ich mache keine Witze ). Also musste ich ein LFSR verwenden.
Da ich in Python nach einer LFSR-Implementierung gesucht habe, bin ich auf dieses Thema gestoßen. Ich fand jedoch, dass das Folgende ein bisschen genauer nach meinen Bedürfnissen war:
%Vor%Der obige LFSR-Generator basiert auf dem GF (2 k ) Modul-Kalkül (GF = Galois-Feld ). Nachdem ich gerade einen Algebra-Kurs abgeschlossen habe, werde ich das auf mathematische Weise erklären.
Nehmen wir zum Beispiel GF (2 4 ), was {a 4Wir nehmen diesen Mengenmodul ein Polynom vierten Grades (d. h. P (x) ∈ GF (2 <4>)), z. P (x) = x 4 + x 1 + x 0 . Diese Moduloperation an einer Gruppe wird auch als GF (2 4 / P) / P (x) bezeichnet. Zu Ihrer Referenz beschreibt P (x) die "Taps" innerhalb des LFSR.
Wir nehmen auch ein zufälliges Polynom von Grad 3 oder niedriger (so dass es nicht von unserem Modul beeinflusst wird, ansonsten könnten wir genauso gut die Modulusoperation direkt darauf durchführen), z. A 0 (x) = x 0 . Nun wird jedes nachfolgende A i (x) berechnet, indem es mit x multipliziert wird: A i (x) = A i-1 (x) * x Mod P (x).
Da wir uns in einem begrenzten Gebiet befinden, kann die Moduloperation eine Wirkung haben, aber nur dann, wenn das resultierende A i (x) mindestens einen Faktor x 4 hat (unser höchster Faktor in P (x)). Man beachte, dass, da wir mit Zahlen in Z 2 arbeiten, die Durchführung der Modulo-Operation selbst nichts anderes ist, als zu bestimmen, ob jedes a i durch Addieren der beiden zu 0 oder 1 wird Werte von P (x) und A (x) zusammen (dh 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0 oder 'xoring' dieser beiden) / p>
Jedes Polynom kann als ein Satz von Bits geschrieben werden, zum Beispiel x 4 + x 1 + x 0 ~ 10011 0 (x) kann als Seed angesehen werden. Die Operation 'mal x' kann als eine Verschiebung nach links gesehen werden. Die Moduloperation kann als eine Bitmaskierungsoperation angesehen werden, wobei die Maske unser P (x) ist. Der oben dargestellte Algorithmus erzeugt daher (ein unendlicher Strom von) gültigen Vier-Bit-LFSR-Mustern. Zum Beispiel für unsere definierten A 0 <(x) (x 0 ) und P (x) (x 4 + x 1 + x 0 ) können wir die folgenden ersten Ergebnisse in GF (2 4 ) definieren ) (beachte, dass A 0 erst am Ende der ersten Runde zurückgegeben wird - Mathematiker beginnen im Allgemeinen bei "1" zu zählen): Beachten Sie, dass Ihre Maske an der vierten Position eine '1' enthalten muss, um sicherzustellen, dass Ihr LFSR Vier-Bit-Ergebnisse generiert. Beachten Sie auch, dass eine "1" an der nullten Position vorhanden sein muss, um sicherzustellen, dass Ihr Bitstream nicht mit einem 0000-Bitmuster endet oder dass das letzte Bit unbenutzt wird (wenn alle Bits nach links verschoben werden, würden Sie dies tun) am Ende mit einer Null an der 0. Stelle nach einer Schicht). Nicht alle P (x) sind notwendigerweise Generatoren für GF (2 k ) (dh nicht alle Masken von k Bits erzeugen alle 2 Normalerweise ist die Ausgabe eines LFSR das Bit, das "verschoben" wird, was eine "1" ist, wenn die Modulo-Operation ausgeführt wird, und eine "0", wenn dies nicht der Fall ist. LFSRs mit einer Periode von 2 k-1, auch Pseudo-Noise oder PN-LFSR genannt, halten sich an Golombs Zufälligkeitspostulate, was besagt, dass dieses Ausgangsbit zufällig "genug" ist. Sequenzen dieser Bits haben daher ihre Verwendung in der Kryptographie, beispielsweise in den mobilen Verschlüsselungsstandards A5 / 1 und A5 / 2 oder dem Bluetooth-Standard E0. Sie sind jedoch nicht so sicher, wie man es möchte: Der Berlekamp-Massey-Algorithmus kann verwendet werden um das charakteristische Polynom (das P (x)) des LFSR rückzuentwickeln. Starke Verschlüsselungsstandards verwenden daher nichtlineare FSR oder ähnliche nichtlineare Funktionen. Ein verwandtes Thema dazu ist die S-Boxen verwendet in AES. Beachten Sie, dass ich den Vorgang int.bit_length() verwendet habe. Dies wurde erst mit Python 2.7 implementiert.
Wenn Sie nur ein endliches Bitmuster möchten, können Sie überprüfen, ob der Anfangswert dem Ergebnis entspricht, und dann die Schleife unterbrechen.
Sie können meine LFSR-Methode in einer For-Schleife verwenden (zB for xor, pattern in lfsr(0b001,0b10011) ) oder Sie können die .next() -Operation wiederholt auf das Ergebnis der Methode anwenden und jedes Mal ein neues (xor, result) -pair zurückgeben.
Es gibt viele Anwendungen von LFSRs. Einer von ihnen erzeugt Geräusche, zum Beispiel der SN76489 und Varianten (verwendet auf dem Master System, Game Gear, MegaDrive, NeoGeo Pocket, ...) verwenden ein LFSR, um weißes / periodisches Rauschen zu erzeugen. Es gibt eine wirklich gute Beschreibung von SN76489's LFSR auf dieser Seite .
Um es wirklich elegant und Pythonic zu machen, versuche, einen Generator, yield -ing sukzessive Werte aus dem LFSR zu erstellen. Außerdem ist der Vergleich mit einem Gleitkomma 0.0 unnötig und verwirrend.
Ein LFSR ist nur eine von vielen Möglichkeiten, Pseudozufallszahlen in Computern zu erstellen. Pseudozufällig, weil die Zahlen nicht wirklich zufällig sind - Sie können sie einfach wiederholen, indem Sie mit dem Anfangswert beginnen und mit den gleichen mathematischen Operationen fortfahren.
Tags und Links python language-agnostic digital-logic