Linearer Code

Ein linearer Code ist in der Kodierungstheorie ein spezieller Blockcode, bei dem die Codewörter Elemente eines endlichdimensionalen Vektorraums ${\displaystyle \mathbb {F} _{q}^{n}}$ über einem endlichen Körper ${\displaystyle \mathbb {F} _{q}}$ sind. Ein Code ist genau dann linear, wenn er ein Untervektorraum von ${\displaystyle \mathbb {F} _{q}^{n}}$ ist.

Lineare Codes h​aben den Vorteil, d​ass Methoden d​er Linearen Algebra verwendet werden können. Sie s​ind somit einfach z​u kodieren u​nd dekodieren. Die meisten wichtigen Codes s​ind linear: Hamming-Code, Low-Density-Parity-Check-Code, Reed-Muller-Code, Hadamard-Code, a​lle zyklischen Codes (damit a​uch BCH, Reed-Solomon-Codes, Golay-Codes u​nd Goppa-Codes).

Ist die Vektorraumdimension des linearen Codes ${\displaystyle C}$ gleich ${\displaystyle k}$, so nennt man ${\displaystyle C}$ einen ${\displaystyle [n,k]}$-Code oder bei einem Hamming-Abstand von ${\displaystyle d}$ auch ${\displaystyle [n,k,d]}$-Code.

Eigenschaften

Da ${\displaystyle C}$ ein Untervektorraum von ${\displaystyle V}$ ist, existiert eine Basis ${\displaystyle g_{1},\dots ,g_{k}}$ von ${\displaystyle C}$. Fasst man diese Basis in einer Matrix

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

zusammen, erhält man eine Erzeugermatrix. Des Weiteren besitzt der Code eine Kontrollmatrix ${\displaystyle H}$. Für sie gilt ${\displaystyle Hc^{T}=0}$ genau dann, wenn ${\displaystyle c}$ ein Codewort ist. Der Rang von ${\displaystyle G}$ ist ${\displaystyle k}$, der von ${\displaystyle H}$ ist ${\displaystyle n-k}$. Der Hamming-Abstand von ${\displaystyle C}$ ist die minimale Anzahl linear abhängiger Spalten der Kontrollmatrix.

Das Hamming-Gewicht eines Codewortes ${\displaystyle c=(c_{1},\dots ,c_{n})}$ ist gleich der Anzahl der ${\displaystyle c_{i}}$, die von Null verschieden sind. Beispielsweise hat das Codewort ${\displaystyle (430540)}$ über ${\displaystyle \mathbb {F} _{7}^{6}}$ das Hamming-Gewicht 4. Der Hamming-Abstand des Codes ist gleich dem kleinsten Hamming-Gewicht aller Codewörter außer dem Nullwort.

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

Beispiel

Der binäre ${\displaystyle [7,4,3]}$-Hamming-Code besitzt folgende Erzeugermatrix in reduzierter Form sowie die dazugehörige Kontrollmatrix:

${\displaystyle G=(\mathbb {E} _{k}|P)}$		${\displaystyle H=(-P^{T}|\mathbb {E} _{n-k})}$
${\displaystyle G={\begin{pmatrix}{\color {Brown}1}&0&0&0&1&1&0\\0&{\color {Brown}1}&0&0&1&0&1\\0&0&\color {Brown}{1}&0&1&1&1\\0&0&0&{\color {Brown}1}&0&1&1\\\end{pmatrix}}\qquad }$		${\displaystyle H={\begin{pmatrix}1&1&1&0&{\color {Brown}1}&0&0\\1&0&1&1&0&{\color {Brown}1}&0\\0&1&1&1&0&0&{\color {Brown}1}\\\end{pmatrix}}}$

Kodierung

Ein Wort ${\displaystyle x=(x_{1},\dots ,x_{k})}$ aus dem Raum ${\displaystyle \mathbb {F} _{q}^{k}}$ wird kodiert, indem das Produkt ${\displaystyle xG}$ gebildet wird. Die Kodierung des Wortes ${\displaystyle (0,0,1,1)}$ mit dem ${\displaystyle [7,4,3]}$-Hamming-Code veranschaulicht beispielsweise die folgende Rechnung.

${\displaystyle {\begin{aligned}x\cdot G&=c\\{\begin{pmatrix}0,0,1,1\end{pmatrix}}\cdot {\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}}\end{aligned}}}$

Da hier die Addition in ${\displaystyle \mathbb {F} _{2}}$ erfolgt, gilt ${\displaystyle 1+1=0}$

Dekodierung

Mit Dekodierung bezeichnet man das Zuordnen eines empfangenen, möglicherweise fehlerhaften Eingabevektors ${\displaystyle x}$ zu einem Codevektor ${\displaystyle c'}$. Die Dekodierung ist nicht die Umkehrfunktion der Kodierung, die einem Codevektor wieder einen Vektor aus ${\displaystyle \mathbb {F} _{q}^{k}}$ zuordnet.

Als Dekodierungsmethode wird in der Kodierungstheorie meistens die Methode der größten Wahrscheinlichkeit (englisch: maximum likelihood decoding) verwendet. Dabei wird ein empfangener Vektor ${\displaystyle x}$ zu dem Codevektor ${\displaystyle c'}$ dekodiert, der mit der größten Wahrscheinlichkeit zum tatsächlich versandten Codevektor ${\displaystyle c}$ identisch ist. Häufig wird der Vektor, bei dem die wenigsten Stellen (Fehler) korrigiert werden müssen, als der Wahrscheinlichste angenommen. Mathematisch gesprochen heißt das, man sucht den Codevektor ${\displaystyle c'}$ mit dem geringsten Hamming-Abstand zum empfangenen Vektor ${\displaystyle x}$. Dieser Fall wird auch als Methode des nächstgelegenen Nachbarn (englisch: nearest neighbor decoding) bezeichnet. Durch Kenntnis der Art der gesendeten Daten oder des verwendeten Kanals können gegebenenfalls andere Informationen verwendet werden, um die Wahrscheinlichkeit für bestimmte Codevektoren zu bestimmen.

Es sei ${\displaystyle c}$ der tatsächlich versendete (Code-)Vektor und ${\displaystyle x}$ der empfangene Vektor. Die Dekodierung sucht aus allen ${\displaystyle q^{n}}$ Codevektoren den oder die Codevektoren ${\displaystyle c'}$, die mit der größten Wahrscheinlichkeit versendet wurden.

${\displaystyle c'=\operatorname {argmax} _{y\in C}\left\{\operatorname {P} \left[y=c\right]\right\}}$

Bei d​er Nearest-Neighbor-Dekodierung also:

${\displaystyle c'=\operatorname {argmin} _{y\in C}\left\{wt(x-y)\right\}}$

Man sollte d​abei beachten, d​ass diese Zuordnung b​ei den meisten Codes n​icht für a​lle Fehlervektoren eindeutig ist. Es g​ibt dann einige Fehlervektoren, d​ie nicht zugeordnet werden können, d​a sie m​ehr als e​inen nächstgelegenen Nachbarn haben. Ist für j​eden Fehlervektor e​ine eindeutige Dekodierung möglich, s​o heißt d​er Code perfekt.

Syndromdekodierung

Eine effizientere Methode für die Dekodierung stellt die sogenannte Syndrom-Dekodierung dar. Das Syndrom ${\displaystyle s_{x}}$ eines Vektors ${\displaystyle x}$ erhält man durch Multiplikation der Kontrollmatrix ${\displaystyle H}$ mit ${\displaystyle x^{T}}$.

${\displaystyle s_{x}^{T}=Hx^{T}}$

Es sei ${\displaystyle e=x-c}$ der Fehlervektor von ${\displaystyle x}$. In ${\displaystyle e}$ sind genau die Koordinaten ungleich Null, bei denen während der Übertragung Fehler aufgetreten sind.

Für das Syndrom von ${\displaystyle x}$ gilt wegen der Linearität des Codes:

${\displaystyle s_{x}^{T}=Hx^{T}=Hc^{T}+He^{T}}$

Da d​as Syndrom v​on fehlerfreien Codevektoren i​mmer Null ist, folgt:

${\displaystyle s_{x}^{T}=He^{T}=s_{e}^{T}}$

Alle (fehlerhaften) Wörter mit dem gleichen Fehlervektor sind im gleichen affinen Unterraum, das heißt für solche Wörter ist das Syndrom ${\displaystyle s_{e}^{T}=He^{T}}$ konstant.

Alle Vektoren, die aus einem beliebigen, festen Vektor durch Subtraktion eines beliebigen Codevektors hervorgegangen sind, bilden eine Nebenklasse der Untergruppe ${\displaystyle C}$ von ${\displaystyle \mathbb {F} _{q}^{n}}$. Der Vektor mit minimalem Gewicht in dieser Klasse heißt Führer der Nebenklasse (englisch: coset leader). Daher ist auch der Begriff „coset leader decoding“ verbreitet.

Um ${\displaystyle x}$ zu ${\displaystyle c'}$ zu dekodieren, sucht man also den Fehlervektor ${\displaystyle e'}$, dessen Syndrom identisch zum Syndrom von ${\displaystyle x}$ ist und dessen Hamming-Gewicht minimal ist. Mit diesem Fehlervektor berechnet man ${\displaystyle c'=x-e'}$ den nächstgelegenen Codevektor ${\displaystyle c'}$. Man kann also eine Tabelle mit bis zu ${\displaystyle q^{n-k}}$ Zeilen aufstellen, die für jedes Syndrom eines empfangenen Vektors den entsprechenden Fehlervektor mit minimalem Hamming-Gewicht beinhaltet. Ist das Syndrom gleich 0, dann muss nichts korrigiert werden ansonsten beschränkt sich Dekodierung auf das Nachschlagen des Fehlervektors in dieser Tabelle und Korrigieren der so detektierten Fehler.

Anders interpretiert sind die Nebenklassen gerade die Äquivalenzklassen der Äquivalenzrelation ${\displaystyle x\equiv y\Leftrightarrow s_{x}^{T}=s_{y}^{T}}$ Die Führer sind gerade Vertreter der Äquivalenzklassen, man wählt einen mit minimalem Hamming-Gewicht. Perfekte Codes zeichnen sich dadurch aus, dass die Führer eindeutig festgelegt sind.

Die Dekodierung von linearen Codes ist im Allgemeinen NP-vollständig, das heißt, es sind keine Algorithmen mit polynomieller Laufzeit bekannt.[1] Die bekannten linearen Codes, beispielsweise Hamming-Codes, zeichnen sich dadurch aus, dass für sie effiziente Dekodierungs-Algorithmen bekannt sind. Die Komplexität der linearen Dekodierung ist Grundlage für das McEliece-Kryptosystem, das als sicher gilt, aber aufgrund seiner vergleichsweise langen Schlüssel bisher selten eingesetzt wird.

Beispiel

Will man den ${\displaystyle [7,4,3]}$-Hamming-Code (von oben) dekodieren, trifft man zuerst die Annahme, dass nur ${\displaystyle 1}$-Bit Fehler auftreten. Die möglichen Fehlervektoren ${\displaystyle e}$ sind dann

${\displaystyle (1,0,0,0,0,0,0)}$

${\displaystyle (0,1,0,0,0,0,0)}$

${\displaystyle (0,0,1,0,0,0,0)}$

${\displaystyle (0,0,0,1,0,0,0)}$

${\displaystyle (0,0,0,0,1,0,0)}$

${\displaystyle (0,0,0,0,0,1,0)}$

${\displaystyle (0,0,0,0,0,0,1)}$

Für jeden dieser Fehlervektoren wird nun das Syndrom ${\displaystyle s^{T}=He^{T}}$ berechnet. Damit ergibt sich

${\displaystyle e}$	${\displaystyle s}$
${\displaystyle (1,0,0,0,0,0,0)}$	${\displaystyle (1,1,0)}$
${\displaystyle (0,1,0,0,0,0,0)}$	${\displaystyle (1,0,1)}$
${\displaystyle (0,0,1,0,0,0,0)}$	${\displaystyle (1,1,1)}$
${\displaystyle (0,0,0,1,0,0,0)}$	${\displaystyle (0,1,1)}$
${\displaystyle (0,0,0,0,1,0,0)}$	${\displaystyle (1,0,0)}$
${\displaystyle (0,0,0,0,0,1,0)}$	${\displaystyle (0,1,0)}$
${\displaystyle (0,0,0,0,0,0,1)}$	${\displaystyle (0,0,1)}$

Wird dann das fehlerhafte Wort ${\displaystyle x=(0,1,1,1,1,0,0)}$ empfangen, ergibt dann ${\displaystyle s^{T}=Hx^{T}=(1,0,1)^{T}}$. Damit ergibt sich der Fehlervektor ${\displaystyle e=e((1,0,1))=(0,1,0,0,0,0,0)}$, und ${\displaystyle x}$ wird somit nach ${\displaystyle c(x)=(0,1,1,1,1,0,0)-(0,1,0,0,0,0,0)=(0,0,1,1,1,0,0)}$ dekodiert. Das Klartextwort ist dann ${\displaystyle (0,0,1,1)}$.

Beispiel mit unvollständiger Dekodierung

Gegeben sei der ternäre (${\displaystyle q=3}$) Wiederholungscode der Länge 3:

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

${\displaystyle H={\begin{pmatrix}2&1&0\\2&0&1\\\end{pmatrix}}}$

Jeweils zwei Spalten von ${\displaystyle H}$ sind linear unabhängig, alle drei dagegen linear abhängig. Der minimale Hamming-Abstand des Codes berechnet sich als minimale Anzahl linear abhängiger Spalten in ${\displaystyle H}$ also zu 3. Es kann damit höchstens ein Zeichenfehler korrigiert werden. Die Syndromtabelle sieht folgendermaßen aus:

${\displaystyle e}$	${\displaystyle s}$
${\displaystyle (1,0,0)}$	${\displaystyle (2,2)}$
${\displaystyle (2,0,0)}$	${\displaystyle (1,1)}$
${\displaystyle (0,1,0)}$	${\displaystyle (1,0)}$
${\displaystyle (0,2,0)}$	${\displaystyle (2,0)}$
${\displaystyle (0,0,1)}$	${\displaystyle (0,1)}$
${\displaystyle (0,0,2)}$	${\displaystyle (0,2)}$

Durch Ausnützen v​on Linearitäten könnte d​ie Anzahl d​er Zeilen halbiert werden, m​an muss d​ann aber testen, o​b ein linear abhängiges Syndrom i​n der Tabelle ist.

Man betrachte nun ${\displaystyle x=(1,1,0)}$, ${\displaystyle y=(1,2,0)}$. Bei ${\displaystyle x}$ ist das Syndrom ${\displaystyle Hx^{t}=(0,2)^{t}}$, die Korrektur lautet: ${\displaystyle (1,1,0)-(0,0,2)=(1,1,1)}$. Die Berechnung des Syndroms von ${\displaystyle y}$ ergibt: ${\displaystyle Hy^{t}=(1,2)^{t}}$. Dieser Wert ist nicht in der Syndromtabelle enthalten, das Wort kann also nicht korrigiert werden.

Anwendung

Die Kodierung u​nd Dekodierung ist, s​o wie s​ie oben beschrieben ist, relativ aufwendig. Bei d​er Kodierung m​uss die Erzeugermatrix i​m Speicher gehalten werden, w​as bei Systemen m​it begrenzten Ressourcen (zum Beispiel mobile Endgeräte o​der Weltraumsonden) problematisch ist. Bei d​er Dekodierung w​ird eine – j​e nach Korrekturrate – große Tabelle benötigt; d​er Speicherverbrauch i​st dementsprechend groß. Aus diesem Grund werden i​n der Regel zusätzliche Eigenschaften d​er Codes benutzt, u​m diese effizient z​u kodieren u​nd dekodieren. Binäre zyklische Codes lassen s​ich beispielsweise s​ehr einfach mittels Schieberegister u​nd Exklusiv-Oder-Gatter realisieren.

Dualer Code

Zu jedem (linearen) Code ${\displaystyle C}$ gibt es einen dualen Code (oder auch Dualcode) ${\displaystyle C^{\perp }}$, der selbst ein linearer Code ist. Die Codewörter des dualen Codes sind alle Wörter aus ${\displaystyle \mathbb {F} _{q}^{n}}$, die zu den Codewörter aus ${\displaystyle C}$ dual sind:

Man definiert hierzu e​in inneres Produkt:

${\displaystyle \langle \cdot$ ;\cdot \rangle \,:\;\mathbb {F} _{q}^{n}\times \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}}

das die Vektoren ${\displaystyle x=(x_{1},x_{2},\dots ,x_{n}),y=(y_{1},y_{2},\dots ,y_{n})}$ folgendermaßen abbildet:

${\displaystyle \langle x;y\rangle =\sum _{i=1}^{n}x_{i}y_{i}}$

Trotz der ähnlichen Definition handelt es sich hierbei nicht um ein Skalarprodukt, da diese Bilinearform nicht positiv definit ist. Es gibt nämlich aufgrund der Eigenschaften von Endlichen Körpern meistens Vektoren, die ungleich dem Nullvektor sind und bei denen das innere Produkt 0 ergibt. Man denke beispielsweise an den binären Vektor ${\displaystyle (1,1)}$.

Mit Hilfe dieser Definition ergibt s​ich der Duale Code als:

${\displaystyle C^{\perp }=\{x\in \mathbb {F} _{q}^{n}\mid \langle x,c\rangle =0\;\mathrm {f{\ddot {u}}r\;alle} \;c\in C\}}$

Eine Erzeugermatrix d​es dualen Codes i​st eine Kontrollmatrix d​es Ursprungscodes u​nd umgekehrt.

Der d​uale Code spielt b​ei der Analyse d​er Eigenschaften v​on Codes e​ine wichtige Rolle.

Ein Spezialfall sind die sogenannten selbstdualen Codes. Dies sind Codes, die mit ihrem Dualcode identisch sind. Aus Dimensiongründen haben diese immer die Dimension ${\displaystyle k=n/2}$. Das wichtigste Beispiel für einen selbstdualen Code ist der erweiterte Hamming-Code, bei dem der binäre [7,4,3]-Hamming-Code um ein Paritätsbit auf gerade Parität erweitert wird:

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

Literatur

• Werner Lütkebohmert: Codierungstheorie. Algebraisch-geometrische Grundlagen und Algorithmen. Vieweg Verlag, Braunschweig u. a. 2003, ISBN 3-528-03197-2 (Vieweg-Studium – Aufbaukurs Mathematik).
• J. H. van Lint: Introduction to Coding Theory. 3. revised and expanded edition. Springer Verlag, Heidelberg u. a. 1999, ISBN 3-540-64133-5 (Graduate texts in mathematics 86).
• Florence J. MacWilliams, Neil J. Sloane: The Theory of Error-Correcting Codes. 2. Printing. North-Holland publishing company, Amsterdam 1978, ISBN 0-444-85009-0 (North Holland mathematical library 16).

Einzelnachweise

1. E. R. Berlekamp, R. J. McEliece, H. C. A. von Tilburg: On the inherent intractability of certain coding problems. In: IEEE Transactions on Information Theory 24. 1978.