Redundanz (Informationstheorie)

Grundidee und Bedeutung

Redundanz bezeichnet in der Informationstheorie Informationen oder Daten, die in einer Informationsquelle mehrfach vorhanden sind. Eine Informationseinheit ist redundant, wenn sie ohne Informationsverlust weggelassen werden kann. Das Erkennen und Entfernen solcher mehrfach vorhandenen Information heißt Deduplikation.

Wichtig ist Redundanz, weil sie je nach Zusammenhang entweder nützlich oder störend sein kann. Bei der Nachrichtenübertragung kann sie absichtlich eingesetzt werden, um Fehler zu erkennen oder sogar zu korrigieren. In Datenbanken und Datenstrukturen versucht man dagegen meist, Redundanzen zu vermeiden, weil sie Speicherplatz verbrauchen und widersprüchliche Daten erzeugen können.

Redundanz bei Nachrichten

Bei der Nachrichten- und Informationsübertragung ist der redundante Teil einer Nachricht der Teil, der keine neue Information enthält. Dieser Teil kann eine Funktion der eigentlichen Information in der Nachricht sein. In technischen Anwendungen wird Redundanz gezielt hinzugefügt, damit Übertragungsfehler erkannt werden können.

Je stärker die Redundanz ist, desto mehr ist möglich: Eine geringe Redundanz kann helfen, Fehler zu erkennen; eine stärkere Redundanz kann zusätzlich erlauben, Fehler zu korrigieren. Dadurch steigt die Qualität der Übertragung, weil weniger Fehler übrig bleiben. Gleichzeitig sinkt die Effizienz, weil mehr Daten übertragen werden müssen. Redundanz verbessert also die Qualität auf Kosten der Quantität, konkret durch eine höhere Datenrate.

Wie viel Redundanz sinnvoll ist, hängt von der Fehlertoleranz der Anwendung ab. Bei Bankgeschäften oder in der Raumfahrt kann schon ein einziges umgekipptes Bit schwere Folgen haben. Bei Internettelefonie oder DVB kann dagegen sogar der dauernde Verlust ganzer Pakete unter Umständen ohne Bedeutung sein.

Fehlertoleranz und Codegrößen

Fehlertoleranz bedeutet, dass eine Kommunikation trotz verlorener oder verfälschter Teilinformationen funktionieren kann. Das gelingt durch redundante Informationen: Der Empfänger kann fehlende oder veränderte Teile unter Umständen aus dem Zusammenhang rekonstruieren. Ein Maß für diese Fehlertoleranz ist die Hamming-Distanz.

Für Codes wird die mittlere Codewortlänge verwendet. Sei Z ein Alphabet und z ∈ Z. C(z) bezeichnet das zu z gehörende Codewort, l(z) bezeichnet die Länge von C(z). Die mittlere Codewortlänge L(C) eines Quell-Codes C(z) mit der Wahrscheinlichkeitsverteilung p(z) ist:

L(C)=∑_{i=1}^{|Z|} l(z_i)p(z_i)

Diese Formel bedeutet: Man multipliziert die Länge jedes Codewortes mit der Wahrscheinlichkeit des zugehörigen Zeichens und summiert alle Beiträge. Häufig vorkommende Zeichen beeinflussen die mittlere Codewortlänge also stärker als seltene Zeichen.

Redundanz eines Codes

Die Redundanz eines Codes ist die Differenz zwischen der mittleren Codewortlänge L(C) und der Entropie H(X). Die Entropie beschreibt dabei den Informationsgehalt beziehungsweise die theoretische Untergrenze für die mittlere Länge einer optimalen Kodierung. Als Beispiel nennt der Artikel die Huffman-Kodierung für ein optimales, also minimales, L(C).

Die Formel für die Code-Redundanz lautet:

R_Code = L(C) - H(X)

Daneben gibt es die Redundanz der Quelle. Sie ist die Differenz zwischen der maximalen Entropie H_max(X)=log_2|Z| und der tatsächlichen Entropie H(X) der Nachrichtenquelle:

R_Quelle = log_2|Z| - H(X)

Da die Codewortlänge nicht kleiner als die Entropie sein kann, ist Redundanz nie negativ. Sie ist also mindestens 0.

Formen der Redundanz in der Kodierung

In der Kodierungstheorie werden zwei Formen der Redundanz unterschieden.

Die Verteilungsredundanz entsteht dadurch, dass die einzelnen Zeichen eines Alphabets unterschiedlich häufig auftreten. Wenn manche Zeichen viel wahrscheinlicher sind als andere, enthält diese ungleiche Verteilung eine Art Regelmäßigkeit, die bei der Kodierung ausgenutzt werden kann.

Die Bindungsredundanz entsteht dadurch, dass nach bestimmten Zeichen bestimmte andere Zeichen besonders wahrscheinlich sind. Das bedeutet: Nicht nur die Häufigkeit einzelner Zeichen ist wichtig, sondern auch ihr Zusammenhang mit benachbarten Zeichen. Ein Beispiel ist ein deutscher Text, in dem auf ein q fast immer ein u folgt.

Redundanz in Datenbanken

In Datenbanken und Datenstrukturen von Programmen versucht man Redundanzen möglichst vollständig zu vermeiden. Der Grund ist, dass sie mehr Speicherplatz benötigen und zu Inkonsistenzen führen können. Inkonsistenz bedeutet, dass mehrfach gespeicherte Daten nicht mehr übereinstimmen. Redundanzen zählen daher zu den Anomalien. Redundanzfreiheit gilt als Grundprinzip für ein logisches Datenmodell.

Ein wichtiges Verfahren zur Vermeidung von Redundanz ist die Normalisierung des Datenbankschemas. Dabei wird die Struktur der Daten so gestaltet, dass unnötige Mehrfachspeicherungen weitgehend vermieden werden. Manche Redundanzen sind jedoch unvermeidbar, zum Beispiel Schlüsselredundanzen, und werden als notwendiges Übel akzeptiert. Andere Redundanzen nimmt man hin, wenn ihre Vermeidung im Verhältnis zum Problem zu aufwendig wäre. Beispiele sind das mehrfache Auftreten eines Attributwertes oder die doppelte Speicherung des Namens Müller für Herrn Müller und für Frau Müller.

Die bewusste Inkaufnahme von Redundanz zur Verbesserung der Leseleistung heißt Denormalisierung. Sie kann sinnvoll sein, wenn absichtlich herbeigeführte Datenredundanz die Rechenzeit einer Software reduziert. Diese geplante Redundanz muss aber von nachlässig entstandener Redundanz unterschieden werden, etwa wenn Normalisierungsregeln nicht angewendet werden.

Redundanz hat in Datenbanken auch Nachteile: Programmierer müssen bei jeder Änderung darauf achten, alle redundanten Daten konsistent zu halten. Das erfordert hohen Synchronisationsaufwand. Je größer ein Projekt ist und je länger daran entwickelt wird, desto schwieriger wird dies. Wenn mehrere Programmierer unabhängig voneinander an redundanten Daten arbeiten, ist es fast unmöglich, Änderungen konsistent zu halten. Denormalisierungen verbessern in der Regel die Leseleistung, verschlechtern aber die Schreibleistung.