Exercise 2.6Z: PN Generator of Length 3

• Return to book

PN-Generator mit  $L = 3$

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}\cdot ( 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.

• Wir verweisen hier auch auf das Lernvideo  Erläuterung der PN-Generatoren an einem Beispiel.

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 zur Zeit  $\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

PN–Generator mit Oktalkennung $15$

(1)  Es handelt sich um eine M-Sequenz mit  $L= 3$.  Daraus folgt $P= 2^L - 1 \hspace{0.15cm}\underline{= 7}$.

(2)  Wir bezeichnen die Zellen von links nach rechts mit  $S_1$,  $S_2$  und  $S_3$.  Dann gilt:

• $S_2(\nu) = S_1(\nu - 1)$,
• $S_3(\nu) = S_2(\nu - 1)$,
• $S_1(\nu) = S_2(\nu - 1) \ {\rm mod } \ S_3(\nu - 1)$.

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

• Zum Taktzeitpunkt  $\nu = 7$  ergibt sich die gleiche Speicherbelegung wie zum Zeitpunkt  $\nu = 0$.
• Daraus folgt  $ {P = 7}$  und die Folge lautet ab  $\nu = 1$  entsprechend dem Lösungsvorschlag 3 :

$$\langle z_\nu \rangle = 1 \ 1 \ 0 \ 0 \ 1 \ 0 \ 1 \ 1 \ 1 \ 0 \ 0 \ 1 \ 0 \ 1 \ 1 \ \text{...}$$

• Dagegen beschreibt Vorschlag 1 die M-Sequenz des PN-Generators mit Länge  $L=4$  und Kennung  $(31)$   ⇒   Periodenlänge ist  $P= 15$.
• Beim Vorschlag 2 ist die Periodenläng  $P= 4$  zu kurz.

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

(3)  Richtig sind die Lösungsvorschläge 2, 3 und 4:

• 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.

PN–Generator mit Oktalkennung  $13$

(4)  In nebenstehender Tabelle ist die Entstehung der PN–Folge beim reziproken Polynom  $G_{\rm R}(D)$  eingetragen. Man erkennt, dass der Lösungsvorschlag 2 zutrifft:

• 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 zwei Zeittakte verschobene Version der Ausgangsfolge von  $(15)$.
• Dagegen ist im (richtigen) 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.