Distanzeigenschaften und Fehlerwahrscheinlichkeitsschranken
Inhaltsverzeichnis
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).
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.
Pfadgewichtsfunktion (2)
\[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 φ0 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 Aw die Anzahl der Pfade mit Pfadgewicht w bezeichnet. Die Summe beginnt mit w = dF.
- Das Pfadgewicht w(φj) ist gleich dem Hamming–Gewicht (also der Anzahl der Einsen) der zum Pfad φj assoziierten Codesequenz xj:
- \[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 xi = 0 mitgezählt, wohingegen die Nullcodesequenz xi = 0 bzw. der Nullpfad φ0 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
\[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 uj. Es wird als Potenz des Formalparameters U ausgedrückt.
- Der Koeffizient Aw, 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 5 – setzt sich aus einem blauen Pfeil (ui = 1) und zwei roten Pfeilen (ui = 0) zusammen. Somit wird aus X 5 der erweiterte Term UX 5.
- Die Sequenzen der beiden grünen Pfade sind u2 = (1, 1, 0, 0) ⇒ x2 = (11, 01, 01, 11) sowie u3 = (1, 0, 1, 0, 0) ⇒ x3 = (11, 10, 00, 10, 11). Daraus ergibt sich der zweite Term 2 · U 2X 6.
- Der graue Pfad (und die drei nicht gezeichneten Pfade) ergeben zusammen den Beitrag 4 · U 3X 7. Jeder dieser Pfade beinhaltet drei blaue Pfeile ⇒ drei Einsen in jeder Informationssequenz.
Pfadgewichtsfunktion aus Zustandsübergangsdiagramm (1)
Es gibt eine elegante Methode, um die Pfadgewichtsfunktion T(X) und deren Erweiterung direkt aus dem Zustandsübergangsdiagramm zu bestimmen. Dies soll hier und auf den folgenden Seiten am Beispiel unseres Standardcodes demonstriert werden.
Zunächst muss dazu das Zustandsübergangsdiagramm umgezeichnet werden. Die Grafik zeigt dieses links in der bisherigen Form als Diagramm (A), während rechts das neue Diagramm (B) angegeben ist.
Man erkennt:
- Der Zustand S0 wird aufgespalten in den Startzustand S0 und den Endzustand S0'. Damit lassen sich alle Pfade des Trellisdiagramms, die im Zustand S0 beginnen und irgendwann zu diesem zurückkehren, auch im rechten Graphen (B) nachvollziehen. Ausgeschlossen sind dagegen direkte Übergänge von S0 nach S0′ und damit auch der Nullpfad (Dauer–S0).
- Im Diagramm (A) sind die Übergänge anhand der Farben Rot (für ui = 0) und Blau (für ui = 1) unterscheidbar, und die Codeworte xi ∈ {00, 01, 10, 11} sind an den Übergängen vermerkt. Im neuen Diagramm (B) werden (00) durch X 0 = 1 und (11) durch X 2 ausgedrückt. Die Codeworte (01) und (10) sind nun nicht mehr unterscheidbar, sondern werden einheitlich mit X bezeichnet.
- Anders formuliert: Das Codewort xi wird nun als X w dargestellt, wobei X eine dem Ausgang (der Codesequenz) zugeordnete Dummy–Variable ist und w = wH(xi) das Hamming–Gewicht des Codewortes xi angibt. Bei einem Rate–1/2–Code ist der Exponent w entweder 0, 1 oder 2.
- Ebenfalls verzichtet wird im Diagramm (B) auf die Farbcodierung. Das Informationsbit ui = 1 wird nun durch U 1 = U und das Informationsbit ui = 0 durch U 0 = 1 gekennzeichnet. Die Dummy–Variable U ist also der Eingangssequenz u zugeordnet.
Die Beschreibung wird auf den nächsten Seiten fortgesetzt.
Pfadgewichtsfunktion aus Zustandsübergangsdiagramm (2)
Ziel unserer Berechnungen wird es sein, den (beliebig komplizierten) Weg von S0 nach S0' durch die erweiterte Pfadgewichtsfunktion Tenh(X, U) zu charakterisieren. Dazu benötigen wir Regeln, um den Graphen schrittweise vereinfachen zu können.
Serielle Übergänge
Zwei serielle Verbindungen – gekennzeichnet durch A(X, U) und B(X, U) – können durch eine einzige Verbindung mit dem Produkt dieser Bewertungen ersetzt werden.
Parallele Übergänge
Zwei parallele Verbindungen werden durch die Summe ihrer Bewertungsfunktionen zusammengefasst.
Ring Die nebenstehende Konstellation kann durch eine einzige Verbindung ersetzt werden, wobei für die Ersetzung gilt:
\[E(X, U) = \frac{A(X, U) \cdot B(X, U)}{1- C(X, U)}
\hspace{0.05cm}.\]
Rückkopplung
Durch die Rückkopplung können sich hier zwei Zustände beliebig oft abwechseln. Für diese Konstellation gilt:
\[F(X, U) = \frac{A(X, U) \cdot B(X, U)\cdot C(X, U)}{1- C(X, U)\cdot D(X, U)} \hspace{0.05cm}.\]
Die hier angegebenen Gleichungen für Ring und Rückkopplung sind in Aufgabe Z3.12 zu beweisen.
Pfadgewichtsfunktion aus Zustandsübergangsdiagramm (3)
Die auf der letzten Seite genannten Regeln sollen nun auf unser Standardbeispiel angewendet werden. In der unteren Grafik sehen Sie links das modifizierte Zustandsübergangsdiagramm (B).
- Zunächst ersetzen wir den rot hinterlegten Umweg von S1 nach S2 über S3 im Diagramm (B) durch die im Diagramm (C) eingezeichnete rote Verbindung. Es handelt sich nach der Klassifizierung auf der letzten Seite um einen „Ring” mit den Beschriftungen A = C = U · X und B = X, und wir erhalten die erste Reduktionsfunktion:
- \[T_1(X, U) = \frac{U \cdot X^2}{1- U \cdot X} \hspace{0.05cm}.\]
- Nun fassen wir die parallelen Verbindungen entsprechend der blauen Hinterlegung im Diagramm (C) zusammen und ersetzen diese durch die blaue Verbindung im Diagramm (D). Die zweite Reduktionsfunktion lautet somit:
- \[T_2(X, U) = T_1(X, U) + X = \frac{U X^2 + X \cdot (1-UX)}{1- U X} = \frac{X}{1- U X} \hspace{0.05cm}.\]
- Der gesamte Graph (D) kann somit durch eine einzige Verbindung von S0 nach S0' ersetzt werden. Nach der Rückkopplungsregel erhält man für die erweiterte Pfadgewichtsfunktion:
- \[T_{\rm enh}(X, U) = \frac{(U X^2) \cdot X^2 \cdot \frac{X}{1- U X}}{1- U \cdot \frac{X}{1- U X}} = \frac{U X^5}{1- U X- U X} = \frac{U X^5}{1- 2 \cdot U X} \hspace{0.05cm}.\]
Mit der Reihenentwicklung 1/(1 – x) = 1 + x + x2 + x3 + ... lässt sich hierfür auch schreiben:
\[T_{\rm enh}(X, U) = U X^5 \cdot \left [ 1 + 2 \hspace{0.05cm}UX + (2 \hspace{0.05cm}UX)^2 + (2 \hspace{0.05cm}UX)^3 + ... \hspace{0.05cm} \right ] \hspace{0.05cm}.\]
Setzt man die formale Input–Variable U = 1, so erhält man die „einfache” Pfadgewichtsfunktion, die allein Aussagen über die Gewichtsverteilung der Ausgangssequenz x erlaubt:
\[T(X) = X^5 \cdot \left [ 1 + 2 X + 4 X^2 + 8 X^3 + ... \hspace{0.05cm} \right ] \hspace{0.05cm}.\]
Das gleiche Ergebnis haben wir bereits aus dem Trellisdiagramm auf Seite 2a abgelesen. Dort gab es einen grauen Pfad mit Gewicht 5, zwei gelbe Pfade mit Gewicht 6 und vier grüne Pfade mit Gewicht 7.
