\documentclass[loesungseite]{schuleab}
\usepackage[utf8]{inputenc}
\usepackage{schulinf}

% Dieses Dokument ist in der Zusammenarbeit von Informatikreferendaren und
% ehemaligen Informatikreferendaren der Studienseminare (heute ZfsL) Arnsberg,
% Hamm und Solingen entstanden.
%
% Das Dokument steht unter der Lizenz: Creative Commons by-nc-sa Version 4.0
% http://creativecommons.org/licenses/by-nc-sa/4.0/deed.de
%
% Nach dieser Lizenz darf das Dokument beliebig kopiert und bearbeitet werden,
% sofern das Folgeprodukt wiederum unter gleichen Lizenzbedingungen vertrieben
% und auf die ursprünglichen Urheber verwiesen wird.
% Eine kommerzielle Nutzung ist ausdrücklich ausgeschlossen.
%
% Die Namensnennung durch einen Verweis und die Lizenzangabe der ursprünglichen
% Urheber auf den Materialien für Schülerinnen und Schüler ist erforderlich.
%
% Die Sammlung der Dokumente steht unter
% http://ddi.uni-wuppertal.de/material/materialsammlung/
% zur Verfügung.
%
% Das LaTeX-Paket zum Setzen der Dokumente der Sammlung steht
% unter  http://www.ctan.org/pkg/schule
% zur Verfügung.

\usepackage[pdfauthor={Referendare der Informatikfachseminare Arnsberg, Hamm und Solingen}]{hyperref}
\includexmp{lizenz}
\cclizenz{byncsaeu}
\footerQRLink{materialsammlung_qr_url.pdf}

\svnid{$Id: ab_03_hamming-code.tex 626 2014-05-22 21:36:50Z pieper $}

\dokName{Hamming-Code}
\jahrgang{9}


\begin{document}

\section*{Selbstkorrigierender Hamming-Code}
An einigen Stellen, wie z.\,B. auf CDs ist es wichtig, nicht nur die Fehler in Daten zu erkennen, sondern sie sogar korrigieren zu können. Dieses soll an binären Zahlen überprüft werden. In einer ersten Überlegung könnte man die Daten einfach doppelt aufschreiben. Aus 010 wird dann 001100. 

\begin{smallenumerate}
	\item Gib am Beispiel 000010 begründet an, dass diese diese Variante nicht sinnvoll ist.
\end{smallenumerate}

Statt doppelt kann man die Zeichen auch verdreifachen. So wird aus dem Beispiel 010 der Code 000111000. Damit lassen sich Fehler an einer einzelner Ziffer erkennen und auch beheben.

\begin{smallenumerate}
	\setcounter{enumi}{1}
	\item Gib an, welcher Wert hier übermittelt werden sollte:
	\begin{smallenumerate}
		\item 010000110111 
		\item 111011000101
	\end{smallenumerate}
\end{smallenumerate}

Bei dieser Methode muss aber die dreifache Menge an Daten gespeichert werden um einfache Fehler zu finden. Richard Hamming (1915 -- 1998) hatte dafür eine passende Idee, aus der er den Hamming-Code entwickelte. Er schreibt für jeweils vier Bit insgesamt sieben Bit nach folgendem Muster:

\begin{tabular}{lll}
Nachrichten & & Codewörter \\
1000 & \textrightarrow & 1110000 \\
0100 & \textrightarrow & 1001100 \\
0010 & \textrightarrow & 0101010 \\
0001 & \textrightarrow & 1101001 \\
\end{tabular}

Alle anderen Möglichkeiten werden dadurch gebildet, dass die Codewörter entsprechend miteinander kombiniert werden. So wird aus einer 0 und 0 oder einer 1 und 1 an der gleichen eine 0. Aus 1 und 0 wird eine 1. So ist für 1001 der Code 0011001.

\begin{smallenumerate}
	\setcounter{enumi}{2}
	\item Gib für alle anderen Kombinationen die genauen Codewörter an.
\end{smallenumerate}

Wird ein Bit falsch übermittelt, so kann man dadurch auf die richtigen Daten schließen, indem man den empfangenen Code mit der Liste vergleicht. Das Codewort, dass die wenigsten Abweichungen hat ist das zugehörige. So ist bei bei 0100111 das mit den wenigsten Änderungen die 0100101.

\begin{smallenumerate}
	\setcounter{enumi}{3}
	\item Suche heraus, welche Daten durch folgende Codewörter übermittelt werden:
	\begin{smallenumerate}
		\item 1011011
		\item 0110101
		\item 0100010
	\end{smallenumerate}
	\item Tausche mit deinen Mitschülern Codewörter aus, deren Werte sie ermitteln müssen.
\end{smallenumerate}

\loesung{
\begin{smallenumerate}
	\item
	\item 
	\item	Alle Codewörter

	\begin{tabular}{lll}
		1111 & \textrightarrow & 1111111 \\
		1110 & \textrightarrow & 0010110 \\
		1101 & \textrightarrow & 1010101 \\
		1100 & \textrightarrow & 0111100 \\
		1011 & \textrightarrow & 0110011\\
		1010 & \textrightarrow & 1011010\\
		1001 & \textrightarrow & 0011001\\
		1000 & \textrightarrow & 1110000\\
		0111 & \textrightarrow & 0001111\\
		0110 & \textrightarrow & 1100110\\
		0101 & \textrightarrow & 0100101\\
		0100 & \textrightarrow & 1001100\\
		0011 & \textrightarrow & 1000011\\
		0010 & \textrightarrow & 0101010\\
		0001 & \textrightarrow & 1101001\\
	\end{tabular}

	\item 
	\begin{smallenumerate}
		\item 1010
		\item 0101
		\item 0010
	\end{smallenumerate}
\end{smallenumerate}
}

\end{document}