Bounds for Block Error Probability

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}.\]