Aufgabe 4.09: Recursive Systematic Convolutional Codes

From LNTwww

Zustandsübergangsdiagramm eines RSC–Codes

In der  Aufgabe 4.8  wurden aus dem Zustandsübergangsdiagramm bereits wichtige Eigenschaften von Faltungscodes abgeleitet, wobei von einer nichtrekursiven Filterstruktur ausgegangen wurde.

Nun wird ein Rate–$1/2$–RSC–Code in ähnlicher Weise behandelt. Hierbei steht "RSC" für "Recursive Systematic Convolutional".

Die Übertragungsfunktionsmatrix eines RSC–Faltungscodes kann wie folgt angegeben werden:

$${\boldsymbol{\rm G}}(D) = \left [ 1\hspace{0.05cm},\hspace{0.3cm} G^{(2)}(D)/G^{(1)}(D) \right ] \hspace{0.05cm}.$$

Ansonsten gelten hier die genau gleichen Voraussetzungen wie bei der Aufgabe 4.8. Wir verweisen wieder auf folgende Theorieseiten:

  1. Systematische Faltungscodes
  2. Darstellung im Zustandsübergangsdiagramm
  3. Definition der freien Distanz
  4. GF(2)–Beschreibungsformen eines Digitalen Filters
  5. Anwendung der $D$–Transformation auf Rate–1/ $n$–Faltungscodes
  6. Filterstruktur bei gebrochen–rationaler Übertragungsfunktion


Im Zustandsübergangsdiagramm wird grundsätzlich vom Zustand  $S_0$  ausgegangen. Von jedem Zustand gehen zwei Pfeile ab. Die Beschriftung lautet "$u_i \hspace{0.05cm}| \hspace{0.05cm} x_i^{(1)}x_i^{(2)}$". Bei einem systematischen Code gilt dabei:

  • Das erste Codebit ist identisch mit dem Informationsbit:   $\hspace{0.2cm} x_i^{(1)} = u_i ∈ \{0, \, 1\}$.
  • Das zweite Codebit ist das Prüfbit (Paritybit):   $\hspace{0.2cm} x_i^{(2)} = p_i ∈ \{0, \, 1\}$.




Hinweise:

  • In den Fragen zu dieser Aufgabe werden folgende vektoriellen Größen verwendet:
    • die Informationssequenz:  $\hspace{0.2cm} \underline{u} = (u_1, \, u_2, \text{...} \hspace{0.05cm} )$,
    • die Paritysequenz:  $\hspace{0.2cm} \underline{p} = (p_1, \, p_2, \text{...} \hspace{0.05cm})$,
    • die Impulsantwort:  $\hspace{0.2cm} \underline{g} = (g_1, \, g_2, \text{...} \hspace{0.05cm} ); \hspace{0.2cm}$ diese ist gleich der Paritysequenz $\underline{p}$  für  $\underline{u} = (1, \, 0, \, 0, \text{...} \hspace{0.05cm} )$.


Fragebogen

1

Wie lautet die Impulsantwort  $\underline{g}$ ?

Es gilt  $\underline{g} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, 1, \text{...} \hspace{0.05cm})$.
Es gilt  $\underline{g} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \text{...} \hspace{0.05cm})$.

2

Es gelte  $\underline{u} = (1, \, 1, \, 0, \, 1)$. Welche Aussagen gelten für die Paritysequenz  $\underline{p}$ ?

Es gilt  $\underline{p} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \text{...} \hspace{0.05cm})$.
Es gilt  $\underline{p} = (1, \, 0, \, 0, \, 0, \, 0, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \text{...} \hspace{0.05cm})$.
Bei begrenzter Informationssequenz  $\underline{u}$  ist stets auch  $\underline{p}$  begrenzt.

3

Wie lautet die  $D$–Übertragungsfunktion  $G(D)$?

Es gilt  $G(D) = 1 + D + D^2 + D^4 + D^5 + D^7 + D^8 + \text{...} \hspace{0.05cm}$
Es gilt  $G(D) = (1 + D^2)/(1 + D + D^2)$.
Es gilt  $G(D) = (1 + D + D^2)/(1 + D^2)$.

4

Nun gelte  $\underline{u} = (1, \, 1, \, 1)$. Welche Aussagen gelten für die Paritysequenz  $\underline{p}$?

Es gilt  $\underline{p} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \text{...} \hspace{0.05cm})$.
Es gilt  $\underline{p} = (1, \, 0, \, 0, \, 0, \, 0, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \text{...} \hspace{0.05cm})$.
Bei unbegrenzter Impulsantwort  $\underline{g}$  ist stets auch  $\underline{p}$  unbegrenzt.

5

Wie groß ist die freie Distanz  $d_{\rm F}$  dieses RSC–Coders?

$d_{\rm F} \ = \ $


Musterlösung

(1)  Verfolgt man die Übergänge im Zustandsdiagramm für die Sequenz  $\underline{u} = (1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0)$  am Eingang, so erhält man den Weg

$$S_0 → S_1 → S_3 → S_2 → S_1 → S_3 → S_2 → S_1 → S_3 → \hspace{0.05cm}\text{...} \hspace{0.05cm}$$
  • Bei jedem Übergang ist das erste Codesymbol $x_i^{(1)}$ gleich dem Informationsbit $u_i$ und das Codesymbol $x_i^{(2)}$ gibt das Paritybit $p_i$ an.
  • Damit erhält man das Ergebnis entsprechend dem Lösungsvorschlag 1:
$$\underline{p}= (\hspace{0.05cm}1\hspace{0.05cm}, \hspace{0.05cm}1\hspace{0.05cm}, \hspace{0.05cm}1\hspace{0.05cm}, \hspace{0.05cm} 0\hspace{0.05cm}, \hspace{0.05cm} 1\hspace{0.05cm}, \hspace{0.05cm} 1\hspace{0.05cm}, \hspace{0.05cm} 0\hspace{0.05cm}, \hspace{0.05cm} 1\hspace{0.05cm}, \hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm}\text{...} \hspace{0.05cm}) = \underline{g}\hspace{0.05cm}.$$
  • Bei einem jeden RSC–Code ist die Impulsantwort $\underline{g}$ unendlich lang und wird irgendwann periodisch, in diesem Beispiel mit der Periode  $P = 3$  und  "$0, \, 1, \, 1$".


Verdeutlichung von  $\underline{p} = (1, \, 1, \, 0, \, 1)^{\rm T} \cdot \mathbf{G}$

(2)  Die Grafik zeigt die Lösung dieser Aufgabe entsprechend der Gleichung  $\underline{p} = \underline{u}^{\rm T} \cdot \mathbf{G}$.

  • Hierbei ist die Generatormatrix  $\mathbf{G}$  nach unten und rechts unendlich weit ausgedehnt.
  • Richtig ist der Lösungsvorschlag 2.


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

  • Zwischen der Impulsantwort $\underline{g}$ und der $D$–Übertragungsfunktion $\mathbf{G}(D)$ besteht der Zusammenhang gemäß dem ersten Lösungsvorschlag:
$$\underline{g}= (\hspace{-0.05cm}1\hspace{-0.05cm}, \hspace{-0.05cm}1\hspace{-0.05cm}, \hspace{-0.05cm}1\hspace{-0.05cm}, \hspace{-0.05cm}0\hspace{-0.05cm}, \hspace{-0.05cm}1\hspace{-0.05cm}, \hspace{-0.05cm}1\hspace{-0.05cm}, \hspace{-0.05cm}0\hspace{-0.05cm}, \hspace{-0.05cm}1\hspace{-0.05cm}, \hspace{-0.05cm}1\hspace{-0.05cm}, ... ) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad G(D) = 1\hspace{-0.05cm}+\hspace{-0.05cm} D\hspace{-0.05cm} +\hspace{-0.05cm} D^2\hspace{-0.05cm} +\hspace{-0.05cm} D^4 \hspace{-0.05cm}+\hspace{-0.05cm} D^5 \hspace{-0.05cm}+\hspace{-0.05cm} D^7 \hspace{-0.05cm}+\hspace{-0.05cm} D^8 + \hspace{0.05cm} \text{...} \hspace{0.05cm}.$$
  • Überprüfen wir nun den zweiten Vorschlag:
$$G(D) = \frac{1+ D^2}{1+ D + D^2} \hspace{0.3cm}\Rightarrow \hspace{0.3cm} G(D) \cdot [1+ D + D^2] = 1+ D^2 \hspace{0.05cm}.$$
  • Die folgende Rechnung zeigt, dass diese Gleichung tatsächlich stimmt:
$$(1+ D+ D^2+ D^4 +D^5 + D^7 + D^8 + \hspace{0.05cm} \text{...}) \cdot (1+ D+ D^2 ) =$$
$$=1+ D+ D^2\hspace{1.05cm} +D^4 + D^5 \hspace{1.05cm} +D^7 + D^8 \hspace{1.05cm} + D^{10}+ \hspace{0.05cm} \text{...}$$
$$+ \hspace{0.8cm}D+ D^2+D^3 \hspace{1.05cm}+ D^5 + D^6 \hspace{1.05cm} +D^8 + D^9 \hspace{1.25cm} +\hspace{0.05cm} \text{...} $$
$$+ \hspace{1.63cm} D^2+D^3+ D^4 \hspace{1.05cm}+ D^6 +D^7 \hspace{1.05cm}+ D^9 + D^{10} \hspace{0.12cm}+ \hspace{0.05cm} \text{...}$$
$$=\underline{1\hspace{0.72 cm}+ D^2} \hspace{0.05cm}.$$
  • Da aber die Gleichung (2) stimmt, muss die letzte Gleichung falsch sein.


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

  • Aus $\underline{u} = (1, \, 1, \, 1)$ folgt $U(D) = 1 + D + D^2$. Damit gilt auch:
$$P(D) = U(D) \cdot G(D) = (1+D+D^2) \cdot \frac{1+D^2}{1+D+D^2}= 1+D^2\hspace{0.3cm} \Rightarrow\hspace{0.3cm} \underline{p}= (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm}\text{...}\hspace{0.05cm})\hspace{0.05cm}. $$
  • Wären die Größen  $u_i$  und  $g_i$  reellwertig, so würde die (diskrete) Faltung  $\underline{p} = \underline{u} * \underline{g}$  stets zu einer Verbreiterung führen   ⇒   $\underline{p}$  wäre in diesem Fall breiter als  $\underline{u}$  und auch breiter als  $\underline{g}$.
  • Bei  $u_i ∈ {\rm GF}(2)$  und  $g_i ∈ {\rm GF}(2)$  kann es (muss es aber nicht) dagegen vorkommen, dass auch bei unbegrenztem  $\underline{u}$  oder bei unbegrenztem  $\underline{g}$  das Faltungsprodukt  $\underline{p} = \underline{u} * \underline{g}$  begrenzt ist.
Verdeutlichung von  $\underline{p} = (1, \, 1, \, 1, \, 0, \, ...)^{\rm T} \cdot \mathbf{G}$
  • Das Ergebnis wird abschließend noch entsprechend der Gleichung $\underline{p} = \underline{u}^{\rm T} \cdot \mathbf{G}$ überprüft.


(5)  Nach ähnlicher Vorgehensweise wie in der Aufgabe A4.8, (4) erkennt man:

  • Die freie Distanz wird auch hier durch den Pfad  $S_0 → S_0 → S_1 → S_2 → S_0 → S_0 → \hspace{0.05cm}\text{...}\hspace{0.05cm}$ bestimmt.
  • Die zugehörige Codesequenz  $\underline{x}$  ist nun aber  " $00 \ 11 \ 10 \ 11 \ 00 \ ... $".
  • Damit ergibt sich die freie Distanz zu  $d_{\rm F} \ \underline{= 5}$.
  • Beim nichtrekursiven Code (Aufgabe 4.8) war dagegen die freie Distanz  $d_{\rm F} = 3$.