Diskrete Mathematik

Quelle: Wikipedia. Seiten: 45. Kapitel: Pascalsches Dreieck, Magisches Quadrat, Hamming-Code, Vollkommen perfektes magisches Quadrat, Hamming-Abstand, Satz von Van der Waerden, Reed-Muller-Code, Matroid, Reed-Solomon-Code, Polyomino, Topologische Kombinatorik, Trinomial Triangle, Faulhabersche Formel, Satz von Schur, On-Line Encyclopedia of Integer Sequences, ASEP, Erzeugende Funktion, Preimage-Angriff, Kollisionsangriff, Golomb-Code, Schubfachprinzip, FHP-Modell, Schurzahlen, Harmonisches Dreieck, Barker-Code, Pascalsche Pyramide, Magischer Würfel, Forschungsinstitut für Diskrete Mathematik, Alphabet, Färbung, Conways LUX-Methode zur Erzeugung Magischer Quadrate, Digitale Geometrie, Hamming-Ähnlichkeit, Einfarbige Lösung, Magisches Sechseck, Konrad-Zuse-Zentrum für Informationstechnik Berlin, Plotkin-Grenze, MDS-Code, Helly-Eigenschaft, Singleton-Schranke, Inversion, Reihenfolgeproblem. Auszug: Der Hamming-Code ist ein von Richard Hamming entwickelter linearer fehlerkorrigierender Blockcode, der in der digitalen Signalverarbeitung und der Nachrichtentechnik zur gesicherten Datenübertragung oder Datenspeicherung verwendet wird. Beim Hamming-Code handelt es sich um eine Klasse von Blockcodes unterschiedlicher Länge, welche durch eine allgemeine Bildungsvorschrift gebildet werden. Die Besonderheit dieses Codes besteht in der Verwendung mehrerer Paritätsbits. Diese Bits ergänzen jeweils unterschiedlich gewählte Gruppen von den die Information tragenden Nutzdatenbits. Durch eine geschickte Wahl der Gruppierung, deren mathematische Grundlagen im Folgenden beschrieben sind, ist nicht nur eine Fehlererkennung, sondern auch eine Fehlerkorrektur der übertragenden Datenbits möglich. Die einzelnen Codewörter des Hamming-Codes weisen einen Hamming-Abstand von drei auf. Durch diesen Unterschied von jeweils drei Bitstellen kann der Decoder einen oder zwei Bitfehler in einem Datenblock immer erkennen, aber nur maximal einen Bitfehler korrigieren. Bei zwei Bitfehlern liefert der Decoder ein gültiges, aber falsches Codewort. Der erweiterte Hamming-Code mit einem Hamming-Abstand von vier kann durch eine zusätzliche Paritystelle bis zu drei Bitfehler in einem Datenblock erkennen, aber auch nur einen Bitfehler korrigieren. Zwei Bitfehler werden bei dem erweiterten Hamming-Code als fehlerhaftes (ungültiges) Codewort erkannt, welches nicht korrigierbar ist. In den 1940er Jahren arbeitete Richard Hamming in der Firma Bell Labs an einem Computer namens Bell Model V, welcher mit fehleranfälligen elektromechanischen Relais mit zwei Maschinenzyklen pro Sekunde ausgestattet war. Die zu Dateneingaben verwendeten Lochkarten konnten durch Abnutzung bei der Leseoperation Fehler aufweisen, die zu den normalen Bürozeiten durch Angestellte der Bell Labs von Hand korrigiert werden mussten. Zu den üblichen Arbeitszeiten von Richard Hamming, außerhalb der Bürozeiten und am Wochenende, führten d