View source for Channel Coding/Algebraic and Polynomial Description

 
{{Header
|Untermenü=Faltungscodierung und geeignete Decoder
|Vorherige Seite=Grundlagen der Faltungscodierung
|Nächste Seite=Codebeschreibung mit Zustands– und Trellisdiagramm
}}

== Aufteilung der Generatormatrix in Teilmatrizen ==
<br>
Entsprechend den Ausführungen im früheren Abschnitt&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Lineare_Codes_und_zyklische_Codes| Lineare Codes und zyklische Codes]]&nbsp; lässt sich das Codewort&nbsp; $\underline{x}$&nbsp; eines linearen Blockcodes aus dem Informationswort&nbsp; $\underline{u}$&nbsp; und der Generatormatrix&nbsp; $\mathbf{G}$&nbsp; in einfacher Weise ermitteln: &nbsp; $\underline{x} = \underline{u} \cdot { \boldsymbol{\rm G}}$. Dabei gilt:
*Die Vektoren&nbsp; $\underline{u}$&nbsp; und&nbsp; $\underline{x}$&nbsp; haben die Länge&nbsp; $k$&nbsp; (Bitanzahl eines Informationswortes) bzw.&nbsp; $n$&nbsp; (Bitanzahl eines Codewortes) und&nbsp; $\mathbf{G}$&nbsp; besitzt die Dimension&nbsp; $k &times; n$&nbsp; $(k$&nbsp; Zeilen und&nbsp; $n$&nbsp; Spalten$)$.<br>

*Bei Faltungscodierung bezeichnen dagegen&nbsp; $\underline{u}$&nbsp; und&nbsp; $\underline{x}$&nbsp; Sequenzen mit&nbsp; $k\hspace{0.05cm}' &#8594; &#8734;$&nbsp; und&nbsp; $n\hspace{0.05cm}' &#8594; &#8734;$. Deshalb wird auch die Generatormatrix&nbsp; $\mathbf{G}$&nbsp; in beiden Richtungen unendlich weit ausgedehnt sein.<br><br>

Als Vorbereitung für die Einführung der Generatormatrix&nbsp; $\mathbf{G}$&nbsp; auf der nächsten Seite definieren wir&nbsp; $m + 1$&nbsp; Teilmatrizen, jeweils mit&nbsp; $k$&nbsp; Zeilen und&nbsp; $n$&nbsp; Spalten, die wir mit&nbsp; $\mathbf{G}_l$&nbsp; bezeichnen, wobei&nbsp; $0 &#8804; l &#8804; m$&nbsp; gilt.<br>

{{BlaueBox|TEXT=  
$\text{Definition:}$&nbsp;  Die &nbsp;'''Teilmatrix'''&nbsp; $\mathbf{G}_l$&nbsp; beschreibt folgenden Sachverhalt: &nbsp; Ist das Matrixelement&nbsp; $\mathbf{G}_l(\kappa, j) = 1$, so sagt dies aus, dass das Codebit&nbsp; $x_i^{(j)}$&nbsp; durch das Informationsbit&nbsp; $u_{i-l}^{(\kappa)}$&nbsp; beeinflusst wird. Andernfalls ist dieses Matrixelement gleich&nbsp; $0$.}}<br>

Diese Definition wird nun an einem Beispiel verdeutlicht.

[[File:P ID2600 KC T 3 1 S4 v1.png|right|frame|Faltungscoder mit&nbsp; $k = 2, \ n = 3, \ m = 1$]] 
{{GraueBox|TEXT=  
$\text{Beispiel 1:}$&nbsp;  
Wir betrachten wiederum den Faltungscodierer gemäß der Grafik mit folgenden Codebits:

::<math>x_i^{(1)} = u_{i}^{(1)} + u_{i-1}^{(1)}+ u_{i-1}^{(2)} \hspace{0.05cm},</math>
::<math>x_i^{(2)} = u_{i}^{(2)} + u_{i-1}^{(1)} \hspace{0.05cm},</math>
::<math>x_i^{(3)} = u_{i}^{(1)} + u_{i}^{(2)}+ u_{i-1}^{(1)} \hspace{0.05cm}.</math>

Wegen der Gedächtnisordnung&nbsp; $m = 1$&nbsp; wird dieser Codierer durch die beiden Teilmatrizen&nbsp; $\mathbf{G}_0$&nbsp; und&nbsp; $\mathbf{G}_1$&nbsp; vollständig charakterisiert:

::<math>{ \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&nbsp; $\mathbf{G}_0$, rote Pfeile:&nbsp; $\hspace{1.1cm}u_i^{(1)}$&nbsp; beeinflusst sowohl&nbsp; $x_i^{(1)}$&nbsp; als auch&nbsp; $x_i^{(3)}$, nicht jedoch&nbsp; $x_i^{(2)}$.<br>

*Zweite Zeile von&nbsp; $\mathbf{G}_0$, blaue Pfeile:&nbsp; $\hspace{0.6cm}u_i^{(2)}$&nbsp; beeinflusst&nbsp; $x_i^{(2)}$&nbsp; und&nbsp; $x_i^{(3)}$, aber nicht&nbsp; $x_i^{(1)}$.<br>

*Erste Zeile von&nbsp; $\mathbf{G}_1$, grüne Pfeile:&nbsp; $\hspace{0.9cm}u_{i-1}^{(1)}$&nbsp; beeinflusst alle drei Coderausgänge.<br>

*Zweite Zeile von&nbsp; $\mathbf{G}_1$, brauner Pfeil:&nbsp; $\hspace{0.45cm}u_{i-1}^{(2)}$&nbsp; beeinflusst nur&nbsp; $x_i^{(1)}$.}}<br>

== Generatormatrix eines Faltungscodierers mit Gedächtnis ''m'' ==
<br>
Mit den Teilmatrizen&nbsp; $\mathbf{G}_0, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \mathbf{G}_m$&nbsp; lassen sich die&nbsp; $n$&nbsp; Codebits zum Zeitpunkt&nbsp; $i$&nbsp; wie folgt ausdrücken:

::<math>\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}.</math>

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

::<math>\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}.</math>

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

::<math>\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},</math>

so kann dieser Zusammenhang durch die Matrixgleichung&nbsp; $\underline{x} = \underline{u} \cdot \mathbf{G}$&nbsp; ausgedrückt werden. Hierbei ist für die Generatormatrix&nbsp; $\mathbf{G}$&nbsp; wie folgt zu setzen:

::<math>{ \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&nbsp; $m$&nbsp; des Faltungscodes. Die Parameter&nbsp; $k$&nbsp; und&nbsp; $n$&nbsp; sind direkt nicht ablesbar.
* Sie sind aber durch die Zeilen&ndash; und Spaltenanzahl der Teilmatrizen&nbsp; $\mathbf{G}_l$&nbsp; festgelegt.<br>


[[File:P ID2601 KC T 3 2 S2 v1.png|right|frame|Generatormatrix eines Faltungscodes]]  
{{GraueBox|TEXT=  
$\text{Beispiel 2:}$&nbsp;  
Mit den zwei Matrizen&nbsp; $\mathbf{G}_0$&nbsp; und&nbsp; $\mathbf{G}_1$&nbsp; &ndash; siehe&nbsp; [[Kanalcodierung/Algebraische_und_polynomische_Beschreibung#Aufteilung_der_Generatormatrix_in_Teilmatrizen| $\text{Beispiel 1}$]]&nbsp; &ndash; erhält man die rechts skizzierte Matrix&nbsp; $\mathbf{G}$.

Anzumerken ist:
*Die Generatormatrix&nbsp;  $\mathbf{G}$&nbsp; 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&nbsp; $\underline{u} = (0, 1, 1, 0, 0, 0, 1, 1)$&nbsp; 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&nbsp; $n = 3$&nbsp; Codewortstränge ablesen. 
*Das gleiche Ergebnis haben wir (auf anderem Wege) im&nbsp; [[Kanalcodierung/Grundlagen_der_Faltungscodierung#Faltungscodierer_mit_zwei_Eing.C3.A4ngen| $\text{Beispiel 4}$]]&nbsp; 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}.$$}}<br>

== Generatormatrix für Faltungscodierer der Rate 1/''n'' ==
<br>
Wir betrachten nun den Sonderfall&nbsp; $k = 1$, 
*zum einen aus Gründen einer möglichst einfachen Darstellung, 
*aber auch, weil Faltungscodierer der Rate&nbsp; $1/n$&nbsp; für die Praxis eine große Bedeutung besitzen.<br><br>

[[File:P ID2602 KC T 3 2 S3a.png|right|frame|Faltungscoder mit&nbsp;  $k = 1, \ n = 2,  \ m = 1$]]
<b>Faltungscodierer mit&nbsp; $k = 1, \ n = 2, \ m = 1$</b><br>

Aus nebenstehender Skizze kann abgeleitet werden:

::<math>{ \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}.</math>

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

[[File:P ID2603 KC T 3 2 S3b.png|right|frame|Faltungscoder mit&nbsp; $k = 1, \ n = 2, \ m = 2$]]
<b>Faltungscodierer mit&nbsp; $k = 1, \ n = 2, \ m = 2$</b><br>

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

::<math>{ \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}</math>

Damit lautet die resultierende Generatormatrix:

::<math>	{ \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}.</math>

Hier führt die Eingangsssequenz&nbsp; $\underline{u} = (1, 0, 1, 1)$&nbsp; zur Codesequenz&nbsp; $\underline{x} = (1, 1, 1, 0, 0, 0, 0, 1, \ \text{...})$.<br><br>

[[File:P ID2604 KC T 3 2 S3c.png|right|frame|Faltungscoder mit&nbsp; $k = 1, \ n = 3, \ m = 3$]]
<b>Faltungscodierer mit $k = 1, \ n = 3, \ m = 3$</b>

Wegen&nbsp; $m = 3$&nbsp; gibt es nun vier Teilmatrizen der jeweiligen Dimension&nbsp; $1 &times; 3$:

::<math>{ \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}.</math>

Damit lautet die resultierende Generatormatrix:

::<math>{ \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},</math>

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

== GF(2)–Beschreibungsformen eines Digitalen Filters ==
<br>
[[File:P ID2605 KC T 3 2 S4 v1.png|right|frame|Digitales Filter in&nbsp; ${\rm GF}(2)$&nbsp; der Ordnung&nbsp; $m$|class=fit]]
Im Kapitel&nbsp; [[Kanalcodierung/Grundlagen_der_Faltungscodierung#Rate.E2.80.931.2F2.E2.80.93Faltungscodierer_.282.29| Grundlagen der Faltungscodierung]]&nbsp; wurde bereits darauf hingewiesen, 
*dass ein Rate&nbsp; $1/n$&ndash;Faltungscodierer durch mehrere Digitale Filter realisiert werden kann, 
*wobei die Filter parallel mit der gleichen Eingangsfolge&nbsp; $\underline{u}$&nbsp; arbeiten. 


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


Die Grafik ist wie folgt zu interpretieren:
*Das Filter besitzt die Impulsantwort&nbsp; $\underline{g} = (g_0, g_1, g_2, \ \text{...} \ , g_m)$.
* Für alle Filterkoeffizienten $($mit den Indizes&nbsp; $0 &#8804; l &#8804; m)$&nbsp; gilt: &nbsp; $g_l &#8712; {\rm GF}(2) = \{0, 1\}$.<br>

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

::<math>x_i = \sum_{l = 0}^{m} g_l \cdot u_{i-l} \hspace{0.05cm}.</math>

*Dies entspricht der (zeitdiskreten)&nbsp; [[Signal_Representation/Faltungssatz_und_Faltungsoperation#Faltung_im_Zeitbereich| Faltungsoperation]]&nbsp; (englisch: &nbsp;<i>Convolution</i>&nbsp;), gekennzeichnet durch einen Stern. Damit kann für die gesamte Ausgangssequenz geschrieben werden:

::<math>\underline{x} = \underline{u} * \underline{g}\hspace{0.05cm}.</math>

*Wesentlicher Unterschied gegenüber dem Kapitel&nbsp; [[Theory_of_Stochastic_Signals/Digitale_Filter| Digitale Filter]]&nbsp; im Buch &bdquo;Stochastische Signaltheorie&rdquo; ist die Modulo&ndash;2&ndash;Addition&nbsp; $(1 + 1 = 0)$&nbsp; anstelle der herkömmlichen Addition&nbsp; $(1 + 1 = 2)$.<br><br>

[[File:P ID2606 KC T 3 2 S4b.png|right|frame|Digitales Filter mit Impulsantwort&nbsp; $(1, 0, 1, 1)$]] 
{{GraueBox|TEXT=  
$\text{Beispiel 3:}$&nbsp;  
Die Impulsantwort des dargestellten Digitalen Filters dritter Ordnung lautet: &nbsp; $\underline{g} = (1, 0, 1, 1)$.
*Die Eingangssequenz dieses Filters sei zeitlich unbegrenzt: &nbsp; $\underline{u} = (1, 1, 0, 0, 0, \ \text{ ...})$.<br>

*Damit ergibt sich die (unendliche) Ausgangssequenz&nbsp; $\underline{x}$&nbsp; im binären Galoisfeld &nbsp; &#8658; &nbsp; ${\rm GF(2)}$:

::<math>\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})</math>
::<math>\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}.</math>

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

::<math>\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}.</math>}}<br>

Zeitdiskrete Signale kann man aber auch durch Polynome bezüglich einer Dummy&ndash;Variablen repräsentieren.<br>

{{BlaueBox|TEXT=  
$\text{Definition:}$&nbsp;  Die zum zeitdiskreten Signal&nbsp; $\underline{x} = (x_0, x_1, x_2, \ \text{...})$&nbsp; gehörige&nbsp; $D$<b>&ndash;Transformierte</b>&nbsp; lautet:

::<math>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}.</math>

Für diese spezielle Transformation in einen Bildbereich verwenden wir auch folgende Notation, wobei &bdquo;$D$&rdquo; für&nbsp; ''Delay Operator''&nbsp; steht:

::<math>\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}.</math>}}<br>

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

::<math>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}.</math>


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

::<math>\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},</math>

::<math>\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}.</math>

{{BlaueBox|TEXT=  
$\text{Satz:}$&nbsp;  Wie bei allen Spektraltransformationen gilt auch bei der&nbsp; $D$&ndash;Transformation im Bildbereich die&nbsp; <b>Multiplikation</b>, da die (diskreten) Zeitsignale&nbsp; $\underline{u}$&nbsp; und&nbsp; $\underline{g}$&nbsp; durch die&nbsp; <b>Faltung</b>&nbsp; verknüpft sind:

::<math>\underline{x} = \underline{u} * \underline{g} \quad
\circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad
X(D) = U(D) \cdot G(D) \hspace{0.05cm}.</math>

Man bezeichnet &ndash; wie in der&nbsp; [[Linear_and_Time_Invariant_Systems/Systembeschreibung_im_Frequenzbereich#.C3.9Cbertragungsfunktion_-_Frequenzgang| Systemtheorie]]&nbsp; allgemein üblich &ndash; auch die&nbsp; $D$&ndash;Transformierte&nbsp; $G(D)$&nbsp; der Impulsantwort&nbsp; $\underline{g}$&nbsp; als&nbsp; '''Übertragungsfunktion'''&nbsp; (englisch: &nbsp; <i>Transfer Function</i>). Der (recht einfache)&nbsp; $\rm Beweis$&nbsp; dieses wichtigen Ergebnisses finden Sie in der Angabe zur&nbsp; [[Aufgaben:3.3Z_Faltung_und_D%E2%80%93Transformation|Aufgabe 3.3Z]].}}<br>

[[File:P ID2607 KC T 3 2 S4b.png|right|frame|Digitales Filter mit Impulsantwort&nbsp; $(1, 0, 1, 1)$]] 
{{GraueBox|TEXT=  
$\text{Beispiel 4:}$&nbsp;  Wir betrachten wieder die zeitdiskreten Signale 

::<math>\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},</math>

::<math>\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}.</math>

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

::<math>X(D) = U(D) \cdot G(D) =  (1+D) \cdot (1+ D^2 + D^3) </math>
::<math>\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}.</math>

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

::<math>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}.</math>}}<br>

== Anwendung der D–Transformation auf Rate–1/''n''–Faltungscoder ==
<br>
Wir wenden nun die Ergebnisse der letzten Seite auf einen Faltungscoder an, wobei wir uns zunächst auf den Sonderfall&nbsp; $k = 1$&nbsp; beschränken. 
*Ein solcher&nbsp; $(n, \ k = 1)$&ndash;Faltungscode lässt sich mit&nbsp; $n$&nbsp; Digitalen  Filtern realisieren, die auf der gleichen Informationssequenz&nbsp; $\underline{u}$&nbsp; parallel arbeiten. 
*Die Grafik zeigt die Anordnung für den Codeparameter&nbsp; $n = 2$ &nbsp; &#8658; &nbsp; Coderate $R = 1/2$.<br>


[[File:P ID2608 KC T 3 2 S5 v1.png|center|frame|Zwei parallel arbeitende Filter, jeweils mit Ordnung&nbsp; $m$|class=fit]]

Die folgenden Gleichungen gelten für beide Filter gleichermaßen, wobei für das obere Filter&nbsp; $j = 1$&nbsp; und für das untere Filter&nbsp; $j = 2$&nbsp; zu setzen ist:
*Die&nbsp; <b>Impulsantworten</b>&nbsp; der beiden Filter ergeben sich zu

::<math>\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}.</math>

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

::<math>\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}.</math>

*Für die&nbsp; $D$<b>&ndash;Transformierten</b>&nbsp; der Ausgangssequenzen gilt:

::<math>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}.</math>

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

{{BlaueBox|TEXT=  
$\text{Definition:}$&nbsp;  Die&nbsp; $D$<b>&ndash;Übertragungsfunktionen</b>&nbsp; der&nbsp; $n$&nbsp; parallel angeordneten Digitalen Filter werden im Vektor&nbsp; $\underline{G}(D)$&nbsp; zusammengefasst:

::<math>\underline{G}(D) = \left ( G^{(1)}(D), G^{(2)}(D), \hspace{0.05cm}\text{...}\hspace{0.1cm}, G^{(n)} (D) \right )\hspace{0.05cm}.</math>

*Der Vektor&nbsp; $\underline{X}(D)$&nbsp; beinhaltet die&nbsp; $D$<b>&ndash;Transformierten</b>&nbsp; der&nbsp; $n$&nbsp; Codesequenzen&nbsp; $\underline{x}^{(1)}, \underline{x}^{(2)}, \ \text{...} \ , \underline{x}^{(n)}$:

::<math>\underline{X}(D) = \left ( X^{(1)}(D), X^{(2)}(D), \hspace{0.05cm}\text{...}\hspace{0.1cm}, X^{(n)} (D) \right )\hspace{0.05cm}.</math>

*Damit erhält man die folgende Vektorgleichung:

::<math>\underline{X}(D) = U(D) \cdot \underline{G}(D)\hspace{0.05cm}.</math>

*Aufgrund des Codeparameters&nbsp; $k = 1$&nbsp; ist&nbsp; $U(D)$&nbsp; hier keine vektorielle Größe.}}<br>

[[File:P ID2609 KC T 3 2 S5b.png|right|frame|Faltungscoder mit&nbsp; $n = 2, \ k = 1,\  m = 2$]] 
{{GraueBox|TEXT=  
$\text{Beispiel 5:}$&nbsp; 
Wir betrachten den Faltungscodierer mit den Codeparametern&nbsp; $n = 2, \ k = 1, \ m = 2$. Für diesen gilt:

::<math>\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},</math>
::<math>\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 </math>
::<math>\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}.</math>

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

::<math>\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}</math>

wobei

::<math>{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</math>

::<math>\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},</math>

::<math>{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</math>

::<math>\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}.</math>

Das gleiche Ergebnis haben wir in der&nbsp; [[Aufgaben:3.1Z_Faltungscodes_der_Rate_1/2|Aufgabe 3.1Z]]&nbsp; auf anderem Wege erhalten. Nach dem Multplexen der beiden Stränge erhält man wieder: &nbsp; 
:$$\underline{x} = (11, 10, 00, 01, 01, 11, 00, 00, \hspace{0.05cm} \text{...} \hspace{0.05cm}).$$}}<br>

== Übertragungsfunktionsmatrix – Transfer Function Matrix ==
<br>
[[File:P ID2616 KC T 3 2 S6b v1.png|right|frame|Allgemeiner&nbsp; $(n, \ k)$&ndash;Faltungscoder |class=fit]]
Wir haben gesehen, dass ein Faltungscode der Rate&nbsp; $1/n$&nbsp; sich am kompaktesten als Vektorgleichung im&nbsp; $D$&ndash;transformierten Bereich beschreiben  lässt: &nbsp; $\underline{X}(D) = U(D) \cdot \underline{G}(D)$. 

Nun erweitern wir das Resultat auf Faltungscodierer mit mehr als einem Eingang &nbsp; &#8658; &nbsp; $k  &#8805; 2$ &nbsp;(siehe Grafik).<br>

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

::<math>\underline{X}(D) = \underline{U}(D) \cdot { \boldsymbol{\rm G}}(D)\hspace{0.05cm}.</math>
<br clear=all>
Dazu sind folgende Maßnahmen erforderlich:
*Aus der skalaren Funktion&nbsp; $U(D)$&nbsp; wird der Vektor&nbsp; $\underline{U}(D) = (U^{(1)}(D), \ U^{(2)}(D), \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ U^{(k)}(D))$.<br>

*Aus dem Vektor&nbsp; $\underline{G}(D)$&nbsp; wird die&nbsp; $k &times; n$&ndash;'''Übertragungsfunktionsmatrix'''&nbsp; $\mathbf{G}(D)$&nbsp; (englisch: &nbsp; <i>Transfer Function Matrix</i>&nbsp; oder&nbsp; <i>Polynomial Generator Matrix</i>):

::<math>{\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}.</math>

*Jedes der&nbsp; $k \cdot n$&nbsp; Matrixelemente&nbsp; $G_i^{(j)}(D)$&nbsp; mit&nbsp; $1 &#8804; i &#8804; k,\ \ 1 &#8804; j &#8804; n$&nbsp; ist ein Polynom über der Dummy&ndash;Variablen&nbsp; $D$&nbsp; im Galoisfeld&nbsp; ${\rm GF}(2)$, maximal vom Grad&nbsp; $m$, wobei&nbsp; $m$&nbsp; das Gedächtnis angibt.<br>

*Für die obige&nbsp; <i>Übertragungsfunktionsmatrix</i>&nbsp; kann mit den zu Beginn dieses Kapitels definierten&nbsp; [[Kanalcodierung/Algebraische_und_polynomische_Beschreibung#Definition_und_Interpretation_der_Teilmatrizen_G0.2C_..._.2C_Gm| Teilmatrizen]]&nbsp; $\mathbf{G}_0, \ \text{...} \ , \mathbf{G}_m$&nbsp; auch geschrieben werden $($als Index verwenden wir wieder  &nbsp;$l)$:

::<math>{\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}.</math>

[[File:P ID2617 KC T 3 1 S4 v1.png|right|frame|Faltungscoder mit&nbsp; $k = 2, \ n = 3, \ m = 1$]] 
{{GraueBox|TEXT=  
$\text{Beispiel 6:}$&nbsp; 
Wir betrachten den&nbsp; $(n = 3, \ k = 2, \ m = 1)$&ndash;Faltungscoder, dessen Teilmatrizen bereits im&nbsp; [[Kanalcodierung/Algebraische_und_polynomische_Beschreibung#Aufteilung_der_Generatormatrix_in_Teilmatrizen| $\text{Beispiel 1}$]]&nbsp; wie folgt ermittelt wurden:

::<math>{ \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>

Wegen&nbsp; $m = 1$&nbsp; existieren keine Teilmatrizen für&nbsp; $l &#8805; 2$. Damit lautet die  Übertragungsfunktionsmatrix:

::<math>{\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}.</math>

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

::<math>\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},</math>
::<math>\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}.</math>

Daraus folgt für den Vektor der&nbsp; $D$&ndash;Transformierten am Coderausgang:

::<math>\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}.</math>

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

::<math>{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</math>

:::<math>\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},</math>

::<math>{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</math>

:::<math>\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},</math>

::<math>{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</math>

:::<math>\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}.</math>

Die gleichen Ergebnisse haben wir auf anderen Wegen bereits in vorherigen Beispielen erhalten: 
* im&nbsp;  [[Kanalcodierung/Grundlagen_der_Faltungscodierung#Faltungscodierer_mit_zwei_Eing.C3.A4ngen|$\text{Beispiel 4}$]]&nbsp; des Kapitels &bdquo;Grundlagen der Faltungscodierung&rdquo;,<br>

*im&nbsp;  [[Kanalcodierung/Algebraische_und_polynomische_Beschreibung#Generatormatrix_eines_Faltungscodierers_mit_Ged.C3.A4chtnis_m| $\text{Beispiel 2}$]]&nbsp; des aktuellen Kapitels.}}<br>

== Systematische Faltungscodes ==
<br>
Die Polynomrepräsentation anhand der Übertragungsfunktionsmtrix&nbsp; $\mathbf{G}(D)$&nbsp; ermöglicht Einblicke in die Struktur eines Faltungscodes. 

*Beispielsweise erkennt man anhand dieser&nbsp; $k &times; n$&ndash;Matrix, ob es sich um einen&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes| systematischen Code]]&nbsp; handelt. 
*Darunter versteht man einen Code, bei dem die Codesequenzen&nbsp; $\underline{x}^{(1)}, \ \text{...} \ , \ \underline{x}^{(k)}$&nbsp; mit den Informationssequenzen&nbsp; $\underline{u}^{(1)}, \ \text{...} \ , \ \underline{u}^{(k)}$&nbsp; identisch sind. 

*Die Grafik zeigt beispielhaft einen systematischen&nbsp; $(n = 4, \ k = 3)$&ndash;Faltungscode.<br>


[[File:P ID2611 KC T 3 2 S7 v2.png|center|frame|Systematischer Faltungscode mit&nbsp; $k = 3, \ n = 4$|class=fit]]

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

::<math>{\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}.</math>

Hierbei ist folgende Nomenklatur verwendet:
*$\mathbf{I}_k$&nbsp; bezeichnet eine diagonale Einheitsmatrix der Dimension&nbsp; $k &times; k$.<br>

*$\mathbf{P}(D)$&nbsp; ist eine&nbsp; $k &times; (n -k)$&ndash;Matrix, wobei jedes Matrixelement ein Polynom in&nbsp; $D$&nbsp; beschreibt.<br><br>

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

::<math>{\boldsymbol{\rm G} }_{\rm sys}(D) = \begin{pmatrix}
		1 & 0 & 1+D^2\\
		0 & 1 & 1+D
\end{pmatrix}\hspace{0.05cm}.</math>

Andere systematische Faltungscodes mit gleichem&nbsp; $n$&nbsp; und gleichem&nbsp; $k$&nbsp; unterscheiden sich demgegenüber nur durch die beiden Matrixelemente in der letzten Spalte.}}<br>


== Äquivalenter systematischer Faltungscode ==
<br>
Zu jedem&nbsp; $(n, \ k)$&ndash;Faltungscode mit Matrix&nbsp; $\mathbf{G}(D)$&nbsp; gibt es einen&nbsp; ''äquivalenten systematischen Code'', dessen&nbsp; $D$&ndash;Matrix wir mit&nbsp; $\mathbf{G}_{\rm sys}(D)$ benennen.<br>

[[File:P ID2622 KC T 3 2 S7 v1.png|center|frame|Unterteilung von&nbsp; $\mathbf{G}(D)$&nbsp; in&nbsp; $\mathbf{T}(D)$&nbsp; und&nbsp; $\mathbf{Q}(D)$|class=fit]]

Um von der Übertragungsfunktionsmatrix&nbsp; $\mathbf{G}(D)$&nbsp; zur Matrix&nbsp; $\mathbf{G}_{\rm sys}(D)$&nbsp; des äquivalenten systematischen Faltungscodes zu kommen, geht man gemäß  Grafik wie folgt vor:
*Man unterteilt die&nbsp; $k &times; n$&ndash;Matrix&nbsp; $\mathbf{G}(D)$&nbsp; in eine quadratische Matrix&nbsp; $\mathbf{T}(D)$&nbsp; mit&nbsp; $k$&nbsp; Zeilen und&nbsp; $k$&nbsp; Spalten und bezeichnet den Rest mit&nbsp; $\mathbf{Q}(D)$.

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

::<math>{\boldsymbol{\rm G}}_{\rm sys}(D)= {\boldsymbol{\rm T}}^{-1}(D) \cdot {\boldsymbol{\rm G}}(D) \hspace{0.05cm}.</math>

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

::<math>{\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}</math>

[[File:P ID2613 KC T 3 2 S1 neu.png|right|frame|Faltungscodierer der Rate&nbsp; $2/3$]] 
{{GraueBox|TEXT=  
$\text{Beispiel 8:}$&nbsp; 
Der auf den letzten Seiten schon häufiger betrachtete Coder der Rate&nbsp; $2/3$&nbsp; ist nicht systematisch, weil zum Beispiel&nbsp; $\underline{x}^{(1)} &ne; \underline{u}^{(1)}, \ \underline{x}^{(2)} &ne; \underline{u}^{(2)}$&nbsp; gilt (siehe nebenstehende Coderschaltung).<br>

Man erkennt dies aber auch anhand der Übertragungsfunktionsmatrix:

::<math>{\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 ]</math>

::<math>\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}.</math>

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

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

::<math>{\boldsymbol{\rm T} }^{-1}(D) = \frac{1}{1+D+D^2} \cdot \begin{pmatrix}
		1 & D\\
		D & 1+D 
\end{pmatrix}\hspace{0.05cm}.</math>

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

::<math>{\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} </math>

::<math>\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} </math>

::<math>\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}. </math>

Zu klären ist noch, wie das Filter einer solchen gebrochen&ndash;rationalen Übertragungsfunktion aussieht.}}<br>

== Filterstruktur bei gebrochen–rationaler Übertragungsfunktion ==
<br>
[[File:P ID2619 KC T 3 2 S8 v1.png|right|frame|Rekursives Filter zur Realisierung von&nbsp; $G(D) = A(D)/B(D)$|class=fit]]
Hat eine Übertragungsfunktion die Form&nbsp; $G(D) = A(D)/B(D)$, so bezeichnet man das zugehörige Filter  als <i>rekursiv</i>. 

Bei einem rekursiven Faltungscodierer mit dem Gedächtnis&nbsp; $m$&nbsp; kann für die beiden Polynome&nbsp; $A(D)$&nbsp; und&nbsp; $B(D)$&nbsp; allgemein geschrieben werden:
::<math>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},</math>
::<math>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}.</math>

Die Grafik zeigt die entsprechende Filterstruktur in der so genannten&nbsp; <i>Controller Canonical Form</i>:<br>
*Die Koeffizienten&nbsp; $a_0, \ \text{...} \ , \ a_m$&nbsp; beschreiben den Vorwärtszweig.
* Die Koeffizienten&nbsp; $b_1, \ \text{...} \ , \ b_m$&nbsp; bilden eine Rückkopplung. 
*Alle Koeffizienten sind binär, also&nbsp; $1$&nbsp; (durchgehende Verbindung) oder&nbsp; $0$&nbsp; (fehlende Verbindung).
<br clear=all>
[[File:P_ID2620__KC_T_3_2_S8b_neu.png|right|frame|Filter:  &nbsp;$G(D) = (1+D^2)/(1+D +D^2)$|class=fit]]
{{GraueBox|TEXT=  
$\text{Beispiel 9:}$&nbsp; Die rechts skizzierte Filterstruktur lässt sich wie folgt beschreiben:

::<math>x_i  =  w_i + w_{i-2} \hspace{0.05cm},</math>
::<math>w_i =  u_i + w_{i-1}+ w_{i-2}  \hspace{0.05cm}.</math>

Entsprechend gilt für die&nbsp; $D$&ndash;Transformierten:

::<math>X(D) =W(D) + W(D) \cdot D^2 =W(D) \cdot \left ( 1+ D^2 \right ) \hspace{0.05cm},</math> 
::<math>W(D) = \hspace{0.08cm} U(D) + W(D) \cdot D+ W(D) \cdot D^2</math> 
::<math>\Rightarrow \hspace{0.3cm}
U(D) = W(D) \cdot \left ( 1+ D + D^2 \right ) \hspace{0.05cm}.</math>

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

::<math>G(D) = \frac{X(D)}{U(D)} = \frac{1+D^2}{1+D+D^2} \hspace{0.05cm}. </math>

Im&nbsp; [[Kanalcodierung/Algebraische_und_polynomische_Beschreibung#.C3.84quivalenter_systematischer_Faltungscode| $\text{Beispiel 8}$]]&nbsp; zum äquivalenten systematischen Faltungscode hat sich im unteren Zweig genau dieser Ausdruck ergeben.}}<br>

== Aufgaben zum Kapitel==
<br>
[[Aufgaben:Aufgabe_3.2:_G–Matrix_eines_Faltungscodierers|Aufgabe 3.2: G–Matrix eines Faltungscodierers]]

[[Aufgaben:Aufgabe_3.2Z:_(3,_1,_3)–Faltungscodierer|Aufgabe 3.2Z: (3, 1, 3)–Faltungscodierer]]

[[Aufgaben:Aufgabe_3.3:_Codesequenzberechnung_über_U(D)_und_G(D)|Aufgabe 3.3: Codesequenzberechnung über U(D) und G(D)]]

[[Aufgaben:Aufgabe_3.3Z:_Faltung_und_D–Transformation|Aufgabe 3.3Z: Faltung und D–Transformation]]

[[Aufgaben:Aufgabe_3.4:_Systematische_Faltungscodes|Aufgabe 3.4: Systematische Faltungscodes]]

[[Aufgaben:Aufgabe_3.4Z:_Äquivalente_Faltungscodes|Aufgabe 3.4Z: Äquivalente Faltungscodes?]]

[[Aufgaben:Aufgabe_3.5:_Rekursive_Filter_für_GF(2)|Aufgabe 3.5: Rekursive Filter für GF(2)]]

{{Display}}