"Informationstheorie Codierung und Kryptographie 001.ps.gz" - читать интересную книгу автораInformationstheorie, Codierung und Kryptologie Miroslaw Kutylowski und Willy-B. Strothmann Uni-GH Paderborn, Skript zur Vorlesung von M. Kutylowski WS 1995/96 Version: -0.5 Korrekturen, Verbesserungsvorschl"age an: [email protected] die aktuellste Version des Skripts kann man auf dem WWW-Server der Uni-GH Paderborn "uber die Datei: http://www.uni-paderborn.de/fachbereich/AG/agmadh/WWW/german/LehreKuty/lehre.html finden. Das Skript basiert auf einer Latex Source (geschrieben durch Guido Haeseler), die auch "uber diese Adresse zug"anglich ist. Die "Ubungsaufgaben sind ebenso durch WWW zug"anglich. Danksagung An diesem Skript haben neben den Autoren mitgewirkt: 0.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 0.1.1 Zwecke der Codierung . . . . . . . . . . . . . . . . . . . . . . 1 0.1.2 Kanalmodel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 0.1.3 Codierung - allgemeine Definition . . . . . . . . . . . . . . . . 2 0.1.4 Block Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1 Fehlererkennende und -korrigierende Codes 4 1.0.1 St"orungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.0.2 Hamming-Distanz . . . . . . . . . . . . . . . . . . . . . . . . 4 1.0.3 Fehlererkennung . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.0.4 Fehlerkorrektur . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.0.5 Notwendige Eigenschaften von fehlererkennden und fehlerkorrigierenden Codes . . . . . . . . . . . . . . . . . . . . . . . 5 1.0.6 Lineare Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.0.7 "Parity check" f"ur lineare Codes . . . . . . . . . . . . . . . . 5 1.0.8 Distanz zwischen Codew"ortern bei linearen bin"aren Codes . . 6 1.1 Parity-Check-Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Parity-Check-Matrix f"ur Korrektur von 1 Fehler . . . . . . . 7 1.2 Hamming Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.1 Fehlerkorrektur-Prozedur . . . . . . . . . . . . . . . . . . . . 8 1.2.2 Ein praktischer Hamming Code: . . . . . . . . . . . . . . . . 8 1.2.3 2 Fehler bei Hamming Codes . . . . . . . . . . . . . . . . . . 8 1.2.4 Hamming Codes sind perfekt . . . . . . . . . . . . . . . . . . 9 1.3 Lineare Codes - Fortsetzung . . . . . . . . . . . . . . . . . . . . . . . 9 1.3.1 Lineare Codes f"ur beliebige K"orper . . . . . . . . . . . . . . . 9 1.3.2 Generatormatrix und Codierverfahren f"ur lineare Codes . . . 9 1.3.3 Decodierverfahren f"ur lineare Codes . . . . . . . . . . . . . . 10 1.3.4 Systematische Codes: . . . . . . . . . . . . . . . . . . . . . . 10 1.3.5 "Aquivalente Codes . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.6 "Aquivalenter systematischer Code - Bestimmung einer Generatormatrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.7 Parity-Check-Matrix f"ur systematische Codes . . . . . . . . . 11 1.4 Erweiterter Hamming Code . . . . . . . . . . . . . . . . . . . . . . . 11 1.5 Dualer Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.5.1 Codes vs. duale Codes . . . . . . . . . . . . . . . . . . . . . . 12 1.6 Reed-Muller Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.6.1 Eigenschaften von !(r; m) Codes . . . . . . . . . . . . . . . . 13 1.6.2 Darstellung boolscher Funktionen durch W"orter . . . . . . . 13 1.6.3 Darstellung boolscher Funktionen durch Polynome . . . . . . 14 1.6.4 Konstruktion von !(r; m) - Codes . . . . . . . . . . . . . . . 15 1.6.5 Parity-Check-Matrix f"ur Reed-Muller Codes . . . . . . . . . . 16 1.7 Fehlerkorrektur bei Reed-Muller Codes . . . . . . . . . . . . . . . . . 16 |
|
|