Redundanz (Informationstheorie)

Eine Kommunikation lässt sich durch redundante Informationen fehlertolerant über einen Informationskanal durchführen, da unter Umständen verloren gegangene oder verfälschte Teilinformationen von dem Empfänger aus ihrem Kontext rekonstruiert werden können. Ein Maß für die Fehlertoleranz ist die Hamming-Distanz.

Sei ${\displaystyle Z}$ ein Alphabet und ${\displaystyle z\in Z}$

${\displaystyle C(z)}$ bezeichnet das zu ${\displaystyle z}$ gehörende Codewort

${\displaystyle l(z)}$ bezeichnet die Länge von ${\displaystyle C(z)}$

Die mittlere Codewortlänge ${\displaystyle L(C)}$ eines Quell-Codes ${\displaystyle C(z)}$ mit der Wahrscheinlichkeitsverteilung ${\displaystyle p(z)}$ ist gegeben durch:

${\displaystyle L(C)=\sum _{i=1}^{|Z|}{l(z_{i})p(z_{i})}}$

Die Redundanz des Codes ist die Differenz zwischen mittlerer Codewortlänge ${\displaystyle L(C)}$ und Entropie ${\displaystyle H(X)}$. (Beispiel: Huffman-Kodierung für optimales (= minimales) ${\displaystyle L(C)}$).

${\displaystyle R_{\text{Code}}=L(C)-H(X)\,}$

Die Redundanz der Quelle ist die Differenz zwischen maximaler Entropie ${\displaystyle H_{\text{max}}(X)=\log _{2}|Z|}$ und der Entropie ${\displaystyle H(X)}$ der Nachrichtenquelle.

${\displaystyle R_{\text{Quelle}}=\log _{2}|Z|-H(X)\,}$

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

In Datenstrukturen von Programmen und Datenbanken können Redundanzen zu Programmfehlern führen. Der Programmierer muss darauf achten, dass er bei allen Änderungen auch die redundanten Daten konsistent hält. Dies erfordert einen hohen Synchronisationsaufwand. Je größer das Projekt ist und je länger an dem Projekt entwickelt wird, desto schwieriger gestaltet sich dies. Wenn mehrere Programmierer unwissenderweise unabhängig voneinander an redundanten Daten arbeiten, so ist es fast unmöglich, die Änderungen konsistent zu halten.

Es gibt einige Fälle, in denen absichtlich herbeigeführte Datenredundanz die Rechenzeit der Software reduziert. Sie kann durch gezielte Denormalisierung erreicht werden. Diese genau kalkulierte und gewollte Redundanz ist jedoch deutlich zu unterscheiden von nachlässig entstandener Redundanz, weil jemand die Normalisierungsregeln nicht anwendet. Denormalisierungen steigern in der Regel die Leseleistung, aber verschlechtern die Schreibleistung.