Distanzeigenschaften und Fehlerwahrscheinlichkeitsschranken
Freie Distanz vs. Minimale Distanz
Eine äußerst wichtige Kenngröße hinsichtlich der Fehlerwahrscheinlichkeit eines linearen Blockcodes ist die minimale Distanz zwischen zwei Codeworten:
\[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}.\]
Der zweite Gleichungsteil ergibt sich aus der Tatsache, dass jeder lineare Code auch das Nullwort (0) beinhaltet. Zweckmäßigerweise setzt man deshalb x' = 0, so dass die Hamming–Distanz dH(x, 0) das gleiche Ergebnis liefert wie das Hamming–Gewicht wH(x).
Alle Codeworte außer dem Nullwort (0) beinhalten mindestens drei Einsen ⇒ dmin = 3. Es gibt sieben Codeworte mit drei Einsen, sieben mit vier Einsen und je eines ohne Einsen bzw. mit sieben Einsen.
Die freie Distanz dF eines Faltungscodes (Convolution Code ⇒ CC) unterscheidet sich formelmäßig nicht von der minimalen Distanz eines linearen Blockcodes:
\[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}.\]
In der Literatur wird anstelle von dF teilweise auch d∞ verwendet.
- Wesentlicher Unterschied zur minimalen Distanz ist, dass bei Faltungscodes nicht Informations– und Codeworte zu betrachten sind, sondern Sequenzen mit der Eigenschaft semi–infinite.
- Jede Codesequenz x beschreibt einen Pfad durch das Trellis. Die freie Distanz ist dabei das kleinstmögliche Hamming–Gewicht eines solchen Pfades (mit Ausnahme des Nullpfades).
Die Grafik zeigt drei der unendlich vielen Pfade mit dem minimalen Hamming–Gewicht wH(x) = dF = 5.
Pfadgewichtsfunktion (1)
Für jeden linearen Blockcode lässt sich wegen der endlichen Anzahl an Codeworten x in einfacher Weise eine Gewichtsfunktion angeben. Für das Beispiel auf der letzten Seite lautet diese:
\[W(X) = 1 + 7 \cdot X^{3} + 7 \cdot X^{4} + X^{7}\hspace{0.05cm}.\]
Bei einem (nicht terminierten) Faltungscode kann keine solche Gewichtsfunktion angegegeben werden, da es unendlich viele, unendlich lange Codesequenzen x 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 x = 0 und nennen diesen den Nullpfad φ0.
- Desweiteren betrachten wir nur noch solche Pfade φj ∈ Φ, die alle zu einer vorgegebenen Zeit t vom Nullpfad abweichen und irgendwann wieder zu diesem zurückkehren.
Obwohl nur ein Bruchteil aller Trellispfade zu dieser Menge Φ gehören, beinhaltet Φ = {φ1, φ2, φ3, ...} noch immer eine unbegrenzte Menge an Pfaden. φ0 gehört nicht zu dieser Menge.
Im obigen Trellis sind einige Pfade φj ∈ Φ eingezeichnet:
- Der gelbe Pfad φ1 gehört zur Sequenz x1 = (11, 10, 11) mit dem Hamming–Gewicht wH(x1) = 5. Damit ist auch das Pfadgewicht w(φ1) = 5. Aufgrund der Festlegung des Abzweigzeitpunktes t hat nur noch dieser einzige Pfad φ1 die freie Distanz dF = 5 zum Nullpfad ⇒ A5 = 1.
- Für die beiden grünen Pfade mit den korrespondierenden Sequenzen x2 = (11, 01, 01, 11) bzw. x3 = (11, 10, 00, 10, 11) gilt w(φ2) = w(φ3) = 6. Kein anderer Pfad weist das Pfadgewicht 6 auf. Wir berücksichtigen diese Tatsache durch den Koeffizienten A6 = 2.
- Eingezeichnet ist auch der graue Pfad φ4, assoziiert mit der Sequenz x4 = (11, 01, 10, 01, 11) ⇒ w(φ4) = 7. Auch die Sequenzen x5 = (11, 01, 01, 00, 10, 11), x6 = (11, 10, 00, 01, 01, 11) und x7 = (11, 10, 00, 10, 00, 10, 11) weisen jeweils das gleiche Pfadgewicht 7 auf ⇒ A7 = 4.
Damit lautet die Pfadgewichtsfunktion (englisch: Path Weight Enumerator Function, PWEF):
\[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}.\]
Die Definition dieser Funktion T(X) wird auf der nächsten Seite nachgeliefert.