Benutzer-Werkzeuge
se:informationstheorie
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
|
se:informationstheorie [2009-02-24 12:45] stefan |
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 | ||
| - | * ein **optimaler Code** besitzt unter bestimmten Randbedingungen (insb. ganzzahlige Wortlängen) die geringstmögliche Redundanz bzw. größtmögliche Effizienz | ||
| - | * 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 H(x|s)** ist der Mittelwert (über alle Zustände) des mittleren Informationsgehalts eines Zeichens, das in einem bestimmten Zustand der Quelle abgegeben wird | ||
| - | * {{:se:bedingteentropie.jpg|}} | ||
| - | * die bedingte Entropie kann nie größer werden als die "normale" Entropie | ||
| - | * die **Verbundentropie (H(x,s)** ist der mittlere Informationsgehalt von ganzen Ausgangsfolgen einer Markov-Quelle | ||
| - | * {{:se:verbundentropie.jpg|}} | ||
| - | * {{:se:verbundentropie2.jpg|}} | ||
| - | * H(x,s) = H(x|s) + H(s) wobei H(s) wiederum eine Verbundentropie ist | ||
| - | * beim Erhöhen der Nachrichtenlänge nähert sich der mittlere Informationsgehalt pro Zeichen asymptotisch der bedingten Entropie | ||
| - | |||
| - | ===== Übertragungskanäle ===== | ||
| - | * abstraktes Kanalmodell des **diskreten Kanals**: x -> Modulator -> physikalischer Kanal -> Demodulator -> y | ||
| - | * die Aufgabe von Modulator und Demodulator ist es, einen möglichst guten diskreten Kanal zu bilden | ||
| - | * die Aufgabe von Codierer und Decodierer ist es, eine zuverlässige Übertragung über diesen Kanal zu gewährleisten | ||
| - | * Demodulationsverfahren | ||
| - | * **Hard-Decision**: Ein- und Ausgabealphabet sind identisch | ||
| - | * **Soft-Decision**: liefert kontinuierlich verteilte Ausgangswerte | ||
| - | * bei **Kanälen mit Gedächtnis** hängt die Wahrscheinlichkeit des Ausgangszeichens nicht nur vom Eingangszeichen ab, sondern auch von den K vorangehenden Zeichen | ||
| - | * diskreter gedächtnisloser Kanal = Discrete Memoryless Channel (DMC) | ||
| - | * die **Kanalmatrix** enthält die Wahrscheinlichkeiten für die Ausgangszeichen | ||
| - | * p(y<sub>j</sub>|x<sub>i</sub>) = Wahrscheinlichkeit, dass y<sub>j</sub> empfangen wird, wenn x<sub>i</sub> gesendet wurde | ||
| - | * die Zeilensummen müssen 1 ergeben: 1 = p(y<sub>1</sub>|x<sub>i</sub>) + p(y<sub>2</sub>|x<sub>i</sub>) + ... + p(y<sub>j</sub>|x<sub>i</sub>) | ||
| - | * p(x<sub>j</sub>|y<sub>i</sub>) heißt A-posteriori-Wahrscheinlichkeit, p(x<sub>j</sub>) heißt A-priori-Wahrscheinlichkeit | ||
| - | * der **Detektor** schließt aus dem empfangenen Zeichen y<sub>i</sub> auf das gesendete Zeichen x<sub>j</sub> | ||
| - | * Maximierung der A-posteriori-Wahrscheinlichkeit (Maximum-A-Posteriori-Probability-Detektion: **MAP-Detektion**) p(y<sub>i</sub>|x<sub>j</sub>) * p(x<sub>j</sub>) | ||
| - | * wenn die Quellenstatistik nicht bekannt ist, fällt p(x<sub>j</sub>) weg bzw. ist für alle Eingangszeichen gleich. Dann wird lediglich das Maximum von p(y<sub>i</sub>|x<sub>j</sub>) gesucht -> **Maximum-Likelihood-Detektor** | ||
| - | * Entropien im Kanal | ||
| - | * {{:se:entropienimkanal.jpg|}} | ||
| - | * die **Verbundentropie** des Kanals gibt den mittleren Informationsgehalt eines Ein-/Ausgangszeichenpaares an | ||
| - | * die bedingte Entropie H(x|y) heißt **Rückschlussentropie** oder **Äquivokation** und gibt den zusätzlichen Informationsgehalt eines Eingangszeichens an, wenn man das Ausgangszeichen kennt | ||
| - | * die bedingte Entropie H(y|x) heißt **Streuentropie** oder **Irrelevanz** und gibt den zusätzlichen Informationsgehalt eines Ausgangszeichens an, wenn man das Eingangszeichen bereits kennt | ||
| - | * H(x,y) = H(x|y) + H(y) = H(y|x) + H(x) | ||
| - | * die **Transinformation I(x;y)** ist ein Maß für die mittlere in einem Ausgangszeichen enthaltene relevante Information (mittlerer Informationsgehalt abzüglich Irrelevanz) | ||
| - | * I(x;y) = H(y) - H(y|x) | ||
| - | * {{:se:transinformation.jpg|}} | ||
| - | * Sonderfälle der DMC | ||
| - | * **rauschfreier Kanal**: Kanalmatrix hat in jeder Zeile nur einen Wert != 0 | ||
| - | * **verlustfreier Kanal**: Kanalmatrix hat in jeder Spalte nur einen Wert != 0 | ||
| - | * **total gestörter Kanal**: Ein- und Ausgangszeichen sind statistisch unabhängig voneinander | ||
| - | * **symmetrischer Kanal**: für die Elemente der Kanalmatrix gilt p(y<sub>i</sub>|x<sub>j</sub>) = 1 - p (Fehlerwahrscheinlichkeit des Kanals) wenn i = j, sonst = p / (q - 1) | ||
| - | * Sonderfall: Binary Symmetric Channel (BSC) und Binary Symmetric Erasure Channel (BSEC) | ||
| - | * die **Kanalkapazität** ist das Maximum der Transinformation für einen gegebenen Kanal | ||
| - | * {{:se:kanalkapazitaet.jpg|}} | ||
| - | * bei symmetrischen Kanälen führen gleiche Wahrscheinlichkeiten der Eingangszeichen zur maximalen Transinformation und damit zur Kanalkapazität | ||
| - | |||
| - | ===== Quellencodierung ===== | ||
| - | * durch Codierung kann die Redundanz von Quellsymbolen verringert (Datenkompression) oder erhöht (Fehlerkorrektur) werden | ||
| - | * 2 Arten | ||
| - | * verlustlose Codierung -> Reduzierung der Redundanz | ||
| - | * verlustbehaftete Codierung -> Reduzierung der Irrelevanz | ||
| - | * ein Quellencodierer erzeugt aus Quellzeichen Codeworte | ||
| - | * die Gesamtheit der Codeworte heißt **Code** | ||
| - | * Codes mit gleicher Wortlänge für jedes Codewort heißen Blockcodes | ||
| - | * Klassen von Codes | ||
| - | * nichtsinguläre Codes: eineindeutige (injektive) Abbildung zwischen Quellzeichen und Codewort (evtl. sind Trennzeichen zwischen den Codeworten nötig) | ||
| - | * eindeutig decodierbare Codes: jede Folge von Codewörtern kann eindeutig auf eine Folge von Quellzeichen abgebildet werden (evtl. müssen alle Codewörter gelesen werden, um das erste Quellzeichen decodieren zu können) | ||
| - | * unmittelbar decodierbare Codes, präfixfreie oder Präfixcodes: die Decodierung ist stets unmittelbar möglich, da kein längeres Codewort Anfangszeichen enthält, die einem kürzeren Codewort entsprechen) | ||
| - | * {{:se:codeklassen.jpg|}} | ||
| - | * {{:se:codebaeume.jpg|}} | ||
| - | * Codeeffizienz: H(x) / L (mit L = mittlere Wortlänge * ld q) oder H(y) / H<sub>max</sub>(y) | ||
| - | * ein eindeutiger Code mit der Effizienz 1 heißt **idealer Code** | ||
| - | * ein **optimaler Code** (bezogen auf eine gegebene Quelle mit H(x)) liegt vor, wenn es keinen anderen eindeutig decodierbaren Code mit kleinerer mittlerer Wortlänge L gibt. Ein idealer Code ist optimal | ||
| - | * die Codewortlängen eines jedes eindeutig decodierbaren Codes müssen die Kraft-McMillan-Ungleichung erfüllen | ||
| - | * {{:se:kraftmcmillanungleichung.jpg|}} | ||
| - | * Huffman-Codes | ||
| - | * einfaches Verfahren zur Erzeugung von optimalen Präfixcodes (mit minimaler mittlerer Codewortlänge) | ||
| - | * **Entropie-Codierung**: Quellzeichen mit geringer Wahrscheinlichkeit bekommen längere Codeworte zugewiesen | ||
| - | * Nachteile | ||
| - | * Übertragungsfehler wirken sich durch Fehlerfortpflanzung stark aus | ||
| - | * codierter Datenstrom ist nicht mehr synchron zum Quelldatenstrom | ||
| - | * Einsortieren der zusammengefassten Zeichen an jeweils höchster Stelle führt zu minimaler Varianz | ||
| - | * Fundamentalsatz der Quellencodierung oder Shannons 1. Satz: Für jede stationäre gedächtnislose Quelle gibt es einen Code, dessen Effizienz beliebig nahe bei 1 liegt. | ||
| - | * **arithmetische Codierung**: Codierung der gesamten Nachricht aus Quellzeichen mit bekannten Auftrittswahrscheinlichkeiten als reelle Zahl | ||
| - | * **zustandsabhängige Codierung**: anwendbar bei gedächtnisbehafteten Quellen, bei denen die Auftrittswahrscheinlichkeiten der Quellzeichen abhängig vom aktuellen Zustand sind | ||
| - | * abhängig vom aktuellen Zustand wird eine für diesen Zustand optimale Codetabelle verwendet -> Codeumschaltung | ||
| - | * **Lauflängencodierung**: hier werden mehrfach hintereinander auftretende Quellzeichen in der Form {Zeichen, Anzahl} codiert | ||
| - | * Ausnutzung der Korrelation aufeinanderfolgender Zeichen | ||
| - | * Kompressionsverfahren mit adaptiven Wörterbüchern | ||
| - | * LZ77: Sliding Window | ||
| - | * {{:se:slidingwindow.jpg|}} | ||
| - | * LZ78: Aufbau eines expliziten adaptiven Wörterbuches (Erweiterung des LZ77, bei dem Zeichenfolgen außerhalb des Search Buffer nicht erkannt werden) | ||
| - | * {{:se:lz78.jpg|}} | ||
| - | * Problem ist das Finden der optimalen Wörterbuchgröße | ||
| - | * LZW: wie LZ78 nur mit Startwörterbuch, das alle Einzelzeichen des Quellalphabets enthält | ||
| - | * {{:se:lzw.jpg|}} | ||
se/informationstheorie.txt · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)
Seiten-Werkzeuge
Falls nicht anders bezeichnet, ist der Inhalt dieses Wikis unter der folgenden Lizenz veröffentlicht: CC Attribution-Noncommercial-Share Alike 4.0 International
