Essentials of Error-Control Coding

Jorge Castiñera Moreira is Associate Professor (Senior Lecturer) in Communication Systems in the Electronics Department, School of Engineering, Mar del Plata University, Argentina. He is Director of the Communications Laboratory, Director of the research project “Open Source software applications for wireless networks” and co-director of the research project “Information Theory. Data Networks. Chaos and Communications”.  Jorge is also responsible for the teaching area “Communications”. Patrick G. Farrell is Visiting Professor in the Department of Communication Systems at Lancaster University, UK, where he supervises 7 research assistants, 50 PhD and 35 MSc students.  His research interests include error-control coding, coded modulation, digital communications, multi-user communications and information theory and source coding.  Patrick has over 350 publications, reports and presentations, and is Editor of two book series (Academic Press and Research Studies Press).

• Preface xiiiAcknowledgements xvList of Symbols xviiAbbreviations xxv1 Information and Coding Theory 11.1 Information 31.1.1 A Measure of Information 31.2 Entropy and Information Rate 41.3 Extended DMSs 91.4 Channels and Mutual Information 101.4.1 Information Transmission over Discrete Channels 101.4.2 Information Channels 101.5 Channel Probability Relationships 131.6 The A Priori and A Posteriori Entropies 151.7 Mutual Information 161.7.1 Mutual Information: Definition 161.7.2 Mutual Information: Properties 171.8 Capacity of a Discrete Channel 211.9 The Shannon Theorems 221.9.1 Source Coding Theorem 221.9.2 Channel Capacity and Coding 231.9.3 Channel Coding Theorem 251.10 Signal Spaces and the Channel Coding Theorem 271.10.1 Capacity of the Gaussian Channel 281.11 Error-Control Coding 321.12 Limits to Communication and their Consequences 34Bibliography and References 38Problems 382 Block Codes 412.1 Error-Control Coding 412.2 Error Detection and Correction 412.2.1 Simple Codes: The Repetition Code 422.3 Block Codes: Introduction and Parameters 432.4 The Vector Space over the Binary Field 442.4.1 Vector Subspaces 462.4.2 Dual Subspace 482.4.3 Matrix Form 482.4.4 Dual Subspace Matrix 492.5 Linear Block Codes 502.5.1 Generator Matrix G 512.5.2 Block Codes in Systematic Form 522.5.3 Parity Check Matrix H 542.6 Syndrome Error Detection 552.7 Minimum Distance of a Block Code 582.7.1 Minimum Distance and the Structure of the H Matrix 582.8 Error-Correction Capability of a Block Code 592.9 Syndrome Detection and the Standard Array 612.10 Hamming Codes 642.11 Forward Error Correction and Automatic Repeat ReQuest 652.11.1 Forward Error Correction 652.11.2 Automatic Repeat ReQuest 682.11.3 ARQ Schemes 692.11.4 ARQ Scheme Efficiencies 712.11.5 Hybrid-ARQ Schemes 72Bibliography and References 76Problems 773 Cyclic Codes 813.1 Description 813.2 Polynomial Representation of Codewords 813.3 Generator Polynomial of a Cyclic Code 833.4 Cyclic Codes in Systematic Form 853.5 Generator Matrix of a Cyclic Code 873.6 Syndrome Calculation and Error Detection 893.7 Decoding of Cyclic Codes 903.8 An Application Example: Cyclic Redundancy Check Code for the Ethernet Standard 92Bibliography and References 93Problems 944 BCH Codes 974.1 Introduction: The Minimal Polynomial 974.2 Description of BCH Cyclic Codes 994.2.1 Bounds on the Error-Correction Capability of a BCH Code: The Vandermonde Determinant 1024.3 Decoding of BCH Codes 1044.4 Error-Location and Error-Evaluation Polynomials 1054.5 The Key Equation 1074.6 Decoding of Binary BCH Codes Using the Euclidean Algorithm 1084.6.1 The Euclidean Algorithm 108Bibliography and References 112Problems 1125 Reed–Solomon Codes 1155.1 Introduction 1155.2 Error-Correction Capability of RS Codes: The Vandermonde Determinant 1175.3 RS Codes in Systematic Form 1195.4 Syndrome Decoding of RS Codes 1205.5 The Euclidean Algorithm: Error-Location and Error-Evaluation Polynomials 1225.6 Decoding of RS Codes Using the Euclidean Algorithm 1255.6.1 Steps of the Euclidean Algorithm 1275.7 Decoding of RS and BCH Codes Using the Berlekamp–Massey Algorithm 1285.7.1 B–M Iterative Algorithm for Finding the Error-Location Polynomial 1305.7.2 B–M Decoding of RS Codes 1335.7.3 Relationship Between the Error-Location Polynomials of the Euclidean and B–M Algorithms 1365.8 A Practical Application: Error-Control Coding for the Compact Disk 1365.8.1 Compact Disk Characteristics 1365.8.2 Channel Characteristics 1385.8.3 Coding Procedure 1385.9 Encoding for RS codes CRS(28, 24), CRS(32, 28) and CRS(255, 251) 1395.10 Decoding of RS Codes CRS(28, 24) and CRS(32, 28) 1425.10.1 B–M Decoding 1425.10.2 Alternative Decoding Methods 1455.10.3 Direct Solution of Syndrome Equations 1465.11 Importance of Interleaving 148Bibliography and References 152Problems 1536 Convolutional Codes 1576.1 Linear Sequential Circuits 1586.2 Convolutional Codes and Encoders 1586.3 Description in the D-Transform Domain 1616.4 Convolutional Encoder Representations 1666.4.1 Representation of Connections 1666.4.2 State Diagram Representation 1666.4.3 Trellis Representation 1686.5 Convolutional Codes in Systematic Form 1686.6 General Structure of Finite Impulse Response and Infinite Impulse Response FSSMs 1706.6.1 Finite Impulse Response FSSMs 1706.6.2 Infinite Impulse Response FSSMs 1716.7 State Transfer Function Matrix: Calculation of the Transfer Function 1726.7.1 State Transfer Function for FIR FSSMs 1726.7.2 State Transfer Function for IIR FSSMs 1736.8 Relationship Between the Systematic and the Non-Systematic Forms 1756.9 Distance Properties of Convolutional Codes 1776.10 Minimum Free Distance of a Convolutional Code 1806.11 Maximum Likelihood Detection 1816.12 Decoding of Convolutional Codes: The Viterbi Algorithm 1826.13 Extended and Modified State Diagram 1856.14 Error Probability Analysis for Convolutional Codes 1866.15 Hard and Soft Decisions 1896.15.1 Maximum Likelihood Criterion for the Gaussian Channel 1926.15.2 Bounds for Soft-Decision Detection 1946.15.3 An Example of Soft-Decision Decoding of Convolutional Codes 1966.16 Punctured Convolutional Codes and Rate-Compatible Schemes 200Bibliography and References 203Problems 2057 Turbo Codes 2097.1 A Turbo Encoder 2107.2 Decoding of Turbo Codes 2117.2.1 The Turbo Decoder 2117.2.2 Probabilities and Estimates 2127.2.3 Symbol Detection 2137.2.4 The Log Likelihood Ratio 2147.3 Markov Sources and Discrete Channels 2157.4 The BCJR Algorithm: Trellis Coding and Discrete Memoryless Channels 2187.5 Iterative Coefficient Calculation 2217.6 The BCJR MAP Algorithm and the LLR 2347.6.1 The BCJR MAP Algorithm: LLR Calculation 2357.6.2 Calculation of Coefficients γi (u_, u) 2367.7 Turbo Decoding 2397.7.1 Initial Conditions of Coefficients αi−1(u_) and βi (u) 2487.8 Construction Methods for Turbo Codes 2497.8.1 Interleavers 2497.8.2 Block Interleavers 2507.8.3 Convolutional Interleavers 2507.8.4 Random Interleavers 2517.8.5 Linear Interleavers 2537.8.6 Code Concatenation Methods 2537.8.7 Turbo Code Performance as a Function of Size and Type of Interleaver 2577.9 Other Decoding Algorithms for Turbo Codes 2577.10 EXIT Charts for Turbo Codes 2577.10.1 Introduction to EXIT Charts 2587.10.2 Construction of the EXIT Chart 2597.10.3 Extrinsic Transfer Characteristics of the Constituent Decoders 261Bibliography and References 269Problems 2718 Low-Density Parity Check Codes 2778.1 Different Systematic Forms of a Block Code 2788.2 Description of LDPC Codes 2798.3 Construction of LDPC Codes 2808.3.1 Regular LDPC Codes 2808.3.2 Irregular LDPC Codes 2818.3.3 Decoding of LDPC Codes: The Tanner Graph 2818.4 The Sum–Product Algorithm 2828.5 Sum–Product Algorithm for LDPC Codes: An Example 2848.6 Simplifications of the Sum–Product Algorithm 2978.7 A Logarithmic LDPC Decoder 3028.7.1 Initialization 3028.7.2 Horizontal Step 3028.7.3 Vertical Step 3048.7.4 Summary of the Logarithmic Decoding Algorithm 3058.7.5 Construction of the Look-up Tables 3068.8 Extrinsic Information Transfer Charts for LDPC Codes 3068.8.1 Introduction 3068.8.2 Iterative Decoding of Block Codes 3108.8.3 EXIT Chart Construction for LDPC Codes 3128.8.4 Mutual Information Function 3128.8.5 EXIT Chart for the SND 3148.8.6 EXIT Chart for the PCND 3158.9 Fountain and LT Codes 3178.9.1 Introduction 3178.9.2 Fountain Codes 3188.9.3 Linear Random Codes 3188.9.4 Luby Transform Codes 3208.10 LDPC and Turbo Codes 322Bibliography and References 323Problems 324Appendix A: Error Probability in the Transmission of Digital Signals 327Appendix B: Galois Fields GF(q) 339Answers to Problems 351Index 357