\newcommand{\dist}{\operatorname{dist}}

\begin{slide}{Hamming-Abstände}

Code-Wörter sind Bit-Folgen.

alle Bit-Folgen gleicher Länge bilden 
einen \emph{metrischen Raum} 
durch die Abstandsfunktion (Hamming distance)


\[ \dist(u,v) := | \{ i : u_i \neq v_i \} | \]

( $=$ Anzahl der Positionen, an denen sich die Werte (Bits) unterscheiden).

(formuliere und beweise die Dreiecks-Ungleichung)

Richard Wesley Hamming (1915 -- 1998)
\url{http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Hamming.html}


\end{slide}

\begin{slide}{Abstände und Codes}

die Hamming-Weite einer Menge $M$ von Codewörtern ist

\[ \dist(M) = \min \{ \dist(u,v) : u\in M, v\in M, u \neq v \} \]

(der kleinste Abstand zwischen zwei Wörtern)

Beispiel: $\dist\{110, 101, 011\}=2$.

Finde möglichst viele Code-Wörter der Länge $l$
mit Weite $\ge w$! (Beispiel: $l=6, w=3$)

\end{slide}

\begin{slide}{Fehler-Erkennung und -Korrektur}

\begin{itemize}
\item
  Ein Code $M$ kann $k$-Bit-Fehler \emph{erkennen},
  falls $\dist(M) > k$.
\item
  Ein Code $M$ kann $k$-Bit-Fehler \emph{korrigieren},
  falls $\dist(M) > 2k$.
\item
  Zu empfangenem (möglicherweise verfälschtem) Codewort $w'$
  bestimmt man das nächstliegende (bzgl. $\dist$) tatsächliche Codewort.
\item
  Falls $\dist(M) > 2k$ und höchstens $k$ Bit falsch,
  dann ist dieses eindeutig bestimmt.
\end{itemize}
Wieviel Bits braucht man für eine Codierung
der Dezimalziffern, die 2-Bit-Fehler korrigieren kann?


\end{slide}
