Difference between revisions of "Channel Coding/General Description of Linear Block Codes"

From LNTwww
Line 108: Line 108:
 
*Aus <b>H</b> &middot; <i><u>x</u></i><sup>T</sup> = <u>0</u> folgt nicht, dass alle Codeworte eine gerade Anzahl von Einsen beinhalten.{{end}}<br>
 
*Aus <b>H</b> &middot; <i><u>x</u></i><sup>T</sup> = <u>0</u> folgt nicht, dass alle Codeworte eine gerade Anzahl von Einsen beinhalten.{{end}}<br>
  
 +
== Codefestlegung durch die Generatormatrix ==
 +
<br>
 +
Die Prüfmatrix <b>H</b> eines (<i>n</i>, <i>k</i>)&ndash;Blockcodes <i>C</i> hat <i>m</i> = <i>n</i> &ndash; <i>k</i> Zeilen und <i>n</i> Spalten. Den gleichen Code kann man aber auch durch die Generatormatrix <b>G</b> mit ebenfalls <i>n</i> Spalten, aber <i>k</i> Zeilen beschreiben:<br>
  
 +
{{Definition}}''':''' Ein linearer Blockcode <i>C</i> kann durch die Prüfmatrix <b>H</b> bzw. mit der Generatormatrix <b>G</b> wie folgt charakterisiert werden:
  
 +
:<math>\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},</math>
 +
:<math>\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}.</math>{{end}}<br>
  
 +
Bevor wir uns den Eigenschaften der Generatormatrix zuwenden, beschreiben wir an einem Beispiel die Erzeugung der Codeworte.<br>
  
 +
{{Beispiel}}''':''' Wir betrachten einen linearen (5, 3)&ndash;Blockcode mit der Generatormatrix
  
 +
:<math>{ \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}.</math>
 +
 +
Damit werden die Informationsworte <i><u>u</u></i> = (<i>u</i><sub>1</sub>, <i>u</i><sub>2</sub>, <i>u</i><sub>3</sub>) den Codeworten <i><u>x</u></i>&nbsp;=&nbsp;(<i>x</i><sub>1</sub>,&nbsp;<i>x</i><sub>2</sub>,&nbsp;<i>x</i><sub>3</sub>,&nbsp;<i>x</i><sub>4</sub>,&nbsp;<i>x</i><sub>5</sub>) gemäß der folgenden Tabelle mit 8 Einträgen zugeordnet. Es gilt <i><u>x</u></i>&nbsp;=&nbsp;<i><u>u</u></i>&nbsp;&middot;&nbsp;<b>G</b>.
 +
 +
:<math>\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},</math>
 +
:<math>\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},</math>
 +
:<math>\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},</math>
 +
:<math>\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},</math>
 +
:<math>\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},</math>
 +
:<math>\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},</math>
 +
:<math>\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},</math>
 +
:<math>\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}.</math>{{end}}<br>
 +
 +
Die hier zur Berechnung herangezogenen Basisvektoren <i><u>g</u></i><sub>1</sub>, <i><u>g</u></i><sub>2</sub>, <i><u>g</u></i><sub>3</sub> &ndash; jeweils mit der Länge <i>n</i> = 5 &ndash; entsprechen den <i>k</i> = 3 Zeilen der Generatormatrix <b>G</b>. Anzumerken ist ferner, dass dieser Code wegen <i>d</i><sub>min</sub> = 1 weder zur Fehlerkorrektur noch zur Fehlererkennung geeignet ist. Trotzdem wird er auch auf den nächsten Seiten beispielhaft weiter betrachtet.<br>
 +
 +
<i>Hinweis</i>: An dieser Stelle möchten wir Sie auf ein Interaktionsmodul zum Buch &bdquo;Digitalsignalübertragung&rdquo; aufmerksam machen, das die Bedeutung und Berechnung von Basisfunktionen vermittelt, wenn auch in völlig anderem Zusammenhang als in diesem Buch:<br>
 +
 +
[[Gram&ndash;Schmidt&ndash;Verfahren Please add link and do not upload flash files.]]
  
  

Revision as of 19:30, 9 January 2017

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 2k Codeworten x = (x1, x2, ... , xn), 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 C1 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 C2 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 C2.


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


Codetabelle des systematischen (7, 4, 3)–Hamming–Codes

Man erkennt aus der Tabelle für den HC (7, 4, 3), dass dieser linear und zyklisch ist (schwarz: 4 Informationsbit, rot: nk = 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 (7, 4, 3)–Hamming–Code

  • den k = 4 Informationsbits x1, x2, x3, x4 , und
  • den m = 3 Prüfbits x5, x6, x7.

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 = nk = 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 = (x1, x2, ... , x7) 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 xT und 0T.

:

(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 · xT = 0T 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 2k = 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 = nk der Prüfgleichungen.
  • Aus H · xT = 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 = nk 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 = (u1, u2, u3) den Codeworten x = (x1x2x3x4x5) 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 g1, g2, g3 – jeweils mit der Länge n = 5 – entsprechen den k = 3 Zeilen der Generatormatrix G. Anzumerken ist ferner, dass dieser Code wegen dmin = 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.