Informationstheorie und Codierung

Beispiele für Codes: Morse-Code, ASCII-Code, Dezimal-, Oktalzahlen etc.

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 ist der Erwartungswert des Informationsgehalts

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

allg. Markov-Quelle = Markov-Quelle 1. Ordnung, gedächtnislose Quelle = Markov-Quelle 0. Ordnung

die bedingte Entropie kann nie größer werden als die "normale" Entropie

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

Hard-Decision: Ein- und Ausgabealphabet sind identisch

Soft-Decision: liefert kontinuierlich verteilte Ausgangswerte

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

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

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)

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

bei symmetrischen Kanälen führen gleiche Wahrscheinlichkeiten der Eingangszeichen zur maximalen Transinformation und damit zur Kanalkapazität

verlustlose Codierung → Reduzierung der Redundanz

verlustbehaftete Codierung → Reduzierung der Irrelevanz

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)

einfaches Verfahren zur Erzeugung von optimalen Präfixcodes (mit minimaler mittlerer Codewortlänge)

Entropie-Codierung: Quellzeichen mit geringer Wahrscheinlichkeit bekommen längere Codeworte zugewiesen

Einsortieren der zusammengefassten Zeichen an jeweils höchster Stelle führt zu minimaler Varianz

abhängig vom aktuellen Zustand wird eine für diesen Zustand optimale Codetabelle verwendet → Codeumschaltung

Ausnutzung der Korrelation aufeinanderfolgender Zeichen

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

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)

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)

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)

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)

gibt es hierbei jedoch ein blockübergreifendes Gedächtnis, spricht man von Faltungscodes

die Gewichtsverteilung sind die Anzahlen der Codewörter mit Hamminggewicht 0…m

die minimale Hammingdistanz ist die kleinste Hammingdistanz zwischen zwei unterschiedlichen Codewörtern eines Codes

das Beispiel hat eine minimale Hammingdistanz von 2 und kann damit 1 Bitfehler bei der Übertragung erkennen

Hard-Decision: das Codewort, das dem Empfangswort zugewiesen wird, ist dasjenige, welches die geringste Hammingdistanz zum Empfangswort aufweist

um mittels Hard-Decision die gleiche Fehlerwahrscheinlichkeit zu erreichen wie mit Soft-Decision müsste man eine verdoppelte Sendeleistung aufwenden

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

die Ergebnisse der Modulo-2-Addition und Modulo-2-Subtraktion entsprechen sich und dem Ergebnis einer XOR-Verknüpfung

jede beliebige Linearkombination aus Codewörtern ergibt wieder ein Codewort

damit muss in jedem linearen Blockcode auch das Nullwort enthalten sein

d(c,c') = w(c-c'), damit ergibt sich die minimale Hammingdistanz aus der Suche nach dem Codewort mit dem geringsten Hamminggewicht (außer dem Nullwort)

das empfangene Codewort wurde durch Verfälschung zu einem anderen gültigen Codewort

bei der Codierung werden aus den Infowörtern durch Multiplikation mit einer Generatormatrix Codewörter erzeugt

die Generatormatrix besteht aus n Codewörtern der Länge m

* ein Vertauschen der Spalten der Generatormatrix erzeugt einen äquivalenten Code mit den gleichen Parametern (aber anderen Codewörtern)
* ein Vertauschen der Zeilen oder das Ersetzen einer Zeile durch ihre Summe mit einer anderen Zeile ändert nicht den Code, sondern nur die Zuordnung von Codewörtern zu Infowörtern

* systematische Codes sind solche, bei denen die Infobits in allen Codeworten an der gleichen Stelle stehen (ergänzt um die Schutzbits), sie lassen sich also ohne Berechnung aus dem Codewort ablesen

die Generatormatrix G hat dabei n Spalten mit jeweils nur einer 1

Expandieren: m' > m, n' = n, R' < R, d'_min >= d_min

Punktieren: m' < m, n' = n, R' > R, d'_min ⇐ d_min

Verlängern: m' > m, n' > n, m' - n' = m - n, R' > R, d'_min ⇐ d_min

Verkürzen: m' < m, n' < n, m' - n' = m - n, R' < R, d'_min >= d_min

Hamming-Codes können erstellt werden, indem die 2^{m - n} - 1 von 0 verschiedenen Paritätsbit-Kombinationen in Spaltenform angeordnet und dann so sortiert werden, dass rechts eine m-n x m-n Einheitsmatrix entsteht. Aus dieser Prüfmatrix kann nun die Generatormatrix des Hamming-Codes abgeleitet werden.

Vorteil: können einfach mittels rückgekoppelten Schieberegistern (LFSR = Linear Feedback Shift Register) realisiert werden

fehlererkennende zyklische Blockcodes (CRC = Cyclic Redundancy Check) erkennen gut Bündelfehler

zyklische Blockcodes erkennen mindestens Einzelfehler, Doppelfehler und Bündelfehler bis zur Länge k = m - n

zyklische Hamming-Codes: werden aus primitiven Generatorpolynomen erzeugt

Fire-Codes: verwenden ein Produkt g(x) = g₁(x) * (x^k₂ + 1) aus zwei irreduziblen Polynomen als Generatorpolynom

* BCH-Codes (Bose-Chaudhuri-Hocquenghem) erlauben die Korrektur von zufällig verteilten Fehlern
* RS-Codes (Reed-Solomon) bilden eine Klasse von nichtbinären BCH-Codes
  * gehören zu den besten bekannten Bündelfehler-korrigierenden Codes (z.B. Audio-CD)

werden z.B. beim Mobilfunk eingesetzt

man kann recht einfach auch den ungleichmäßigen Schutz der Nachrichtenbits erreichen (wichtige Bereiche werden besser geschützt)

* der Entwurf erfolgt nicht algebraisch, sondern durch rechnergestützte Suche
* Unterscheidung in rekursiv/nicht-rekursiv und systematisch/nicht-systematisch
  * häufig: Nonrecursive nonsystematic Convolution (NSC)

*

das Beispiel macht aus einem Eingangsbit drei Ausgangsbit, die der Reihe nach gesendet werden

die Länge der Verzögerungskette (3 Bits gehen in die Berechnung ein) nennt man Einflusslänge (Constraint Length)

das Gedächtnis ist die die Anzahl der vorangehenden Bits in der Verzögerungskette (Anzahl - 1)

* {{:se:schaltbildfaltungscodiererallgemein.jpg|}}

* Darstellungsformen

grafisch (s.o.)

die Decodierung erfolgt mittels des Viterbi-Algorithmus, also der Suche nach dem am besten übereinstimmenden Pfad des Trellisdiagramms

  - Zweigdistanz/Zweigmetrik für jeden Zweig ermitteln (unterschiedliche Bits zur Eingangsfolge bei Hard-Decision, euklidische Distanz bei Soft-Decision)
  - die Zweigdistanz wird zur Survivormetrik des Ursprungsknotens des Zweiges addiert -> neue Summenzweigmetrik/Summenmetrik
  - die neue Survivormetrik des Zielknotens ergibt sich als Minimum aller Summenzweigmetriken der in den Knoten mündenden Zweige. Diese Survivormetriken werden für alle Knoten berechnet.
  - die Survivorpfade ergeben sich durch Rückverfolgen (Backtracing) des Pfades, der den Zweig mit der minimalen Summenzweigmetrik enthält
* {{:se:viterbi1.jpg|}}
* {{:se:viterbi2.jpg|}}
* {{:se:viterbi3.jpg|}}

* analog zur Hammingdistanz kann man bei Faltungscodes eine Minimaldistanz d_free (freie Distanz) als kleinstes Gewicht der Pfade vom Nullzustand in den Nullzustand (ohne reinen Nullpfad)

Gleichverteilung der Symbolwahrscheinlichkeiten ⇒ maximale Entropie (Entscheidungsgehalt) H₀ = ld(q)

A-posteriori p(x|y)

A-priori p(x)

bei symmetrischen Kanälen führt eine Gleichverteilung der Wahrscheinlichkeiten der Eingangszeichen zur maximalen Transinformation

primitive Generatorpolynome erzeugen Codes mit d_min = 3

"normale" Entropie mit p(x_i) berechnen

bei statistisch unabhängigen Ausgangszeichen: n * H(x)

optimal/kompakt: größtmögliche Effizienz bei gegebener Quelle → kleinste mittlere Wortlänge

ideal: eindeutig decodierbarer Effizienz &eta; = 1

eindeutig decodierbar: Erfüllen der Kraft-McMillan-Ungleichung

perfekt/dicht gepackt: alle Worte eines Coderaums liegen in Korrigierkugeln mit Radius e_kor, 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

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> &le; k<sub>1</sub>, t<sub>max</sub> < k<sub>2</sub> / 2 + 1

zyklisch