%%This is a very basic article template. %%There is just one section and two subsections. \documentclass[a4paper, 12pt]{article} \usepackage[DIV12]{typearea} \usepackage{xcolor} \usepackage[ngerman]{babel} \usepackage[ansinew]{inputenc} \usepackage{amsmath} \usepackage{amssymb} \usepackage{dsfont} \begin{document} \title{fehlerkorrigierende Codes} \author{Thomas Irgang \\ Katholische Universitt Eichsätt} %\institute{Katholische Universitt Eichsätt} \date{\today} \maketitle \newpage \tableofcontents \newpage \section{Was sind fehlerkorrigierende Codes?} \subsection{Was fehlerkorrigierende Codes nicht sind!} Fehlerkorrigierende Codes haben \emph{nichts} mit Verschlüsselung zu tun! Ganz im Gegenteil. Es geht darum Datenverlust zu vermeiden. Die codierten Daten sollen trotz Fehlern bei der Übertragung/Speicherung lesbar bleiben. \subsection{Definition fehlerkorrigierender Codes} Fehlerkorrigierende Codes sind Codes, die es ermöglichen trotz Fehlern, die bei der Übertragung oder Speicherung von Daten auftreten, die Daten wieder herzustellen. \subsection{Wozu braucht man fehlerkorrigierende Codes} Auch, oder gerade im Zeitalter der digitalen Datenverarbeitung passieren ständig Fehler. Zum Beispiel: \begin{itemize} \item werden CDs verkratzt \item entstehen Fehler bei der Übertragung von Daten auf Leitungen \item kommen Funksignale ``gestört'' an \end{itemize} \subsection{Modellvorstellung} Die Grundsituatuion sieht folgendermaßen aus:\\ Ein Sender will einem Empfänger eine Nachricht schicken. Dazu wird die Nachricht in Codewörtern codiert. Diese codierte Nachricht wird an den Empfänger übermittelt, wobei bei der Übertragung jedoch Fehler auftreten. Der Empfänger versucht die veränderte Nachricht beim decodieren wieder herzustellen. \subsection{Problemstellung} Wie kann man an Hand der übertragenen Nachricht einfach erkennen, ob ein Fehler beim Übertragen passiert ist?\\ Eine einfache Möglichkeit ist z.B. ein Prüfbit. Dabei wird vereinbart, dass die Anzahl der Einsen immer gerade/ungerade sein muss ( ``gerade/ungerade Parität'' ). Ein Bitumkehrfehler kann damit erkannt werden. Falls ein Fehler erkannt wird fordert der Empfänger die Nachricht nochmal an.\\ Das Problem ist damit jedoch nicht gelöst! Was ist wenn die Übertragung so schlecht ist, dass bei fast jedem Datenpacket fehler auftreten? Was ist wenn die Nachricht nicht einfach nochmal geschickt werden kann, z.B. weil die Datenquelle eine verkratzte CD ist?\\ Man braucht also Verfahren, die die Daten so kodieren, dass eine begrenzte Anzahl von Fehlern korrigiert werden kann. Wie kann man das erreichen? \subsubsection{Die Lösung} Wenn die Codewörter sich paarweise in mehrern Bits unterscheiden kann man sich diesen Unterschied als ``Abstand'' der Codewörter vorstellen. Es gibt also ``freie'' Bereiche zwischen den Codewörter, damit gibt es eine Umgebung um jedes Codewort in dem jedes Wort darin minimalen Abstand zu diesem Codewort hat. Wenn wir also ein Wort empfangen können wir es dem Codewort zuordnen von dem es den geringsten Abstand hat. An einem Beispiel wird das sofort klar. \subsubsection{Beispiel} Gegeben sind die Codewörter $a,b \in C \subseteq \{ 0,1 \}^{4}$ (aus dem Code C, der aus 4-Tupeln über $\{ 0,1 \}$ besteht), $a:=0011$, $b:=1110$\\ a und b unterscheiden sich in: $\left. \begin{array}{c} {\color{red}00}1{\color{red}1} \\ {\color{red}11}1{\color{red}0} \end{array} \right\}$ drei Stellen.\\ Wenn wir jetzt ein verändertes Codewort x empfangen, z.B. $x=0110$, können wir es mit a und b vergleichen\\ a und x: $\left. \begin{array}{c} 0{\color{red}0}1{\color{red}1} \\ 0{\color{red}1}1{\color{red}0} \\ \end{array} \right\}$ unterscheiden sich in zwei Stellen.\\ b und x: $\left. \begin{array}{c} {\color{red}1}110 \\ {\color{red}0}110 \\ \end{array} \right\}$ unterscheiden sich in einer Stelle.\\ Damit können wir unter der Annahme einer minimalen Fehlerzahl x als b decodieren. \subsection{Hammingabstand} Die Anzahl der Stellen in denen sich zwei Codewörter unterscheiden bezeichnet man als \emph{Hammingabstand}. Mathematisch sieht das so aus: \[ u,v \in C \subseteq \{ 0,1 \}^{n} \] \[ d(u,v)=| \{ i: u_i \neq v_i \} | \] Der minimale Hammingabstand eines Codes ist definiert als: \[ d(C):=min\{ d(u,v) \ : \ u,v \in C \} \] Also der minimale Abstand den zwei Codewörter haben. \subsection{Aufgaben} Definiere: $c : A \rightarrow C$, A Alphabet, C Code, d.h. $c(5)$ ist das Codewort von 5\\ c(0)=00011, c(1)=00110, c(2)=01100, c(3)=11000\\ \begin{enumerate} \item Bestimme den minimalen Hamming-Abstand der Codewörter c(0), c(1), c(2), c(3)! \item Kann man das veränderte Codewort x=00010 eindeutig decodieren? \item Beschreiben Sie den Zusammenhang zwischen dem minimalen Hamming-Abstand eines Codes und seiner Eigenschaften bezüglich des erkennens und korrigierens von Fehlern? \end{enumerate} \subsubsection{Lösung zu den Aufgaben} \begin{enumerate} \item \[ \begin{array}{ccccc} & 00011 & 00110 & 01100 & 11000 \\ 00011 & - & 2 & 4 & 4 \\ 00110 & - & - & 2 & 4 \\ 01100 & - & - & - & 2 \\ 11000 & - & - & - & - \\ \end{array} \] $\Rightarrow$ der Minimalabstand der Codewörter ist 2. \item Nein, das Wort hat z.B. Abstand 1 sowohl von 0 als auch von 1 und ist kein gültiges Codewort. Daraus folgt: \item Ein Minimalabstand von 2 reicht aus um einen Fehler zu erkennen (man muss mindestens 2 Bit ändern um wieder ein gültiges Codewort zu erhalten), das veränderte Codewort kann aber i. A. nicht eindeutig einem Codewort zugeordnet werden. \end{enumerate} Allgemein folgt daraus: \subsection{Minimalabstand und Fehlereigenschaften} Ein Code $C \subseteq {0,1}^n$ heißt ein \emph{t-fehlerkorrigierender} Code falls der Minimalabstand zwischen zwei Codewörtern $\geq 2t+1$ ist. Ein solcher Code kann $2t$ Fehler erkennen.\\ Es gibt also um jedes Codewort eine Umgebung mit Radius t in der in der jedes Wort dem Codewort zugeordnet werden kann. \section{Mathematik und feherkorrigierende Codes} \subsection{Was hat das mit Mathe zu tun?} Was hat das ganze denn nun überhaupt mit Mathe zu tun?\\ Wir müssen irgendwie ``effektiv'' mit dem Code umgehen können! Es wäre sehr mühselig bzw. rechenaufwendig jedes empfangene Codewort mit jedem gültigen Codewort zu vergleichen, bzw. den Mindestabstand mit jedem Codewort zu bestimmen nur um es zu decodieren. An dieser Stelle kommt die Mathematik, bzw. viel mehr die lineare Algebra, ins Spiel. \subsection{Vektoren und Codes} Ihr kennt Vektoren aus dem Matheunterricht. Man kann aber nicht nur Vektoren über $\mathds{R}$ betrachten, sondern über jedem Körper. Die beiden Elemente 0 und 1 bilden auch einen Körper (Beiweis siehe \ref{z2}) und unsere Codewörter sind Vektoren über diesem Körper (Beweis siehe \ref{vr}).\\ Wenn die Codewörter alle in einem Unterraum des Vektorraums liegen - ein solcher Code heißt linearer Code - bringt das eine Reihe von Vorteilen mit sich. \subsection{lineare Codes} Ein linearer Code kann: \begin{itemize} \item mit Hilfe einer Basis erzeugt werden und \item mit Hilfe von Matrizen ``verarbeitet'' werden. \end{itemize} Verarbeitet bedeutet in diesem Zusammenhang dass Daten codiert, decodiert und Fehler korrigiert werden. \subsection{Matrizenmultiplikation} Im folgenden brauchen wir die Multiplikation von Vektoren mit Matrizen. Diese Multiplikation ist allgemein definiert durch: \[ \left( \begin{array}{ccc} a_{11} & \ldots & a_{1n} \\ a_{21} & \ldots & a_{2n} \\ \ldots & \ldots & \ldots \\ a_{m1} & \ldots & a_{mn} \\ \end{array} \right) \cdot \left( \begin{array}{c} v_1 \\ v_2 \\ \ldots \\ v_4 \\ \end{array} \right) = \left( \begin{array}{c} \sum_{i=1}^n a_{1i} \cdot v_i \\ \sum_{i=1}^n a_{2i} \cdot v_i \\ \ldots \\ \sum_{i=1}^n a_{mi} \cdot v_i \\ \end{array} \right) \] (also: Zeile $\cdot$ Spalte)\\ Ein Beispiel dazu: \[ \left( \begin{array}{ccccc} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{array} \right) \cdot \left( \begin{array}{c} 1 \\ 1 \\ 0 \\ \end{array} \right) = \left( \begin{array}{c} 1 \cdot 1 + 0 \cdot 1 + 0 \cdot 0 \\ 1 \cdot 1 + 1 \cdot 1 + 0 \cdot 0 \\ 0 \cdot 1 + 1 \cdot 1 + 1 \cdot 0 \\ 0 \cdot 1 + 0 \cdot 1 + 0 \cdot 0 \\ 0 \cdot 1 + 0 \cdot 1 + 0 \cdot 0 \\ \end{array} \right) = \left( \begin{array}{c} 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ \end{array} \right) \] \subsection{ein Beispiel} Die Matrix $G:=\left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ \end{array}\right)$ (G für Generatormatrix) erzeugt einen linearen 1-fehlerkorrigierenden Code. Die Spalten der Matrix spannen dabei einen linearen Unterraum auf in dem die Codewörter liegen. Wenn jetzt z.B. das Datenwort $x:=\left(\begin{array}{c} 0 \\ 1 \\ 1 \\ 0 \end{array}\right)$ codiert werden soll rechnet man einfach $G \cdot x = \left(\begin{array}{c} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \end{array}\right)$. Dadurch muss man statt 16 ($=2^4$) Codewörtern nur 4 speichern. Damit können wir Daten effektiv codieren und Codes effektiv speichern. Um auch effektiv decodieren zu können brauchen wir noch etwas mehr Mathematik. \subsection{Minimalgewicht} Als \emph{Gewicht} eines Vektors wird seine Anzahl der von 0 verschiedenen Stellen bezeichnet. Formal sieht die Definition so aus: \[ w(c):=| \{ i \ | \ c_i \neq 0 \} |, c \in C \] Das \emph{Minimalgewicht $w(C)$} des Codes C definiert man dann als: \[ w(C):=min \{ w(c) | c \in C, c \neq 0 \} \] Weiter ergibt sich, dass $d(C)=w(C)$. (Beweis siehe \ref{dgleichw}). Man muss also maximal $|C|$ Codewörter betrachten anstatt $|C|$ Codewörter paarweise miteinander zu vergleichen.\\ \emph{Achtung:} Dies vereinfacht das erkennen von Fehlerkorrektureigenschaften erheblich, man muss aber dennoch alle Codewörter betrachen, denn $a:=011100$ und $b:=111000$ haben beide Gewicht 3, der lineare Code für den diese eine Basis sind enthält aber auch $a+b$, also $\left.\begin{array}{cc} & 111000 \\ + & 011100 \\ \end{array} \right\} = 100100$, hat damit ein Minimalgewicht $\leq 2$ und kann somit keine Fehler korrigieren. \subsection{Aufgabe} Wie viele Fehler kann der folgende lineare Code erkennen/korrigieren? \[ \begin{array}{cccc} 0000000 & 0001110 & 0010111 & 0011001 \\ 0100101 & 0101011 & 0110010 & 0111100 \\ 1111111 & 1110001 & 1101000 & 1100110 \\ 1011010 & 1010100 & 1001101 & 1000011 \\ \end{array} \] \subsubsection{Lösung zu den Aufgaben} Der Code hat Minimalgewicht 3 $\Rightarrow $ er kann einen Fehler korrigiern und 3 Fehler erkennen. Dies ist der Code der von der obigen Generatormatrix erzeugt wird. \subsection{Aber was ist mit decodieren?} Wir können jetzt also einfach Datenwörter codieren, bzw. alle $2^k$ Codewörter aus $k$ Basisvektoren erzeugen und einen Code schnell einschätzen. Aber wie können wir einfach fehlerkorriegiern und die Codewörter decodieren? Dazu brauchen wir, wie soll es auch anders sein, mehr Theorie. \subsection{der duale Code} Um einen linearen Code effektiv zu decodieren brauchen wir den dualen Code. Sei C ein Code, der zu C \emph{duale Code $C^\perp$} ist definiert durch: \[ C^\perp := \{ v \in V \ | \ c \cdot v = 0 \forall c \in C \} \] dabei bedeutet $c \cdot v = \sum_{i=1}^n c_i \cdot v_i$.\\ \emph{Achtung:} Bei dieser Definition gibt es ein paar merkwürdige Phänomene! $C^\perp$ und $C$ können teilweise übereinstimmen. Dies ist eine Folge des endlichen Körpers $\mathds{Z}_2$ und spielt hier im weiteren keine Rolle, soll aber niemanden verwirren. Trotz allem gilt aber:\\ \[ C^{\perp \perp} = C \] \subsection{die Kontrollmatrix} Wenn wir den dualen Code haben, haben wir auch die Kontrollmatrix und sind damit wieder einen Schritt näher am Ziel. Eine Matrix deren Zeilen eine Basis des dualen Codes sind nennt man \emph{Kontrollmatrix} des linearen Codes, das Produkt $H \cdot s$ nennt man das \emph{Syndrom}. Mit Hilfe des Syndroms können wir nun endlich einen linearen Code effektiv decodieren. Da die Basis des dualen Codes Teilmenge des Codes ist gilt natürlich $s(c)=0 \ \forall \ c \in C$. \subsection{Syndromdecodierung} Weiterhin gilt $s(v)=s(w) \Leftrightarrow v+C = w+C$ (siehe \ref{nklassen})\\ Das bedeutet dass das Syndrom eines Vektors nur von der Nebenklasse abhängt in der der Vektor liegt.\\ Als \emph{Anführer} einer Nebenklasse wird der Vektor mit dem kleinsten Gewicht bezeichnet. Diese Nebenklassenanführer sind eindeutig, d.h. jede Nebenklasse hat genau einen Anführer. (siehe \ref{eindeutig}) \\ \subsection{der Decodieralgorithmus} Damit kann man, mit Hilfe einer Liste der Nebenklassenanführer folgendermaßen vorgehen: \begin{enumerate} \item Syndrom vom empfangen Wort x berechen \item Nebenklassenanführer e feststellen \item Codewort c durch $c=x+e$ berechnen \end{enumerate} \section{ein vollständiges Beispiel} Diesen Algorithmus können wir jetzt mal an einem Beispiel durchspielen. Wir benutzen wieder die Generatormatrix $G:=\left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ \end{array}\right)$\\ Als erstes brauchen wir wieder eine Kontrollmatrix, also brauchen wir den dualen Code. Wir brauchen also drei linear unabhängige Vektoren die das Gleichungssystem \[ \begin{array}{ccc} (1)\ c_1 + c_6 + c_7 & = & 0 \\ (2)\ c_2 + c_5 + c_7 & = & 0 \\ (3)\ c_3 + c_5 + c_6 + c_7 & = & 0\\ (4)\ c_4 + c_5 + c_6 & = & 0\\ \end{array} \] erfüllen. Dies ist z.B. bei den Vektoren $ \left( \begin{array}{c} 1\\0\\0\\1\\1\\0\\1 \end{array} \right),\ \left( \begin{array}{c} 0\\1\\0\\1\\0\\1\\1 \end{array} \right),\ \left( \begin{array}{c} 0\\0\\1\\0\\1\\1\\1 \end{array} \right) $ der Fall, die Matrix $ K := \left( \begin{array}{ccccccc} 1 & 0 & 0 & 1 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 1 & 1 & 1\\ \end{array} \right) $ ist also eine Kontrollmatrix zu $G$. Jetzt können wir die Nebenklassenanführer berechnen. Dies erreichen wir in dem wir indem wir die Syndrome der Einheitsvektoren berechen (siehe \ref{eindeutig}). Dadurch erhalten wir: \[ \begin{array}{cc} 0000000 & 000 \\ 0000001 & 111 \\ 0000010 & 011 \\ 0000100 & 101 \\ 0001000 & 110 \\ 0010000 & 001 \\ 0100000 & 010 \\ 1000000 & 100 \\ \end{array} \] Jetzt müssen wir nur noch die die Codewörter ihren Datenwörtern zuordnen. Das ist aber einfach, denn wenn wir die Generatormatrix betrachten sehen wir dass die ersten 4 Bit des Codeworts das Datenwort sind. Es reicht also die letzten drei Bit abzuschneiden.\\ Jetzt haben wir alles um den Algorithmus anzuwenden. Nehmen wir uns ein Datenwort z.B. $x=0110$. Als erstes codieren wir das Datenwort durch Multiplikation mit der Matrix. \[ \left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ \end{array}\right) \cdot \left( \begin{array}{c} 0\\1\\1\\0 \end{array} \right) = \left( \begin{array}{c} 0\\1\\1\\0\\0\\1\\0 \end{array} \right) \] Wenn jetzt bei der Übertragung ein Fehler passiert und aus dem Codewort z.B. $ \left( \begin{array}{c} 1\\1\\1\\0\\0\\1\\0 \end{array} \right) $ wird ergibt die Multiplikation mit der Kontrollmatrix \[ \left( \begin{array}{ccccccc} 1 & 0 & 0 & 1 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 1 & 1 & 1\\ \end{array} \right) \cdot \left( \begin{array}{c} 1\\ 1\\ 1\\ 0\\ 0\\ 1\\ 0\\ \end{array} \right) = \left( \begin{array}{c} 1 + 0 + 0 + 0 + 0 + 0 + 0\\ 0 + 1 + 0 + 0 + 0 + 1 + 0\\ 0 + 0 + 1 + 0 + 0 + 1 + 0\\ \end{array} \right) = \left( \begin{array}{c} 1\\ 0\\ 0\\ \end{array} \right) \] Also ist der Fehlervektor $ \left( \begin{array}{c} 1\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ \end{array} \right) $ und $\left( \begin{array}{c} 1\\ 1\\ 1\\ 0\\ 0\\ 1\\ 0\\ \end{array} \right) + \left( \begin{array}{c} 1\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ \end{array} \right) = \left( \begin{array}{c} 0\\ 1\\ 1\\ 0\\ 0\\ 1\\ 0\\ \end{array} \right) $ , das Datenwort ist demnach $ \left( \begin{array}{c} 0\\ 1\\ 1\\ 0\\ \end{array} \right) $ was korrekt ist. Die Korrektur funktioniert also. \section{Beweise und Ergänzungen} \subsection{Der Körper $ \mathds{Z}_2$ } \label{z2} Um zu zeigen dass die Elemente $ \{ 0,1 \} $ einen Körper bilden muss man zeigen dass die beiden Elemente die Körperaxiome erfüllen. Dazu müssen wir zuerst die Addition und die Multiplikation definieren. Dies erfolgt mit Hilfe der Modulo-Rechnung. Was ist Modulo-Rechnung?\\ Einfach ausgedrückt ist $ a \ mod \ b $ der Rest der ganzzahligen Divison, d.h. $ 15 : 6 = 2 \ Rest \ 3$, dann ist $ 15 \ mod \ 6 = 3$ (in vielen Programmiersprachen der \%-Operator).\\ Im $ \mathds{Z}_2$ ist die Addition durch \[ a +_2 b := (a+b)mod \ 2 \] definiert und die Multiplikation durch \[ a \cdot_2 b := (a \cdot b)mod \ 2 \] definiert. Mit diesem Vorwissen sind die Körperaxiome einfach zu zeigen.\\ \begin{description} \item[Kommutativgesetz] $ a+b = (a+b)mod \ 2 = (b+a)mod \ 2 = b+a $ \\ $ a \cdot b = (a \cdot b)mod \ 2 = (b \cdot a)mod \ 2 = b \cdot a $ \item[Assoziativgesetz] $ (a+b)+c = ((a+b)mod \ 2)+c)mod \ 2 = (a+b+c)mod \ 2 = (a+((b+c)mod \ 2))mod 2 = a+(b+c) $ \\ $ (a \cdot b) \cdot c = ((a \cdot b)mod \ 2) \cdot c)mod \ 2 = (a \cdot b \cdot c)mod \ 2 = (a \cdot ((b \cdot c)mod \ 2))mod 2 = a \cdot (b \cdot c)$ \item[neutrales Element der Addition] $a +_2 0 = (a+0)mod \ 2 = a\ mod\ 2 = a$, d.h. die ``übliche'' 0 ist auch das Null-Element in $\mathds{Z}_2 $. \item[neutrales Element der Multiplikation] Analog zur Addition folgt: $a \cdot_2 1 = (a\cdot 1)mod \ 2 = a\ mod\ 2 = a$, d.h. die ``übliche'' 1 ist auch das Eins-Element in $\mathds{Z}_2 $. \item[eindeutige Lösbarkeit der Gleichung $a\cdot x = 1$ für $a\neq 0$] Im $mathds{Z}_2$ gibt es genau ein Element $\neq $ 0, die 1, und $1\cdot 1 = 1$, d.h. die 1 ist ihr eigenes inverses Element. \item[Distributivgesetz] $a\cdot_2 (b +_2 c) = a\cdot_2 ((b+c)mod \ 2) = (a\cdot (b+c))mod \ 2 = (a\cdot b + a\cdot c)mod \ 2 = (((a\cdot b)mod \ 2) + ((a\cdot c)mod \ 2))mod \ 2 = a\cdot_2 b +_2 a\cdot_2 c$ \end{description} Damit ist gezeigt dass $\mathds{Z}_2 $ ein Körper ist. \subsection{Vektorraum über $\mathds{Z}_2$ } \label{vr} Es reicht zu zeigen, dass $\mathds{Z}_2^n$ bezüglich der Addition und der Multiplikation mit einem Körperelement abgeschlossen ist, d.h. wenn $a,b \in \mathds{Z}_2^n$ dann ist auch $\alpha \cdot a + \beta \cdot b \in \mathds{Z}_2^n$.\\ $a,b \in \mathds{Z}_2^n$, also $a=\left( \begin{array}{c} a_1\\ a_2\\ \ldots \\ a_n\\ \end{array} \right)$, dann ist $a+b$ definiert als $\left( \begin{array}{c} a_1 + b_1\\ a_2 + b_2\\ \ldots \\ a_n+b_n\\ \end{array} \right)$. Da $\mathds{Z}_2$ ein Körper ist und $a_i, b_i \in \mathds{Z}_2$, dass $a_i + b_i \in \mathds{Z}_2$. Damit folgt $a+b \in \mathds{Z}_2^n$. $\mathds{Z}_2^n$ ist also bezüglich der Addition abgeschlossen. Man muss noch zeigen dass $\mathds{Z}_2^n$ bezüglich der Multiplikation abgeschlossen ist. Das funktioniert ähnlich:\\ $\alpha \cdot \left( \begin{array}{c} a_1\\ a_2\\ \ldots \\ a_n\\ \end{array} \right) = \left( \begin{array}{c} \alpha \cdot a_1\\ \alpha \cdot a_2\\ \ldots \\ \alpha \cdot a_n\\ \end{array} \right)$. Da $\mathds{Z}_2$ ein Körper ist folgt wieder $\alpha \cdot a \in \mathds{Z}_2^n$.\\ Damit ist eigentlich nur gezeigt dass $\mathds{Z}_2^n$ ein Unterraum ist, dies ist in diesem Fall aber ausreichend. \subsection{$d(x)=w(x)$ } \label{dgleichw} Im folgenden seien $u,v,w \in C$.\\ Im folgenden braucht man dass $d(\cdot, \cdot)$ eine Metrik ist, d.h. \begin{enumerate} \item $d(u,v)>0$ für $u\neq v$ und $d(u,u)=0$ \item $d(u,v)=d(v,u)$ \item $d(u,w)\leq d(u,v) + d(v,w)$ \end{enumerate} Dann mal los. \begin{enumerate} \item ist klar \item ist auch klar \item Wir können annehmen dass sich $u$ und $w$ genau an den ersten $t$ Stellen unterscheiden.\\ Unter den ersten $t$ Stellen gibt es dann $r$ Stellen an denen sich $u$ und $v$ unterscheiden ($r \in \{ 0, \ldots , t \} $), das heißt aber $v$ und $w$ unterscheiden sich in $t-r$ Stellen.\\ Weiter unterscheiden sich $u$ und $v$ in den letzten $n-t$ Stellen in $s$ Stellen. Dann unterscheiden sich $v$ und $w$ ebenfalls in $s$ Stellen. Insgesamt folgt dann: $d(u,v)=r+s$ und $d(w,v)=t-r+s$, also $d(u,v)+d(w,v)=r+s+t-r+s=t+2s$ und damit gilt \[ d(u,w) \leq d(u,v) + d(w,v) \] da $s\geq 0$. \end{enumerate} Damit folgt dann aber \[ d(C) = min\{ d(c,c')\ |\ c,c'\in C,\ c\neq c' \} \leq min\{ d(c,0)\ |\ c\in C,\ c\neq 0 \} = w(C) \] Also der Minimalabstand ist kleiner als das Minimalgewicht des Codes. Wenn wir jetzt noch zeigen dass es ein Codewort vom Gewicht d(C) gibt ist die Gleichheit gezeigt. Seien also $c,c'\in C$ mit $d(c,c')=d(C)$. Es gilt $w(c-c')=d(c-c',0)=d(c,c')=d(C)$. Da $C$ ein linearer Code ist, ist $c-c'\in C$. Damit haben wie die Gleichheit gezeigt. Für lineare Codes (und nur für lineare Codes) gilt also $d(C)=w(C)$ \subsection{Nebenklassen und Syndrome} \label{nklassen} Vorweg: $v+C:=\{ v+c\ |\ c \in C \} $. Weiter ist $s(\cdot)$ eine lineare Abbildung, d.h. $s(v+c)=s(v)+s(c)$\\ Schauen wir uns jetzt die Aussage an:\\ $s(v)=s(w),\ v,w\in \mathds{Z}_2^n$\\ $\Leftrightarrow s(v)-s(w)=0$\\ $\Leftrightarrow s(v-w)=0$\\ $\Leftrightarrow v-w\in C$\\ $\Leftrightarrow v+C=w+C$\\ \label{eindeutig} Nun zur Eindeutigkeit.\\ \emph{Satz über die Eindeutigkeit der Nebenklassenanfüher}\\ Sei $C$ ein linearer $t$-fehlerkorrigierender Code. Dann gilt: \begin{enumerate} \item Jeder Vektor von V vom Gewicht $\leq t$ ist ein Nebenklassenanführer. \item Die Anführer von Nebenklassen die einen Vektor vom Gewicht $\leq t$ enthalten sind eindeutig bestimmt. \end{enumerate} Beweis:\\ Sei v ein Vektor vom Gewicht $\leq t$. Betrachten wir nun einen beliebigen Vektor $v'\in v+C\ \Leftrightarrow \exists c \in C$ mit $v' = v+c$. Sei weiter $v' \neq v$, d.h. $c\neq 0$. Wir müssen jetzt zeigen, dass $w(v')\geq t+1$ ist. Wenn wir das gezeigt haben wissen wir auch, da $v'$ ein beliebiger Vektor aus diese Nebenklasse war, dass alle Vektoren diese Nebenklasse $\neq v$ ein Gewicht von $\geq t+1$ haben.\\ Da $v$ und $v'$ in der selben Nebenklasse sind ist $v-v' \in C$, also $v-v'$ ist ein Codewort. Aber $v\neq v'$ und damit $v-v'\neq 0$ . Deshalb gilt $w(v-v') \geq 2t+1$, da $C$ ein $t$-fehlerkorrigierender Code ist. Damit folgt: \[ 2t+1 \leq w(v-v') = d(v-v',0) = d(v,v') \leq d(v,0) + d(v',0) = w(v) + w(v') \leq t + w(v') \] also haben wir $2t+1 \leq t+w(v') \Leftrightarrow t+1 \leq w(v')$ und damit ist der Satz gezeigt. \section{Literatur} Albrecht Beutelspacher: Lineare Algebra, Vieweg, 6.Auflage, Wiesbaden 2003 \end{document}