12.2 Lineare Codes
Bisher haben wir noch keine lineare Algebra gesehen. Das wollen wir jetzt ändern. Nach dem vorherigen Abschnitt stellt sich die Frage, wie man geeignete Codes \(C\) findet. Dabei ist es naheliegend, die Vektorraumstruktur von \(K^n\) auszunutzen.
Wenn \(C\) ein Untervektorraum ist, können wir die minimale Hamming-Distanz berechnen, indem wir alle Vektoren mit \(0\) vergleichen:
Ist \(C\) ein linearer Code, so gilt
Für \(v, w\in K^n\) gilt \(d(v,w) = d(v-w, 0)\), wie man unmittelbar nachprüft. Weil für \(v, w\in C\) auch \(v-w\) in \(C\) liegt, folgt daraus die Behauptung.
Wir suchen dann lineare Codes, so dass \(\dim C\) und \(d(C)\) möglichst groß sind, aber dabei \(n\) möglichst klein ist.
Wie oben gesagt, wollen wir die Elemente von \(K^n\) als Zeilenvektoren betrachten.
Sei \(C\subseteq K^n\) ein linearer Code. Eine Erzeugermatrix (oder Generatormatrix) ist eine Matrix, deren Zeilen eine Basis von \(C\) bilden.
Wir sagen, eine Erzeugermatrix sei in Standardform, wenn sie eine Blockmatrix der Form \(\left( \begin{array}{cc} E_k & A \end{array} \right)\) mit \(A\in M_{k\times (n-k)}(K)\) ist.
Wenn \(G\) eine Erzeugermatrix des linearen Codes \(C\) ist, dann ist die Abbildung \(w\mapsto wG\) ein Isomorphismus \(K^k\to C\). Wenn wir die Ursprungsnachrichten als Wörter in \(K^k\) schreiben, ist die Kodierungsfunktion also einfach die durch \(G\) gegebene lineare Abbildung (im Zeilenvektor-Sinn).
Wir hatten zu Beginn den Paritätscheck-Code betrachtet, der einem Wort aus sieben Bits (Nullen und Einsen) eine achte Null oder Eins so hinzufügt, dass die Gesamtzahl der Einsen gerade ist.
Die Menge der Nachrichten ist also \(\mathbb F_2^7\), der Code \(C\) ist gegeben durch
wobei die Summe in \(\mathbb F_2\) zu bilden ist. Der Code \(C\) besitzt eine Erzeugermatrix in Standardform, und zwar
Ist \(C\) ein linearer Code, so hat \(C\) höchstens eine Erzeugermatrix in Standardform.
Für die Qualität eines Codes tut es offenbar nichts zur Sache, wenn wir eine Permutation der Standardbasisvektoren von \(K^n\) durchführen (also \(C\) durch sein Bild unter einem Automorphismus von \(K^n\) ersetzen, der durch eine Permutationsmatrix gegeben ist). Wir nennen zwei Codes, die durch eine Operation dieser Art ineinander übergehen, äquivalent. Da wir jede Matrix durch elementare Zeilenumformungen auf reduzierte Zeilenstufenform bringen können und diese den von den Zeilen aufgespannten Untervektorraum nicht verändern, ist klar, dass es zu jedem linearen Code einen äquivalenten Code gibt, der eine Erzeugermatrix in Standardform besitzt.
Sei \(C\) ein linearer \([n, k]\)-Code über \(K\). Eine Paritätsprüfmatrix ist eine Matrix \(H\in M_{(n-k)\times n}(K)\), so dass für alle \(c\in K^n\) gilt:
d.h. \(C\) ist die Lösungsmenge des durch \(Hx=0\) gegebenen linearen Gleichungssystems (wenn wir die Elemente von \(C\) zu Spaltenvektoren transponieren).
Ist \(G=(E_k \mid A)\) eine Erzeugermatrix von \(C\) in Standardform, dann ist \(H=(-A^t | E_{n-k})\) eine Paritätsprüfmatrix, denn es gilt offenbar \(HG^t = 0\), also \(\{ c^t;\ c\in C\} \subseteq \operatorname{Ker}(H)\), und \(\operatorname{rg}(H) = n-k\), so dass sogar \(\{ c^t;\ c\in C\} = \operatorname{Ker}(H)\) folgt.
Die minimale Hamming-Distanz eines Codes hat die folgende Interpretation in Termen einer Paritätsprüfmatrix:
Sei \(C\) ein linearer \([n,k]\)-Code mit minimaler Hamming-Distanz \(d(C)\). Sei \(H\) eine Paritätsprüfmatrix von \(C\), und sei \(d\) die kleinste Zahl, so dass je \(d-1\) Spalten von \(H\) stets linear unabhängig sind, aber so dass es \(d\) Spalten in \(H\) gibt, die linear abhängig sind. Dann gilt \(d=d(C)\).
Dass es \(d\) Spalten in \(H\) gibt, die linear abhängig sind, ist äquivalent dazu, dass die Lösungsmenge des linearen Gleichungssystems \(Hx=0\) einen Vektor \(x\) enthält, in dem höchstens \(d\) Einträge \(\ne 0\) sind. Aus diesem Argument und Lemma 12.7 folgt sofort die Behauptung.