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.
Author(s): Martin Bossert
Edition: 3. Auflage
Publisher: Oldenbourg Wissenschaftsverlag
Year: 2013
Language: German
Pages: XVIII+532
City: München
Kanalcodierung, 3., überarbeitete Auflage......Page 4
Vorwort zur 3. Auflage......Page 6
Vorwort zur 2. Auflage......Page 8
Vorwort zur 1. Auflage......Page 12
Inhaltsverzeichnis......Page 14
Einleitung......Page 20
1 Grundbegriffe......Page 24
1.1 Gewicht, Distanz......Page 26
1.1.1 Mindestdistanz und Fehlerkorrigierbarkeit......Page 27
1.1.2 Hamming-Schranke......Page 28
1.2 Prüfmatrix und Syndrom......Page 30
1.3 Decodierprinzipien......Page 31
1.4 Fehlerwahrscheinlichkeit......Page 34
1.5 Hamming-Codes......Page 36
1.6 Generatormatrix......Page 38
1.7 Zyklische Codes......Page 39
1.9 Erweiterung und Verkürzung von Codes......Page 40
1.10 Kanalkapazität und Kanalcodiertheorem......Page 42
1.11 Anmerkungen......Page 44
1.12 Übungsaufgaben......Page 45
2.2 Ringe, Körper......Page 48
2.3 Primkörper......Page 50
2.4 Gaußkörper......Page 53
2.5.1 Irreduzible Polynome......Page 55
2.5.2 Primitive Polynome, Wurzeln......Page 56
2.5.3 Eigenschaften von Erweiterungskörpern......Page 59
2.6 Kreisteilungsklassen und quadratische Reste......Page 61
2.7 Anmerkungen......Page 62
2.8 Übungsaufgaben......Page 63
3.1 Definition von RS-Codes......Page 66
3.1.1 Diskrete Fourier-Transformation (DFT)......Page 67
3.1.2 Parameter von RS-Codes......Page 69
3.1.3 Generatorpolynom......Page 70
3.1.4 Prüfpolynom......Page 71
3.1.5 Codierung......Page 72
3.1.6 Zwei Eigenschaften zyklischer Codes......Page 73
3.1.7 GRS-Codes und Erweiterungen von RS-Codes......Page 74
3.2.1 Prinzip der algebraischen Decodierung......Page 78
3.2.2 Der Fehler als zyklischer Code......Page 81
3.2.3 Decodierung mit Fehler-Generatorpolynom......Page 83
3.2.4 Decodierung mit Fehler-Prüfpolynom......Page 89
3.2.5 Verfahren von Sugiyama et al., Welch–Berlekamp und
Gao......Page 94
3.2.6 Verfahren von Gorenstein–Zierler, Peterson und
Berlekamp–Massey......Page 99
3.2.7 Korrektur von Fehlern und Auslöschungen......Page 102
3.3.1 Interleaved RS-Codes (IRS)......Page 106
3.3.2 Power Decodierung......Page 108
3.4 Algebraische Listendecodierung durch
Interpolation......Page 110
3.5 Anmerkungen......Page 111
3.6 Übungsaufgaben......Page 113
4.1.1 Definition mit Kreisteilungsklassen......Page 116
4.1.3 Eigenschaften von primitiven BCH-Codes......Page 119
4.1.4 Berechnung des Generatorpolynoms......Page 121
4.2 Nicht-primitive BCH-Codes......Page 123
4.3 Verkürzte und erweiterte BCH-Codes......Page 124
4.4.2 Zusammenhang zwischen RS- und BCH-Codes......Page 125
4.5 Asymptotisches Verhalten von BCH-Codes......Page 126
4.6 Decodierung von BCH-Codes......Page 127
4.7 Anmerkungen......Page 128
4.8 Übungsaufgaben......Page 129
5.1 Reed-Muller-Codes (1. Ordnung),
Simplex-Codes und Walsh-Sequenzen......Page 130
5.1.2 Hamming- und Simplex-Code......Page 132
5.1.3 Simplex-Code und binäre Pseudo-Zufallsfolgen......Page 134
5.1.4 Reed-Muller- und Simplex-Code......Page 137
5.2 Reed-Muller-Codes höherer Ordnung......Page 139
5.3 q-wertige Hamming-Codes......Page 142
5.4 Binäre Quadratische-Reste-Codes......Page 144
5.5.1 Definition und Darstellung......Page 145
5.5.2 LDPC Codes mit Euklidischer- und Projektiver
Geometrie......Page 147
5.6 Anmerkungen......Page 151
5.7 Übungsaufgaben......Page 152
6.1 Dualer Code und MacWilliams-Identität......Page 154
6.3 Gilbert-Varshamov-Schranke......Page 160
6.4 Singleton-Schranke (MDS)......Page 162
6.6 Asymptotische Schranken......Page 163
6.7 Minimales Trellis von linearen Blockcodes......Page 165
6.7.1 Konstruktion mit Hilfe der Prüfmatrix......Page 167
6.7.2 Konstruktion mit Hilfe der Generatormatrix......Page 170
6.7.3 Eigenschaften eines minimalen Trellis......Page 175
6.8 Anmerkungen......Page 180
6.9 Übungsaufgaben......Page 182
7 Weitere Decodierverfahren......Page 184
7.1 Kanalmodelle und Metriken......Page 185
7.1.1 q-närer symmetrischer Kanal......Page 186
7.1.2 Additives weißes Gaußsches Rauschen (AWGN)......Page 187
7.1.3 Zeitvariante Kanäle......Page 188
7.1.4 Hamming- und euklidische Metrik......Page 190
7.2.1 MAP- und ML-Decodierung......Page 191
7.2.2 Zuverlässigkeit für die binäre Übertragung......Page 192
7.2.3 Decodierkomplexität und der Satz von Evseev......Page 198
7.2.4 Codiergewinn......Page 200
7.3.1 Permutationsdecodierung......Page 201
7.3.2 Mehrheitsdecodierung (majority logic decoding)......Page 203
7.3.3 DA-Algorithmus......Page 205
7.3.4 Viterbi-Algorithmus......Page 208
7.4 Soft-Decision Decodierung......Page 209
7.4.1 Generalized-Minimum-Distance (GMD) Decodierung......Page 210
7.4.2 Chase- und Dorsch-Algorithmen......Page 212
7.4.3 Listen-Viterbi-Algorithmus......Page 214
7.4.4 Iterative Verfahren......Page 218
7.5 Decodierung als Optimierungsproblem......Page 225
7.6 Anmerkungen......Page 228
7.7 Übungsaufgaben......Page 229
8 Faltungscodes......Page 232
8.1 Grundlagen von Faltungscodes......Page 233
8.1.1 Codierung durch sequentielle Schaltkreise......Page 234
8.1.2 Impulsantwort und Faltung......Page 235
8.1.3 Einflusslänge, Gedächtnisordnung und
Gesamteinflusslänge......Page 237
8.1.4 Generatormatrix im Zeitbereich......Page 239
8.1.5 Zustandsdiagramm, Codebaum und Trellis......Page 241
8.1.6 Freie Distanz und Distanzfunktion......Page 245
8.1.7 Terminierung, Truncation und Tail-Biting......Page 249
8.1.8 Generatormatrix im transformierten Bereich......Page 253
8.1.9 Systematische und katastrophale Generatormatrizen......Page 257
8.1.10 Punktierte Faltungscodes......Page 260
8.2 Algebraische Beschreibung......Page 263
8.2.2 Faltungscodierer in Steuer- und Beobachterentwurf......Page 264
8.2.3 Äquivalente Generatormatrizen......Page 267
8.2.4 Smith-Form einer Generatormatrix......Page 269
8.2.5 Basisgeneratormatrix......Page 271
8.2.6 Katastrophale Generatormatrizen......Page 273
8.2.7 Systematische Generatormatrizen......Page 275
8.2.8 Prüfmatrix und dualer Code......Page 277
8.3.1 Spalten- und Zeilendistanz......Page 278
8.3.2 Erweiterte Distanzmaße......Page 282
8.4 Maximum-Likelihood (Viterbi-) Decodierung......Page 286
8.4.1 Metrik......Page 288
8.4.2 Viterbi-Algorithmus......Page 290
8.4.3 Schranken zur Decodierfähigkeit......Page 294
8.4.4 Interleaving......Page 297
8.4.5 Soft-Output-Viterbi-Algorithmus (SOVA)......Page 298
8.5 Soft-Output-Decodierung......Page 301
8.6 Sequentielle Decodierung......Page 304
8.6.1 Fano-Metrik......Page 305
8.6.2 Zigangirov-Jelinek (ZJ)-Decodierer......Page 306
8.6.3 Fano-Decodierer......Page 308
8.7.1 Definition von (P)UM-Codes......Page 309
8.7.2 Trellis von (P)UM-Codes......Page 311
8.7.3 Distanzmaße bei (P)UM-Codes......Page 312
8.7.4 Konstruktion von (P)UM-Codes......Page 313
8.7.5 BMD-Decodierung......Page 316
8.8 Tabellen guter Codes......Page 318
8.9 Anmerkungen......Page 322
8.10 Übungsaufgaben......Page 324
9 Verallgemeinerte Codeverkettung......Page 326
9.1 Einführende Beispiele......Page 329
9.2 GC-Codes mit Blockcodes......Page 334
9.2.1 Definition von GC-Codes......Page 335
9.2.2 Zur Partitionierung von Blockcodes......Page 337
9.2.3 Codekonstruktionen......Page 344
9.2.4 Decodierung von GC-Codes......Page 350
9.2.5 UEP-Codes mit mehrstufigem Fehlerschutz......Page 368
9.2.6 Zyklische Codes als GC-Codes......Page 369
9.3 Error Locating Codes......Page 375
9.3.1 Verallgemeinerte Error Locating (GEL) Codes......Page 376
9.3.2 GEL Codes für zweidimensionale Fehler......Page 381
9.4.1 Partitionierung von (P)UM-Codes......Page 389
9.4.2 Einführende Beispiele zur Partitionierung durch das
Trellis......Page 393
9.4.3 Partitionierung von Faltungscodes......Page 402
9.4.4 Konstruktion und Decodierung eines GC-Codes......Page 405
9.4.5 Turbo-Codes und ungelöste Probleme......Page 412
9.5.1 Innere Faltungs- und äußere Blockcodes......Page 414
9.5.2 Innere Block- und äußere Faltungscodes......Page 419
9.6 Mehrfachverkettung und Reed-Muller-Codes......Page 421
9.6.1 GMC, Decodieralgorithmus für RM-Codes......Page 424
9.6.2 L-GMC, Listendecodierung von RM-Codes......Page 429
9.6.3 Simulationsergebnisse und Komplexität......Page 433
9.7 Anmerkungen......Page 437
10.1 Einführende Beispiele......Page 442
10.2.1 Partitionierung von Signalen......Page 445
10.2.2 Definition der Codierten Modulation......Page 447
10.2.3 Lattices und verallgemeinerte Mehrfachverkettung......Page 449
10.2.4 Decodierung......Page 453
10.2.5 Trelliscodierte Modulationssysteme......Page 457
10.3.1 Einführendes Beispiel......Page 459
10.3.2 Algebraische Beschreibung der Faltungsmodulation......Page 461
10.3.3 Partitionierung für Faltungsmodulation......Page 464
10.3.4 Äußere Faltungscodes......Page 465
10.4 Anmerkungen......Page 469
A.1 Euklidischer Algorithmus für ganze Zahlen......Page 472
A.2 Euklidischer Algorithmus für Polynome......Page 474
B.1 Lee-Metrik......Page 480
B.2 Manhattan- und Mannheim-Metrik......Page 483
B.3 Kombinatorische Metrik......Page 484
C. Lösungen zu den Übungsaufgaben......Page 488
Literaturverzeichnis......Page 520
Index......Page 542
