Benutzer-Werkzeuge
se:informationstheorie
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
|
se:informationstheorie [2009-02-26 20:28] stefan |
se:informationstheorie [2014-04-05 11:42] (aktuell) |
||
|---|---|---|---|
| Zeile 329: | Zeile 329: | ||
| * {{:se:viterbi3.jpg|}} | * {{:se:viterbi3.jpg|}} | ||
| * analog zur Hammingdistanz kann man bei Faltungscodes eine Minimaldistanz d<sub>free</sub> (freie Distanz) als kleinstes Gewicht der Pfade vom Nullzustand in den Nullzustand (ohne reinen Nullpfad) | * analog zur Hammingdistanz kann man bei Faltungscodes eine Minimaldistanz d<sub>free</sub> (freie Distanz) als kleinstes Gewicht der Pfade vom Nullzustand in den Nullzustand (ohne reinen Nullpfad) | ||
| + | |||
| + | ===== Klausur ===== | ||
| + | ==== Wichtige Feststellungen und Definitionen ==== | ||
| + | * Entropie: mittlerer Informationsgehalt der Zeichen des Quellalphabets | ||
| + | * Gleichverteilung der Symbolwahrscheinlichkeiten => **maximale Entropie** (Entscheidungsgehalt) H<sub>0</sub> = ld(q) | ||
| + | * bedingte Entropie: mittlere Entropie aller Zustände | ||
| + | * H(x|s) ≤ H(x) | ||
| + | * Verbundentropie: mittlerer Informationsgehalt von Ausgangsfolgen einer Quelle | ||
| + | * Wahrscheinlichkeiten | ||
| + | * A-posteriori p(x|y) | ||
| + | * A-priori p(x) | ||
| + | * Äquivokation/Rückschlussentropie/Verlust H(x|y) | ||
| + | * Irrelevanz/Streuentropie/Rauschen H(y|x) | ||
| + | * Transinformation: mittlere im Ausgangszeichen eines Kanals enthaltene Information | ||
| + | * Kanalkapazität: Maximum der Transinformation | ||
| + | * bei symmetrischen Kanälen führt eine Gleichverteilung der Wahrscheinlichkeiten der Eingangszeichen zur maximalen Transinformation | ||
| + | * Zusammenfassen von Eingangssymbolen zu Eingangsfolgen erhöht die Codeeffizienz (1. Fundamentalsatz der Quellencodierung) | ||
| + | * arithmetische Codierung geht nur für stationäre gedächtnislose Quellen | ||
| + | * Ausnutzen von bedingten Wahrscheinlichkeiten bei Markov-Quellen erhöht die Effizienz | ||
| + | * Codeumschaltung: bei zustandsabhängiger Codierung wird je nach Zustand eine andere Codetabelle verwendet | ||
| + | * Lauflängencodierung ist nur sinnvoll, wenn genügend Zeichenfolgen auftreten, die in der Darstellung (Code, Lauflänge) kürzer sind als normal | ||
| + | * Verfahren mit adaptiven Wörterbüchern eignen sich auch für nicht-stationäre Quellen | ||
| + | * Blockcodes teilen die Nachrichten in gleichgroße Blöcke auf | ||
| + | * um bei einem Gausskanal mittels Hard-Decision die gleiche Wortfehlerwahrscheinlichkeit erreichen wie mit Soft-Decision braucht man die doppelte Sendeleistung | ||
| + | * lineare Blockcodes: n < m, 2<sup>n</sup> Codeworte | ||
| + | * Wortfehler/Restfehler: aus dem Empfangswort wird auf das falsche Codewort geschlossen oder beim Korrigieren eines Fehlers wird das falsche Codewort erzeugt | ||
| + | * für kleine Bitfehlerwahrscheinlichkeiten resultiert ein Wortfehler meist aus der Verfälschung zu einem Codewort mit der zum korrekten Codewort minimalen Hammingdistanz | ||
| + | * Modifikationen (Expandieren, Punktieren, Verlängern, Verkürzen) führen systematische Codes wieder in systematische Codes über | ||
| + | * CRC-Codes sind fehlererkennende zyklische Blockcodes | ||
| + | * mit größeren Zykluslängen sind höhere Coderaten möglich | ||
| + | * primitives Polynom: die Zykluslänge entspricht dem maximalem Wert 2<sup>k</sup> - 1 und ist irreduzibel | ||
| + | * primitive Generatorpolynome erzeugen Codes mit d<sub>min</sub> = 3 | ||
| + | * meist werden CRC-Codes aus Generatorpolynomen der Form g<sub>prim</sub>(x) * (x + 1) | ||
| + | * dann: d<sub>min</sub> = 4, z = 2<sup>k - 1</sup> - 1 | ||
| + | * jeder lineare Blockcode (auch zyklische Codes) enthält das Nullwort | ||
| + | |||
| + | ==== Berechnungen ==== | ||
| + | * Redundanz: ρ = H<sub>0</sub> - H(x) | ||
| + | * Coderedundanz/Weitschweifigkeit p<sub>Code</sub> = L - H(x) (mit L = mittlere Wortlänge in Bit) | ||
| + | * relative Coderedundanz: p<sub>Code<sub>rel</sub></sub> = p<sub>Code</sub> / L | ||
| + | * Codeeffizienz η = H(x) / L | ||
| + | * Coderate R = m / n | ||
| + | * Entropie einer Markov-Quelle ohne Berücksichtigung der statistischen Bindung | ||
| + | * "normale" Entropie mit p(x<sub>i</sub>) berechnen | ||
| + | * bedingte Entropie bei gegebener Markov-Quelle | ||
| + | - p(x<sub>i</sub>|s) sind gegeben durch Zustandsdiagramm | ||
| + | - p(s) für alle Zustände ermitteln (lineares Gleichungssystem) | ||
| + | - H(x|s) für jeden Zustand ermitteln und mit p(s) multiplizieren und aufaddieren | ||
| + | * Verbundentropie | ||
| + | * bei Markov-Quellen | ||
| + | * Formel mit p(x,s) = p(x|s) * p(s) | ||
| + | * H(x,s) für n Zeichen = (n - 1) * H(x|s) + H(x) | ||
| + | * bei statistisch unabhängigen Ausgangszeichen: n * H(x) | ||
| + | * zyklische Blockcodes | ||
| + | * Generieren | ||
| + | * vollständig definiert durch Generatorpolynom und Codewortlänge (n = Rang des Generatorpolynoms) | ||
| + | * g(x) und n gegeben (oder aus m ermittelt) -> alle Permutationen von Wörtern der Länge n mit g(x) multiplizieren | ||
| + | * systematische Codes: Permutationen der Länge n erzeugen, d(x) = u(x) * x<sup>k</sup> mod g(x) addieren | ||
| + | * Generatormatrix erzeugen | ||
| + | * Koeffizienten eintragen und n Mal verschieben -> Streifenform | ||
| + | * zyklische Hamming-Codes: Erzeugen durch primitive Generatorpolynome | ||
| + | * Fire-Codes: Erzeugen durch Produkt zweier irreduzibler Polynome | ||
| + | * minimale Hammingdistanz durch Prüfmatrix ermitteln: jede Auswahl von d<sub>min</sub> - 1 Spalten ist linear unabhängig und es gibt mindestens eine Auswahl von d<sub>min</sub> linear abhängigen Spalten | ||
| + | |||
| + | ==== Eigenschaften ==== | ||
| + | * Code | ||
| + | * optimal/kompakt: größtmögliche Effizienz bei gegebener Quelle -> kleinste mittlere Wortlänge | ||
| + | * ideal: eindeutig decodierbarer Effizienz η = 1 | ||
| + | * eindeutig decodierbar: Erfüllen der Kraft-McMillan-Ungleichung | ||
| + | * perfekt/dicht gepackt: alle Worte eines Coderaums liegen in Korrigierkugeln mit Radius e<sub>kor</sub>, Hamming-Schranke wird mit Gleichheit erfüllt | ||
| + | * äquivalent: Codes mit gleichen Parametern m, n, d<sub>min</sub> und w | ||
| + | * Code und Leistungsfähigkeit können abweichen, aber Distanzeigenschaften bleiben gleich | ||
| + | * Erzeugen durch Vertauschen von Spalten in der Generatormatrix | ||
| + | * systematisch: alle Eingangsbits stehen in allen Codeworten an der gleichen Stelle | ||
| + | * klar-systematisch: die Eingangsbits stehen der Reihe nach am Anfang der Codeworte | ||
| + | * Hamming-Codes: Coderate geht mit wachsender Blocklänge gegen 1 | ||
| + | * Erzeugung: alle Permutationen von m - n Schutzbits als Spalten einer Prüfmatrix eintragen | ||
| + | * Hamming-Schranke mit Gleichheit erfüllt | ||
| + | * sind perfekt | ||
| + | * äquidistant: Codeworte haben paarweise jeweils gleiche Abstände d<sub>min</sub>, Plotkin-Schranke mit Gleichheit erfüllt | ||
| + | * identisch: Codes bestehen aus denselben Codeworten (nicht unbedingt in derselben Zuordnung zu Eingangsworten) | ||
| + | * zyklisch: Codeworte gehen durch Verschiebung ineinander über | ||
| + | * Quelle | ||
| + | * stationär: Wahrscheinlichkeiten der Ausgabezeichen sind unabhängig von der Zeit | ||
| + | * gedächtnislos: Wahrscheinlichkeiten der Ausgabezeichen sind unabhängig von Zeichen davor/danach | ||
| + | * Kanal | ||
| + | * diskret: zeit- und wertdiskret | ||
| + | * symmetrisch: Anzahl Eingänge = Anzahl Ausgänge, Fehlerwahrscheinlichkeit p | ||
| + | * verlustfrei/ungestört: nur ein von 0 verschiedener Eintrag je Spalte in der Kanalmatrix, aus Ausgangszeichen kann sicher auf das Eingangszeichen geschlossen werden | ||
| + | * rauschfrei: Kanalmatrix ist quadratische Einheitmatrix, in jeder Zeile nur ein von 0 verschiedener Eintrag, 1 Eingangszeichen -> 1 Ausgangszeichen | ||
| + | * total gestört: Ein- und Ausgangszeichen sind statistisch unabhängig, Transinformation = 0 | ||
| + | * zyklische Blockcodes | ||
| + | * Codewortlänge muss gleich der Zykluslänge sein | ||
| + | * Zykluslänge z = kleinstes i, für das gilt: x<sup>i</sup> + 1 mod g(x) = 0 | ||
| + | * Fehlererkennung: Einzel-, Doppel- und Bündelfehler bis zum Grad von g(x) sicher, darüber hinaus mit hoher Wahrscheinlichkeit | ||
| + | * Fehlerkorrektur | ||
| + | * primitives g(x): d<sub>min</sub> = 3 -> e<sub>kor</sub> = 1 | ||
| + | * g(x) = g<sub>prim</sub>(x) * (x + 1): d<sub>min</sub> = 4 -> e<sub>kor</sub> = 1 | ||
| + | * g(x) = g<sub>1</sub>(x) * (x<sup>k<sub>2</sub></sup> + 1) (Fire-Codes): d<sub>min</sub> = 4, sie können aber Bündelfehler korrigieren: t<sub>max</sub> ≤ k<sub>1</sub>, t<sub>max</sub> < k<sub>2</sub> / 2 + 1 | ||
| + | |||
| + | ==== ToDo ==== | ||
| + | * Shannon-Grenze | ||
| + | * Wann welche Codierung? arithmetisch bei gedächtnisbehaftet? | ||
| + | * Gleichförmige Quantisierung | ||
| + | * Beispiele machen | ||
| + | * Huffman Code | ||
| + | * Arithmetische Codierung | ||
| + | * Lempel Ziv | ||
| + | * Kanalkapazität berechnen | ||
| + | * Kraft-McMillan | ||
| + | * Gewichtsverteilung berechnen | ||
| + | * Syndrome berechnen | ||
| + | * Decodierung der verschiedenen Codes | ||
| + | * zyklisch | ||
| + | * Polynomdivision | ||
| + | * Zykluslänge bestimmen | ||
se/informationstheorie.1235676506.txt.gz · 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
