General Description of Linear Block Codes

Lineare Codes und zyklische Codes

Alle bisher behandelten Codes – Single Parity–check Code, Repetition Code und Hamming–Code – sind linear. Nun wird die für binäre Blockcodes gültige Definition von Linearität nachgereicht.

: Ein linearer Blockcode C ist ein Satz von 2^k Codeworten x = (x₁, x₂, ... , x_n), wobei die (Modulo–2)–Summe zweier beliebiger Codeworte x und x' wiederum ein gültiges Codewort ergibt:

[math]\displaystyle{ \underline{x}, \underline{x}\hspace{0.05cm}' \in {\rm GF}(2^n),\hspace{0.3cm} \underline{x}, \underline{x}\hspace{0.05cm}' \in \mathcal{C} \hspace{0.3cm} \Rightarrow \hspace{0.3cm}\underline{x} + \underline{x}\hspace{0.05cm}' \in \mathcal{C} \hspace{0.05cm}. }[/math]

Diese Bedingung muss auch für x = x' erfüllt sein.

Hinweis: Die Modulo–Addition wird nun nicht mehr durch das Modulo–Additionszeichen ausgedrückt, sondern mit dem herkömmlichen Pluszeichen. Diese Vereinfachung der Schreibweise wird für den Rest dieses Buches beibehalten.

: Wir betrachten zwei (3, 2)–Blockcodes:

[math]\displaystyle{ \mathcal{C}_1 = \{ (0, 0, 0) \hspace{0.05cm}, (0, 1, 1) \hspace{0.05cm},(1, 0, 1) \hspace{0.05cm},(1, 1, 0) \}\hspace{0.05cm}, }[/math]

[math]\displaystyle{ \mathcal{C}_2 = \{ (0, 0, 0) \hspace{0.05cm}, (0, 1, 1) \hspace{0.05cm},(1, 1, 0) \hspace{0.05cm},(1, 1, 1) \hspace{0.05cm}. }[/math]

Man erkennt:

Der Code C₁ ist linear, da die Modulo–2–Addition zweier beliebiger Codeworte stets auch ein gültiges Codewort ergibt, zum Beispiel (0, 1, 1) + (1, 0, 1) = (1, 1, 0).

Die obige Definition gilt auch für die Modulo–2–Addition eines Codewortes mit sich selbst, zum Beispiel (0, 1, 1) + (0, 1, 1) = (0, 0, 0) ⇒ Jeder lineare Code beinhaltet das Nullwort.

Obwohl die letzte Voraussetzung erfüllt wird, ist C₂ kein linearer Code. Für diesen Code gilt nämlich beispielsweise: (0, 1, 1) + (1, 1, 0) = (1, 0, 1). Dies ist kein gültiges Codewort von C₂.

Im Folgenden beschränken wir uns ausschließlich auf lineare Codes, da nichtlineare Codes für die Praxis von untergeordneter Bedeutung sind.

: Ein linearer Blockcode C heißt zyklisch, wenn eine jede zyklische Verschiebung eines Codewortes x (nach links oder rechts) wieder ein gültiges Codewort ergibt:

[math]\displaystyle{ \underline{x}= (x_1, x_2, ... \hspace{0.05cm}, x_n) \in \mathcal{C} \hspace{0.3cm} \Rightarrow \hspace{0.3cm}\underline{x}\hspace{0.05cm}'= (x_n, x_1, ... \hspace{0.05cm}, x_{n-1}) \in \mathcal{C} \hspace{0.05cm}. }[/math]

Man erkennt aus der Tabelle für den HC (7, 4, 3), dass dieser linear und zyklisch ist (schwarz: 4 Informationsbit, rot: n – k = 3 Prüfbit).

Außerdem ergibt sich auch dann ein gültiges Codewort, wenn man alle Bit invertiert: 0 ↔ 1. Auch das 0–Wort (n mal eine „0”) und das 1–Wort (n mal eine „1”) sind bei diesem Code zulässig.