Toggellichter

Wie kann eine CD immer noch ausgelesen werden, auch wenn einige Kratzer ihre Rückseite zieren? Wie kann ein Rover, der auf dem Mond Untersuchungen vornehmen soll, seine Daten an die Basisstation auf der Erde übermitteln, auch wenn sicher einige Fehler bei der Übermittlung auftreten? Wie kann ich meine Daten auf drei Festplatten effizient abspeichern, sodass, wenn eine dieser Festplatten ausfällt, immer noch alle Daten rekonstruiert werden können?

Mit diesen und ähnlichen Fragen beschäftigt sich die Codierungstheorie. Die grundlegende Idee dabei ist die folgende: Gegeben ist ein endliches Alphabet $F$ (z.B. $F=\{0,1\}$ im binären Fall) und eine Codelänge $n$ . Die zu codierenden Daten werden nun immer in Blöcken der Länge $n$ abgespeichert/übermittelt. Ein solcher Block $b$ enthält aber tatsächlich nur die Information von einer kleineren Zahl $k\leq n$ an $F$ -bits. Das heißt, bei der Codierung wird immer je ein Wort der Länge $k$ über dem Alphabet $F$ in ein Wort der Länge $n$ über demselben Alphabet umgewandelt. Dabei sind $l\coloneqq n-k$ $F$ -Bits redundant. Mathematisch gesprochen ist diese Codierung nichts anderes als eine injektive Abbildung $\iota\colon F^k\to F^n$ . Ihr Bild $C\coloneqq\mathrm{im}(\iota)$ wird als ein $(n,k)$ –Code bezeichnet ( $n$ heißt die Länge von $C$ und $k$ die Dimension).

Nun kann folgendes passieren: In dem Block $b$ der Länge $n$ werden einige Symbole (durch Rauschen im Kanal oder Ähnliches) verändert. Sagen wir dies seien $m$ Symbole. Somit entsteht ein neuer gestörter Block $b'$ . Kann die ursprüngliche Information noch rekonstruiert werden? Dazu definieren wir den Hamming-Abstand zweier Codewörter $c,d\in C$ als $d_{\mathrm H}(c,d)=|\{i\in\{1,\ldots,n\}\,|\,c_i\neq d_i\}|$ (hierbei ist $c=(c_1,\ldots,c_n)$ und $d=(d_1,\ldots,d_n)$ mit $c_i,d_i\in F$ ). Die Idee ist nun, den gestörten Block $b'$ zu demjenigen Codewort in $C$ abzuändern, das im Hamming-Abstand gemessen am nächsten an diesem Block dran liegt. Aber ist dieses Codewort überhaupt eindeutig? Im Allgemeinen nicht!

Um „zu stark gestörte“ Blöcke $b'$ als solche zu erkennen und rekonstruierbare Blöcke immer eindeutig rekonstruieren zu können, wird daher um jedes zulässige Codewort $c\in C$ ein Ball $B_r(c)\coloneqq\{d\in C\,|\, d_{\mathrm H}(c,d)\leq r\}$ vom Radius $r$ im Hamming-Abstand gezogen, sodass sich keine zwei dieser Bälle überschneiden: $B_r(c)\cap B_r(d)=\emptyset$ für $c,d\in C$ verschieden. Liegt nun $b'$ in einem dieser Bälle, so wird es zu dem Codewort $b=c$ rekonstruiert. Auf diese Weise ist $b$ aufgrund der obigen Bedingung immer eindeutig.

Aber wie ist hierbei der Radius $r$ zu wählen? Wir wollen, dass sich $B_r(c)$ und $B_r(d)$ für $c\neq d$ aus $C$ nicht schneiden. Dies ist aber genau dann richtig, wenn $r\lt d_{\mathrm{H}}(c,d)/2$ . Diese Bedingung muss nun für alle $c$ und $d$ erfüllt sein. Setzen wir also $d(C)\coloneqq\min\{d_{\mathrm{H}}(c,d)\,|\,c,d\in C,\, c\neq d\}$ (der Minimalabstand von $C$ ), so ist $r\coloneqq\left\lfloor\frac{d(C)-1}{2}\right\rfloor$ der bestmögliche Radius. Der Parameter $d\coloneqq d(C)$ bestimmt also den Korrekturradius. In dieser Situation nennt man $C$ auch einen $(n,k,d)$ -Code.

Hamming-Codes

Die Hamming-Codes sind von dem Mathematiker Richard Wesley Hamming entwickelte binäre lineare Codes $C$ der Länge $n=2^l-1$ , der Dimension $k=n-l$ und mit dem Minimalabstand $d=3$ (hierbei ist $l\geq 2$ ein zu wählender Parameter, der genau die Redundanz des Codes misst). Das Wort linear bedeutet hier, dass unser Alphabet $F$ hier ein Körper, nämlich der Körper $\mathrm{GF}(2)$ mit zwei Elementen $0$ und $1$ ist ( $\mathrm{GF}(2)$ steht für Galois field nach dem Mathematiker Évariste Galois), und $C\subseteq\mathrm{GF}(2)^n$ ein linearer Teilraum des Vektorraums $V=\mathrm{GF}(2)^n$ ist. Ein solcher linearer Code lässt sich prinzipiell auf zwei Arten darstellen: 1.) über eine sogenannte Generatormatrix $G\in F^{k\times n}$ ; oder 2.) über eine Kontrollmatrix $H\in F^{n\times(n-k)}$ . Eine Generatormatrix ist einfach eine Matrix, die die obige Codierungsabbildung $\iota$ in Koordinaten beschreibt. Eine Kontrollmatrix $H$ von $C$ hingegen ist eine Matrix, deren Kern genau der Code $C$ ist, d.h. um zu überprüfen, ob ein Block $b\in F^n$ dem Code $C$ angehört, berechnet man einfach den liegenden Vektor $bH$ (wir benutzen im Folgenden immer kovariante Notation) und überprüft alle $l=n-k$ Stellen, ob diese gleich null sind, und $bH$ somit der Nullvektor ist. Die Hamming-Codes lassen sich am einfachsten über ihre Kontrollmatrix beschreiben. Wähle nämlich $H\in\mathrm{GF}(2)^{(2^l-1)\times l}$ so, dass ihre Zeilen genau alle Vektoren des $l$ -dimensionalen Vektorraums $\mathrm{GF}(2)^l$ außer dem Nullvektor sind (das sind nämlich genau $n=2^l-1$ viele). Somit ist $H$ eine $(2^l-1)\times l$ -Matrix, wie gewünscht. Der $(n=2^l-1,k=n-l)$ -Hamming-Code hat also genau $l$ Bits Redundanz, denn man muss genau $l$ Paritätstests durchführen. Die tatsächlich codierte Information hat also eine Länge von $2^l-1-l$ Bits (was für große $l$ deutlich größer als die Redundanz ist). Wir wollen uns nun noch überlegen, wie viele Fehler ein Hamming-Code korrigieren kann. Dazu nehmen wir an, dass $c,d\in C$ unterschiedliche Codewörter sind, die minimalen Hamming-Abstand voneinander haben. Durch verschieben (da dies den Hamming-Abstand gleich lässt, dürfen wir das) können wir annehmen, dass $d=0$ der Nullvektor ist (der, da $C$ ein linearer Code ist, ja immer in $C$ enthalten ist). Es gibt sicher drei Vektoren $u,v,w\in\mathrm{GF}(2)^l\setminus\{0\}$ , die linear abhängig sind, d.h. $u+v+w=0$ . Sind $i,j,k\in\{1,\ldots,2^l-1\}$ die zugehörigen Indizes, sodass $u,v,w$ die $i$ -te, $j$ -te, und $k$ -te Spalte der Kontrollmatrix sind, so erfüllt der Vektor $c=(c_1,\ldots,c_{2^l-1})$ mit $c_m=0$ falls $m\neq i,j,k$ und $c_i=c_j=c_k=1$ sicher die obige Kontrollbedingung $cH=0$ , denn $cH$ ist dann genau $u+v+w$ , was ja nach Annahme null war. Damit ist gezeigt, dass der Minimalabstand (oder, wie dieser für lineare Codes auch genannt wird: das Minimalgewicht) $d=d(C)$ höchstens drei sein kann. Hat der Vektor $c$ aber weniger als drei Einsen als Einträge, dann kann er die Kontrollbedingung nicht erfüllen, denn je zwei Spalten der Kontrollmatrix kombinieren sich nicht zu null (sie sind linear unabhängig). Damit ist $d(C)=3$ . Daraus sehen wir, dass ein Hamming-Code immer nur einen einzigen Fehler korrigieren kann. Dies mag zunächst ein bisschen unbefriedigend erscheinen. Der große Vorteil, den Hamming-Codes jedoch haben, ist, dass sie sich sehr elegant implementieren lassen. Dazu kannst Du Dir gerne dieses Video des YouTubers 3Blue1Brown anschauen.

Nun aber zum Exponat „Hammingcode“: Hier wird derjenige Hamming-Code dargestellt, für den $l=3$ und demnach $n=2^l-1=7$ und $k=n-l=4$ ; also der sogenannte $(7,4)$ -Hamming-Code. Daher gibt es $n=7$ Lampen und $k=4$ Knöpfe. Du kannst hier einmal selbst probieren, welche Konstellationen an brennenden Lampen sich einstellen lassen und welche nicht. Was auffällig ist, ist das — wenn mindestens eine Lampe brennt — dann schon immer mindestens drei Lampen brennen. Das spiegelt genau den oben erläuterten Sachverhalt wieder, dass das Minimalgewicht eines jeden Hamming-Codes genau $d=3$ ist. Auch lässt sich anhand des Exponats gut üben, was eine Kontrollmatrix und eine Generatormatrix ist. Die Generatormatrix lässt sich zum Beispiel einfach aufstellen, indem man die Basiskonstellationen (also wenn nur genau ein einziger Knopf gedrückt ist) als Zeilenvektoren in eine $4\times 7$ -Matrix schreibt. Gelingt es Dir auch, drei Kontrollbedingungen zu finden, mit denen man überprüfen kann, ob ein Konstellation an brennenden Lämpchen zulässig ist? Dies scheint zunächst deutlich schwerer zu sein. Würdest Du Deine gefundenen drei Bedingungen in eine Matrix schreiben, so erhältst Du die gesuchte Kontrollmatrix $H$ der Dimension $7\times 3$ .

$\mathbf{GF(2)^5}$

Auch dieses Exponat stellt einen linearen Code dar. Du siehst neun Lämpchen. Wenn Du jede einzelne dieser Lampen ein- und ausschalten könntest, gäbe es damnach $2^9$ Möglichkeiten. Codiert man den Zustand, dass eine Lampe brennt mit $1$ , und den Zustand, dass sie nicht brennt, mit $0$ , so entspricht jede dieser Möglichkeiten genau einem Element aus dem $9$ -dimensionalen Vektorraum $V=\mathrm{GF}(2)^9$ über dem Körper $\mathrm{GF}(2)$ mit den zwei Elementen $0$ und $1$ . Nun kannst Du aber nicht jede Lampe einzeln ansteuern. Dafür lassen sich nur die Lampen einer Zeile bzw. Spalte der in einem Quadrat aus $3\times 3$ Gitterpunkten angeordneten Lampen alle gleichzeitig umschalten. Damit kann es höchstens $2\cdot2\cdot2\cdot2\cdot2\cdot2=2^6$ mögliche Konstellationen geben (für jede Spalte und Zeile ein Faktor $2$ ). Es stellt sich aber heraus, dass sich jede mögliche Konstellation auf genau zwei Arten einstellen lässt: Drückt man nämlich alle sechs Knöpfe (also die der drei Zeilen und der drei Spalten), so erhält man dieselbe Konstellation wie zuvor. Der Raum der möglichen Konstellelationen bildet nun einen linearen Code der Länge $n=9$ (denn es sind neun Lampen) und der Dimension $5$ (denn es sind, wie eben erläutert, $2^5$ Möglichkeiten). Dieser Code wird als Vektorraum erzeugt von den Basiskonstellationen also von jenen Konstellationen, bei denen genau die Lampen einer Zeile bzw. Spalte brennen (wobei eine davon überflüssig ist). Hieran lässt sich nun wiederum gut der Begriff der Generatormatrix erläutern. Die Zeilen dieser Matrix sind nämlich genau die Basiskonstellationen, aus denen alle anderen kombiniert werden können:

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

Die letzte Spalte benötigen wir hier nicht als Basiskonstellation, da sie ja aus den anderen zusammengesetzt werden kann.

Wie sieht nun aber eine geeignete Kontrollmatrix $H$ für den hier vorliegenden $5$ -dimensionalen Code aus? Gesucht sind also $4=n-k=9-5$ lineare Kontrollbedingung, die sicherstellen, dass wir es mit einer zulässigen Konstellation zu tun haben. Dazu macht man folgende Beobachtung: Wähle eine der vier Ecken des Quadrates aus. Betrachte nun diejenigen vier Lampen, die am nächsten an dieser Ecke liege (sie bilden ein $2\times 2$ Quadrat). Es ist zu beobachten, dass bei allen Konstellationen, die Du einstellen kannst, immer eine gerade Anzahl dieser vier Lampen brennt. Aber lässt sich dies auch beweisen? Ja! sogar sehr einfach. Für die Basiskonstellationen (also, wenn nur eine Zeile bzw. Spalte von Lampen brennt) brennen nämlich immer entweder null oder zwei dieser vier Lampen (also eine gerade Anzahl). Kombiniert man nun Basiskonstellationen zusammen, so muss diese Eigenschaft erhalten bleiben, da beim Drücken eines Knopfes ja immer entweder null oder zwei der vier Lampen umgeschaltet werden. Wir erhalten also auf diese Weise vier Kontrollbedingungen (für jede Ecke eine), die erfüllt sein müssen, damit eine Konstellation von brennenden Lampen auch wirklich eingestellt werden kann. Das ist genau die richtige Anzahl (siehe oben). Aber sind diese vier Bedingungen auch unabhängig voneinander? Die Antwort ist wiederum: Ja! Um dies einzusehen, schreiben wir die genannten vier Bedingung wieder in eine Matrix $H\in\mathrm{GF}(2)^{9\times 4}$ :

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

Die vier Spalten dieser (Kontroll-)Matrix $H$ sind nun linear unabängig, denn die erste, dritte, siebte, und neunte Zeile bilden eine Permutationsmatrix (die regulär ist). Dies ist der Tatsache geschuldet, dass jede der vier Eckenlampen in genau einer der vier Kontrollbedingungen auftritt.

Eine letzte Aufgabe: Gelingt es Dir auch fünf Lampen zu finden, die den Zustand aller anderer Lampen eindeutig bestimmen (man nennt dies Interpolation)?

Literatur

[1] https://de.wikipedia.org/wiki/Linearer_Code

[2] https://de.wikipedia.org/wiki/Hamming-Code

[3] https://de.wikipedia.org/wiki/Generatormatrix

[4] https://de.wikipedia.org/wiki/Endlicher_Körper

[5] https://de.wikipedia.org/wiki/Lineare_Unabhängigkeit