0%

Providing in-depth treatment of error correction 

Error Correction Coding: Mathematical Methods and Algorithms, 2nd Edition provides a comprehensive introduction to classical and modern methods of error correction. The presentation provides a clear, practical introduction to using a lab-oriented approach.  Readers are encouraged to implement the encoding and decoding algorithms with explicit algorithm statements and the mathematics used in error correction, balanced with an algorithmic development on how to actually do the encoding and decoding. Both block and stream (convolutional) codes are discussed, and the mathematics required to understand them are introduced on a “just-in-time” basis as the reader progresses through the book. 

The second edition increases the impact and reach of the book, updating it to discuss recent important technological advances. New material includes: 

  • Extensive coverage of LDPC codes, including a variety of decoding algorithms. 
  • A comprehensive introduction to polar codes, including systematic encoding/decoding and list decoding.   
  • An introduction to fountain codes. 
  • Modern applications to systems such as HDTV, DVBT2, and cell phones 

Error Correction Coding includes extensive program files (for example, C++ code for all LDPC decoders and polar code decoders), laboratory materials for students to implement algorithms, and an updated solutions manual, all of which are perfect to help the reader understand and retain the content.  

The book covers classical BCH, Reed Solomon, Golay, Reed Muller, Hamming, and convolutional codes which are still component codes in virtually every modern communication system. There are also fulsome discussions of recently developed polar codes and fountain codes that serve to educate the reader on the newest developments in error correction. 

Table of Contents

  1. Cover
  2. Error Correction Coding
  3. Copyright
  4. Preface
  5. List of Program Files
  6. List of Laboratory Exercises
  7. List of Laboratory Exercises
  8. List of Figures
  9. List of Tables
  10. List of Boxes
  11. About the Companion Website
  12. Part I: Introduction and Foundations
    1. Chapter 1: A Context for Error Correction Coding
    2. 1.1 Purpose of This Book
    3. 1.2 Introduction: Where Are Codes?
    4. 1.3 The Communications System
    5. 1.4 Basic Digital Communications
    6. 1.5 Signal Detection
    7. 1.6 Memoryless Channels
    8. 1.7 Simulation and Energy Considerations for Coded Signals
    9. 1.8 Some Important Definitions and a Trivial Code: Repetition Coding
    10. 1.9 Hamming Codes
    11. 1.10 The Basic Questions
    12. 1.11 Historical Milestones of Coding Theory
    13. 1.12 A Bit of Information Theory
    14. 1.14 References
  13. Part II: Block Codes
    1. Chapter 2: Groups and Vector Spaces
    2. 2.1 Introduction
    3. 2.2 Groups
    4. 2.3 Fields: A Prelude
    5. 2.4 Review of Linear Algebra
    6. 2.25 Exercises
    7. References
    8. Chapter 3: Linear Block Codes
    9. 3.1 Basic Definitions
    10. 3.2 The Generator Matrix Description of Linear Block Codes
    11. 3.3 The Parity Check Matrix and Dual Codes
    12. 3.4 Error Detection and Correction Over Hard‐Output Channels
    13. 3.5 Weight Distributions of Codes and Their Duals
    14. 3.6 Binary Hamming Codes and Their Duals
    15. 3.7 Performance of Linear Codes
    16. 3.8 Erasure Decoding
    17. 3.9 Modifications to Linear Codes
    18. 3.10 Best‐Known Linear Block Codes
    19. Exercises
    20. 3.12 References
    21. Chapter 4: Cyclic Codes, Rings, and Polynomials
    22. 4.1 Introduction
    23. 4.2 Basic Definitions
    24. 4.3 Rings
    25. 4.4 Quotient Rings
    26. 4.5 Ideals in Rings
    27. 4.6 Algebraic Description of Cyclic Codes
    28. 4.7 Nonsystematic Encoding and Parity Check
    29. 4.8 Systematic Encoding
    30. 4.9 Some Hardware Background
    31. 4.10 Cyclic Encoding
    32. 4.11 Syndrome Decoding
    33. 4.12 Shortened Cyclic Codes
    34. 4.13 Binary CRC Codes
    35. Appendix 4.A Linear Feedback Shift Registers
    36. 4.14 Exercise
    37. References
    38. Chapter 5: Rudiments of Number Theory and Algebra
    39. 5.1 Motivation
    40. 5.2 Number Theoretic Preliminaries
    41. 5.3 The Chinese Remainder Theorem
    42. 5.4 Fields
    43. 5.5 Galois Fields: Mathematical Facts
    44. 5.6 Implementing Galois Field Arithmetic
    45. 5.7 Subfields of Galois Fields
    46. 5.8 Irreducible and Primitive Polynomials
    47. 5.9 Conjugate Elements and Minimal Polynomials
    48. 5.10 Factoring
    49. 5.11 Cyclotomic Cosets
    50. Appendix 5.A How Many Irreducible Polynomials Are There?
    51. Exercise
    52. References
    53. Chapter 6: BCH and Reed–Solomon Codes: Designer Cyclic Codes
    54. 6.1 BCH Codes
    55. 6.2 Reed–Solomon Codes
    56. 6.3 Decoding BCH and RS Codes: The General Outline
    57. 6.4 Finding the Error Locator Polynomial
    58. 6.5 Nonbinary BCH and RS Decoding
    59. 6.6 Euclidean Algorithm for the Error Locator Polynomial
    60. 6.7 Erasure Decoding for Nonbinary BCH or RS Codes
    61. 6.8 Galois Field Fourier Transform Methods
    62. 6.9 Variations and Extensions of Reed–Solomon Codes
    63. Appendix 6.A Proof of Newton's Identities
    64. 6.11 Exercise
    65. References
    66. Chapter 7: Alternate Decoding Algorithms for Reed–Solomon Codes
    67. 7.1 Introduction: Workload for Reed–Solomon Decoding
    68. 7.2 Derivations of Welch–Berlekamp Key Equation
    69. 7.3 Finding the Error Values
    70. 7.4 Methods of Solving the WB Key Equation
    71. 7.5 Erasure Decoding with the WB Key Equation
    72. 7.6 The Guruswami–Sudan Decoding Algorithm and Soft RS Decoding
    73. Exercises
    74. 7.8 References
    75. Notes
    76. Chapter 8: Other Important Block Codes
    77. 8.1 Introduction
    78. 8.2 Hadamard Matrices, Codes, and Transforms
    79. 8.3 Reed–Muller Codes
    80. 8.4 Building Long Codes from Short Codes: The Squaring Construction
    81. 8.5 Quadratic Residue Codes
    82. 8.6 Golay Codes
    83. 8.7 Exercises
    84. References
    85. Chapter 9: Bounds on Codes
    86. 9.1 The Gilbert–Varshamov Bound
    87. 9.2 The Plotkin Bound
    88. 9.3 The Griesmer Bound
    89. 9.4 The Linear Programming and Related Bounds
    90. 9.5 The McEliece–Rodemich–Rumsey–Welch Bound
    91. 9.6 Exercises
    92. 9.7 References
    93. Chapter 10: Bursty Channels, Interleavers, and Concatenation
    94. 10.1 Introduction to Bursty Channels
    95. 10.2 Interleavers
    96. 10.3 An Application of Interleaved RS Codes: Compact Discs
    97. 10.4 Product Codes
    98. 10.5 Reed–Solomon Codes
    99. 10.6 Concatenated Codes
    100. 10.7 Fire Codes
    101. 10.9 References
    102. Chapter 11: Soft‐Decision Decoding Algorithms
    103. 11.1 Introduction and General Notation
    104. 11.2 Generalized Minimum Distance Decoding
    105. 11.3 The Chase Decoding Algorithms
    106. 11.4 Halting the Search: An Optimality Condition
    107. 11.5 Ordered Statistic Decoding
    108. 11.6 Soft Decoding Using the Dual Code: The Hartmann Rudolph Algorithm
    109. 11.8 References
  14. Part III: Codes on Graphs
    1. Chapter 12: Convolutional Codes
    2. 12.1 Introduction and Basic Notation
    3. 12.2 Definition of Codes and Equivalent Codes
    4. 12.3 Decoding Convolutional Codes
    5. 12.4 Some Performance Results
    6. 12.5 Error Analysis for Convolutional Codes
    7. 12.6 Tables of Good Codes
    8. 12.7 Puncturing
    9. 12.8 Suboptimal Decoding Algorithms for Convolutional Codes
    10. 12.9 Convolutional Codes as Block Codes and Tailbiting Codes
    11. 12.10 A Modified Expression for the Path Metric
    12. 12.11 Soft Output Viterbi Algorithm (SOVA)
    13. 12.12 Trellis Representations of Block and Cyclic Codes
    14. References
    15. Chapter 13: Trellis‐Coded Modulation
    16. 13.1 Adding Redundancy by Adding Signals
    17. 13.2 Background on Signal Constellations
    18. 13.3 TCM Example
    19. 13.4 Some Error Analysis for TCM Codes
    20. 13.5 Decoding TCM Codes
    21. 13.6 Rotational Invariance
    22. 13.7 Multidimensional TCM
    23. 13.8 Multidimensional TCM Example: The V.34 Modem Standard
    24. 13.9 Exercises
    25. 13.10 References
  15. Part IV: Iteratively Decoded Codes
    1. Chapter 14: Turbo Codes
    2. 14.1 Introduction
    3. 14.2 Encoding Parallel Concatenated Codes
    4. 14.3 Turbo Decoding Algorithms
    5. 14.4 On the Error Floor and Weight Distributions
    6. 14.5 EXIT Chart Analysis
    7. 14.6 Block Turbo Coding
    8. 14.7 Turbo Equalization
    9. Exercise
    10. References
    11. Chapter 15: Low‐Density Parity‐Check Codes: Introduction, Decoding, and Analysis
    12. 15.1 Introduction
    13. 15.2 LDPC Codes: Construction and Notation
    14. 15.3 Tanner Graphs
    15. 15.4 Decoding LDPC Codes
    16. 15.5 Why Low‐Density Parity‐Check Codes?
    17. 15.6 The Iterative Decoder on General Block Codes
    18. 15.7 Density Evolution
    19. 15.8 EXIT Charts for LDPC Codes
    20. 15.9 Irregular LDPC Codes
    21. 15.10 More on LDPC Code Construction
    22. 15.11 Encoding LDPC Codes
    23. 15.12 A Variation: Low‐Density Generator Matrix Codes
    24. Exercise
    25. References
    26. Chapter 16: Low‐Density Parity‐Check Codes: Designs and Variations
    27. 16.1 Introduction
    28. 16.2 Repeat‐Accumulate Codes
    29. 16.3 LDPC Convolutional Codes
    30. 16.4 Quasi‐Cyclic Codes
    31. 16.5 Construction of LDPC Codes Based on Finite Fields
    32. 16.6 Code Design Based on Finite Geometries
    33. 16.7 Ensembles of LDPC Codes
    34. 16.8 Constructing LDPC Codes by Progressive Edge Growth (PEG)
    35. 16.9 Protograph and Multi‐Edge‐Type LDPC Codes
    36. 16.10 Error Floors and Trapping Sets
    37. 16.11 Importance Sampling
    38. 16.12 Fountain Codes
    39. 16.13 References
    40. Notes
  16. Part V: Polar Codes
    1. Chapter 17: Polar Codes
    2. 17.1 Introduction and Preview
    3. 17.2 Notation and Channels
    4. 17.3 Channel Polarization, Channel
    5. 17.4 Channel Polarization, Channels
    6. 17.5 Some Theorems of Polar Coding Theory
    7. 17.6 Designing Polar Codes
    8. 17.7 Perspective: The Channel Coding Theorem
    9. 17.8 Systematic Encoding of Polar Codes
    10. 17.9 List Decoding of Polar Codes
    11. 17.10 LLR‐Based Successive Cancellation List Decoding
    12. 17.11 Simplified Successive Cancellation Decoding
    13. 17.12 Relations with Reed–Muller Codes
    14. 17.13 Hardware and Throughput Performance Results
    15. 17.14 Generalizations, Extensions, and Variations
    16. Appendix 17.A is a Bit‐Reverse Permutation
    17. 17.15 Exercises
    18. References
  17. Part VI: Applications
    1. Chapter 18: Some Applications of Error Correction in Modern Communication Systems
    2. 18.1 Introduction
    3. 18.2 Digital Video Broadcast T2 (DVB‐T2)
    4. 18.3 Digital Cable Television
    5. 18.4 E‐UTRA and Long‐Term Evolution
    6. 18.5 References
  18. Part VII: Space-Time Coding
    1. Chapter 19: Fading Channels and Space‐Time Codes
    2. 19.1 Introduction
    3. 19.2 Fading Channels
    4. 19.3 Diversity Transmission and Reception: The MIMO Channel
    5. 19.4 Space‐Time Block Codes
    6. 19.5 Space‐Time Trellis Codes
    7. 19.6 How Many Antennas?
    8. 19.7 Estimating Channel Information
    9. 19.8 Exercises
    10. 19.9 References
  19. References
  20. Index
  21. End User License Agreement
18.118.254.94