Erzeugung von diskreten Zufallsgrößen
Pseudozufallsgrößen
Eine Möglichkeit zur Erzeugung einer binären Zufallsfolge $〈z_{\rm ν}〉 ∈$ {0, 1} mit guten statistischen Eigenschaften bieten die so genannten Pseudozufallsgeneratoren, auch bekannt unter dem Namen PN-Generatoren, wobei „PN” für Pseudonoise steht. Diese besitzen folgende Eigenschaften:
- Die durch einen solchen Generator erzeugte Binärfolge ist im strengen Sinne nicht stochastisch, sondern weist periodische und damit deterministische Eigenschaften auf.
- Ist die Periodenlänge $P$ jedoch hinreichend groß, so erscheint die Folge für einen Betrachter als zufällig mit für viele Anwendungsfälle hinreichend guten statistischen Eigenschaften.
- Der Vorteil eines Pseudozufallsgenerators gegenüber einer „echten” stochastischen Quelle ist, dass die Zufallsfolge bei Kenntnis einiger weniger Parameter reproduzierbar ist.
Aus der letzten Eigenschaft heraus ergeben sich auch die wichtigsten Anwendungen der Pseudonoise-Generatoren:
- zum einen die Fehlerhäufigkeitsmessung bei der Digitalsignalübertragung,
- zum zweiten zur Bandspreizung bei CDMA (Code Division Multiple Access).
Bei einem solchen Spread Spectrum System wird das Sendesignal mit einer binären Zufallsfolge moduliert, deren Symbolfolgefrequenz deutlich größer als die Bitfrequenz ist. Dadurch bietet sich die Möglichkeit der Mehrfachausnutzung von Kanälen. Da am Empfänger die gleiche Folge phasenrichtig zugesetzt werden muss, ist auch hier der Einsatz von reproduzierbaren PN-Sequenzen üblich.
Ausführliche Informationen zu den Bandspreizverfahren finden Sie im Buch „Beispiele von Nachrichtensysteme” im Kapitel 4: UMTS – Universal Mobile Telecommunications System.
Realisierung von PN-Generatoren
Pseudozufallsgeneratoren werden meist durch rückgekoppelte Schieberegister realisiert, wobei zu jedem Taktzeitpunkt der Inhalt des Registers um eine Stelle nach rechts geschoben wird (siehe Grafik). Für das aktuell erzeugte Symbol gilt mit $g_l ∈$ {0, 1} und $l =$ 1, ... , $L$–1: $$z_\nu = (g_1\cdot z_{\nu-1}+g_2\cdot z_{\nu-2}+...+g_l\cdot z_{\nu-l}+...+g_{L-1}\cdot z_{\nu-L+1}+ z_{\nu-L})\hspace{0.1cm} \rm mod \hspace{0.2cm}2.$$
Die zu vorherigen Zeitpunkten generierten Binärwerte $z_{ν–1}$ bis $z_{ν–L}$ sind in den Speicherzellen des Schieberegisters abgelegt. Die Koeffizienten $g_1 ... g_{L–1}$ sind ebenfalls Binärwerte, wobei eine „1” eine Rückkopplung an der entsprechenden Stelle kennzeichnet und eine „0” keine Rückführung.
Die Modulo-2-Addition kann zum Beispiel durch eine XOR-Verknüpfung realisiert werden: $$(x + y)\hspace{0.1cm} \rm mod\hspace{0.1cm}2 = \it x\hspace{0.1cm}\rm XOR\hspace{0.1cm} \it y = \left\{\begin{array}{*{2}{c}} 0 & \rm falls\hspace{0.1cm} \it x= y,\\ 1 & \rm falls\hspace{0.1cm} \it x\neq y. \\ \end{array} \right.$$
Voraussetzung für die Entstehung einer PN-Folge ist, dass nicht alle Speicherelemente mit Nullen vorbelegt sind, da sonst die Modulo-2-Addition immer nur das Symbol „0” erzeugen würde.
Die statistischen Eigenschaften der erzeugten Zufallsfolge werden im Wesentlichen durch den Grad L und die Rückführungskoeffizienten $g_l$ (mit $l =$ 1, ... , $L$–1) bestimmt.
Zur Kennzeichnung unterschiedlicher PN-Generatoren verwendet man in der Literatur alternativ:
- die sogenannten Generatorpolynome von der Art
$$G(D) = g_L\cdot D^L+g_{L-1}\cdot D^{L-1}+...+g_1\cdot D+g_0 .$$
- Hierbei ist stets $g_0 = g_L =$ 1 zu setzen und $D$ ein formaler Parameter, der eine Verzögerung um einen Takt angibt. $D^L$ kennzeichnet dann eine Verzögerung um $L$ Takte.
- die Oktaldarstellung der Binärzahl $(g_L ... g_2 g_1 g_0).$ Wichtig ist, dass hierbei die Rückkopplungskoeffizienten – von rechts mit $g_0$ beginnend – zu Tripeln zusammengefasst und diese oktal (0 ... 7) geschrieben werden.
Das Generatorpolynom $D^4 + D^3 + 1$ gehört zu einem Schieberegister vom Grad $L =$ 4 mit der Oktaldarstellung $(g_4 g_3 g_2 g_1 g_0) = (11001)_{\rm bin} = (31)_{\rm oct}. $
Folgen maximaler Länge (M-Sequenzen)
Sind nicht alle $L$ Speicherzellen des Schieberegisters mit Nullen vorbelegt, so entsteht stets eine periodische Zufallsfolge $〈z_ν〉$. Die Periodenlänge $P$ dieser Folge hängt im starken Maße von den Rückkopplungskoeffizienten ab. Für jeden Grad $L$ gibt es zumindest eine Konfiguration mit maximaler Periodenlänge $$P_{max} = \rm 2^{\it L}-\rm 1.$$ Eine solche PN-Folge bezeichnet man auch oft als M-Sequenz, wobei das „M” für „Maximal“ steht. Eine M-Sequenz kann man daran erkennen, dass das Generatorpolynom $G(D)$ primitiv ist. Wie im Buch Kanalcodierung noch ausführlich dargelegt werden wird, bezeichnet man ein Polynom $G(D)$ vom Grad $L$ dann als primitiv, wenn folgende Bedingung erfüllt ist: $$\frac{(D^n+\rm 1)}{\it G(D)} \neq 0\hspace{0.5cm} {\rm f\ddot{u}r}\hspace{0.5cm}\it n<P_{max} = \rm 2^{\it L}-\rm 1.$$
Ein Schieberegister vom Grad $L =$ 4 mit Oktalkennung (31) und Generatorpolynom $G(D) = D^4 + D^3 + 1$ führt zu einer Folge maximaler Länge: $P_{\rm max} = 2^4 – 1 = 15.$ Der mathematische Nachweis hierfür ist aufwändig:
- Man muss anhand obiger Polynomdivision für $n =$ 1, ... , 14 zeigen, dass der Quotient stets ungleich 0 ist. Erst die Division $(D^{15} + 1)/G(D)$ liefert ein Ergebnis ohne Rest.
- Hierbei ist zu berücksichtigen, dass in der Modulo-2-Algebra +1 und –1 identisch sind.
In der Tabelle sind einige PN-Generatoren maximaler Länge bis zum Grad $L =$ 31 aufgeführt. Die Auswahl ist auf Konfigurationen mit nur einer Anzapfung – also mit zwei Rückführungen – beschränkt. Das bedeutet, dass die zugehörigen Polynome jeweils aus drei Summanden bestehen. Für Applikationen, die eine hohe Geschwindigkeit erfordern, sind solche Generatoren sehr nützlich.
