Quelltext der Seite Kanalcodierung/Distanzeigenschaften und Fehlerwahrscheinlichkeitsschranken

 
{{Header
|Untermenü=Faltungscodierung und geeignete Decoder
|Vorherige Seite=Decodierung von Faltungscodes
|Nächste Seite=Soft–in Soft–out Decoder
}}

== Freie Distanz vs. Minimale Distanz ==
<br>
Eine äußerst wichtige Kenngröße hinsichtlich der Fehlerwahrscheinlichkeit eines linearen Blockcodes ist die <i>minimale Distanz</i> zwischen zwei Codeworten:

:<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}')
			=
			\min_{\substack{\underline{x} \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{C} \\ {\underline{x}} \hspace{0.05cm}\ne \hspace{0.05cm} \underline{0}}}\hspace{0.1cm}w_{\rm H}(\underline{x})
			\hspace{0.05cm}.</math>

Der zweite Gleichungsteil ergibt sich aus der Tatsache, dass jeder lineare Code auch das Nullwort (<u>0</u>) beinhaltet. Zweckmäßigerweise setzt man deshalb <u><i>x</i></u>' = <u>0</u>, so dass die Hamming&ndash;Distanz <i>d</i><sub>H</sub>(<u><i>x</i></u>, <u>0</u>) das gleiche Ergebnis liefert wie das Hamming&ndash;Gewicht <i>w</i><sub>H</sub>(<u><i>x</i></u>).<br>

{{Beispiel}}''':''' <b>Beispiel:</b> Die nachfolgende Tabelle zeigt die 16 Codeworte des (7, 4, 3)&ndash;Hamming&ndash;Codes.<br>

[[Datei:P ID2684 KC T 3 5 S1 neu.png|Codewort des (7, 4, 3)–Hamming–Codes|class=fit]]<br>

Alle Codeworte außer dem Nullwort (<u>0</u>)  beinhalten mindestens drei Einsen&nbsp;&#8658;&nbsp; <i>d</i><sub>min</sub> = 3. Es gibt sieben Codeworte mit drei Einsen, sieben mit vier Einsen und je eines ohne Einsen bzw. mit sieben Einsen.{{end}}<br>

Die <b>freie Distanz</b> <i>d</i><sub>F</sub> eines Faltungscodes (<i>Convolution Code</i> &#8658; CC) unterscheidet sich formelmäßig nicht von der minimalen Distanz eines linearen Blockcodes:

:<math>d_{\rm F}(\mathcal{CC}) =
			\min_{\substack{\underline{x},\hspace{0.05cm}\underline{x}' \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{CC} \\ {\underline{x}} \hspace{0.05cm}\ne \hspace{0.05cm} \underline{x}'}}\hspace{0.1cm}d_{\rm H}(\underline{x}, \hspace{0.05cm}\underline{x}')
			=
			\min_{\substack{\underline{x} \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{CC} \\ {\underline{x}} \hspace{0.05cm}\ne \hspace{0.05cm} \underline{0}}}\hspace{0.1cm}w_{\rm H}(\underline{x})
			\hspace{0.05cm}.</math>

In der Literatur wird anstelle von <i>d</i><sub>F</sub> teilweise auch <i>d</i><sub>&#8734;</sub> verwendet.
*Wesentlicher Unterschied zur minimalen Distanz ist, dass bei Faltungscodes nicht Informations&ndash; und Codeworte zu betrachten sind, sondern Sequenzen mit der Eigenschaft semi&ndash;infinite.<br>

*Jede Codesequenz <u><i>x</i></u> beschreibt einen Pfad durch das Trellis. Die freie Distanz ist dabei das kleinstmögliche Hamming&ndash;Gewicht eines solchen Pfades (mit Ausnahme des Nullpfades).<br>

[[Datei:P ID2685 KC T 3 5 S1c v1.png|Einige Pfade mit <i>w</i>(<u><i>x</i></u>) = <i>d</i><sub>F</sub>|class=fit]]<br>

Die Grafik zeigt drei der unendlich vielen Pfade mit dem minimalen Hamming&ndash;Gewicht <i>w</i><sub>H</sub>(<u><i>x</i></u>) = <i>d</i><sub>F</sub> = 5.<br>

== Pfadgewichtsfunktion (1) ==
<br>
Für jeden linearen Blockcode lässt sich wegen der endlichen Anzahl an Codeworten <u><i>x</i></u> in einfacher Weise eine Gewichtsfunktion angeben. Für das Beispiel auf der letzten Seite lautet diese:

:<math>W(X) = 1 + 7 \cdot X^{3} + 7 \cdot X^{4} + X^{7}\hspace{0.05cm}.</math>

Bei einem (nicht terminierten) Faltungscode kann keine solche Gewichtsfunktion angegegeben werden, da es unendlich viele, unendlich lange Codesequenzen <u><i>x</i></u> gibt, und damit auch unendlich viele Trellispfade. Um dieses Problem in den Griff zu bekommen, gehen wir nun von folgenden Voraussetzungen aus:
*Als Bezugsgröße für das Trellisdiagramm wählen wir stets den Pfad der Codesequenz <u><i>x</i></u> = <u>0</u> und nennen diesen den <i>Nullpfad &phi;</i><sub>0</sub>.<br>

*Desweiteren betrachten wir nur noch solche Pfade <i>&phi;<sub>j</sub></i> &#8712; <i>&Phi;</i>, die alle zu einer vorgegebenen Zeit <i>t</i> vom Nullpfad abweichen und irgendwann wieder zu diesem zurückkehren.<br><br>

Obwohl nur ein Bruchteil aller Trellispfade zu dieser Menge <i>&Phi;</i> gehören, beinhaltet <i>&Phi;</i> = {<i>&phi;</i><sub>1</sub>, <i>&phi;</i><sub>2</sub>, <i>&phi;</i><sub>3</sub>, ...} noch immer eine unbegrenzte Menge an Pfaden. <i>&phi;</i><sub>0</sub> gehört nicht zu dieser Menge.<br>

[[Datei:P ID2686 KC T 3 5 S2a v1.png|Einige Pfade und ihre Pfadgewichte|class=fit]]<br>

Im obigen Trellis sind einige Pfade <i>&phi;<sub>j</sub></i> &#8712; <i>&Phi;</i> eingezeichnet:
*Der gelbe Pfad <i>&phi;</i><sub>1</sub> gehört zur Sequenz <u><i>x</i></u><sub>1</sub> = (11, 10, 11) mit dem Hamming&ndash;Gewicht <i>w</i><sub>H</sub>(<u><i>x</i></u><sub>1</sub>) = 5. Damit ist auch das  Pfadgewicht <i>w</i>(<i>&phi;</i><sub>1</sub>) = 5. Aufgrund der Festlegung des Abzweigzeitpunktes <i>t</i> hat nur noch dieser einzige Pfad <i>&phi;</i><sub>1</sub> die freie Distanz <i>d</i><sub>F</sub> = 5 zum Nullpfad &nbsp;&#8658;&nbsp; <i>A</i><sub>5</sub> = 1.<br>

*Für die beiden grünen Pfade  mit den korrespondierenden Sequenzen <u><i>x</i></u><sub>2</sub> = (11, 01, 01,  11) bzw. <u><i>x</i></u><sub>3</sub> = (11, 10, 00, 10,  11)  gilt <i>w</i>(<i>&phi;</i><sub>2</sub>) = <i>w</i>(<i>&phi;</i><sub>3</sub>) = 6. Kein anderer Pfad weist das Pfadgewicht 6 auf. Wir berücksichtigen diese Tatsache  durch den Koeffizienten <i>A</i><sub>6</sub>&nbsp;=&nbsp;2.<br>

*Eingezeichnet ist auch der graue Pfad <i>&phi;</i><sub>4</sub>, assoziiert mit der Sequenz <u><i>x</i></u><sub>4</sub> = (11, 01, 10, 01,  11)  &nbsp;&#8658;&nbsp; <i>w</i>(<i>&phi;</i><sub>4</sub>) = 7. Auch die Sequenzen <u><i>x</i></u><sub>5</sub> = (11, 01, 01, 00, 10, 11), <u><i>x</i></u><sub>6</sub> = (11, 10, 00, 01, 01, 11) und <u><i>x</i></u><sub>7</sub> = (11, 10, 00, 10, 00, 10,  11)  weisen jeweils das gleiche Pfadgewicht 7 auf &nbsp;&#8658;&nbsp; <i>A</i><sub>7</sub>&nbsp;=&nbsp;4.<br><br>

Damit lautet die Pfadgewichtsfunktion (englisch: <i>Path Weight Enumerator Function</i>, PWEF):

:<math>T(X) = A_5 \cdot X^5 + A_6 \cdot X^6  + A_7 \cdot X^7 + ... \hspace{0.1cm}=  X^5 + 2 \cdot X^6  + 4 \cdot X^7+ ... \hspace{0.1cm}
\hspace{0.05cm}.</math>

Die Definition dieser Funktion <i>T</i>(<i>X</i>) wird auf der nächsten Seite nachgeliefert.<br>








{{Display}}