Wie erstelle ich zufällige zahlen in einem mikrocontroller effizient?
Wie erstelle ich zufällige zahlen in einem mikrocontroller effizient? Gibt es irgendwelche Allgemeinen Richtlinien oder eine besonders schnelle Methode?
- Wie viel Zufälligkeit brauchen Sie? Ist die Geschwindigkeit der top-Wunsch hier, oder nicht-Berechenbarkeit besonders wichtig? Es gibt viele verschiedene algorithmen für pseudo-random number generation richten sich an unterschiedliche Anwendungen mit unterschiedlichen Zielen. Ein Spiel, zum Beispiel, wäre es nicht notwendig, die nicht-Vorhersagbarkeit ganz so viel wie zu sagen, etwas, generieren hohe Sicherheit-Verschlüsselung-codes.
- Ich brauche Geschwindigkeit. Es gibt keine kryptographische Voraussetzung.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Können Sie generieren Pseudo - zahlen durch manipulation bits durch die Simulation einer LINEAR FEEDBACK SHIFT REGISTER
Kommt dann die Frage " wie viele bits möchtest du simulieren?'
Wikipedia hat einige Informationen.
Normalerweise erzeugt pseudo-zufällige zahlen und nicht die tatsächlichen Zufallszahlen, obwohl beide möglich sind, zu unterschiedlichen Preisen.
Es gibt zwei Allgemeine Kategorien, je nachdem, ob die Sequenz für kryptografische Zwecke verwendet werden. Der primäre Unterschied ist, ob das wissen von einer Zahl in der Sequenz erlaubt die Vorhersage der nächsten. Allzweck-RNG sorgen sich nicht darum, ob das wissen des Algorithmus wäre damit ein Beobachter, duplizieren Sie die Sequenz, und Sie laufen ein bisschen schneller.
Einem typischen Allzweck-RNG-Algorithmus wird die Mersenne Twister. Es gibt viele öffentliche Implementierungen von verschiedenen algorithmen. Siehe hier für einen.
Wenn der MT benötigt zu viel Speicher, eine halbwegs anständige ist der fallback auf die linear congruential generator. (Die MT war nicht erfunden, bis 1997.) Dieser generator hat bestimmte Probleme, aber es benötigt fast keine Speicher, fast kein code, und ist extrem schnell. Implementierungen sind überall, und es wurde ausführlich in Knuth ' s Seminumerical Algorithmen.
Samen, alle RNG, benötigen Sie eine Quelle der Entropie, siehe http://en.wikipedia.org/wiki/Entropy_(computing) (Hinweis: SO erhält verwirrt über die ()'s in diesem link.) Dies ist in der Regel abgeleitet von timing-Ereignisse, die der CPU beobachten können, wie Tastatureingaben, (ich denke, das wird nicht für Sie arbeiten) unterbricht, und packet eingetroffen. Eine Echtzeit-Uhr ist oft eine akzeptable Quelle, wenn es unterhält seinen eigenen Staat, als Neustarts sind selten zeitlich in jede Art von Sequenz.
können Sie speichern einen Samen, EEPROM, und wenn das Gerät bootet, können Sie die Schrittweite ein samenkorn, und speichern Sie es erneut. Also, jedes neu starten Sie haben verschiedene zufällige Zahl.
Wenn Sie Zugang zu einem ADC, dann Lesen Sie das niedrigstwertige bit aus, und verwenden Sie es als einen Samen für eine Pseudo-Random Number Generator, wie andere auch schon gepostet haben. Natürlich werden Sie brauchen, um mehr als ein bit vom ADC, also mehrere Lesevorgänge erforderlich sind, könnte eine Weile dauern. Aber Sie müssen diese Einstellung nur einmal beim starten zum Beispiel, und verwenden Sie dann schneller PRNG erzeugen neue Zufallszahlen.
Viele Embedded-Geräte gebaut haben, die inn ADC, z.B. die ATMega-Familie bilden Atmel.
Wenn die hardware hat eine Schaltfläche für den Benutzer, mit einem einfachen trick ist, zu zählen, wie lange die Taste gedrückt wird. Mit einem schnell genug, kurze counter erhalten Sie eine "zufällige" Zahl.
Pseudo-Zufallszahlen-Generatoren, die die Schnellste und am wenigsten anspruchsvolle w.r.t. der Befehlssatz (nur shift-und xor, keine Multiplikation oder division) sind kleinere Variante (N) der Mersenne twister Idee (sogenannte Generalized Linear Feedback Shift register). Mersenne twister selbst braucht zu viel Speicher für mikrocontroller.
Das problem mit diesen Generatoren ist, dass Sie können zu generieren, die lange Sequenzen in der Nähe von null, wenn man Pech hat. Mit einer angemessenen Größe des Staates Platz und Initialisierung von einer anderen PNRG ist dies jedoch unwahrscheinlich.
Sind Sie auch nicht sicher für Kryptographie oder Glücksspiel, eine intelligente Widersacher kann Vorhersagen, zukünftige Zustände nach Beobachtung der Ausgabe. Dies ist, weil Sie linear sind.
Ich einmal so konstruiert einen generator für ein kleines Nichtstandard-Prozessor mit einer staatlichen Raum von etwa 50 24-bit-Worten. Getestet habe ich die Varianten mit den Eingefleischten test-suite, bis ich gefunden eine gute. Die Anwendung war die Erzeugung von zufälligen Variationen für ein hardware-test.
Lesen der timer und xoring/nanding/etc es mit einer Serie von bits, wird eine halb zufällig an den Benutzer, wie das timing zwischen den Ereignissen ist wahrscheinlich genug auseinander, dass der Benutzer nicht wirklich in der Lage sein zu sagen, die Korrelation mit dem timer.
Wenn Sie können lassen Sie eine pin schweben, es könnte helfen, um Zufallszahlen zu generieren, die mit linear feedback shift register. Ich bin mir nicht sicher, ob dies ist der Weg zu gehen, aber bitte haben Sie einen Blick auf meinen code:
EDIT: ich fand heraus, meine Antwort kann eine schlechte. Mehr details, warum sollten Sie nicht verwenden ein floating-digital pin: https://electronics.stackexchange.com/questions/50476/random-number-generators-using-a-gpio-pin