Linearer Code

Linearer Code

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

Lineare 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, Reed-Solomon-Codes, Golay-Codes und Goppa-Codes).

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

Inhaltsverzeichnis

Eigenschaften

Da C ein Untervektorraum von V ist, existiert eine Basis g_1, \dots, g_k von C. Fasst man diese Basis in einer Matrix

 G=\begin{pmatrix}
g_1 \\
\vdots\\
g_k
\end{pmatrix}

zusammen, erhält man eine Erzeugermatrix. Des Weiteren besitzt der Code eine Kontrollmatrix H. Für sie gilt HcT = 0 genau dann, wenn c ein Codewort ist. Der Rang von G ist k, der von H ist nk. Der Hammingabstand von C ist die minimale Anzahl linear abhängiger Spalten der Kontrollmatrix.

Das Hamminggewicht eines Codewortes c=(c_1,\dots,c_n) ist gleich der Anzahl der ci, die von Null verschieden sind. Beispielsweise hat das Codewort (430540) über \mathbb{F}_7^6 das Hamminggewicht 4. Der Hammingabstand des Codes ist gleich dem kleinsten Hamminggewicht 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 G=(\mathbb{E}_k|P) hat. Dabei ist \mathbb{E}_k die (k \times k)-Einheitsmatrix, und P ist eine (k \times (n-k))-Matrix. Dann heißt G Erzeugermatrix in reduzierter Form. Die ersten k Koordinaten können als Informationssymbole und die letzten nk 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 binäre [7,4,3]-Hammingcode besitzt folgende Erzeugermatrix in reduzierter Form sowie die dazugehörige Kontrollmatrix:

G=(\mathbb{E}_k|P)     H=(-P^T|\mathbb{E}_{n-k})

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     
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}

Codierung

Ein Wort x=(x_1, \dots, x_k) aus dem Raum \mathbb{F}_q^k wird codiert, indem das Produkt xG gebildet wird. Die Codierung des Wortes (0,0,1,1) mit dem [7,4,3]-Hammingcode veranschaulicht beispielsweise die folgende Rechnung.

\begin{align}
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{align}

Da hier die Addition in \mathbb{F}_2 erfolgt, gilt 1 + 1 = 0

Decodierung

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

Als Decodierungsmethode wird in der Codierungstheorie meistens die Methode der größten Wahrscheinlichkeit (englisch: maximum likelihood decoding) verwendet. Dabei wird ein empfangener Vektor x zu dem Codevektor c' decodiert, der mit der größten Wahrscheinlichkeit zum tatsächlich versandten Codevektor 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 c' mit dem geringsten Hammingabstand zum empfangenen Vektor 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 c der tatsächlich versendete (Code-)Vektor und x der empfangene Vektor. Die Decodierung sucht aus allen qn Codevektoren den oder die Codevektoren c', die mit der größten Wahrscheinlichkeit versendet wurden.

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

Bei der Nearest-Neighbor-Dekodierung also:

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

Man sollte dabei beachten, dass diese Zuordnung bei den meisten Codes nicht für alle Fehlervektoren eindeutig ist. Es gibt dann einige Fehlervektoren, die nicht zugeordnet werden können, da sie mehr als einen nächstgelegenen Nachbarn haben.

Syndromdecodierung

Eine effizientere Methode für die Decodierung stellt die sogenannte Syndrom-Decodierung dar. Das Syndrom sx eines Vektors x erhält man durch Multiplikation der Kontrollmatrix H mit xT.

s_x^T = H x^T

Es sei e = xc der Fehlervektor von x. In e sind genau die Koordinaten ungleich Null, bei denen während der Übertragung Fehler aufgetreten sind.

Für das Syndrom von x gilt wegen der Linearität des Codes:

s_x^T = H x^T = H c^T + H e^T

Da das Syndrom von fehlerfreien Codevektoren immer Null ist, folgt:

s_x^T = H e^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 s_e^T=H e^T konstant.

Alle Vektoren, die aus einem beliebigen, festen Vektor durch Subtraktion eines beliebigen Codevektors hervorgegangen sind, bilden eine Nebenklasse der Untergruppe C von \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 x zu c' zu decodieren, sucht man also den Fehlervektor e', dessen Syndrom identisch zum Syndrom von x ist und dessen Hamminggewicht minimal ist. Mit diesem Fehlervektor berechnet man c' = xe' den nächstgelegenen Codevektor c'.

Man kann also eine Tabelle mit bis zu qnk Zeilen aufstellen, die für jedes Syndrom eines empfangenen Vektors den entsprechenden Fehlervektor mit minimalem Hamminggewicht beinhaltet. Ist das Syndrom gleich 0, dann muss nichts korrigiert werden ansonsten beschränkt sich Decodierung auf das Nachschlagen des Fehlervektors in dieser Tabelle und Korrigieren der so detektierten Fehler.

Die Decodierung 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 Decodierungs-Algorithmen bekannt sind. Die Komplexität der linearen Decodierung 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 [7,4,3]-Hammingcode (von oben) 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 e sind dann

(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 sT = HeT berechnet. Damit ergibt sich

e s
(1,0,0,0,0,0,0) (1,1,0)
(0,1,0,0,0,0,0) (1,0,1)
(0,0,1,0,0,0,0) (1,1,1)
(0,0,0,1,0,0,0) (0,1,1)
(0,0,0,0,1,0,0) (1,0,0)
(0,0,0,0,0,1,0) (0,1,0)
(0,0,0,0,0,0,1) (0,0,1)

Wird dann das fehlerhafte Wort x = (0,1,1,1,1,0,0) empfangen, ergibt dann sT = HxT = (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).

Beispiel mit unvollständiger Decodierung

Gegeben sei der ternäre (q = 3) Wiederholungscode der Länge 3:


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

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

e s
(1,0,0) (2,2)
(2,0,0) (1,1)
(0,1,0) (1,0)
(0,2,0) (2,0)
(0,0,1) (0,1)
(0,0,2) (0,2)

Durch Ausnützen von Linearitäten könnte die Anzahl der Zeilen halbiert werden, man muss dann aber testen, ob ein linear abhängiges Syndrom in der Tabelle ist.

Man betrachte nun x = (1,1,0), y = (1,2,0). Bei x ist das Syndrom Hxt = (0,2)t, die Korrektur lautet: (1,1,0) − (0,0,2) = (1,1,1). Die Berechnung des Syndroms von y ergibt: Hyt = (1,2)t. Dieser Wert ist nicht in der Syndromtabelle enthalten, das Wort kann also nicht korrigiert werden.

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.

Dualer Code

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

Man definiert hierzu ein inneres Produkt:

\langle \cdot ; \cdot \rangle \,: \; \mathbb{F}_q^n \times \mathbb{F}_q^n \to \mathbb{F}_q

das die Vektoren x=(x_1,x_2,\dots,x_n),y=(y_1,y_2,\dots, y_n) folgendermaßen abbildet:

\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 (1,1).

Mit Hilfe dieser Definition ergibt sich der Duale Code als:

C^\perp = \{x \in \mathbb{F}_q^n \mid \langle x,c\rangle = 0\; \mathrm{f\ddot ur\; alle} \; c \in C \}

Eine Erzeugermatrix des dualen Codes ist eine Kontrollmatrix des Ursprungscodes und umgekehrt.

Der duale Code spielt bei der Analyse der Eigenschaften von Codes eine 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 k = n / 2. Das wichtigste Beispiel für einen selbstdualen Code ist der erweiterte Hammingcode, bei dem der binäre [7,4,3]-Hammingcode um ein Paritätsbit auf gerade Parität erweitert wird:


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}

Quellen

  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.

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).

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Code-book Excited Linear Prediction — Code( book) Excited Linear Prediction (CELP) ist ein hybrides Audiokompressionsverfahren, das die Vorteile der Signalformkodierung mittels Vektorquantisierung und der parametrischen Verfahren vereint. Das Ergebnis ist eine gute Sprachqualität,… …   Deutsch Wikipedia

  • Code Excited Linear Prediction — Code( book) Excited Linear Prediction (CELP) ist ein hybrides Audiokompressionsverfahren, das die Vorteile der Signalformkodierung mittels Vektorquantisierung und der parametrischen Verfahren vereint. Das Ergebnis ist eine gute Sprachqualität,… …   Deutsch Wikipedia

  • Code Coverage — Die kontrollflussorientierten Testverfahren, auch Überdeckungstests genannt, gehören zu der Gruppe der strukturorientierten Testmethoden. Die kontrollflussorientierten Testverfahren orientieren sich am Kontrollflussgraphen des Programms. Es… …   Deutsch Wikipedia

  • Code-Excited Linear Prediction — Prinzipaufbau des CELP Decoders Code( book) Excited Linear Prediction (CELP) ist ein hybrides Verfahren zur Audiodatenkompression, das die Vorteile der Signalformkodierung mittels Vektorquantisierung und der parametrischen Verfahren vereint. Das… …   Deutsch Wikipedia

  • Golay-Code — Die Bezeichnung Golay Code steht für zwei eng verwandte Codes, welche eine herausragende Stellung in der Codierungstheorie einnehmen. Sie sind (abgesehen von trivialen Codes und Wiederholungs Codes) bis auf Isomorphie die einzigen beiden… …   Deutsch Wikipedia

  • Perfekter Code — Ein perfekter Code, oder auch dicht gepackter Code, bezeichnet in der Codierungstheorie einen Blockcode , bei dem jedes Wort nur zu genau einem Codewort eine minimale Hamming Distanz hat. Bei der für gewöhnlich verwendeten Maximum Likelihood… …   Deutsch Wikipedia

  • Block-Code — systematischer Blockcode Ein Blockcode ist eine Art von Kanalkodierung, gekennzeichnet dadurch, dass die benutzten Codewörter alle dieselbe Anzahl an Symbolen aus einem Alphabet (Informatik), z. B. Bits haben. Obwohl Blockcodes häufig nicht… …   Deutsch Wikipedia

  • Zyklischer Code — Ein zyklischer Code ist ein in der digitalen Signalverarbeitung und der Nachrichtentechnik eingesetzter Kanalcode. Zyklische Codes sind Teil der Gruppe der linearen Codes und werden unter anderem zur Vorwärtsfehlerkorrektur auf… …   Deutsch Wikipedia

  • Hadamard-Code — Matrix des [32,6,16] Hadamard Codes der NASA Raumsonde Mariner 9 (1971/1972). Die Farbe Schwarz kodiert die Binärziffer 1, und die Farbe Weiß kodiert die Binärziffer 0 …   Deutsch Wikipedia

  • Hamming-Code — Der Hamming Code ist ein von Richard Hamming entwickelter linearer fehlerkorrigierender Blockcode, der in der digitalen Signalverarbeitung und der Nachrichtentechnik zur gesicherten Datenübertragung oder Datenspeicherung verwendet wird. Beim… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”