Preface ...................................................... xiii
1 Introduction .............................................. 1
§1.1 Why You Should Read This Book ............................. 1
§1.2 Communications Problem .................................... 2
§1.3 Coding: Trial and Error ................................... 4
§1.4 Codes and Ensembles ....................................... 5
§1.5 MAP and ML Decoding and APP Processing .................... 9
§1.6 Channel Coding Theorem .................................... 9
§1.7 Linear Codes and Complexity .............................. 13
§1.8 Rate, Probability, Complexity, and Length ................ 18
§1.9 Tour of Iterative Decoding ............................... 23
§1.10 Notation, Conventions, and Useful Facts .................. 27
Notes .................................................... 32
Problems ................................................. 35
References ............................................... 44
2 Factor Graphs ............................................ 49
§2.1 Distributive Law ......................................... 49
§2.2 Graphical Representation of Factorizations ............... 50
§2.3 Recursive Determination of Marginals ..................... 51
§2.4 Marginalization via Message Passing ...................... 54
§2.5 Decoding via Message Passing ............................. 57
§2.6 Limitations of Cycle-Free Codes .......................... 64
§2.7 Message Passing on Codes with Cycles ..................... 65
Notes .................................................... 65
Problems ................................................. 67
References ............................................... 68
3 Binary Erasure Channel ................................... 71
§3.1 Channel Model ............................................ 71
§3.2 Transmission via Linear Codes ............................ 72
§3.3 Tanner Graphs ............................................ 75
§3.4 Low-Density Parity-Check Codes ........................... 76
§3.5 Message-Passing Decoder .................................. 82
§3.6 Two Basic Simplifications ................................ 83
§3.7 Computation Graph and Tree Ensemble ...................... 87
§3.8 Tree Channel and Convergence to Tree Channel ............. 94
§3.9 Density Evolution ........................................ 95
§3.10 Monotonicity ............................................. 96
§3.11 Threshold ................................................ 97
§3.12 Fixed Point Characterization of Threshold ................ 98
§3.13 Stability ............................................... 100
§3.14 EXIT Charts ............................................. 101
§3.15 Capacity-Achieving Degree Distributions ................. 108
§3.16 Gallager's Lower Bound on Density ....................... 111
§3.17 Optimally Sparse Degree Distribution Pairs .............. 113
§3.18 Degree Distributions with Given Maximum Degree .......... 114
§3.19 Peeling Decoder and Order of Limits ..................... 115
§3.20 EXIT Function and MAP Performance ....................... 122
§3.21 Maxwell Decoder ......................................... 131
§3.22 Exact Finite-Length Analysis ............................ 134
§3.23 Finite-Length Scaling ................................... 143
§3.24 Weight Distribution and Error Floor ..................... 148
Notes ................................................... 156
Problems ................................................ 160
References .............................................. 169
4 Binary Memoryless Symmetric Channels .................... 175
§4.1 Basic Definitions and Examples .......................... 175
§4.2 Message-Passing Decoder ................................. 209
§4.3 Two Basic Simplifications ............................... 214
§4.4 Tree Channel and Convergence to Tree Channel ............ 216
§4.5 Density Evolution ....................................... 217
§4.6 Monotonicity ............................................ 221
§4.7 Threshold ............................................... 226
§4.8 Fixed Point Characterization of Threshold ............... 226
§4.9 Stability ............................................... 230
§4.10 EXIT Charts ............................................. 234
§4.11 Gallager's Lower Bound on Density ....................... 245
§4.12 GEXIT Function and MAP Performance ...................... 249
§4.13 Finite-Length Scaling ................................... 257
§4.14 Error Floor under MAP Decoding .......................... 258
Notes ................................................... 261
Problems ................................................ 267
References .............................................. 283
5 General Channels ........................................ 291
§5.1 Fading Channel .......................................... 291
§5.2 Channel ................................................. 294
§5.3 Channels with Memory .................................... 297
§5.4 Coding for High Spectral Efficiency ..................... 303
§5.5 Multiple-Access Channel ................................. 308
Notes ................................................... 312
Problems ................................................ 314
References .............................................. 316
6 Turbo Codes ............................................. 323
§6.1 Convolutional Codes ..................................... 323
§6.2 Structure and Encoding .................................. 334
§6.3 Decoding ................................................ 336
§6.4 Basic Simplifications ................................... 339
§6.5 Density Evolution ....................................... 341
§6.6 Stability Condition ..................................... 344
§6.7 EXIT Charts ............................................. 346
§6.8 GEXIT Function and MAP Performance ...................... 347
§6.9 Weight Distribution and Error Floor ..................... 349
§6.10 Variations on the Theme ................................. 363
Notes ................................................... 365
Problems ................................................ 369
References .............................................. 375
7 General Ensembles ....................................... 381
§7.1 Multi-Edge-Type LDPC Code Ensembles ..................... 382
§7.2 Multi-Edge-Type LDPC Codes: Analysis .................... 389
§7.3 Structured Codes ........................................ 397
§7.4 Non-Binary Codes ........................................ 405
§7.5 Low-Density Generator Codes and Rateless Codes .......... 410
Notes ................................................... 418
Problems ................................................ 421
References .............................................. 421
8 Expander Codes and Flipping Algorithm ................... 427
§8.1 Building Codes from Expanders ........................... 427
§8.2 Flipping Algorithm ...................................... 428
§8.3 Bound on Expansion of a Graph ........................... 429
§8.4 Expansion of a Random Graph ............................. 431
Notes ................................................... 434
Problems ................................................ 435
References .............................................. 435
A Encoding Low-Density Parity-Check Codes ................. 437
§A.1 Encoding Generic LDPC Codes ............................. 437
§A.2 Greedy Upper Triangulation .............................. 443
§А.3 Linear Encoding Complexity .............................. 448
§A.4 Analysis of Asymptotic Gap .............................. 452
Notes ................................................... 456
Problems ................................................ 456
References .............................................. 457
В Efficient Implementation of Density Evolution ........... 459
§B.1 Quantization ............................................ 460
§B.2 Variable-Node Update via Fourier Transform .............. 460
§В.3 Check-Node Update via Table Method ...................... 462
§B.4 Check-Node Update via Fourier Method .................... 464
Notes ................................................... 477
Problems ................................................ 477
References .............................................. 478
С Concentration Inequalities .............................. 479
§C.1 First and Second Moment Method .......................... 480
§C.2 Bernstein's Inequality .................................. 482
§С.3 Martingales ............................................. 484
§C.4 Wormald's Differential Equation Approach ................ 490
§C.5 Convergence to Poisson Distribution ..................... 497
Notes ................................................... 500
Problems ................................................ 501
References .............................................. 502
D Formal Power Sums ....................................... 505
§D.i Definition .............................................. 505
§D.2 Basic Properties ........................................ 505
§D.3 Summation of Subsequences ............................... 506
§D.4 Coefficient Growth of Powers of Polynomials ............. 507
§D.5 Unimodality ............................................. 529
Notes ................................................... 529
Problems ................................................ 530
References .............................................. 535
E Convexity, Degradation, and Stability ................... 537
Authors ....................................................... 551
Index ......................................................... 559
|
