Vorlesung Informatik 1 - Teil B: Theorie
1.5 Codierung, Entscheidungsgehalt
Codierung (Code): Abbildung eines Zeichenvorrates auf einen Ur-Zeichenvorrat.
In der Informatik sind Binärcodierung wichtg (Urvorrat hat zwei Zeichen)
Beispiel: Urvorrat U = { 0,1 }
Zielvorrat Z = { N, O, S, W
}
Eine Binärcodierung ist so etwas wie eine Maschine, die mit ja/nein Entscheidungen ein Element
des Zielvorrates findet:
Möglicher Code: 00=N 01=O 10=S 11=W Codierung mit fester Wortlänge 2 Bit
Anderer Code: 00=N 01=O 001=S 0001=W Codierung mit variabler Wortlänge
Wir betrachten zunächst Binärcodierungen mit fester Wortlänge:
Frage: wie viele Bits sind für die
Codierung des Zeichenvorrates Z notwendig?
Wir berechnen zunächst den mittleren Entscheidungsgehalt eines Zeichens aus Z:
\( h = log_2 |Z| [bit] \)
wobei |Z| die Mächtigkeit des Zeichensatzes ist (Anzahl Zeichen). Er ist ein Maß für den
Informationsgehalt der Codierung und wird in [bit] (kleingeschrieben!) gemessen. Die Einheit Shannon [Sh]
statt [bit] ist heute nicht mehr gebräuchlich.
Damit berechnet sich die Zahl der Bits zu:
\( n_{bit} = \lceil log_2 |N| \rceil \)
Die beiden halben Klammern ⌈ ⌉ stehen für die nächst höhere ganze Zahl.
Für die Berechnung des
binären Logarithmus ist folgende Beziehung hilfreich: \( log_2 x = \frac{log_{10} x}{log_{10} 2} \)
Jedes zusätzliche Bit verdoppelt die Anzahl der Möglichkeiten.
Beispiel: Z = {0, 1, 2, 3, ... , 9 } |Z| = 10
\( n_{bit} = \lceil log_2 10 \rceil = \lceil 3.32 \rceil = 4 [Bit] \) pro Zeichen
Um ein Zeichen eines Zeichensatzes mit 10 Zeichen binär mit fester Wortlänge zu codieren brauchen wir 4 Bit!
Redundanz: Nicht genuzter Entscheidungsgehalt einer Codierung.
Im Beispiel
ist r=4-log2 10 = 0.68 [bit] pro Zeichen
Hat man eine Nachricht aus Zeichen eines Zeichensatzes, berechnet sich der Informationsgehalt der Nachricht aus der Anzahl der Zeichen multipliziert mit dem Informationsgehalt eines Zeichens.
Diese Berechnungen gelten unter der Annahme, dass alle Zeichen des Zeichensatzes mit gleicher Wahrscheinlichkeit auftreten!
Den Fall unterschiedlicher Auftrittswahrscheinlichkeiten behandeln wir später.