Exercise 2.6Z: PN Generator of Length 3

• Return to book

Nebenstehende Skizze zeigt einen PN-Generator der Länge $L = 3$ mit dem Generatorpolynom

$$G( D) = D^{\rm 3} + D^{\rm 2} + \rm 1$$

und somit der Oktalkennung ($g_3 \ g_2 \ g_1 \ g_0$) = $(1 \ 1 \ 0 \ 1)_{\rm bin} = (15)_{\rm oct}$.

Das zugehörige reziproke Polynom $$G_{\rm R}(D) = D^{\rm 3} ( D^{\rm -3} + D^{\rm -2} + 1) = D^{\rm 3} + D^{\rm 1} + \rm 1$$

hat die Oktalkennung $(1 \ 0 \ 1 \ 1)_{\rm bin} = (13)_{\rm oct}$.

• Zum Startzeitpunkt seien die drei Speicherzellen mit den Binärwerten $1$, $0$ und $1$ vorbelegt.
• Beide Anordnungen erzeugen eine M-Sequenz.

Hinweise:

• Die Aufgabe gehört zum Kapitel Erzeugung von diskreten Zufallsgrößen.
• Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
• Wir möchten Sie gerne auch auf das folgende Lernvideo hinweisen:

Verdeutlichung der PN-Generatoren am Beispiel ''L'' = 4

Fragebogen

1

Wie groß ist die Periodenlänge der Konfiguration $(15)$?

$P \ = $

2

Ermitteln Sie die Ausgangsfolge $〈z_ν\rangle$ für die Zeitpunkte $1$, ... , $P$. Wie lauten die ersten 15 Binärwerte der Ausgangsfolge? Hinweis: Bezeichnen Sie die Zellen von links nach rechts mit $S_1$, $S_2$ und $S_3$. Ausgegeben wird der Wert $z_ν$, der zum Zeitpunkt $\nu$ in die Speicherzelle $S_1$ eingetragen wird.

	$1\ 0 \ 0 \ 1 \ 1 \ 0 \ 1 \ 0 \ 1 \ 1 \ 1 \ 1 \ 0 \ 0 \ 0$ . . .
	$1 \ 0 \ 0 \ 1 \ 1 \ 0 \ 0 \ 1 \ 1 \ 0 \ 0 \ 1 \ 1 \ 0 \ 0 $ . . .
	$1 \ 1 \ 0 \ 0 \ 1 \ 0 \ 1 \ 1 \ 1 \ 0 \ 0 \ 1 \ 0 \ 1 \ 1$ . . .
	$0 \ 0 \ 1 \ 1 \ 1 \ 0 \ 1 \ 0 \ 0 \ 1 \ 1 \ 1 \ 0 \ 1 \ 0 $. . .

3

Welche der folgenden Aussagen treffen für jede M-Sequenz zu?

	Die Anzahl der Nullen und Einsen ist gleich.
	In jeder Periode gibt es eine Eins mehr als Nullen.
	Die maximale Anzahl aufeinander folgender Einsen ist $L$.
	Die Folge $1 \ 0 \ 1 \ 0 \ 1 \ 0 $ . . . ist nicht möglich.

4

Betrachten Sie nun die reziproke Anordnung $(13)$. Wie lauten hier die ersten 15 Binärwerte der Ausgangsfolge bei gleicher Anfangsbelegung?

	$0 \ 0 \ 0 \ 1 \ 1 \ 1 \ 1 \ 0 \ 1 \ 0 \ 1 \ 1 \ 0 \ 0 \ 1 $ . . .
	$0 \ 0 \ 1 \ 1 \ 1 \ 0 \ 1 \ 0 \ 0 \ 1 \ 1 \ 1 \ 0 \ 1 \ 0 $ . . .
	$0 \ 0 \ 1 \ 0 \ 1 \ 1 \ 1 \ 0 \ 0 \ 1 \ 0 \ 1 \ 1 \ 1 \ 0 $ . . .

Musterlösung

Solution

(1)  Es handelt sich um eine M-Sequenz mit L = 3. Daraus folgt P = 2^L - 1 = 7.

(2)  Wir bezeichnen die Zellen von links nach rechts mit S₁, S₂ und S₃. Dann gilt:

• S₂(ν) = S₁(ν – 1),
• S₃(ν) = S₂(ν – 1),

• S₃(ν) = S₂(ν – 1) mod S₃(ν – 1).

Das Ergebnis ist in der ersten Zeile obiger Tabelle (rot markiert) eingetragen:

Zum Taktzeitpunkt ν = 7 ergibt sich die gleiche Speicherbelegung wie zum Zeitpunkt ν = 0. Daraus folgt P = 7 und die Folge ist ab ν = 1: 〈z_ν〉 = 〈 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 ... 〉.

Vorschlag 3 ist der richtige. Vorschlag 1 beschreibt die M-Sequenz des PN-Generators mit Länge L = 4 und Kennung (31); die Periodenlänge ist P = 15. Beim Vorschlag 2 ist P = 4.

Der letzte Vorschlag schließlich hätte zwar die gewünschte Periodenlänge P = 7, aber aus der Modulo-2-Addition von S₂ = 0 und S₃ = 1 (für ν = 0) folgt zum nächsten Zeitpunkt (ν = 1) zwingend: S₁ = 1. Diese Eigenschaft zeigt die Folge 4 nicht.

(3)  Die maximale Anzahl aufeinander folgender Einsen ist L (nämlich dann, wenn in allen L Speicherzellen eine Eins steht). Es ist dagegen nicht möglich, dass alle Speicherzellen mit Nullen belegt sind. Deshalb gibt es stets eine Eins mehr als Nullen.

Die Periodenlänge der letzten Folge beträgt P = 2. Bei einer M-Sequenz gilt dagegen P = 2^L – 1. Für keinen Wert von L ist P = 2 möglich.

Richtig sind somit die Lösungsvorschläge 2, 3 und 4.

(4)  Auch bei der reziproken Anordnung muss die Periodenlänge P = 7 gelten, so dass der Vorschlag 1 (mit P = 15) ausscheidet. Der Vorschlag 3 ist nur eine um 2 Zeittakte verschobene Version der Ausgangsfolge von (15). Dagegen ist im zweiten Vorschlag die Inverse von .... 1 1 0 0 1 0 1 ... – also die Folge ... 1 0 1 0 0 1 1 ... – enthalten, wenn auch mit einem Phasenversatz.

In der unteren Tabelle ist die Entstehung der PN–Folge beim reziproken Polynom G_R(D) eingetragen. Die Tabelle bestätigt die Richtigkeit von Lösungsvorschlag 2.