Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
se:informationstheorie [2009-02-21 18:40] stefan angelegt |
se:informationstheorie [2014-04-05 11:42] |
||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ====== Informationstheorie und Codierung ====== | ||
- | ===== Überblick ===== | ||
- | * Quellencodierung beseitigt Redundanz in der Nachricht | ||
- | * Kanalcodierung fügt der Nachricht wieder Redundanz hinzu (z.B. zur Fehlerkorrektur) | ||
- | |||
- | ===== Informationstheorie ===== | ||
- | * basiert auf grundlegenden Arbeiten von Shannon | ||
- | * eine **Quelle** liefert informationskennzeichnende **Zeichen** x<sub>i</sub> aus einem q Zeichen umfassenden **Alphabet** X mit gewissen Wahrscheinlichkeiten | ||
- | * bei **stationäre Quellen** sind die Wahrscheinlichkeiten, mit denen die Quelle Zeichen abgibt nicht von der Zeit abhängig | ||
- | * bei **gedächtnislosen Quellen** sind die Wahrscheinlichkeiten der Zeichen unabhängig von zuvor oder im Anschluss gesendeten Zeichen | ||
- | * aus den Elementen des Zeichenvorrats können **Worte** w<sub>i</sub> der Länge m<sub>i</sub> gebildet werden. Es lassen sich q<sup>m</sup> verschiedene Worte gleicher Länge m herstellen | ||
- | * eine **Codierung** ist die Vorschrift zur eindeutigen Abbildung der Zeichen eines Zeichenvorrats A auf Codeworte, die aus den Zeichen eines Zeichenvorrats B gebildet werden: C(x<sub>i</sub>) = w<sub>i</sub> | ||
- | * Beispiele für Codes: Morse-Code, ASCII-Code, Dezimal-, Oktalzahlen etc. | ||
- | * **Information** ist Abbau von Ungewissheit (Beispiel Zufallsexperiment: Ausgang vorher unbekannt, danach bekannt) | ||
- | * **Informationsgehalt** I(x<sub>i</sub>)/bit = -ld p(x<sub>i</sub>) | ||
- | * I(x<sub>i</sub>, x<sub>j</sub>) = I(x<sub>i</sub>) + I(x<sub>j</sub>) | ||
- | * der Informationsgehalt ist umso größer, je unwahrscheinlicher das Zeichen ist | ||
- | * jedes Zeichen eines binären Zeichenvorrats hat bei gleichwahrscheinlichem Auftreten einen Informationsgehalt von -ld (0,5) = 1 | ||
- | * die **Entropie H** ist der mittlere Informationsgehalt der Zeichen einer Quelle -> Maß für statistische Unordnung bzw. Unsicherheit | ||
- | * {{:se:entropie.jpg|}} | ||
- | * die Entropie ist der Erwartungswert des Informationsgehalts | ||
- | * die Entropie wird maximal, wenn alle Zeichen eines Zeichenvorrats gleich wahrscheinlich sind, Bezeichnung: H<sub>max</sub> oder H<sub>0</sub> | ||
- | * die maximale Entropie wird auch als **Entscheidungsgehalt** einer Quelle bezeichnet | ||
- | * der Unterschied zwischen H(x) und H<sub>0</sub> wird als **Redundanz** bezeichnet: p = H<sub>0</sub> - H(x) | ||
- | * eine Redundanz kann auch für Codes angegeben werden: p<sub>code</sub> = L - H(x) mit L = mittlere Codewortlänge | ||
- | * relative Coderedundanz oder Weitschweifigkeit: (L - H(x)) / L, Codeeffizienz: H(x) / L | ||
- | * eine Quelle, deren Gedächtnis K Zeichen in die Vergangenheit reicht, wird als Markov-Quelle K-ter Ordnung bezeichnet | ||
- | * allg. Markov-Quelle = Markov-Quelle 1. Ordnung, gedächtnislose Quelle = Markov-Quelle 0. Ordnung | ||
- | * die **bedingte Entropie** ist der Mittelwert (über alle Zustände) des mittleren Informationsgehalts eines Zeichens, das in einem bestimmten Zustand der Quelle abgegeben wird | ||
- | * {{:se:bedingteentropie.jpg|}} |