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