die Kanalcodierung zur Fehlererkennung und -korrektur ist ein wesentlicher Bestandteil in modernen digitalen Kommunikations- und Speichersystemen wie etwa CD und DVD, Internet-Datenübertragung, Mobilfunk, Satellitenkommunikation und digitales Fernsehen. Das Buch gibt eine grundlegende Einführung in die Codierungstheorie. Alle derzeit bekannten Decodierverfahren werden beschrieben und eingeordnet. Durch die übersichtliche und geschlossene Darstellung eignet sich das Werk gut zum vorlesungsbegleitenden Studium. Übungsaufgaben helfen, das vermittelte Wissen zu vertiefen.
Inhaltsverzeichnis
1;Einleitung;19 2;1 Grundbegriffe;23 2.1;1.1 Gewicht, Distanz;25 2.1.1;1.1.1 Mindestdistanz und Fehlerkorrigierbarkeit;26 2.1.2;1.1.2 Hamming-Schranke;27 2.2;1.2 Prüfmatrix und Syndrom;29 2.3;1.3 Decodierprinzipien;30 2.4;1.4 Fehlerwahrscheinlichkeit;33 2.5;1.5 Hamming-Codes;35 2.6;1.6 Generatormatrix;37 2.7;1.7 Zyklische Codes;38 2.8;1.8 Dualer Code;39 2.9;1.9 Erweiterung und Verkürzung von Codes;39 2.10;1.10 Kanalkapazität und Kanalcodiertheorem;41 2.11;1.11 Anmerkungen;43 2.12;1.12 Übungsaufgaben;44 3;2 Galois-Felder;47 3.1;2.1 Gruppen;47 3.2;2.2 Ringe, Körper;47 3.3;2.3 Primkörper;49 3.4;2.4 Gaußkörper;52 3.5;2.5 Erweiterungskörper;54 3.5.1;2.5.1 Irreduzible Polynome;54 3.5.2;2.5.2 Primitive Polynome, Wurzeln;55 3.5.3;2.5.3 Eigenschaften von Erweiterungskörpern;58 3.6;2.6 Kreisteilungsklassen und quadratische Reste;60 3.7;2.7 Anmerkungen;61 3.8;2.8 Übungsaufgaben;62 4;3 Reed-Solomon-Codes;65 4.1;3.1 Definition von RS-Codes;65 4.1.1;3.1.1 Diskrete Fourier-Transformation (DFT);66 4.1.2;3.1.2 Parameter von RS-Codes;68 4.1.3;3.1.3 Generatorpolynom;69 4.1.4;3.1.4 Prüfpolynom;70 4.1.5;3.1.5 Codierung;71 4.1.6;3.1.6 Zwei Eigenschaften zyklischer Codes;72 4.1.7;3.1.7 GRS-Codes und Erweiterungen von RS-Codes;73 4.2;3.2 Algebraische Decodierung bis zur halben Mindestdistanz;77 4.2.1;3.2.1 Prinzip der algebraischen Decodierung;77 4.2.2;3.2.2 Der Fehler als zyklischer Code;80 4.2.3;3.2.3 Decodierung mit Fehler-Generatorpolynom;82 4.2.4;3.2.4 Decodierung mit Fehler-Prüfpolynom;88 4.2.5;3.2.5 Verfahren von Sugiyama et al., WelchBerlekamp und Gao;93 4.2.6;3.2.6 Verfahren von GorensteinZierler, Peterson und BerlekampMassey;98 4.2.7;3.2.7 Korrektur von Fehlern und Auslöschungen;101 4.3;3.3 Algebraische Decodierung über die halbe Mindestdistanz;105 4.3.1;3.3.1 Interleaved RS-Codes (IRS);105 4.3.2;3.3.2 Power Decodierung;107 4.4;3.4 Algebraische Listendecodierung durch Interpolation;109 4.5;3.5 Anmerkungen;110 4.6;3.6 Übungsaufgaben;112 5;4 BCH-Codes;115 5.1;4.1 Primitive BCH-Code
s;115 5.1.1;4.1.1 Definition mit Kreisteilungsklassen;115 5.1.2;4.1.2 Definition mit DFT;118 5.1.3;4.1.3 Eigenschaften von primitiven BCH-Codes;118 5.1.4;4.1.4 Berechnung des Generatorpolynoms;120 5.2;4.2 Nicht-primitive BCH-Codes;122 5.3;4.3 Verkürzte und erweiterte BCH-Codes;123 5.4;4.4 Nicht-binäre BCH-Codes und RS-Codes;124 5.4.1;4.4.1 Nicht-binäre BCH-Codes;124 5.4.2;4.4.2 Zusammenhang zwischen RS- und BCH-Codes;124 5.5;4.5 Asymptotisches Verhalten von BCH-Codes;125 5.6;4.6 Decodierung von BCH-Codes;126 5.7;4.7 Anmerkungen;127 5.8;4.8 Übungsaufgaben;128 6;5 Weitere Codeklassen;129 6.1;5.1 RM-Codes (1. Ord.), Simplex-Codes und Walsh-Sequenzen;129 6.1.1;5.1.1 Reed-Muller- und Hamming-Code;131 6.1.2;5.1.2 Hamming- und Simplex-Code;131 6.1.3;5.1.3 Simplex-Code und binäre Pseudo-Zufallsfolgen;133 6.1.4;5.1.4 Reed-Muller- und Simplex-Code;136 6.2;5.2 Reed-Muller-Codes höherer Ordnung;138 6.3;5.3 q-wertige Hamming-Codes;141 6.4;5.4 Binäre Quadratische-Reste-Codes;143 6.5;5.5 Low-Density Parity-Check Codes;144 6.5.1;5.5.1 Definition und Darstellung;144 6.5.2;5.5.2 LDPC Codes mit Euklidischer- und Projektiver Geometrie;146 6.6;5.6 Anmerkungen;150 6.7;5.7 Übungsaufgaben;151 7;6 Eigenschaften von Blockcodes und Trellisdarstellung;153 7.1;6.1 Dualer Code und MacWilliams-Identität;153 7.2;6.2 Automorphismus;159 7.3;6.3 Gilbert-Varshamov-Schranke;159 7.4;6.4 Singleton-Schranke (MDS);161 7.5;6.5 Reiger-Schranke (Bündelfehlerkorrektur);162 7.6;6.6 Asymptotische Schranken;162 7.7;6.7 Minimales Trellis von linearen Blockcodes;164 7.7.1;6.7.1 Konstruktion mit Hilfe der Prüfmatrix;166 7.7.2;6.7.2 Konstruktion mit Hilfe der Generatormatrix;169 7.7.3;6.7.3 Eigenschaften eines minimalen Trellis;174 7.8;6.8 Anmerkungen;179 7.9;6.9 Übungsaufgaben;181 8;7 Weitere Decodierverfahren;183 8.1;7.1 Kanalmodelle und Metriken;184 8.1.1;7.1.1 q-närer symmetrischer Kanal;185 8.1.2;7.1.2 Additives weißes Gaußsches Rauschen (AWGN);186 8.1.3;7.1.3 Zeitvariante Kanäle;187 8.1.4;7.1.4 Hamming- und euk
lidische Metrik;189 8.2;7.2 Decodierprinzipien, Zuverlässigkeit, Komplexität und Codiergewinn;190 8.2.1;7.2.1 MAP- und ML-Decodierung;190 8.2.2;7.2.2 Zuverlässigkeit für die binäre Übertragung;191 8.2.3;7.2.3 Decodierkomplexität und der Satz von Evseev;197 8.2.4;7.2.4 Codiergewinn;199 8.3;7.3 Hard-Decision Decodierung;200 8.3.1;7.3.1 Permutationsdecodierung;200 8.3.2;7.3.2 Mehrheitsdecodierung (majority logic decoding);202 8.3.3;7.3.3 DA-Algorithmus;204 8.3.4;7.3.4 Viterbi-Algorithmus;207 8.4;7.4 Soft-Decision Decodierung;208 8.4.1;7.4.1 Generalized-Minimum-Distance (GMD) Decodierung;209 8.4.2;7.4.2 Chase- und Dorsch-Algorithmen;211 8.4.3;7.4.3 Listen-Viterbi-Algorithmus;213 8.4.4;7.4.4 Iterative Verfahren;217 8.5;7.5 Decodierung als Optimierungsproblem;224 8.6;7.6 Anmerkungen;227 8.7;7.7 Übungsaufgaben;228 9;8 Faltungscodes;231 9.1;8.1 Grundlagen von Faltungscodes;232 9.1.1;8.1.1 Codierung durch sequentielle Schaltkreise;233 9.1.2;8.1.2 Impulsantwort und Faltung;234 9.1.3;8.1.3 Einflusslänge, Gedächtnisordnung und Gesamteinflusslänge;236 9.1.4;8.1.4 Generatormatrix im Zeitbereich;238 9.1.5;8.1.5 Zustandsdiagramm, Codebaum und Trellis;240 9.1.6;8.1.6 Freie Distanz und Distanzfunktion;244 9.1.7;8.1.7 Terminierung, Truncation und Tail-Biting;248 9.1.8;8.1.8 Generatormatrix im transformierten Bereich;252 9.1.9;8.1.9 Systematische und katastrophale Generatormatrizen;256 9.1.10;8.1.10 Punktierte Faltungscodes;259 9.2;8.2 Algebraische Beschreibung;262 9.2.1;8.2.1 Code, Generatormatrix und Codierer;263 9.2.2;8.2.2 Faltungscodierer in Steuer- und Beobachterentwurf;263 9.2.3;8.2.3 Äquivalente Generatormatrizen;266 9.2.4;8.2.4 Smith-Form einer Generatormatrix;268 9.2.5;8.2.5 Basisgeneratormatrix;270 9.2.6;8.2.6 Katastrophale Generatormatrizen;272 9.2.7;8.2.7 Systematische Generatormatrizen;274 9.2.8;8.2.8 Prüfmatrix und dualer Code;276 9.3;8.3 Distanzmaße;277 9.3.1;8.3.1 Spalten- und Zeilendistanz;277 9.3.2;8.3.2 Erweiterte Distanzmaße;281 9.4;8.4 Maximum-Likelihood (Viterbi-
) Decodierung;285 9.4.1;8.4.1 Metrik;287 9.4.2;8.4.2 Viterbi-Algorithmus;289 9.4.3;8.4.3 Schranken zur Decodierfähigkeit;293 9.4.4;8.4.4 Interleaving;296 9.4.5;8.4.5 Soft-Output-Viterbi-Algorithmus (SOVA);297 9.5;8.5 Soft-Output-Decodierung;300 9.6;8.6 Sequentielle Decodierung;303 9.6.1;8.6.1 Fano-Metrik;304 9.6.2;8.6.2 Zigangirov-Jelinek (ZJ)-Decodierer;305 9.6.3;8.6.3 Fano-Decodierer;307 9.7;8.7 (Partial-) Unit-Memory-Codes, (P)UM-Codes;308 9.7.1;8.7.1 Definition von (P)UM-Codes;308 9.7.2;8.7.2 Trellis von (P)UM-Codes;310 9.7.3;8.7.3 Distanzmaße bei (P)UM-Codes;311 9.7.4;8.7.4 Konstruktion von (P)UM-Codes;312 9.7.5;8.7.5 BMD-Decodierung;315 9.8;8.8 Tabellen guter Codes;317 9.9;8.9 Anmerkungen;321 9.10;8.10 Übungsaufgaben;323 10;9 Verallgemeinerte Codeverkettung;325 10.1;9.1 Einführende Beispiele;328 10.2;9.2 GC-Codes mit Blockcodes;333 10.2.1;9.2.1 Definition von GC-Codes;334 10.2.2;9.2.2 Zur Partitionierung von Blockcodes;336 10.2.3;9.2.3 Codekonstruktionen;343 10.2.4;9.2.4 Decodierung von GC-Codes;349 10.2.5;9.2.5 UEP-Codes mit mehrstufigem Fehlerschutz;367 10.2.6;9.2.6 Zyklische Codes als GC-Codes;368 10.3;9.3 Error Locating Codes;374 10.3.1;9.3.1 Verallgemeinerte Error Locating (GEL) Codes;375 10.3.2;9.3.2 GEL Codes für zweidimensionale Fehler;380 10.4;9.4 GC-Codes mit Faltungscodes;388 10.4.1;9.4.1 Partitionierung von (P)UM-Codes;388 10.4.2;9.4.2 Einführende Beispiele zur Partitionierung durch das Trellis;392 10.4.3;9.4.3 Partitionierung von Faltungscodes;401 10.4.4;9.4.4 Konstruktion und Decodierung eines GC-Codes;404 10.4.5;9.4.5 Turbo-Codes und ungelöste Probleme;411 10.5;9.5 GC-Codes mit Block- und Faltungscodes;413 10.5.1;9.5.1 Innere Faltungs- und äußere Blockcodes;413 10.5.2;9.5.2 Innere Block- und äußere Faltungscodes;418 10.6;9.6 Mehrfachverkettung und Reed-Muller-Codes;420 10.6.1;9.6.1 GMC, Decodieralgorithmus für RM-Codes;423 10.6.2;9.6.2 L-GMC, Listendecodierung von RM-Codes;428 10.6.3;9.6.3 Simulationsergebnisse und Komplexität;432 10.7;9.7 Anmer
kungen;436 11;10 Codierte Modulation;441 11.1;10.1 Einführende Beispiele;441 11.2;10.2 GC mit Blockmodulation;444 11.2.1;10.2.1 Partitionierung von Signalen;444 11.2.2;10.2.2 Definition der Codierten Modulation;446 11.2.3;10.2.3 Lattices und verallgemeinerte Mehrfachverkettung;448 11.2.4;10.2.4 Decodierung;452 11.2.5;10.2.5 Trelliscodierte Modulationssysteme;456 11.3;10.3 GC mit Faltungsmodulation;458 11.3.1;10.3.1 Einführendes Beispiel;458 11.3.2;10.3.2 Algebraische Beschreibung der Faltungsmodulation;460 11.3.3;10.3.3 Partitionierung für Faltungsmodulation;463 11.3.4;10.3.4 Äußere Faltungscodes;464 11.3.5;10.3.5 Äußere Blockcodes;468 11.4;10.4 Anmerkungen;468 12;A Euklidischer Algorithmus;471 12.1;A.1 Euklidischer Algorithmus für ganze Zahlen;471 12.2;A.2 Euklidischer Algorithmus für Polynome;473 13;B Metriken;479 13.1;B.1 Lee-Metrik;479 13.2;B.2 Manhattan- und Mannheim-Metrik;482 13.3;B.3 Kombinatorische Metrik;483 13.4;ösungen zu den Übungsaufgaben;487 14;Literaturverzeichnis;519 15;Index;541