Aufgabe 3.7Z: Welcher Code ist katastrophal?

From LNTwww

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.





Hinweise:

  • 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}$  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

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