Kanalcodierung (eBook)

Martin Bossert (Autor)

eBook Download: PDF

2013 | 1. Auflage
549 Seiten
De Gruyter Oldenbourg (Verlag)
978-3-486-75516-9 (ISBN)

Infos

Die Kanalcodierung zur Fehlererkennung und -korrektur ist ein wesentlicher Bestandteil in modernen digitalen Kommunikationssystemen wie 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.

Martin Bossert, Ulm

Autor

lt;!doctype html public "-//w3c//dtd html 4.0 transitional//en">

Martin Bossert, Ulm

Inhalt

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

Rezensionen

lt;!doctype html public "-//w3c//dtd html 4.0 transitional//en">

"Der Tiefgang des Buches ist hervorragend."
Prof. Dr. C. G. Schäffer, Helmut-Schmidt-Universität Hamburg

Produkt-Details

• Erscheint lt. Verlag: 28.6.2013
• Verlagsort: Berlin/München/Boston
• Sprache: deutsch
• Themenwelt: Technik ► Bauwesen
• Themenwelt: Technik ► Elektrotechnik / Energietechnik
• Themenwelt: Technik ► Maschinenbau
• Schlagworte: Bossert • Digitale Kommunikation • Fehlererkennung • Fehlerkorrektur • Kanalcodierung
• ISBN-10: 3-486-75516-1 / 3486755161
• ISBN-13: 978-3-486-75516-9 / 9783486755169