Einführung

Sei $K$ eine endliche Menge mit $q=|K|$ Elementen. Eine Teilmenge $C\neq\emptyset$ von $K^n=\{(u_1,\ldots,u_n)\,|\,u_i\in K\}$ heisst ein Blockcode, kurz auch Code über dem Alphabet $K$. Die Elemente von $C$ nennen wir Codeworte und $n$ heisst die Länge von $C$. Für $q=2$ (bzw. $q=3$) nennen wir $C$ auch einen binären (bzw. ternären) Code.

Es kommt beim Alphabet $K$ nur auf die Mächtigkeit an, $|K|=q$. Daher werden wir meist $K=\{0,1,\ldots,q-1\}$ setzen, sodass $K$, indem wir nun $i\in K$ mit der Restklasse $i+q\cdot\mathbb{Z}\in\mathbb{Z}_q$ identifizieren. Ein binärer Code wird dem entsprechend stets ein Code über dem Körper $\mathbb{F}_2=\mathbb{Z}_2$ sein.

Der Computer verknüpft die Bits 0 und 1 genau nach den Rechenregeln im Körper $K=\mathbb{F}_2$, also $0+0=0$, $0+1=1$, $1+0=1$, $1+1=0$.

Seien $K$ ein Alphabet und $u=(u_1,\ldots,u_n)$, $v=(v_1,\ldots,v_n)$ Elemente in $K^n$. Dann heisst

\[ d(u,v):=|\{i\,|\,u_i\neq v_i\}| \] der Hamming-Abstand von $u$ und $v$. Dieser Abstand definiert auf $K^n$ eine Metrik, d.h. es gilt $\forall u,v,w\in K$

$d(u,v)\geq 0 \quad\text{ und }\quad d(u,v)=0\Leftrightarrow u=v$
$d(u,v)=d(v,u)$
$d(u,v)\leq d(u,w)+d(w,v)$

Dazu gilt die Translationsinvarianz: $d(u+w,v+w)=d(u,v)$.

Betrachten wir nun den Übertragungskanal. Wir nahmen an, die Wahrscheinlichkeit der korrekten übertragung eines Symbols aus einem Alphabet der Mächtigkeit $|K|=q$ ist stets grösser als der reiner Zufall, d.h. $1-p>1/q$, wobei $p$ die Wahrscheinlichkeit ist, dass ein Symbol falsch übertragen wird. Wir haben

\[ 1-p>\frac{1}{q}\Leftrightarrow p<\frac{q-1}{q}. \]

Dazu nehmen wir an, dass bei der falschen Übertragung eines Symbols, alle $q-1$ möglichen Fehler gleichwahrscheinlich sind. Wenn unser Kanal diese zwei Bedingungen erfüllt, nennen wir ihn $q$-när symmetrisch. Wenn $q=2$, binär-symmetrisch. Und $p$ heisst Symbolfehlerwahrscheinlichkeit des Kanals.

Die ML-Decodierung (Maximum Likelihood)

Sei $P(v|c)$ die bedingte Wahrscheinlichkeit, dass $v\in K^n$ empfangen wird, falls $c\in K^n$ gesendet wurde. Diese Decodierungs-Methode decodiert einen Vektor $v$ zu einem Codewort $c\in C$, für welches gilt

\[ P(v|c)=\max_{c'\ C}P(v|c'). \]

Das von der Methode gewählte Wort $c$ ist also dasjenige, welches die bedingte Wahrscheinlichkeit über alle Worte des “Dictionary” $C$ maximisiert.

Wenn der Kanal $q$-när symmetrisch ist, gilt dann

\[ P(v|c')=(\frac{p}{q-1})^a\cdot(1-p)^{n-a}, \]

wobei $a:=d(v,c')$ der Hamming-Abstand ist und $\frac{p}{q-1}$ aus

\[ p<\frac{q-1}{q}\quad\Leftrightarrow\quad q<\frac{q-1}{p}\quad\Leftrightarrow\quad \frac{1}{q}>\frac{p}{q-1} \]

kommt.

Erklärung: Wenn das gesendete Wort $c'$ ist, und das Wort, welches empfangen wurde $v$ ist, und wenn $d(c',v)=a$, d.h. beide Wörter unterscheiden sich an genau $a$ stellen, dann gilt die obige Formel.

Die Bedingung $p<\frac{q-1}{q}$ liefert $\frac{p}{(q-1)(1-p)}<1$. Somit ist die Funktion

\[ f(a)=\left(\frac{p}{q-1}\right)^a\cdot(1-p)^{n-a}=\left(\frac{p}{(q-1)(1-p)}\right)^a\cdot(1-p)^n \]

mit wachsendem $a$ monoton fallend. Also gilt

\[ P(v|c)=\max_{c'\in C}P(v|c') \]

genau für diejenigen Worte $c\in C$, für die

\[ d(v,c)=\min_{c'\in C}d(v|c') \]

ist.

Im Fall von $q$-när-symmetrischen Kanälen verlangt die ML-Decodierung also eine Decodierung zum nächstgelegenen Codewort.

Bei gegebenem $v$ soll $P(c|v)$ maximiert werden. Wir sehen es im Falle, dass alle Codeworte mit der gleichen Wahrscheinlichkeit benutzt werden:

\[ P(v|c)=\frac{P(v,c)}{P(c)}=\frac{P(v,c)\cdot P(v)}{P(v)\cdot P(c)}=P(c|v)\cdot P(v)\cdot\frac{1}{P(c)}, \]

wo $\frac{1}{P(c)}=\frac{1}{|C|}$ wegen der gleichverteilung der Benutzung der Codeworte. In diesem Fall wird also das Maximum $P(c|v)$ in den gleichen Codeworten $c\in C$ wie für $P(v|c)$ angenommen.

Was ist ein guter Code?

Wir möchten bestimmen können, was ein guter Code ist und was nicht denn es geht bei der Codierungstheorie grundsätzlich um Optimierung. Dazu sollen wir die Merkmale eines Code bestimmen.

Der Abstand zwischen je zwei Codeworten ist sicher wichtig, denn je grösser er ist, desto eindeutiger die Decodierung aber auch desto weniger Codeworte ein gegebener Code $C\subset K^n$ hat ($n$ festgelegt), d.h. desto kleiner die Code-Dichte in $K^n$ ist. Wenn diese Dichte zu klein ist, weil der Abstand zwischen je zwei Codeworten gross ist, muss man einen höheren $n$ wählen, als vielleicht nötig wäre. Algorithmisch kann dies ein Problem sein. Daher die folgende Definition:

Defin.: Sei $C$ ein Code der Länge $n$ über dem Alphabet $K$. - Ist $|C|>1$, so nennen wir

\[ d(C):=\min\{d(c,c')\,|\,c,c'\in C, c\neq c'\} \]

die Minimaldistanz von $C$. Für $|C|=1$ setzen wir $d(C)=0$. - Ist $d(C)=d$ und $M=|C|$, so sagen wir, dass $C$ ein $(n,M,d)$-Code über $K$ ist. Wir nennen $(n,M,d)$ die Parameter von $C$.

Wie in Euklidischen Räumen können wir über den Hamming-Abstand Kugeln definieren.

Seien $K$ ein Alphabet und $r\in \mathbb{N}_0$. Für $u\in K^n$ definiert

\[ B_r(u):=\{v\,|\,v\in K^n, d(u,v)\leq r\} \]

die Kugel von Radius $r$ um den Mittelpunkt $u$ in $K^n$. Ist $|K|=q$, so gilt

\[ |B_r(u)|=\sum_{j=0}^r \binom n j \cdot (q-1)^j\,, \]

denn

\[ |\{v\,|\,v\in K^n, d(u,v)=j\}|=\binom n j \cdot (q-1)^j \quad\text{(hängt nicht von }u\text{ ab)} \]

Mittels diesen Definitionen lassen sich nun Aussagen über die Güte der ML-Decodierung machen.

Sei $d$ die Minimaldistanz von $C\subset K^n$ mit $d\geq 2 e+1$. Angenommen, im Kanal passieren höchstens $e$ Fehler, d.h. wird $c\in C$ gesendet, so wird ein $c\in B_e(c)$ empfangen. Für $c\neq c'\in C$ sichert die Bedingung $d\geq 2 e+1$, dass $B_e(c)\cap B_e(c')\neq\emptyset$, dass also die Kugeln rund um die Codeworte paarweise disjunkt sind. Somit ist $c$ das zu $v$ nächstgelegene Codewort und der ML-Decodierer liefert in der Tat das gesuchte Wort.

Es treten also bei $e\leq\frac{d-1}{2}$ keine Decodierfehler auf.

Liegt das empfangene Wort $v$ in der 2 Mal grösseren Kugel $B_{d-1}(c)$, mit $v\neq c$, so wiss der Decodierer, dass Fehler bei der Übertragung passiert sind, denn die Kugel $B_{d-1}(c)$ enthält nur $c$ als Codewort. Dementstrechend definieren wir:

Sei $C$ ein Code.

$C$ heisst $t$-fehlererkennend, falls $\forall c\in C$, die Kugel $B_t(c)$ ausser $c$ kein weiteres Codewort enthält.
$C$ heisst $t$-fehlererkorrigierend, falls $B_e(c)\cap B_e(c')=\emptyset\quad\forall c\neq c', \quad c,c'\in C$.

Hat der Code $C\neq\{0\}$ die Minimaldistanz $d$, so können wir bis zu $d-1$ fehler erkennen und bis zu $\left\lfloor \frac{d-1}{2} \right\rfloor$ Fehler korrigieren.

Beispiele

Wiederholungscodes: $C=\{(k,k,\ldots,k)\,|\,k\in K\}\subset K^n$ heisst Wiederholungscode der Länge $n$ über $K$. Für $|C|>1$ ist $d(C)=n$ und $C$ kann bis zu $\left\lfloor \frac{n-1}{2} \right\rfloor$ Fehler korrigieren. Für diese gute Fehlerkorrektur haben wir auch einen hohen Preis zu zahlen, denn von den $n$ übertragenen Zeichen trägt nur ein Zeichen die eigentliche Information.

Kontrollcodes: Das Alphabet $K$ sei nun eine Abelsche Gruppe und für $i=1,\ldots,n$ seien $\pi_i$ Permutationen auf $K$, also bijektive Abbildungen $K\rightarrow K$. Ferner sei $a$ ein beliebiges Element von $K$. Dann heisst

\[ C=\{(c_1,\ldots,c_n)\,|\,c_i\in K,\, \sum_{i=1}^n\pi_i(c_i)=a\} \]

ein Kontrollcode und und $\sum_{i=1}^n\pi_i(c_i)=a$ die Kontrollgleichung. Der Code $C$ ist 1-fehlererkennend, da sich $c_i$ eindeutig aus $\pi_i(c_i)=a-\sum_{j=1 \\ j\neq i}^n \pi_j(c_j)$ be-rechnen lässt.

Der Paritätscheck-Code: Dieser Code ist gegeben durch: \[ C=\{(c_1,\ldots,c_n)\,|\,c_i\in K,\, \sum_{i=1}^nc_i=0\} \]

Erkennung einer ungeraden Anzahl von Fehlern bei der Übertragung.

Die ISBN-Codes: Für die Bücher. Beispiel:

\[ \underbrace{0}_{\text{Sprachregion}} - \underbrace{387}_{\text{Verlag}} - \underbrace{96617}_{\text{Buchnummer}} - X \]

$X$ wird aus den 9 ersten Ziffern berechnet.

Perfekte Codes

Sei $C$ ein Code der Länge $n$ über $K$. Wir nennen $C$ perfekt, falls ein $e\in\mathbb{N}_0$ existiert, so dass

\[ K^n=\bigcup_{c\in C} B_e(c)\qquad\text{(Disjunkte Vereinigung)} \]

Behauptung: Sei $C$ ein Code der Länge $n$ über $K$, mit $|K|=q$. Ferner gelte $d(C)\geq 2e+1$ mit $e\in\mathbb{N}_0$.

Hamming-Schranke: Es gilt \[ q^n\geq |C|\cdot\sum_{j=0}^e\binom n j\cdot(q-1)^j. \]
Genau dann ist $C$ perfekt, wenn die sogenannte Kugelpackungsgleichung

\[ q^n=|C|\cdot\sum_{j=0}^e\binom n j\cdot(q-1)^j. \]

erfüllt ist.

Beweis: Wir zeigen nur a), weil b) trivial ist.

Wir haben, dass $B_e(c)\cap B_e(c')=\emptyset\quad\forall c\neq c', \quad c,c'\in C$. Somit erhalten wir

\[ \begin{eqnarray*} q^n=|K|^n &\geq& \left|\bigcup_{c\in C}B_e(c)\right| \\ &=& \sum_{c\in C}|B_e(c)| \\ &=& |C|\cdot |B_e(0)| \\ &=& |C|\cdot\sum_{j=0}^e\binom n j. \end{eqnarray*} \]

Offenbar sind $C=K^n$ und jeder einelementiger $C$ perfekt. Weiterhin ist der binäre Wiederholungscode ungerader Länge $n=2e+1$ perfekt. Er enthält nur die beiden Codeworte $c=(0,0,\ldots,0)$ und $c=(1,1,\ldots,1)$ und man kann ganz $K^n$ mit den beiden Kugeln vom Radius $e$ um $c$ und $c'$ überdecken. Es sind die trivialen perfekten Codes.

Ein nicht trivialer perfekter Code: Sei $K=\mathbb{F}_2=\{0,1\}$.

\[ C=\left\{c=(c_1,c_2,\ldots,c_7)\,|\,c_i\in K, \begin{align} c_1+c_4+c_6+c_7=0 \\ c_2+c_4+c_5+c_7=0 \\ c_3+c_5+c_6+c_7=0 \end{align} \right\}. \]

Offenbar ist $C$ ein $K$-Vektorraum der Dimension 4, also $|c|=2^{\text{dim }C}=2^4$. Wegen der Translationsinvarianz von $d(.,.)$ gilt dann $d(C)=\min\{d(c,0)\,|\,0\neq c\in C\}$. An den drei Gleichungen kann man nachprüfen, dass jedes von Null verschiedene Codewort mindestens drei Einträge “1” haben muss. Also gilt – da z.B. das Vektor $(0,0,0,1,1,1,0)$ genau drei Einträge “1” hat – $d(C)=3$.
$C$ ist also ein 1-fehlerkorrigierender $(7,2^4,3)$-Code. Man verifiziere, dass die Kugelpackungsgleichung erfüllt ist:

\[ 2^7=|K|^7\geq 2^4\cdot(1+7)=2^7 \]

Dieser Code gehört der Familie der Hamming-Codes.

Lineare Codes

Ist das Alphabet $K$ ein Körper, so ist $K^n$ ein $K$-Vektorraum. Lineare Codes sind Unterraüme dieses Vektorraums. Sie bieten gegenüber Codes, die nur Teilmengen des $K^n$ sind, eine Fülle von vorteilen. So müssen nicht mehr alle Codeworte abgespeichert werden, sondern nur noch eine Basis, da sich jedes Codewort mit ihr eindeutig darstellen lässt. Weiterhin kann man die Minimaldistanz sehr viel schneller berechnen. Und die Decodieralgorithmen sind schneller, weil sie die Vektorraumstruktur ausnutzen.

Durch die Forderung der Linearität verliert man natürlich auch. Ein linearer Code hat bei vorgegebener Länge und Minimaldistanz oft weniger Codeworte als ein nichtlinearer.

Ist $k=\dim C$ und $d=d(C)$ die Minimaldistanz, so sprechen wir auch von einem $[n,k]$- oder $[n,k,d]$-Code über $K$. Falls $q=|K|$, nennen wir auch $[n,k,d]_q$ die Parameter von $C$.

Beispiel: Der Paritätscheck-Code

Wir wollen nun eine gewisse Gewichstfunktion definieren und nutzen, damit der Aufwand zur Bestimmung der Minimaldistanz reduziert wird.

Seien $K$ ein Körper und $n\in\mathbb{N}$.

Für $u=(u_1,\ldots,u_n)\in K^n$ setzen wir

\[ wt(u)=d(u,0)=|\{i\,|\,u_i\neq 0\}| \]

und nennen $wt:K^n\to\{0,1,\ldots,n\}$ die Gewichtsfunktion und $wt(u)$ das Gewicht von $u$.

Ist $\{0\}\neq C\subset K^n$, so heisst $wt(C):=\min\{wt(c)\,|\,0\neq c\in C\}$ das Minimalgewicht von $C$. Für $C=\{0\}$ setzen wir $wt(C)=0$.

Behauptung: Für einen linearen Code $C$ gilt $wt(C)=d(C)$.

Beweis: Ist $|C|=1$, so ist die Aussage klar richtig.
Für $|C|>1$ gist:

\[ \begin{eqnarray*} d(C) &=& \min\{d(c,c')\,|\,c,c'\in C,\quad c\neq c'\} \\ &=& \min\{d(c-c',0)\,|\,c,c'\in C,\quad c\neq c'\} \quad\text{(Translationsinvarianz von }d\text{ und Additivität von }C) \\ &=& \min\{wt(c)\,|\,0\neq c\in C\} \\ &=& wt(C). \end{eqnarray*} \]

Der Satz reduziert also den Aufwand zur Berechnung der Minimaldistanz von $\frac{|C|\cdot (|C|-1)}{2}$ Abstandsbestimmungen auf $|c|-1$ Gewichtsbestimmungen. Nämlich gilt

\[ \begin{eqnarray*} \frac{|C|\cdot (|C|-1)}{2} &=& \binom {|C|} 2=\frac{|C|!}{(|C|-2)!\cdot 2} \\ &=& \text{Anzahl der Möglichen Codeworte-Paare, wo es an die Reihenfolge der Paar-Elemente nicht kommt.} \end{eqnarray*} \]

Sei $(K)_{k,n}$ die Menge der Matrizen über dem Körper $K$ mit $k$ Zeilen und $n$ Spalten. Sei $C$ ein $[n,k]$-Code über $K$.

Ist $k\geq 1$, so heisst eine Matrix $G\in (K)_{k,n}$ eine Erzeugermatrix für $C$, falls

\[ c=K^k\cdot G=\{(u_1,\ldots,u_k)\cdot G\,|\,u_i\in K\}. \]

Die Zeilen von $G$ bilden also eine Basis von $C$. Insbesondere hat $G$ somit den Rang $k=\dim C$.

Ist $k<n$, so heisst eine Matrix $H\in (K)_{n-k,n}$ eine Kontrollmatrix für $C$, falls

\[ C=\{u\,|\,u\in K^n,\,H\cdot u^T=0\}. \]

Da ein $k$-dimensionaler Unterraum von $K^n$ sich als Durschschnitt von eieigneten $n-k$ Hyperebenen schreiben lässt, existiert stets eine Kontrollmatrix. Es gilt zudem:

\[ \text{Rang }H=n-\dim\text{Kern }H=n-\dim C=n-k. \]

Beispiel \[ C=\{(c_1,\ldots,c_n)\,|\,c_i\in K,\,\sum_{i=1}^n c_i=0\}. \]

Die Matrix

\[ \begin{pmatrix} 1 & -1 & 0 &\ldots & 0 & 0 \\ 0 & 1 & -1 &\ldots & 0 & 0 \\ \vdots \\ 0 & 0 & 0 &\ldots & 1 & -1 \\ \end{pmatrix} \in (K)_{n-1,n} \]

ist eine Erzeugermatrix für $C$, denn die Zeilen bilden eine Basis von $C$.

Die Matrix

\[ H=[1,1,\ldots,1]\in (K)_{1,n} \]

ist wegen

\[ C=\{(u_1,\ldots,u_n)\,|\,u\in K^n,\,H\cdot u^T=\sum_{i=1}^n u_i=0\} \]

eine Kontrollmatrix.

Mittels Erzeugermatrizen kann man einfach codieren, indem man einem Informationswort $u\in K^n$ das Codewort $c=u\cdot G\in C$ zuordnet. Kontrollmatrizen können zum Decodieren sinnvoll eingesetzt werden.

Die Syndrom-Decodierung

Sei $C$ ein [n,k]-Code über $K$ mit der Kontrollmatrix $H$. Bei der ML-Decodierung wird zu einem empfangenen Wort $\tilde{c}\in K^n$ ein Codewort $c\in C$ gesucht, so dass der Fehler $f=\tilde{c}-c\in \tilde{c}+C$ minimales Gewicht hat. Nun gilt:

\[ H\cdot\tilde{c}^T=H\cdot(f+c)^T=H\cdot f^T+H\cdot c^T=H\cdot f^T. \]

Bezeichnen wir den Vektor $s\in K^n$, für den $s^T=H\cdot v^T$ gilt, als das Syndrom von $v\in K^n$, so haben $\tilde{c}$ und der gesuchte Fehler $f$ das gleiche Syndrom.

Beachten wir noch, dass

\[ H\cdot v^T=H\cdot u^T \quad\Leftrightarrow\quad v-u\in C, \] und

\[ v-u\in C \quad\Leftrightarrow\quad c+C=u+C. \]

Das bedeutet, dass das Syndrom con $\tilde{c}$ die Nebenklasse von $c$ im $K^n$ festlegt, in welcher der Fehler zu suchen ist, und zwar eindeutig. Angenommen, wir könnten für jede Nebenklasse $v+C$ einen sogenannten **Nebenklassenführer”” $f_v$v+C$ mit

\[ wt(f_v)=\min\{wt(c+c)\,|\,c\in C)\} \]

bestimmen (Dies erfordert Aufwand, falls $|C|$ gross ist). Wir könnten das empfangene Wort $\tilde{c}$ zum Codewort $c=\tilde{c}-f_{\tilde{c}}$ decodieren. Das nennt man Syndrom-Decodierung.

Anstatt die $|K|^k$ Abstände $d(\tilde{c},c)$ mit $c\in C$ zu bestimmen ($\tilde{c}$ bleibt hier fest), wird bei der Syndrom-Decodierung unter den $|K|^{n-k}$ Klassenführer derjenige gesucht, der das gleiche Syndrom wie $\tilde{c}$ hat. Falls $k>n/2$, so sind also weniger Vergleiche auszuführen.

Neben der Decodierung ist eine Kontrollmatrix auch hilfreich bei der Bestimmung der Minimaldistanz.

Ist $C$ ein $[n,k]$-Code über $K$, mit $k\geq 1$ und der Kontrollmatrix $H$, so gilt:

\[ \begin{eqnarray*} d(C) &=& wt(C) \\ &=& \min\{r\,|\,r\in\mathbb{N}, \quad\text{es gibt }r\text{ linear von }H\text{ unabhängige Spalten}\} \\ &=& \min\{r\,|\,r\in\mathbb{N}, \quad\text{je }(r-1)\text{ Spalten von }H\text{ sind linear unabhängig}\} \\ \end{eqnarray*} \]

Beweis: Wir haben nur das zweite Gleichheitszeichen zu beweisen.
Seien $h_1,\ldots, h_n$ die Spalten von $H$. Da nach Voraussetzung $C\neq\{0\}$, sind diese Spalten linear unabhängig. Sei nun $w\in\mathbb{N}$ minimal gewählt, so dass es $w$ linear abhängige Spalten gilt, etwa $h_{i_1},\ldots,h_{i_w}$. Also können wir $c_j\in K$ mit $c_j\neq 0$ genau für $j\in\{i_1,\ldots,i_w\}$ finden, so dass $\sum_{j=1}^n c_j=0$. Setzen wir $c=(c_1,\ldots,c_n)$, so gilt $H\cdot c^T=0$, also $c\in C$. Wegen $wt(c)=w$ erhalten wir $wt(C)\leq w$.

Angenommen, es gäbe $o\neq\tilde{c}\in C$ mit $\tilde{w}=wt(\tilde{c})<w$. Dann würde $H\cdot\tilde{c}^T=0$ die Existenz von $\tilde{w}$ linear abhängigen Spalten von $H$ liefern entgegen der Definition von $w$. Damit ist die Behauptung gezeigt.

Beispiel: Die Hamming-Codes Seien $K$ ein Körper mit $q$ Elementen und $2\leq k\leq\mathbb{N}$. Jeder Vektor $0\neq u\in K^k$ definiert eine Gerade durch Null im $K^k$, nämlich

\[ <u>:=\{k\cdot u,|\,k\in K\}. \]

Da die skalaren Vielfachen ungleich Null von $u$ die gleiche Gerade definieren, gibt es genau

\[ n=\frac{q^k-1}{q-1}=\frac{\text{Anzahl von }k\text{-Vektoren}\neq0}{\text{Anzahl von Skalaren}\neq0}=\frac{|K^k|-1}{|K|-1} \]

verschiedene Geraden im $K^k$.
Sind $<h_1>, <h_2>,\ldots,<h_n>$ diese Geraden, wobei wir die $h_i$ als Spaltenvektoren schreiben, so setzen wir

\[ H=(h_1,\ldots,h_n)\in K_{k,n}. \]

Der Code $C$ über $K$ mit der Kontrollmatrix $H$, also

\[ C=\{c\in K^n\,|\,H\cdot c^T=0\} \]

heisst ein Hamming-Code. Das Vielfache der Einheitsvektoren $e_1,\ldots,e_n\in K^n$ als Spalten in $H$ stehen, folgt $\dim C=n-k$. Ferner sind je zwei Spalten von $H$ linear unabhängig und geeignete drei Spalten abhängig.

Mit dem zuletzt gezeigten Satz erhalten wir direkt $wt(C)=d(C)=3$. Somit hat $C$ die Parameter $[n,n-k,3]$, ist also 1-fehlerkorrigierend.

Die Kugelpackungsgleichung

\[ \left|\bigcup_{c\in C}B_1(c)\right|=|C|\cdot|B_1(0)|=q^{n-k}\cdot(1+n(q-1))=q^n \]

liegt ferner die Perfektheit von $C$.

Richard Hamming

Richard Hamming arbeitete bei den Bell Labs in den 1940er Jahren an eine auf elektromechanischen Relais-basierte Maschine (der Bell Model V Computer). Während den Wochenenden, wenn Fehler in den Relais gemeldet wurden, hörte die Maschine auf zu laufen und Flash Lichter blickten, so dass die zuständige Informatiker das Problem aufheben konnten. Hamming hat sich einmal in einem aufgenommenen Interview darüber geäussert:

“Damn it, if the Machine can detect an error, why can’t it locate the position of the error and correct it?”

So sprach der Erfinder des ersten fehlerkorrigierenden Codes.

Kodierungstheorie