Aufgaben:Exercise 3.7Z: Which Code is Catastrophic?

• Return to book

Codierer für $m = 3$und Zustandsübergangsdiagramm

Die nebenstehende Grafik zeigt

• zwei unterschiedliche Coder A und Coder B, jeweils mit dem Gedächtnis $m = 3$ (oben),
• zwei Zustandsübergangsdiagramme, bezeichnet mit Diagramm 1 und Diagramm 2 (unten).

In der letzten Teilaufgabe sollen Sie entscheiden, welches Diagramm zum Coder A gehört und welches zum Coder B.

Zunächst werden die drei Übertragungsfunktionen

• $G(D) = 1 + D + D^2 + D^3$,
• $G(D) = 1 + D^3$, und
• $G(D) = 1 + D + D^3$

analysiert und anschließend die Ausgangssequenzen $\underline{x}$ unter der Voraussetzung

$$\underline{u}= \underline{1}= (1, 1, 1, \text{...} \hspace{0.05cm}) \hspace{0.15cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.15cm} U(D)= \frac{1}{1+D}$$

berechnet. Diese Übertragungsfunktionen stehen im direkten Zusammenhang mit den skizzierten Codierern.

• Desweiteren ist noch zu klären, welcher der beiden Codes katastrophal ist:
• Von einem solchen spricht man dann, wenn eine endliche Anzahl von Übertragungsfehlern zu unendlich vielen Decodierfehlern führt.

Hinweise:

• Die Aufgabe gehört zum Kapitel Codebeschreibung mit Zustands– und Trellisdiagramm.
• Bezug genommen wird insbesondere auf die Abschnitte Zustandsdefinition für ein Speicherregister sowie Darstellung im Zustandsübergangsdiagramm.
• Angegeben werden noch zwei Polynomprodukte in ${\rm GF}(2)$:

$$(1+D) \cdot (1+D^2) = 1+D +D^2+D^3\hspace{0.05cm},$$

$$(1+D) \cdot (1+D+D^2) = 1+D^3\hspace{0.05cm}.$$

Fragebogen

1

Welche Ausgangssequenz $\underline{x}$ ergibt sich für $\underline{u} = \underline{1}, \ G(D) = 1 + D + D^2 + D^3$?

	$\underline{x} = (1, \, 0, \, 0, \, 1, \, 1, \, 1, \, \text{...} \hspace{0.05cm})$,
	$\underline{x} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \, \text{...} \hspace{0.05cm})$,
	$\underline{x} = (1, \, 1, \, 1, \, 0, \, 0, \, 0, \, \text{...} \hspace{0.05cm})$.
	Die Ausgangsfolge $\underline{x}$ ist zeitlich begrenzt.

2

Welche Ausgangssequenz $\underline{x}$ ergibt sich für $\underline{u} = \underline{1}$ und $G(D) = 1 + D^3$?

	$\underline{x} = (1, \, 0, \, 0, \, 1, \, 1, \, 1, \, \text{...} \hspace{0.05cm})$,
	$\underline{x} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \, \text{...} \hspace{0.05cm})$,
	$\underline{x} = (1, \, 1, \, 1, \, 0, \, 0, \, 0, \, \text{...} \hspace{0.05cm})$,
	Die Ausgangsfolge $\underline{x}$ ist zeitlich begrenzt.

3

Welche Ausgangssequenz $\underline{x}$ ergibt sich für $\underline{u} = \underline{1}$ und $G(D) = 1 + D + D^3$?

	$\underline{x} = (1, \, 0, \, 0, \, 1, \, 1, \, 1, \, \text{...} \hspace{0.05cm})$,
	$\underline{x} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \,\text{...} \hspace{0.05cm})$,
	$\underline{x} = (1, \, 1, \, 1, \, 0, \, 0, \, 0, \, \text{...} \hspace{0.05cm})$,
	Die Ausgangsfolge $\underline{x}$ ist zeitlich begrenzt.

4

Wie lautet die Codesequenz $\underline{x}$ von Coder A für die Eins–Sequenz am Eingang?

	$\underline{x} = (11, \, 00, \, 01, \, 10, \, 10, \, 10, \, \text{...} \hspace{0.05cm})$,
	$\underline{x} = (11, \, 10, \, 11, \, 00, \, 00, \, 00, \,\text{...} \hspace{0.05cm})$,
	$\underline{x} = (11, \, 11, \, 11, \, 11, \, 11, \, 11, \,\text{...} \hspace{0.05cm})$.
	Die Codesequenz $\underline{x}$ beinhaltet endlich viele Einsen.

5

Wie lautet die Codesequenz $\underline{x}$ von Coder B für die Eins–Sequenz am Eingang?

	$\underline{x} = (11, \, 00, \, 01, \, 10, \, 10, \, 10, \, \text{...} \hspace{0.05cm})$,
	$\underline{x} = (11, \, 10, \, 11, \, 00, \, 00, \, 00, \, \text{...} \hspace{0.05cm}$,
	$\underline{x} = (11, \, 11, \, 11, \, 11, \, 11, \, 11, \, \text{...} \hspace{0.05cm})$.
	Die Codesequenz $\underline{x}$ beinhaltet endlich viele Einsen.

6

Welche Aussagen treffen für Coder B zu?

	Zu Coder B gehört das Zustandsübergangsdiagramm 1.
	Zu Coder B gehört das Zustandsübergangsdiagramm 2.
	Der Coder B ist katastrophal.

Musterlösung

Solution

(1)  Zutreffend sind die Lösungsvorschläge 2 und 4:

• Die $D$–Transformierte der Codesequenz $\underline{x}$ ergibt sich mit $U(D) = 1/(1+ D)$ zu

$$X(D)= \frac{1+D +D^2+D^3}{1+D}= 1 +D^2 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} \underline{x}= (1,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} ... \hspace{0.1cm})\hspace{0.05cm}.$$

• Berücksichtigt wurde $(1 + D) \cdot (1 + D^2) = 1 + D + D^2 + D^3$.

(2)  Wegen $(1 + D) \cdot (1 + D + D^2) = 1 + D^3$ sind hier die Lösungsvorschläge 3 und 4 zutreffend:

$$X(D)= \frac{1+D^3}{1+D}= 1 +D + D^2 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} \underline{x}= (1,\hspace{0.05cm} 1,\hspace{0.05cm} 1,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} \text{...} \hspace{0.05cm})\hspace{0.05cm}.$$

(3)  Richtig ist allein der Lösungsvorschlag 1:

• Die Polynomdivision $(1 + D + D^3)$ durch $(1 + D)$ ist im binären Galoisfeld nicht ohne Rest möglich.
• Man erhält $X(D) = 1 + D^3 + D^4 + D^5 + \ \text{...} \hspace{0.05cm} $   ⇒   Ausgangssequenz $\underline{x} = (1, \, 0, \, 0, \, 1, \, 1, \, 1, \, \text{...} \hspace{0.05cm})$, die sich bis ins Unendliche erstreckt.

(4)  Richtig ist allein der Lösungsvorschlag 1:

• Die Übertragungsfunktionsmatrix von Coder A lautet:

$${\boldsymbol{\rm G}}_{\rm A}(D)= \left (1 +D + D^3\hspace{0.05cm}, \hspace{0.15cm} 1+D +D^2+D^3 \right ) \hspace{0.05cm}.$$

• Das jeweils erste Codebit ist deshalb durch die Sequenz entsprechend Teilaufgabe (3) gegeben und das zweite Bit durch die Sequenz entsprechend Teilaufgabe (1):

$$\underline{x}^{(1)}\hspace{-0.15cm} \ = \ \hspace{-0.15cm} (1,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 1,\hspace{0.05cm} 1,\hspace{0.05cm} ... \hspace{0.1cm})\hspace{0.05cm}, \hspace{1cm} \underline{x}^{(2)}\hspace{-0.15cm} \ = \ \hspace{-0.15cm} (1,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} \text{...} \hspace{0.05cm} \hspace{0.01cm})\hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{x}= (11,\hspace{0.05cm} 00,\hspace{0.05cm} 01,\hspace{0.05cm} 10,\hspace{0.05cm} 10,\hspace{0.05cm} 10,\hspace{0.05cm} \text{...} \hspace{0.05cm} \hspace{0.01cm})\hspace{0.05cm}.$$

(5)  Zutreffend sind die Lösungsvorschläge 2 und 4:

• Die Übertragungsfunktion von Coder B lautet $\mathbf{G}_{\rm B} = (1 + D^3, \ 1 + D + D^2 + D^3)$.
• Die erste Codesequenz ergibt sich nun entsprechend Teilaufgabe (2), während $\underline{x}^{(2)}$ weiterhin der Teilaufgabe (1) entspricht.
• Somit erhält man hier $\underline{x} = (11, \, 10, \, 11, \, 00, \, 00, \, 00, \, \text{...} \hspace{0.05cm})$   ⇒   Lösungsvorschlag 2.
• Richtig ist aber auch der Lösungsvorschlag 4. Unter der hier getroffenen Annahme, dass die Einsfolge gesendet wurde $(\underline{u} = \underline{1})$, beinhaltet die Codesequenz $\underline{x}$ nur fünf Einsen.
• In der nächsten Teilaufgabe wird dieser Sachverhalt nochmals aufgegriffen.

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

Wie aus dem Zustandsdiagramm 1 hervorgeht, führt hier die Informationssequenz $\underline{u} = \underline{1} = (1, \, 1, \, 1, \, 1, \, 1, \, 1, \, \text{...} \hspace{0.05cm})$ zur Codesequenz $\underline{x} = (11, \, 00, \, 01, \, 10, \, 10, \, 10, \, ...)$. Dies bedeutet:

• Zum Coder A gehört das Zustandsübergangsdiagramm 1.
• Zum Coder B gehört das Zustandsübergangsdiagramm 2   ⇒   Lösungsvorschlag 2.

Für den Coder B gelten dabei folgende Aussagen:

• $\underline{u} = \underline{0} = (0, \, 0, \, 0, \, 0, \, 0, \, 0, \, \text{...} \hspace{0.05cm}) \hspace{0.35cm} \Rightarrow \hspace{0.35cm} \underline{x} = (00, \, 00, \, 00, \, 00, \, 00, \, 00, \, \text{...} \hspace{0.05cm})$,
• $\underline{u} = \underline{1} = (1, \, 1, \, 1, \, 1, \, 1, \, 1, \, \text{...} \hspace{0.05cm}) \hspace{0.35cm} \Rightarrow \hspace{0.35cm} \underline{x} = (11, \, 10, \, 11, \, 00, \, 00, \, 00, \, \text{...} \hspace{0.05cm})$.

Das bedeutet:

• Mit nur fünf Bitfehlern an den Positionen 1, 2, 3, 5, 6 wird die Nullfolge als Einsfolge decodiert und umgekehrt.
• Einen solchen Code nennt man katastrophal   ⇒   Lösungsvorschlag 3.