Examples of Binary Block Codes

Single Parity–check Codes (1)

Der Single Parity–check Code (SPC) fügt zu dem Informationsblock u = (u₁, u₂, ... , u_k) ein Prüfbit (englisch: Parity) p hinzu:

\[\underline{u} = (u_1, u_2,\hspace{0.05cm} ... \hspace{0.05cm} , u_k) \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{x} = (x_1, x_2,\hspace{0.05cm} ... \hspace{0.05cm} , x_n) = (u_1, u_2,\hspace{0.05cm} ... \hspace{0.05cm} , u_k, p) \hspace{0.05cm}.\]

Die Grafik zeigt drei Beispiele solcher Codes mit |C| = 4 (k = 2), |C| = 8 (k = 3) und |C| = 16 (k = 4).

Dieser sehr einfache Code ist wie folgt charakterisiert:

Aus n = k + 1 folgt für die Coderate R = k/n = (n – 1)/n und für die Redundanz 1 – R = 1/n. Für k = 2 ergibt sich zum Beispiel die Coderate 2/3 und die relative Redundanz beträgt 33.3%.

Das Prüfbit erhält man durch die Modulo–2–Addition. Darunter versteht man die Addition im Galoisfeld zur Basis 2 ⇒ GF(2), sodass 1⊕1 = 0 ergibt:

\[p = u_1 \oplus u_2 \oplus ... \hspace{0.05cm} \oplus u_k \hspace{0.05cm}.\]

Damit enthält jedes gültige Codewort x eine gerade Anzahl von Einsen. Ausgedrückt mit ⊕ bzw. in vereinfachter Schreibweise entsprechend der zweiten Gleichung lautet diese Bedingung:

\[ x_1 \oplus x_2 \oplus ... \hspace{0.05cm} \oplus x_n = 0 \hspace{0.05cm}, \hspace{0.5cm}{\rm oder:}\hspace{0.15cm} \sum_{i=1}^{n} \hspace{0.2cm} x_i = 0\hspace{0.05cm} , \hspace{0.3cm} {\rm Addition\hspace{0.15cm} in \hspace{0.15cm} GF(2)} \hspace{0.05cm}. \]

Für k = 2 ⇒ n = 3 ergeben sich die folgenden vier Codeworte, wobei in der ersten Zeile das Prüfbit jeweils durch einen kleinen Pfeil markiert ist:

\[\underline{x}_0 = (0, 0_{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 0)\hspace{0.05cm}, \hspace{0.2cm} \underline{x}_1 = (0, 1_{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 1)\hspace{0.05cm}, \hspace{0.2cm} \underline{x}_2 = (1, 0 _{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 1)\hspace{0.05cm}, \hspace{0.2cm} \underline{x}_3 = (1, 1 _{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 0)\]

Es handelt sich um einen linearen Code, da die Summe zweier beliebiger Codeworte wieder ein gültiges Codewort ergibt, zum Beispiel x₁ ⊕ x₂ = x₃.

Für beliebiges k ⇒ n = k + 1 unterscheidet sich jedes Codewort von allen anderen an einer geraden Anzahl von Positionen. Bei diesem Code ist die minimale Distanz d_min = 2.

Mit der allgemeinen Codebezeichnung (n, k, d_min) lässt sich jeder Single Parity–check Code auch mit (n, n – 1, 2) benennen. Die Grafik zeigt den SPC (3, 2, 2), den SPC (4, 3, 2) und den SPC (5, 4, 2).

: Jeder Single Parity–check Code (SPC) lässt sich formal wie folgt beschreiben: \[\mathcal{C} = \{ \underline{x} \in {\rm GF}(2^n)\hspace{-0.15cm}: \hspace{0.15cm}{\rm mit \hspace{0.15cm}geradzahliger\hspace{0.15cm} Anzahl\hspace{0.15cm} von\hspace{0.15cm} Einsen\hspace{0.15cm} in \hspace{0.15cm}} \underline{x} \}\hspace{0.05cm}.\]

Single Parity–check Codes (2)

Der digitale Kanal ändert möglicherweise das Codewort x = (x₁, x₂, ... , x_n) in das Empfangswort y = (y₁, y₂, ... , y_n), wobei mit dem Fehlervektor e = (e₁, e₂, ... , e_n) gilt: y = x ⊕ e. Zur Decodierung des Single Parity–check Codes bildet man das sogenannte Syndrom:

\[s = y_1 \oplus y_2 \oplus ... \hspace{0.05cm} \oplus y_n = \sum_{i=1}^{n} \hspace{0.2cm} y_i \hspace{0.1cm} \in \hspace{0.2cm} \{0, 1 \} \hspace{0.05cm}.\]

Das Ergebnis „s = 1” weist dann auf (mindestens) einen Bitfehler innerhalb des Codewortes hin, während „s = 0” wie folgt zu interpretieren ist:

Die Übertragung war fehlerfrei, oder:

Die Anzahl der Bitfehler ist geradzahlig.

: Wir betrachten den SPC (4, 3, 2) und gehen davon aus, dass das Nullwort gesendet wurde. Die Tabelle zeigt alle Möglichkeiten, dass f Bit verfälscht werden und gibt das jeweilige Syndrom s (entweder 0 oder 1) an.

Für das BSC–Modell mit ε = 1% ergeben sich dann folgende Wahrscheinlichkeiten:

Das Informationswort wird richtig decodiert (blaue Hinterlegung):

\[{\rm Pr}(\underline{v} = \underline{u}) = {\rm Pr}(\underline{y} = \underline{x}) = (1 - \varepsilon)^n = 0.99^4 \approx 96\,\%\hspace{0.05cm}.\]

Der Decoder erkennt, dass Übertragungsfehler aufgetreten sind (grüne Hinterlegung):

\[{\rm Pr}(s=1) \hspace{-0.1cm} = \hspace{-0.1cm} \sum_{f=1 \atop f \hspace{0.1cm}{\rm ungerade} }^{n} {n \choose f} \cdot \varepsilon^{f} \cdot (1 - \varepsilon)^{n-f} = \]

\[\hspace{1.8cm} = \hspace{-0.1cm} {4 \choose 1} \cdot 0.01 \cdot 0.99^3 + {4 \choose 3} \cdot 0.01^3 \cdot 0.99 \approx 3.9\,\%\hspace{0.05cm}.\]

Das Informationswort wird falsch decodiert (rote Hinterlegung):

\[{\rm Pr}(\underline{v} \ne \underline{u}) \hspace{-0.1cm} = \hspace{-0.1cm} \sum_{f=2 \atop f \hspace{0.1cm}{\rm gerade} }^{n} {n \choose f} \cdot \varepsilon^{f} \cdot (1 - \varepsilon)^{n-f} = \]

\[\hspace{2cm} = \hspace{-0.1cm} 1 - {\rm Pr}(\underline{v} = \underline{u}) - {\rm Pr}(s=1)\approx 0.1\,\%\hspace{0.05cm}.\]

Wir verweisen hier auf das Modul Ereigniswahrscheinlichkeiten der Binomialverteilung. Please add link and do not upload flash videos.

In der Aufgabe A1.5 werden die hier gewonnenen Ergebnisse noch ausführlich diskutiert.