Informationstheorie und Codierung

Aus II-Wiki
Wechseln zu: Navigation, Suche

Übersicht Informationstheorie und Codierung

Übersicht

Informationsquellen

  • Zufallsquelle
    • z Symbole
    • Symbolwahrscheinlichkeit:
    • Entropie:
  • Bernoulliquelle
    • Symbolwarscheinlichkeit: aus Tabelle
    • Informationsgehalt:
    • Entropie:
  • Markoffquelle
    • Quelle mit Gedächtnis
    • Ordnung: beschreibt von wievielen Zuständen der nächste Zustand abhängt
    • Entropie für Prozess 1.Ordnung:

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:
      • Redundanz:
    • Blockcodierungen
      • erster Shannonscher Satz: Coderedundanz kann prinzipiell durch Blockcodierung beseitigt werden
      • m Symbole zu Blöcken zusammengefasst und codiert
      • --> 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

Kanalmodell

  • durch Störungen auf dem Kanal gehen Informationen verloren (Äquivokation)
  • oder kommen hinzu (Irrelevanz)
  • Entropie am Empfänger:
  • Entropie am Sender:
  • Irrelevanz:
  • Äquivokation:
  • Transinformation:
  • Kanalkapazität:

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:

Klassifizierung korrigierender Codes


  • Begriffe:
    • Blocklänge n = k + i
    • k - Kontrollbits , i- Informationsbits
    • Blockfehlerwahrscheinlichkeit für v Fehler im Block:
    • 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) = * i(x) + r(x) r(x) ist rest von * i(x) mod g(x) damit isses wieder teilbar
  • Schaltungstechnisch:
    • digitale Schaltungen mit Verzögerungsgliedern
  • spezielle zyklische Codes:
    • Hamming Code primitives GeneratorPolynom vom Grad k erzeugen, dmin = 3 Codewortlänge
    • Abramsoncode: Polynom g(x) mit x+1 multiplizieren--> d um 1 erhöht
    • Firecode
      • zum Burstfehler erkennen, beheben
      • mit 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:
  • 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