Kanalcodierung/Codebeschreibung mit Zustands– und Trellisdiagramm: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
Zeile 63: Zeile 63:
 
== Darstellung im Zustandsübergangsdiagramm (1) ==
 
== Darstellung im Zustandsübergangsdiagramm (1) ==
 
<br>
 
<br>
Die Grafik zeigt das <b>Zustandsübergangsdiagramm</b> (englisch: <i>State Transition Diagram</i>) für unseren Standardcodierer. Dieses liefert alle Informationen über den  (<i>n</i> = 2, <i>k</i> = 1, <i>m</i> = 2)&ndash;Faltungscodierer in kompakter Form. Die Farbgebung ist mit der sequenziellen Darstellung auf der vorherigen Seite abgestimmt. Der Vollständigkeit halber ist auch die Herleitungstabelle nochmals angegeben.<br>
+
Die Grafik zeigt das <b>Zustandsübergangsdiagramm</b> (englisch: <i>State Transition Diagram</i>) für unseren Standardcodierer. Dieses liefert alle Informationen über den  (<i>n</i> = 2, <i>k</i> = 1, <i>m</i> = 2)&ndash;Faltungscodierer in kompakter Form. Die Farbgebung ist mit der [http://www.lntwww.de/Kanalcodierung/Codebeschreibung_mit_Zustands%E2%80%93_und_Trellisdiagramm#Zustandsdefinition_f.C3.BCr_ein_Speicherregister_.281.29 sequenziellen Darstellung] auf der vorherigen Seite abgestimmt. Der Vollständigkeit halber ist auch die Herleitungstabelle nochmals angegeben.<br>
  
 
[[Datei:P ID3022 KC T 3 3 S2 v2.png|Zustandsübertragungsdiagramm 1 für <i>n</i> = 2, <i>k</i> = 1, <i>m</i> = 2|class=fit]]<br>
 
[[Datei:P ID3022 KC T 3 3 S2 v2.png|Zustandsübertragungsdiagramm 1 für <i>n</i> = 2, <i>k</i> = 1, <i>m</i> = 2|class=fit]]<br>
Zeile 92: Zeile 92:
 
*Da die früheren Informationsbits <i>u<sub>i</sub></i><sub>&ndash;1</sub> und <i>u<sub>i</sub></i><sub>&ndash;2</sub> nicht abgespeichert werden, beziehen sich hier die Zustände <i>s<sub>i</sub></i> = <i>S<sub>&mu;</sub></i> auf die verarbeiteten Größen <i>w<sub>i</sub></i><sub>&ndash;1</sub> und <i>w<sub>i</sub></i><sub>&ndash;2</sub>, wobei <i>w<sub>i</sub></i> = <i>u<sub>i</sub></i> + <i>w<sub>i</sub></i><sub>&ndash;1</sub> + <i>w<sub>i</sub></i><sub>&ndash;2</sub> gilt.<br>
 
*Da die früheren Informationsbits <i>u<sub>i</sub></i><sub>&ndash;1</sub> und <i>u<sub>i</sub></i><sub>&ndash;2</sub> nicht abgespeichert werden, beziehen sich hier die Zustände <i>s<sub>i</sub></i> = <i>S<sub>&mu;</sub></i> auf die verarbeiteten Größen <i>w<sub>i</sub></i><sub>&ndash;1</sub> und <i>w<sub>i</sub></i><sub>&ndash;2</sub>, wobei <i>w<sub>i</sub></i> = <i>u<sub>i</sub></i> + <i>w<sub>i</sub></i><sub>&ndash;1</sub> + <i>w<sub>i</sub></i><sub>&ndash;2</sub> gilt.<br>
  
*Da dieser Code systematisch ist, gilt <i>x<sub>i</sub></i><sup>(1)</sup> = <i>u<sub>i</sub></i>. Die Herleitung der zweiten Codebits <i>x<sub>i</sub></i><sup>(2)</sup> finden Sie in Aufgabe A3.5. Es handelt sich um ein rekursives Filter, wie in Kapitel 3.2 beschrieben.<br><br>
+
*Da dieser Code systematisch ist, gilt <i>x<sub>i</sub></i><sup>(1)</sup> = <i>u<sub>i</sub></i>. Die Herleitung der zweiten Codebits <i>x<sub>i</sub></i><sup>(2)</sup> finden Sie in Aufgabe A3.5. Es handelt sich um ein rekursives Filter, wie in [http://www.lntwww.de/Kanalcodierung/Algebraische_und_polynomische_Beschreibung#Filterstruktur_bei_gebrochen.E2.80.93rationaler_.C3.9Cbertragungsfunktion Kapitel 3.2] beschrieben.<br><br>
  
 
Der Bildervergleich zeigt, dass sich für beide Codierer ein ähnliches Zustandsübergangsdiagramm ergibt:
 
Der Bildervergleich zeigt, dass sich für beide Codierer ein ähnliches Zustandsübergangsdiagramm ergibt:
Zeile 110: Zeile 110:
 
*Ab dem Zeitpunkt <i>i</i> = <i>m</i> + 1 = 3 hat das Trellis für jeden Übergang von <i>s<sub>i</sub></i> nach <i>s<sub>i</sub></i><sub>+1</sub> genau das gleiche Aussehen. Jeder Zustand <i>S<sub>&mu;</sub></i> ist durch einen roten Pfeil (<i>u<sub>i</sub></i> = 0) und einen blauen Pfeil (<i>u<sub>i</sub></i>&nbsp;=&nbsp;1) mit einem Nachfolgezustand verbunden.<br>
 
*Ab dem Zeitpunkt <i>i</i> = <i>m</i> + 1 = 3 hat das Trellis für jeden Übergang von <i>s<sub>i</sub></i> nach <i>s<sub>i</sub></i><sub>+1</sub> genau das gleiche Aussehen. Jeder Zustand <i>S<sub>&mu;</sub></i> ist durch einen roten Pfeil (<i>u<sub>i</sub></i> = 0) und einen blauen Pfeil (<i>u<sub>i</sub></i>&nbsp;=&nbsp;1) mit einem Nachfolgezustand verbunden.<br>
  
*Gegenüber einem <i>Codebaum</i>, der mit jedem Zeitschritt <i>i</i> exponentiell anwächst &ndash; siehe zum Beispiel Kapitel 3.8, Seite 2a im Buch &bdquo;Digitalsignalübertragung&rdquo; &ndash; ist hier die Zahl der Knoten (also der möglichen Zustände) auf 2<sup><i>m</i></sup> begrenzt.<br>
+
*Gegenüber einem <i>Codebaum</i>, der mit jedem Zeitschritt <i>i</i> exponentiell anwächst &ndash; siehe zum Beispiel [http://www.lntwww.de/Digitalsignal%C3%BCbertragung/Viterbi%E2%80%93Empf%C3%A4nger#Fehlergr.C3.B6.C3.9Fen_und_Gesamtfehlergr.C3.B6.C3.9Fen_.281.29 Kapitel 3.8, Seite 2a] im Buch &bdquo;Digitalsignalübertragung&rdquo; &ndash; ist hier die Zahl der Knoten (also der möglichen Zustände) auf 2<sup><i>m</i></sup> begrenzt.<br>
  
*Diese erfreuliche Eigenschaft eines jeden Trellisdiagramms nutzt auch der Viterbi&ndash;Algorithmus zur effizienten Maximum&ndash;Likelihood&ndash;Decodierung von Faltungscodes.<br><br>
+
*Diese erfreuliche Eigenschaft eines jeden Trellisdiagramms nutzt auch der [http://www.lntwww.de/Kanalcodierung/Decodierung_von_Faltungscodes#Blockschaltbild_und_Voraussetzungen Viterbi&ndash;Algorithmus] zur effizienten Maximum&ndash;Likelihood&ndash;Decodierung von Faltungscodes.<br><br>
  
 
== Darstellung im Trellisdiagramm (2) ==
 
== Darstellung im Trellisdiagramm (2) ==
Zeile 131: Zeile 131:
 
== Definition der freien Distanz (1) ==
 
== Definition der freien Distanz (1) ==
 
<br>
 
<br>
Als eine wichtige Kenngröße der linearen Blockcodes wurde in Kapitel 1.1 die <b>minimale Hamming&ndash;Distanz</b> zwischen zwei beliebigen Codeworten <u><i>x</i></u> und <u><i>x</i></u>' eingeführt:
+
Als eine wichtige Kenngröße der linearen Blockcodes wurde in [http://www.lntwww.de/Kanalcodierung/Zielsetzung_der_Kanalcodierung#Fehlererkennung_und_Fehlerkorrektur Kapitel 1.1] die <b>minimale Hamming&ndash;Distanz</b> zwischen zwei beliebigen Codeworten <u><i>x</i></u> und <u><i>x</i></u>' eingeführt:
  
 
:<math>d_{\rm min}(\mathcal{C}) =
 
:<math>d_{\rm min}(\mathcal{C}) =
 
\min_{\substack{\underline{x},\hspace{0.05cm}\underline{x}' \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{C} \\ {\underline{x}} \hspace{0.05cm}\ne \hspace{0.05cm} \underline{x}'}}\hspace{0.1cm}d_{\rm H}(\underline{x}, \hspace{0.05cm}\underline{x}')\hspace{0.05cm}.</math>
 
\min_{\substack{\underline{x},\hspace{0.05cm}\underline{x}' \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{C} \\ {\underline{x}} \hspace{0.05cm}\ne \hspace{0.05cm} \underline{x}'}}\hspace{0.1cm}d_{\rm H}(\underline{x}, \hspace{0.05cm}\underline{x}')\hspace{0.05cm}.</math>
  
Aufgrund der Linearität gehört  zu jedem Blockcode auch das Nullwort <u>0</u>. Damit ist <i>d</i><sub>min</Sub> auch gleich dem minimalen Hamming&ndash;Gewicht <i>w</i><sub>H</Sub> (<u><i>x</i></u>) eines Codewortes <u><i>x</i></u> &ne; <u>0</u>.<br>
+
Aufgrund der Linearität gehört  zu jedem Blockcode auch das Nullwort <u>0</u>. Damit ist <i>d</i><sub>min</Sub> auch gleich dem minimalen [http://www.lntwww.de/Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung Hamming&ndash;Gewicht] <i>w</i><sub>H</Sub> (<u><i>x</i></u>) eines Codewortes <u><i>x</i></u> &ne; <u>0</u>.<br>
  
 
Bei Faltungscodes erweist sich die Beschreibung der Distanzverhältnisse als wesentlich aufwändiger, da ein Faltungscode aus unendlich langen und unendlich vielen Codesequenzen besteht.<br>
 
Bei Faltungscodes erweist sich die Beschreibung der Distanzverhältnisse als wesentlich aufwändiger, da ein Faltungscode aus unendlich langen und unendlich vielen Codesequenzen besteht.<br>
Zeile 159: Zeile 159:
 
== Definition der freien Distanz (2) ==
 
== Definition der freien Distanz (2) ==
 
<br>
 
<br>
Je größer die freie Distanz <i>d</i><sub>F</sub> ist, desto besser ist das asymptotische Verhalten des Faltungscoders. Zur genauen Berechnung von Fehlerwahrscheinlichkeit benötigt man allerdings &ndash; ebenso wie bei den linearen Blockcodes &ndash; die Gewichtsfunktion (englisch: <i>Weight Enumerator Function</i>) &nbsp;&#8658;&nbsp; siehe Kapitel 3.5.<br>
+
Je größer die freie Distanz <i>d</i><sub>F</sub> ist, desto besser ist das asymptotische Verhalten des Faltungscoders. Zur genauen Berechnung von Fehlerwahrscheinlichkeit benötigt man allerdings &ndash; ebenso wie bei den linearen Blockcodes &ndash; die [http://www.lntwww.de/Kanalcodierung/Schranken_f%C3%BCr_die_Blockfehlerwahrscheinlichkeit#Distanzspektrum_eines_linearen_Codes_.282.29 Gewichtsfunktion] (englisch: <i>Weight Enumerator Function</i>) &nbsp;&#8658;&nbsp; siehe [http://www.lntwww.de/Beispiele_von_Nachrichtensystemen/Allgemeine_Beschreibung_von_DSL#Motivation_f.C3.BCr_xDSL Kapitel 3.5.]<br>
  
 
Die freie Distanz <i>d</i><sub>F</sub> nimmt mit wachsendem Gedächtnis <i>m</i> zu, vorausgesetzt, man verwendet für die Übertragungsfunktionsmatrix <b>G</b>(<i>D</i>) geeignete Polynome. In der Tabelle sind für Rate&ndash;1/2&ndash;Faltungscodes die  <i>n</i> = 2 Polynome zusammen mit dem <i>d</i><sub>F</sub>&ndash;Wert angegeben. Von Bedeutung ist insbesondere der sog. <i>Industriestandardcode</i> mit <i>m</i> = 6 &nbsp;&#8658;&nbsp; 64 Zustände und der freien Distanz <i>d</i><sub>F</sub> = 10.<br>
 
Die freie Distanz <i>d</i><sub>F</sub> nimmt mit wachsendem Gedächtnis <i>m</i> zu, vorausgesetzt, man verwendet für die Übertragungsfunktionsmatrix <b>G</b>(<i>D</i>) geeignete Polynome. In der Tabelle sind für Rate&ndash;1/2&ndash;Faltungscodes die  <i>n</i> = 2 Polynome zusammen mit dem <i>d</i><sub>F</sub>&ndash;Wert angegeben. Von Bedeutung ist insbesondere der sog. <i>Industriestandardcode</i> mit <i>m</i> = 6 &nbsp;&#8658;&nbsp; 64 Zustände und der freien Distanz <i>d</i><sub>F</sub> = 10.<br>
Zeile 171: Zeile 171:
 
[[Datei:P ID2640 KC T 3 3 S4d v3.png|Zustandsübergangsdiagramm 3 für <i>n</i> = 2, <i>k</i> = 1, <i>m</i> = 2|class=fit]]<br>
 
[[Datei:P ID2640 KC T 3 3 S4d v3.png|Zustandsübergangsdiagramm 3 für <i>n</i> = 2, <i>k</i> = 1, <i>m</i> = 2|class=fit]]<br>
  
Verwendet man <b>G</b>(<i>D</i>) = (1+<i>D</i>, 1+<i>D</i><sup>2</sup>), so ändert sich das Zustandsübergangsdiagramm gegenüber dem Standard&ndash;Coder &nbsp;&#8658;&nbsp; Seite 2a nur wenig. Die Auswirkungen sind aber gravierend:
+
Verwendet man <b>G</b>(<i>D</i>) = (1+<i>D</i>, 1+<i>D</i><sup>2</sup>), so ändert sich das Zustandsübergangsdiagramm gegenüber dem Standard&ndash;Coder &nbsp;&#8658;&nbsp; [http://www.lntwww.de/Kanalcodierung/Codebeschreibung_mit_Zustands%E2%80%93_und_Trellisdiagramm#Darstellung_im_Zustands.C3.BCbergangsdiagramm_.281.29 Seite 2a] nur wenig. Die Auswirkungen sind aber gravierend:
 
*Die freie Distanz ist nun nicht mehr <i>d</i><sub>F</sub> = 5, sondern nur noch <i>d</i><sub>F</sub> = 3, wobei die Codesequenz <u><i>x</i></u> = (11, 01, 00, 00, ...) zur Informationssequenz <u><i>u</i></u> = <u>1</u> = (1, 1, 1, 1, ...) gehört.<br>
 
*Die freie Distanz ist nun nicht mehr <i>d</i><sub>F</sub> = 5, sondern nur noch <i>d</i><sub>F</sub> = 3, wobei die Codesequenz <u><i>x</i></u> = (11, 01, 00, 00, ...) zur Informationssequenz <u><i>u</i></u> = <u>1</u> = (1, 1, 1, 1, ...) gehört.<br>
  
Zeile 215: Zeile 215:
 
*eine möglichst große freie Distanz <i>d</i><sub>F</Sub> besitzt, die natürlich kleiner ist als die des Muttercodes.<br><br>
 
*eine möglichst große freie Distanz <i>d</i><sub>F</Sub> besitzt, die natürlich kleiner ist als die des Muttercodes.<br><br>
  
{{Beispiel}}''':''' Ausgehend von unserem Rate&ndash;1/2&ndash;Standardcode mit den Parametern <i>n</i><sub>0</sub> = 2, <i>m</i> = 2 erhält man mit der Punktierungsmatrix
+
{{Beispiel}}''':''' Ausgehend von unserem [http://www.lntwww.de/Kanalcodierung/Grundlagen_der_Faltungscodierung#Rate.E2.80.931.2F2.E2.80.93Faltungscodierer_.281.29 Rate&ndash;1/2&ndash;Standardcode] mit den Parametern <i>n</i><sub>0</sub> = 2, <i>m</i> = 2 erhält man mit der Punktierungsmatrix
  
 
:<math>{\boldsymbol{\rm P}} =  
 
:<math>{\boldsymbol{\rm P}} =  
Zeile 234: Zeile 234:
 
*Modifizierte Empfangssequenz:&nbsp;&nbsp;&nbsp;&nbsp; <u><i>y</i></u>' = (11, 1E, E1, 11, 0E, E1, ...).<br><br>
 
*Modifizierte Empfangssequenz:&nbsp;&nbsp;&nbsp;&nbsp; <u><i>y</i></u>' = (11, 1E, E1, 11, 0E, E1, ...).<br><br>
  
Jedes punktierte Bit in der Empfangssequenz <u><i>y</i></u> (markiert durch einen Unterstrich) wird also durch ein <i>Erasure</i> E ersetzt &ndash; siehe Binary Erasure Channel. Ein solches durch die Punktierung entstandene <i>Erasure</i> wird vom Decoder genauso behandelt wie eine Auslöschung durch den Kanal.<br>
+
Jedes punktierte Bit in der Empfangssequenz <u><i>y</i></u> (markiert durch einen Unterstrich) wird also durch ein <i>Erasure</i> E ersetzt &ndash; siehe [http://www.lntwww.de/Kanalcodierung/Klassifizierung_von_Signalen#Binary_Erasure_Channel_.E2.80.93_BEC Binary Erasure Channel.] Ein solches durch die Punktierung entstandene <i>Erasure</i> wird vom Decoder genauso behandelt wie eine Auslöschung durch den Kanal.<br>
  
 
Natürlich erhöht sich durch die Punktierung die Fehlerwahrscheinlichkeit. Dies kann man bereits daran erkennen, dass die freie Distanz nach der Punktierung auf <i>d</i><sub>F</sub> = 3 sinkt. Demgegenüber besitzt der Muttercode die freie Distanz <i>d</i><sub>F</sub> = 5.{{end}}<br>
 
Natürlich erhöht sich durch die Punktierung die Fehlerwahrscheinlichkeit. Dies kann man bereits daran erkennen, dass die freie Distanz nach der Punktierung auf <i>d</i><sub>F</sub> = 3 sinkt. Demgegenüber besitzt der Muttercode die freie Distanz <i>d</i><sub>F</sub> = 5.{{end}}<br>

Version vom 24. Januar 2017, 21:37 Uhr

Zustandsdefinition für ein Speicherregister (1)


Ein Faltungscodierer kann auch als Automat mit endlicher Anzahl von Zuständen aufgefasst werden. Die Zustandsanzahl ergibt sich dabei aus der Zahl der Speicherelemente  ⇒  Gedächtnis m zu 2m.

Faltungscodierer mit k = 1, n = 2 und m = 2

Im Kapitel 3.3 gehen wir meist vom gezeichneten Faltungscodierer aus, der durch folgende Kenngrößen charakterisiert wird:

  • k = 1, n = 2  ⇒  Coderate R = 1/2,
  • Gedächtnis m = 2  ⇒  Einflusslänge ν = 3,
  • Übertragungsfunktionsmatrix in Oktalform (7, 5)  ⇒  G(D) =(1 + D + D2, 1 + D2).

Die Codesequenz zum Zeitpunkt i  ⇒  xi = (xi(1), xi(2)) hängt außer vom Informationsbit ui auch vom Inhalt (ui–1, ui–2) des Speichers ab. Hierfür gibt es 2m = 4 Möglichkeiten, die man als die Zustände S0, S1, S2 und S3 bezeichnet. Der Registerzustand Sμ sei dabei über den Index definiert:

\[\mu = u_{i-1} + 2 \cdot u_{i-2}\hspace{0.05cm}, \hspace{0.5cm}{\rm allgemein\hspace{-0.1cm}:}\hspace{0.15cm} \mu = \sum_{l = 1}^{m} \hspace{0.1cm}2\hspace{0.03cm}^{l-1} \cdot u_{i-l} \hspace{0.05cm}.\]

Im Englischen verwendet man für „Zustand” den Begriff State. Entsprechend ist auch im deutschen Text manchmal vom Registerstatus die Rede.

Um Verwechslungen zu vermeiden, unterscheiden wir im Weiteren durch Groß– bzw. Kleinbuchstaben:

  • die möglichen Zustände Sμ mit den Indizes 0 ≤ μ ≤ 2m – 1,
  • die aktuellen Zustände si zu den Zeitpunkten i = 1, 2, 3, ....

Auf der nächsten Seite verdeutlichen wir die Zustände an einem Beispiel.

Zustandsdefinition für ein Speicherregister (2)


: Die folgende Grafik zeigt für obigen Faltungscodierer jeweils den Beginn (i ≤ 15)
  • der Informationssequenz u  ⇒  Informationsbits ui,
  • der aktuellen Zustände si ∈ {S0, S1, S2, S3} zu den Zeitpunkten i, sowie
  • der jeweiligen Codesequenzen xi = (xi(1), xi(2)).

Zur Verdeutlichung der Registerzustände Sμ

Die Farbkennzeichnungen sollen den Übergang zu den nachfolgenden Grafiken auf den nächsten Seiten erleichtern. Man erkennt aus obiger Darstellung beispielsweise:

  • Zum Zeitpunkt i = 5 gilt ui–1 = u4 = 0, ui–2 = u3 = 1. Das heißt, der Automat befindet sich im Zustand s5 = S2. Mit dem Informationsbit ui = u5 = 0 erhält man die Codesequenz x5 = (11).
  • Der Zustand für den Zeitpunkt i = 6 ergibt sich aus ui–1 = u5 = 0 und ui–2 = u4 = 0 zu s6 = S0. Wegen u6 = 0 wird nun x6 = (00) ausgegeben und der neue Zustand s7 ist wiederum S0.
  • Auch zum Zeitpunkt i = 12 wird wegen u12 = 0 die Codesequenz x12 = (11) ausgegeben und man geht vom Zustand s12 = S2 in den Zustand s13 = S0 über.
  • Dagegen wird zum Zeitpunkt i = 9 die Codesequenz (00) ausgegeben und auf s9 = S2 folgt s10 = S1. Gleiches gilt auch für i = 15. In beiden Fällen lautet das aktuelle Informationsbit ui = 1.


Aus diesem Beispiel ist zu erkennen, dass die Codesequenz xi zum Zeitpunkt i allein

  • vom aktuellen Zustand si = Sμ (0 ≤ μ ≤ 2m – 1), sowie
  • vom aktuellen Informationsbit ui

abhängt. Ebenso wird der Nachfolgezustand si+1 allein durch si und ui bestimmt. Diese Eigenschaften werden im so genannten Zustandsübergangsdiagramm auf der nächsten Seite berücksichtigt.

Darstellung im Zustandsübergangsdiagramm (1)


Die Grafik zeigt das Zustandsübergangsdiagramm (englisch: State Transition Diagram) für unseren Standardcodierer. Dieses liefert alle Informationen über den (n = 2, k = 1, m = 2)–Faltungscodierer in kompakter Form. Die Farbgebung ist mit der sequenziellen Darstellung auf der vorherigen Seite abgestimmt. Der Vollständigkeit halber ist auch die Herleitungstabelle nochmals angegeben.

Zustandsübertragungsdiagramm 1 für n = 2, k = 1, m = 2

Die 2m+k Übergänge sind mit „ui | xi” beschriftet. Beispielsweise ist abzulesen:

  • Durch das Informationsbit ui = 0 (gekennzeichnet durch eine rote Beschriftung) gelangt man vom Zustand si = S1 zum Zustand si+1 = S2 und die beiden Codebits lauten xi(1) = 1, xi(2) = 0.
  • Mit dem Informationsbit ui = 1 (blaue Beschriftung) im Zustand si = S1 ergeben sich dagegen die Codebits zu xi(1) = 0, xi(2) = 1, und man kommt zum neuen Zustand si+1 = S3.

Die Struktur des Zustandsübergangsdiagramms ist allein durch die Parameter m und k festgelegt:

  • Die Anzahl der Zustände ist 2m · k.
  • Von jedem Zustand gehen 2k Pfeile ab.

Ein weiteres Beispiel folgt auf der nächsten Seite.

Darstellung im Zustandsübergangsdiagramm (2)


Die obere Grafik zeigt nochmals das Zustandsübergangsdiagramm für unseren Standardcodierer. Dieses dient lediglich als Vergleichsgrundlage für das nachfolgende Beispiel.

Zustandsübertragungsdiagramm 1 für n = 2, k = 1, m = 2

Die untere Grafik gilt für einen systematischen Code, ebenfalls mit den Kenngrößen n = 2, k = 1, m = 2. Es handelt sich um die äquivalente systematische Repräsentation des obigen Codierers. Man bezeichnet diesen auch als RSC–Codierer (englisch: Recursive Systematic Convolutional Encoder).

Zustandsübertragungsdiagramm 2 für n = 2, k = 1, m = 2

Gegenüber dem oberen Zustandsübergangsdiagramm erkennt man folgende Unterschiede:

  • Da die früheren Informationsbits ui–1 und ui–2 nicht abgespeichert werden, beziehen sich hier die Zustände si = Sμ auf die verarbeiteten Größen wi–1 und wi–2, wobei wi = ui + wi–1 + wi–2 gilt.
  • Da dieser Code systematisch ist, gilt xi(1) = ui. Die Herleitung der zweiten Codebits xi(2) finden Sie in Aufgabe A3.5. Es handelt sich um ein rekursives Filter, wie in Kapitel 3.2 beschrieben.

Der Bildervergleich zeigt, dass sich für beide Codierer ein ähnliches Zustandsübergangsdiagramm ergibt:

  • Man gelangt von jedem Zustand si ∈ {S0, S1, S2,S3} zu den gleichen Nachfolgezuständen si+1.
  • Ein Unterschied besteht hinsichtlich der ausgegebenen Codesequenzen xi ∈ {00, 01, 10, 11}.

Darstellung im Trellisdiagramm (1)


Man kommt vom Zustandsübergangsdiagramm zum so genannten Trellisdiagramm (oder kurz: Trellis), indem man zusätzlich eine Zeitkomponente  ⇒  Laufvariable i berücksichtigt. Die folgende Grafik stellt die beiden Diagramme für unseren Standardcodierer (n = 2, k = 1, m = 2) gegenüber.

Zustandsübergangsdiagramm vs. Trellisdiagramm (n = 2, k = 1, m = 2)

Die untere Darstellung hat Ähnlichkeit mit einem Gartenspalier – etwas Phantasie vorausgesetzt. Die englische Übersetzung hierfür ist „Trellis”. Weiter ist anhand dieser Grafik zu erkennen:

  • Da alle Speicherregister mit Nullen vorbelegt sind, startet das Trellis stets vom Zustand s1 = S0. Zum nächsten Zeitpunkt (i = 2) sind dann nur die beiden Zustände S0 und S1 möglich.
  • Ab dem Zeitpunkt i = m + 1 = 3 hat das Trellis für jeden Übergang von si nach si+1 genau das gleiche Aussehen. Jeder Zustand Sμ ist durch einen roten Pfeil (ui = 0) und einen blauen Pfeil (ui = 1) mit einem Nachfolgezustand verbunden.
  • Gegenüber einem Codebaum, der mit jedem Zeitschritt i exponentiell anwächst – siehe zum Beispiel Kapitel 3.8, Seite 2a im Buch „Digitalsignalübertragung” – ist hier die Zahl der Knoten (also der möglichen Zustände) auf 2m begrenzt.
  • Diese erfreuliche Eigenschaft eines jeden Trellisdiagramms nutzt auch der Viterbi–Algorithmus zur effizienten Maximum–Likelihood–Decodierung von Faltungscodes.

Darstellung im Trellisdiagramm (2)


Das folgende Beispiel soll zeigen, dass zwischen der Aneinanderreihung der Codesequenzen xi und den Pfaden durch das Trellisdiagramm eine 1:1–Zuordnung besteht. Auch die Informationssequenz u ist aus dem ausgewählten Trellispfad anhand der Farben der einzelnen Zweige ablesbar. Ein roter Zweig steht für das Informationsbit ui = 0, ein blauer für ui = 1.

: Auf der ersten Seite dieses Abschnitts wurde für unseren Rate–1/2–Standardcodierer mit Gedächtnis m = 2 sowie die Informationssequenz u = (1, 1, 1, 0, 0, 0, 1, 0, 1, ...) die Codesequenz x hergeleitet, die in nachfolgender Tabelle für i ≤ 9 nochmals angegeben ist.

Trellisdiagramm einer Beispielssequenz

Darunter gezeichnet ist das Trellisdiagramm. Man erkennt:

  • Der ausgewählte Pfad durch das Trellis ergibt sich durch die Aneinanderreihung roter und blauer Pfeile, die für die möglichen Informationsbits ui = 0 bzw. ui = 1 stehen. Diese Aussage gilt für jeden Rate–1/n–Faltungscode. Bei einem Code mit k > 1 gäbe es 2k verschiedenfarbige Pfeile.
  • Bei einem Rate–1/n–Faltungscode sind die Pfeile mit den Codeworten xi = (xi(1), ... , (xi(n)) beschriftet, die sich aus dem Informationsbit ui und den aktuellen Registerzuständen si ergeben. Für n = 2 gibt es nur vier mögliche Codeworte, nämlich 00, 01, 10 und 11.
  • In vertikaler Richtung erkennt man aus dem Trellis die möglichen Registerzustände Sμ. Bei einem Rate–k/n–Faltungscode mit der Gedächtnisordnung m gibt es 2k · m verschiedene Zustände. Im vorliegenden Beispiel (k = 1, m = 2) sind dies nur die Zustände S0, S1, S2 und S3.


Definition der freien Distanz (1)


Als eine wichtige Kenngröße der linearen Blockcodes wurde in Kapitel 1.1 die minimale Hamming–Distanz zwischen zwei beliebigen Codeworten x und x' eingeführt:

\[d_{\rm min}(\mathcal{C}) = \min_{\substack{\underline{x},\hspace{0.05cm}\underline{x}' \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{C} \\ {\underline{x}} \hspace{0.05cm}\ne \hspace{0.05cm} \underline{x}'}}\hspace{0.1cm}d_{\rm H}(\underline{x}, \hspace{0.05cm}\underline{x}')\hspace{0.05cm}.\]

Aufgrund der Linearität gehört zu jedem Blockcode auch das Nullwort 0. Damit ist dmin auch gleich dem minimalen Hamming–Gewicht wH (x) eines Codewortes x0.

Bei Faltungscodes erweist sich die Beschreibung der Distanzverhältnisse als wesentlich aufwändiger, da ein Faltungscode aus unendlich langen und unendlich vielen Codesequenzen besteht.

: Die freie Distanz dF eines Faltungscodes ist gleich der Anzahl der Bits, in dem sich zwei beliebige Codesequenzen x und x' (mindestens) unterscheiden. Anders ausgedrückt: Die freie Distanz ist gleich der minimalen Hamming–Distanz zwischen zwei beliebigen Pfaden durch das Trellis.


Da Faltungscodes ebenfalls linear sind, kann man auch hier als Bezugssequenz die unendlich lange Nullsequenz heranziehen: x = 0. Damit ist die freie Distanz dF gleich dem minimalen Hamming–Gewicht (Anzahl der Einsen) einer Codesequenz x0.

: Wir betrachten die Nullsequenz 0 (weiß markiert) sowie zwei andere Codesequenzen x sowie x' (mit gelber bzw. dunkler Hinterlegung) in unserem Standard–Trellis und charakterisieren diese Sequenzen anhand der Zustandsfolgen:

\[\underline{0} \hspace{-0.15cm} = \hspace{-0.15cm} \left ( S_0 \rightarrow S_0 \rightarrow S_0\rightarrow S_0\rightarrow S_0\rightarrow \hspace{0.05cm}... \hspace{0.05cm}\right)= \left ( 00, 00, 00, 00, 00,\hspace{0.05cm} ... \hspace{0.05cm}\right) \hspace{0.05cm},\] \[\underline{x} \hspace{-0.15cm} = \hspace{-0.15cm} \left ( S_0 \rightarrow S_1 \rightarrow S_2\rightarrow S_0\rightarrow S_0\rightarrow \hspace{0.05cm}... \hspace{0.05cm}\right)= \left ( 11, 10, 11, 00, 00,\hspace{0.05cm} ... \hspace{0.05cm}\right) \hspace{0.05cm},\] \[\underline{x}' \hspace{-0.15cm} = \hspace{-0.15cm} \left ( S_0 \rightarrow S_1 \rightarrow S_3\rightarrow S_2\rightarrow S_0\rightarrow \hspace{0.05cm}... \hspace{0.05cm}\right)= \left ( 11, 01, 01, 11, 00,\hspace{0.05cm} ... \hspace{0.05cm}\right) \hspace{0.05cm}.\]

Zur Definition der freien Distanz

Man erkennt aus diesen Darstellungen:

  • Die freie Distanz dF = 5 ist gleich dem Hamming–Gewicht wH(x). Keine andere Sequenz als die gelb hinterlegte unterscheidet sich von 0 um weniger als 5 Bit. Beispielsweise ist wH(x′) = 6.
  • In diesem Beispiel ergibt sich die freie Distanz dF = 5 auch als die Hamming–Distanz zwischen den Sequenzen x und x′, die sich genau in fünf Bitpositionen unterscheiden.


Definition der freien Distanz (2)


Je größer die freie Distanz dF ist, desto besser ist das asymptotische Verhalten des Faltungscoders. Zur genauen Berechnung von Fehlerwahrscheinlichkeit benötigt man allerdings – ebenso wie bei den linearen Blockcodes – die Gewichtsfunktion (englisch: Weight Enumerator Function)  ⇒  siehe Kapitel 3.5.

Die freie Distanz dF nimmt mit wachsendem Gedächtnis m zu, vorausgesetzt, man verwendet für die Übertragungsfunktionsmatrix G(D) geeignete Polynome. In der Tabelle sind für Rate–1/2–Faltungscodes die n = 2 Polynome zusammen mit dem dF–Wert angegeben. Von Bedeutung ist insbesondere der sog. Industriestandardcode mit m = 6  ⇒  64 Zustände und der freien Distanz dF = 10.

Optimale Faltungscodes der Rate 1/2

Das folgende Beispiel zeigt, welche Auswirkungen es hat, wenn man ungünstige Polynome zugrundelegt.

: Unser (n = 2, k = 1, m = 2)–Standard–Coder basiert auf der Übertragungsfunktionsmatrix G(D) = (1+D+D2, 1+D2). Dieser weist die freie Distanz dF = 5 auf.

Zustandsübergangsdiagramm 3 für n = 2, k = 1, m = 2

Verwendet man G(D) = (1+D, 1+D2), so ändert sich das Zustandsübergangsdiagramm gegenüber dem Standard–Coder  ⇒  Seite 2a nur wenig. Die Auswirkungen sind aber gravierend:

  • Die freie Distanz ist nun nicht mehr dF = 5, sondern nur noch dF = 3, wobei die Codesequenz x = (11, 01, 00, 00, ...) zur Informationssequenz u = 1 = (1, 1, 1, 1, ...) gehört.
  • Das heißt: Durch nur drei Übertragungsfehler an den Positionen 1, 2, und 4 verfälscht man die Einssequenz (1) in die Nullsequenz (0) und produziert so unendlich viele Decodierfehler.
  • Einen Faltungscodierer mit diesen Eigenschaften bezeichnet man als katastrophal. Der Grund für dieses extrem ungünstige Verhalten ist, dass hier 1+D und 1+D2 nicht teilerfemd sind.


Terminierte Faltungscodes


Bei der theoretischen Beschreibung der Faltungscodes geht man stets von Informationssequenzen u und Codesequenzen x aus, die per Definition unendlich lang sind. In praktischen Anwendungen, siehe zum Beispiel GSM und UMTS verwendet man dagegen stets eine Informationssequenz endlicher Länge L. Bei einem Rate–1/n–Faltungscode hat dann die Codesequenz mindestens die Länge n · L.

Terminierter Faltungscode der Rate R = 128/260

Die Grafik zeigt ohne Hinterlegung das Trellis unseres Standard–Rate–1/2–Faltungscodes bei binärer Eingangsfolge u der endlichen Länge L = 128. Damit hat die Codefolge x die Länge 2 · L = 256. Aufgrund des undefinierten Endzustands ist eine vollständige Maximum–Likelihood–Decodierung der gesendeten Folge allerdings nicht möglich. Da man nicht weiß, welcher der Zustände S0, ... , S3 sich für i > L einstellen würden, wird die Fehlerwahrscheinlichkeit (etwas) größer sein als im Grenzfall L → ∞.

Um dies zu verhindern, terminiert man den Faltungscode entsprechend der Hinterlegung in obiger Grafik:

  • Man fügt an die L = 128 Informationsbits noch m = 2 Nullen an  ⇒  L' = 130.
  • Damit ergibt sich beispielsweise für den farblich hervorgehobenen Pfad durch das Trellis:
\[\underline{x}' = (11\hspace{0.05cm},\hspace{0.05cm} 01\hspace{0.05cm},\hspace{0.05cm} 01\hspace{0.05cm},\hspace{0.05cm} 00 \hspace{0.05cm},\hspace{0.05cm} ...\hspace{0.1cm},\hspace{0.05cm} 10\hspace{0.05cm},\hspace{0.05cm}00\hspace{0.05cm},\hspace{0.05cm} 01\hspace{0.05cm},\hspace{0.05cm} 01\hspace{0.05cm},\hspace{0.05cm} 11 \hspace{0.05cm} ) \]
\[\Rightarrow \hspace{0.3cm}\underline{u}' = (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.1cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0 \hspace{0.05cm} ) \hspace{0.05cm}.\]
  • Das Trellis endet nun stets (also unabhängig von den Daten) im definierten Endzustand S0 und man erreicht so die bestmögliche Fehlerwahrscheinlichkeit entsprechend Maximum–Likelihood.
  • Die Verbesserung hinsichtlich der Fehlerwahrscheinlichkeit erkauft man sich allerdings auf Kosten einer kleineren Coderate. Gilt L >> m, so ist dieser Verlust nur gering. Im betrachteten Beispiel ergibt sich mit Terminierung die Coderate R ' = 0.5 · L/(L + m) ≈ 0.492 anstelle von R = 0.5.

Punktierte Faltungscodes


Wir gehen von einem Faltungscode der Rate R0 = 1/n0 aus, den wir Muttercode nennen. Streicht man von dessen Codesequenz einige Bits entsprechend einem vorgegebenen Muster, so spricht man von einem punktierten Faltungscode (englisch: Punctured Convolutional Code) mit der Coderate R > R0.

Die Punktierung geschieht mittels der Punktierungsmatrix P mit folgenden Eigenschaften:

  • Die Zeilenzahl ist n0, die Spaltenzahl gleich der Punktierungsperiode p, die durch die gewünschte Coderate bestimmt wird.
  • Die n0 · p Matrixelemente Pij sind binär (0 oder 1). Bei Pij = 1 wird das entsprechende Codebit übernommen, bei Pij = 0 punktiert.
  • Die Rate des punktierten Faltungscodes ergibt sich als der Quotient aus p und der Anzahl N1 der Einsen in der P–Matrix.

Man findet günstig punktierte Faltungscodes üblicherweise nur mittels computergestützter Suche. Dabei bezeichnet man einen punktierten Faltungscode dann als günstig, wenn er

  • die gleiche Gedächtnisordnung m aufweist wie der Muttercode (auch die Gesamteinflusslänge ist in beiden Fällen gleich: ν = m + 1),
  • eine möglichst große freie Distanz dF besitzt, die natürlich kleiner ist als die des Muttercodes.

: Ausgehend von unserem Rate–1/2–Standardcode mit den Parametern n0 = 2, m = 2 erhält man mit der Punktierungsmatrix

\[{\boldsymbol{\rm P}} = \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}\hspace{0.3cm}\Rightarrow \hspace{0.3cm} p = 3\hspace{0.05cm}, \hspace{0.2cm}N_1 = 4\]

einen punktierten Faltungscode der Rate R = p/N1 = 3/4. Wir betrachten hierzu folgende Konstellation:

  • Informationssequenz:                     u = (1, 0, 0, 1, 1, 0, ...),
  • Codesequenz ohne Punktierung:    x = (11, 10, 11, 11, 01, 01, ...),
  • Codesequenz mit Punktierung:      x' = (11, 1_, _1, 11, 0_, _1, ...),
  • Empfangssequenz ohne Fehler:      y = (11, 1_, _1, 11, 0_, _1, ...),
  • Modifizierte Empfangssequenz:     y' = (11, 1E, E1, 11, 0E, E1, ...).

Jedes punktierte Bit in der Empfangssequenz y (markiert durch einen Unterstrich) wird also durch ein Erasure E ersetzt – siehe Binary Erasure Channel. Ein solches durch die Punktierung entstandene Erasure wird vom Decoder genauso behandelt wie eine Auslöschung durch den Kanal.

Natürlich erhöht sich durch die Punktierung die Fehlerwahrscheinlichkeit. Dies kann man bereits daran erkennen, dass die freie Distanz nach der Punktierung auf dF = 3 sinkt. Demgegenüber besitzt der Muttercode die freie Distanz dF = 5.


Eine Anwendung findet die Punktierung zum Beispiel bei den so genannten RCPC–Codes (Rate Compatible Punctered Convolutional Codes). Näheres hierzu in der Aufgabe A3.8.

Aufgaben


A3.6 Zustandsübergangsdiagramm

Zusatzaufgaben:3.6 Übergangsdiagramm für m = 3

A3.7 Vergleich zweier Faltungscoder

Zusatzaufgaben:3.7 Welcher Code ist katastrophal ?

A3.8 RCPC–Codes