Aufgabe 3.6Z: Übergangsdiagramm bei 3 Zuständen

Zustandsübergangsdiagramm für $m = 3$ (unvollständig)

Im Zustandsübergangsdiagramm eines Codierers mit Gedächtnis $m$ gibt es $2^m$ Zustände. Das dargestellte Diagramm mit acht Zuständen beschreibt deshalb einen Faltungscoder mit dem Gedächtnis $m = 3$.

Normalerweise bezeichnet man die Zustände mit $S_0, \ \text{...} \ , \ S_{\mu}, \ \text{...} \ , \ S_7$, wobei der Index $\mu$ aus der Belegung des Schieberegisters (Inhalt von links nach rechts: $u_{i–1}, u_{i–2}, u_{i–3})$ festgelegt ist:

$$\mu = \sum_{l = 1}^{m} \hspace{0.1cm}2\hspace{0.03cm}^{l-1} \cdot u_{i-l} \hspace{0.05cm}.$$

Der Zustand $S_0$ ergibt sich deshalb für den Schieberegisterinhalt „$000$”, der Zustand $S_1$ für „$100$” und der Zustand $S_7$ für „$111$”.

In obiger Grafik sind allerdings für die Zustände $S_0, \, \text{...} \, , \, S_7$ Platzhalter names $\mathbf{A}, \, \text{...} \, , \, \mathbf{H}$ verwendet. In den Teilaufgaben (1) und (2) sollen Sie klären, welcher Platzhalter für welchen Zustand steht.

Bei Faltungscodierer der Rate $1/n$, die hier ausschließlich betrachtet werden sollen, gehen von jedem Zustand $S_{\mu}$ zwei Pfeile ab, ein roter für das aktuelle Informationsbit $u_i = 0$ und ein blauer für $u_i = 1$. Auch deshalb ist das gezeigte Zustandsübergangsdiagramm nicht vollständig.

Zu erwähnen ist weiterhin:

Bei jedem Zustand kommen auch zwei Pfeile an, wobei diese durchaus gleichfarbig sein können.
Neben den Pfeilen stehen üblicherweise noch die $n$ Codebits. Auch hierauf wurde hier verzichtet.

Hinweise:

Die Aufgabe bezieht sich auf die beiden ersten Seiten des Kapitels Codebeschreibung mit Zustands– und Trellisdiagramm.
In der Aufgabe 3.7Z werden zwei Faltungscodes mit Gedächtnis $m = 3$ untersucht, die beide durch das hier analysierte Zustandsübergangsdiagramm beschrieben werden können.
Bitte bei allen Fragen den ensprechenden Index eingeben,
Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

${\rm Zustand} \ \mathbf{A} \ ⇒ \ {\rm Index} \ {\mu} \ = \ $

${\rm Zustand} \ \mathbf{F} \ ⇒ \ {\rm Index} \ {\mu} \ = \ $

${\rm Zustand} \ \mathbf{B} \ ⇒ \ {\rm Index} \ {\mu} \ = \ $

${\rm Zustand} \ \mathbf{C} \ ⇒ \ {\rm Index} \ {\mu} \ = \ $

${\rm Zustand} \ \mathbf{D} \ ⇒ \ {\rm Index} \ {\mu} \ = \ $

${\rm Zustand} \ \mathbf{E} \ ⇒ \ {\rm Index} \ {\mu} \ = \ $

${\rm Zustand} \ \mathbf{G} \ ⇒ \ {\rm Index} \ {\mu} \ = \ $

${\rm Zustand} \ \mathbf{H} \ ⇒ \ {\rm Index} \ {\mu} \ = \ $

${\rm Von \ {\it S}_{\rm 1} \ zum \ Zustand \ mit \ Index \ {\mu}} \ = \ $

${\rm Von \ {\it S}_{\rm 3} \ zum \ Zustand \ mit \ Index \ {\mu}} \ = \ $

${\rm Von \ {\it S}_{\rm 5} \ zum \ Zustand \ mit \ Index \ {\mu}} \ = \ $

${\rm Von \ {\it S}_{\rm 7} \ zum \ Zustand \ mit \ Index \ {\mu}} \ = \ $

Musterlösung

(1) Der Platzhalter $\mathbf{A}$ steht für den Zustand $S_0$ ⇒ $u_{i–1} = 0, \ u_{i–2} = 0, \ u_{i–3} = 0$. Dies ist der einzige Zustand $S_{\mu}$, bei dem man durch das Infobit $u_i = 0$ (roter Pfeil) im gleichen Zustand $S_{\mu}$ bleibt.

Zusammenhang zwischen Platzhalter und Zuständen

Vom Zustand $S_7$ ⇒ $u_{i–1} = 1, \ u_{i–2} = 1, \ u_{i–3} = 1$ kommt man mit $u_i = 1$ (blauer Pfeil) auch wieder zum Zustand $S_7$. Einzugeben waren also für $\mathbf{A}$ der Index $\underline{\mu = 0}$ und für $\mathbf{F}$ der Index $\underline{\mu = 7}$.

(2) Ausgehend vom Zustand $\mathbf{A} = S_0$ kommt man entsprechend der Ausgangsgrafik im Uhrzeigersinn mit den roten Pfeilen $(u_i = 0)$ bzw. den blauen Pfeilen $(u_i = 1)$ zu folgenden Zuständen:

$u_{i–3} = 0, \ u_{i–2} = 0, \ u_{i–1} = 0, \ u_i = 1 ⇒ s_{i+1} = \mathbf{B} = S_1$,
$u_{i–3} = 0, \ u_{i–2} = 0, \ u_{i–1} = 1, \ u_i = 0 ⇒ s_{i+1} = \mathbf{C} = S_2$,
$u_{i–3} = 0, \ u_{i–2} = 1, \ u_{i–1} = 0, \ u_i = 1 ⇒ s_{i+1} = \mathbf{D} = S_5$,
$u_{i–3} = 1, \ u_{i–2} = 0, \ u_{i–1} = 1, \ u_i = 1 ⇒ s_{i+1} = \mathbf{E} = S_3$,
$u_{i–3} = 0, \ u_{i–2} = 1, \ u_{i–1} = 1, \ u_i = 1 ⇒ s_{i+1} = \mathbf{F} = S_7$,
$u_{i–3} = 1, \ u_{i–2} = 1, \ u_{i–1} = 1, \ u_i = 0 ⇒ s_{i+1} = \mathbf{G} = S_6$,
$u_{i–3} = 1, \ u_{i–2} = 1, \ u_{i–1} = 0, \ u_i = 0 ⇒ s_{i+1} = \mathbf{H} = S_4$,
$u_{i–3} = 1, \ u_{i–2} = 0, \ u_{i–1} = 0, \ u_i = 0 ⇒ s_{i+1} = \mathbf{A} = S_0$.

Einzugeben waren also die Indizes $\mu$ in der Reihenfolge 1, 2, 5, 3, 6, 4. Die Grafik zeigt den Zusammenhang zwischen den Platzhaltern und den Zuständen $S_{\mu}$.

(3) Vom Zustand $S_1$ ⇒ $u_{i–1} = 1, \ u_{i–2} = 0, \ u_{i–3} = 0$ kommt man mit $u_i = 0$ (roter Pfeil) zum Zustand $S_2$. Dagegen landet man mit $u_i = 1$ (blauer Pfeil) beim Zustand $S_3$ ⇒ $u_{i–1} = 1, \ u_{i–2} = 1, \ u_{i–3} = 0$.

Zustandsübergangsdiagramm mit $2^3$ Zuständen

Nebenstehende Grafik zeigt das Zustandsübergangsdiagramm mit allen Übergängen. Aus diesem kann abgelesen werden:

Vom Zustand $S_3$ kommt man mit $u_i = 0$ zum Zustand $S_6$.
Vom Zustand $S_5$ kommt man mit $u_i = 0$ zum Zustand $S_2$.
Vom Zustand $S_7$ kommt man mit $u_i = 0$ zum Zustand $S_6$.

Einzugeben waren also die Indizes der Reihenfolge 3, 6, 2, 6.