Channel Coding/Algebraic and Polynomial Description

1. Channel Coding
2. Faltungscodierung und geeignete Decoder
3. Algebraic and Polynomial Description

• Previous page
• Next page

• Previous page
• Next page

Definition und Interpretation der Teilmatrizen G0, ... , Gm

Entsprechend den Ausführungen in Kapitel 1.4 lässt sich das Codewort x eines linearen Blockcodes aus dem Informationswort u und der Generatormatrix G in einfacher Weise ermitteln:

[math]\displaystyle{ \underline{x} = \underline{u} \cdot { \boldsymbol{\rm G}} \hspace{0.05cm}. }[/math]

Dabei gilt:

• Die Vektoren u und x haben die Länge k (Bitanzahl eines Informationswortes) bzw. n (Bitanzahl eines Codewortes) und G besitzt die Dimension k × n (k Zeilen und n Spalten).
  

• Bei Faltungscodierung bezeichnen dagegen u und x Sequenzen mit k' → ∞ und n' → ∞. Deshalb wird auch die Generatormatrix G in beiden Richtungen unendlich weit ausgedehnt sein.
  
  

Als Vorbereitung für die Einführung der Generatormatrix G auf der nächsten Seite definieren wir m + 1 Teilmatrizen, jeweils mit k Zeilen und n Spalten, die wir mit G_l bezeichnen, wobei 0 ≤ l ≤ m gilt.

: Ist das Matrizenelement G_l(κ, j) = 1, so sagt dies aus, dass das Codebit x_i^(j) durch das Informationsbit u_i–l^(κ) beeinflusst wird. Andernfalls ist dieses Matrixelement gleich 0.

Diese Definition wird nun an einem Beispiel verdeutlicht.

:

Wir betrachten wiederum den Faltungscodierer gemäß nebenstehender Grafik mit den folgenden Codebits:

[math]\displaystyle{ x_i^{(1)} \hspace{-0.15cm} = \hspace{-0.15cm} u_{i}^{(1)} + u_{i-1}^{(1)}+ u_{i-1}^{(2)} \hspace{0.05cm}, }[/math]

[math]\displaystyle{ x_i^{(2)} \hspace{-0.15cm} = \hspace{-0.15cm} u_{i}^{(2)} + u_{i-1}^{(1)} \hspace{0.05cm}, }[/math]

[math]\displaystyle{ x_i^{(3)} \hspace{-0.15cm} = \hspace{-0.15cm} u_{i}^{(1)} + u_{i}^{(2)}+ u_{i-1}^{(1)} \hspace{0.05cm}. }[/math]

Wegen der Gedächtnisordnung m = 1 wird dieser Codierer durch die beiden Teilmatrizen G₀ und G₁ charakterisiert:

[math]\displaystyle{ { \boldsymbol{\rm G}}_0 = \begin{pmatrix} 1 & 0 & 1\\ 0 & 1 & 1 \end{pmatrix} \hspace{0.05cm}, \hspace{0.5cm} { \boldsymbol{\rm G}}_1 = \begin{pmatrix} 1 & 1 & 1\\ 1 & 0 & 0 \end{pmatrix}\hspace{0.05cm}. }[/math]

Diese Matrizen sind wie folgt zu interpretieren:

• Erste Zeile von G₀, rote Pfeile:       u_i⁽¹⁾ beeinflusst sowohl x_i⁽¹⁾ als auch x_i⁽³⁾, nicht jedoch x_i⁽²⁾.
  

• Zweite Zeile von G₀, blaue Pfeile:   u_i⁽²⁾ beeinflusst x_i⁽²⁾ und x_i⁽³⁾, aber nicht x_i⁽¹⁾.
  

• Erste Zeile von G₁, grüne Pfeile:     u_i–1⁽¹⁾ beeinflusst alle drei Coderausgänge.
  

• Zweite Zeile von G₁, brauner Pfeil: u_i–1⁽²⁾ beeinflusst nur x_i⁽¹⁾.

Generatormatrix eines Faltungscodierers mit Gedächtnis m

Mit den Teilmatrizen G₀, ... , G_m lassen sich die n Codebits zum Zeitpunkt i wie folgt ausdrücken:

[math]\displaystyle{ \underline{x}_i = \sum_{l = 0}^{m} \hspace{0.15cm}\underline{u}_{i-l} \cdot { \boldsymbol{\rm G}}_l = \underline{u}_{i} \cdot { \boldsymbol{\rm G}}_0 + \underline{u}_{i-1} \cdot { \boldsymbol{\rm G}}_1 + ... + \underline{u}_{i-m} \cdot { \boldsymbol{\rm G}}_m \hspace{0.05cm}. }[/math]

Hierbei sind folgende vektorielle Größen zu berücksichtigen:

[math]\displaystyle{ \underline{\it u}_i = \left ( u_i^{(1)}, u_i^{(2)}, \hspace{0.05cm}... \hspace{0.1cm}, u_i^{(k)}\right )\hspace{0.05cm},\hspace{0.5cm} \underline{\it x}_i = \left ( x_i^{(1)}, x_i^{(2)}, \hspace{0.05cm}... \hspace{0.1cm}, x_i^{(n)}\right )\hspace{0.05cm}. }[/math]

Betrachtet man die bei i = 1 beginnenden und sich zeitlich bis ins Unendliche erstreckenden Sequenzen

[math]\displaystyle{ \underline{\it u} = \big( \underline{\it u}_1\hspace{0.05cm}, \underline{\it u}_2\hspace{0.05cm}, \hspace{0.05cm}... \hspace{0.1cm}, \underline{\it u}_i\hspace{0.05cm}, \hspace{0.05cm}... \hspace{0.1cm} \big)\hspace{0.05cm},\hspace{0.5cm} \underline{\it x} = \big( \underline{\it x}_1\hspace{0.05cm}, \underline{\it x}_2\hspace{0.05cm}, \hspace{0.05cm}... \hspace{0.1cm}, \underline{\it x}_i\hspace{0.05cm}, \hspace{0.05cm}... \hspace{0.1cm} \big)\hspace{0.05cm}, }[/math]

so kann dieser Zusammenhang durch die Matrixgleichung x = u · G ausgedrückt werden. Hierbei ist für die Generatormatrix G zu setzen:

[math]\displaystyle{ { \boldsymbol{\rm G}}=\begin{pmatrix} { \boldsymbol{\rm G}}_0 & { \boldsymbol{\rm G}}_1 & { \boldsymbol{\rm G}}_2 & \cdots & { \boldsymbol{\rm G}}_m & & & \\ & { \boldsymbol{\rm G}}_0 & { \boldsymbol{\rm G}}_1 & { \boldsymbol{\rm G}}_2 & \cdots & { \boldsymbol{\rm G}}_m & &\\ & & { \boldsymbol{\rm G}}_0 & { \boldsymbol{\rm G}}_1 & { \boldsymbol{\rm G}}_2 & \cdots & { \boldsymbol{\rm G}}_m &\\ & & & \cdots & \cdots & & & \cdots \end{pmatrix}\hspace{0.05cm}. }[/math]

Aus der Gleichung erkennt man sofort das Gedächtnis m des Faltungscodes. Die Parameter k und n sind direkt nicht ablesbar. Sie sind aber durch die Zeilen– und Spaltenzahl der Teilmatrizen G_l festgelegt.

:

Mit den zwei Matrizen G₀ und G₁ – siehe letztes Beispiel – erhält man die rechts skizzierte Matrix G.

Anzumerken ist:

• Die Generatormatrix G erstreckt sich nach unten und nach rechts eigentlich bis ins Unendliche. Explizit dargestellt sind aber nur 8 Zeilen und 12 Spalten.

• Für die zeitlich begrenzte Informationssequenz u = (0, 1, 1, 0, 0, 0, 1, 1) ist der gezeichnete Matrixteil ausreichend. Die Codesequenz lautet dann:   x = (0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0).

• Anhand der Beschriftungsfarben lassen sich die n = 3 Codewortstränge ablesen. Das gleiche Ergebnis haben wir (auf anderem Wege) im Beispiel am Ende von Kapitel 3.1 erhalten.

[math]\displaystyle{ \underline{\it x}^{(1)} = (0\hspace{0.05cm}, 0\hspace{0.05cm}, 1\hspace{0.05cm}, 1) \hspace{0.05cm},\hspace{0.5cm} \underline{\it x}^{(2)} = (1\hspace{0.05cm}, 0\hspace{0.05cm},1\hspace{0.05cm}, 1) \hspace{0.05cm},\hspace{0.5cm} \underline{\it x}^{(3)} = (1\hspace{0.05cm}, 1\hspace{0.05cm}, 1\hspace{0.05cm}, 0) \hspace{0.05cm}. }[/math]