Der theoretische Hintergrund zu Zufallszahlen wird hier nur so weit betrachtet, wie es für das Verständnis ihrer Anwendung erforderlich ist. Wer sich eingehend über die Theorie informieren möchte, möge bspw. bei Wikipedia nachschlagen. Im Beitrag auf dieser Seite geht es vor allem um die praktischen Aspekte für den Microcontroller-Programmierer.
Wozu benötigt man Zufallszahlen?
Zufallszahlen haben ein weites Anwendungsfeld in der Informatik. Sie werden bspw. für Simulationen und Datenverschlüsselung (Kryptographie), aber auch für Computerspiele gebraucht, um in die Reaktion des Computers bzw. des Programms einen nicht vorhersagbaren Aspekt einzubauen. In typischen industriellen Microcontroller-Anwendungen wie z. B. einer Heizungssteuerung wird man Zufallszahlen hingegen eher nicht benötigen. Ein einfaches und unmittelbar einleuchtendes Beispiel für ein Mikrocontroller-Programm, das Zufallszahlen verwendet, stellt eine Würfelsimulation dar - siehe etwa unseren Bausatz Experimentierwürfel. Auch im Audio-Bereich werden Zufallszahlen genutzt, um akustisches Rauschen zu erzeugen, das Bestandteil vieler komplexer Geräusche ist.
Echte Zufallszahlen ...
Eine Folge echter Zufallszahlen zeichnet sich dadurch aus, dass sie auch bei perfekter Kenntnis des erzeugenden Vorgangs nicht vorhersagbar und nicht reproduzierbar (identisch wiederholbar) ist. Echte Zufallszahlen lassen sich nur mit einem gewissen Hardware-Aufwand erzeugen, indem man bspw. thermisches Rauschen nutzt, das sich in Halbleiterbauelementen als elektrisches Rauschen äußert, also in winzigen Spannungsschwankungen, die zur Auswertung hoch verstärkt werden müssen.
Schaltbild zum ADC-Zufallszahlengenerator
In manchen Internetbeiträgen findet sich der Tipp, man könne echte Zufallszahlen einfach dadurch erzeugen, dass man den Spannungspegel an einem offenen Controller-Eingang über den ADC (Analog-Digital-Wandler) abfragt und möglichst nur die "unteren" Bits des Ergebnisses verwendet. An einem offenen Eingang stelle sich ein schwankendes, unvorhersehbares Spannungsniveau ein, das als zufällig betrachtet werden könne. Das klingt fast zu schön, um wahr zu sein, und sollte auf jeden Fall geprüft werden! Das ist mit der nebenstehenden Schaltung und diesem Programm möglich:
- Assemblerprogramm und Hex-Datei im ZIP-Archiv
Das Programm ist für eine Taktfrequenz von 1,2 MHz ausgelegt. Zum erneuten Assemblieren wird diese Makrosammlung benötigt.
Was macht das Programm? Es erzeugt Töne, deren Frequenz durch Zufallszahlen bestimmt wird. Für jeden Ton wird der ADC viermal abgefragt. Von den Ergebnissen wird jeweils nur das Bit 0 verwendet. Diese vier Bits werden zu einer Zufallszahl zusammengeschoben, die aus einer Tabelle die Daten zu einem von 16 Tönen (im Halbtonabstand auf der gleichmäßig temperierten Tonskala) auswählt. Wenn der Tipp Recht hat, müsste so eine völlig chaotische Melodie entstehen. Meine Beobachtung ist jedoch eine andere: Es gibt nur eine geringe Variation der Töne. Offenbar schwankt der Spannungspegel am offenen Pin kaum. Das ändert sich erst, wenn man ein längeres Kabel an den Pin anschließt und womöglich noch dessen blankes Ende in die Hand nimmt. Was da die Spannung ändert, dürfte vor allem Einstrahlung aus dem Wechselstromnetz sein ("Brumm"). Nicht wirklich zufällig... Damit man auch einen Eindruck vom gesamten 10bit-Zahlenwert bekommt, den der ADC aus dem Anschluss liest, lässt sich das Programm in einen anderen Modus versetzen, indem PB4 auf Masse gelegt wird. Dann (nach einem Reset) wird das ADC-Ergebnis direkt in eine Tonfrequenz im Bereich von etwa 140 bis 4.840 Hz umgesetzt. Hierbei wird sich natürlich erst recht keine große Schwankungsbreite einstellen, wenn am einfach nichts an PB2 anschließt.
... und Pseudo-Zufallszahlen
Vielfach braucht man jedoch überhaupt keinen Hardwareaufwand zu treiben, denn in den meisten Anwendungen dürften so genannte Pseudo-Zufallszahlen völlig ausreichen und sind evtl. sogar vorteilhaft. Ein Generator für Pseudo-Zufallszahlen erzeugt eine Folge von Zahlen, die auf den ersten Blick ohne Zusammenhang, eben zufällig, zu sein scheinen. Tatsächlich steckt aber ein mathematisches Prinzip hinter der Erzeugung, und unter gleichen Voraussetzungen entsteht immer wieder dieselbe, identische Abfolge. Diese Reproduzierbarkeit ist von Vorteil, wenn etwa eine Simulation mit identischen zufälligen Einflussgrößen wiederholt werden soll.
Es gibt mehrere Methoden, um Pseudo-Zufallszahlen zu erzeugen. In Computern, die über leistungsfähige mathematische Co-Prozessoren verfügen, lassen sich problemlos mathematisch aufwendige Algorithmen programmieren, die bspw. Divisionen durch sehr große Primzahlen oder Ähnliches durchführen. Bei der Realisierung mit einem viel niedriger getakteten Mikrocontroller ohne allzu große Rechenfähigkeit und vielleicht knappem Programmspeicherplatz greift man besser auf andere, bodenständigere Methoden zurück. Bewährt sind so genannte linear rückgekoppelte Schieberegister, kurz LFSR (für linear feedback shift register). Die mathematische Beschreibung der Funktion, die ein LFSR ausdrückt, findet sich bspw. bei Wikipedia. Die technische Umsetzung ist mit Hilfe eines Schieberegisters und einem oder mehrerer Exklusiv-Oder-Gatter (EOR) direkt in Hardware sehr effizient möglich. Aber auch ein Microcontroller-Programm benötigt nur einige Zeilen (Assembler-) Code zur Realisierung in Software.
Beispiel für ein einfaches LFSR
Das Prinzip des LFSR besteht darin, den Ausgang eines Schieberegisters auf den Eingang rückzukoppeln und mindestens eine EOR-Operation durchzuführen. Die nebenstehende Abbildung stellt eine besonders einfache Realisierung mit einem 23-Bit-Schieberegister und nur einem EOR-Gatter dar. Bei geeigneter Wahl einer Kombination aus Registerlänge n und den Einkopplungsstellen durchläuft das LFSR beim Shiften (bitweises Weiterschieben) aus einem beliebigen Anfangszustand ungleich null sämtliche 2n - 1 möglichen Zustände, bis der Startzustand wieder erreicht ist. Im Falle dieser Beispielimplementierung sind das bereits mehr als acht Millionen Zustände. Durch Abgreifen eines Bits, z. B. Bit 0, nach jedem Shift-Schritt oder Verwendung größerer Registeranteile nach mehreren Schritten lassen sich Pseudo-Zufallszahlen gewinnen. Komplexere LFSR enthalten mehrere EOR-Gatter, die zwischen einzelnen Registerzellen angeordnet sind und das "umlaufende" Bit mehrfach mit dem internen Bit-Strom verknüpfen. Auf diese Weise findet eine stärkere Veränderung des Registerinhalts pro Shift-Schritt statt.
Eine Zwischenstufe zwischen den echten und Pseudo-Zufallszahlen stellen Zahlenwerte dar, die auf besondere Weise gewonnen werden und als scheinbar echte Zufallszahlen bezeichnet werden können. Eine solche Zahl ist bspw. die exakte Uhrzeit zu einem bestimmten Zeitpunkt oder die möglichst genau gemessene Zeitdauer eines Tastendrucks. Wird eine scheinbar echte Zufallszahl zur Initialisierung eines LFSR verwendet, so kann man durch das Shiften eine Folge scheinbar echter Zufallszahlen generieren. Der Experimentierwürfel geht so vor, wenn aus dem Normalbetrieb heraus durch langen Tastendruck der Dauerwürfelmodus gestartet wird.
LFSR-Beispielprogramm für ATtiny13
Schaltbild zur Zufallszahlenanwendung
Ein Beispielprogramm demonstriert die Erzeugung von Zufallszahlen per LFSR und zeigt einfache Anwendungsmöglichkeiten. Der Piezo-Piepser zwischen PB0 und PB1 kann durch einen kleinen Lautsprecher (z. B. PC-Lautsprecher) in Reihe mit einem Widerstand (z. B. 470 Ω) ersetzt werden.
Das Programm ist - wie meistens in dieser Rubrik - für den ATtiny mit 1,2 MHz Systemtakt ausgelegt. Es stehen das Assemblerprogramm als Textdatei sowie Assemblerprogramm und Hex-Datei im ZIP-Archiv zum Download zur Verfügung. Zum erneuten Assemblieren wird diese Makrosammlung benötigt.
Durch den Pegel an PB2 wird (auch jederzeit im laufenden Betrieb) zwischen zwei unterschiedlichen LFSR-Realisierungen umgeschaltet:
- PB2 offen oder auf VCC: das oben dargestellte LFSR mit 23 Bits
- PB2 auf Masse: ein LFSR mit 32 Bits und drei 'Anzapfungen'
Über den Pegel an PB3 und PB4 lassen sich vier verschiedene Funktionen wählen. Das muss schon vor dem Programmstart geschehen; nach jedem Funktionswechsel ist also ein Reset erforderlich. Jede Funktion ist primär entweder als akustischer oder als optischer Effekt konzipiert.
- PB3 und PB4 offen (oder auf VCC-Pegel): Es werden Töne erzeugt, deren Frequenz und Dauer zufallsabhängig sind. Sicher nicht jedermanns Musikgeschmack...
- PB3 offen, PB4 auf Masse: Wieder werden Töne erzeugt, diesmal aber etwas harmonischer, denn es werden nur Töne aus der (Halbton-) Tonleiter im Umfang von einer Oktave ausgewählt, die zudem immer gleichlang sind, und die Sprungweite beim Tonwechsel ist begrent. Wenn man länger lauscht, erkennt man dann und wann vielleicht einen Anflug von Melodie.
- PB3 auf Masse, PB4 offen: Die LED wird per PWM (Pulsweitenmodulation) angesteuert. Zweimal pro Sekunde wird das Taktverhältnis neu zufallsabhängig gesetzt. Das Auge empfindet wechselnde Helligkeiten.
- PB3 und PB4 auf Masse: Etwa 40.000 Mal pro Sekunde wird zufallsabhängig entschieden, ob die Spannung am Lautsprecher entweder umgeschaltet oder nicht geändert wird. Das resultierende Signal kann als schnell wechselnde Mischung vieler unterschiedlicher Tonfrequenzen interpretiert werden. Es äußert sich als Rauschen.
Die entscheidenden Unterprogramme sind zufallsz1 und zufallsz2, die Zufallszahlen in wählbarer Bit-Länge bereitstellen. Im 'echten' Einsatz bräuchte man natürlich nur eine dieser alternativen LFSR-Realisierungen.