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:

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

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:

\[\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},\]

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

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

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.

Codefestlegung durch die Prüfmatrix

Wir betrachten den (7, 4, 3)–Hamming–Code mit Codeworten x der Länge n = 7, nämlich

den k = 4 Informationsbits x₁, x₂, x₃, x₄ , und

den m = 3 Prüfbits x₅, x₆, x₇.

Die Paritätsgleichungen lauten somit:

\[x_1 + x_2 + x_3 + x_5 \hspace{-0.1cm} = \hspace{-0.1cm} 0 \hspace{0.05cm},\] \[x_2 + x_3 + x_4 + x_6 \hspace{-0.1cm} = \hspace{-0.1cm} 0 \hspace{0.05cm},\] \[x_1 + x_2 + x_4 + x_7 \hspace{-0.1cm} = \hspace{-0.1cm} 0 \hspace{0.05cm}. \]

In der Matrixschreibweise lautet dieser Gleichungssatz:

\[{ \boldsymbol{\rm H}} \cdot \underline{x}^{\rm T}= \underline{0}^{\rm T} \hspace{0.05cm}. \]

In dieser Gleichung werden verwendet:

die Prüfmatrix H mit m = n – k = 3 Zeilen und n = 7 Spalten:

\[{ \boldsymbol{\rm H}} = \begin{pmatrix} 1 &1 &1 &0 &1 & 0 & 0\\ 0 &1 &1 &1 &0 & 1 & 0\\ 1 &1 &0 &1 &0 & 0 & 1 \end{pmatrix}\hspace{0.05cm},\]

das Codewort x = (x₁, x₂, ... , x₇) der Länge n = 7,

das Nullvektor 0 = (0, 0, 0) der Länge m = 3.

Durch Transponieren werden aus x und 0 die entsprechenden Spaltenvektoren x^T und 0^T.

:

Die Grafik illustriert die m = 3 Paritätsgleichungen eines Codes C mit den Codeparametern n = 6 und k = 3 in der Reihenfolge rot, grün und blau. Entsprechend H · x^T = 0^T lautet die Prüfmatrix:

\[{ \boldsymbol{\rm H}} = \begin{pmatrix} 1 &1 &0 &1 &0 & 0\\ 1 &0 &1 &0 &1 & 0\\ 0 &1 &1 &0 &0 & 1 \end{pmatrix}\hspace{0.05cm}.\]

Die 2^k = 8 Worte einer systematischen Realisierung dieses Codes lauten (mit den Prüfbits rechts vom kleinen Pfeil):

\[\underline{x}_0 \hspace{-0.1cm} = \hspace{-0.1cm} (0, 0, 0_{\hspace{0.01cm} \rightarrow} 0, 0, 0)\hspace{0.05cm}, \hspace{0.2cm} \underline{x}_1 = (0, 0, 1_{\hspace{0.01cm} \rightarrow}0, 1, 1)\hspace{0.05cm},\hspace{0.2cm} \underline{x}_2 = (0, 1, 0_{\hspace{0.01cm} \rightarrow}1, 0, 1)\hspace{0.05cm},\] \[\underline{x}_3 \hspace{-0.1cm} = \hspace{-0.1cm} (0, 1, 1_{\hspace{0.01cm} \rightarrow}1, 1, 0)\hspace{0.05cm},\hspace{0.2cm} \underline{x}_4 = (1, 0, 0_{\hspace{0.01cm} \rightarrow} 1, 1, 0)\hspace{0.05cm}, \hspace{0.2cm} \underline{x}_5 = (1, 0, 1_{\hspace{0.01cm} \rightarrow}1, 0, 1)\hspace{0.05cm},\] \[\underline{x}_6 \hspace{-0.1cm} = \hspace{-0.1cm} (1, 1, 0_{\hspace{0.01cm} \rightarrow}0, 1, 1)\hspace{0.05cm}, \hspace{0.2cm} \underline{x}_7 = (1, 1, 1_{\hspace{0.01cm} \rightarrow}0, 0, 0)\hspace{0.05cm}.\]

Man erkennt aus diesen Angaben:

Die Anzahl der Spalten von H ist gleich der Codelänge n.

Die Anzahl der Zeilen von H ist gleich der Anzahl m = n – k der Prüfgleichungen.

Aus H · x^T = 0 folgt nicht, dass alle Codeworte eine gerade Anzahl von Einsen beinhalten.