Kanalcodierung/Grundlagen der Faltungscodierung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(13 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 7: Zeile 7:
  
 
== # ÜBERBLICK ZUM DRITTEN HAUPTKAPITEL # ==
 
== # ÜBERBLICK ZUM DRITTEN HAUPTKAPITEL # ==
 
+
<br>
Dieses dritte Hauptkapitel behandelt '''Faltungscodes''' (englisch: ''Convolutional Codes''), die erstmals 1955 von [https://de.wikipedia.org/wiki/Peter_Elias Peter Elias] beschrieben wurden [Eli55]<ref name='Eli55'>Elias, P.: ''Coding for Noisy Channels''. In: IRE Conv. Rec. Part 4,S. 37-47, 1955.</ref>. Während bei den linearen Blockcodes (siehe [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#.23_.C3.9CBERBLICK_ZUM_ERSTEN_HAUPTKAPITEL_.23|Erstes Hauptkapitel]]) und den Reed–Solomon–Codes (siehe [[Kanalcodierung/Einige_Grundlagen_der_Algebra#.23_.C3.9CBERBLICK_ZUM_ZWEITEN_HAUPTKAPITEL_.23|Zweites Hauptkapitel]]) die Codewortlänge jeweils $n$ ist, basiert die Theorie der Faltungscdes auf „semi–infiniten” Informations– und Codesequenzen. Ebenso liefert die Maximum–Likelihood–Decodierung mittels des Viterbi–Algorithmuses per se die gesamte Sequenz.
+
Dieses dritte Hauptkapitel behandelt&nbsp; '''Faltungscodes'''&nbsp; (englisch: &nbsp;''Convolutional Codes''), die erstmals 1955 von&nbsp; [https://de.wikipedia.org/wiki/Peter_Elias Peter Elias]&nbsp; beschrieben wurden [Eli55]<ref name='Eli55'>Elias, P.: ''Coding for Noisy Channels''. In: IRE Conv. Rec. Part 4,S. 37-47, 1955.</ref>. Während bei den linearen Blockcodes (siehe&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#.23_.C3.9CBERBLICK_ZUM_ERSTEN_HAUPTKAPITEL_.23|Erstes Hauptkapitel]])&nbsp; und den Reed–Solomon–Codes&nbsp; (siehe [[Kanalcodierung/Einige_Grundlagen_der_Algebra#.23_.C3.9CBERBLICK_ZUM_ZWEITEN_HAUPTKAPITEL_.23|Zweites Hauptkapitel]])&nbsp; die Codewortlänge jeweils&nbsp; $n$&nbsp; ist, basiert die Theorie der Faltungscdes auf „semi–infiniten” Informations– und Codesequenzen. Ebenso liefert die Maximum–Likelihood–Decodierung mittels des Viterbi–Algorithmuses per se die gesamte Sequenz.
  
 
Im Einzelnen werden in diesem Kapitel behandelt:
 
Im Einzelnen werden in diesem Kapitel behandelt:
  
*Wichtige ''Definitionen'' für Faltungscodes: Coderate, Gedächtnis, Einflusslänge, freie Distanz
+
*Wichtige ''Definitionen''&nbsp; für Faltungscodes: &nbsp; Coderate, Gedächtnis, Einflusslänge, freie Distanz
*''Gemeinsamkeiten'' und ''Unterschiede'' zu den linearen Blockcodes,
+
*''Gemeinsamkeiten''&nbsp; und ''Unterschiede''&nbsp; zu den linearen Blockcodes,
*''Generatormatrix'' und ''Übertragungsfunktionsmatrix'' eines Faltungscodes,
+
*''Generatormatrix''&nbsp; und ''Übertragungsfunktionsmatrix''&nbsp; eines Faltungscodes,
*''gebrochen–rationale Übertragungsfunktionen'' für systematische Faltungscodes,
+
*''gebrochen–rationale Übertragungsfunktionen''&nbsp; für systematische Faltungscodes,
*Beschreibung mit ''Zustandsübergangsdiagramm'' und ''Trellisdiagramm'',
+
*Beschreibung mit ''Zustandsübergangsdiagramm''&nbsp; und ''Trellisdiagramm'',
*''Terminierung'' und ''Punktierung'' von Faltungscodes,
+
*''Terminierung''&nbsp; und ''Punktierung''&nbsp; von Faltungscodes,
*''Decodierung'' von Faltungscodes ''Viterbi–Algorithmus'',
+
*''Decodierung''&nbsp; von Faltungscodes &nbsp; &nbsp; ''Viterbi–Algorithmus'',
*''Gewichtsfunktionen'' und Näherungen für die ''Bitfehlerwahrscheinlichkeit''.
+
*''Gewichtsfunktionen''&nbsp; und Näherungen für die ''Bitfehlerwahrscheinlichkeit''.
  
  
 
== Voraussetzungen und Definitionen ==
 
== Voraussetzungen und Definitionen ==
 
<br>
 
<br>
Wir betrachten in diesem Kapitel eine unendlich lange binäre Informationssequenz $\underline{u}$ und unterteilen diese in Informationsblöcke $\underline{u}_i$ zu je $k$ Bit. Man kann diesen Sachverhalt wie folgt formalisieren:
+
Wir betrachten in diesem Kapitel eine unendlich lange binäre Informationssequenz&nbsp; $\underline{u}$&nbsp; und unterteilen diese in Informationsblöcke&nbsp; $\underline{u}_i$&nbsp; zu je&nbsp; $k$&nbsp; Bit. Man kann diesen Sachverhalt wie folgt formalisieren:
  
::<math>\underline{\it u} = \left ( \underline{\it u}_1, \underline{\it u}_2, ... \hspace{0.1cm}, \underline{\it u}_i , \text{...} \hspace{0.1cm}\right ) \hspace{0.3cm}{\rm mit}\hspace{0.3cm} \underline{\it u}_i = \left ( u_i^{(1)}, u_i^{(2)}, \text{...} \hspace{0.1cm}, u_i^{(k)}\right )\hspace{0.05cm},</math>
+
::<math>\underline{\it u} = \left ( \underline{\it u}_1, \underline{\it u}_2, \hspace{0.05cm} \text{...} \hspace{0.05cm}, \underline{\it u}_i , \hspace{0.05cm} \text{...} \hspace{0.05cm}\right ) \hspace{0.3cm}{\rm mit}\hspace{0.3cm} \underline{\it u}_i = \left ( u_i^{(1)}, u_i^{(2)}, \hspace{0.05cm} \text{...} \hspace{0.05cm}, u_i^{(k)}\right )\hspace{0.05cm},</math>
  
 
::<math>u_i^{(j)}\in {\rm GF(2)}\hspace{0.3cm}{\rm f\ddot{u}r} \hspace{0.3cm}1 \le j \le k  
 
::<math>u_i^{(j)}\in {\rm GF(2)}\hspace{0.3cm}{\rm f\ddot{u}r} \hspace{0.3cm}1 \le j \le k  
 
\hspace{0.5cm}\Rightarrow \hspace{0.5cm} \underline{\it u}_i \in {\rm GF}(2^k)\hspace{0.05cm}.</math>
 
\hspace{0.5cm}\Rightarrow \hspace{0.5cm} \underline{\it u}_i \in {\rm GF}(2^k)\hspace{0.05cm}.</math>
  
Im Englischen bezeichnet man eine solche Sequenz ohne negative Indizes als <i>semi&ndash;infinite</i>.<br>
+
Im Englischen bezeichnet man eine solche Sequenz ohne negative Indizes als <i>semi&ndash;infinite</i>&nbsp;.<br>
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Definition:}$&nbsp;  Bei einem <b>binären Faltungscode</b> (englisch: <i>Binary Convolutional Code</i>)  wird zum Taktzeitpunkt $i$ ein Codewort $\underline{x}_i$ bestehend aus $n$ Codebits ausgegeben:
+
$\text{Definition:}$&nbsp;  Bei einem&nbsp; <b>binären Faltungscode</b>&nbsp; (englisch: &nbsp;<i>Binary Convolutional Code</i>&nbsp;)  wird zum Zeitpunkt&nbsp; $i$&nbsp; ein Codewort&nbsp; $\underline{x}_i$&nbsp; bestehend aus&nbsp; $n$&nbsp; Codebit ausgegeben:
  
::<math>\underline{\it x}_i = \left ( x_i^{(1)}, x_i^{(2)}, \text{...} \hspace{0.1cm}, x_i^{(n)}\right )\in {\rm GF}(2^n)\hspace{0.05cm}.</math>
+
::<math>\underline{\it x}_i = \left ( x_i^{(1)}, x_i^{(2)}, \hspace{0.05cm} \text{...} \hspace{0.05cm}, x_i^{(n)}\right )\in {\rm GF}(2^n)\hspace{0.05cm}.</math>
  
 
Dieses ergibt sich entsprechend
 
Dieses ergibt sich entsprechend
*den $k$ Bit des aktuellen Informationsblockes $\underline{u}_i$, und<br>
+
*den&nbsp; $k$&nbsp; Bit des aktuellen Informationsblockes&nbsp; $\underline{u}_i$, und<br>
  
*den $m$ vorherigen Informationsblöcken $\underline{u}_{i&ndash;1}, \ ... \ \underline{u}_{i&ndash;m}$.<br>}}<br>
+
*den&nbsp; $m$&nbsp; vorherigen Informationsblöcken&nbsp; $\underline{u}_{i-1}$, ... , $\underline{u}_{i-m}$.<br>}}<br>
  
Die folgende Grafik verdeutlicht diesen Sachverhalt für die Parameter $k = 4, n = 7, m = 2$ und $i = 4$. Die $n = 7$ zum Zeitpunkt $i = 4$ erzeugten Codebits $x_4^{(1)}, \ ... \ , x_4^{(7)}$ können (direkt) von den $k \cdot (m+1) = 12$ rot markierten Informationsbits abhängen und werden durch Modulo&ndash;2&ndash;Additionen erzeugt.<br>
+
[[Datei:P ID2590 KC T 3 1 S1 v1.png|right|frame|Abhängigkeiten bei einem Faltungscodierer mit&nbsp; $m = 2$|class=fit]]
  
[[Datei:P ID2590 KC T 3 1 S1 v1.png|center|frame|Abhängigkeiten bei einem Faltungscodierer mit $m = 2$|class=fit]]
+
Nebenstehende Grafik verdeutlicht diesen Sachverhalt für die Parameter&nbsp; $k = 4, \ n = 7, \ m = 2$&nbsp; und&nbsp; $i = 4$.
  
Gelb eingezeichnet ist zudem ein $(n, k)$&ndash;Faltungscodierer. Zu beachten ist, dass sich der Vektor $\underline{u}_i$ und die Sequenz $\underline{u}^{(i)}$ grundlegend unterscheide:  
+
Die&nbsp; $n = 7$&nbsp; zum Zeitpunkt&nbsp; $i = 4$&nbsp; erzeugten Codebits&nbsp; $x_4^{(1)}$, ... , $x_4^{(7)}$&nbsp; können (direkt) von den&nbsp; $k \cdot (m+1) = 12$&nbsp; rot markierten Informationsbits abhängen und werden durch Modulo&ndash;2&ndash;Additionen erzeugt.<br>
*Während $\underline{u}_i = (u_i^{(1)}, u_i^{(2)}, \ ... \ , u_i^{(k)})$ die $k$ zum Zeitpunkt $i$ parallel anliegenden Informationsbits zusammenfasst,
+
 
* bezeichnet $\underline{u}^i = (u_i^{(i)}$, $u_2^{(i)}, \ ...)$ die (horizontale) Sequenz am $i$&ndash;ten Eingang des Faltungscodierers.  
+
Gelb eingezeichnet ist zudem ein&nbsp; $(n, k)$&ndash;Faltungscodierer. Zu beachten ist, dass sich der Vektor&nbsp; $\underline{u}_i$&nbsp; und die Sequenz&nbsp; $\underline{u}^{(i)}$&nbsp; grundlegend unterscheiden:  
 +
*Während&nbsp; $\underline{u}_i = (u_i^{(1)}, u_i^{(2)}$, ... , $u_i^{(k)})$&nbsp; die&nbsp; $k$&nbsp; zum Zeitpunkt&nbsp; $i$&nbsp; parallel anliegenden Informationsbits zusammenfasst,
 +
* bezeichnet&nbsp; $\underline{u}^i = (u_1^{(i)}$, $u_2^{(i)}, \ \text{...})$&nbsp; die (horizontale) Sequenz am&nbsp; $i$&ndash;ten Eingang des Faltungscodierers.  
  
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
 
$\text{Definitionen bezüglich Faltungscodes:}$&nbsp;   
 
$\text{Definitionen bezüglich Faltungscodes:}$&nbsp;   
*Die <b>Coderrate</b> ergibt sich wie bei den Blockcodes zu $R = k/n$.<br>
+
*Die&nbsp; <b>Coderrate</b>&nbsp; ergibt sich wie bei den Blockcodes zu&nbsp; $R = k/n$.<br>
  
*Man bezeichnet $m$ als das <b>Gedächtnis</b> (englisch: <i>Memory</i>) des Codes und den <i>Convolutional Code</i>  selbst mit ${\rm CC}(n, k, m)$.<br>
+
*Man bezeichnet&nbsp; $m$&nbsp; als das&nbsp; <b>Gedächtnis</b>&nbsp; (englisch: &nbsp;<i>Memory</i>&nbsp;)&nbsp; des Codes und den <i>Convolutional Code</i>&nbsp; selbst mit&nbsp; ${\rm CC} \ (n, k, m)$.<br>
  
*Daraus ergibt sich die <b>Einflusslänge</b> (englisch: <i>Constraint Length</i>) zu $\nu = m + 1$.<br>
+
*Daraus ergibt sich die&nbsp; <b>Einflusslänge</b>&nbsp; (englisch: &nbsp;<i>Constraint Length</i>&nbsp;) zu&nbsp; $\nu = m + 1$.<br>
  
*Für $k > 1$ gibt man diese Parameter oft auch in Bit an: $m_{\rm Bit} = m \cdot k$ bzw. $\nu_{\rm Bit} = (m + 1) \cdot k$.<br>}}
+
*Für&nbsp; $k > 1$&nbsp; gibt man diese Parameter oft auch in Bit an: &nbsp; $m_{\rm Bit} = m \cdot k$ &nbsp; &nbsp;bzw.&nbsp; &nbsp; $\nu_{\rm Bit} = (m + 1) \cdot k$.<br>}}
  
 
== Gemeinsamkeiten und Unterschiede gegenüber Blockcodes ==
 
== Gemeinsamkeiten und Unterschiede gegenüber Blockcodes ==
 
<br>
 
<br>
Aus der [[Kanalcodierung/Grundlagen_der_Faltungscodierung#Voraussetzungen_und_Definitionen| Definition]] auf der vorherigen Seite ist ersichtlich, dass ein binärer Faltungscode mit $m = 0$ (also ohne Gedächtnis) identisch wäre mit einem binären Blockcode wie in Hauptkapitel 1 beschrieben. Wir schließen diesen Grenzfall aus und setzen deshalb für das Folgende stets voraus:
+
Aus der&nbsp; [[Kanalcodierung/Grundlagen_der_Faltungscodierung#Voraussetzungen_und_Definitionen| Definition]]&nbsp; auf der vorherigen Seite ist ersichtlich, dass ein binärer Faltungscode mit&nbsp; $m = 0$&nbsp; (also ohne Gedächtnis) identisch wäre mit einem binären Blockcode wie in ersten Hauptkapitel beschrieben. Wir schließen diesen Grenzfall aus und setzen deshalb für das Folgende stets voraus:
*Das Gedächtnis $m$ sei größer oder gleich $1$.<br>
+
*Das Gedächtnis&nbsp; $m$&nbsp; sei größer oder gleich&nbsp; $1$.<br>
  
*Die Einflusslänge $\nu$ sei größer oder gleich $2$.<br><br>
+
*Die Einflusslänge&nbsp; $\nu$&nbsp; sei größer oder gleich&nbsp; $2$.<br><br>
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 1:}$&nbsp; Bei einem $(7, 4)$&ndash;Blockcode hängt das Codewort $\underline {x}_4$ nur vom Informationswort $\underline{u}_4$ ab, nicht jedoch von $\underline{u}_2$ und $\underline{u}_3$, wie bei dem [[Kanalcodierung/Grundlagen_der_Faltungscodierung#Voraussetzungen_und_Definitionen| beispielhaften Faltungscodes]] (mit $m = 2$) auf der letzten Seite.<br>
+
$\text{Beispiel 1:}$&nbsp; Bei einem&nbsp; $(7, 4)$&ndash;Blockcode hängt das Codewort&nbsp; $\underline {x}_4$&nbsp; nur vom Informationswort&nbsp; $\underline{u}_4$&nbsp; ab, nicht jedoch von&nbsp; $\underline{u}_2$&nbsp; und&nbsp; $\underline{u}_3$, wie bei dem&nbsp; [[Kanalcodierung/Grundlagen_der_Faltungscodierung#Voraussetzungen_und_Definitionen| beispielhaften Faltungscodes]]&nbsp; $($mit&nbsp; $m = 2)$&nbsp; auf der letzten Seite.<br>
  
[[Datei:P ID2592 KC T 3 1 S2 v2.png|center|frame|Abhängigkeiten bei einem $(7, 4)$–Blockcode zum Zeitpunkt $i = 4$|class=fit]]
+
[[Datei:P ID2592 KC T 3 1 S2 v2.png|right|frame|Abhängigkeiten bei einem&nbsp; $(7, 4)$–Blockcode zum Zeitpunkt&nbsp; $i = 4$|class=fit]]
  
Gilt beispielsweise $x_4^{(1)} = u_4^{(1)}, \ x_4^{(2)} = u_4^{(2)}, \ x_4^{(3)} = u_4^{(3)}, \ x_4^{(4)} = u_4^{(4)}$ sowie
+
Gilt beispielsweise  
 +
:$$x_4^{(1)} = u_4^{(1)}, \ x_4^{(2)} = u_4^{(2)},$$
 +
:$$x_4^{(3)} = u_4^{(3)}, \ x_4^{(4)} = u_4^{(4)}$$
 +
sowie
 +
:$$x_4^{(5)} = u_4^{(1)}+ u_4^{(2)}+u_4^{(3)}\hspace{0.05cm},$$
 +
:$$x_4^{(6)} = u_4^{(2)}+ u_4^{(3)}+u_4^{(4)}\hspace{0.05cm},$$
 +
:$$x_4^{(7)} = u_4^{(1)}+ u_4^{(2)}+u_4^{(4)}\hspace{0.05cm},$$
  
::<math>x_4^{(5)} = u_4^{(1)}+ u_4^{(2)}+u_4^{(3)}\hspace{0.05cm} ,\hspace{0.3cm}
+
so handelt es sich um einen so genannten&nbsp;  [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes| systematischen Hamming&ndash;Code]]&nbsp; $\text{HS (7, 4, 3)}$. In der Grafik sind diese speziellen Abhängigkeiten für&nbsp; $x_4^{(1)}$&nbsp; und&nbsp; $x_4^{(7)}$&nbsp; rot eingezeichnet.}}<br>
x_4^{(6)} = u_4^{(2)}+ u_4^{(3)}+u_4^{(4)}\hspace{0.05cm} ,\hspace{0.3cm}
 
x_4^{(7)} = u_4^{(1)}+ u_4^{(2)}+u_4^{(4)}\hspace{0.05cm} ,</math>
 
  
so handelt es sich um einen so genannten  [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes_.282.29| systematischen Hamming&ndash;Code]] $(7, 4, 3)$. In der Grafik sind diese speziellen Abhängigkeiten für $x_4^{(1)}$ und $x_4^{(7)}$ rot eingezeichnet.}}<br>
+
In gewisser Weise könnte man auch einen&nbsp; $(n, k)$&ndash;Faltungscode mit Gedächtnis&nbsp; $m &#8805; 1$&nbsp; als Blockcode interpretieren, dessen Codeparameter&nbsp; $n\hspace{0.05cm}' \gg n$&nbsp; und&nbsp; $k\hspace{0.05cm}' \gg k$&nbsp; allerdings sehr viel größere Werte annehmen müssten als die des vorliegenden Faltungscodes. Aufgrund der großen Unterschiede in der Beschreibung, in den Eigenschaften und insbesondere bei der Decodierung betrachten wir aber Faltungscodes in diesem Lerntutorial als etwas völlig Neues. Hierfür sprechen folgende Gründe:
 +
*Ein Blockcodierer setzt Informationsworte der Länge&nbsp; $k$&nbsp; Bit blockweise in Codeworte mit je&nbsp; $n$&nbsp; Bit um. Der Blockcode ist dabei um so leistungsfähiger, je größer seine Codewortlänge&nbsp; $n$&nbsp; ist. Bei gegebener Coderate&nbsp; $R = k/n$&nbsp; erfordert dies auch eine große Informationswortlänge&nbsp; $k$.<br>
  
In gewisser Weise könnte man auch einen $(n, k)$&ndash;Faltungscode mit Gedächtnis $m &#8805; 1$ als Blockcode interpretieren, dessen Codeparameter $n\hspace{0.05cm}' \gg n$ und $k\hspace{0.05cm}' \gg k$ allerdings sehr viel größere Werte annehmen müssten als die des vorliegenden Faltungscodes. Aufgrund der großen Unterschiede in der Beschreibung, in den Eigenschaften und insbesondere bei der Decodierung betrachten wir aber Faltungscodes in diesem Lerntutorial als etwas völlig Neues. Hierfür sprechen folgende Gründe:
+
*Dagegen wird die Korrekturfähigkeit eines Faltungscodes im wesentlichen durch sein Gedächtnis&nbsp; $m$&nbsp; bestimmt. Die Codeparameter&nbsp; $k$&nbsp; und&nbsp; $n$&nbsp; werden hier meist sehr klein gewählt&nbsp; $(1, \ 2, \ 3, \ \text{...})$. Von praktischer Bedeutung sind somit nur ganz wenige und zudem sehr einfache Faltungscodes.<br>
*Ein Blockcodierer setzt Informationsworte der Länge $k$ Bit blockweise in Codeworte mit je $n$ Bit um. Der Blockcode ist dabei um so leistungsfähiger, je größer seine Codewortlänge $n$ ist. Bei gegebener Coderate $R = k/n$ erfordert dies auch eine große Informationswortlänge $k$.<br>
 
  
*Dagegen wird die Korrekturfähigkeit eines Faltungscodes im wesentlichen durch sein Gedächtnis $m$ bestimmt. Die Codeparameter $k$ und $n$ werden hier meist sehr klein gewählt $(1, \ 2, \ 3, \ \text{...})$. Von praktischer Bedeutung sind somit nur ganz wenige und zudem sehr einfache Faltungscodes.<br>
+
*Auch schon bei kleinen Werten für&nbsp; $k$&nbsp; und&nbsp; $n$&nbsp; überführt ein Faltungscoder eine ganze Sequenz von Informationsbits&nbsp; $(k\hspace{0.05cm}' &#8594; &#8734;)$&nbsp; in eine sehr lange Sequenz von Codebits&nbsp; $(n\hspace{0.05cm}' = k\hspace{0.05cm}'/R)$. Ein solcher Code bietet somit oft ebenfalls eine große Korrekturfähigkeit.<br>
  
*Auch schon bei kleinen Werten für $k$ und $n$ überführt ein Faltungscoder eine ganze Sequenz von Informationsbits $(k\hspace{0.05cm}' &#8594; &#8734;)$ in eine sehr lange Sequenz von Codebits $(n\hspace{0.05cm}' = k\hspace{0.05cm}'/R)$. Ein solcher Code bietet somit oft ebenfalls eine große Korrekturfähigkeit.<br>
+
*Es gibt effiziente Faltungsdecoder, zum Beispiel den&nbsp; [[Kanalcodierung/Decodierung_von_Faltungscodes#Viterbi.E2.80.93Algorithmus.2C_basierend_auf_Korrelation_und_Metriken| Viterbi&ndash;Algorithmus]]&nbsp; und den&nbsp; [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#BCJR.E2.80.93Decodierung:_Vorw.C3.A4rts.E2.80.93R.C3.BCckw.C3.A4rts.E2.80.93Algorithmus| BCJR&ndash;Algorithmus]], die Zuverlässigkeitsinformationen über den Kanal &nbsp; &rArr; &nbsp; ''Soft&ndash;Decision&ndash;Input''&nbsp; verarbeiten können und Zuverlässigkeitsinformation über das Decodierergebnis &nbsp; &rArr; &nbsp; <i>Soft&ndash;Decision&ndash;Output</i>&nbsp; liefern.<br>
 
 
*Es gibt effiziente Faltungsdecoder &nbsp; &#8658; &nbsp; zum Beispiel den [[Kanalcodierung/Decodierung_von_Faltungscodes#Viterbi.E2.80.93Algorithmus.2C_basierend_auf_Korrelation_und_Metriken_.281.29| Viterbi&ndash;Algorithmus]] und den [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#BCJR.E2.80.93Decodierung:_Vorw.C3.A4rts.E2.80.93R.C3.BCckw.C3.A4rts.E2.80.93Algorithmus| BCJR&ndash;Algorithmus]], die Zuverlässigkeitsinformationen über den Kanal &nbsp; &rArr; &nbsp; ''Soft&ndash;Decision&ndash;Input'' verarbeiten können und Zuverlässigkeitsinformation über das Decodierergebnis &nbsp; &rArr; &nbsp; <i>Soft&ndash;Decision&ndash;Output</i>  liefern.<br>
 
  
 
== Rate–1/2–Faltungscodierer ==
 
== Rate–1/2–Faltungscodierer ==
 
<br>
 
<br>
Die Grafik zeigt einen $(n = 2, \ k = 1)$&ndash;Faltungscodierer. Zum Taktzeitpunkt $i$ liegt das Informationsbit $u_i$ am Codereingang an und es wird ein 2&ndash;Bit&ndash;Codeblock $\underline{x}_i = (x_i^{(1)}, \ x_i^{(2)})$ ausgegeben.<br>
+
[[Datei:P ID2593 KC T 3 1 S3a v1.png|right|frame|Faltungscoder&nbsp; $(n = 2, \hspace{0.05cm} k = 1)$&nbsp; für ein Informationsbit&nbsp; $u_i$|class=fit]]
 +
<i>Vorbemerkung</i>: &nbsp; Die beiden Begriffe &bdquo;Faltungscodierer&rdquo; und &bdquo;Faltungscoder&rdquo; werden in unserem Lerntutorial synonym verwendet und können beliebig ausgetauscht werden.
 +
*Beide Begriffe bezeichnen die konkrete Umsetzung einer Informationssequenz&nbsp; $\underline{u}$&nbsp; in eine Codesequenz&nbsp; $\underline{x}$.<br>
  
[[Datei:P ID2593 KC T 3 1 S3a v1.png|center|frame|Faltungscoder $(k = 1, \ n = 2)$ für ein Informationsbit $u_i$|class=fit]]<br>
 
  
Unter Berücksichtigung der (halb&ndash;unendlich) langen Informationssequenz $\underline{u}$ ergibt sich folgendes Modell:<br>
+
Die Begriffe &bdquo;Faltungscodierer&rdquo; und &bdquo;Faltungscode&rdquo; sollte man allerdings nicht verwechseln.
 +
*Unter einem Faltungscode&nbsp; ${\rm CC} \ (n, \ k, \ m)$ &nbsp; &#8658; &nbsp; $R = k/n$&nbsp; versteht man die Menge aller möglichen Codesequenzen&nbsp; $\underline{x}$, die mit diesem Code unter Berücksichtigung aller möglichen Informationssequenzen&nbsp; $\underline{u}$&nbsp; (am Eingang) generiert werden kann.
 +
*Es gibt verschiedene Faltungscodierer, die den gleichen Faltungscode realisieren.<br>
  
[[Datei:P ID2594 KC T 3 1 S3b v1.png|center|frame|Faltungscoder $(k = 1, \ n = 2)$ für die Informationssequenz $\underline{u}$|class=fit]]<br>
 
  
Um aus einem einzigen Informationsbit $u_i$ zwei Codebits $x_i^{(1)}$ und $x_i^{(2)}$ generieren zu können, muss der Faltungscodierer mindestens ein Speicherelement beinhalten:
+
[[Datei:P ID2594 KC T 3 1 S3b v1.png|right|frame|Faltungscoder&nbsp; $(n = 2, \hspace{0.05cm} k = 1)$&nbsp; für die Informationssequenz&nbsp; $\underline{u}$|class=fit]]
 +
Die obere Grafik zeigt einen&nbsp; $(n = 2, \hspace{0.05cm} k = 1)$&ndash;Faltungscodierer.
  
:<math>k = 1\hspace{0.05cm}, n = 2 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} m \ge 1
+
*Zum Taktzeitpunkt&nbsp; $i$&nbsp; liegt das Informationsbit&nbsp; $u_i$&nbsp; am Codereingang an und es wird der 2&ndash;Bit&ndash;Codeblock&nbsp; $\underline{x}_i = (x_i^{(1)}, \ x_i^{(2)})$&nbsp; ausgegeben.
  \hspace{0.05cm}.</math>
+
*Unter Berücksichtigung der (halb&ndash;unendlich) langen Informationssequenz&nbsp; $\underline{u}$&nbsp; ergibt sich das Modell entsprechend der zweiten Grafik.<br>
 +
*Um aus einem einzigen Informationsbit&nbsp; $u_i$&nbsp; zwei Codebit&nbsp; $x_i^{(1)}$&nbsp; und&nbsp; $x_i^{(2)}$&nbsp; generieren zu können, muss der Faltungscodierer mindestens ein Speicherelement beinhalten:
 +
:$$k = 1\hspace{0.05cm}, \ n = 2 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} m \ge 1
 +
  \hspace{0.05cm}.$$
  
<i>Anmerkung</i>: Die beiden Begriffe <i>Faltungscodierer</i> und <i>Faltungscoder</i> werden in unserem Lerntutorial synonym verwendet und können beliebig ausgetauscht werden. Beide Begriffe bezeichnen die konkrete Umsetzung einer Informationssequenz $\underline{u}$ in eine Codesequenz $\underline{x}$.<br>
+
{{GraueBox|TEXT= 
 +
$\text{Beispiel 2:}$&nbsp; Nachfolgend ist ein Faltungscodierer für die Parameter&nbsp; $k = 1, \ n = 2$&nbsp; und&nbsp; $m = 1$&nbsp; dargestellt. Das gelb hinterlegte Quadrat kennzeichnet ein Speicherelement. Dessen Beschriftung&nbsp;  $D$&nbsp; ist von <i>Delay</i> abgeleitet.<br>
  
Die Begriffe <i>Faltungscodierer</i> und <i>Faltungscode</i> sollte man allerdings nicht verwechseln. Unter einem Faltungscode ${\rm CC}(k, \ n, \ m)$ &nbsp;&#8658;&nbsp; $R = k/n$ versteht man die Menge aller möglichen Codesequenzen $\underline{x}$, die mit diesem Code unter Berücksichtigung aller möglichen Informationssequenzen $\underline{u}$ (am Eingang) generiert werden kann. Es gibt verschiedene Faltungscodierer, die den gleichen Faltungscode realisieren.<br>
+
[[Datei:P ID2595 KC T 3 1 S3c v1.png|right|frame|Faltungscodierer mit&nbsp; $k = 1, \ n = 2, \ m = 1$&nbsp; sowie Beispielsequenzen|class=fit]]
  
{{Beispiel}}''':''' Nachfolgend ist ein Faltungscodierer für die Parameter $k = 1, \ n = 2$ und $m = 1$ dargestellt. Das gelbe Quadrat kennzeichnet ein Speicherelement. Dessen Beschriftung  $D$ ist von <i>Delay</i> abgeleitet.<br>
+
*Es handelt sich hier um einen <i>systematischen</i>&nbsp; Faltungscodierer, gekennzeichnet durch&nbsp; $x_i^{(1)} = u_i$.
 +
*Der zweite Ausgang liefert&nbsp; $x_i^{(2)} = u_i + u_{i-1}$.  
  
[[Datei:P ID2595 KC T 3 1 S3c v1.png|center|frame|Faltungscodierer mit $k = 1, \ n = 2, \ m = 1$ sowie Beispielsequenzen|class=fit]]<br>
+
*In der beispielhaften Ausgangssequenz&nbsp; $\underline{x}$&nbsp; nach&nbsp; <i>Multiplexing</i>&nbsp; sind alle&nbsp; $x_i^{(1)}$&nbsp; rot und alle&nbsp; $x_i^{(2)}$&nbsp; blau beschriftet.}}<br>
  
Es handelt sich hier um einen <i>systematischen</i> Faltungscodierer, gekennzeichnet durch $x_i^{(1)} = u_i$. Der zweite Ausgang liefert $x_i^{(2)} = u_i + u_{i&ndash;1}$. In der beispielhaften Ausgangssequenz nach <i>Multiplexing</i> sind alle $x_i^{(1)}$ rot und alle $x_i^{(2)}$ blau beschriftet.{{end}}<br>
+
[[Datei:P ID2596 KC T 3 1 S3d v1.png|right|frame|Faltungscoder&nbsp; $(k = 1, \ n = 2, \ m = 2)$&nbsp; in zwei verschiedenen Darstellungen|class=fit]]
 +
{{GraueBox|TEXT=
 +
$\text{Beispiel 3:}$&nbsp;
 +
Die Grafik zeigt einen&nbsp; $(n = 2, \ k = 1)$&ndash;Faltungscodierers mit&nbsp; $m = 2$&nbsp; Speicherelementen: 
 +
*Links ist das Ersatzschaltbild dargestellt.
 +
*Rechts ist eine Realisierungsform dieses Coders angegeben.  
  
== Rate–1/2–Faltungscodierer (2) ==
+
*Die beiden Informationsbits lauten:
<br>
+
::<math>x_i^{(1)} = u_{i} + u_{i-1}+ u_{i-2} \hspace{0.05cm},</math>
Nachfolgend sehen Sie links das Ersatzschaltbild eines $(n = 2, \ k = 1)$&ndash;Faltungscodierers, aber nun mit $m = 2$ Speicherelementen. Die beiden Informationsbits lauten:
+
::<math>x_i^{(2)} = u_{i} + u_{i-2} \hspace{0.05cm}.</math>
  
:<math>x_i^{(1)} \hspace{-0.15cm}  = \hspace{-0.15cm} u_{i} + u_{i-1}+ u_{i-2} \hspace{0.05cm},</math>
+
*Wegen&nbsp; $x_i^{(1)} &ne; u_i$&nbsp; handelt es sich hier nicht um einen systematischen Code.
:<math>x_i^{(2)} \hspace{-0.15cm} = \hspace{-0.15cm} u_{i} + u_{i-2} \hspace{0.05cm}.</math>
+
<br clear=all>
 +
Man erkennt:
 +
*Die Informationssequenz&nbsp; $\underline{u}$&nbsp; wird in einem Schieberegister der Länge&nbsp; $L = m + 1 = 3$&nbsp; abgelegt.<br>
  
Wegen $x_i^{(1)} &ne; u_i$ handelt es sich hier nicht um einen systematischen Code.<br>
+
*Zum Taktzeitpunkt&nbsp; $i$&nbsp; beinhaltet das linke Speicherelement das aktuelle Informationsbit&nbsp; $u_i$, das zu den nächsten Taktzeitpunkten jeweils um eine Stelle nach rechts verschoben wird.<br>
  
[[Datei:P ID2596 KC T 3 1 S3d v1.png|center|frame|Faltungscoder $(k = 1, \ n = 2, \ m = 2)$ in zwei verschiedenen Darstellungen|class=fit]]<br>
+
*Aus der Anzahl der gelben Quadrate ergibt sich wieder das Gedächtnis&nbsp; $m = 2$&nbsp; des Coders.<br><br>
  
Rechts angegeben ist eine Realisierungsform dieses Coders. Man erkennt:
+
Aus den beiden Darstellungen wird deutlich, dass&nbsp;  $x_i^{(1)}$&nbsp; und&nbsp; $x_i^{(2)}$&nbsp; jeweils als der Ausgang eines&nbsp; [[Stochastische_Signaltheorie/Digitale_Filter|Digitalen Filters]]&nbsp; über dem Galoisfeld&nbsp; ${\rm GF(2)}$&nbsp; interpretiert werden kann, wobei beide Filter parallel mit der gleichen Eingangsfolge&nbsp; $\underline{u}$&nbsp; arbeiten.  
*Die Informationssequenz $\underline{u}$ wird in einem Schieberegister der Länge $L = m + 1 = 3$ abgelegt.<br>
 
  
*Zum Taktzeitpunkt $i$ beinhaltet das linke Speicherelement das aktuelle Informationsbit $u_i$, das zu den nächsten Taktzeitpunkten jeweils um eine Stelle nach rechts verschoben wird.<br>
+
Da sich (ganz allgemein) das Ausgangssignal eines Filters aus der&nbsp; [[Signaldarstellung/Faltungssatz_und_Faltungsoperation#Faltung_im_Zeitbereich| Faltung]]&nbsp; des Eingangssignals mit der Filterimpulsantwort ergibt, spricht man von&nbsp;  <i>Faltungscodierung</i>.<br>}}
  
*Aus der Anzahl der gelben Quadrate ergibt sich wieder das Gedächtnis $m = 2$ des Coders.<br><br>
+
== Faltungscodierer mit zwei Eingängen ==
 +
<br>
 +
[[Datei:P ID2598 KC T 3 1 S4 v1.png|right|frame|Faltungscodierer mit&nbsp; $k = 2$&nbsp; und&nbsp; $n = 3$]]
 +
Nun betrachten wir einen Faltungscodierer, der aus&nbsp; $k = 2$&nbsp; Informationsbits&nbsp; $n = 3$&nbsp; Codebits generiert.
 +
*Die Informationssequenz&nbsp; $\underline{u}$&nbsp; wird in Blöcke zu je zwei Bit aufgeteilt.
 +
*Zum Taktzeitpunkt&nbsp; $i$&nbsp; liegt am oberen Eingang das Bit&nbsp; $u_i^{(1)}$&nbsp; an und am unteren Eingang&nbsp; $u_i^{(2)}$.
 +
*Für die&nbsp; $n = 3$&nbsp; Codebits zum Zeitpunkt&nbsp; $i$&nbsp; gilt dann:
 +
::<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>
  
Aus den beiden Darstellungen wird deutlich, dass  $x_i^{(1)}$ und $x_i^{(2)}$ jeweils als der Ausgang eines Digitalen Filters über dem Galoisfeld ${\rm GF(2)}$ interpretiert werden kann, wobei beide Filter parallel mit der gleichen Eingangsfolge $\underline{u}$ arbeiten. Da sich (ganz allgemein) das Ausgangssignal eines Filters aus der [[Signaldarstellung/Faltungssatz_und_Faltungsoperation#Faltung_im_Zeitbereich| Faltung]] des Eingangssignals mit der Filterimpulsantwort ergibt, spricht man von  <i>Faltungscodierung</i>.<br>
+
In der Grafik sind die Info&ndash;Bits&nbsp; $u_i^{(1)}$&nbsp; und&nbsp; $u_i^{(2)}$&nbsp; rot bzw. blau gekennzeichnet, und die vorherigen Info&ndash;Bits&nbsp; $u_{i-1}^{(1)}$&nbsp; und&nbsp; $u_{i-1}^{(2)}$&nbsp; grün bzw. braun.  
  
== Faltungscodierer mit k = 2 Eingängen ==
+
Anzumerken ist:
<br>
+
*Das <i>Gedächtnis</i>&nbsp; $m$&nbsp; ist gleich der maximalen Speicherzellenzahl in einem Zweig &nbsp;&nbsp;&#8658;&nbsp;&nbsp; hier&nbsp; $m = 1$.
Nun betrachten wir einen Faltungscodierer, der aus $k = 2$ Informationsbits $n = 3$ Codebits generiert. Die Informationssequenz $\underline{u}$ wird in Blöcke zu je zwei Bit aufgeteilt. Zum Taktzeitpunkt $i$ liegt am oberen Eingang das Bit $u_i^{(1)}$ an und am unteren Eingang $u_i^{(2)}$. Für die $n = 3$ Codebits zum Zeitpunkt $i$ gilt dann:
 
[[Datei:P ID2598 KC T 3 1 S4 v1.png|right|frame|Faltungscodierer mit $k = 2$ und $n = 3$]]
 
  
:<math>x_i^{(1)} \hspace{-0.15cm}  =  \hspace{-0.15cm} u_{i}^{(1)} + u_{i-1}^{(1)}+ u_{i-1}^{(2)} \hspace{0.05cm},</math>
+
*Die <i>Einflusslänge</i>&nbsp; $\nu$&nbsp; ist gleich der Summe aller Speicherelemente &nbsp;&nbsp;&#8658;&nbsp;&nbsp; hier&nbsp; $\nu = 2$.<br>
:<math>x_i^{(2)} \hspace{-0.15cm}  =  \hspace{-0.15cm} u_{i}^{(2)} + u_{i-1}^{(1)} \hspace{0.05cm},</math>
 
:<math>x_i^{(3)} \hspace{-0.15cm}  = \hspace{-0.15cm} u_{i}^{(1)} + u_{i}^{(2)}+ u_{i-1}^{(1)} \hspace{0.05cm}.</math>
 
  
In der Grafik sind die Info&ndash;Bits $u_i^{(1)}$ und $u_i^{(2)}$ rot bzw. blau gekennzeichnet, und die vorherigen Info&ndash;Bits $u_{i&ndash;1}^{(1)}$ und $u_{i&ndash;1}^{(2)}$ grün bzw. braun. Anzumerken ist:
+
*Alle Speicherelemente seien zu Beginn der Codierung (<i>Initialisierung</i>&nbsp;) auf Null gesetzt.<br><br>
*Das <b>Gedächtnis</b> $m$ ist gleich der maximalen Speicherzellenzahl in einem Zweig &nbsp;&nbsp;&#8658;&nbsp;&nbsp; hier $m = 1$.
 
  
*Die <b>Einflusslänge</b> $\nu$ ist gleich der Summe aller Speicherelemente &nbsp;&nbsp;&#8658;&nbsp;&nbsp; hier $\nu = 2$.<br>
+
Der hiermit definierte Code ist die Menge aller möglichen Codesequenzen&nbsp; $\underline{x}$, die sich bei Eingabe aller möglichen Informationssequenzen&nbsp; $\underline{u}$&nbsp; ergeben. Sowohl&nbsp; $\underline{u}$&nbsp; als auch&nbsp; $\underline{x}$&nbsp; seien dabei (zeitlich) unbegrenzt.<br>
  
*Alle Speicherelemente seien zu Beginn der Codierung (<i>Initialisierung</i>) auf Null gesetzt.<br><br>
+
{{GraueBox|TEXT= 
 
+
$\text{Beispiel 4:}$&nbsp; Die Informationssequenz sei &nbsp;$\underline{u} = (0, 1, 1, 0, 0, 0, 1, 1, \ \text{ ...})$. Daraus ergeben sich die Teilsequenzen&nbsp; $\underline{u}^{(1)} = (0, 1, 0, 1, \ \text{ ...})$ &nbsp;und&nbsp; $\underline{u}^{(2)} = (1, 0, 0, 1, \ \text{ ...})$.  
Der hiermit definierte Code ist die Menge aller möglichen Codesequenzen $\underline{x}$, die sich bei Eingabe aller möglichen Informationssequenzen $\underline{u}$ ergeben. Sowohl $\underline{u}$ als auch $\underline{x}$ seien dabei (zeitlich) unbegrenzt.<br>
 
  
{{Beispiel}}''':''' Die Informationssequenz sei $\underline{u} = (0, 1, 1, 0, 0, 0, 1, 1, \ ...)$. Daraus ergeben sich die beiden Teilsequenzen $\underline{u}^{(1)} = (0, 1, 0, 1, \ ...)$ und $\underline{u}^{(2)} = (1, 0, 0, 1, \ ...)$. Mit der Festlegung $u_0^{(1)} = u_0^{(2)} = 0$ folgt aus den obigen Gleichungen für die $n = 3$ Codebits:
+
Mit der Festlegung&nbsp; $u_0^{(1)} = u_0^{(2)} = 0$&nbsp; folgt aus den obigen Gleichungen für die&nbsp; $n = 3$&nbsp; Codebits
*im ersten Codierschritt $(i = 1)$:
+
*im ersten Codierschritt&nbsp; $(i = 1)$:
  
 
::<math>x_1^{(1)} = u_{1}^{(1)} = 0  \hspace{0.05cm},\hspace{0.4cm}
 
::<math>x_1^{(1)} = u_{1}^{(1)} = 0  \hspace{0.05cm},\hspace{0.4cm}
Zeile 161: Zeile 182:
 
x_1^{(3)} = u_{1}^{(1)} + u_{1}^{(2)} = 0+1 = 1 \hspace{0.05cm},</math>
 
x_1^{(3)} = u_{1}^{(1)} + u_{1}^{(2)} = 0+1 = 1 \hspace{0.05cm},</math>
  
*im zweiten Codierschritt $(i = 2)$:
+
*im zweiten Codierschritt&nbsp; $(i = 2)$:
  
::<math>x_2^{(1)} \hspace{-0.15cm}  = \hspace{-0.15cm} u_{2}^{(1)} + u_{1}^{(1)}+ u_{1}^{(2)} = 1 + 0 + 1 = 0\hspace{0.05cm},\hspace{0.4cm}
+
::<math>x_2^{(1)} =u_{2}^{(1)} + u_{1}^{(1)}+ u_{1}^{(2)} = 1 + 0 + 1 = 0\hspace{0.05cm},\hspace{0.4cm}
x_2^{(2)} = u_{2}^{(2)} + u_{1}^{(1)} = 0+0 = 0\hspace{0.05cm},</math>
+
x_2^{(2)} = u_{2}^{(2)} + u_{1}^{(1)} = 0+0 = 0\hspace{0.05cm},\hspace{0.4cm}
::<math>x_2^{(3)} \hspace{-0.15cm}  = \hspace{-0.15cm} u_{2}^{(1)} + u_{2}^{(2)}+ u_{1}^{(1)} = 1 + 0+0 =1\hspace{0.05cm},</math>
+
x_2^{(3)} = u_{2}^{(1)} + u_{2}^{(2)}+ u_{1}^{(1)} = 1 + 0+0 =1\hspace{0.05cm},</math>
  
*im dritten Codierschritt $(i = 3)$:
+
*im dritten Codierschritt&nbsp; $(i = 3)$:
  
::<math>x_3^{(1)} \hspace{-0.15cm}  = \hspace{-0.15cm} u_{3}^{(1)} + u_{2}^{(1)}+ u_{2}^{(2)} = 0+1+0 = 1\hspace{0.05cm},\hspace{0.4cm}
+
::<math>x_3^{(1)} =u_{3}^{(1)} + u_{2}^{(1)}+ u_{2}^{(2)} = 0+1+0 = 1\hspace{0.05cm},\hspace{0.4cm}
x_3^{(2)} = u_{3}^{(2)} + u_{2}^{(1)} = 0+1=1\hspace{0.05cm},</math>
+
x_3^{(2)} = u_{3}^{(2)} + u_{2}^{(1)} = 0+1=1\hspace{0.05cm},\hspace{0.4cm}
::<math>x_3^{(3)} \hspace{-0.15cm}  = \hspace{-0.15cm} u_{3}^{(1)} + u_{3}^{(2)}+ u_{2}^{(1)} = 0+0+1 =1\hspace{0.05cm},</math>
+
x_3^{(3)} =u_{3}^{(1)} + u_{3}^{(2)}+ u_{2}^{(1)} = 0+0+1 =1\hspace{0.05cm},</math>
  
*und schließlich im vierten Codierschritt $(i = 4)$:
+
*und schließlich im vierten Codierschritt&nbsp; $(i = 4)$:
  
::<math>x_4^{(1)} \hspace{-0.15cm}  = \hspace{-0.15cm} u_{4}^{(1)} + u_{3}^{(1)}+ u_{3}^{(2)} = 1+0+0 = 1\hspace{0.05cm},\hspace{0.4cm}
+
::<math>x_4^{(1)} = u_{4}^{(1)} + u_{3}^{(1)}+ u_{3}^{(2)} = 1+0+0 = 1\hspace{0.05cm},\hspace{0.4cm}
x_4^{(2)} = u_{4}^{(2)} + u_{3}^{(1)} = 1+0=1\hspace{0.05cm},</math>
+
x_4^{(2)} = u_{4}^{(2)} + u_{3}^{(1)} = 1+0=1\hspace{0.05cm},\hspace{0.4cm}
::<math>x_4^{(3)} \hspace{-0.15cm}  = \hspace{-0.15cm} u_{4}^{(1)} + u_{4}^{(2)}+ u_{3}^{(1)} = 1+1+0 =0\hspace{0.05cm}.</math>
+
x_4^{(3)}= u_{4}^{(1)} + u_{4}^{(2)}+ u_{3}^{(1)} = 1+1+0 =0\hspace{0.05cm}.</math>
  
Damit lautet die Codesequenz nach dem Multiplexer: &nbsp; $\underline{x} = (0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, \ ...)$.{{end}}<br>
+
Damit lautet die Codesequenz nach dem Multiplexer: &nbsp; &nbsp; $\underline{x} = (0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, \ \text{...})$.}}<br>
  
 
== Aufgaben zum Kapitel==
 
== Aufgaben zum Kapitel==
 
<br>
 
<br>
[[Aufgaben:3.1 Analyse eines Faltungscoders|A3.1 Analyse eines Faltungscoders]]
+
[[Aufgaben:Aufgabe_3.1:_Analyse_eines_Faltungscodierers|Aufgabe 3.1: Analyse eines Faltungscodierers]]
  
[[Aufgaben:3.1Z_Faltungscodes_der_Rate_1/2|Zusatzaufgaben:3.1 Faltungscodes der Rate 1/2]]
+
[[Aufgaben:Aufgabe_3.1Z:_Faltungscodes_der_Rate_1/2|Aufgabe 3.1Z: Faltungscodes der Rate 1/2]]
  
 
==Quellenverzeichnis==
 
==Quellenverzeichnis==

Aktuelle Version vom 3. Juni 2019, 15:04 Uhr

# ÜBERBLICK ZUM DRITTEN HAUPTKAPITEL #


Dieses dritte Hauptkapitel behandelt  Faltungscodes  (englisch:  Convolutional Codes), die erstmals 1955 von  Peter Elias  beschrieben wurden [Eli55][1]. Während bei den linearen Blockcodes (siehe  Erstes Hauptkapitel)  und den Reed–Solomon–Codes  (siehe Zweites Hauptkapitel)  die Codewortlänge jeweils  $n$  ist, basiert die Theorie der Faltungscdes auf „semi–infiniten” Informations– und Codesequenzen. Ebenso liefert die Maximum–Likelihood–Decodierung mittels des Viterbi–Algorithmuses per se die gesamte Sequenz.

Im Einzelnen werden in diesem Kapitel behandelt:

  • Wichtige Definitionen  für Faltungscodes:   Coderate, Gedächtnis, Einflusslänge, freie Distanz
  • Gemeinsamkeiten  und Unterschiede  zu den linearen Blockcodes,
  • Generatormatrix  und Übertragungsfunktionsmatrix  eines Faltungscodes,
  • gebrochen–rationale Übertragungsfunktionen  für systematische Faltungscodes,
  • Beschreibung mit Zustandsübergangsdiagramm  und Trellisdiagramm,
  • Terminierung  und Punktierung  von Faltungscodes,
  • Decodierung  von Faltungscodes   ⇒   Viterbi–Algorithmus,
  • Gewichtsfunktionen  und Näherungen für die Bitfehlerwahrscheinlichkeit.


Voraussetzungen und Definitionen


Wir betrachten in diesem Kapitel eine unendlich lange binäre Informationssequenz  $\underline{u}$  und unterteilen diese in Informationsblöcke  $\underline{u}_i$  zu je  $k$  Bit. Man kann diesen Sachverhalt wie folgt formalisieren:

\[\underline{\it u} = \left ( \underline{\it u}_1, \underline{\it u}_2, \hspace{0.05cm} \text{...} \hspace{0.05cm}, \underline{\it u}_i , \hspace{0.05cm} \text{...} \hspace{0.05cm}\right ) \hspace{0.3cm}{\rm mit}\hspace{0.3cm} \underline{\it u}_i = \left ( u_i^{(1)}, u_i^{(2)}, \hspace{0.05cm} \text{...} \hspace{0.05cm}, u_i^{(k)}\right )\hspace{0.05cm},\]
\[u_i^{(j)}\in {\rm GF(2)}\hspace{0.3cm}{\rm f\ddot{u}r} \hspace{0.3cm}1 \le j \le k \hspace{0.5cm}\Rightarrow \hspace{0.5cm} \underline{\it u}_i \in {\rm GF}(2^k)\hspace{0.05cm}.\]

Im Englischen bezeichnet man eine solche Sequenz ohne negative Indizes als semi–infinite .

$\text{Definition:}$  Bei einem  binären Faltungscode  (englisch:  Binary Convolutional Code ) wird zum Zeitpunkt  $i$  ein Codewort  $\underline{x}_i$  bestehend aus  $n$  Codebit ausgegeben:

\[\underline{\it x}_i = \left ( x_i^{(1)}, x_i^{(2)}, \hspace{0.05cm} \text{...} \hspace{0.05cm}, x_i^{(n)}\right )\in {\rm GF}(2^n)\hspace{0.05cm}.\]

Dieses ergibt sich entsprechend

  • den  $k$  Bit des aktuellen Informationsblockes  $\underline{u}_i$, und
  • den  $m$  vorherigen Informationsblöcken  $\underline{u}_{i-1}$, ... , $\underline{u}_{i-m}$.


Abhängigkeiten bei einem Faltungscodierer mit  $m = 2$

Nebenstehende Grafik verdeutlicht diesen Sachverhalt für die Parameter  $k = 4, \ n = 7, \ m = 2$  und  $i = 4$.

Die  $n = 7$  zum Zeitpunkt  $i = 4$  erzeugten Codebits  $x_4^{(1)}$, ... , $x_4^{(7)}$  können (direkt) von den  $k \cdot (m+1) = 12$  rot markierten Informationsbits abhängen und werden durch Modulo–2–Additionen erzeugt.

Gelb eingezeichnet ist zudem ein  $(n, k)$–Faltungscodierer. Zu beachten ist, dass sich der Vektor  $\underline{u}_i$  und die Sequenz  $\underline{u}^{(i)}$  grundlegend unterscheiden:

  • Während  $\underline{u}_i = (u_i^{(1)}, u_i^{(2)}$, ... , $u_i^{(k)})$  die  $k$  zum Zeitpunkt  $i$  parallel anliegenden Informationsbits zusammenfasst,
  • bezeichnet  $\underline{u}^i = (u_1^{(i)}$, $u_2^{(i)}, \ \text{...})$  die (horizontale) Sequenz am  $i$–ten Eingang des Faltungscodierers.


$\text{Definitionen bezüglich Faltungscodes:}$ 

  • Die  Coderrate  ergibt sich wie bei den Blockcodes zu  $R = k/n$.
  • Man bezeichnet  $m$  als das  Gedächtnis  (englisch:  Memory )  des Codes und den Convolutional Code  selbst mit  ${\rm CC} \ (n, k, m)$.
  • Daraus ergibt sich die  Einflusslänge  (englisch:  Constraint Length ) zu  $\nu = m + 1$.
  • Für  $k > 1$  gibt man diese Parameter oft auch in Bit an:   $m_{\rm Bit} = m \cdot k$    bzw.    $\nu_{\rm Bit} = (m + 1) \cdot k$.

Gemeinsamkeiten und Unterschiede gegenüber Blockcodes


Aus der  Definition  auf der vorherigen Seite ist ersichtlich, dass ein binärer Faltungscode mit  $m = 0$  (also ohne Gedächtnis) identisch wäre mit einem binären Blockcode wie in ersten Hauptkapitel beschrieben. Wir schließen diesen Grenzfall aus und setzen deshalb für das Folgende stets voraus:

  • Das Gedächtnis  $m$  sei größer oder gleich  $1$.
  • Die Einflusslänge  $\nu$  sei größer oder gleich  $2$.

$\text{Beispiel 1:}$  Bei einem  $(7, 4)$–Blockcode hängt das Codewort  $\underline {x}_4$  nur vom Informationswort  $\underline{u}_4$  ab, nicht jedoch von  $\underline{u}_2$  und  $\underline{u}_3$, wie bei dem  beispielhaften Faltungscodes  $($mit  $m = 2)$  auf der letzten Seite.

Abhängigkeiten bei einem  $(7, 4)$–Blockcode zum Zeitpunkt  $i = 4$

Gilt beispielsweise

$$x_4^{(1)} = u_4^{(1)}, \ x_4^{(2)} = u_4^{(2)},$$
$$x_4^{(3)} = u_4^{(3)}, \ x_4^{(4)} = u_4^{(4)}$$

sowie

$$x_4^{(5)} = u_4^{(1)}+ u_4^{(2)}+u_4^{(3)}\hspace{0.05cm},$$
$$x_4^{(6)} = u_4^{(2)}+ u_4^{(3)}+u_4^{(4)}\hspace{0.05cm},$$
$$x_4^{(7)} = u_4^{(1)}+ u_4^{(2)}+u_4^{(4)}\hspace{0.05cm},$$

so handelt es sich um einen so genannten  systematischen Hamming–Code  $\text{HS (7, 4, 3)}$. In der Grafik sind diese speziellen Abhängigkeiten für  $x_4^{(1)}$  und  $x_4^{(7)}$  rot eingezeichnet.


In gewisser Weise könnte man auch einen  $(n, k)$–Faltungscode mit Gedächtnis  $m ≥ 1$  als Blockcode interpretieren, dessen Codeparameter  $n\hspace{0.05cm}' \gg n$  und  $k\hspace{0.05cm}' \gg k$  allerdings sehr viel größere Werte annehmen müssten als die des vorliegenden Faltungscodes. Aufgrund der großen Unterschiede in der Beschreibung, in den Eigenschaften und insbesondere bei der Decodierung betrachten wir aber Faltungscodes in diesem Lerntutorial als etwas völlig Neues. Hierfür sprechen folgende Gründe:

  • Ein Blockcodierer setzt Informationsworte der Länge  $k$  Bit blockweise in Codeworte mit je  $n$  Bit um. Der Blockcode ist dabei um so leistungsfähiger, je größer seine Codewortlänge  $n$  ist. Bei gegebener Coderate  $R = k/n$  erfordert dies auch eine große Informationswortlänge  $k$.
  • Dagegen wird die Korrekturfähigkeit eines Faltungscodes im wesentlichen durch sein Gedächtnis  $m$  bestimmt. Die Codeparameter  $k$  und  $n$  werden hier meist sehr klein gewählt  $(1, \ 2, \ 3, \ \text{...})$. Von praktischer Bedeutung sind somit nur ganz wenige und zudem sehr einfache Faltungscodes.
  • Auch schon bei kleinen Werten für  $k$  und  $n$  überführt ein Faltungscoder eine ganze Sequenz von Informationsbits  $(k\hspace{0.05cm}' → ∞)$  in eine sehr lange Sequenz von Codebits  $(n\hspace{0.05cm}' = k\hspace{0.05cm}'/R)$. Ein solcher Code bietet somit oft ebenfalls eine große Korrekturfähigkeit.
  • Es gibt effiziente Faltungsdecoder, zum Beispiel den  Viterbi–Algorithmus  und den  BCJR–Algorithmus, die Zuverlässigkeitsinformationen über den Kanal   ⇒   Soft–Decision–Input  verarbeiten können und Zuverlässigkeitsinformation über das Decodierergebnis   ⇒   Soft–Decision–Output  liefern.

Rate–1/2–Faltungscodierer


Faltungscoder  $(n = 2, \hspace{0.05cm} k = 1)$  für ein Informationsbit  $u_i$

Vorbemerkung:   Die beiden Begriffe „Faltungscodierer” und „Faltungscoder” werden in unserem Lerntutorial synonym verwendet und können beliebig ausgetauscht werden.

  • Beide Begriffe bezeichnen die konkrete Umsetzung einer Informationssequenz  $\underline{u}$  in eine Codesequenz  $\underline{x}$.


Die Begriffe „Faltungscodierer” und „Faltungscode” sollte man allerdings nicht verwechseln.

  • Unter einem Faltungscode  ${\rm CC} \ (n, \ k, \ m)$   ⇒   $R = k/n$  versteht man die Menge aller möglichen Codesequenzen  $\underline{x}$, die mit diesem Code unter Berücksichtigung aller möglichen Informationssequenzen  $\underline{u}$  (am Eingang) generiert werden kann.
  • Es gibt verschiedene Faltungscodierer, die den gleichen Faltungscode realisieren.


Faltungscoder  $(n = 2, \hspace{0.05cm} k = 1)$  für die Informationssequenz  $\underline{u}$

Die obere Grafik zeigt einen  $(n = 2, \hspace{0.05cm} k = 1)$–Faltungscodierer.

  • Zum Taktzeitpunkt  $i$  liegt das Informationsbit  $u_i$  am Codereingang an und es wird der 2–Bit–Codeblock  $\underline{x}_i = (x_i^{(1)}, \ x_i^{(2)})$  ausgegeben.
  • Unter Berücksichtigung der (halb–unendlich) langen Informationssequenz  $\underline{u}$  ergibt sich das Modell entsprechend der zweiten Grafik.
  • Um aus einem einzigen Informationsbit  $u_i$  zwei Codebit  $x_i^{(1)}$  und  $x_i^{(2)}$  generieren zu können, muss der Faltungscodierer mindestens ein Speicherelement beinhalten:
$$k = 1\hspace{0.05cm}, \ n = 2 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} m \ge 1 \hspace{0.05cm}.$$

$\text{Beispiel 2:}$  Nachfolgend ist ein Faltungscodierer für die Parameter  $k = 1, \ n = 2$  und  $m = 1$  dargestellt. Das gelb hinterlegte Quadrat kennzeichnet ein Speicherelement. Dessen Beschriftung  $D$  ist von Delay abgeleitet.

Faltungscodierer mit  $k = 1, \ n = 2, \ m = 1$  sowie Beispielsequenzen
  • Es handelt sich hier um einen systematischen  Faltungscodierer, gekennzeichnet durch  $x_i^{(1)} = u_i$.
  • Der zweite Ausgang liefert  $x_i^{(2)} = u_i + u_{i-1}$.
  • In der beispielhaften Ausgangssequenz  $\underline{x}$  nach  Multiplexing  sind alle  $x_i^{(1)}$  rot und alle  $x_i^{(2)}$  blau beschriftet.


Faltungscoder  $(k = 1, \ n = 2, \ m = 2)$  in zwei verschiedenen Darstellungen

$\text{Beispiel 3:}$  Die Grafik zeigt einen  $(n = 2, \ k = 1)$–Faltungscodierers mit  $m = 2$  Speicherelementen:

  • Links ist das Ersatzschaltbild dargestellt.
  • Rechts ist eine Realisierungsform dieses Coders angegeben.
  • Die beiden Informationsbits lauten:
\[x_i^{(1)} = u_{i} + u_{i-1}+ u_{i-2} \hspace{0.05cm},\]
\[x_i^{(2)} = u_{i} + u_{i-2} \hspace{0.05cm}.\]
  • Wegen  $x_i^{(1)} ≠ u_i$  handelt es sich hier nicht um einen systematischen Code.


Man erkennt:

  • Die Informationssequenz  $\underline{u}$  wird in einem Schieberegister der Länge  $L = m + 1 = 3$  abgelegt.
  • Zum Taktzeitpunkt  $i$  beinhaltet das linke Speicherelement das aktuelle Informationsbit  $u_i$, das zu den nächsten Taktzeitpunkten jeweils um eine Stelle nach rechts verschoben wird.
  • Aus der Anzahl der gelben Quadrate ergibt sich wieder das Gedächtnis  $m = 2$  des Coders.

Aus den beiden Darstellungen wird deutlich, dass  $x_i^{(1)}$  und  $x_i^{(2)}$  jeweils als der Ausgang eines  Digitalen Filters  über dem Galoisfeld  ${\rm GF(2)}$  interpretiert werden kann, wobei beide Filter parallel mit der gleichen Eingangsfolge  $\underline{u}$  arbeiten.

Da sich (ganz allgemein) das Ausgangssignal eines Filters aus der  Faltung  des Eingangssignals mit der Filterimpulsantwort ergibt, spricht man von  Faltungscodierung.

Faltungscodierer mit zwei Eingängen


Faltungscodierer mit  $k = 2$  und  $n = 3$

Nun betrachten wir einen Faltungscodierer, der aus  $k = 2$  Informationsbits  $n = 3$  Codebits generiert.

  • Die Informationssequenz  $\underline{u}$  wird in Blöcke zu je zwei Bit aufgeteilt.
  • Zum Taktzeitpunkt  $i$  liegt am oberen Eingang das Bit  $u_i^{(1)}$  an und am unteren Eingang  $u_i^{(2)}$.
  • Für die  $n = 3$  Codebits zum Zeitpunkt  $i$  gilt dann:
\[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}.\]

In der Grafik sind die Info–Bits  $u_i^{(1)}$  und  $u_i^{(2)}$  rot bzw. blau gekennzeichnet, und die vorherigen Info–Bits  $u_{i-1}^{(1)}$  und  $u_{i-1}^{(2)}$  grün bzw. braun.

Anzumerken ist:

  • Das Gedächtnis  $m$  ist gleich der maximalen Speicherzellenzahl in einem Zweig   ⇒   hier  $m = 1$.
  • Die Einflusslänge  $\nu$  ist gleich der Summe aller Speicherelemente   ⇒   hier  $\nu = 2$.
  • Alle Speicherelemente seien zu Beginn der Codierung (Initialisierung ) auf Null gesetzt.

Der hiermit definierte Code ist die Menge aller möglichen Codesequenzen  $\underline{x}$, die sich bei Eingabe aller möglichen Informationssequenzen  $\underline{u}$  ergeben. Sowohl  $\underline{u}$  als auch  $\underline{x}$  seien dabei (zeitlich) unbegrenzt.

$\text{Beispiel 4:}$  Die Informationssequenz sei  $\underline{u} = (0, 1, 1, 0, 0, 0, 1, 1, \ \text{ ...})$. Daraus ergeben sich die Teilsequenzen  $\underline{u}^{(1)} = (0, 1, 0, 1, \ \text{ ...})$  und  $\underline{u}^{(2)} = (1, 0, 0, 1, \ \text{ ...})$.

Mit der Festlegung  $u_0^{(1)} = u_0^{(2)} = 0$  folgt aus den obigen Gleichungen für die  $n = 3$  Codebits

  • im ersten Codierschritt  $(i = 1)$:
\[x_1^{(1)} = u_{1}^{(1)} = 0 \hspace{0.05cm},\hspace{0.4cm} x_1^{(2)} = u_{1}^{(2)} = 1 \hspace{0.05cm},\hspace{0.4cm} x_1^{(3)} = u_{1}^{(1)} + u_{1}^{(2)} = 0+1 = 1 \hspace{0.05cm},\]
  • im zweiten Codierschritt  $(i = 2)$:
\[x_2^{(1)} =u_{2}^{(1)} + u_{1}^{(1)}+ u_{1}^{(2)} = 1 + 0 + 1 = 0\hspace{0.05cm},\hspace{0.4cm} x_2^{(2)} = u_{2}^{(2)} + u_{1}^{(1)} = 0+0 = 0\hspace{0.05cm},\hspace{0.4cm} x_2^{(3)} = u_{2}^{(1)} + u_{2}^{(2)}+ u_{1}^{(1)} = 1 + 0+0 =1\hspace{0.05cm},\]
  • im dritten Codierschritt  $(i = 3)$:
\[x_3^{(1)} =u_{3}^{(1)} + u_{2}^{(1)}+ u_{2}^{(2)} = 0+1+0 = 1\hspace{0.05cm},\hspace{0.4cm} x_3^{(2)} = u_{3}^{(2)} + u_{2}^{(1)} = 0+1=1\hspace{0.05cm},\hspace{0.4cm} x_3^{(3)} =u_{3}^{(1)} + u_{3}^{(2)}+ u_{2}^{(1)} = 0+0+1 =1\hspace{0.05cm},\]
  • und schließlich im vierten Codierschritt  $(i = 4)$:
\[x_4^{(1)} = u_{4}^{(1)} + u_{3}^{(1)}+ u_{3}^{(2)} = 1+0+0 = 1\hspace{0.05cm},\hspace{0.4cm} x_4^{(2)} = u_{4}^{(2)} + u_{3}^{(1)} = 1+0=1\hspace{0.05cm},\hspace{0.4cm} x_4^{(3)}= u_{4}^{(1)} + u_{4}^{(2)}+ u_{3}^{(1)} = 1+1+0 =0\hspace{0.05cm}.\]

Damit lautet die Codesequenz nach dem Multiplexer:     $\underline{x} = (0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, \ \text{...})$.


Aufgaben zum Kapitel


Aufgabe 3.1: Analyse eines Faltungscodierers

Aufgabe 3.1Z: Faltungscodes der Rate 1/2

Quellenverzeichnis

  1. Elias, P.: Coding for Noisy Channels. In: IRE Conv. Rec. Part 4,S. 37-47, 1955.