Aus der Einleitung von

Werner Heise, Pasquale Quattrocchi :
Informations- und Codierungstheorie.

Mathematische Grundlagen der Daten-Kompression
und -Sicherung in diskreten Kommunikationssystemen.

3. Aufl., Springer-Verlag, Berlin-Heidelberg 1995

Selten läßt sich die Geburt einer mathematischen Disziplin exakt datieren. Mit der Informations- und Codierungstheorie ist das anders. 1948 erschien im Juli-Heft des Bell Systems Technical Journal 27, 379-423, der erste Teil von Claude E. Shannons Artikel "A mathematical theory of communication". Da heißt es:

,,Das grundlegende Problem der Kommunikation besteht darin, an einer Stelle entweder genau oder angenähert eine Nachricht wiederzugeben, die an einer anderen Stelle ausgewählt wurde."

Die Übermittlung von Nachrichten mittels eines Kommunikationssystems kann man sich räumlich (Rundfunk, Telegraphie, Fernschreiber, Telefon, Fernsehen usw.) oder zeitlich (Tonband, Schallplatte, Film, Videoband und so weiter) vorstellen. Um möglichst viele (bislang technisch realisierte oder nicht realisierte) Systeme zu erfassen, werden die Baueinheiten eines Kommunikationssystems als schwarze Kästen mit gewissen Ein- und Ausgängen betrachtet. Diese schwarzen Kästen nehmen Daten auf, speichern und verarbeiten sie und geben dann wieder Daten aus. Die Baueinheiten werden durch ihre Aufgaben und Wirkungen als Funktionseinheiten definiert und beschrieben. Ein abstraktes Kommunikationssystem besteht aus den folgenden Baueinheiten:

1.Nachrichtenquelle[message source],
2.Quellencodierer[source encoder],
3.Kanalcodierer[channel encoder],
4.Kanal[channel],
5.Rauschquelle[noise],
6.Kanaldecodierer[channel decoder],
7.Quellendecodierer[source decoder],
8.Nachrichtensenke[message sink].

Im folgenden beschreiben wir vorbehaltlich späterer Präzisierung und Einengung der Bedingungen den Nachrichtenfluß in diesem Kommunikationssystem.

Die (diskrete und stationäre) Nachrichtenquelle (1) verfügt über einen gewissen endlichen Nachrichtenvorrat. Die einzelnen Nachrichten werden in einem stochastischen Proze mit gewissen, als bekannt vorausgesetzten Wahrscheinlichkeiten aus dem Vorrat ausgewählt; diese Auswahl geschieht unabhängig vom konkreten Zeitpunkt. Mit einem bestimmten Signalisiertempo gibt sie die als Signale dargestellten ausgewählten Nachrichten weiter. Der Informationsgehalt einer Nachricht mißt deren Seltenheitswert; häufige Nachrichten haben einen geringen Informationsgehalt.

Der Quellencodierer (2) setzt die Darstellung der Nachrichten der physikalischen Auslegung des Kanals entsprechend in Folgen von solchen Signalen um, die der Kanal übertragen kann. Der Kanal kann pro Sekunde nur eine gewisse Anzahl von Signalen aufnehmen. Um der Nachrichtenquelle ein möglichst hohes Signalisiertempo zu ermöglichen, wird der Quellencodierer seine Eingangssignale in solche Folgen von Ausgangssignalen übersetzen, daß relativ häufige Nachrichten im Gegensatz zu den seltenen Nachrichten nur wenig Zeit zur Übertragung im Kanal beanspruchen. Die Funktion des Quellencodierers wird als Informationsverdichtung der Nachrichten oder Datenkompression bezeichnet: Die Darstellung wird von unnützer Redundanz befreit; bei der Nachrichtenübertragung kommt es uns nur auf den Transport des Informationsgehaltes der Nachrichten an. Der Kanal (4) wird als das von den anderen Baueinheiten unabhängige Herzstück des Kommunikationssystems angesehen: So wie man ein Tonband zu verschiedenartigsten Zwecken verwenden kann, so lassen sich an den Kanal die unterschiedlichsten Nachrichtenquellen und -senken anschließen. Wir definieren als Zeiteinheit die Zeitspanne, die der Kanal im Mittel benötigt, um am Eingang ein zulässiges Signal aufzunehmen. Beim Vorhandensein einer Rauschquelle (5) werden diese Signale während der Übertragung mit einer statistisch ermittelten Wahrscheinlichkeit gestört und verstümmelt: In eine Telegraphenleitung schlägt der Blitz ein, der magnetisierende Belag eines Tonbandes hat Fehler, eine Schallplatte ist verstaubt. Der Vorrat der Ausgangssignale eines Kanals wird sich also im allgemeinen von dem Vorrat der zulässigen Eingangssignale unterscheiden. Die Auswahl der Signale, die wir während einer konkreten Nachrichtenübertragung am Ausgang des Kanals beobachten, hängt bedingt durch die Aktivität der Rauschquelle statistisch von der Auswahl der Eingangssignale ab. Die als Signale dargestellten Nachrichten verlieren durch die Störung im Kanal einen gewissen Informationsgehalt, die Äquivokation. Der verbleibende theoretisch nutzbare Anteil des Informationsgehaltes der Nachrichten wird als Transinformation bezeichnet. Die Rauschquelle bewirkt nicht nur einen Informationsverlust, sondern kann selbst als Nachrichtenquelle betrachtet werden; die von ihr verursachten Störungen sind Signale, die ihrerseits Nachrichten mit einem gewissen Informationsgehalt repräsentieren. Den Kanal kümmert es wenig, daß der Benutzer des Kommunikationssystems an dieser Information überhaupt nicht interessiert ist. Er addiert diesen für den Benutzer irrelevanten und daher als Irrelevanz bezeichneten Informationsgehalt zur Transinformation. Der am Ausgang des Kanals beobachtete Informationsgehalt entstammt also nur zu einem Teil der Nachrichtenquelle; es erscheint unmöglich, die Transinformation aus diesem Informationsgehalt herauszufiltern. Als Kapazität des Kanals werden wir den Transinformationsgehalt eines "durchschnittlichen", in den Kanal eingegebenen Signals bei Nutzung des Kanals durch eine optimale Nachrichtenquelle definieren.

Es ist die Aufgabe des Kanalcodierers (3), trotz dieser widrigen Umstände eine zumindest einigermaßen zuverlässige Nachrichtenübertragung zu gewährleisten. Er speichert die eingehenden Signale jeweils in Blöcken aus je k Signalen und fügt je nach Zusammensetzung dieser Blöcke planmäßig r := n - k Kontrollsignale hinzu. Unter Beibehaltung des gesamten Informations- gehaltes, aber unter Einbuße von Informationsgehalt pro Signal, gibt der Kanalcodierer dann eine Folge von Blöcken aus je n Signalen an den Kanal ab. Das Verhältnis k/n wird als Informationsrate bezeichnet. Der Shannonsche Kanalcodierungssatz besagt, daß es bei einem gestörten Kanal der Kapazität K und einer vorgegebenen Zahl R < K möglich ist, die Nachrichten mit einer Informationsrate mindestens gleich R so zu codieren, daß bei der Nachrichtenübertragung ein beliebiger Sicherheitsgrad erreicht wird. Allerdings geben die bekannten Beweise dieses Satzes keine konkreten Hinweise zur praktischen Konstruktion eines geeigneten Kanalcodierers: Die Anzahl der Signale, die zu Blöcken zusammengefaßt werden müßten, wüchse schon bei kleinen Systemen in astronomische Höhen. Die Anzahl der benötigten Speicherplätze läge jenseits jeder technischen Akzeptabilität. Wichtiger als der Kanalcodierungssatz selber ist seine Umkehrung: Bei einer Informationsrate über der Kanalkapazität sind der Zuverlässigkeit der Nachrichtenübertragung Schranken gesetzt. Die Herabsetzung der Informationsrate unter die Kapazität des Kanals bedeutet zwangsläufig eine Herabsetzung des Signalisiertempos der Nach-richtenquelle. In der Theorie der fehlererkennenden und fehlerkorrigierenden Codes werden Methoden und Verfahren bereitgestellt, mit denen der Kanalcodierer unter technisch realisierbaren Bedingungen arbeiten kann.

Der Kanaldecodierer (6) speichert die vom Kanal ausgegebenen Signale wieder in Blöcken von je n Signalen und bemüht sich unter Ausnutzung seiner Kenntnis des vom Kanalcodierer benutzten Verfah-rens trotz der von der Rauschquelle verursachten Störungen die k Signale zu rekonstruieren, die der Kanalcodierer ursprünglich zu einem Block zusammenfaßte. Wenn ihm das nicht gelingt, begeht er einen Decodierfehler. Wenn der Kanaldecodierer seine Unzulänglichkeit erkennt, so kann er eine Fehlermeldung weiterleiten. Dies ist besonders dann angezeigt, wenn das Kommunikationssystem Rückfragen zuläßt. Ein Decodierfehler kann aber auch darin bestehen, daß der Kanaldecodierer einen falschen Block von k Signalen rekonstruiert. In diesem Fall werden einige - aber nicht notwendig alle - der k in den Kanalcodierer eingespeisten Signale von Übertragungsfehlern betroffen. Mehr noch als die Decodierfehlerwahrscheinlichkeit stellt die Übertragungsfehlerwahrscheinlichkeit ein Maß für die Sicherheit der Nachrichtenübertragung des Teilsystems Kanalcodierer-Kanal-Kanaldecodierer dar. Bei empfindlichen Kommunikationssystemen können Decodierfehler katastrophale Folgen haben.

Der Quellendecodierer (7) übersetzt die ihm vom Kanaldecodierer übermittelten Signale in solche Signale, wie sie die Nachrichtenquelle aussandte, und gibt sie an den Empfänger, die Nachrichtensenke (8), weiter. Wenn aber der Kanaldecodierer einen Decodierfehler beging, so kann der Quellendecodierer aus dem Takt fallen und die gesamte weitere Nachrichtensendung verderben. Der gleiche Effekt kann auftreten, wenn im System Synchronisationsfehler vorkommen, das heißt, wenn der Kanal Signale verschluckt oder einfügt. (Dank der genauen Uhren, die heutzutage als Taktgeber benutzt werden, sind in der Datenverarbeitung Systeme mit Synchronisationsfehlern selten.) Wenn mit Decodierfehlern des Kanaldecodierers gerechnet werden muß, so empfiehlt es sich, unter eventuellem Verzicht auf maximale Datenkompression, den Quellencodierer und -decodierer mit selbststabilisierenden Verfahren wie Block-Codes oder Komma-Codes (die auch gegen Synchronisationsfehler helfen) arbeiten zu lassen.

Die Informationstheorie wird als Theorie der Übertragung des Informationsgehaltes von Daten über ein Kommunikationssystem im wesentlichen von wahrscheinlichkeitstheoretischen Methoden bestimmt. Die Codierungstheorie (im engeren Sinne) benutzt als Theorie der fehlererkennenden und fehlerkorrigierenden Codes hauptsächlich kombinatorische und algebraische Methoden. Der nur eine halbe Seite umfassende Artikel Notes on digital coding von Marcel J. E. Golay aus dem Jahre 1949 und die aus patentrechtlichen Gründen zeitverzögert 1950 erschienene Arbeit Error-detecting and error-correcting codes von Richard W. Hamming haben für die Codierungstheorie eine ähnliche Bedeutung wie Shannons oben erwähnter Artikel für die Informationstheorie. Motiviert durch den nichtkonstruktiven Charakter des Shannonschen Kanalcodierungssatzes, entdeckt Golay - ausgehend von einem von Shannon angegebenen Beispiel (des binären (7,4)-Hamming-Codes in heutiger Sprache) - im wesentlichen alle linearen perfekten Codes (von ihm "verlustlose Codes" genannt). Hamming wurde bei seiner Forschungstätigkeit in den Bell-Laboratorien zum Nachdenken über in der Praxis anwendbare Methoden der Datensicherung angeregt: Bei den alten Relais-Großrechenanlagen mußte mit etwa einer Fehlfunktion auf zwei bis drei Millionen Relais-Operationen gerechnet werden. Mit Hilfe einfacher fehlererkennender Verfahren - wie zum Beispiel der 2-aus-5-Codierung - wurden solche Störungen erkannt; das laufende Programm wurde mit einer Fehlermeldung unterbrochen. Trotz der gesteigerten Zuverlässigkeit der neuen Schaltelemente erzwangen die größeren Dimensionen und die erhöhten Rechengeschwindigkeiten der moderneren Computer die Entwicklung besserer Fehlerbekämpfungsmethoden durch automatische Korrektur; den Luxus, kostbare Rechenzeit wegen eines Stillstands des Rechners nach einem Programm-Abbruch zu vergeuden, wollte und konnte man sich nicht mehr leisten. Hamming entdeckte unabhängig von Golay die später nach ihm benannten 1-fehlerkorrigierenden binären Hamming-Codes und beschrieb die Grundzüge einer Strukturtheorie der fehlererkennenden und fehlerkorrigierenden Codes.

Ein Code muß stets als integraler Bestandteil des Kommunikationssystems betrachtet werden: In Abhängigkeit vom verwendeten Code müssen Codierer und Decodierer technisch ausgelegt werden. In der Praxis überwiegt der durch die Komplexität der verwendeten Funktionseinheiten bedingte technische Aufwand in seiner Bedeutung die Beschränkung der Codierungsmöglichkeiten, wie sie nach dem Shannonschen Kanalcodierungssatz durch die Kanalkapazität dem Kommunikationssystem auferlegt sind. In diesem Zusammenhang ist es nützlich, sich an eine alte Bauernregel zu erinnern, die besagt, daß sich die Lösung eines konkreten Problems um so leichter finden lät, je reichhaltiger die Automorphismengruppe der dieser Aufgabe zu Grunde liegenden mathematischen Struktur ist. In der algebraischen Codierungstheorie befaßt man sich mit der Konstruktion mathematisch strukturierter Codes und untersucht natürlich auch die Beschränkungen, denen Codes mit gewissen Eigenschaften unterworfen sind.

Werner Heise, München, 22. September 1995