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.) |
||
(16 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
Zeile 15: | Zeile 15: | ||
**Quelle mit Gedächtnis | **Quelle mit Gedächtnis | ||
**Ordnung: beschreibt von wievielen Zuständen der nächste Zustand abhängt | **Ordnung: beschreibt von wievielen Zuständen der nächste Zustand abhängt | ||
− | **Entropie für Prozess 1 | + | **Entropie für Prozess 1.Ordnung: <math>H_2 = -\sum_{i=1}^z p_i \sum_{j=1}^z p_{j/i}*ld(p_{j/i})</math> |
==Quellencodierer== | ==Quellencodierer== | ||
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 48: | Zeile 48: | ||
==Kanalcodierer== | ==Kanalcodierer== | ||
+ | ===Kanalmodell=== | ||
+ | [[Datei:Entropiediagramm.PNG|Kanalmodell]] | ||
+ | * durch Störungen auf dem Kanal gehen Informationen verloren (Äquivokation) | ||
+ | * oder kommen hinzu (Irrelevanz) | ||
+ | * Entropie am Empfänger: <math>H(X) = -\sum_i p(X_i)ld(p(X_i))</math> <math>X_i = \sum_j p(Y_j)p(Y_j|X_i)</math> | ||
+ | * Entropie am Sender: <math>H(Y) = -\sum_j p(Y_j)ld(p(Y_j))</math> <math>Y_j = \sum_i p(X_i)p(X_i|Y_j)</math> | ||
+ | * Irrelevanz: <math>H(Y|X) = -\sum_i p(X_i) \sum_j p(Y_j|X_i)*ld(p(Y_j|X_i))</math> | ||
+ | * Äquivokation: <math>H(X|Y) = -\sum_j p(Y_j) \sum_i p(X_i|Y_j)*ld(p(X_i|Y_j))</math> | ||
+ | * Transinformation: <math>T(Y|X) = H(Y) - H(Y|X) = H(X) - H(X|Y) = H(X) - H(X,Y) + H(Y)</math> | ||
+ | * Kanalkapazität: <math> C = T(X,Y) * f_{Sy}</math> | ||
+ | === 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: | ||
+ | [[Datei:KorrigierendeCodes.PNG|Klassifizierung korrigierender Codes]] | ||
+ | |||
+ | |||
+ | * Begriffe: | ||
+ | ** Blocklänge n = k + i | ||
+ | ** k - Kontrollbits , i- Informationsbits | ||
+ | ** Blockfehlerwahrscheinlichkeit für v Fehler im Block: <math> p_{v,n} = \binom n v p^v_e (1 - p_e)^{n-v}</math> | ||
+ | ** 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) = <math>x^k</math> * i(x) + r(x) r(x) ist rest von <math>x^k</math> * i(x) mod g(x) damit isses wieder teilbar | ||
+ | * Schaltungstechnisch: | ||
+ | ** digitale Schaltungen mit Verzögerungsgliedern | ||
+ | <gallery widths="350" heights="110" > | ||
+ | Datei:Multiplikator.PNG|Multiplikator | ||
+ | Datei:Divisor.PNG|Divisor | ||
+ | </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== | ||
+ | *Anforderungen: | ||
+ | ** gleichstromfrei | ||
+ | ** synchronisierbar | ||
+ | ** erkennbare Fehler (z.B. durch Disparität) | ||
+ | * Coderedundanz hier: <math> R = gesendete Bits - Informationsbits</math> | ||
+ | * 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 |
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