Direkt zum Inhalt

Lexikon der Mathematik: linearer Code

eine Codierung, die in anderer Sichtweise eine lineare Abbildung ϕ von Vektorräumen ϕ : UV ist.

Die (n × k)-Matrix A der linearen Abbildung ϕ in der kanonischen Basis nennt man Generatormatrix des Codes. Ist die Abbildung auf den ersten k Koordinaten die Identität, dann nennt man den Code systematisch.

Jedem Code C = Im ϕV entspricht im Dualraum V der Annullator Ann(C) = {αV; α(c) = 0 für alle cC}, der als dualer Code ϕ : WV bezeichnet wird (oft wird fälschlicherweise auch das orthogonale Komplement C dualer Code genannt). Der duale Code C ist eine (n, nk)-Codierung, wenn C eine (n, k)-Codierung ist. Betrachtet man die zu ϕ duale Abbildung s : VW, so erhält man eine lineare Abbildung, deren Kern Ker s = Im ϕ genau das Bild der Codierung ϕ ist.

Die ((nkn)-Matrix der Abbildung s wird auch als Syndrommatrix bezeichnet. Das Syndrom eines Codewortes c ist das Bild s(c) bei dieser Abbildung. Für korrekt übertragene Codeworte c gilt s(c) = 0. Bei fehlerbehafteten Codeworten c = c + e gilt s(c) = s(c) + s(e) = s(e), und die Fehlerkorrektur wird mit dem Vektor e mit dem geringsten Hamminggewicht, der zum Syndrom s(c) gehört, durchgeführt.

Beispielweise ist für den systematischen (7, 5)-Hamming-Code

\begin{eqnarray}({x}_{1},{x}_{2},\ldots, {x}_{5})\to ({c}_{1},{c}_{2},\ldots, {c}_{7})\end{eqnarray}

mit c1 = x1, c2 = x2, c3 = x3, c4 = x4, c5 = x2 +x3 +x4, c6 = x1 +x3 +x4 und c7 = x1 +x2 +x4 eine Generatormatrix

\begin{eqnarray}G=\left(\begin{array}{ccccc}1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ 0 & 1 & 1 & 1 & 0\\ 1 & 0 & 1 & 1 & 0\\ 1 & 1 & 0 & 1 & 0\end{array}\right)\end{eqnarray}

und eine Kontrollmatrix

\begin{eqnarray}H=\left(\begin{array}{ccccccc}0 & 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right).\end{eqnarray}

Ist c = (1101101) ein empfangenes Codewort, so ist das Syndrom von c der Vektor (101). Wenn ein einziger Fehler aufgetreten ist, dann kann er nur im 5-ten Bit gewesen sein, denn s(e5) ist auch (101). Die erfolgreiche Korrektur ergibt das Codewort (1101001). Bei zwei Fehlern kann c aber auch aus dem Codewort (1001100) entstanden sein (zweites und siebtes Bit verfälscht), der Code kann diesen schweren Doppelfehler nicht mehr korrigieren.

Lineare Codes haben wegen ihrer algebraischen Struktur gute fehlerkorrigierende Eigenschaften. So ist der minimale Hamming-Abstand eines linearen Codes gleich d, wenn die Dimension des von den Spaltenvektoren der Kontrollmatrix erzeugten Unterraumes d − 1 ist.

Die wichtigsten linearen Codes sind die Reed-Muller-Codes und die zyklischen Codes.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos