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 $\text{ Coder A }$ und $\text{ Coder B}$, jeweils mit dem Gedächtnis  $m = 3$  (oben),
• zwei Zustandsübergangsdiagramme, bezeichnet mit $\text{ Diagramm 1 }$ und $\text{ Diagramm 2 }$ (unten).

In der letzten Teilaufgabe sollen Sie entscheiden, welches Diagramm zum $\text{ Coder A }$ gehört und welches zum $\text{ 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.

Hints:

• This exercise belongs to the chapter  "Code description with state and trellis diagram".
• Reference is made in particular to the sections.
  •   "State definition for a memory register"  and.
  •   "Representation in the state transition diagram".
• Two more polynomial products in ${\rm GF}(2)$ are given:

$$(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}$  und  $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 $\text{ 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 $\text{ 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 $\text{ Coder B }$ zu?

	Zu $\text{ Coder B }$ gehört das $\text{ Diagramm 1}$.
	Zu $\text{ Coder B }$ gehört das $\text{ Diagramm 2}$.
	Der $\text{ 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 $\text{ 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 $\text{ 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  $\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 $\text{ Coder A }$ gehört das Zustandsübergangsdiagramm 1.
• Zum $\text{ Coder B }$ gehört das Zustandsübergangsdiagramm 2   ⇒   Lösungsvorschlag 2.

Für den $\text{ 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.