Informationstheorie und Codierung

Übersicht Informationstheorie und Codierung

Informationsquellen

• Zufallsquelle
  • z Symbole
  • Symbolwahrscheinlichkeit: $p_{i}=1/z$
  • Entropie: $H_{0}=ld(z)(Bits/S)$
• Bernoulliquelle
  • Symbolwarscheinlichkeit: $p(S_{i})$ aus Tabelle
  • Informationsgehalt: $I_{i}=-ld(p_{i})$
  • Entropie: $H_{1}=-\sum _{m=1}^{z}p_{i}*ld(p_{i})$
• Markoffquelle
  • Quelle mit Gedächtnis
  • Ordnung: beschreibt von wievielen Zuständen der nächste Zustand abhängt
  • Entropie für Prozess 1.Ordnung: $H_{2}=-\sum _{i=1}^{z}p_{i}\sum _{j=1}^{z}p_{j/i}*ld(p_{j/i})$

Quellencodierer

• Code - Menge von Codeworten die Symbolen eineindeutig zugeordnet sind
• betrachten Codierung diskreter Quellen
• Gleichmäßige Codes - alle Codeworte haben gleiche Länge (nicht effizient)
• Ungleichmäßige Codes:
  • Fano
    • Ordne Symbole nach fallenden Wahrscheinlichkeiten
    • bilde 2 Gruppen gleicher Wahrscheinlichkeit und ordne 1 oder 0 zu
    • solange wiederholen bis alles Symbole codiert sind
  • Huffman
    • Ordne Symbole nach fallenden Wahrscheinlichkeiten
    • Fasse niedrigste Wahrscheinlichkeiten zusammen, ordne erneut
    • wenn alle zusammengefasst, Baum aufstellen und Bits zuordnen
  • Coderedundanz
    • mittlere Codewortlänge: $H_{c}\approx I_{cm}=\sum _{i}p_{i}l_{ci}$
    • Redundanz: $R=I_{cm}-H_{1}\geq 0$
  • Blockcodierungen
    • erster Shannonscher Satz: Coderedundanz kann prinzipiell durch Blockcodierung beseitigt werden
    • m Symbole zu Blöcken zusammengefasst und codiert
    • $H_{1}<I_{cm}<H_{1}+1/m$ --> durch zusammenfassen vieler zeichen kann man sich beliebig annähern
  • Optimalcodierung von Markoff-Quellen
    • Codiere Zustandswahrscheinlichkeiten und Übergänge
    • Codeworte mehrfach vergeben --> Dekodierung ohne Kenntnis der Vergangenheit nicht möglich
    • Decodierungsfehler wirken sich lange aus
  • weitere Codes:
    • Golomb
    • Rice
    • universelle Präfixcodes
    • arithmetische Codierung

Kanalcodierer

Kanalmodell

• durch Störungen auf dem Kanal gehen Informationen verloren (Äquivokation)
• oder kommen hinzu (Irrelevanz)
• Entropie am Empfänger: $H(X)=-\sum _{i}p(X_{i})ld(p(X_{i}))$ $X_{i}=\sum _{j}p(Y_{j})p(Y_{j}|X_{i})$
• Entropie am Sender: $H(Y)=-\sum _{j}p(Y_{j})ld(p(Y_{j}))$ $Y_{j}=\sum _{i}p(X_{i})p(X_{i}|Y_{j})$
• Irrelevanz: $H(Y|X)=-\sum _{i}p(X_{i})\sum _{j}p(Y_{j}|X_{i})*ld(p(Y_{j}|X_{i}))$
• Äquivokation: $H(X|Y)=-\sum _{j}p(Y_{j})\sum _{i}p(X_{i}|Y_{j})*ld(p(X_{i}|Y_{j}))$
• Transinformation: $T(Y|X)=H(Y)-H(Y|X)=H(X)-H(X|Y)=H(X)-H(X,Y)+H(Y)$
• Kanalkapazität: $C=T(X,Y)*f_{Sy}$

Kanalcodierung

• Aufgabe: redundante Informationen hinzufügen um Fehler zu erkennen und eventuell zu korrigieren
• Fehlerzahl zu hoch --> Neuübertragung nötig
• Grundlage: Fehlerhafte Übertragung durch:
  • Verzerrungen: Phasen und Dämpfungsverzerrung
  • Interferenzen: Nebensprechen, Rauschen, Fremdstörungen
• führt zu Bitfehlern
• Klassifizierung korrigierender Codes:

• Begriffe:
  • Blocklänge n = k + i
  • k - Kontrollbits , i- Informationsbits
  • Blockfehlerwahrscheinlichkeit für v Fehler im Block: $p_{v,n}={\binom {n}{v}}p_{e}^{v}(1-p_{e})^{n-v}$
  • Hammingdistanz d : Mindestanzahl verschiedener Bits pro Block
  • d-1 Fehler erkennbar
  • (d-1)/2 Fehler korrigierbar
  • Redundanz = k
• Fehlererkennung durch Paritätsbits:
  • 1D Paritätsbits angehängt
  • Kreuzsicherungscode 2-D Paritätsbits für Zeilen und Spalten vom Block
• Hammingcode:
  • Blockcode, nutzt mod 2 Arithmetik
  • H(7,4) 4 informationsbits 7 Bit Blocklänge
  • Struktur: k1 k2 i4 k3 i3 i2 i1
  • wobei k3 = i3 + i2 + i1| k2 = i4 + i2 + i1 | k1 = i4 + i3 + i1
  • Korrektor am Empfänger berechnen --> Syndrometabelle gibt aufschluss über Fehlerort (c1,c2,c3)
• Lineare Codes:
  • Berechnung über Matrixmultiplikation Y = i + G
  • Generatormatrix invertieren für Prüfmatrix
  • Hammingcode auch als Linearcode darstellbar
• zyklische Codes:
  • Generatormatrix aus Verschiebung eines Generator Polynoms gegenerieren ( *2 = verschieben)
• Technische Realisierung:
  • Fehlerpolynom e(x) finden
  • Multiplikation am Sender (y(x) = g(x) * i(x)
  • additive Störung (y'(x)= y(x) + e(x))
  • Division am Empfänger (y'(x)/g(x) = y(x)/g(x) + e(x)/g(x))
  • Rest: r(x) = e(x)/g(x) wenn ungleich 0 Fehler --> in Syndromtabelle nachschauen
  • alternativ Division am Empfänger: y(x) = $x^{k}$ * i(x) + r(x) r(x) ist rest von $x^{k}$ * i(x) mod g(x) damit isses wieder teilbar
• Schaltungstechnisch:
  • digitale Schaltungen mit Verzögerungsgliedern

• 

  Multiplikator

• 

  Divisor

• spezielle zyklische Codes:
  • Hamming Code primitives GeneratorPolynom vom Grad k erzeugen, dmin = 3 Codewortlänge $n=2^{k}-1$
  • Abramsoncode: Polynom g(x) mit x+1 multiplizieren--> d um 1 erhöht
  • Firecode
    • zum Burstfehler erkennen, beheben
    • mit $x^{k}2+1$ multiplizieren d=4, einige Burstfehler erkennbar
    • Bursts mit Länge l beheben
    • iterativer Algorithmus zum Beheben von Fehlerbursts..
• Codespreizung (Interleaving):
  • Zeilenweise einlesen von Daten und Spaltenweise versenden
  • Tritt ein Fehlerburst auf gehen nur daten einer Spalte verloren --> korrigierbar
  • Verbesserung: Spreizungtiefe, bei CD z.B. 4 --> kontinuierlichere Verarbeitung
• Fehlerkorrektur höherstufiger Codes ( ähnlich Hammingcode mit Korrektursymbolen usw.)
• Faltungscodes

Leitungscodierer

• Anforderungen:
  • gleichstromfrei
  • synchronisierbar
  • erkennbare Fehler (z.B. durch Disparität)
• Coderedundanz hier: $R=gesendeteBits-Informationsbits$
• AMI Code (Alternate Mark inversion)
  • 0 als 0 gesendet
  • 1 abwechselnd +/-
• HDB3-Code
  • Erweiterung AMI
  • maximal 3 aufeinanderfolgende Nullen --> bessere Synchronisierbarkeit
  • mit Paritätsausgleichs und Verletzungsbits (B00V)
• PST Code (Paired Selected Ternary)
• 4B3T Codes
  • MMS43-Code (Franaszek)
  • 4B3T Code Tabellenauswahl abhängig von Disparität
  • CMI( Code MArk Inversion)
    • 0 --> -+ | 1 --> --/++
    • für LWL 0 statt -
• 5B6B Code