Kanalcodierung

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