Distanzeigenschaften und Fehlerwahrscheinlichkeitsschranken

Aus LNTwww
< Kanalcodierung
Version vom 16. Januar 2017, 18:33 Uhr von Ayush (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „ {{Header |Untermenü=Faltungscodierung und geeignete Decoder |Vorherige Seite=Decodierung von Faltungscodes |Nächste Seite=Soft–in Soft–out Decoder }}…“)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Wechseln zu:Navigation, Suche

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).

: Beispiel: Die nachfolgende Tabelle zeigt die 16 Codeworte des (7, 4, 3)–Hamming–Codes.

Codewort des (7, 4, 3)–Hamming–Codes

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).

Einige Pfade mit w(x) = dF

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.

Einige Pfade und ihre Pfadgewichte

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.