Linearer Code

Ein Linearer Code ist in der Kodierungstheorie ein spezieller Blockcode: Man betrachtet die Blöcke als endlichdimensionale Vektorräume über einen endlichen Körper $V=\mathbb {F} _{q}^{n}$. Ein Code ist genau dann ein Linerarer Code $C$ , falls er ein Untervektorraum von $V$ ist.

Die Linearen Codes haben den Vorteil, dass Methoden der Linearen Algebra verwendet werden können. Sie sind somit einfach zu codieren und decodieren.

Die meisten wichtigen Codes sind linear: Hamming Code, Reed-Muller-Code, Hadamard-Code, alle zyklischen Codes (Damit auch BCH und Reed-Solomon Codes), Golay Codes, Goppa-Codes.

Ist die Vektorraumdimension von $C$ gleich $k$, so nennt man $C$ einen $[n,k]$-Code, oder bei einem Hammingabstand von $d$ auch $[n,k,d]$-Code.

Eigenschaften

Da $C$ einen Untervektorraum besitzt, existiert eine Basis $g_{1},\dots ,g_{k}$. Fasst man diese Basis in einer Matrix

$G={\begin{pmatrix}g_{1}\\\vdots \\g_{k}\end{pmatrix}}$

zusammen erhält man eine Erzeugermatrix. Desweiteren besitzt der Code eine Kontrollmatrix $H$, diese hat die Eigenschaft, dass $Hc^{t}=0$ gilt für alle Codewörter $c$ des Codes $C$. Der Hammingabstand von $C$ ist gleich der minimalen Anzahl von linear abhängigen Spalten der Kontrollmatrix.

Permutiert man die einzelnen Koordinaten der Codewörter, dann erhält man einen äquivalenten Code. Damit und mittels linearer Algebra kann man zu jedem linearen Code eine äquivalenten finden, der eine Erzeugermatrix der Form $G=(\mathbb {E} _{k}|P)$ hat, dabei ist $\mathbb {E}$ die $(k\times k)$ Einheitsmatrix, und $P$ ist eine $(k\times (n-k))$ Matrix. $G$ heißt dann eine Erzeugermatrix in reduzierter Form. Die ersten $k$ Koordinaten können dann als Informationssymbole und die letzten $n-k$ als Kontrollsymbole interpretiert werden. Ist $G$ eine Erzeugermatrix in reduzierter Form, kann eine Kontrollmatrix $H$ sofort gefunden werden: $H=(-P^{t}|\mathbb {E} _{n-k})$. Ein linearer Code ist bereits durch seine Erzeugermatrix oder seine Kontrollmatrix bestimmt.

Beispiel: der $[7,4,3]$-Hammingcode besitzt folgende Erzeugermatrix in reduzierter Form, sowie die dazugehörige Konrollmatrix.

$G={\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&1&1&1\\0&0&0&1&0&1&1\\\end{pmatrix}}\qquad H={\begin{pmatrix}1&1&1&0&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\\\end{pmatrix}}$

Codierung

Ein Wort $x=(x_{1},\dots ,x_{k})$ aus dem Raum $\mathbb {F} _{q}^{k}$ wird codiert, indem das Produkt $xG$ gebildet wird. Soll beispielsweise das Wort $(0,0,1,1)$ mit dem $[7,4,3]$-Hammingcode codiert werden, sieht das so aus:

${\begin{pmatrix}0,0,1,1\end{pmatrix}}{\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&1&1&1\\0&0&0&1&0&1&1\\\end{pmatrix}}={\begin{pmatrix}0,0,1,1,1,0,0\end{pmatrix}}$.

Man beachte, dass hier die Multiplikation in $\mathbb {F} _{2}$ erfolgt, also modulo 2.

Decodierung

Als Decodierung wird in der Codierungstheorie die maximum-likehood Methode verdwendet, sprich ein empfangenes Wort $x$ wird zu dem Codewort $c$ decodiert, welches den geringsten Hammingabstand zu $x$ hat. Es sei $e=x-c$, $e$ wird Fehlervektor genannt. In $e$ sind genau die Koordinaten ungleich Null, bei denen während der Übertragung Fehler auftraten. Nun sind alle (fehlerhaften) Wörter mit dem gleichen Fehlervektor im gleichen affinen Unterraum. Deshalb ist für solche Worte $z^{t}=He^{t}$ konstant.

Daraus resultiert folgende Decodierregel: Wähle für jeden möglichen Fehlervektor $e$ jeweils das Wort mit minimalem Hamminggewicht, also das mit möglichst wenigen Koordinaten ungleich Null; und damit sozusagen ein "fehlerhaftes" Nullwort. Für jedes dieser Worte berechne man $z^{t}=He^{t}$ und speichere diese Paare. Man kann somit für jedes $z$ den dazugehörenden Fehlervektor $e=e(z)$ berechen. Um dann ein empfanges Wort $x$ zu decodieren berechnet man dann $c(x):=x-e(Hx^{t})$. Damit erhält man ein gültiges Codewort, ist $G$ noch in reduzierter Form, kann dann die Information einfach an den ersten $k$ Symbolen abgelesen werden (falls nicht muss eventuell noch ein lineares Gleichungssystem gelöst werden). $e$ heißt dabei Nebenklassenführer und $z$ Syndrom, die Decodieregel Syndrom-Decodierung.

Will man den $[7,4,3]$-Hammingcode decodieren, trifft man zuerst die Annahme, dass nur $1$-Bit Fehler auftreten (falls mehr Fehler auftreten ist keine Fehlerkorrektur sondern nur noch eine Fehlererkennung möglich). Die möglichen Fehlervektoren sind dann $(0,0,0,0,0,0,0)$, $(1,0,0,0,0,0,0)$, $(0,1,0,0,0,0,0)$, $(0,0,1,0,0,0,0)$, $(0,0,0,1,0,0,0)$, $(0,0,0,0,1,0,0)$, $(0,0,0,0,0,1,0)$, $(0,0,0,0,0,0,1)$ Für jeden dieser Fehlervektoren wird nun das Syndrom $z^{t}=He^{t}$ berechnet. Damit ergibt sich

$z$	$e$
$(0,0,0)$	$(0,0,0,0,0,0,0)$
$(1,1,0)$	$(1,0,0,0,0,0,0)$
$(1,0,1)$	$(0,1,0,0,0,0,0)$
$(1,1,1)$	$(0,0,1,0,0,0,0)$
$(0,1,1)$	$(0,0,0,1,0,0,0)$
$(1,0,0)$	$(0,0,0,0,1,0,0)$
$(0,1,0)$	$(0,0,0,0,0,1,0)$
$(0,0,1)$	$(0,0,0,0,0,0,1)$

Wird dann das Wort $x=(0,1,1,1,1,0,0)$ empfangen ergibt dann $Hx^{t}=(1,0,1)^{t}$. Damit ergibt sich der Fehlervektor $e=e((1,0,1))=(0,1,0,0,0,0,0)$ und $x$ wird somit nach $c(x)=(0,1,1,1,1,0,0)-(0,1,0,0,0,0,0)=(0,0,1,1,1,0,0)$ decodiert, das Klartextwort ist dann $(0,0,1,1)$.

Anwendung

Die Codierung und Decodierung ist, so wie sie oben beschrieben ist, relativ aufwendig. Bei der Codierung muss die Erzeugermatrix im Speicher gehalten werden, was bei Systemen mit begrenzten Ressourcen (zum Beispiel mobile Endgeräte oder Weltraumsonden) problematisch ist. Bei der Decodierung wird eine - je nach Korrekturrate - große Tabelle benötigt, der Speicherverbrauch ist dementsprechend groß. Aus diesem Grund werden in der Regel zusätzliche Eigenschaften der Codes benutzt um diese effizient zu codieren und decodieren. Binäre Zyklische Codes lassen sich beispielsweise sehr einfach mittels Schieberegister und XOR Gatter realisieren.

Literatur

Werner Lütkebohmert: Codierungstheorie, Vieweg Verlag, 2003, ISBN 3-528-03197-2

J. H. van Lint: Introduction to Coding Theory, Springer Verlag, 1999, ISBN 3-540-64133-5

F. J. MacWilliams, N. J. A. Sloane: The Theory of Error-Correcting Codes, North-Holland publishing company, 1972