Iterative Error Correction: Turbo, Low-Density Parity-Check and Repeat-Accumulate Codes

Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 9
Preface......Page 13
Book outline......Page 15
Acknowledgements......Page 16
Notation......Page 17
Commonly used abbreviations......Page 21
1 Channels, codes and capacity......Page 22
1.1 Binary input memoryless channels......Page 23
1.2.1 A measure of information......Page 29
1.2.2 Entropy......Page 31
Mutual information......Page 33
1.2.3 Capacity......Page 34
1.3 Codes and decoding......Page 37
1.3.1 Decoding......Page 39
Maximum likelihood (ML) decoding......Page 40
Maximum a posteriori (MAP) decoding......Page 43
1.3.2 Performance measures......Page 45
Union bounds......Page 46
1.4 Bibliographic notes......Page 50
1.5 Exercises......Page 51
2.2 Error correction using parity checks......Page 55
2.2.1 Low-density parity-check codes......Page 58
2.3 Encoding......Page 61
2.3.1 (Almost) linear-time encoding for LDPC codes......Page 65
2.4 Decoding......Page 69
2.4.1 Message passing on the binary erasure channel......Page 71
2.4.2 Bit-flipping decoding......Page 75
2.4.3 Sum-product decoding......Page 82
2.5 Bibliographic notes......Page 92
2.6 Exercises......Page 93
3.2 LDPC properties......Page 96
Regular versus irregular codes......Page 97
Low-rank parity-check matrices......Page 101
3.2.2 Girth and expansion......Page 103
3.2.3 Codeword and pseudo-codeword weights......Page 105
Minimum distance......Page 106
Stopping sets......Page 107
3.2.4 Cyclic and quasi-cyclic codes......Page 110
Row-circulant quasi-cyclic codes......Page 111
Block-circulant quasi-cyclic codes......Page 114
Routing complexity......Page 116
Serial versus parallel implementation......Page 117
3.3.1 Pseudo-random constructions......Page 118
Column or row splitting......Page 121
Bit-filling and progressive edge growth (PEG) Tanner graphs......Page 122
Superposition and protographs......Page 123
Codes from combinatorial designs......Page 126
Codes from finite geometries......Page 129
Partial geometries......Page 131
Resolvable designs......Page 133
3.4 LDPC design rules......Page 135
3.5 Bibliographic notes......Page 138
3.6 Exercises......Page 139
4.2 Convolutional encoders......Page 142
4.2.1 Memory order and impulse response......Page 146
Generator matrix......Page 147
4.2.2 Recursive convolutional encoders......Page 148
4.2.3 Puncturing......Page 152
4.2.4 Convolutional code trellises......Page 153
4.2.5 Minimum free distance......Page 156
4.3.1 Maximum a posteriori (BCJR) decoding......Page 157
4.3.2 Log MAP decoding......Page 169
Log likelihood ratios......Page 170
4.3.3 Maximum likelihood (Viterbi) decoding......Page 177
4.4 Bibliographic notes......Page 181
4.5 Exercises......Page 182
5.2 Turbo encoders......Page 186
Interleavers......Page 187
Code rate......Page 188
Code termination......Page 189
5.3 Iterative turbo decoding......Page 190
5.4.1 Interleaving gain......Page 197
5.4.2 Choosing the component codes......Page 199
Effective free distance......Page 201
Spreading factor......Page 203
Dispersion......Page 205
Interleaver delay......Page 206
Odd–even interleavers......Page 207
Algorithmic interleavers......Page 208
5.4.4 Design rules......Page 209
5.5 Factor graphs and implementation......Page 211
5.5.1 Implementation and complexity......Page 212
Number of iterations......Page 213
Serial versus parallel implementation......Page 214
Hard-decision and absolute-value stopping criteria......Page 215
Cross entropy stopping criterion......Page 216
5.6 Bibliographic notes......Page 217
5.7 Exercises......Page 219
6.1 Serial concatenation......Page 222
6.1.2 Turbo decoding of SC codes......Page 224
6.1.3 Code design......Page 228
6.2 Repeat-accumulate codes......Page 230
6.2.1 Encoding RA codes......Page 232
Repetition code decoder......Page 233
Combiner decoder......Page 234
Turbo decoding of RA codes......Page 235
6.2.3 Sum–product decoding of RA codes......Page 238
6.2.4 Irregular RA codes......Page 241
6.2.5 Weight-3 IRA codes......Page 245
6.2.6 Accumulate-repeat-accumulate codes......Page 247
6.2.7 Code design......Page 248
L-type interleavers......Page 251
6.3 Bibliographic notes......Page 253
6.4 Exercises......Page 255
7.1 Introduction......Page 258
7.2 Density evolution......Page 259
Regular LDPC codes......Page 260
Irregular LDPC codes......Page 261
7.2.2 Ensemble thresholds......Page 264
Stability......Page 267
7.2.3 Density evolution and repeat-accumulate codes......Page 268
7.2.4 Density evolution on general binary input memoryless channels......Page 270
Thresholds calculated using density evolution......Page 273
7.2.5 Density evolution and turbo codes......Page 275
7.2.6 Designing ensembles with good thresholds......Page 277
Capacity-achieving ensembles......Page 280
7.2.7 Approximations to density evolution......Page 281
7.3 EXIT charts......Page 282
7.3.1 Mutual information......Page 283
7.3.2 EXIT charts for turbo codes......Page 285
Exit charts for serially concatenated codes......Page 293
7.3.3 EXIT charts for RA codes......Page 294
EXIT charts for IRA codes......Page 295
7.3.4 EXIT charts for LDPC codes......Page 297
7.4 Bibliographic notes......Page 300
7.5 Exercises......Page 302
8.2 Maximum likelihood analysis......Page 304
8.2.1 Input-output weight enumerating functions for convolutional codes......Page 306
8.2.2 Parallel concatenated code ensembles......Page 311
Interleaving gain......Page 313
Effective free distance......Page 315
8.2.3 Serially concatenated code ensembles......Page 317
Interleaving gain......Page 319
Effective free distance......Page 320
8.2.4 The error floor of irregular block codes......Page 322
Threshold versus error floor......Page 324
8.2.5 Designing iterative codes to improve the interleaving gain and error floor......Page 326
8.2.6 Asymptotic (in the code length) performance of iterative ensembles......Page 327
Asymptotically vanishing word error probability......Page 329
8.3 Finite-length analysis......Page 330
Expurgated ensembles......Page 334
Ensembles without repeated edges......Page 335
Pseudo-codewords......Page 338
8.4 Bibliographic notes......Page 339
8.5 Exercises......Page 341
References......Page 343
Index......Page 352