Coding Theory - Algorithms, Architectures, and Applications

Coding Theory......Page 4
Contents......Page 8
Preface......Page 12
1.1 Communication Systems......Page 16
1.2.1 Entropy......Page 18
1.2.2 Channel Capacity......Page 19
1.2.3 Binary Symmetric Channel......Page 20
1.2.4 AWGN Channel......Page 21
1.3 A Simple Channel Code......Page 23
2 Algebraic Coding Theory......Page 28
2.1 Fundamentals of Block Codes......Page 29
2.1.1 Code Parameters......Page 31
2.1.2 Maximum Likelihood Decoding......Page 34
2.1.3 Binary Symmetric Channel......Page 38
2.1.4 Error Detection and Error Correction......Page 40
2.2.2 Generator Matrix......Page 42
2.2.3 Parity-Check Matrix......Page 45
2.2.4 Syndrome and Cosets......Page 46
2.2.5 Dual Code......Page 51
2.2.6 Bounds for Linear Block Codes......Page 52
2.2.7 Code Constructions......Page 56
2.2.8 Examples of Linear Block Codes......Page 61
2.3.1 Definition of Cyclic Codes......Page 77
2.3.2 Generator Polynomial......Page 78
2.3.3 Parity-Check Polynomial......Page 82
2.3.4 Dual Codes......Page 85
2.3.5 Linear Feedback Shift Registers......Page 86
2.3.6 BCH Codes......Page 89
2.3.7 Reed–Solomon Codes......Page 96
2.3.8 Algebraic Decoding Algorithm......Page 99
2.4 Summary......Page 108
3 Convolutional Codes......Page 112
3.1.1 Convolutional Encoder......Page 113
3.1.2 Generator Matrix in the Time Domain......Page 116
3.1.3 State Diagram of a Convolutional Encoder......Page 118
3.1.4 Code Termination......Page 119
3.1.5 Puncturing......Page 121
3.1.6 Generator Matrix in the D-Domain......Page 123
3.1.7 Encoder Properties......Page 125
3.2 Trellis Diagram and the Viterbi Algorithm......Page 127
3.2.1 Minimum Distance Decoding......Page 128
3.2.2 Trellises......Page 130
3.2.3 Viterbi Algorithm......Page 131
3.3.1 Free Distance......Page 136
3.3.2 Active Distances......Page 137
3.3.3 Weight Enumerators for Terminated Codes......Page 141
3.3.4 Path Enumerators......Page 144
3.3.5 Pairwise Error Probability......Page 146
3.3.6 Viterbi Bound......Page 149
3.4.1 Euclidean Metric......Page 151
3.4.2 Support of Punctured Codes......Page 152
3.4.3 Implementation Issues......Page 153
3.5 Soft-output Decoding......Page 155
3.5.1 Derivation of APP Decoding......Page 156
3.5.2 APP Decoding in the Log Domain......Page 160
3.6.1 Coding of Speech Data......Page 162
3.6.2 Hybrid ARQ......Page 165
3.6.3 EGPRS Modulation and Coding......Page 167
3.6.4 Retransmission Mechanism......Page 170
3.6.5 Link Adaptation......Page 171
3.6.6 Incremental Redundancy......Page 172
3.7 Summary......Page 175
4 Turbo Codes......Page 178
4.1.1 Codes Based on Sparse Graphs......Page 180
4.1.2 Decoding for the Binary Erasure Channel......Page 183
4.1.3 Log-Likelihood Algebra......Page 184
4.1.4 Belief Propagation......Page 189
4.2.1 Product Codes......Page 192
4.2.2 Iterative Decoding of Product Codes......Page 195
4.3.1 Parallel Concatenation......Page 197
4.3.2 The UMTS Turbo Code......Page 198
4.3.3 Serial Concatenation......Page 199
4.3.4 Partial Concatenation......Page 200
4.3.5 Turbo Decoding......Page 201
4.4 EXIT Charts......Page 203
4.4.1 Calculating an EXIT Chart......Page 204
4.4.2 Interpretation......Page 206
4.5.1 Partial Weights......Page 211
4.5.2 Expected Weight Distribution......Page 212
4.6 Woven Convolutional Codes......Page 213
4.6.1 Encoding Schemes......Page 215
4.6.2 Distance Properties of Woven Codes......Page 217
4.6.3 Woven Turbo Codes......Page 220
4.6.4 Interleaver Design......Page 223
4.7 Summary......Page 227
5.1 Introduction......Page 230
5.1.1 Digital Modulation Schemes......Page 231
5.1.2 Diversity......Page 238
5.2.1 Basic Description......Page 244
5.2.2 Spatial Channel Models......Page 249
5.2.3 Channel Estimation......Page 254
5.3.1 Channel Capacity......Page 256
5.3.2 Outage Probability and Outage Capacity......Page 265
5.3.3 Ergodic Error Probability......Page 267
5.4.1 Alamouti’s Scheme......Page 272
5.4.2 Extension to More than Two Transmit Antennas......Page 275
5.4.3 Simulation Results......Page 278
5.5.1 General Concept......Page 280
5.5.2 Iterative APP Preprocessing and Per-layer Decoding......Page 282
5.5.3 Linear Multilayer Detection......Page 287
5.5.4 Original BLAST Detection......Page 290
5.5.5 QL Decomposition and Interference Cancellation......Page 293
5.5.6 Performance of Multi-Layer Detection Schemes......Page 302
5.5.7 Unified Description by Linear Dispersion Codes......Page 306
5.6 Summary......Page 309
A.1.1 Groups......Page 310
A.1.2 Rings......Page 311
A.1.3 Finite Fields......Page 313
A.2 Vector Spaces......Page 314
A.3 Polynomials and Extension Fields......Page 315
A.4 Discrete Fourier Transform......Page 320
B Linear Algebra......Page 326
C Acronyms......Page 334
Bibliography......Page 340
Index......Page 350