Home / Tutorials / Programmieren / Zufallszahlengenerator

Zufallszahlengenerator

Die Generierung von Zufallszahlen durch Software verlässt sich im großen und ganzen auf  sog. rekursive Zahlenfolgen. Das sind Zahlenfolgen bei denen man immer das aktuelle Ergebnis in den Algorithmus einsetzt um das nächste Ergebnis zu erhalten. Unter den richtigen Voraussetzungen (oder anders ausgedrückt mit dem richtigen Algorithmus) verhalten sich diese Zahlenfolgen recht chaotisch und unvorhersehbar. Eine recht einfache Variante, die sich zu dem sehr gut in Assembler implementieren lässt, ist das „Linear feedback shift register“ (LFSR) oder „Linear rückgekoppeltes Schieberegister„. Vorweg soll hier gesagt sein, dass die hier generierten Zufallszahlen qualitativ recht „schlecht“ sind. Das bedeutet die statistische Verteilung der generierten Zahlen ist nicht gut genug um sie z.B. für kryptographische Algorithmen zu benutzen. In diesem konkreten Beispiel benutze ich ein 16bit LFSR mit dem Polynom x16 + x5 + x3 + x2 + 1. Dieses LFSR hat eine Folgenlänge von 65535, das bedeutet dass sich die Zahlenfolge nach 65535 Schritten wiederholt. 7beca88b105cff288d1340f35de8aff3 Die Zahlenfolge berechnet sich wie folgt:

  1. Die Bits Nummer 0 und 2 werden XOR verknüpft
  2. Das Ergebnis aus 1) wird mit Bit 3 XOR verknüpft
  3. Das Ergebnis aus 2) wird mit Bit 5 XOR verknüpft
  4. Das ganze Register wird nach rechts verschoben. Dabei wird das Ergebnis aus 3) in die frei werdende Stelle des 16. Bits geschoben.
  5. Das „überschüssige“ Bit das in der Grafik nach rechts verschwindet ist Pseudozufällige entweder 0 oder 1. 8 Stück davon stückeln wir zu einer 8-Bit Folge zusammen und bilden eine 8-Bit Zufallszahl.

Die XOR-Verknüpfung ist allerdings bei den AVRs nur für ganze Register implementiert und nicht für einzelne Bits. Dieses Problem umgehen wie in dem wir 2 Register als Zwischenspeicher verwenden. Da die XOR-Verknüpfung nur die Bits 0,2,3 und 5 betrifft, kann man mit einem einzelnen Register bereits alle betreffenden Bits zwischenspeichern. Durch sog. Maskieren können wir konkret bestimmen welche Bits für die XOR-Verknüpfung verwendet werden sollen. Die Bit-Jongliererei sieht dann so aus:


randomize:
ldi temp3,0
randomize_loop:

lds temp1,LORND
lds temp2,LORND

andi temp1,0b00000001
andi temp2,0b00000100

lsl temp1
lsl temp1
eor temp1,temp2

lds temp2,LORND
andi temp2,0b00010000
lsl temp1
eor temp1,temp2

lds temp2,LORND
andi temp2,0b00100000
lsl temp1
lsl temp1
eor temp1,temp2

lsl temp1
lsl temp1
lsl temp1

lds temp1,HIRND
lds temp2,LORND

rol temp1
rol temp2

sts HIRND,temp1
sts LORND,temp2

lds temp1,RND
rol temp1
sts RND,temp1

inc temp3
cpi temp3,8
brne randomize_loop

reti

.DSEG
HIRND: .BYTE 1
LORND: .BYTE 1
RND: .BYTE 1
  1. Bit 0 bis 8 in Temp1 und Temp2 kopieren.
  2. Mit dem Befehl andi das Bit 0 in Temp1 maskieren und das Bit 2 in Temp2
  3. Das Register Temp1 muss 2 mal nach links geschoben werden damit die Bits an der selben Stellen stehen, die XOR-Verknüpft werden sollen.
  4. mit dem Befehl eor die XOR-Verknüpfung von Temp1 und Temp2 berechnen. Das Ergebnis wird in Temp1 gespeichert.
  5. Das Low-Byte des LSFR wird wieder in Temp2 zwischengespeichert und das Bit 3 wird maskiert.
  6. Temp1 hat immer noch das Ergebnis aus der ersten XOR-Verknüpfung. Mit einer Rechtsverschiebung wird das Ergebnisbit an die richige Stelle verschoben bevor wir wieder eor anwenden. Das Ergebnis wird wieder in Temp1 gespeichert.
  7. Das Low-Byte LSFR wird wieder in Temp2 zwischengespeichert und das Bit 5 wird maskiert.
  8. Temp1 wird 2 mal nach rechts verschoben und eor auf Temp1 und Temp2 angewendet. Das Ergebnisbit ist nun an der Stelle 5.
  9. Durch 3 mal Linksverschieben von Temp1 wird das Ergebnisbit in das Carry-Bit befördert.
  10. Letztendlich wird durch einmaliges Rollen des LFSR das Carry-Bit an die Stelle 1 des LFSR befördert. Achtung, hier wird werden alle 16-bit gerollt!

Das ganze wird dann noch in einer Schleife 8 mal ausgeführt wird und der output beim Rollen des LSFR wird jedesmal in ein Ausgaberegister weiter gerollt, welches dann als Ausgabezahl dient. Puh….anstregend, was? Zum glück müssen wir das ganze nicht jedesmal per Hand machen, der AVR sollte das auch alleine schaffen… Zum initialisieren des Generators muss man die 2 Speicherstellen HIRND und LORND mit 2 Zahlen laden (sog. Seeden) ausserdem muss die Subroutine „randomize“ wenn möglich immer im Hintergrund laufen so lange man die Zufallszahlen benötigt. Am besten also in der Mainschleife oder so etwas. Die Subroutine muss auch mindestens einmal aufgerufen werden bevor man eine neue Zufallszahl lädt. Ansonsten bekommt man logischerweise immer die selbe Zahl. In diesem Beispielvideo greife ich in regelmässigen Zeitabständen auf die Zufallszahl zu und übergebe sie als neuen Positionsbefehl an die Servosteuerung. Die Sache ist an sich, ausser zu Demonstrationszwecken, recht Sinnfrei.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Die Checkbox für die Zustimmung zur Speicherung ist nach DSGVO zwingend.

Ich stimme zu.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.

x

Check Also

An Arduino Unu with the word Assembler superimposed

Arduino Assembler: Einführung

Was hat es mit Assembler überhaupt auf sich? Kurz gesagt, ist der Unterschied zwischen Assembler ...