Channel Coding/General Description of Linear Block Codes

1. Channel Coding
2. Binäre Blockcodes zur Kanalcodierung
3. General Description of Linear Block Codes

• Previous page
• Next page

• Previous page
• Next page

Lineare Codes und zyklische Codes

Alle bisher behandelten Codes

• Single Parity–check Code,
• Repetition Code,
• Hamming–Code

sind linear. Nun wird die für binäre Blockcodes gültige Definition von Linearität nachgereicht.

$\text{Definition:}$  Ein linearer binärer Blockcode $\mathcal{C}$ ist ein Satz von $2^k$ Codeworten $\underline{x}= (x_1, x_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, x_n)$, wobei die (Modulo–2)–Summe zweier beliebiger Codeworte $\underline{x}$ und $\underline{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 $\underline{x} = \underline{x}'$ erfüllt sein.

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

$\text{Beispiel 1:}$  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 $\mathcal{C}_1$ 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 $\underline{0}$.
  

• Obwohl die letzte Voraussetzung erfüllt wird, ist $\mathcal{C}_2$ 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 $\mathcal{C}_2$.

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

$\text{Definition:}$  Ein linearer Blockcode $\mathcal{C}$ heißt zyklisch, wenn eine jede zyklische Verschiebung eines Codewortes $\underline{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}.\]

Codetabelle des systematischen (7, 4, 3)–Hamming–Codes
schwarz: $k= 4$ Informationsbits, rot: $n-k = 3$ Prüfbits

$\text{Beispiel 2:}$ 

• Man erkennt aus der Tabelle für den (7, 4, 3)–Hamming–Code , dass dieser linear und zyklisch ist.
• Es ergibt sich auch dann ein gültiges Codewort, wenn man alle Bit invertiert: $0 ↔ 1$.
• Auch das $\underline{0}$–Wort ($n$ mal eine „Null”) und das $\underline{1}$–Wort ($n$ mal eine „Eins”) sind bei diesem Code zulässig.

Codefestlegung durch die Prüfmatrix

(7, 4, 3)–Hamming–Code

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

• den $k = 4$ Informationsbits $x_1$>, $x_2$, $x_3$, $x_4$ , und
  
• den $m = 3$ Prüfbits $x_5$, $x_6$, $x_7$.
  
  

Die Paritätsgleichungen lauten somit:

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

In 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 ${ \boldsymbol{\rm 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 $\underline{x}= (x_1, x_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, x_7)$ der Länge $n = 7$,
  

• das Nullvektor $\underline{0} = (0, 0, 0)$ der Länge $m = 3$.
  
  

Durch Transponieren werden aus den Zeilenvektoren $\underline{x}$ und $\underline{0}$ die entsprechenden Spaltenvektoren $\underline{x}^{\rm T}$ und $\underline{0}^{\rm T}$.

:

(6, 3, 3)–Blockcode

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.

Codefestlegung durch die Generatormatrix

Die Prüfmatrix H eines (n, k)–Blockcodes C hat m = n – k Zeilen und n Spalten. Den gleichen Code kann man aber auch durch die Generatormatrix G mit ebenfalls n Spalten, aber k Zeilen beschreiben:

: Ein linearer Blockcode C kann durch die Prüfmatrix H bzw. mit der Generatormatrix G wie folgt charakterisiert werden:

\[\mathcal{C} \hspace{-0.1cm} = \hspace{-0.1cm} \{ \underline{x} \in {\rm GF}(2^n): \hspace{0.2cm}{ \boldsymbol{\rm H}} \cdot \underline{x}^{\rm T}= \underline{0}^{\rm T} \}\hspace{0.05cm},\]

\[\mathcal{C} \hspace{-0.1cm} = \hspace{-0.1cm} \{ \underline{x} \in {\rm GF}(2^n)\hspace{0.05cm}, \hspace{0.1cm}\underline{u} \in {\rm GF}(2^k) : \hspace{0.2cm}\underline{x} = \underline{u} \cdot { \boldsymbol{\rm G}} \}\hspace{0.05cm}.\]

Bevor wir uns den Eigenschaften der Generatormatrix zuwenden, beschreiben wir an einem Beispiel die Erzeugung der Codeworte.

: Wir betrachten einen linearen (5, 3)–Blockcode mit der Generatormatrix

\[{ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &1 &0 &1 &1\\ 0 &1 &0 &1 &0\\ 0 &1 &1 &1 &0 \end{pmatrix} = \begin{pmatrix} \underline{g}_1\\ \underline{g}_2\\ \underline{g}_3\\ \end{pmatrix} \hspace{0.05cm}.\]

Damit werden die Informationsworte u = (u₁, u₂, u₃) den Codeworten x = (x₁, x₂, x₃, x₄, x₅) gemäß der folgenden Tabelle mit 8 Einträgen zugeordnet. Es gilt x = u · G.

\[\underline{u}_0 \hspace{-0.15cm} = \hspace{-0.15cm} (0, 0, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_0 = (0, 0, 0, 0, 0) \hspace{0.05cm},\] \[\underline{u}_1 \hspace{-0.15cm} = \hspace{-0.15cm} (0, 0, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_1 = (0, 1, 1, 1, 0) \hspace{0.1cm}= \hspace{0.1cm}\underline{g}_3\hspace{0.05cm},\] \[\underline{u}_2 \hspace{-0.15cm} = \hspace{-0.15cm} (0, 1, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_2 = (0, 1, 0, 1, 0)\hspace{0.1cm}= \hspace{0.1cm} \underline{g}_2\hspace{0.05cm},\] \[\underline{u}_3 \hspace{-0.15cm} = \hspace{-0.15cm} (0, 1, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_3 = (0, 0, 1, 0, 0) \hspace{0.1cm}= \hspace{0.1cm} \underline{g}_2+\underline{g}_3\hspace{0.05cm},\] \[\underline{u}_4 \hspace{-0.15cm} = \hspace{-0.15cm} (1, 0, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_4 = (1, 1, 0, 1, 1)\hspace{0.1cm}= \hspace{0.1cm} \underline{g}_1 \hspace{0.05cm},\] \[\underline{u}_5 \hspace{-0.15cm} = \hspace{-0.15cm}(1, 0, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_5 = (1, 0, 1, 0, 1)\hspace{0.1cm}= \hspace{0.1cm} \underline{g}_1+\underline{g}_3\hspace{0.05cm},\] \[\underline{u}_6 \hspace{-0.15cm} = \hspace{-0.15cm} (1, 1, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_6 = (1, 0, 0, 0, 1)\hspace{0.1cm}= \hspace{0.1cm} \underline{g}_1+\underline{g}_2\hspace{0.05cm},\]

\[\underline{u}_7 \hspace{-0.15cm} = \hspace{-0.15cm} (1, 1, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_7 = (1, 1, 1, 1, 1) \hspace{0.1cm}= \hspace{0.1cm} \underline{g}_1+ \underline{g}_2+\underline{g}_3\hspace{0.05cm}.\]

Die hier zur Berechnung herangezogenen Basisvektoren g₁, g₂, g₃ – jeweils mit der Länge n = 5 – entsprechen den k = 3 Zeilen der Generatormatrix G. Anzumerken ist ferner, dass dieser Code wegen d_min = 1 weder zur Fehlerkorrektur noch zur Fehlererkennung geeignet ist. Trotzdem wird er auch auf den nächsten Seiten beispielhaft weiter betrachtet.

Hinweis: An dieser Stelle möchten wir Sie auf ein Interaktionsmodul zum Buch „Digitalsignalübertragung” aufmerksam machen, das die Bedeutung und Berechnung von Basisfunktionen vermittelt, wenn auch in völlig anderem Zusammenhang als in diesem Buch:

Gram–Schmidt–Verfahren Please add link and do not upload flash files.

Systematische Codes (1)

Die im Beispiel auf der letzten Seite verwendeten Vektoren g₁, g₂, ... , g_k sind die Basisvektoren des linearen Blockcodes C. Der Code selbst kann als k–dimensionaler Untervektorraum von GF(2ⁿ) angesehen werden. Die Basisvektoren g₁, g₂, ... , g_k sind linear unabhängig.

Der Untervektorraum C wird aber nicht nur durch die Basisvektoren

\[\underline{g}_1 = (1, 1, 0, 1, 1) \hspace{0.05cm},\hspace{0.3cm} \underline{g}_2 = (0, 1, 0, 1, 0) \hspace{0.05cm},\hspace{0.3cm} \underline{g}_3 = (0, 1, 1, 1, 0) \hspace{0.05cm}\]

aufgespannt, sondern andere Basisvektoren g'₁, g'₂ und g'₃ sind ebenso geeignet, so lange zwischen diesen die lineare Unabhängigkeit gewährleistet ist.

: Wir vergleichen die beiden Codes C und C ' mit den Generatormatrizen

\[{ \boldsymbol{\rm G}} = \begin{pmatrix} \underline{g}_1\\ \underline{g}_2\\ \underline{g}_3\\ \end{pmatrix}= \begin{pmatrix} 1 &1 &0 &1 &1\\ 0 &1 &0 &1 &0\\ 0 &1 &1 &1 &0 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm G}\hspace{0.05cm}'} = \begin{pmatrix} \underline{g}\hspace{0.05cm}'_1\\ \underline{g}\hspace{0.05cm}'_2\\ \underline{g}\hspace{0.05cm}'_3\\ \end{pmatrix}= \begin{pmatrix} 1 &0 &0 &0 &1\\ 0 &1 &0 &1 &0\\ 0 &0 &1 &0 &0 \end{pmatrix}\hspace{0.05cm}.\]

Die beiden Codes sind identisch: Sie beinhalten die genau gleichen Codeworte; es gilt nur eine andere Zuordnung. Bei dem Übergang von G auf G' wurden folgende erlaubte Operationen ausgeführt:

\[\underline{g}\hspace{0.05cm}'_1 = \underline{g}_1 + \underline{g}_2 \hspace{0.05cm},\hspace{0.3cm} \underline{g}\hspace{0.05cm}'_2 = \underline{g}_2 \hspace{0.05cm},\hspace{0.3cm} \underline{g}\hspace{0.05cm}'_3 = \underline{g}_2 + \underline{g}_3 \hspace{0.05cm}.\]

Zum entsprechenden Code C ' kommt man mit der Gleichung x ' = u · G.

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

Die Codeworte x_i; beziehen sich auf die Generatormatrix G. Sie finden diese auf der letzten Seite.

Diese Codetabelle macht nochmals deutlich:

• C und C ' beinhalten die genau gleichen Codeworte. Sie sind damit identische Codes und besitzen beide die gleiche Korrekturfähigkeit (siehe nächste Seite).
  

• C ' ist aber nun ein systematischer Code, da die ersten k Binärstellen eines jeden Codewortes x' mit den Binärstellen des Informationswortes u übereinstimmen.
  

Systematische Codes (2)

Die Eigenschaft „systematisch” soll nun noch in mathematischer Form angegeben werden.

: Bei einem systematischen (n, k)–Blockcode C_sys beinhaltet jedes Codewort x explizit das Informationswort u, das heißt es gilt

\[\underline{u} = (u_1, u_2, ... \hspace{0.05cm}, u_k) \hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm} = (u_1, u_2, ... \hspace{0.05cm}, u_k, x_{k+1}, ... \hspace{0.05cm}, x_n)\hspace{0.05cm},\]

und die Generatormatrix hat die spezifische Form

\[{ \boldsymbol{\rm G_{sys}}} =\left({ \boldsymbol{\rm I}}_k \: ; \: { \boldsymbol{\rm P}}\right)\]

mit der k×k–Einheitsmatrix I_k und einer geeignet zu wählenden (n – k)×k–Matrix P.

Für das Beispiel auf der letzten Seite kann also auch geschrieben werden:

\[{ \boldsymbol{\rm G_{sys}}} =\left({ \boldsymbol{\rm I}}_3 \: ; \: { \boldsymbol{\rm P}}\right)\hspace{0.3cm}{\rm mit}\hspace{0.3cm} { \boldsymbol{\rm I_{3}}} = \begin{pmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &0 &1 \end{pmatrix}\hspace{0.3cm}{\rm und}\hspace{0.3cm} { \boldsymbol{\rm P}} = \begin{pmatrix} 0 &1 \\ 1 &0 \\ 0 &0 \end{pmatrix}\hspace{0.05cm}.\]

Erfreulich aus Sicht der Kanalcodierung ist, dass für jeden Code C ein systematischer (identischer oder zumindest äquivalenter) Code C_sys gefunden werden kann.

Zum identischen Code (das heißt x und x_sys haben die gleichen Codeworte, nur die Zuordnung u → x ist unterschiedlich) kommt man durch folgende Manipulationen bezüglich G:

• Vertauschen oder Permutieren der Zeilen,
  

• Multiplizieren aller Zeilen mit einem konstanten Vektor ungleich 0,
  

• Ersetzen einer Zeile durch eine Linearkombination zwischen dieser Zeile und einer anderen.
  
  

Ein identischer systematischer Code kann immer dann gefunden werden, wenn zu einer Generatormatrix G eine Matrix A existiert, so dass G_sys = A · G gilt. Ist dies nicht möglich, so findet man zumindest durch Vertauschen oder Permutieren der Spalten von G einen äquivalenten systematischen Code:

\[\mathcal{C}_{\rm sys} = {\rm \pi} (\mathcal{C})\hspace{0.3cm}{\rm mit}\hspace{0.3cm}{\rm \pi}():\hspace{0.15cm}{\rm Permutationsoperator}\hspace{0.05cm}.\]

Die Codes C und C_sys beinhalten dann zwar andere Codeworte, aber sie zeigen gleiche Eigenschaften. Beispielsweise weist C_sys die gleiche minimale Hamming–Distanz d_min auf wie der Code C.

: Wir betrachten die Generatormatrizen

\[{ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &1 &0 &0 \\ 0 &0 &1 &1 \end{pmatrix}\hspace{0.3cm}{\rm und}\hspace{0.3cm} { \boldsymbol{\rm G_{sys}}} = \begin{pmatrix} 1 &0 &1 &0 \\ 0 &1 &0 &1 \end{pmatrix}\hspace{0.05cm}.\]

G_sys ergibt sich aus G durch Vertauschen der zweiten und dritten Spalte. Die zugehörigen Codes beinhalten unterschiedliche Codeworte und sind somit auch nicht identisch. Aber sie sind äquivalent: Es handelt sich in beiden Fällen um einen (4, 2, 2)–Blockcode   ⇒   d_min = 2:

\[\mathcal{C} \hspace{-0.15cm} = \hspace{-0.15cm} \{ (0, 0, 0, 0) \hspace{0.05cm}, (0, 0, 1, 1) \hspace{0.05cm},(1, 1, 0, 0) \hspace{0.05cm},(1, 1, 1, 1) \}\hspace{0.05cm},\]

\[cal{C}_{\rm sys} \hspace{-0.15cm} = \hspace{-0.15cm} \{ (0, 0, 0, 0) \hspace{0.05cm}, (0, 1, 0, 1) \hspace{0.05cm},(1, 0, 1, 0) \hspace{0.05cm},(1, 1, 1, 1) \}\hspace{0.05cm}.\]

Zusammenhang zwischen Generator– und Prüfmatrix (1)

Zur Definition dieser beiden Beschreibungsmatrizen gehen wir von folgenden Definitionsgleichungen aus:

\[\underline{x} = \underline{u} \cdot { \boldsymbol{\rm G}} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{x}^{\rm T} = { \boldsymbol{\rm G}}^{\rm T} \cdot \underline{u}^{\rm T} \hspace{0.05cm},\]

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

Verknüpft man diese zwei Gleichungen, so erhält man:

\[{ \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} \cdot \underline{u}^{\rm T} = \underline{0}\hspace{0.5cm} \forall \hspace{0.15cm}\underline{u} \in {\rm GF}(2^k)\hspace{0.3cm} \Rightarrow \hspace{0.3cm} { \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = { \boldsymbol{\rm 0}} \hspace{0.05cm}.\]

Anzumerken ist, dass in diesen Gleichungen 0 einen Zeilenvektor mit k Elementen bezeichnet und 0 eine Matrix mit m Zeilen und k Spalten. Alle Elemente von 0 und 0 sind identisch 0.

: Wir betrachten wie im Beispiel auf der dritten Seite dieses Kapitels den (5, 3)–Blockcode

\[\mathcal{C} = \{ \hspace{0.35cm} ( \hspace{0.05cm} 0, 0, 0, 0, 0) \hspace{0.05cm},\]

\[ \hspace{0.8cm}( \hspace{0.05cm} 0, 1, 1, 1, 0) \hspace{0.05cm},\]

\[ \hspace{0.8cm}( \hspace{0.05cm}0, 1, 0, 1, 0) \hspace{0.05cm},\]

\[ \hspace{0.8cm}( \hspace{0.05cm}0, 0, 1, 0, 0) \hspace{0.05cm},\]

\[ \hspace{0.8cm}( \hspace{0.05cm} 1, 1, 0, 1, 1) \hspace{0.05cm},\]

\[ \hspace{0.8cm}( \hspace{0.05cm}1, 0, 1, 0, 1) \hspace{0.05cm},\]

\[ \hspace{0.8cm}( \hspace{0.05cm}1, 0, 0, 0, 1) \hspace{0.05cm},\]

\[ \hspace{0.8cm}(\hspace{0.05cm}1, 1, 1, 1, 1) \}\hspace{0.05cm}.\]

Aus n = 5 und k = 3 folgt für die Anzahl der Prüfgleichungen m = 2. Durch Analyse der möglichen Codeworte erhält man folgende Ergebnisse:

\[x_1 \oplus x_5 \hspace{-0.15cm} = \hspace{-0.15cm} 0 \hspace{0.05cm},\] \[x_2 \oplus x_4 \hspace{-0.15cm} = \hspace{-0.15cm} 0\]

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

\[\Rightarrow \hspace{0.3cm} { \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = \begin{pmatrix} 1 &0 &0 &0 &1\\ 0 &1 &0 &1 &0 \end{pmatrix} \begin{pmatrix} 1 &0 &0 \\ 1 &1 &1 \\ 0 &0 &1 \\ 1 &1 &1 \\ 1 &0 &0 \end{pmatrix} = \begin{pmatrix} 0 &0 &0 \\ 0 &0 &0 \end{pmatrix}\hspace{0.05cm}.\]

Die Nullmatrix besteht hier aus m = 2 Zeilen und k = 3 Spalten. Beispielsweise gilt für das Element in der ersten Zeile und der ersten Spalte:

\[1 \cdot 1 \hspace{0.05cm}\oplus \hspace{0.05cm} 0 \cdot 1 \hspace{0.05cm}\oplus \hspace{0.05cm} 0 \cdot 0 \hspace{0.05cm}\oplus \hspace{0.05cm} 0 \cdot 1 \hspace{0.05cm}\oplus \hspace{0.05cm} 1 \cdot 1 = 0 \hspace{0.05cm}.\]

Im allgemeinen Fall können H und G nicht direkt ineinander umgerechnet werden, schon allein aufgrund der unterschiedlichen Dimensionen von Prüfmatrix (m x n) und Generatormatrix (k x n).

Zusammenhang zwischen Generator– und Prüfmatrix (2)

Der Rechengang vereinfacht sich, wenn die k&timesn–Generatormatrix in systematischer Form vorliegt:

\[{ \boldsymbol{\rm G_{sys}}} =\left({ \boldsymbol{\rm I}}_k \: ; \: { \boldsymbol{\rm P}}\right)\hspace{0.05cm}.\]

Dann folgt aus H · G^T = 0 für die m&timesn–Prüfmatrix mit m = n – k:

\[{ \boldsymbol{\rm H}} =\left(-{ \boldsymbol{\rm P}}^{\rm T} \: ; \: { \boldsymbol{\rm I}}_m \right) = \left [ \left({ \boldsymbol{\rm P}}^{\rm T} \: ; \: { \boldsymbol{\rm I}}_m \right)\right ]_{{\rm bin\ddot{a}r}} \hspace{0.05cm}.\]

Die erste der beiden Gleichungen gilt allgemein. Da wir uns im gesamten Kapitel 1 auf binäre Codes beschränken ⇒ C  ∈  GF(2ⁿ), gilt –P = +P, und man erhält die Form, die wir im Weiteren verwenden.

: Wir betrachten weiterhin den beispielhaften (5, 3)–Blockcode, gehen aber nun von der systematischen Generatormatrix G_sys aus:

\[{ \boldsymbol{\rm G_{sys}}} = \begin{pmatrix} 1 &0 &0 &0 &1\\ 0 &1 &0 &1 &0\\ 0 &0 &1 &0 &0 \end{pmatrix} =\left({ \boldsymbol{\rm I}}_3 \: ; \: { \boldsymbol{\rm P}}\right)\]

\[\Rightarrow \hspace{0.3cm} { \boldsymbol{\rm I_3}}= \begin{pmatrix} 1 &0 &0 \\ 0 &1 &0\\ 0 &0 &1 \end{pmatrix}, \hspace{0.3cm} { \boldsymbol{\rm P}}= \begin{pmatrix} 0 &1 \\ 1 &0\\ 0 &0 \end{pmatrix} \hspace{0.3cm}\Rightarrow\hspace{0.3cm} { \boldsymbol{\rm P}^{\rm T}} = \begin{pmatrix} 0 &1 &0\\ 1 &0 &0 \end{pmatrix}\hspace{0.05cm}.\]

Damit erhält man für die Prüfmatrix

\[{ \boldsymbol{\rm H}} =\left({ \boldsymbol{\rm P}}^{\rm T} \: ; \: { \boldsymbol{\rm I}}_2 \right) = \begin{pmatrix} 0 &1 &0 &1 &0\\ 1 &0 &0 &0 &1 \end{pmatrix} \hspace{0.05cm},\]

und es ergibt sich folgende Codetabelle:

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

Zusammen mit dem Vektor x = (u₁, u₂, u₃, p₁, p₂) = (x₁, x₂, x₃, x₄, x₅) lauten dann die Prüfbits

\[p_1 = u_2 \hspace{0.05cm},\hspace{0.2cm}p_2 = u_1 \hspace{0.05cm},\]

und die entsprechenden Prüfgleichungen des Decoders:

\[x_2 + x_4 = 0 \hspace{0.05cm},\hspace{0.2cm}x_1 + x_5 = 0 \hspace{0.05cm}.\]

Man erkennt aus diesen Gleichungen und auch aus obiger Codetabelle, dass dieser Code gegenüber einem Übertragungsfehler hinsichtlich des dritten Bits (x₃ = u₃) keinen Schutz bieten. Damit ist natürlich weder eine Fehlererkennung und noch weniger Fehlerkorrektur möglich. Gleiches gilt aber auch für den nichtsystematischen Code auf der letzten Seite.

Darstellung von SPC und RC als duale Codes

Nun sollen für die bereits in Kapitel 1.3 behandelten Codes noch jeweils die Generatormatrix G und die Prüfmatrix H angegeben werden. Die Codelänge sei für die folgenden Beispiele stets n = 5, doch lassen sich die Ergebnisse auch für andere Codelängen in gleicher Weise interpretieren. Es gilt für

• den Single–Parity–check Code ⇒ SPC (5, 4):

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

• den Wiederholungscode (Repetition Code) ⇒ RC (5,1):

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

Die jeweils erste Gleichung lässt sich einfach aus der jeweiligen Definition herleiten und die abgeleitete Gleichung folgt aus der Beziehung H · G^T = 0. Aus den obigen Matrizen kann verallgemeinert werden:

• Die Generatormatrix des RC (5, 1) ist identisch mit der Prüfmatrix des SPC (5, 4). Es handelt sich jeweils um (5, 1)–Matrizen.
  

• Die Prüfmatrix des RC (5, 1) ist identisch mit der Generatormatrix des SPC (5, 4). Die beiden Matrizen haben jeweils 5 Spalten und 4 Zeilen.
  

• Dieser Sachverhalt ergibt sich, weil es sich bei den hier betrachteten Beispielen um duale Codes handelt. Zur Erklärung benötigen wir noch zwei Definitionen:
  

1: Zwei lineare Codes C und C ', beide aus GF(2ⁿ), sind orthogonal, wenn alle Codeworte x ∈ C zu allen Codeworten x' ∈ C ' orthogonal sind. Man bezeichnet C und C ' als duale Codes.

2: Zwei Codeworte x ∈ GF(2ⁿ) und x' ∈ GF(2ⁿ) sind immer dann zueinander orthogonal, wenn das innere Produkt verschwindet:

\[\left \langle \underline{x} \cdot \underline{x}' \right \rangle = \sum_{i=1 }^{n} x_i \cdot x_i' = 0 \hspace{0.05cm}, \hspace{0.5cm} \left \langle \underline{x} \cdot \underline{x}' \right \rangle \in {\rm GF}(2^n) \hspace{0.05cm}.\]

Wegen der Produktbildung in GF(2ⁿ) sind auch folgende Codewort–Paare zueinander orthogonal:

\[\left \langle \hspace{0.1cm}(0, 1, 1, 0) \hspace{0.05cm}, \hspace{0.2cm} (1, 1, 1, 0) \hspace{0.1cm} \right \rangle = 0\hspace{0.05cm},\hspace{0.2cm} \left \langle \hspace{0.1cm}(0, 1, 1, 0) \hspace{0.05cm}, \hspace{0.2cm} (0, 1, 1, 0) \hspace{0.1cm}\right \rangle = 0\hspace{0.05cm}.\]

Der Code C spannt einen k–dimensionalen Untervektorraum in GF(2ⁿ) auf. Der Untervektorraum des dualen Codes C ' ist zu diesem orthogonal und weist die Dimension n – k auf. Damit gilt:

\[{\rm dim} \{ \mathcal{C} \} + {\rm dim} \{ \mathcal{C}' \} = n\hspace{0.05cm}.\]

Einige Eigenschaften des (7, 4, 3)–Hamming–Codes

Fassen wir die bisherigen Ergebnisse dieses Kapitels am Beispiel des systematischen Hamming–Codes nochmals zusammen, der bereits im Kapitel 1.3 ausführlich beschrieben wurde. Dieser (7, 4, 3)–Code ist gekennzeichnet durch

• die Anzahl der Prüfgleichungen: m = 3,
  

• die Codelänge: n = 2^m – 1 = 7,
  

• die Informationswortlänge: k = n – m = 4,
  

• die Anzahl der Codeworte (Dimension): 2^k = 16,
  

• die Rate R = k/n = 4/7,
  

• die minimale Distanz d_min = 3 (unabhängig von m, n und k).
  

In der obigen Tabelle sind die 2^k = 16 Codeworte angegeben (Informationsbit schwarz, Prüfbit rot). Man erkennt daraus, dass

• der Code sowohl das 0–Wort (0000000) als auch das 1–Wort (1111111) beinhaltet,

• es sieben Codeworte gibt, die sich aus (0001011) jeweils durch zyklische Verschiebung ergeben (alle gelb hinterlegt),

• es sieben Codeworte gibt, die sich aus (0011101) jeweils durch zyklische Verschiebung ergeben (alle grün hinterlegt),

• zu jedem Codewort auch das „negierte” Codewort existiert, zum Beispiel neben (0001011) auch das Codewort (1110100),

• die Prüfmatrix wie folgt geschrieben werden kann:

\[{ \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}=\left({ \boldsymbol{\rm P}}^{\rm T} \: ; \: { \boldsymbol{\rm I}}_3 \right)\]

\[\Rightarrow\hspace{0.3cm}{ \boldsymbol{\rm P}}^{\rm T} = \begin{pmatrix} 1 &1 &1 &0 \\ 0 &1 &1 &1 \\ 1 &1 &0 &1 \end{pmatrix}\hspace{0.05cm},\hspace{0.2cm}{ \boldsymbol{\rm I}}_3 = \begin{pmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &0 &1 \end{pmatrix}\hspace{0.05cm},\]

• dementsprechend für die Generatormatrix gilt:

\[{ \boldsymbol{\rm G}} =\left({ \boldsymbol{\rm I}}_4 \: ; \: { \boldsymbol{\rm P}}\right) = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1\\ 0 &1 &0 &0 &1 &1 &1\\ 0 &0 &1 &0 &1 &1 &0\\ 0 &0 &0 &1 &0 &1 &1 \end{pmatrix}\hspace{0.05cm}.\]

Aufgaben

A1.7 H und G des (7, 4)–Hamming–Codes

A1.8 Identische Codes

A1.9 Erweiterter Hamming–Code

A1.10 Einige Generatormatrizen