Informationstheorie und Codierung: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
Mr. D (Diskussion | Beiträge) |
Beagle (Diskussion | Beiträge) K (hat „Informationstheorie und Kodierung“ nach „Informationstheorie und Codierung“ verschoben: Das Fach wird Informationstheorie und Codierung geschrieben.) |
||
(2 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
Zeile 31: | Zeile 31: | ||
*** wenn alle zusammengefasst, Baum aufstellen und Bits zuordnen | *** wenn alle zusammengefasst, Baum aufstellen und Bits zuordnen | ||
** Coderedundanz | ** Coderedundanz | ||
− | *** mittlere Codewortlänge: <math>H_c\approx I_{cm} = \sum_{i}p_i </math> | + | *** mittlere Codewortlänge: <math>H_c\approx I_{cm} = \sum_{i}p_i l_{ci} </math> |
*** Redundanz: <math>R = I_{cm} -H_1 \ge 0 </math> | *** Redundanz: <math>R = I_{cm} -H_1 \ge 0 </math> | ||
** Blockcodierungen | ** Blockcodierungen | ||
Zeile 105: | Zeile 105: | ||
Datei:Divisor.PNG|Divisor | Datei:Divisor.PNG|Divisor | ||
</gallery> | </gallery> | ||
+ | |||
+ | *spezielle zyklische Codes: | ||
+ | ** Hamming Code primitives GeneratorPolynom vom Grad k erzeugen, dmin = 3 Codewortlänge <math> n = 2^k -1 </math> | ||
+ | ** Abramsoncode: Polynom g(x) mit x+1 multiplizieren--> d um 1 erhöht | ||
+ | ** Firecode | ||
+ | *** zum Burstfehler erkennen, beheben | ||
+ | *** mit <math> x^k2+1 </math> 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== | ==Leitungscodierer== |
Aktuelle Version vom 13. Oktober 2012, 16:48 Uhr
Übersicht Informationstheorie und Codierung
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
- Fano
Kanalcodierer
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:
- 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