se:informationstheorie
**Dies ist eine alte Version des Dokuments!**
Überblick
basiert auf grundlegenden Arbeiten von Shannon
eine Quelle liefert informationskennzeichnende Zeichen xi 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 wi der Länge mi gebildet werden. Es lassen sich qm 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(xi) = wi
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(xi)/bit = -ld p(xi)
I(xi, xj) = I(xi) + I(xj)
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
-
die Entropie ist der Erwartungswert des Informationsgehalts
die Entropie wird maximal, wenn alle Zeichen eines Zeichenvorrats gleich wahrscheinlich sind, Bezeichnung: Hmax oder H0
der Unterschied zwischen H(x) und H0 wird als Redundanz bezeichnet: p = H0 - H(x)
eine Redundanz kann auch für Codes angegeben werden: pcode = 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
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
die Verbundentropie (H(x,s) ist der mittlere Informationsgehalt von ganzen Ausgangsfolgen einer Markov-Quelle
-
-
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
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(yj|xi) = Wahrscheinlichkeit, dass yj empfangen wird, wenn xi gesendet wurde
die Zeilensummen müssen 1 ergeben: 1 = p(y1|xi) + p(y2|xi) + … + p(yj|xi)
p(xj|yi) heißt A-posteriori-Wahrscheinlichkeit, p(xj) heißt A-priori-Wahrscheinlichkeit
der Detektor schließt aus dem empfangenen Zeichen yi auf das gesendete Zeichen xj
Maximierung der A-posteriori-Wahrscheinlichkeit (Maximum-A-Posteriori-Probability-Detektion: MAP-Detektion) p(yi|xj) * p(xj)
wenn die Quellenstatistik nicht bekannt ist, fällt p(xj) weg bzw. ist für alle Eingangszeichen gleich. Dann wird lediglich das Maximum von p(yi|xj) gesucht → Maximum-Likelihood-Detektor
Entropien im Kanal
-
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)
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(yi|xj) = 1 - p (Fehlerwahrscheinlichkeit des Kanals) wenn i = j, sonst = p / (q - 1)
die Kanalkapazität ist das Maximum der Transinformation für einen gegebenen Kanal
Quellencodierung
durch Codierung kann die Redundanz von Quellsymbolen verringert (Datenkompression) oder erhöht (Fehlerkorrektur) werden
2 Arten
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)
-
-
Codeeffizienz: H(x) / L (mit L = mittlere Wortlänge * ld q) oder H(y) / Hmax(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
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
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.
se/informationstheorie.1235408920.txt.gz · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)