Channel Coding/Algebraic and Polynomial Description

1. Channel Coding
2. Convolutional Codes and Their Decoding
3. Algebraic and Polynomial Description

• Previous page
• Next page

• Previous page
• Next page

Division of the generator matrix into partial matrices

Following the discussion in the earlier section  "Linear Codes and Cyclic Codes"  the codeword  $\underline{x}$  of a linear block code can be determined from the information word  $\underline{u}$  and the generator matrix  $\mathbf{G}$  in a simple way:   $\underline{x} = \underline{u} \cdot { \boldsymbol{\rm G}}$. The following holds:

• The vectors  $\underline{u}$  and  $\underline{x}$  have length  $k$  (bit count of an information word), respectively.   $n$  (bit count of a codeword) and  $\mathbf{G}$  has dimension  $k × n$  $(k$  rows and  $n$  columns$)$.
  

• In convolutional coding, on the other hand  $\underline{u}$  and  $\underline{x}$  denote sequences with  $k\hspace{0.05cm}' → ∞$  and  $n\hspace{0.05cm}' → ∞$. Therefore, the generator matrix  $\mathbf{G}$  will also be infinitely extended in both directions.
  
  

In preparation for the introduction of the generator matrix  $\mathbf{G}$  on the next page, we define  $m + 1$  partial matrices, each with  $k$  rows and  $n$  columns, which we denote by  $\mathbf{G}_l$  where  $0 ≤ l ≤ m$  holds.

$\text{Definition:}$  The  partial matrix  $\mathbf{G}_l$  describes the following fact:   If the matrix element  $\mathbf{G}_l(\kappa, j) = 1$, this says that the code bit  $x_i^{(j)}$  is influenced by the information bit  $u_{i-l}^{(\kappa)}$ . Otherwise, this matrix element is equal to  $0$.

This definition will now be illustrated by an example.

Convolutional encoder with  $k = 2, \ n = 3, \ m = 1$

$\text{Example 1:}$  We again consider the convolutional encoder according to the diagram with the following code bits:

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

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

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

Because of the memory order  $m = 1$  this encoder is fully characterized by the two partial matrices  $\mathbf{G}_0$  and  $\mathbf{G}_1$ :

\[{ \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}.\]

These matrices are to be interpreted as follows:

• first row of  $\mathbf{G}_0$, red arrows:  $\hspace{1.1cm}u_i^{(1)}$  affects both  $x_i^{(1)}$  and  $x_i^{(3)}$, but not  $x_i^{(2)}$.
  

• Second row of  $\mathbf{G}_0$, blue arrows:  $\hspace{0.6cm}u_i^{(2)}$  affects  $x_i^{(2)}$  and  $x_i^{(3)}$, but not  $x_i^{(1)}$.
  

• First row of  $\mathbf{G}_1$, green arrows:  $\hspace{0.9cm}u_{i-1}^{(1)}$  affects all three encoder outputs.
  

• Second row of  $\mathbf{G}_1$, brown arrow:  $\hspace{0.45cm}u_{i-1}^{(2)}$  affects only  $x_i^{(1)}$.

Generator matrix of a convolutional encoder with memory m

With the partial matrices  $\mathbf{G}_0, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \mathbf{G}_m$  the  $n$  code bits at time  $i$  can be expressed as follows:

\[\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 +\hspace{0.05cm} \text{...} \hspace{0.05cm} + \underline{u}_{i-m} \cdot { \boldsymbol{\rm G}}_m \hspace{0.05cm}.\]

The following vectorial quantities must be taken into account:

\[\underline{\it u}_i = \left ( u_i^{(1)}, u_i^{(2)}, \hspace{0.05cm}\text{...} \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}\text{...} \hspace{0.1cm}, x_i^{(n)}\right )\hspace{0.05cm}.\]

Considering the sequences

\[\underline{\it u} = \big( \underline{\it u}_1\hspace{0.05cm}, \underline{\it u}_2\hspace{0.05cm}, \hspace{0.05cm}\text{...} \hspace{0.1cm}, \underline{\it u}_i\hspace{0.05cm}, \hspace{0.05cm}\text{...} \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}\text{...} \hspace{0.1cm}, \underline{\it x}_i\hspace{0.05cm}, \hspace{0.05cm}\text{...} \hspace{0.1cm} \big)\hspace{0.05cm},\]

starting at  $i = 1$  and extending in time to infinity, this relation can be expressed by the matrix equation  $\underline{x} = \underline{u} \cdot \mathbf{G}$  . Here, for the generator matrix  $\mathbf{G}$  set as follows:

\[{ \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}.\]

• From the equation one immediately recognizes the memory  $m$  of the convolutional code. The parameters  $k$  and  $n$  are not directly readable.
• However, they are determined by the number of rows and columns of the partial matrices  $\mathbf{G}_l$ .
  

Generator matrix of a convolutional code

$\text{Example 2:}$  Mit den zwei Matrizen  $\mathbf{G}_0$  und  $\mathbf{G}_1$  – siehe  $\text{Beispiel 1}$  – erhält man die rechts skizzierte Matrix  $\mathbf{G}$.

Anzumerken ist:

• Die Generatormatrix  $\mathbf{G}$  erstreckt sich nach unten und nach rechts eigentlich bis ins Unendliche. Explizit dargestellt sind aber nur acht Zeilen und zwölf Spalten.

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

$$\underline{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  $\text{Beispiel 4}$  am Ende des letzten Kapitels erhalten:

$$\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}.$$

Generatormatrix für Faltungscodierer der Rate 1/n

Wir betrachten nun den Sonderfall  $k = 1$,

• zum einen aus Gründen einer möglichst einfachen Darstellung,
• aber auch, weil Faltungscodierer der Rate  $1/n$  für die Praxis eine große Bedeutung besitzen.
  
  

Faltungscoder mit  $k = 1, \ n = 2, \ m = 1$

Faltungscodierer mit  $k = 1, \ n = 2, \ m = 1$

Aus nebenstehender Skizze kann abgeleitet werden:

\[{ \boldsymbol{\rm G}}_0=\begin{pmatrix} 1 & 1 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm G}}_1=\begin{pmatrix} 0 & 1 \end{pmatrix}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} { \boldsymbol{\rm G}}=\begin{pmatrix} 11 & 01 & 00 & 00 & 00 & \cdots & \\ 00 & 11 & 01 & 00 & 00 & \cdots & \\ 00 & 00 & 11 & 01 & 00 & \cdots & \\ 00 & 00 & 00 & 11 & 01 & \cdots & \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \end{pmatrix}\hspace{0.05cm}.\]

Für die Eingangssequenz  $\underline{u} = (1, 0, 1, 1)$  beginnt die Codesequenz mit  $\underline{x} = (1, 1, 0, 1, 1, 1, 1, 0, \ \text{...})$.
Dieses Ergebnis ist gleich der Summe der Zeilen 1, 3 und 4 der Generatormatrix.

Faltungscoder mit  $k = 1, \ n = 2, \ m = 2$

Faltungscodierer mit  $k = 1, \ n = 2, \ m = 2$

Aufgrund der Gedächtnisordnung  $m = 2$  gibt es hier drei Teilmatrizen:

\[{ \boldsymbol{\rm G}}_0=\begin{pmatrix} 1 & 1 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm G}}_1=\begin{pmatrix} 1 & 0 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm G}}_2=\begin{pmatrix} 1 & 1 \end{pmatrix}\]

Damit lautet die resultierende Generatormatrix:

\[ { \boldsymbol{\rm G}}=\begin{pmatrix} 11 & 10 & 11 & 00 & 00 & 00 & \cdots & \\ 00 & 11 & 10 & 11 & 00 & 00 & \cdots & \\ 00 & 00 & 11 & 10 & 11 & 00 & \cdots & \\ 00 & 00 & 00 & 11 & 10 & 11 & \cdots & \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \end{pmatrix}\hspace{0.05cm}.\]

Hier führt die Eingangsssequenz  $\underline{u} = (1, 0, 1, 1)$  zur Codesequenz  $\underline{x} = (1, 1, 1, 0, 0, 0, 0, 1, \ \text{...})$.

Faltungscoder mit  $k = 1, \ n = 3, \ m = 3$

Faltungscodierer mit $k = 1, \ n = 3, \ m = 3$

Wegen  $m = 3$  gibt es nun vier Teilmatrizen der jeweiligen Dimension  $1 × 3$:

\[{ \boldsymbol{\rm G}}_0=\begin{pmatrix} 1 & 1 & 0 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm G}}_1=\begin{pmatrix} 0 & 0 & 1 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm G}}_2=\begin{pmatrix} 0 & 0 & 1 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm G}}_3=\begin{pmatrix} 0 & 1 & 1 \end{pmatrix}\hspace{0.05cm}.\]

Damit lautet die resultierende Generatormatrix:

\[{ \boldsymbol{\rm G}}=\begin{pmatrix} 110 & 001 & 001 & 011 & 000 & 000 & 000 & \cdots & \\ 000 & 110 & 001 & 001 & 011 & 000 & 000 & \cdots & \\ 000 & 000 & 110 & 001 & 001 & 011 & 000 & \cdots & \\ 000 & 000 & 000 & 110 & 001 & 001 & 011 & \cdots & \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \end{pmatrix}\hspace{0.05cm},\]

und man erhält für  $\underline{u} = (1, 0, 1, 1)$  die Codesequenz  $\underline{x} = (1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, \ \text{...})$.

GF(2)–Beschreibungsformen eines Digitalen Filters

Digitales Filter in  ${\rm GF}(2)$  der Ordnung  $m$

Im Kapitel  Grundlagen der Faltungscodierung  wurde bereits darauf hingewiesen,

• dass ein Rate  $1/n$–Faltungscodierer durch mehrere Digitale Filter realisiert werden kann,
• wobei die Filter parallel mit der gleichen Eingangsfolge  $\underline{u}$  arbeiten.

Bevor wir diese Aussage vertiefen, sollen zuerst die Eigenschaften eines Digitalfilters für das Galoisfeld  ${\rm GF(2)}$  genannt werden.

Die Grafik ist wie folgt zu interpretieren:

• Das Filter besitzt die Impulsantwort  $\underline{g} = (g_0, g_1, g_2, \ \text{...} \ , g_m)$.
• Für alle Filterkoeffizienten $($mit den Indizes  $0 ≤ l ≤ m)$  gilt:   $g_l ∈ {\rm GF}(2) = \{0, 1\}$.
  

• Die einzelnen Symbole  $u_i$  der Eingangsfolge  $\underline{u}$  seien ebenfalls binär:   $u_i ∈ \{0, 1\}$.
• Damit gilt für das Ausgangssymbol zu den Zeitpunkten  $i ≥ 1$  mit Addition und Multiplikation in  ${\rm GF(2)}$:

\[x_i = \sum_{l = 0}^{m} g_l \cdot u_{i-l} \hspace{0.05cm}.\]

• Dies entspricht der (zeitdiskreten)  Faltungsoperation  (englisch:  Convolution ), gekennzeichnet durch einen Stern. Damit kann für die gesamte Ausgangssequenz geschrieben werden:

\[\underline{x} = \underline{u} * \underline{g}\hspace{0.05cm}.\]

• Wesentlicher Unterschied gegenüber dem Kapitel  Digitale Filter  im Buch "Stochastische Signaltheorie" ist die Modulo–2–Addition  $(1 + 1 = 0)$  anstelle der herkömmlichen Addition  $(1 + 1 = 2)$.
  
  

Digitales Filter mit Impulsantwort  $(1, 0, 1, 1)$

$\text{Beispiel 3:}$  Die Impulsantwort des dargestellten Digitalen Filters dritter Ordnung lautet:   $\underline{g} = (1, 0, 1, 1)$.

• Die Eingangssequenz dieses Filters sei zeitlich unbegrenzt:   $\underline{u} = (1, 1, 0, 0, 0, \ \text{ ...})$.
  

• Damit ergibt sich die (unendliche) Ausgangssequenz  $\underline{x}$  im binären Galoisfeld   ⇒   ${\rm GF(2)}$:

\[\underline{x} = (\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}1,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 1\hspace{0.05cm})\]

\[\Rightarrow \hspace{0.3cm} \underline{x} =(\hspace{0.05cm}1,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 1,\hspace{0.05cm} 0, \hspace{0.05cm}0,\hspace{0.05cm} \text{ ...} \hspace{0.05cm}) \oplus (\hspace{0.05cm}0,\hspace{0.05cm}\hspace{0.05cm}1,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 1,\hspace{0.05cm}0, \hspace{0.05cm} \hspace{0.05cm} \text{ ...}\hspace{0.05cm}) = (\hspace{0.05cm}1,\hspace{0.05cm}\hspace{0.05cm}1,\hspace{0.05cm} 1,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 0, \hspace{0.05cm} \text{ ...} \hspace{0.05cm}) \hspace{0.05cm}.\]

• Bei der herkömmlichen Faltung (für reelle Zahlen) hätte dagegen das Ergebnis gelautet:

\[\underline{x}= (\hspace{0.05cm}1,\hspace{0.05cm}\hspace{0.05cm}1,\hspace{0.05cm} 1,\hspace{0.05cm} 2,\hspace{0.05cm} 1,\hspace{0.05cm} 0, \text{ ...} \hspace{0.05cm}) \hspace{0.05cm}.\]

Zeitdiskrete Signale kann man aber auch durch Polynome bezüglich einer Dummy–Variablen repräsentieren.

$\text{Definition:}$  Die zum zeitdiskreten Signal  $\underline{x} = (x_0, x_1, x_2, \ \text{...})$  gehörige  $D$–Transformierte  lautet:

\[X(D) = x_0 + x_1 \cdot D + x_2 \cdot D^2 + \hspace{0.05cm}\text{...}\hspace{0.05cm}= \sum_{i = 0}^{\infty} x_i \cdot D\hspace{0.05cm}^i \hspace{0.05cm}.\]

Für diese spezielle Transformation in einen Bildbereich verwenden wir auch folgende Notation, wobei "$D$" für  Delay Operator  steht:

\[\underline{x} = (x_0, x_1, x_2,\hspace{0.05cm}...\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad X(D) = \sum_{i = 0}^{\infty} x_i \cdot D\hspace{0.05cm}^i \hspace{0.05cm}.\]

Hinweis:   In der Literatur wird manchmal  $x(D)$  anstelle von  $X(D)$  verwendet. Wir schreiben in unserem Lerntutorial aber alle Bildbereichsfunktionen mit Großbuchstaben, zum Beispiel die Fourier–, die Laplace– und die $D$–Transformation:

\[x(t) \hspace{0.15cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}}\!\!\!-\!\!\bullet\hspace{0.15cm} X(f)\hspace{0.05cm},\hspace{0.4cm} x(t) \hspace{0.15cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}\rm L}\!\!\!-\!\!\bullet\hspace{0.15cm} X(p) \hspace{0.05cm},\hspace{0.4cm} \underline{x} \hspace{0.15cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.15cm} X(D) \hspace{0.05cm}.\]

Wir wenden nun die  $D$–Transformation auch auf die Informationssequenz  $\underline{u}$  und die Impulsantwort $\underline{g}$  an. Aufgrund der zeitlichen Begrenzung von  $\underline{g}$  ergibt sich die obere Summationsgrenze bei $G(D)$ zu $i = m$:

\[\underline{u} = (u_0, u_1, u_2,\hspace{0.05cm}\text{...}\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad U(D) = \sum_{i = 0}^{\infty} u_i \cdot D\hspace{0.05cm}^i \hspace{0.05cm},\]

\[\underline{g} = (g_0, g_1, \hspace{0.05cm}\text{...}\hspace{0.05cm}, g_m) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad G(D) = \sum_{i = 0}^{m} g_i \cdot D\hspace{0.05cm}^i \hspace{0.05cm}.\]

$\text{Satz:}$  Wie bei allen Spektraltransformationen gilt auch bei der  $D$–Transformation im Bildbereich die  Multiplikation, da die (diskreten) Zeitsignale  $\underline{u}$  und  $\underline{g}$  durch die  Faltung  verknüpft sind:

\[\underline{x} = \underline{u} * \underline{g} \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad X(D) = U(D) \cdot G(D) \hspace{0.05cm}.\]

Man bezeichnet – wie in der  Systemtheorie  allgemein üblich – auch die  $D$–Transformierte  $G(D)$  der Impulsantwort  $\underline{g}$  als  Übertragungsfunktion  (englisch:   Transfer Function). Der (recht einfache)  $\rm Beweis$  dieses wichtigen Ergebnisses finden Sie in der Angabe zur  Aufgabe 3.3Z.

Digitales Filter mit Impulsantwort  $(1, 0, 1, 1)$

$\text{Beispiel 4:}$  Wir betrachten wieder die zeitdiskreten Signale

\[\underline{u} = (\hspace{0.05cm}1\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}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad U(D) = 1+ D \hspace{0.05cm},\]

\[\underline{g} = (\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+ D^2 + D^3 \hspace{0.05cm}.\]

Wie im  $\text{Beispiel 3}$  (auf dieser Seite oben) erhält man auch auf diesem Lösungsweg:

\[X(D) = U(D) \cdot G(D) = (1+D) \cdot (1+ D^2 + D^3) \]

\[\Rightarrow \hspace{0.3cm} X(D) = 1+ D^2 + D^3 +D + D^3 + D^4 = 1+ D + D^2 + D^4 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{x} = (\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} 0\hspace{0.05cm}, \text{...} \hspace{0.05cm}) \hspace{0.05cm}.\]

Die Multiplikation mit  $D$  im Bildbereich entspricht im Zeitbereich einer Verschiebung um eine Stelle nach rechts, weshalb man  $D$  als Verzögerungsoperator  (englisch:  Delay Operator ) bezeichnet:

\[W(D) = D \cdot X(D) \quad \bullet\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\circ\quad \underline{w} = (\hspace{0.05cm}0\hspace{0.05cm},\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} 0\hspace{0.05cm}, \text{...} \hspace{0.05cm}) \hspace{0.05cm}.\]

Anwendung der D–Transformation auf Rate–1/n–Faltungscoder

Wir wenden nun die Ergebnisse der letzten Seite auf einen Faltungscoder an, wobei wir uns zunächst auf den Sonderfall  $k = 1$  beschränken.

• Ein solcher  $(n, \ k = 1)$–Faltungscode lässt sich mit  $n$  Digitalen Filtern realisieren, die auf der gleichen Informationssequenz  $\underline{u}$  parallel arbeiten.
• Die Grafik zeigt die Anordnung für den Codeparameter  $n = 2$   ⇒   Coderate $R = 1/2$.
  

Zwei parallel arbeitende Filter, jeweils mit Ordnung  $m$

Die folgenden Gleichungen gelten für beide Filter gleichermaßen, wobei für das obere Filter  $j = 1$  und für das untere Filter  $j = 2$  zu setzen ist:

• Die  Impulsantworten  der beiden Filter ergeben sich zu

\[\underline{g}^{(j)} = (g_0^{(j)}, g_1^{(j)}, \hspace{0.05cm}\text{...}\hspace{0.05cm}, g_m^{(j)}\hspace{0.01cm}) \hspace{0.05cm},\hspace{0.2cm}{\rm mit }\hspace{0.15cm} j \in \{1,2\}\hspace{0.05cm}.\]

• Die zwei  Ausgangssequenzen  lauten, wobei berücksichtigt ist, dass beide Filter auf der gleichen Eingangssequenz  $\underline{u} = (u_0, u_1, u_2, \hspace{0.05cm} \text{...})$  arbeiten:

\[\underline{x}^{(j)} = (x_0^{(j)}, x_1^{(j)}, x_2^{(j)}, \hspace{0.05cm}\text{...}\hspace{0.05cm}) = \underline{u} \cdot \underline{g}^{(j)} \hspace{0.05cm},\hspace{0.2cm}{\rm mit }\hspace{0.15cm} j \in \{1,2\}\hspace{0.05cm}.\]

• Für die  $D$–Transformierten  der Ausgangssequenzen gilt:

\[X^{(j)}(D) = U(D) \cdot G^{(j)}(D) \hspace{0.05cm},\hspace{0.2cm}{\rm mit }\hspace{0.15cm} j \in \{1,2\}\hspace{0.05cm}.\]

Um diesen Sachverhalt kompakter darstellen zu können, definieren wir nun folgende vektorielle Größen eines Faltungscodes der Rate  $1/n$:

$\text{Definition:}$  Die  $D$–Übertragungsfunktionen  der  $n$  parallel angeordneten Digitalen Filter werden im Vektor  $\underline{G}(D)$  zusammengefasst:

\[\underline{G}(D) = \left ( G^{(1)}(D), G^{(2)}(D), \hspace{0.05cm}\text{...}\hspace{0.1cm}, G^{(n)} (D) \right )\hspace{0.05cm}.\]

• Der Vektor  $\underline{X}(D)$  beinhaltet die  $D$–Transformierten  der  $n$  Codesequenzen  $\underline{x}^{(1)}, \underline{x}^{(2)}, \ \text{...} \ , \underline{x}^{(n)}$:

\[\underline{X}(D) = \left ( X^{(1)}(D), X^{(2)}(D), \hspace{0.05cm}\text{...}\hspace{0.1cm}, X^{(n)} (D) \right )\hspace{0.05cm}.\]

• Damit erhält man die folgende Vektorgleichung:

\[\underline{X}(D) = U(D) \cdot \underline{G}(D)\hspace{0.05cm}.\]

• Aufgrund des Codeparameters  $k = 1$  ist  $U(D)$  hier keine vektorielle Größe.

Faltungscoder mit  $n = 2, \ k = 1,\ m = 2$

$\text{Beispiel 5:}$  Wir betrachten den Faltungscodierer mit den Codeparametern  $n = 2, \ k = 1, \ m = 2$. Für diesen gilt:

\[\underline{g}^{(1)} =(\hspace{0.05cm}1\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+ D + D^2 \hspace{0.05cm},\]

\[\underline{g}^{(2)}= (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad G(D) = 1+ D^2 \]

\[\Rightarrow \hspace{0.3cm} \underline{G}(D) = \big ( 1+ D + D^2 \hspace{0.05cm}, \hspace{0.1cm}1+ D^2 \big )\hspace{0.05cm}.\]

Die Informationssequenz sei  $\underline{u} = (1, 0, 1, 1)$   ⇒   $D$–Transformierte  $U(D) = 1 + D^2 + D^3$. Damit erhält man:

\[\underline{X}(D) = \left ( X^{(1)}(D),\hspace{0.1cm} X^{(2)}(D) \right ) = U(D) \cdot \underline{G}(D) \hspace{0.05cm}, \hspace{0.2cm}\]

wobei

\[{X}^{(1)}(D) = (1+ D^2 + D^3) \cdot (1+ D + D^2)=1+ D + D^2 + D^2 + D^3 + D^4 + D^3 + D^4 + D^5 = 1+ D + D^5\]

\[\Rightarrow \hspace{0.3cm} \underline{x}^{(1)} = (\hspace{0.05cm}1\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} 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}) \hspace{0.05cm},\]

\[{X}^{(2)}(D) = (1+ D^2 + D^3) \cdot (1+ D^2)=1+ D^2 + D^2 + D^4 + D^3 + D^5 = 1+ D^3 + D^4 + D^5\]

\[\Rightarrow \underline{x}^{(2)} = (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm}0\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} 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}) \hspace{0.05cm}.\]

Das gleiche Ergebnis haben wir in der  Aufgabe 3.1Z  auf anderem Wege erhalten. Nach dem Multplexen der beiden Stränge erhält man wieder:  

$$\underline{x} = (11, 10, 00, 01, 01, 11, 00, 00, \hspace{0.05cm} \text{...} \hspace{0.05cm}).$$

Übertragungsfunktionsmatrix – Transfer Function Matrix

Allgemeiner  $(n, \ k)$–Faltungscoder

Wir haben gesehen, dass ein Faltungscode der Rate  $1/n$  sich am kompaktesten als Vektorgleichung im  $D$–transformierten Bereich beschreiben lässt:   $\underline{X}(D) = U(D) \cdot \underline{G}(D)$.

Nun erweitern wir das Resultat auf Faltungscodierer mit mehr als einem Eingang   ⇒   $k ≥ 2$  (siehe Grafik).

Um einen Faltungscode der Rate  $k/n$  im $D$–Bereich abbilden zu können, muss die Dimension obiger Vektorgleichung hinsichtlich Eingang und Übertragungsfunktion erhöht werden:

\[\underline{X}(D) = \underline{U}(D) \cdot { \boldsymbol{\rm G}}(D)\hspace{0.05cm}.\]

Dazu sind folgende Maßnahmen erforderlich:

• Aus der skalaren Funktion  $U(D)$  wird der Vektor  $\underline{U}(D) = (U^{(1)}(D), \ U^{(2)}(D), \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ U^{(k)}(D))$.
  

• Aus dem Vektor  $\underline{G}(D)$  wird die  $k × n$–Übertragungsfunktionsmatrix  $\mathbf{G}(D)$  (englisch:   Transfer Function Matrix  oder  Polynomial Generator Matrix):

\[{\boldsymbol{\rm G}}(D)=\begin{pmatrix} G_1^{(1)}(D) & G_1^{(2)}(D) & \hspace{0.05cm} \text{...} \hspace{0.05cm} & G_1^{(n)}(D)\\ G_2^{(1)}(D) & G_2^{(2)}(D) & \hspace{0.05cm} \text{...} \hspace{0.05cm} & G_2^{(n)}(D)\\ \vdots & \vdots & & \vdots\\ G_k^{(1)}(D) & G_k^{(2)}(D) & \hspace{0.05cm} \text{...} \hspace{0.05cm} & G_k^{(n)}(D) \end{pmatrix}\hspace{0.05cm}.\]

• Jedes der  $k \cdot n$  Matrixelemente  $G_i^{(j)}(D)$  mit  $1 ≤ i ≤ k,\ \ 1 ≤ j ≤ n$  ist ein Polynom über der Dummy–Variablen  $D$  im Galoisfeld  ${\rm GF}(2)$, maximal vom Grad  $m$, wobei  $m$  das Gedächtnis angibt.
  

• Für die obige  Übertragungsfunktionsmatrix  kann mit den zu Beginn dieses Kapitels definierten  Teilmatrizen  $\mathbf{G}_0, \ \text{...} \ , \mathbf{G}_m$  auch geschrieben werden $($als Index verwenden wir wieder  $l)$:

\[{\boldsymbol{\rm G}}(D) = \sum_{l = 0}^{m} {\boldsymbol{\rm G}}_l \cdot D\hspace{0.03cm}^l = {\boldsymbol{\rm G}}_0 + {\boldsymbol{\rm G}}_1 \cdot D + {\boldsymbol{\rm G}}_2 \cdot D^2 + \hspace{0.05cm} \text{...} \hspace{0.05cm}+ {\boldsymbol{\rm G}}_m \cdot D\hspace{0.03cm}^m \hspace{0.05cm}.\]

Faltungscoder mit  $k = 2, \ n = 3, \ m = 1$

$\text{Beispiel 6:}$  Wir betrachten den  $(n = 3, \ k = 2, \ m = 1)$–Faltungscoder, dessen Teilmatrizen bereits im  $\text{Beispiel 1}$  wie folgt ermittelt wurden:

\[{ \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}.\]

Wegen  $m = 1$  existieren keine Teilmatrizen für  $l ≥ 2$. Damit lautet die Übertragungsfunktionsmatrix:

\[{\boldsymbol{\rm G} }(D) = {\boldsymbol{\rm G} }_0 + {\boldsymbol{\rm G} }_1 \cdot D = \begin{pmatrix} 1+D & D & 1+D\\ D & 1 & 1 \end{pmatrix} \hspace{0.05cm}.\]

Die (zeitlich begrenzte) Informationssequenz sei  $\underline{u} = (0, 1, 1, 0, 0, 0, 1, 1)$, woraus sich die beiden Eingangsfolgen wie folgt ergeben:

\[\underline{u}^{(1)} = (\hspace{0.05cm}0\hspace{0.05cm},\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad {U}^{(1)}(D) = D + D^3 \hspace{0.05cm},\]

\[\underline{u}^{(2)} = (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm}0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad {U}^{(2)}(D) = 1 + D^3 \hspace{0.05cm}.\]

Daraus folgt für den Vektor der  $D$–Transformierten am Coderausgang:

\[\underline{X}(D) = \big (\hspace{0.05cm} {X}^{(1)}(D)\hspace{0.05cm}, \hspace{0.05cm} {X}^{(2)}(D)\hspace{0.05cm}, \hspace{0.05cm} {X}^{(3)}(D)\hspace{0.05cm}\big ) = \underline{U}(D) \cdot {\boldsymbol{\rm G} }(D) \begin{pmatrix} D+D^3 & 1+D^3 \end{pmatrix} \cdot \begin{pmatrix} 1+D & D & 1+D\\ D & 1 & 1 \end{pmatrix}\hspace{0.05cm}.\]

Damit ergeben sich in den drei Strängen folgende Codesquenzen:

\[{X}^{(1)}(D) = (D + D^3) \cdot (1+D) + (1 + D^3) \cdot D =D + D^2 + D^3 + D^4 + D + D^4 = D^2 + D^3\]

\[\Rightarrow \hspace{0.3cm} \underline{x}^{(1)} = (\hspace{0.05cm}0\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}\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm}\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} \text{...} \hspace{0.05cm}) \hspace{0.05cm},\]

\[{X}^{(2)}(D)= (D + D^3) \cdot D + (1 + D^3) \cdot 1 = D^2 + D^4 + 1 + D^3 = 1+D^2 + D^3 + D^4\]

\[\Rightarrow \hspace{0.3cm}\underline{x}^{(2)} = (\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} 1\hspace{0.05cm},\hspace{0.05cm}\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm}\hspace{0.05cm} \text{...} \hspace{0.05cm}) \hspace{0.05cm},\]

\[{X}^{(3)}(D)=(D + D^3) \cdot (1 + D) + (1 + D^3) \cdot 1 = D + D^2 + D^3+ D^4 + 1 + D^3 = 1+ D + D^2 + D^4\]

\[\Rightarrow \hspace{0.3cm}\underline{x}^{(3)} = (\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}\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm}\hspace{0.05cm} \text{...} \hspace{0.05cm}) \hspace{0.05cm}.\]

Die gleichen Ergebnisse haben wir auf anderen Wegen bereits in vorherigen Beispielen erhalten:

• im  $\text{Beispiel 4}$  des Kapitels "Grundlagen der Faltungscodierung",
  

• im  $\text{Beispiel 2}$  des aktuellen Kapitels.

Systematische Faltungscodes

Die Polynomrepräsentation anhand der Übertragungsfunktionsmtrix  $\mathbf{G}(D)$  ermöglicht Einblicke in die Struktur eines Faltungscodes.

• Beispielsweise erkennt man anhand dieser  $k × n$–Matrix, ob es sich um einen  systematischen Code  handelt.
• Darunter versteht man einen Code, bei dem die Codesequenzen  $\underline{x}^{(1)}, \ \text{...} \ , \ \underline{x}^{(k)}$  mit den Informationssequenzen  $\underline{u}^{(1)}, \ \text{...} \ , \ \underline{u}^{(k)}$  identisch sind.

• Die Grafik zeigt beispielhaft einen systematischen  $(n = 4, \ k = 3)$–Faltungscode.
  

Systematischer Faltungscode mit  $k = 3, \ n = 4$

Ein systematischer  $(n, k)$–Faltungscode liegt immer dann vor, wenn die Übertragungsfunktionsmatrix (mit  $k$  Zeilen und  $n$  Spalten) folgendes Aussehen hat:

\[{\boldsymbol{\rm G}}(D) = {\boldsymbol{\rm G}}_{\rm sys}(D) = \left [ \hspace{0.05cm} {\boldsymbol{\rm I}}_k\hspace{0.05cm} ; \hspace{0.1cm} {\boldsymbol{\rm P}}(D) \hspace{0.05cm}\right ] \hspace{0.05cm}.\]

Hierbei ist folgende Nomenklatur verwendet:

• $\mathbf{I}_k$  bezeichnet eine diagonale Einheitsmatrix der Dimension  $k × k$.
  

• $\mathbf{P}(D)$  ist eine  $k × (n -k)$–Matrix, wobei jedes Matrixelement ein Polynom in  $D$  beschreibt.
  
  

$\text{Beispiel 7:}$  Ein systematischer Faltungscode mit  $n = 3, \ k = 2, \ m = 2$  könnte beispielsweise die folgende Übertragungsfunktionsmatrix aufweisen:

\[{\boldsymbol{\rm G} }_{\rm sys}(D) = \begin{pmatrix} 1 & 0 & 1+D^2\\ 0 & 1 & 1+D \end{pmatrix}\hspace{0.05cm}.\]

Andere systematische Faltungscodes mit gleichem  $n$  und gleichem  $k$  unterscheiden sich demgegenüber nur durch die beiden Matrixelemente in der letzten Spalte.

Äquivalenter systematischer Faltungscode

Zu jedem  $(n, \ k)$–Faltungscode mit Matrix  $\mathbf{G}(D)$  gibt es einen  äquivalenten systematischen Code, dessen  $D$–Matrix wir mit  $\mathbf{G}_{\rm sys}(D)$ benennen.

Unterteilung von  $\mathbf{G}(D)$  in  $\mathbf{T}(D)$  und  $\mathbf{Q}(D)$

Um von der Übertragungsfunktionsmatrix  $\mathbf{G}(D)$  zur Matrix  $\mathbf{G}_{\rm sys}(D)$  des äquivalenten systematischen Faltungscodes zu kommen, geht man gemäß Grafik wie folgt vor:

• Man unterteilt die  $k × n$–Matrix  $\mathbf{G}(D)$  in eine quadratische Matrix  $\mathbf{T}(D)$  mit  $k$  Zeilen und  $k$  Spalten und bezeichnet den Rest mit  $\mathbf{Q}(D)$.

• Anschließend berechnet man die zu  $\mathbf{T}(D)$  inverse Matrix  $\mathbf{T}^{-1}(D)$  und daraus die Matrix für den äquivanten systematischen Code:

\[{\boldsymbol{\rm G}}_{\rm sys}(D)= {\boldsymbol{\rm T}}^{-1}(D) \cdot {\boldsymbol{\rm G}}(D) \hspace{0.05cm}.\]

• Da  $\mathbf{T}^{-1}(D) \cdot \mathbf{T}(D)$  die  $k × k$–Einheitsmatrix  $\mathbf{I}_k$  ergibt, kann die Übertragungsfunktionsmatrix des äquivalenten systematischen Codes in der gewünschten Form geschrieben werden:

\[{\boldsymbol{\rm G}}_{\rm sys}(D) = \big [ \hspace{0.05cm} {\boldsymbol{\rm I}}_k\hspace{0.05cm} ; \hspace{0.1cm} {\boldsymbol{\rm P}}(D) \hspace{0.05cm}\big ] \hspace{0.5cm}{\rm mit}\hspace{0.5cm} {\boldsymbol{\rm P}}(D)= {\boldsymbol{\rm T}}^{-1}(D) \cdot {\boldsymbol{\rm Q}}(D) \hspace{0.05cm}. \hspace{0.05cm}\]

Faltungscodierer der Rate  $2/3$

$\text{Beispiel 8:}$  Der auf den letzten Seiten schon häufiger betrachtete Coder der Rate  $2/3$  ist nicht systematisch, weil zum Beispiel  $\underline{x}^{(1)} ≠ \underline{u}^{(1)}, \ \underline{x}^{(2)} ≠ \underline{u}^{(2)}$  gilt (siehe nebenstehende Coderschaltung).

Man erkennt dies aber auch anhand der Übertragungsfunktionsmatrix:

\[{\boldsymbol{\rm G} }(D) = \big [ \hspace{0.05cm} {\boldsymbol{\rm T} }(D)\hspace{0.05cm} ; \hspace{0.1cm} {\boldsymbol{\rm Q} }(D) \hspace{0.05cm}\big ]\]

\[\Rightarrow \hspace{0.3cm} {\boldsymbol{\rm T} }(D) = \begin{pmatrix} 1+D & D\\ D & 1 \end{pmatrix}\hspace{0.05cm},\hspace{0.2cm} {\boldsymbol{\rm Q} }(D) = \begin{pmatrix} 1+D \\ 1 \end{pmatrix}\hspace{0.05cm}.\]

Die Determinante von  $\mathbf{T}(D)$  ergibt sich zu  $(1 + D) \cdot 1 + D \cdot D = 1 + D + D^2$  und ist ungleich Null.

Somit kann für die Inverse von  $\mathbf{T}(D)$  geschrieben werden (Vertauschung der Diagonalelemente!):

\[{\boldsymbol{\rm T} }^{-1}(D) = \frac{1}{1+D+D^2} \cdot \begin{pmatrix} 1 & D\\ D & 1+D \end{pmatrix}\hspace{0.05cm}.\]

Das Produkt  $\mathbf{T}(D) \cdot \mathbf{T}^{–1}(D)$  ergibt die Einheitsmatrix  $\mathbf{I}_2$, und für die dritte Spalte von  $\mathbf{G}_{\rm sys}(D)$  gilt:

\[{\boldsymbol{\rm P} }(D)= {\boldsymbol{\rm T} }^{-1}(D) \cdot {\boldsymbol{\rm Q} }(D) = \frac{1}{1+D+D^2} \cdot \begin{pmatrix} 1 & D\\ D & 1+D \end{pmatrix}\cdot \begin{pmatrix} 1+D\\ 1 \end{pmatrix} \]

\[\Rightarrow \hspace{0.3cm} {\boldsymbol{\rm P} }(D) = \frac{1}{1+D+D^2} \cdot \begin{pmatrix} (1+D) + D \\ D \cdot (1+D) + (1+D) \end{pmatrix} = \frac{1}{1+D+D^2} \cdot \begin{pmatrix} 1 \\ 1+D^2 \end{pmatrix} \]

\[\Rightarrow \hspace{0.2cm}{\boldsymbol{\rm G} }_{\rm sys}(D) = \begin{pmatrix} 1 & 0 & \frac{1}{1+D+D^2}\\ 0 & 1 &\frac{1+D^2}{1+D+D^2} \end{pmatrix}\hspace{0.05cm}. \]

Zu klären ist noch, wie das Filter einer solchen gebrochen–rationalen Übertragungsfunktion aussieht.

Filterstruktur bei gebrochen–rationaler Übertragungsfunktion

Rekursives Filter zur Realisierung von  $G(D) = A(D)/B(D)$

Hat eine Übertragungsfunktion die Form  $G(D) = A(D)/B(D)$, so bezeichnet man das zugehörige Filter als rekursiv.

Bei einem rekursiven Faltungscodierer mit dem Gedächtnis  $m$  kann für die beiden Polynome  $A(D)$  und  $B(D)$  allgemein geschrieben werden:

\[A(D) = \sum_{l = 0}^{m} a_l \cdot D\hspace{0.05cm}^l = a_0 + a_1 \cdot D + a_2 \cdot D^2 +\ \text{...} \ \hspace{0.05cm} + a_m \cdot D\hspace{0.05cm}^m \hspace{0.05cm},\]

\[B(D) = 1 + \sum_{l = 1}^{m} b_l \cdot D\hspace{0.05cm}^l = 1 + b_1 \cdot D + b_2 \cdot D^2 + \ \text{...} \ \hspace{0.05cm} + b_m \cdot D\hspace{0.05cm}^m \hspace{0.05cm}.\]

Die Grafik zeigt die entsprechende Filterstruktur in der so genannten  Controller Canonical Form:

• Die Koeffizienten  $a_0, \ \text{...} \ , \ a_m$  beschreiben den Vorwärtszweig.
• Die Koeffizienten  $b_1, \ \text{...} \ , \ b_m$  bilden eine Rückkopplung.
• Alle Koeffizienten sind binär, also  $1$  (durchgehende Verbindung) oder  $0$  (fehlende Verbindung).

Filter:  $G(D) = (1+D^2)/(1+D +D^2)$

$\text{Beispiel 9:}$  Die rechts skizzierte Filterstruktur lässt sich wie folgt beschreiben:

\[x_i = w_i + w_{i-2} \hspace{0.05cm},\]

\[w_i = u_i + w_{i-1}+ w_{i-2} \hspace{0.05cm}.\]

Entsprechend gilt für die  $D$–Transformierten:

\[X(D) =W(D) + W(D) \cdot D^2 =W(D) \cdot \left ( 1+ D^2 \right ) \hspace{0.05cm},\]

\[W(D) = \hspace{0.08cm} U(D) + W(D) \cdot D+ W(D) \cdot D^2\]

\[\Rightarrow \hspace{0.3cm} U(D) = W(D) \cdot \left ( 1+ D + D^2 \right ) \hspace{0.05cm}.\]

Somit erhält man für die Übertragungsfunktion dieses Filters:

\[G(D) = \frac{X(D)}{U(D)} = \frac{1+D^2}{1+D+D^2} \hspace{0.05cm}. \]

Im  $\text{Beispiel 8}$  zum äquivalenten systematischen Faltungscode hat sich im unteren Zweig genau dieser Ausdruck ergeben.

Aufgaben zum Kapitel

Aufgabe 3.2: G–Matrix eines Faltungscodierers

Aufgabe 3.2Z: (3, 1, 3)–Faltungscodierer

Aufgabe 3.3: Codesequenzberechnung über U(D) und G(D)

Aufgabe 3.3Z: Faltung und D–Transformation

Aufgabe 3.4: Systematische Faltungscodes

Aufgabe 3.4Z: Äquivalente Faltungscodes?

Aufgabe 3.5: Rekursive Filter für GF(2)