Kanalcodierung/Distanzeigenschaften und Fehlerwahrscheinlichkeitsschranken

1. Kanalcodierung
2. Faltungscodierung und geeignete Decoder
3. Distanzeigenschaften und Fehlerwahrscheinlichkeitsschranken

• Vorherige Seite
• Nächste Seite

• Vorherige Seite
• Nächste Seite

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 d_H(x, 0) das gleiche Ergebnis liefert wie das Hamming–Gewicht w_H(x).

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

Alle Codeworte außer dem Nullwort (0) beinhalten mindestens drei Einsen ⇒  d_min = 3. Es gibt sieben Codeworte mit drei Einsen, sieben mit vier Einsen und je eines ohne Einsen bzw. mit sieben Einsen.

Die freie Distanz d_F 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 d_F 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 w_H(x) = d_F = 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 φ₀.
  

• 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 Φ = {φ₁, φ₂, φ₃, ...} noch immer eine unbegrenzte Menge an Pfaden. φ₀ gehört nicht zu dieser Menge.

Im obigen Trellis sind einige Pfade φ_j ∈ Φ eingezeichnet:

• Der gelbe Pfad φ₁ gehört zur Sequenz x₁ = (11, 10, 11) mit dem Hamming–Gewicht w_H(x₁) = 5. Damit ist auch das Pfadgewicht w(φ₁) = 5. Aufgrund der Festlegung des Abzweigzeitpunktes t hat nur noch dieser einzige Pfad φ₁ die freie Distanz d_F = 5 zum Nullpfad  ⇒  A₅ = 1.
  

• Für die beiden grünen Pfade mit den korrespondierenden Sequenzen x₂ = (11, 01, 01, 11) bzw. x₃ = (11, 10, 00, 10, 11) gilt w(φ₂) = w(φ₃) = 6. Kein anderer Pfad weist das Pfadgewicht 6 auf. Wir berücksichtigen diese Tatsache durch den Koeffizienten A₆ = 2.
  

• Eingezeichnet ist auch der graue Pfad φ₄, assoziiert mit der Sequenz x₄ = (11, 01, 10, 01, 11)  ⇒  w(φ₄) = 7. Auch die Sequenzen x₅ = (11, 01, 01, 00, 10, 11), x₆ = (11, 10, 00, 01, 01, 11) und x₇ = (11, 10, 00, 10, 00, 10, 11) weisen jeweils das gleiche Pfadgewicht 7 auf  ⇒  A₇ = 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.

Pfadgewichtsfunktion (2)

: Für die Pfadgewichtsfunktion (englisch: Path Weight Enumerator Function, PWEF) eines Faltungscodes gilt:

\[T(X) = \sum_{\varphi_j \in {\it \Phi}}\hspace{0.1cm} X^{w(\varphi_j)} \hspace{0.1cm}=\hspace{0.1cm} \sum_{w = d_{\rm F}}^{\infty}\hspace{0.1cm} A_w \cdot X^w \hspace{0.05cm}.\]

• Φ bezeichnet die Menge aller Pfade an, die den Nullpfad φ₀ genau zum festgelegten Zeitpunkt t verlassen und (irgendwann) später zu diesem zurückkehren.
  

• Gemäß der zweiten Gleichung sind die Summanden nach ihren Pfadgewichten w geordnet, wobei A_w die Anzahl der Pfade mit Pfadgewicht w bezeichnet. Die Summe beginnt mit w = d_F.
  

• Das Pfadgewicht w(φ_j) ist gleich dem Hamming–Gewicht (also der Anzahl der Einsen) der zum Pfad φ_j assoziierten Codesequenz x_j:

\[w({\varphi_j) = w_{\rm H}(\underline {x}}_j) \hspace{0.05cm}.\]

Hinweis: Die für die linearen Blockcodes definierte Gewichtsfunktion W(X) und die hier definierte Pfadgewichtsfunktion T(X) weisen viele Gemeinsamkeiten auf, sie sind jedoch nicht identisch.

Betrachten wir nochmals die Gewichtsfunktion

\[W(X) = 1 + 7 \cdot X^{3} + 7 \cdot X^{4} + X^{7}\]

des (7, 4, 3)–Hamming–Codes und die Pfadgewichtsfunktion

\[T(X) = X^5 + 2 \cdot X^6 + 4 \cdot X^7+ 8 \cdot X^8+ ... \]

unseres Standard–Faltungscodierers, so fällt die „1” in der ersten Gleichung auf. Das heißt: Bei den linearen Blockcodes wird das Bezugs–Codewort x_i = 0 mitgezählt, wohingegen die Nullcodesequenz x_i = 0 bzw. der Nullpfad φ₀ bei den Faltungscodes ausgeschlossen wird. Nach Ansicht der Autoren hätte man auch W(X) ohne die „1” definieren können. Damit wäre unter anderem vermieden worden, dass sich die Bhattacharyya–Schranke für lineare Blockcodes und für Faltungscodes durch „–1” unterscheiden, wie aus den folgenden Gleichungen hervorgeht:

Bhattacharyya–Schranke für die linearen Blockcodes:

\[{\rm Pr(Blockfehler)} \le W(X = \beta) -1 \hspace{0.05cm},\]

Bhattacharyya–Schranke für die Faltungscodes:

\[{\rm Pr(Burstfehler)} \le T(X = \beta) \hspace{0.05cm},\]

Die Pfadgewichtsfunktion T(X) liefert nur Informationen hinsichtlich der Gewichte der Codesequenz x. Mehr Informationen erhält man, wenn zusätzlich auch die Gewichte der Informationssequenz u erfasst werden. Man benötigt dann zwei Formalparameter X und U, wie aus der Definition auf der folgenden Seite hervorgeht.

Erweiterte Pfadgewichtsfunktion

: Die erweiterte Pfadgewichtsfunktion (englisch: Enhanced Path Weight Enumerator Function, EPWEF) lautet:

\[T_{\rm enh}(X, U) = \sum_{\varphi_j \in {\it \Phi}}\hspace{0.1cm} X^{w(\varphi_j)} \cdot U^{{ u}(\varphi_j)} \hspace{0.1cm}=\hspace{0.1cm} \sum_{w} \sum_{u}\hspace{0.1cm} A_{w, \hspace{0.05cm}u} \cdot X^w \cdot U^{u} \hspace{0.05cm}.\]

Es gelten alle Angaben der Definition von T(X) auf der letzten Seite. Zusätzlich ist zu beachten:

• Das Pfadeingangsgewicht u(φ_j) ist gleich dem Hamming–Gewicht der zum Pfad φ_j assoziierten Informationssequenz u_j. Es wird als Potenz des Formalparameters U ausgedrückt.
  

• Der Koeffizient A_w, u bezeichnet die Anzahl der Pfade φ_j mit dem Pfadausgangsgewicht w(φ_j) und dem Pfadeingangsgewicht u(φ_j). Als Laufvariable für den zweiten Anteil wird u verwendet.
  

• Setzt man in der erweiterten Pfadgewichtsfunktion den Formalparameter U = 1, so ergibt sich die ursprüngliche Gewichtsfunktion T(X) gemäß der Definition auf der letzten Seite.
  
  

Bei vielen (und allen relevanten) Faltungscodes lässt sich obere Gleichung noch vereinfachen:

\[T_{\rm enh}(X, U) =\hspace{0.1cm} \sum_{w = d_{\rm F}}^{\infty}\hspace{0.1cm} A_w \cdot X^w \cdot U^{u} \hspace{0.05cm}.\]

Die erweiterte Pfadgewichtsfunktion unseres Standardcodieres lautet somit:

\[T_{\rm enh}(X, U) = U \cdot X^5 + 2 \cdot U^2 \cdot X^6 + 4 \cdot U^3 \cdot X^7+ ... \hspace{0.1cm} \hspace{0.05cm}.\]

Vergleicht man dieses Ergebnis mit dem unten dargestellten Trellis, so erkennt man:

• Der gelb hinterlegte Pfad – gekennzeichnet durch X ⁵ – setzt sich aus einem blauen Pfeil (u_i = 1) und zwei roten Pfeilen (u_i = 0) zusammen. Somit wird aus X ⁵ der erweiterte Term UX ⁵.
  

• Die Sequenzen der beiden grünen Pfade sind u₂ = (1, 1, 0, 0)  ⇒  x₂ = (11, 01, 01, 11) sowie u₃ = (1, 0, 1, 0, 0)  ⇒  x₃ = (11, 10, 00, 10, 11). Daraus ergibt sich der zweite Term 2 · U ²X ⁶.
  

• Der graue Pfad (und die drei nicht gezeichneten Pfade) ergeben zusammen den Beitrag 4 · U ³X ⁷. Jeder dieser Pfade beinhaltet drei blaue Pfeile  ⇒  drei Einsen in jeder Informationssequenz.