KC-News 3/1996

Zufall und C(h)aos

von Frank Dachselt

Mitunter steht ein Programmierer vor der Aufgabe, etwas Zufälliges oder zumindest annähernd Zufälliges auf seinem Rechner zu erzeugen. Die bekannten Realisierungen reichen von der Verwendung bestimmter numerischer Rekursionen (Zufallsgeneratoren in Hochsprachen) bis hin zur Nutzung des beim Z80/U880 vorhandenen Refreshregisters.

Das Ergebnis steht dann meist als Folge zufällig erscheinender Zahlen zur weiteren Verwendung bereit. Der Vollständigkeit halber soll hier angemerkt werden, daß es sich bei allen soft- oder hardwaremäßig realisierten, freilaufenden Generatoren genaugenommen nur um Pseudozufall handelt, denn unser Rechner ist ja ein determiniertes System (auch, wenn es mitunter nicht so scheint).

Im folgenden soll ein Generatorprinzip mit einigen bemerkenswerten Eigenschaften vorgestellt werden, dessen softwaremäßige Realisierung besonderes einfach ist. Der Beitrag soll gleichzeitig ein kleiner Exkurs in die Assembler-Programmierung sein und auch einem Anfänger die Möglichkeit zum Experimentieren geben.

Das Prinzip des zur Klasse der linear rückgekoppelten Schieberegister gehörenden (Pseudo-)Zufallsgenerators ist in Bild 1 dargestellt. Er besteht aus einer Registerkette (hier 16 Bit), deren Inhalt mit jedem Takt um eine Bitstelle nach links verschoben wird. Das höchstwertigste Bit (hier Bit 15) geht dabei verloren, das niederwertigste Bit (Bit 0) ergibt sich aus der Modulo-2-Addition (XOR-Verknüpfung) einer bestimmten Menge von Bits des vorhergehenden Zustandes (hier sind das die Bits 10, 12, 13 und 15).

Bild 1: Linear rückgekoppeltes Schieberegister als Zufallsgenerator

Das bedeutet: Enthalten diese Bitstellen eine gerade Anzahl von Einsen, so ist Bit 0 im nächsten Takt Null, bei einer ungeraden Anzahl von Einsen ist es entsprechend Eins. Auf diese Weise wird in der Registerkette eine Folge von 16-Bit-Zahlen erzeugt. Bei geeigneter Wahl der Rückkopplung, die allein durch Anzahl und Wertigkeit der verknüpften Bitstellen bestimmt ist, durchläuft der Generator genau 2ⁿ - 1 Zustände, bis er wieder seinem Anfangszustand annimmt und der Zyklus von vorn beginnt. Dabei bezeichnet n die Länge der Registerkette, im abgebildeten Beispiel beträgt die Periode des Generators also 2¹⁶ - 1 = 65535.

Mit anderen Worten: Der Generator erzeugt innerhalb einer Periode genau 2ⁿ - 1 verschiedene n-Bit-Zahlen. Das sind bis auf eine Ausnahme alle möglichen mit n Bit darstellbaren Zahlen. Die Ausnahme ist, wie sich schnell überlegen läßt, die Zahl Null, denn der Null folgt stets wieder eine Null; dieser Zustand der Registerkette ist sozusagen stabil. Die Null darf demzufolge auch nicht als Startwert verwendet werden. Dagegen ist jede andere Zahl Bestandteil der 2ⁿ - 1 Takte dauernden Periode und kann als Startwert benutzt werden.

Die Reihenfolge, mit der die von Null verschiedenen Zahlen durch den Generator erzeugt werden, ist scheinbar zufällig, wenn auch durch das Generationsprinzip eindeutig bestimmt. Dies läßt sich besonders gut bei einer grafischen Ausgabe beobachten.

Dreh- und Angelpunkt des Generatorprinzips ist eine passende Rückkopplung. Auf die zugrundeliegenden Theorie soll an dieser Stelle nicht eingegangen werden; wer sich dennoch für die tieferen Zusammenhänge interessiert, kann mal unter den Stichworten "linear rückgekoppelte Schieberegister", "Maximallängenfolgen" und "primitive Polynome" nachschauen.

Solche geeigneten Rückkopplungen gibt es für jede Registerlänge n, wobei n - 1 jeweils das höchstwertigste in die Rückkopplung einfließende Bit bezeichnet. In der Tabelle am Ende dieses Textes ist für Registerlängen von 3 bis 16 Bit jeweils eine Rückkopplung angegeben, die für eine Programmierung besonders geeignet ist. Auf das Format der Darstellung wird im folgenden noch näher eingegangen.

Nun zur Umsetzung des Generators in einem Assemblerprogramm. Als Beispiel soll dazu zunächst die in Bild 1 dargestellte 16-Bit-Variante verwendet werden. Beschränkt man sich auf Registerlängen kleiner oder gleich 16 Bit, findet die Registerkette im Doppelregister HL Platz. In HL steht also stets die aktuelle Zufallszahl, aus der in jedem Schleifendurchlauf (Generatorschritt) der nächste Wert erzeugt wird.

Zunächst muß der Wert der Rückkoppelfunktion bestimmt werden, der dann Bit 0 der neuen Zufallszahl ergibt. Im Beispiel werden für die Rückkopplung nur Bits aus dem höherwertigen Byte verwendet, so daß auch nur das Register H betrachtet werden muß, was die ganze Sache etwas vereinfacht. Um nur die in der Rückkopplung verwendeten Bits von H zu erhalten, wird der Registerinhalt, nachdem er in den Akkumulator A geladen wurde, mit einem Rückkoppelbyte (0B4H) maskiert.

In dieser Maske sind genau die Bitstellen gleich Eins (markiert), die aus dem Register H in der Rückkoppelfunktion verwendet werden. Das Ergebnis im Akkumulator ist ein Byte, in dem alle nichtmarktierten Bits gleich Null sind und alle markierten Bits den korrespondierenden Bits des Registers H entsprechen. Da zusätzliche Null-Bits ohne Einfluß auf den Wert der Rückkopplung sind, kann das neue Bit 0 jetzt auch als Modulo-2-Addition aller 8 Bits des Akkumulators bestimmt werden.

Und genau das hat unser Prozessor aber im Prinzip bereits getan, sozusagen als Zugabe bei der AND-Operation, indem er nämlich die Parität des Ergebnisses bestimmt und in das P/V-Flag einträgt: Nach einer logischen Operation wie AND steht im P/V-Flag eine Eins, wenn die Anzahl der Einsen im Ergebnis gerade ist, sonst eine Null. Das ist bis auf eine Negation genau der neue Wert von Bit 0 der Registerkette.

Der Inhalt des P/V-Flags läßt sich nur als Sprungbedingung auswerten, günstiger für die nachfolgende Schiebeoperation ist aber ein Ergebnis im C-Flag. Um das zu erreichen, sind die dem AND folgenden zwei Befehle vorhanden. Dabei ist die Tatsache von Bedeutung, daß bei den logischen Operationen AND, OR und XOR das C-Flag gundsätzlich auf Null gesetzt wird.

Ist die Anzahl der Einsen im Ergebnis der AND-Operation gerade, dann ist das C-Flag bereits richtig gesetzt und es kann mit Bedingung PE (Parity even) sofort zur Verschiebeoperation gesprungen werden. Im anderen Fall wird zuvor das C-Flag noch negiert. Damit steht jetzt der richtige Wert der Rückkoppelfunktion im C-Flag und kann mittels einer zyklischen Linksverschiebung des Registers L in dessen Bit 0 übernommen werden.

Nach dieser Operation befindet sich im C-Flag das vormals höchstwertigste Bit des Register L und wird im folgenden durch die zyklische Linksverschiebung des Registers H als dessen niederwertigstes Bit übernommen. Damit ist der Generatorschritt abgeschlossen; im Register HL steht nun die neue Zufallszahl.

Mit nur 6 Maschinenbefehlen ist die Realisierung also überaus einfach und effektiv.

- Generatorschritt (16 Bit) -

;
; HL = alte Zufallszahl
      LD A,H
      AND 0B4H   ;Rückkoppel-Maske H (RKM H)
      JP PE,S1
      CCF        ;C-Flag negieren
S1:   RL L
      RL H       ;HL = neue Zufallszahl

Was jetzt noch fehlt, um den Zufallsgenerator zu testen, ist eine Schleife, die den Generatorschritt in einer bestimmten Anzahl von Durchläufen jeweils einmal ausführt und die erzeugte Zufallszahl in irgendeiner Weise weiterverarbeitet.

Dabei ist noch sicherzustellen, daß beim Start des Generators im Register HL eine von Null verschiedene Zahl steht und die Zufallszahl bei der Verarbeitung nicht verändert wird. Die Verwendung der Zufallszahl besteht in den hier gezeigten Programmbeispielen jeweils darin, einen Teil des Bildschirms "zufällig" mit Punkten zu füllen.

Dazu wird die erzeugte Zufallszahl in zwei Teile zerlegt, die jeweils die x- und y-Koordinaten des zu setzenden Punktes bilden. Die niederwertigen 8 Bit (Register L) entsprechen der y-Koordinate, die höherwertigen 8 Bit (Register H) der x-Koordinate. Der Nullpunkt ist dabei - abweichend von den üblichen Grafikkoordinaten - die linke obere Ecke.

Natürlich läßt sich für diesen Zweck auch das CAOS-Unterprogramm 30h verwenden, aber damit es schneller geht, ist das hier direkt programmiert. Auf eine ausführliche Beschreibung dieses Programmteils soll an dieser Stelle verzichtet werden; im Quelltext sind Kommentare enthalten, die das Verständnis ermöglichen sollten.

In der 16-Bit-Variante wird ein 256 mal 256 Punkte großes Quadrat auf dem Bildschirm mit Punkten gefüllt. Das ist noch nicht der gesammte Pixel-RAM, aber eine entsprechende Erweiterung ist wohl nicht allzu schwer zu programmieren. Die äußere Programmschleife wird genau 65535-mal durchlaufen, was genau der Periode des Generators entspricht.

Wer genau hinsieht, wird feststellen, daß der Punkt (0,0) in der linken oberen Ecke nicht gesetzt wird, denn dieser entspricht dem Zustand HL=0, der wie oben beschrieben nicht auftritt. Neben dem Setzen der Punkte auf dem Bildschirm ist in gleicher Weise auch das Rücksetzen und das Negieren möglich. Dazu ist an der gekennzeichneten Stelle im Quelltext die Verknüpfungsoperation der Bitmaske im Register A mit dem Byte aus dem IRM zu modifizieren.

Wie oben bereits gesagt, läßt sich der Generator auch für andere Registerlängen realisieren. Dabei tritt der Fall auf, daß sich die Bitstellen für die Rückkopplung nicht alle in einem Byte (also entweder im Register H oder im Register L) befinden, sondern auf beide 8-Bit-Register verteilen. Für die Registerlängen 9, 10 und 12 läßt sich das nicht vermeiden.

Die Bestimmung des Wertes der Rückkoppelfunktion ist dann etwas zu modifizieren, was am Beispiel eines 12 Bit langen Generators gezeigt werden soll.

Zunächst werden wie im ersten Beispiel die benötigten Bits des Registers H mit der Maske RKM H ausgewählt. Das Ergebnis wird dann erst einmal im Register C zwischengespeichert. Die bereits mitbestimmte Parität wird an dieser Stelle nicht benötigt. Danach erfolgt die Maskierung des Registers L mit der Maske RKM L. Die folgende Operation (XOR C) verknüpft die beiden maskierten Bytes bitweise und bildet so zunächst einmal Teilsummen von jeweils zwei Bits (wie bei der normalen Addition läßt sich auch die Modulo-2-Addition beliebig in Teilsummen zerlegen, d.h. die Reihenfolge der Addition der einzelnen Bits spielt keine Rolle).

Da XOR eine logische Funktion ist, wird auch hier gleich wieder die Parität des Ergebnisses bestimmt und im P/V-Flag eingetragen (genaugenommen enthält das P/V-Flag nach der Operation XOR C also die Parität der 16 Bit in den Registern A und C). Ebenso ist das C-Flag nach dieser Operation grundsätzlich auf Null gesetzt. Damit ist der gleiche Zustand erreicht wie nach AND im obigen 16-Bit-Beispiel und es kann in gleicher Weise fortgefahren werden.

Eine weitere Modifikation ist der letzte Befehl des Generatorschritts. Hier wird das dem höchstwertigsten folgende Bit der Registerkette auf Null gesetzt. Damit wird erreicht, daß alle nicht benötigten Bits des Registerpaares HL immer Null sind und der Inhalt von HL somit als 12-Bit-Zufallszahl verwendet werden kann.

- Generatorschritt (12 Bit) -

;
; HL = alte Zufallszahl (12 Bit)
      LD A,H
      AND 08H    ;Rückkoppel-Maske H (RKM H)
      LD C,A
      LD A,L
      AND 29H    ;Rückkoppel-Maske L (RKM L)
      XOR C
      JP PE,S1
      CCF
S1:   RL L
      RL H
;
      RES 4,H    ;HL = neue Zufallszahl (12 Bit)

Die folgende Tabelle nun zeigt für Registerlängen von 3 bis 16 Bit jeweils eine geeignete Rückkopplung in Form der Rückkoppelmasken RKM H und RKM L, die Operanden für den RES-Befehl (letzter Befehl im 12-Bit-Beispiel) sowie die jeweils erzeugte Periode der Zufallszahlenfolge. Mit diesen Parametern können die Beipspielprogramme modifiziert werden, um einen Generator der jeweiligen Registerlänge zu programmieren.

n	RKM H	RKM L	RES	Periode
16	B4h	-	-	65.535
15	60h	-	7,H	32.767
14	27h	-	6,H	16.383
13	1Bh	-	5,H	8.191
12	08h	29h	4,H	4.095
11	05h	-	3,H	2.047
10	02h	04h	2,H	1.023
9	01h	08h	1,H	511
8	-	8Eh	0,H	255
7	-	44h	7,L	127
6	-	21h	6,L	63
5	-	12h	5,L	31
4	-	09h	4,L	15
3	-	05h	3,L	7

Bei Generatoren mit Registerlängen bis zu 8 Bit kann auf die Verwendung des Registers H verzichtet werden, was zu einer Vereinfachung des Programmtextes führt. Für einige markante Fälle bezüglich der Registerlänge n sind im Paket ZUFALL.PMA vollständige Quelltexte enthalten.

Der visuelle Effekt auf dem Bildschirm ist sicherlich nur bei den größeren Registerlängen interessant. Die Variaten mit n kleiner oder gleich 8 erzeugen - bedingt durch das gewählte Verfahren der Koordinatenzuordnung - jeweils nur eine mehr oder weniger lange Linie am linken Bildschirmrand.

Viel Spaß beim Experimentieren!

Beispiele:

zufall08.asm

Assemblerquelltext des Demo-Programms für ein Register der Länge 8

 

zufall12.asm

Assemblerquelltext des Demo-Programms für ein Register der Länge 12

 

zufall15.asm

Assemblerquelltext des Demo-Programms für ein Register der Länge 15

 

zufall16.asm

Assemblerquelltext des Demo-Programms für ein Register der Länge 16