[Tom.Richardson].Modern.coding.theory.[Unpublished].updated.time.by.time

hcuieee

1 INTRODUCTION 19
1.1 Codes and Their Applications . . . . . . . . . . . . . . . . . . . 19
1.2 The Communications Problem . . . . . . . . . . . . . . . . . . . 20
1.3 Coding: (Two) Trial(s, their Rate) and (their Associated) Error . . 21
1.4 Codes and Ensembles . . . . . . . . . . . . . . . . . . . . . . . . 22
1.5 MAP and ML Decoding and their Optimality . . . . . . . . . . . 25
1.6 The Channel Coding Theorem . . . . . . . . . . . . . . . . . . . 26
1.7 The Complexity of Coding . . . . . . . . . . . . . . . . . . . . . 28
1.7.1 Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . 29
1.7.2 The Description/Encoding Complexity of Linear Codes . . 32
1.7.3 The MAP Decoding Complexity of Linear Codes . . . . . 32
1.8 Rate, Probability, Complexity and Length . . . . . . . . . . . . . 34
1.8.1 Unbounded Complexity . . . . . . . . . . . . . . . . . . 35
1.8.2 Unbounded Delay . . . . . . . . . . . . . . . . . . . . . 36
1.9 A First Tour of Iterative Coding . . . . . . . . . . . . . . . . . . 37
1.10 Notation and Conventions . . . . . . . . . . . . . . . . . . . . . . 42
Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2 THE BINARY ERASURE CHANNEL 57
2.1 The Channel Model . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.2 Transmission via Linear Codes . . . . . . . . . . . . . . . . . . . 58
2.2.1 Maximum A Posteriori Block Decoding . . . . . . . . . . 59
2.2.2 Maximum A Posteriori Bit Decoding . . . . . . . . . . . 59
2.3 Solving (Sparse) Linear Systems Iteratively . . . . . . . . . . . . 61
2.4 Tanner Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.5 Low-Density Parity-Check Codes . . . . . . . . . . . . . . . . . 64
2.6 Iterative Decoding of LDPC Codes . . . . . . . . . . . . . . . . . 68
2.7 The Message-Passing Decoder . . . . . . . . . . . . . . . . . . . 71
2.8 Analysis: Basic Simplifications . . . . . . . . . . . . . . . . . . . 73
2.8.1 Restriction to the All-Zero Codeword . . . . . . . . . . . 73
2.8.2 Concentration . . . . . . . . . . . . . . . . . . . . . . . . 74
2.9 Analysis: Asymptotic Case . . . . . . . . . . . . . . . . . . . . . 76
2.9.1 The Computation Tree Ensemble . . . . . . . . . . . . . 76
2.9.2 The Tree Ensemble . . . . . . . . . . . . . . . . . . . . . 79
2.9.3 Convergence to Tree Ensemble . . . . . . . . . . . . . . . 81
2.9.4 Density Evolution . . . . . . . . . . . . . . . . . . . . . 81
2.9.5 Monotonicity . . . . . . . . . . . . . . . . . . . . . . . . 83
2.9.6 Threshold . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2.9.7 Order of Limits . . . . . . . . . . . . . . . . . . . . . . . 84
2.9.8 Fixed-Point Characterization of Thresholds . . . . . . . . 86
2.9.9 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
2.9.10 Analytic Determination of Thresholds . . . . . . . . . . . 88
2.9.11 Capacity-Achieving Degree Distributions . . . . . . . . . 89
2.9.12 Gallager’s Lower Bound on Density . . . . . . . . . . . . 93
2.9.13 Optimally-Sparse Degree Distribution Pairs . . . . . . . . 95
2.9.14 Degree Distributions with Given Maximum Degree . . . . 97
2.9.15 EXIT Charts . . . . . . . . . . . . . . . . . . . . . . . . 99
2.10 Analysis: Finite-Length Case . . . . . . . . . . . . . . . . . . . . 114
2.10.1 Stopping Sets . . . . . . . . . . . . . . . . . . . . . . . . 114
2.10.2 Infinite Number of Iterations . . . . . . . . . . . . . . . . 116
2.10.3 Fixed Number of Iterations . . . . . . . . . . . . . . . . . 118
2.10.4 Finite-Length Scaling . . . . . . . . . . . . . . . . . . . 119
2.10.5 Weight Distribution . . . . . . . . . . . . . . . . . . . . . 125
2.10.6 Approximation and Optimization . . . . . . . . . . . . . 135
Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
3 BINARY MEMORYLESS SYMMETRIC CHANNELS 151
3.1 Basic Definitions and Examples . . . . . . . . . . . . . . . . . . 151
3.1.1 Log-Likelihood Ratios . . . . . . . . . . . . . . . . . . . 151
3.1.2 Channel Symmetry . . . . . . . . . . . . . . . . . . . . . 153
3.1.3 Distributions . . . . . . . . . . . . . . . . . . . . . . . . 153
3.1.4 Symmetry and Channel Equivalence . . . . . . . . . . . . 159
3.1.5 Capacity of BMS Channels . . . . . . . . . . . . . . . . . 161
3.1.6 Functionals of BMS Channels . . . . . . . . . . . . . . . 164
3.1.7 Linear Codes and BMS Channels . . . . . . . . . . . . . 168
3.1.8 Physical Degradation . . . . . . . . . . . . . . . . . . . . 169
3.1.9 Erasure Decomposition Lemma . . . . . . . . . . . . . . 177
3.1.10 Symmetry under MAP Decoding . . . . . . . . . . . . . . 178
3.2 Message-Passing Algorithms . . . . . . . . . . . . . . . . . . . . 179
3.3 Analysis: Basic Simplifications . . . . . . . . . . . . . . . . . . . 184
3.3.1 Restriction to the All-One Codeword . . . . . . . . . . . 184
3.3.2 Concentration . . . . . . . . . . . . . . . . . . . . . . . . 185
3.4 Analysis: Asymptotic Case . . . . . . . . . . . . . . . . . . . . . 185
3.4.1 Tree Channels . . . . . . . . . . . . . . . . . . . . . . . 185
3.4.2 Convergence to Tree Ensemble . . . . . . . . . . . . . . . 186
3.4.3 Density Evolution . . . . . . . . . . . . . . . . . . . . . 186
3.4.4 Monotonicity . . . . . . . . . . . . . . . . . . . . . . . . 189
3.4.5 Threshold . . . . . . . . . . . . . . . . . . . . . . . . . . 191
3.4.6 Fixed-Point Characterization of Thresholds . . . . . . . . 193
3.4.7 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
3.4.8 Gallager’s Lower Bound on the Density . . . . . . . . . . 201
3.4.9 EXIT Charts . . . . . . . . . . . . . . . . . . . . . . . . 203
3.4.10 GEXIT Charts and MAP Thresholds . . . . . . . . . . . . 210
3.5 Analysis: Finite-Length Case . . . . . . . . . . . . . . . . . . . . 211
3.5.1 Finite-Length Scaling . . . . . . . . . . . . . . . . . . . 211
Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
4 FACTOR GRAPHS 223
4.1 The Distributive Law . . . . . . . . . . . . . . . . . . . . . . . . 223
4.2 Graphical Representation of Factorizations . . . . . . . . . . . . . 224
4.3 Recursive Determination of Marginals . . . . . . . . . . . . . . . 225
4.4 Efficient Marginalization Via Message Passing . . . . . . . . . . 227
4.4.1 Generalization to Commutative Semirings . . . . . . . . . 229
4.5 The Decoding Problem . . . . . . . . . . . . . . . . . . . . . . . 231
4.5.1 Bitwise MAP Decoding . . . . . . . . . . . . . . . . . . 231
4.5.2 Equivalence to Belief Propagation . . . . . . . . . . . . . 232
4.5.3 Blockwise MAP Decoding . . . . . . . . . . . . . . . . . 234
4.5.4 Limitations of Cycle-Free Codes . . . . . . . . . . . . . . 235
4.6 Forney Style Factor Graphs . . . . . . . . . . . . . . . . . . . . . 238
4.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
4.7.1 Convolutional Codes . . . . . . . . . . . . . . . . . . . . 240
4.7.2 Fully-Interleaved Fading Channels . . . . . . . . . . . . . 246
4.7.3 The Z Channel . . . . . . . . . . . . . . . . . . . . . . . 252
4.7.4 Channels With Memory . . . . . . . . . . . . . . . . . . 254
4.7.5 Coding for High Spectral Efficiency . . . . . . . . . . . . 258
4.7.6 Multiple-Access Channel . . . . . . . . . . . . . . . . . . 263
4.7.7 Non-Binary Codes . . . . . . . . . . . . . . . . . . . . . 266
Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
5 TURBO CODES 281
5.1 Structure, Encoding and Decoding . . . . . . . . . . . . . . . . . 281
5.1.1 Turbo Codes: Parallel and Serial Concatenation . . . . . . 281
5.1.2 Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . 284
5.2 Asymptotic Analysis . . . . . . . . . . . . . . . . . . . . . . . . 286
5.2.1 Density Evolution . . . . . . . . . . . . . . . . . . . . . 289
5.2.2 Computation of Density Evolution . . . . . . . . . . . . . 289
5.2.3 Stability Condition . . . . . . . . . . . . . . . . . . . . . 292
5.2.4 Weight Distribution . . . . . . . . . . . . . . . . . . . . . 294
5.2.5 Minimum Distance of Turbo Codes . . . . . . . . . . . . 304
5.3 Interleaver Design . . . . . . . . . . . . . . . . . . . . . . . . . . 305
5.4 Variations on the Theme . . . . . . . . . . . . . . . . . . . . . . 305
Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
6 ENSEMBLES, OPTIMIZATION, QUANTIZATION 319
6.1 Multi-edge type LDPC codes . . . . . . . . . . . . . . . . . . . . 319
6.1.1 Parameterization . . . . . . . . . . . . . . . . . . . . . . 321
6.1.2 Cascaded Constructions for Degree-One Variable Nodes . 323
6.2 Graph Ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . 323
6.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
6.3.1 Concentration . . . . . . . . . . . . . . . . . . . . . . . . 324
6.3.2 Density evolution . . . . . . . . . . . . . . . . . . . . . . 324
6.3.3 Fixed Points, Convergence, and Monotonicity . . . . . . . 325
6.3.4 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
6.3.5 Stability of Simple Cascades . . . . . . . . . . . . . . . . 332
6.4 Multi-Edge type Examples . . . . . . . . . . . . . . . . . . . . . 333
6.4.1 Capacity Achieving Codes with Finite AverageWeight . . 334
6.4.2 CT codes . . . . . . . . . . . . . . . . . . . . . . . . . . 335
6.4.3 Standard Irregular LDPC and Irregular Repeat Accumulate
Codes . . . . . . . . . . . . . . . . . . . . . . . . . . 335
6.4.4 MN codes of Kantor and Saad . . . . . . . . . . . . . . . 335
6.4.5 LDPC for Low Error Floors . . . . . . . . . . . . . . . . 336
6.5 Turbo Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
6.6 RA Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
6.7 Low-Density Generator Codes . . . . . . . . . . . . . . . . . . . 338

6.8 Luby Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
7 GRAPH DESIGN 341
7.1 Structured Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 341
7.2 Loops and Girth . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
7.2.1 Liftings of LDPC Codes and Graphs . . . . . . . . . . . . 344
7.2.2 Matched Liftings . . . . . . . . . . . . . . . . . . . . . . 346
7.2.3 Matched Liftings as LDPC codes over Rings . . . . . . . 346
7.2.4 Group Rings . . . . . . . . . . . . . . . . . . . . . . . . 346
7.2.5 Matched Lifted LDPC Codes . . . . . . . . . . . . . . . . 348
7.2.6 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . 348
7.2.7 Invariance . . . . . . . . . . . . . . . . . . . . . . . . . . 350
7.2.8 Decoder Implications . . . . . . . . . . . . . . . . . . . . 351
7.3 Product Liftings . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
7.4 Adjusting the graph for other sizes and rates . . . . . . . . . . . . 351
7.5 Algebraic Constructions . . . . . . . . . . . . . . . . . . . . . . 352
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
8 ENCODING LOW-DENSITY PARITY-CHECK CODES 353
8.1 General Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . 354
8.1.1 A Practical Greedy Algorithm . . . . . . . . . . . . . . . 357
8.1.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 362
8.1.3 Transpose Erasure Decoding . . . . . . . . . . . . . . . . 362
8.1.4 Linear Time Encoding . . . . . . . . . . . . . . . . . . . 362
8.1.5 Asymptotic Algorithm . . . . . . . . . . . . . . . . . . . 363
Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366

9.1 Building Codes from Expanders . . . . . . . . . . . . . . . . . . 367
9.2 The Flipping Algorithm . . . . . . . . . . . . . . . . . . . . . . . 368
9.3 Bounds on the Expansion of a Graph . . . . . . . . . . . . . . . 369
9.4 The Expansion of Random Graphs . . . . . . . . . . . . . . . . . 371
Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
10 STATISTICAL MECHANICS OF LDPC CODES 375
10.1 The Decoding Problem Rewritten . . . . . . . . . . . . . . . . . 375
10.2 Parlez-Vous Statistical Mechanics? . . . . . . . . . . . . . . . . . 376
10.3 The Random-Codeword Model . . . . . . . . . . . . . . . . . . . 380
10.4 Weight Distribution . . . . . . . . . . . . . . . . . . . . . . . . . 383
10.4.1 Mean-Field Approximation . . . . . . . . . . . . . . . . 385
10.4.2 Replica Symmetric Approach . . . . . . . . . . . . . . . 393
10.4.3 Comparison: Statistical Physics and Combinatorics Approach
. . . . . . . . . . . . . . . . . . . . . . . . . . . 400
10.5 MAP Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
10.6 Dictionary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409

zhaichunhua168

ahshima

thanks

ahshima

thanks

ahshima

thanks

liyuanliu

好书，谢谢分享！！！！！！！！！！！！！

kevinwjs

kevinwjs

:victory:

kevinwjs

kevinwjs