Theoretische Grundlagen

Nachdem in Kap.  2 praktische und theoretische Erfahrungen mit Elementen der Codierungstheorie an alltäglichen Codierungen gesammelt wurden, wollen wir in diesem Kapitel grundlegende Begriffe der Codierungstheorie allgemein beschreiben. Dabei werden Wörter als n-Tupel über einem Alphabet A und Codes als „bloße“ Teilmengen das An, also ohne irgendeine Rechenstruktur, aufgefasst. Insbesondere beschränken wir uns auf Wörter der konstanten Länge n, die jeweils eine konstante Anzahl k von zu übermittelnden Nachrichtenzeichen und damit n − k Prüfzeichen enthalten. Man spricht von (n, k)-Blockcodes. Auf die Faltungscodes wird in diesem Buch nicht eingegangen. Diese Prüfzeichen werden der Nachricht gerne vorangestellt oder angehängt. Damit kann nach der Decodierung des gesendeten (gespeicherten) Wortes die Nachricht sofort abgelesen werden (systematische Codierung). Als zentral für die Erkennung und Korrektur von Fehlern erweist sich der dem anschaulichen Abstand nachempfundene Hamming-Abstand zweier Codewörter. Mit ihm kann als eine Decodierungsstrategie die Hamming-Decodierung formuliert werden. Sie erweist sich der Maximum-Likelihood-Decodierung (MLD) als gleichwertig, sofern man annimmt, dass die Übertragungskanäle binär und symmetrisch sind sowie die Fehlerwahrscheinlichkeit je Bit kleiner als 0,5 ist. Dies ist in der Praxis oft der Fall. Um der bei der Hamming-Decodierung möglichen „sinnlosen“ Decodierung entgegenzuwirken, wird die Strategie der Bounded-Distance-Decodierung (BD) eingeführt und eine Schranke für den Abbruch einer Decodierung entwickelt. Dazu und zur Definition von t-fehlererkennenden bzw. t-fehlerkorrigierenden Codes erweist sich der ebenfalls der Anschauung entliehene Begriff der t-Umgebung bzw. der „Kugelumgebung“ eines Wortes als nützlich. Der Minimalabstand d eines Codes zeigt sich als entscheidende Größe für die Fehlerkorrekturkapazität. Damit werden die in Kap.  2 vorgestellten Codes untersucht. Die Informationsrate eines Codes stellt eine weitere Maßzahl für die „Güte“ eines Codes dar. Es wird auf die Frage eingegangen, welche Anforderungen ein „guter“ (n, k, d)-Blockcode erfüllen soll. Dazu werden zwei der wichtigsten Schranken der Codierungstheorie entwickelt, die Hamming- und die Singleton-Schranke. Wird in den entsprechenden Ungleichungen die Gleichheit erreicht, so spricht man von perfekten Codes bzw. von optimalen Codes (MDS-Codes). Am Ende des Kapitels wird auf die Namensgebung dieser „Maximal Distance Separable“ Codes experimentell eingegangen. Mit dem Wort „optimal“ wird ausgedrückt, dass ein Code die maximale Anzahl von Wörtern enthält. Mit dem Wort „perfekt“ wird ausgedrückt, dass der Idealfall der vollständigen Überdeckung der Wortmenge An durch elementfremde Kugeln erreicht wird. In solchen Codes ist die Decodierungsstrategie „Decodierung zum Kugelmittelpunkt“ möglich. Auf die zur Menge der perfekten Codes gehörigen Hamming-Codes und die Golay-Codes wird in Kap.  4 eingegangen.