Dies ist eine alte Version des Dokuments!

Inhaltsverzeichnis

Informationstheorie und Codierung

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_i 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_i der Länge m_i gebildet werden. Es lassen sich q^m 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_i) = w_i
- 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_i)/bit = -ld p(x_i)
- I(x_i, x_j) = I(x_i) + I(x_j)
- 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: H_max oder H₀
  - die maximale Entropie wird auch als Entscheidungsgehalt einer Quelle bezeichnet
der Unterschied zwischen H(x) und H₀ wird als Redundanz bezeichnet: p = H₀ - H(x)
- eine Redundanz kann auch für Codes angegeben werden: p_code = 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
- 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
- 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_j|x_i) = Wahrscheinlichkeit, dass y_j empfangen wird, wenn x_i gesendet wurde
- die Zeilensummen müssen 1 ergeben: 1 = p(y₁|x_i) + p(y₂|x_i) + … + p(y_j|x_i)
- p(x_j|y_i) heißt A-posteriori-Wahrscheinlichkeit, p(x_j) heißt A-priori-Wahrscheinlichkeit
der Detektor schließt aus dem empfangenen Zeichen y_i auf das gesendete Zeichen x_j
- Maximierung der A-posteriori-Wahrscheinlichkeit (Maximum-A-Posteriori-Probability-Detektion: MAP-Detektion) p(y_i|x_j) * p(x_j)
- wenn die Quellenstatistik nicht bekannt ist, fällt p(x_j) weg bzw. ist für alle Eingangszeichen gleich. Dann wird lediglich das Maximum von p(y_i|x_j) 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)
  - I(x;y) = H(y) - H(y|x)
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_i|x_j) = 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
- 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

verlustlose Codierung

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) / H_max(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
  - Ü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
- LZ78: Aufbau eines expliziten adaptiven Wörterbuches (Erweiterung des LZ77, bei dem Zeichenfolgen außerhalb des Search Buffer nicht erkannt werden)
  - Problem ist das Finden der optimalen Wörterbuchgröße
- LZW: wie LZ78 nur mit Startwörterbuch, das alle Einzelzeichen des Quellalphabets enthält

verlustbehaftete Codierung

bei verlustloser Codierung liegt der Schwerpunkt auf der Effizienz (Kompressionsrate), die begrenzt ist durch die Quellenentropie
statt Verlusten sagt man auch Verzerrungen
das Maß der Qualitätsbeeinträchtigung durch Verzerrungen muss vom jeweiligen Rezipienten bestimmt werden, da messbare Abweichungen nicht unbedingt mit der von Menschen empfundenen Qualität übereinstimmen
einfache Berechnungen der Verzerrung ermitteln den (absoluten oder quadratischen) Abstand zwischen Eingangs- und Ausgangszeichen
dabei ist es sinnvoll, den mittleren quadratischen Fehler dieser Abstände zu ermitteln (MSE = Mean Square Error)
```
* {{:se:mse.jpg|}}
```
* das Signal-Verzerrungs-Verhältnis (SNR = Signal to Noise Ratio) setzt den Erwartungswert der quadratischen Eingangszeichen zu dem der Verzerrung ins Verhältnis
um zeit- und wertkontinuierlichen Signale wie Sprache codieren zu können, müssen die diskretisiert werden
die Diskretisierung zeitkontinuierlicher Signale erfordert immer eine Zeitdiskretisierung (Abtastung)
eine verlustfreie Abtastung kann nur bei bandbegrenzten Signalen und ausreichend hoher Abtastrate gewährleistet werden (→ Nyquist-Theorem)

diese Bandbegrenzung ist aber nicht immer gegeben, sodass meist eine Antialias-Tiefpassfilterung vorgenommen werden muss

* Antialiasing sorgt für eine Abschwächung des Alias-Effekts (zu hohe Frequenzen werden als niedrig abgetastet)    
  * {{:se:aliaseffekt.jpg|}}
* ein Tiefpassfilter schwächt zu hohe Frequenzen ab, sodass das Endsignal nur Frequenzen innerhalb eines bestimmten Bandes aufweist      
* Beispiel Telefonie: alle Frequenzen über 3,4kHz werden "abgeschnitten"

* im Anschluss an die Abtastung müssen die ermittelten Werte quantisiert werden

* die Quantisierung bildet die kontinuierlichen oder fein quantisierten Ausgangswerte nicht umkehrbar auf diskrete Repräsentanten ab (Quantisierungsniveaus)
* {{:se:quantisierung.jpg|}}
* der Quantisierungsfehler kann als mit den Ausgangswerten unkorrelierte Zufallsvariable angesehen werden    
* die Quantisierungsintervalle können theoretisch beliebig und unterschiedlich groß sein, es bietet sich jedoch an, gleich große Intervalle zu bilden
  * {{:se:gleichmaessigequantisierung.jpg|}}
  * die Zahl der Quantisierungsniveaus ist in der Praxis immer endlich (2<sup>w</sup> mit w als Binärwortlänge für die codierten Stufen)
    * {{:se:quantisierungskennlinien.jpg|}}
    * {{:se:snrgleichmaessigerquantisierer.jpg|}}
* bei Sprache ist die Verteilung der Frequenzen recht ungleich: viele kleine Signalwerte, wenig große. Daher muss die Quantisiereraussteuerung gering bleiben, was zu geringerem SNR führt
  * Gegenmaßnahmen: **ungleichmäßige Quantisierung** (unterschiedliche Quantisierungsstufenhöhen) oder **adaptive Quantisierung** (Anpassung des Quantisierers an momentane Größe der Eingangswerte)

JPEG

Verfahren zur Standbildkompression (ISO-Standard)
nur Decodierprozess ist vorgeschrieben, nicht aber der Codierprozess
der Baseline-Codec hat die Eigenschaften:
- Arbeitsweise auf Basis der Diskreten Cosinus-Transformation (DCT)
- Quellbild hat 8 bit pro Komponente (z.B. pro Farbe)
- Huffman-Codierung
- 2 verlustbehaftete Schritte: Subsampling und Quantisierung der DCT-Werte
  * Farbraumtransformation
- Bilder liegen meist in RGB-Darstellung mit 8 bit pro Farbe vor
- Berechnung der Helligkeitsinformationen (Luminanz) und Farbdifferenzinformationen (Chrominanz) und Darstellung in Form von YUV
- sinnvoll, da das menschliche Auge Helligkeitsunterschiede besser wahrnimmt als Farbunterschiede
- die Auflösung der Chrominanzwerte kann nochmal um den Faktor 2 verringert werden (Subsampling)
  * die Codierung erfolgt im Frequenzbereich, wozu die Werte in diesen überführt werden müssen → DCT
- die DCT-Werte stellen niedrige und hohe Ortsfrequenzen dar (sich langsam bzw. schnell verändernde Werteabfolgen in Zeilen- und Spaltenrichtung) bzw. die Ähnlichkeit der Blöcke mit den Basisfunktionen
- die Quantisierung der DCT-Werte bestimmt den Kompressionsfaktor
  - die Quantisierung erfolgt gleichförmig, jedoch für jeden der 64 Koeffizienten mit einer in einer Quantisierungsmatrix festgelegten Stufenhöhe
  - dabei werden die höherfrequenten Koeffizienten gröber quantisiert als die niederfrequenten, die letztere für die menschliche Wahrnehmung wichtiger sind
Codierung der quantisierten DCT-Werte mittels Huffman-Codierung
- zuerst werden die Koeffizienten nach ihren Frequenzen sortiert (schlangenförmig von links oben nach rechts unten), sodass es zu längeren Nullfolgen (durch weniger hochfrequente Anteile in Bildern und zusätzlich die gröbere Quantisierung) kommt → Lauflängencodierung
- die DC-Werte (Wert des Pixels 1/1) werden als Differenz zum DC-Werte des Blocks links neben dem aktuellen Block angegeben (die Differenz hat eine geringere Korrelation als die DC-Werte selbst, und kann damit effektiver Huffman-codiert werden)

MP3

bei der Audiokompression kann man Phänomene der Psychoakustik ausnutzen, um Irrelevanz (die der Empfänger nicht wahrnimmt) "abzuschneiden"
- Töne mit hohem Schalldruck (laute Töne) maskieren Töne in umliegenden Frequenzen, die einen geringeren Schalldruck aufweisen (Simultanverdeckung)
- auch kurz nach und interessanterweise auch vor dem Auftreten eines Maskierers verdeckt dieser Töne umliegender Frequenzen
- moderne Audiocodierverfahren basieren auf dem Ausnutzen der Maskierungsschwelle und einem dadurch möglichen größeren Rauschen, als dies beim klassischen Verfahren (CD) der Fall ist (weißes Rauschen)
MP3 definiert nur codierten Bitstrom und Decoder-Algorithmus
der Standard sieht Abtastraten von 32, 44.1 oder 48 KHz vor mit Bitraten zwischen 32 und 320 kbit/s
ab ca. 160 kbit/s wird kein Unterschied mehr zwischen uncodiertem und codiertem Signal wahrgenommen
- die Polyphasen-Filterbank teilt das Signal in 32 Teilbänder, die danach noch mit MDTC in jeweils 18 Unterkanäle aufgeteilt werden → 576 Spektralwerte
- mittels FFT wird gleichzeitig das Perzeptionsmodell erstellt, das hauptsächlich die konkreten Verdeckungsschwellen als Ergebnis liefert
- die Quantisierung (zwei Schleifen) muss dafür sorgen, dass die Verzerrung in allen Kanälen unterhalb der Maskierungsschwelle bleibt
- dabei werden ungleichmäßige Quantisierer eingesetzt, die kleine Spektralwerte mit höherer Genauigkeit darstellen
- die quantisierten Spektralwerte werden Huffman-codiert (die häufigen kleinen Werte bekommen kurze Codewörter)
- die Bitrate wird iterativ angepasst
- die Spektralwerte können durch einen globalen Verstärkungsfaktor und Skalierungsfaktoren für bestimmte Bereiche des Spektrums abgeschwächt werden
- Funktionsweise: der globale Verstärkungsfaktor wird variiert und nach einer erneuten Quantisierung und Codierung überprüft, ob das Ergebnis der Ausgangsbitrate entspricht und die Maskierungsschwelle eingehalten wird (evtl. Korrektur durch Anpassung der Skalierungsfaktoren)

Kanalcodierung

die Grundidee der Kanalcodierung ist die Vermeidung von Übertragungsfehlern oder die Erkennung der solchen durch gezieltes Hinzufügen von Redundanz
FEC (Forward Error Control) und ARQ (Automatic Repeat Request)
- FEC wird verwendet, wenn es keinen Rückkanal gibt oder die Übertragungszeit für den Request und die Antwort zu lang wäre (z.B. Mobilfunk)
- bei PC-Netzen wird meist ARQ verwendet, da der Overhead hier keine große Rolle spielt und ARQ weniger aufwändig ist als FEC (bei gleicher Restfehlerwahrscheinlichkeit)
Auswahl eines Kanalcodes abhängig von Fehlerverhalten, Bandbreite, Sendeleistung, Delay und Art der Daten (wichtige Daten brauchen bessere Absicherung)
werden Nachrichten in geichgroße Blöcke aufgeteilt, handelt es sich um Blockcodes
- gibt es hierbei jedoch ein blockübergreifendes Gedächtnis, spricht man von Faltungscodes
Coderate: Verhältnis von Infosymbolen zu Codesymbolen
Hamminggewicht: Anzahl der von Null verschiedenen Symbole eines Codewortes
- die Gewichtsverteilung sind die Anzahlen der Codewörter mit Hamminggewicht 0…m
Hammingdistanz: Anzahl der verschiedenen Symbole zweier Codewörter
- die minimale Hammingdistanz ist die kleinste Hammingdistanz zwischen zwei unterschiedlichen Codewörtern eines Codes
Kurzbezeichnung für Blockcodes: (m, n, d_min)_q
der Coderaum umfasst alle m-stelligen Codewörter und dient u.a. der Darstellung von Distanzen zwischen den Codewörtern
- das Beispiel hat eine minimale Hammingdistanz von 2 und kann damit 1 Bitfehler bei der Übertragung erkennen
mögliche Fehlererkennung: e_det = d_min - 1
mögliche Fehlerkorrektur: e_kor = (d_min - 1) / 2 (abrunden)
perfekter Code (dicht gepackter Code): alle Codeworte des Codes liegen in Korrigierkugeln mit einem Radius von e_kor
Decodierung: Hard-Decision (Empfangsworte stammen aus dem Codealphabet), Soft-Decision (Empfangsworte stammen aus einem größeren Alphabet)
- bei der Decodierung soll anhand des Empfangswortes das Wort gefunden werden, das mit der größten Wahrscheinlichkeit gesendet wurde
  - Maximierung der A-posteriori-Wahrscheinlichkeit (MAP): p(c|r) bzw. p(u|r)
  - wird auch Minimum Error Probability Decoding (MED) genannt, da die geringste Wortfehlerwahrscheinlichkeit erzielt wird
- Hard-Decision: das Codewort, das dem Empfangswort zugewiesen wird, ist dasjenige, welches die geringste Hammingdistanz zum Empfangswort aufweist
- Soft-Decision: Entscheidung aufgrund des Abstandsmaßes zwischen Codewort und Empfangswort (quadrierte euklidische Distanz im Coderaum)
  - die feinere Quantisierung der Symbole des Empfangswortes führt zu einer geringeren quantisierungsbedingten Verfälschung und sorgt für eine Berücksichtigung der in den Symbolen enthaltenen Zuverlässigkeitsinformation
- um mittels Hard-Decision die gleiche Fehlerwahrscheinlichkeit zu erreichen wie mit Soft-Decision müsste man eine verdoppelte Sendeleistung aufwenden
Interleaving: Methode zum Umgang mit Bündelfehlern (mehrere Fehler gleichzeitig: Fehlerbursts)
- die Codeworte werden ineinander verschachtelt, wodurch Bündelfehler sich zwar auf mehrere Worte, aber auf jedes einzeln nicht so stark auswirken
- Folge ist ein erhöhter Speicherbedarf und eine Übertragungsverzögerung

Lineare Blockcodes

häufig verwendet: Modulo-2-Rechnung
- die Ergebnisse der Modulo-2-Addition und Modulo-2-Subtraktion entsprechen sich und dem Ergebnis einer XOR-Verknüpfung

Stefans Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

**Dies ist eine alte Version des Dokuments!**