Error correction coding: mathematical methods and algorithms

Error Correction Coding Mathematical Methods and Algorithms......Page 1
Contents......Page 16
Preface......Page 10
List of Program Files......Page 30
List of Laboratory Exercises......Page 35
List of Algorithms......Page 36
List of Figures......Page 38
List of Tables......Page 44
List of Boxes......Page 46
Part I Introduction and Foundations......Page 48
1.2 Introduction: Where Are Codes?......Page 49
1.3 The Communications System......Page 51
1.4 Basic Digital Communications......Page 56
1.4.1 Binary Phase-Shift Keying......Page 57
1.4.2 More General Digital Modulation......Page 58
1.5.1 The Gaussian Channel......Page 61
1.5.2 MAP and ML Detection......Page 63
1.5.3 Special Case: Binary Detection......Page 65
1.5.4 Probability of Error for Binary Detection......Page 66
1.5.5 Bounds on Performance: The Union Bound......Page 69
1.5.6 The Binary Symmetric Channel......Page 70
1.6 Memoryless Channels......Page 72
1.7 Simulation and Energy Considerations for Coded Signals......Page 73
1.8 Some Important Definitions......Page 74
1.8.1 Detection of Repetition Codes Over a BSC......Page 75
1.8.2 Soft-Decision Decoding of Repetition Codes Over the AWGN......Page 79
1.8.4 Summary......Page 80
1.9 Hamming Codes......Page 81
1.9.1 Hard-Input Decoding Hamming Codes......Page 82
1.9.2 Other Representations of the Hamming Code......Page 83
A Polynomial Representation......Page 84
The Tanner Graph Representation......Page 85
1.10 The Basic Questions......Page 86
Entropy and Conditional Entropy......Page 87
Relative Entropy, Mutual Information, and Channel Capacity......Page 88
1.12.2 Definitions for Continuous Random Variables......Page 90
1.12.4 “Proof” of the Channel Coding Theorem......Page 92
1.12.5 Capacity for the Continuous-Time AWGN Channel......Page 96
1.12.6 Transmission at Capacity with Errors......Page 98
1.12.7 The Implication of the Channel Coding Theorem......Page 99
Use of Coding in Conjunction with the BSC......Page 100
Resources and Implementation Suggestions......Page 101
1.13 Exercises......Page 103
1.14 References......Page 107
Part II Block Codes......Page 108
2.2 Groups......Page 109
2.2.1 Subgroups......Page 112
2.2.2 Cyclic Groups and the Order of an Element......Page 113
2.2.3 Cosets......Page 114
2.2.4 Lagrange’s Theorem......Page 115
2.2.5 Induced Operations; Isomorphism......Page 116
2.2.6 Homomorphism......Page 119
2.3 Fields: A Prelude......Page 120
2.4 Review of Linear Algebra......Page 122
2.5 Exercises......Page 127
2.6 References......Page 129
3.1 Basic Definitions......Page 130
3.2 The Generator Matrix Description of Linear Block Codes......Page 131
3.3 The Parity Check Matrix and Dual Codes......Page 133
3.3.1 Some Simple Bounds on Block Codes......Page 135
3.4.2 Error Correction: The Standard Array......Page 137
3.5 Weight Distributions of Codes and Their Duals......Page 142
3.6 Hamming Codes and Their Duals......Page 144
3.7 Performance of Linear Codes......Page 145
3.7.1 Error detection performance......Page 146
3.7.2 Error Correction Performance......Page 147
3.7.3 Performance for Soft-Decision Decoding......Page 150
3.8 Erasure Decoding......Page 151
3.9 Modifications to Linear Codes......Page 152
3.11 Exercises......Page 154
3.12 References......Page 159
4.2 Basic Definitions......Page 160
4.3 Rings......Page 161
4.3.1 Rings of Polynomials......Page 162
4.4 Quotient Rings......Page 163
4.5 Ideals in Rings......Page 165
4.6 Algebraic Description of Cyclic Codes......Page 167
4.7 Nonsystematic Encoding and Parity Check......Page 169
4.8 Systematic Encoding......Page 171
4.9.1 Computational Building Blocks......Page 173
4.9.2 Sequences and Power series......Page 174
First-Element-First Processing......Page 175
Last-Element-First Processing......Page 176
First-Element-First Processing......Page 179
4.10 Cyclic Encoding......Page 180
4.11 Syndrome Decoding......Page 184
4.12 Shortened Cyclic Codes......Page 190
Method 1: Simulating the Extra Clock Shifts......Page 191
4.13 Binary CRC Codes......Page 194
4.13.1 Byte-Oriented Encoding and Decoding Algorithms......Page 197
4.13.2 CRC Protecting Data Files or Data Packets......Page 200
Appendix 4.A.1 Basic Concepts......Page 201
Appendix 4.A.2 Connection With Polynomial Division......Page 204
Appendix 4.A.3 Some Algebraic Properties of Shift Sequences......Page 207
Resources and Implementation Suggestions......Page 208
Follow-On Ideas and Problems......Page 209
Resources and Implementation Suggestions......Page 210
4.14 Exercises......Page 212
4.15 References......Page 217
5.1 Motivation......Page 218
5.2.1 Divisibility......Page 222
5.2.2 The Euclidean Algorithm and Euclidean Domains......Page 224
5.2.3 The Sugiyama Algorithm......Page 229
5.2.4 Congruence......Page 231
5.2.5 The ø Function......Page 232
Fermat\'s Little Theorem......Page 233
RSA Encryption......Page 234
5.3 The Chinese Remainder Theorem......Page 235
The Evaluation Homomorphism......Page 237
The Interpolation Problem......Page 238
5.4 Fields......Page 240
5.4.1 An Examination of R and C......Page 241
5.4.2 Galois Field Construction: An Example......Page 243
5.4.3 Connection with Linear Feedback Shift Registers......Page 246
5.5 Galois Fields: Mathematical Facts......Page 247
5.6.1 Zech Logarithms......Page 251
5.6.2 Hardware Implementations......Page 252
5.7 Subfields of Galois Fields......Page 253
5.8 Irreducible and Primitive polynomials......Page 254
5.9 Conjugate Elements and Minimal Polynomials......Page 256
5.9.1 Minimal Polynomials......Page 259
5.10 Factoring xn – 1......Page 262
5.11 Cyclotomic Cosets......Page 264
Appendix 5.A How Many Irreducible Polynomials Are There?......Page 265
Appendix 5.A.1 Solving for Im Explicitly: The Moebius Function......Page 269
Programming Part......Page 270
Programming Part......Page 271
5.12 Exercises......Page 272
5.13 References......Page 281
6.1.1 Designing BCH Codes......Page 282
6.1.2 The BCH Bound......Page 284
6.1.3 Weight Distributions for Some Binary BCH Codes......Page 286
6.1.4 Asymptotic Results for BCH Codes......Page 287
6.2.1 Reed-Solomon Construction 1......Page 289
6.2.2 Reed-Solomon Construction 2......Page 290
6.2.3 Encoding Reed-Solomon Codes......Page 291
6.2.4 MDS Codes and Weight Distributions for RS Codes......Page 292
6.3.1 Computation of the Syndrome......Page 294
6.3.3 Chien Search......Page 295
6.4 Finding the Error Locator Polynomial......Page 297
6.4.1 Simplifications for Binary Codes and Peterson’s Algorithm......Page 298
6.4.2 Berlekamp-Massey Algorithm......Page 300
6.4.3 Characterization of LFSR Length in Massey’s Algorithm......Page 302
6.4.4 Simplifications for Binary Codes......Page 306
6.5 Non-Binary BCH and RS Decoding......Page 308
6.5.1 Forney’s Algorithm......Page 309
6.6 Euclidean Algorithm for the Error Locator Polynomial......Page 313
6.7 Erasure Decoding for Nonbinary BCH or RS codes......Page 314
6.8 Galois Field Fourier Transform Methods......Page 316
6.8.1 Equivalence of the Two Reed-Solomon Code Constructions......Page 321
6.8.2 Frequency-Domain Decoding......Page 322
6.9.1 Simple Modifications......Page 323
6.9.2 Generalized Reed-Solomon Codes and Alternant Codes......Page 324
6.9.3 Goppa Codes......Page 325
6.9.5 The McEliece Public Key Cryptosystem......Page 327
Programming Part......Page 328
Resources and Implementation Suggestions......Page 329
Resources and Implementation Suggestions......Page 330
Programming Part......Page 331
Appendix 6.A Proof of Newton’s Identities......Page 332
6.10 Exercises......Page 334
6.11 References......Page 338
7.2 Derivations of Welch-Berlekamp Key Equation......Page 340
7.2.1 The Welch-Berlekamp Derivation of the WB Key Equation......Page 341
7.2.2 Derivation From the Conventional Key Equation......Page 345
7.3 Finding the Error Values......Page 347
7.4.1 Background: Modules......Page 349
7.4.2 The Welch-Berlekamp Algorithm......Page 350
7.4.3 Modular Solution of the WB Key Equation......Page 357
7.5 Erasure Decoding with the Welch-Berlekamp Key Equation......Page 368
7.6.1 Bounded Distance, ML, and List Decoding......Page 369
7.6.2 Error Correction by Interpolation......Page 370
7.6.3 Polynomials in Two Variables......Page 371
Degree and Monomial Order......Page 372
Zeros and Multiple Zeros......Page 375
7.6.4 The GS Decoder: The Main Theorems......Page 377
The Factorization Theorem......Page 378
The Correction Distance......Page 380
The Number of Polynomials in the Decoding List......Page 382
7.6.5 Algorithms for Computing the Interpolation Step......Page 384
Finding Linearly Dependent Columns: The Feng-Tzeng Algorithm......Page 385
Finding the Intersection of Kernels: The Kötter Algorithm......Page 389
7.6.6 A Special Case: m = 1 and L = 1......Page 395
7.6.7 The Roth-Ruckenstein Algorithm......Page 397
What to Do with Lists of Factors?......Page 401
Notation......Page 405
A Factorization Theorem......Page 407
Mapping from Reliability to Multiplicity......Page 408
The Geometry of the Decoding Regions......Page 410
Computing the Reliability Matrix......Page 411
7.7 Exercises......Page 412
7.8 References......Page 415
8.2.1 Introduction to Hadamard Matrices......Page 416
8.2.2 The Paley Construction of Hadamard Matrices......Page 418
8.2.3 Hadamard Codes......Page 421
8.3.1 Boolean Functions......Page 422
8.3.2 Definition of the Reed-Muller Codes......Page 423
Decoding RM (1, m) Codes......Page 426
Expediting Decoding Using the Fast Hadamard Transform......Page 429
Details for an RM (2, 4) Code......Page 431
A Geometric Viewpoint......Page 434
8.3.5 Other Constructions of Reed-Muller Codes......Page 438
8.4 Building Long Codes from Short Codes: The Squaring Construction......Page 439
8.5 Quadratic Residue Codes......Page 443
8.6 Golay Codes......Page 445
Algebraic Decoding of the g23 Golay Code......Page 447
Arithmetic Decoding of the g24 Code......Page 448
8.7 Exercises......Page 450
8.8 References......Page 451
9 Bounds on Codes......Page 453
9.1 The Gilbert-Varshamov Bound......Page 456
9.2 The Plotkin Bound......Page 457
9.3 The Griesmer Bound......Page 458
9.4 The Linear Programming and Related Bounds......Page 460
9.4.2 Character......Page 462
9.4.3 Krawtchouk Polynomials and Characters......Page 463
9.5 The McEliece-Rodemich-Rumsey-Welch Bound......Page 465
9.6 Exercises......Page 467
9.7 References......Page 471
10.2 Interleavers......Page 472
10.3 An Application of Interleaved RS Codes: Compact Discs......Page 474
10.4 Product Codes......Page 477
10.5 Reed-Solomon Codes......Page 478
10.6 Concatenated Codes......Page 479
10.7.1 Fire Code Definition......Page 480
10.7.2 Decoding Fire Codes: Error Trapping Decoding......Page 482
10.8 Exercises......Page 484
10.9 References......Page 485
11.1 Introduction and General Notation......Page 486
11.2 Generalized Minimum Distance Decoding......Page 488
11.2.1 Distance Measures and Properties......Page 489
11.4 Halting the Search: An Optimality Condition......Page 492
11.5 Ordered Statistic Decoding......Page 494
11.6 Exercises......Page 496
11.7 References......Page 497
Part III Codes on Graphs......Page 498
12.1 Introduction and Basic Notation......Page 499
12.1.1 The State......Page 503
12.2 Definition of Codes and Equivalent Codes......Page 505
12.2.1 Catastrophic Encoders......Page 508
12.2.2 Polynomial and Rational Encoders......Page 511
12.2.3 Constraint Length and Minimal Encoders......Page 512
12.2.4 Systematic Encoders......Page 515
12.3.1 Introduction and Notation......Page 516
12.3.2 The Viterbi Algorithm......Page 518
Decoding Streams of Data: Windows on the Trellis......Page 528
Output Decisions......Page 529
Hard and Soft Decoding; Quantization......Page 531
Synchronization Issues......Page 533
12.4 Some Performance Results......Page 534
12.5 Error Analysis for Convolutional Codes......Page 538
12.5.1 Enumerating Paths Through the Trellis......Page 540
Enumerating on More Complicated Graphs: Mason’s Rule......Page 543
12.5.2 Characterizing the Node Error Probability Pe and the Bit Error Rate Pb......Page 545
12.5.3 A Bound on Pd for Discrete Channels......Page 548
12.5.4 A Bound on Pd for BPSK Signaling Over the AWGN Channel......Page 550
12.5.5 Asymptotic Coding Gain......Page 551
12.6 Tables of Good Codes......Page 552
12.7 Puncturing......Page 554
12.7.1 Puncturing to Achieve Variable Rate......Page 556
12.8 Suboptimal Decoding Algorithms for Convolutional Codes......Page 557
12.8.2 The Fano Metric......Page 558
12.8.3 The Stack Algorithm......Page 562
12.8.4 The Fano Algorithm......Page 564
12.8.5 Other Issues for Sequential Decoding......Page 567
12.8.6 A Variation on the Viterbi Algorithm: The M Algorithm......Page 568
12.9 Convolutional Codes as Block Codes......Page 569
12.10.1 Block Codes......Page 570
12.10.2 Cyclic Codes......Page 571
12.10.3 Trellis Decoding of Block Codes......Page 572
Programming Part......Page 573
Programming Part......Page 575
12.11 Exercises......Page 576
12.12 References......Page 580
13.2 Background on Signal Constellations......Page 582
13.3 TCM Example......Page 584
13.3.1 The General Ungerboeck Coding Framework......Page 591
13.3.2 The Set Partitioning Idea......Page 592
13.4.1 General Considerations......Page 593
13.4.2 A Description of the Error Events......Page 595
13.4.3 Known Good TCM Codes......Page 599
13.5 Decoding TCM Codes......Page 601
13.6 Rotational Invariance......Page 603
Differential Encoding......Page 605
Constellation Labels and Partitions......Page 606
13.7 Multidimensional TCM......Page 608
13.7.1 Some Advantages of Multidimensional TCM......Page 609
Basic Definitions......Page 610
Common Lattices......Page 612
Sublattices and Cosets......Page 613
Sources of Coding Gain in Lattice Codes......Page 614
13.8 The V.34 Modem Standard......Page 618
13.9 Exercises......Page 625
13.10 References......Page 627
Part IV Iteratively Decoded Codes......Page 628
14.1 Introduction......Page 629
14.2 Encoding Parallel Concatenated Codes......Page 631
14.3 Turbo Decoding Algorithms......Page 633
14.3.2 Notation......Page 635
14.3.3 Posterior Probability......Page 637
14.3.4 Computing αt and βt......Page 639
14.3.5 Computing γr......Page 640
14.3.6 Normalization......Page 641
14.3.7 Summary of the BCJR Algorithm......Page 643
14.3.8 A Matrix/Vector Formulation......Page 644
14.3.10 The BCJR Algorithm for Systematic Codes......Page 645
14.3.11 Turbo Decoding Using the BCJR Algorithm......Page 647
14.3.12 Likelihood Ratio Decoding......Page 649
Log Prior Ratio λp, t......Page 650
14.3.14 Turbo Decoding Stopping Criteria......Page 652
The Cross Entropy Stopping Criterion......Page 653
The Sign Change Ratio (SCR) Criterion......Page 654
The Max-Log-MAP Algorithm......Page 655
14.3.16 Corrections to the Max-Log-MAP Algorithm......Page 656
14.3.17 The Soft Output Viterbi Algorithm......Page 657
14.4.1 The Error Floor......Page 659
14.4.2 Spectral Thinning and Random Interleavers......Page 661
14.4.3 On Interleavers......Page 665
14.5 EXIT Chart Analysis......Page 666
14.5.1 The EXIT Chart......Page 669
14.6 Block Turbo Coding......Page 670
14.7.1 Introduction to Turbo Equalization......Page 673
14.7.2 The Framework for Turbo Equalization......Page 674
14.8 Exercises......Page 676
14.9 References......Page 679
15.1 Introduction......Page 681
15.2 LDPC Codes: Construction and Notation......Page 682
15.4 Transmission Through a Gaussian Channel......Page 685
15.5 Decoding LDPC Codes......Page 687
15.5.1 The Vertical Step: Updating qmn (x)......Page 688
15.5.2 Horizontal Step: Updating rmn (x)......Page 691
15.5.3 Terminating and Initializing the Decoding Algorithm......Page 694
15.5.4 Summary of the Algorithm......Page 695
15.5.6 Likelihood Ratio Decoder Formulation......Page 696
15.6 Why Low-Density Parity-Check Codes?......Page 700
15.7 The Iterative Decoder on General Block Codes......Page 701
15.8 Density Evolution......Page 702
15.9 EXIT Charts for LDPC Codes......Page 706
15.10 Irregular LDPC Codes......Page 707
15.10.1 Degree Distribution Pairs......Page 709
15.10.3 Density Evolution for Irregular Codes......Page 711
15.10.4 Computation and Optimization of Density Evolution......Page 714
15.11.1 A Construction Based on Finite Geometries......Page 715
15.12 Encoding LDPC Codes......Page 716
15.14 Serial Concatenated Codes; Repeat-Accumulate Codes......Page 718
15.14.1 Irregular RA Codes......Page 720
Background......Page 721
Numerical Considerations......Page 722
15.15 Exercises......Page 723
15.16 References......Page 726
16.1 Introduction......Page 727
16.3 Functions on Local Domains......Page 728
16.4 Factor Graphs and Marginalization......Page 733
16.4.1 Marginalizing on a Single Variable......Page 734
16.4.2 Marginalizing on All Individual Variables......Page 738
16.5.1 Block Codes......Page 741
16.5.2 Modifications to Message Passing for Binary Variables......Page 742
16.5.3 Trellis Processing and the Forward/Backward Algorithm......Page 743
16.6 Summary of Decoding Algorithms on Graphs......Page 746
16.7.1 Clustering......Page 747
16.7.2 Stretching Variable Nodes......Page 748
16.7.3 Exact Computation of Graphs with Cycles......Page 749
16.8 Exercises......Page 753
16.9 References......Page 755
Part V Space-Time Coding......Page 756
17.2 Fading Channels......Page 757
17.2.1 Rayleigh Fading......Page 759
17.3 Diversity Transmission and Reception: The MIMO Channel......Page 761
17.3.1 The Narrowband MIMO Channel......Page 763
17.3.2 Diversity Performance with Maximal-Ratio Combining......Page 764
17.4.1 The Alamouti Code......Page 766
17.4.3 Performance Calculation......Page 768
Real Orthogonal Designs......Page 770
Encoding and Decoding Based on Orthogonal Designs......Page 771
Generalized Real Orthogonal Designs......Page 773
17.4.4 Complex Orthogonal Designs......Page 774
17.5 Space-Time Trellis Codes......Page 775
17.5.1 Concatenation......Page 776
17.6 How Many Antennas?......Page 779
17.8 Exercises......Page 780
17.9 References......Page 781
A Log Likelihood Algebra......Page 782
A.l Exercises......Page 784
References......Page 786
Index......Page 797