Schieberegistern mit Rückkoppelung durch Übertrag sind linearen Schieberegistern mit Rückkoppelung sehr ähnlich. Während bei letzteren die Rückkoppelung durch XOR-Verknüpfung entsteht wird bei der hier behandelten Methode die Summe der Bits zu einem weiteren Register, im folgenden "Carry" genannt addiert (siehe auch [1]). Das Carry modulo 2 liefert das neue Bit, welches links in das Schieberegister hineingeschoben wird. Danach wird das neue Carry gebildet, indem es um eine Position nach rechts geschoben wird.
Die zugehörigen Gleichungen lauten:
mit:
Die Schieberichtung geht dabei von links nach rechts, also Bit 1 nach Bit 2, Bit 3 nach Bit 4, Bit n-1 nach Bit n usw. Wie aus der Grafik ersichtlich ist, müssen nicht alle Bits zur Summenbildung herangezogen werden. Aus der Berechnung der maximalen Periode der Zufallszahlen erhält man die Anordnung der Abgriffe. Als Maximale Periode nimmt man Zahlen, welche 2 als primitive Wurzel haben, z.B. 2,5,11,13,19,1061,3083,4373,9949.(diese Zahlen werden in der Literatur [1] ausführlich in tabellarischer Form aufgeführt)
Hier wären Bit 1, Bit 2, Bit 3, Bit 4, Bit 6, Bit 7, Bit 9, Bit 10, und Bit 13 für die Rückkoppelung zu wählen. Die Größe des Carrys muß dabei mindestens
Da das Prinzip des Generators sehr einfach ist, kann bei seiner Erstellung auf aufwendige mathematische Formeln zur Bestimmung der "Pseudozufälligkeit" der Zahlen verzichtet werden. In der Regel bleibt der Generator bei schlecht gewählten Abnahmepunkten in einer endlosen Folge von Nullen oder Einsen hängen, sofern eine hinreichend große Anzahl von Durchläufen stattgefunden hat.
Beispiele für gute Abnahmestellen:
(3,2) (32,6,3,2) (32,19,17,2) (64,3,2,1) (64,45,28,2) (96,15,5,2) (96,54,15,2) (128,43,42,2) (128,97,68,2)
Bei der Realisierung wurde ein 32Bit großes Register mit dem Zweck eine sehr große Periode zu erreichen gewählt. Um die erhaltenen Werte bei den Späteren Tests in einem praktikablen Rahmen zu erhalten werden immer die Höchsten 8Bits abgegriffen. Dabei hat sich bei der Bestimmung der Entropie (Markoff Quelle) gezeigt, daß nur jede achte Zufallszahl zu einem optimalen Ergebnis führt. Aufgrund der Abnahmestellen (32,6,3,2) ergibt sich eine Periode
// Name: LSFRC.cpp (linear feedback shift register with carry)
// Aufgabe:
// Implementierung eines Schieberegister mit Rückkoppelung durch
// übertrag. Damit die erzeugten Pseudozufallsbits ausgewertet werden
// können, werden aus den Ausgabebits Zahlen zwischen 0 und 255 erzeugt.
// Ersteller: Sascha Heinisch
#include <iostream.h>
#include <conio.h>
#include <fstream.h>
int Bilde_zufalls_zahl()
{
static unsigned long wert = 3206890276;
static unsigned long carry =0;
static unsigned long summe =0;
static int t;
for (t=0;t<=7;t++) // 8 Durchläufe um 8Bit zu erhalten
{
summe=0; // Summe auf Null setzen
if (wert & 0x00000001) summe++; // ##########################
if (wert & 0x04000000) summe++; // Summieren der rück-
if (wert & 0x20000000) summe++; // geführten Bits
if (wert & 0x40000000) summe++; // ##########################
summe = summe + carry; // neue Summe berechnen
carry = summe >> 1; // Summe / 2 ergibt neues Carry
wert = wert >> 1; // Wert nach rechts shiften
summe = summe % 2; // Summe Modulo 2, falls ungerade
if (summe) wert = wert | 0x80000000; // neues Bit in Wert setzen
}
return (int) (wert & 0x0FF); // Bit Integer zurückgeben
}
void main()
{
ofstream output;
unsigned long i,anz;
clrscr(); // Bildschirm Löschen
cout>anz; // Eingabe Anzahl Zufallszahlen
cout<<"O.K."<<endl;
output.open("test.dat"); // Datei öffnen
for (i=0;i<anz;i++)
{
output<<Bilde_zufalls_zahl()<<endl; // Schreibe Zufallszahlen
}
output.close(); // Datei schließen
}