Channel Coding/Bounds for Block Error Probability

1. Channel Coding
2. Binäre Blockcodes zur Kanalcodierung
3. Bounds for Block Error Probability

• Previous page
• Next page

• Previous page
• Next page

Distanzspektrum eines linearen Codes (1)

Wir gehen weiterhin von einem linearen und binären (n, k)–Blockcode C aus. Ein wesentliches Ziel des Codedesigns ist es, die Blockfehlerwahrscheinlichkeit Pr(υ ≠ u) = Pr(z ≠ x) möglichst gering zu halten. Dies erreicht man unter anderem dadurch, dass

• die minimale Distanz d_min zwischen zwei Codeworten x und x' möglichst groß ist, so dass man bis zu t = ⌊(d_min–1)/2⌋ Bitfehler richtig korrigieren kann;
  

• gleichzeitig die minimale Distanz d_min ⇒ worst–case möglichst selten auftritt, wenn man alle zulässigen Codeworte berücksichtigt.
  
  

: Wir benennen die Anzahl der Codeworte x' ∈ C mit der Hamming–Distanz i vom betrachteten Codewort x des gleichen Codes C mit W_i(x), wobei gilt:

\[W_i(\underline{x}) = \left | \hspace{0.05cm} \left \{ \underline{x} \hspace{0.05cm}, \underline{x}{\hspace{0.03cm}' \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}|\hspace{0.1cm} d_{\rm H}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{x}' ) = i \right \} \hspace{0.05cm} \right |\hspace{0.05cm}.\]

Man bezeichnet diesen Wert auch als Vielfachheit (englisch: Multiplicity).

Die Betragsstriche kennzeichnen hierbei die Anzahl der Codeworte x', die die Bedingung { ... } erfüllen.

: Wir betrachten den (5, 2)–Blockcode C mit der Generatormatrix

\[{ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &1 &1 &0 \\ 0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.\]

Die nachfolgende Tabelle zeigt die Hamming–Distanzen zwischen allen Codeworten x mit den vier möglichen Bezugsworten x₀, ... , x₃.

Man erkennt, dass unabhängig vom Bezugswort x_i gilt:

\[W_0 = 1 \hspace{0.05cm},\hspace{0.2cm} W_1 = W_2 = 0 \hspace{0.05cm},\hspace{0.2cm}W_3 = 2 \hspace{0.05cm},\hspace{0.2cm} W_4 = 1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} d_{\rm min} = 3\hspace{0.05cm}.\]

Distanzspektrum eines linearen Codes (2)

Nicht nur im letzten Beispiel, sondern bei jedem linearen Code ergeben sich für jedes Codewort die gleichen Vielfachheiten W_i. Da zudem das Nullwort 0 = (0, 0, ..., 0) Bestandteil eines jeden linearen Binärcodes ist, lässt sich die Definition der letzten Seite auch wie folgt formulieren:

: Das Distanzspektrum eines linearen binären (n, k)–Blockcodes ist die Menge {W_i} mit i = 0, 1, ... , n. Hierbei gibt W_i die Anzahl der Codeworte x ∈ C mit Hamming–Gewicht w_H(x) = i an. Oft beschreibt man die Menge {W_i} auch als Polynom mit einer Pseudovariablen X:

\[\left \{ \hspace{0.05cm} W_i \hspace{0.05cm} \right \} \hspace{0.3cm} \Leftrightarrow \hspace{0.3cm} W(X) = \sum_{i=0 }^{n} W_i \cdot Xi^{i} = W_0 + W_1 \cdot X + W_2 \cdot X^{2} + ... \hspace{0.05cm} + W_n \cdot X^{n}\hspace{0.05cm}.\]

Man bezeichnet W(X) auch als Gewichtsfunktion (englisch: Weight Enumerator Function, WEF).

Beispielsweise lautet die Gewichtsfunktion des (5, 2)–Codes

\[\mathcal{C} = \left \{ \hspace{0.05cm}(0, 0, 0, 0, 0) \hspace{0.05cm},\hspace{0.15cm} (0, 1, 0, 1, 1) \hspace{0.05cm},\hspace{0.15cm}(1, 0, 1, 1, 0) \hspace{0.05cm},\hspace{0.15cm}(1, 1, 1, 0, 1) \hspace{0.05cm} \right \}\]

vom Beispiel auf der letzten Seite

\[W(X) = 1 + 2 \cdot X^{3} + X^{4}\hspace{0.05cm}.\]

Wie aus der Tabelle seiner Codeworte hervorgeht, erhält man für den (7, 4, 3)–Hamming–Code:

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

Die Überführung des Distanzspektrums {W_i} in die Gewichtsfunktion W(X) bietet zudem bei manchen Aufgabenstellungen große numerische Vorteile. Ist beispielsweise die Weight Enumerator Function W(X) eines (n, k)–Blockcodes bekannt, so gilt für die WEF des hierzu dualen (n, n–k)–Codes C_Dual:

\[W_{\rm Dual}(X) = \frac{(1+X)^n}{2^k} \cdot W \left ( \frac{1-X}{1+X} \right )\hspace{0.05cm}.\]

: Gesucht ist die Gewichtsfunktion W(X) des Single Parity–check Codes mit n = 6, k = 5 ⇒  SPC (6, 5). Man erhält diese durch Vergleich aller 2⁵ = 32 Codeworte mit dem Nullwort:

\[W_{\rm SPC(6,\hspace{0.08cm}5)}(X) = 1 + 15 \cdot X^{2} + 15 \cdot X^{4} + X^{6}\hspace{0.05cm}.\]

Unter Berücksichtigung obiger Gleichung kommt man sehr viel schneller zum gleichen Ergebnis:

• Der zu SPC (6, 5) duale Code ist der Repetition Code RC (6, 1) mit nur zwei Codeworten (0, 0, 0, 0, 0, 0) und (1, 1, 1, 1, 1, 1), die sich in keiner bzw. allen Bitpositionen unterscheiden:

\[W_{\rm RC(6,\hspace{0.08cm}1)}(X) = 1 + X^{6}\hspace{0.05cm}.\]

• Daraus folgt für die Gewichtsfunktion des SPC (6, 5) nach obiger Gleichung mit k = 1:

\[W_{\rm SPC(6,\hspace{0.08cm}5)}(X) \hspace{-0.15cm} = \hspace{-0.15cm} \frac{(1+X)^6}{2^1} \cdot W \left [1 + \left ( (1-X)/(1+X)\right )^6 \right ] = \]

\[\hspace{2.5cm} = \hspace{-0.15cm} 1/2 \cdot \left [( 1+X) ^6 + ( 1-X) ^6 \right ] = 1 + 15 \cdot X^{2} + 15 \cdot X^{4} + X^{6}\hspace{0.05cm}.\]

Union Bound der Blockfehlerwahrscheinlichkeit

Wir betrachten wie im Beispiel zum Distanzspektrum den (5, 2)–Blockcode C = {x₀, x₁, x₂, x₃} und setzen voraus, dass das Codewort x₀ gesendet wurde. Die Grafik verdeutlicht den Sachverhalt).

Im fehlerfreien Fall würde dann der Codewortschätzer z = x₀ liefern. Andernfalls käme es zu einem Blockfehler (das heißt z ≠ x und dementsprechend υ ≠ u) mit der Wahrscheinlichkeit

\[{\rm Pr(Blockfehler)} = {\rm Pr}\left ([\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}1}] \hspace{0.05cm}\cup\hspace{0.05cm}[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}2}] \hspace{0.05cm}\cup\hspace{0.05cm}[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}3}] \right ) \hspace{0.05cm}.\]

Das Ereignis „Verfälschung von x₀ nach x₁” tritt für ein gegebenes Empfangswort y entsprechend der ML–Entscheidungsregel genau dann ein, wenn für die bedingte Wahrscheinlichkeitsdichtefunktion gilt:

\[[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}1}] \hspace{0.3cm} \Longleftrightarrow \hspace{0.3cm} f(\underline{x}_{\hspace{0.02cm}0}\hspace{0.02cm} | \hspace{0.05cm}\underline{y}) < f(\underline{x}_{\hspace{0.02cm}1}\hspace{0.02cm} | \hspace{0.05cm}\underline{y}) \hspace{0.05cm}.\]

Da [x₀ → x₁], [x₀ → x₂], [x₀ → x₃] nicht notwendigerweise disjunkte Ereignisse sind (die sich somit gegenseitig ausschließen würden), ist die Wahrscheinlichkeit der Vereinigungsmenge kleiner oder gleich der Summe der Einzelwahrscheinlichkeiten:

\[{\rm Pr(Blockfehler)} \le {\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}1}] \hspace{0.05cm}+\hspace{0.05cm}{\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}2}] \hspace{0.05cm}+ \hspace{0.05cm}{\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}3}] \hspace{0.05cm}.\]

Man nennt diese obere Schranke für die (Block–)Fehlerwahrscheinlichkeit die Union Bound. Diese wurde bereits im Kapitel 4.3 des Buches „Digitalsignalübertragung” verwendet.

Verallgemeinern und formalisieren wir diese Ergebnisse (sowohl x als auch x' gehören zum Code C):

Blockfehlerwahrscheinlichkeit

\[{\rm Pr(Blockfehler)} = {\rm Pr} \left ( \bigcup_{\underline{x}' \ne \underline{x}} \hspace{0.15cm} [\underline{x} \mapsto \underline{x}'] \right )\hspace{0.05cm},\]

Obere Schranke nach der Union Bound:

\[{\rm Pr(Union \hspace{0.15cm}Bound)} \le \sum_{\underline{x}' \ne \underline{x}} \hspace{0.15cm} {\rm Pr}[\underline{x} \mapsto \underline{x}'] \hspace{0.05cm},\]

Paarweise Fehlerwahrscheinlichkeit (nach dem MAP– bzw. ML–Kriterium):

\[{\rm Pr}\hspace{0.02cm}[\underline{x} \mapsto \underline{x}'] = {\rm Pr} \left [ f(\underline{x}\hspace{0.05cm} | \hspace{0.05cm}\underline{y}) \le f(\underline{x}'\hspace{0.05cm} | \hspace{0.05cm}\underline{y}) \right ] \hspace{0.05cm}.\]

Auf den nächsten Seiten werden diese Ergebnisse auf verschiedene Kanäle angewendet.

Union Bound für das BSC–Modell

Wir betrachten weiterhin den beispielhaften (5, 2)–Code:

Für den digitalen Kanal verwenden wir das BSC–Modell (Binary Symmetric Channel):

\[{\rm Pr}(y = 1 \hspace{0.05cm} | \hspace{0.05cm}x = 0 ) \hspace{-0.15cm} = {\rm Pr}(y = 0 \hspace{0.05cm} | \hspace{0.05cm}x = 1 ) = {\rm Pr}(e = 1) = \varepsilon \hspace{0.05cm},\] \[{\rm Pr}(y = 0 \hspace{0.05cm} | \hspace{0.05cm}x = 0 ) \hspace{-0.15cm} = {\rm Pr}(y = 1 \hspace{0.05cm} | \hspace{0.05cm}x = 1 ) = {\rm Pr}(e = 0) = 1 -\varepsilon \hspace{0.05cm}.\]

Die beiden Codeworte x₀ = (0, 0, 0, 0, 0) und x₁ = (0, 1, 0, 1, 1) unterscheiden sich in genau d = 3 Bitpositionen, wobei d die Hamming–Distanz zwischen x₀ und x₁ angibt. Ein falsches Decodierergebnis [x₀ → x₁] erhält man immer dann, wenn mindestens zwei der drei Bit an den Bitpositionen 2, 4 und 5 verfälscht werden. Die Bitpositionen 1 und 3 spielen hier dagegen keine Rolle, da diese für x₀ und x₁ gleich sind. Da der betrachtete Code t  = ⌊(d–1)/2⌋ = 1 Fehler korrigieren kann, gilt:

\[{\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}1}] \hspace{-0.1cm} = \hspace{-0.1cm} \sum_{i=t+1 }^{d} {d \choose i} \cdot \varepsilon^{i} \cdot (1 - \varepsilon)^{d-i} = {3 \choose 2} \cdot \varepsilon^{2} \cdot (1 - \varepsilon) + {3 \choose 3} \cdot \varepsilon^{3} =\] \[\hspace{2.5cm} = \hspace{-0.1cm} 3 \cdot \varepsilon^2 \cdot (1 - \varepsilon) + \varepsilon^3 = {\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}2}]\hspace{0.05cm}.\]

Die Codeworte x₀ und x₃ unterscheiden sich in vier Bitpositionen. Zu einer falschen Decodierung des Blocks kommt es deshalb mit Sicherheit, wenn vier oder drei Bit verfälscht werden. Eine Verfälschung von zwei Bit hat mit 50–prozentiger Wahrscheinlichkeit ebenfalls einen Blockfehler zur Folge, wenn man hierfür eine Zufallsentscheidung voraussetzt:

\[{\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}3}] = \varepsilon^4 + 4 \cdot \varepsilon^3 \cdot (1 - \varepsilon) + {1}/{2} \cdot 6 \cdot \varepsilon^2 \cdot (1 - \varepsilon)^2 \hspace{0.05cm}.\]

Daraus ergibt sich für die „Union Bound”:

\[{\rm Pr(Union \hspace{0.15cm}Bound)} = {\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}1}] +{\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \hspace{-0.02cm}\mapsto \hspace{-0.02cm} \underline{x}_{\hspace{0.02cm}2}] +{\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \hspace{-0.02cm}\mapsto \hspace{-0.02cm} \underline{x}_{\hspace{0.02cm}3}] \ge {\rm Pr(Blockfehler)} .\]

In der Tabelle sind die Ergebnisse für verschiedene Werte des BSC–Parameters ε zusammengefasst:

Zu erwähnen ist, dass die völlig unterschiedlich zu berechnenden Wahrscheinlichkeiten Pr(x₀ → x₁) und Pr(x₀ → x₃) genau das gleiche Ergebnis liefern.

Die obere Schranke nach Bhattacharyya (1)

Eine weitere obere Schranke für die Blockfehlerwahrscheinlichkeit wurde von Bhattacharyya angegeben:

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

Hierzu ist anzumerken:

• W(X) ist die zu Beginn dieses Kapitels 1.6 definierte Gewichtsfunktion, die den verwendeten Kanalcode charakterisiert.
  

• Der Bhattacharyya–Parameter β kennzeichnet den digitalen Kanal. Beispielsweise gilt:

\[\beta = \left\{ \begin{array}{c} \lambda \\ \sqrt{4 \cdot \varepsilon \cdot (1- \varepsilon)}\\ {\rm exp}[- R \cdot E_{\rm B}/N_0] \end{array} \right.\quad \begin{array}{*{1}c} {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BEC-Modell},\\ {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BSC-Modell}, \\ {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}AWGN-Modell}. \end{array}\]

• Die Bhattacharyya–Schranke liegt stets (und meist deutlich) oberhalb der Kurve für die „Union Bound”. Mit dem Ziel, eine für alle Kanäle einheitliche Schranke zu finden, müssen hier sehr viel gröbere Abschätzungen vorgenommen werden als für die Herleitung der Union Bound.
  
  

Bhattacharyya–Schranke für das BSC–Modell

Für die paarweise Verfälschungswahrscheinlichkeit des BSC–Modells wurde vorne hergeleitet:

\[{\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}1}] = \sum_{i= \left\lfloor (d-1)/2 \right\rfloor}^{d} {d \choose i} \cdot \varepsilon^{i} \cdot (1 - \varepsilon)^{d-i} = \sum_{i= \left\lceil d/2 \right\rceil }^{d} {d \choose i} \cdot \varepsilon^{i} \cdot (1 - \varepsilon)^{d-i}\hspace{0.05cm}.\]

Hierbei kennzeichnet ε = Pr(y = 1| x = 0) = Pr(y = 0| x = 1) < 0.5 das BSC–Modell und d = d_H(x₀, x₁) gibt die Hamming–Distanz der betrachteten Codeworte an.

Um zur Bhattacharyya–Schranke zu kommen, müssen folgende Abschätzungen getroffen werden:

• Für alle i < d gilt εⁱ · (1 – ε)^{d – i} ≤ [ε · (1 – ε)]^d/2:

\[{\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}1}] \le [\varepsilon \cdot (1 - \varepsilon)]^{d/2} \cdot \sum_{i= \left\lceil d/2 \right\rceil }^{d} {d \choose i} \hspace{0.05cm}.\]

• Änderung bezüglich der unteren Grenze der Laufvariablen i:

\[\sum_{i= \left\lceil d/2 \right\rceil }^{d} {d \choose i} \hspace{0.15cm} < \hspace{0.15cm} \sum_{i= 0 }^{d} {d \choose i} = 2^d\hspace{0.05cm}, \hspace{0.2cm}\beta = 2 \cdot \sqrt{\varepsilon \cdot (1 - \varepsilon)} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}1}] = \beta^{d} \hspace{0.05cm}.\]

• Umsortierung gemäß den Hamming–Gewichten W_i (Hamming–Distanz d = i kommt W_i mal vor):

\[{\rm Pr(Blockfehler)} \hspace{0.1cm} \le \hspace{0.1cm} \sum_{i= 1 }^{n} W_i \cdot \beta^{i} = 1 + W_1 \cdot \beta + W_2 \cdot \beta^2 + ... \hspace{0.05cm}+ W_n \cdot \beta^n \hspace{0.05cm}.\]

• Mit der Gewichtsfunktion W(X) = 1 + W₁ · X + W₂ · X ² + ... + W_n · X ⁿ:

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

Die obere Schranke nach Bhattacharyya (2)

In der Tabelle ist die Bhattacharyya–Schranke für verschiedene BSC–Parameter ε abgegeben, gültig für den beispielhaften (5, 2)–Code. Für diesen gilt:

\[W_0 = 1 \hspace{0.05cm},\hspace{0.2cm} W_1 = W_2 = 0 \hspace{0.05cm},\hspace{0.2cm}W_3 = 2 \hspace{0.05cm},\hspace{0.2cm} W_4 = 1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} W(X) = 1 + 2 \cdot X^3 + X^4\]

\[\Rightarrow \hspace{0.3cm} {\rm Pr(Blockfehler)} \le W(\beta) -1 = 2 \cdot \beta^3 + \beta^4 = {\rm Pr(Bhattacharyya)} \hspace{0.05cm}.\]

Basierend auf diesem Beispiel für den einfachen (5, 2)–Code, der allerdings wenig praxisrelevant ist, sowie dem Beispiel auf der nächsten Seite für den (7, 4, 3)–Hamming–Code kann man zusammenfassen:

• Die Blockfehlerwahrscheinlichkeit eines Codiersystems ist oft analytisch nicht angebbar und muss per Simulation ermittelt werden. Gleiches gilt für die Bitfehlerwahrscheinlichkeit.
  

• Die Union Bound liefert eine obere Schranke für die Blockfehlerwahrscheinlichkeit. Bei vielen Anwendungen (insbesondere bei kurzen Codes) liegt sie nur geringfügig über dieser.
  

• Die Bhattacharyya–Schranke liegt beim BEC–Kanal etwa um den Faktor 2 oberhalb der Union Bound – siehe Aufgabe A1.14. Beim BSC– und beim AWGN–Kanal ist der Abstand zwischen beiden Schranken deutlich größer. Der Faktor 10 (oder mehr) ist keine Seltenheit.
  

• Die Bhattacharyya–Schranke W(β) – 1 wirkt auf den ersten Blick sehr einfach. Es sind einige Vereinfachungsschritte erforderlich, um auf diese Form zu kommen. Trotzdem benötigt man auch hier Kenntnis über die genaue Gewichtsfunktion W(ξ) des Codes.
  

• Bei Kenntnis des Übertragungskanals (BEC, BSC, AWGN oder Abwandlungen hiervon) und dessen Parameter spricht vom Aufwand her nichts dagegen, die Union Bound als obere Schranke für die Blockfehlerwahrscheinlichkeit zu verwenden.