Beispiele binärer Blockcodes

Aus LNTwww
Wechseln zu:Navigation, Suche

Single Parity–check Codes (1)


Der Single Parity–check Code (SPC) fügt zu dem Informationsblock u = (u1, u2, ... , uk) 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).

Single Parity–check Code (n = k + 1)

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 x1x2 = x3.
  • 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 dmin = 2.

Mit der allgemeinen Codebezeichnung (n, k, dmin) 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}.\]