Essentials of Error–Control Coding

Rapid advances in electronic and optical technology have enabled the implementation of powerful error-control codes, which are now used in almost the entire range of information systems with close to optimal performance. These codes and decoding methods are required for the detection and correction of the errors and erasures which inevitably occur in digital information during transmission, storage and processing because of noise, interference and other imperfections. Error-control coding is a complex, novel and unfamiliar area, not yet widely understood and appreciated. This book sets out to provide a clear description of the essentials of the subject, with comprehensive and up-to-date coverage of the most useful codes and their decoding algorithms. A practical engineering and information technology emphasis, as well as relevant background material and fundamental theoretical aspects, provides an in-depth guide to the essentials of Error-Control Coding.* Provides extensive and detailed coverage of Block, Cyclic, BCH, Reed-Solomon, Convolutional, Turbo, and Low Density Parity Check (LDPC) codes, together with relevant aspects of Information Theory* EXIT chart performance analysis for iteratively decoded error-control techniques* Heavily illustrated with tables, diagrams, graphs, worked examples, and exercises* Invaluable companion website features slides of figures, algorithm software, updates and solutions to problems Offering a complete overview of Error Control Coding, this book is an indispensable resource for students, engineers and researchers in the areas of telecommunications engineering, communication networks, electronic engineering, computer science, information systems and technology, digital signal processing and applied mathematics.

Table of Contents:
Preface & Acknowledgements. Symbols & Abbreviations. 1 INFORMATION AND CODING THEORY. 1.2 Entropy and Information Rate. 1.3 Extended Discrete Memoryless Source. 1.4 Channels and Mutual Information. 1.5 Channel Probability Relationships. 1.6 The a priori and a posteriori Entropies. 1.7 Mutual Information. 1.8 Capacity of a Discrete Channel. 1.9 Shannon's Theorems. 1.10 Signal Spaces and the Channel Coding Theorem. 1.11 Error Control Coding. 1.12 Limits to Communication and their Consequences. Bibliography and References. Problems. 2. BLOCK CODES. 2.1 Error Control Coding. 2.2 Error Detection and Correction. 2.3 Block Codes: Introduction and Parameters. 2.4 The Vector Space over the Binary Field. 2.5 Linear Block Codes. 2.6 Syndrome Error Detection. 2.7 Minimum Distance of a Block Code. 2.8 Error Correction Capability of a Block Code. 2.9 Syndrome Detection and the Standard Array. 2.10 Hamming Codes. 2.11 Forward Error Correction (FEC) and Automatic Repeat ReQuest (ARQ). Bibliography and References. Problems. 3 CYCLIC CODES. 3.1 Description. 3.2 Polynomial Representation of Codewords. 3.3 Generator Polynomial of a Cyclic Code. 3.4 Cyclic Codes in Systematic Form. 3.5 Generator Matrix of a Cyclic Code. 3.6 Syndrome Calculation and Error Detection. 3.7 Decoding of Cyclic Codes. 3.8 An Application Example: CRC Code for the Ethernet Standard. Bibliography and References. Problems. 4 BCH CODES. 4.1 Introduction: The Minimal Polynomial. 4.2 Description of BCH Cyclic Codes. 4.3 Decoding of BCH Codes. 4.4 Error Location and Error Evaluation Polynomials. 4.5 The Key Equation. 4.6 Decoding of BCH Codes using the Euclidean Algorithm. Bibliography and References. Problems. 5 REED-SOLOMON CODES. 5.1 Introduction. 5.2 Error Correction Capability of RS Codes: The Vandermonde Determinant. 5.3 RS Codes in Systematic Form. 5.4 Syndrome Decoding of RS Codes. 5.5 The Euclidean Algorithm. Error Location and Evaluation Polynomials. 5.6 Decoding of RS Codes using the Euclidean Algorithm. 5.7 Decoding of RS and BCH Codes using the Berlekamp- Massey Algorithm. 5.8 A Practical Application: Error-Control Coding for the Compact Disc (CD). 5.9 Encoding for RS codes C(RS)(28,24), C(RS)(32,28) and C(RS)(255,251). 5.10 Decoding of RS Codes C(RS)(28,24) and C(RS)(32,28). . 5.11 Importance of Interleaving Bibliography and References Problems. 6 CONVOLUTIONAL CODES. 6.1 Linear Sequential Circuits. 6.2 Convolutional Codes and Encoders. 6.3 Description in the D-Transform Domain. 6.4 Convolutional Encoder Representations. 6.5 Convolutional Codes in Systematic Form. 6.6 General Structure of FIR and IIR Finite State Sequential Machines. 6.7 State Transfer Function Matrix: Calculation of the Transfer Function. 6.8 Relationship between the Systematic and Non-Systematic Forms. 6.9 Distance Properties of Convolutional Codes. 6.10 Minimum Free Distance of a Convolutional Code. 6.11 Maximum Likelihood Detection (MLD). 6.12 Decoding of Convolutional Codes: The Viterbi Algorithm. 6.13 Extended and Modified State Diagram. 6.14 Error Probability Analysis for Convolutional Codes. 6.15 Hard and soft Decisions. 6.16 Punctured Convolutional Codes and Rate Compatible Schemes. Bibliography and References. Problems. 7 TURBO CODES. 7.1 A Turbo Encoder. 7.2 Decoding of Turbo Codes. 7.3 Markov Sources and Discrete Channels. 7.4 The BCJR Algorithm: Trellis Coding and Discrete Memoryless Channels. 7.5 Iterative Coefficient Calculation. 7.6 MAP BCJR Algorithm and the Log Likelihood Ratio. 7.7 Turbo Decoding. 7.8 Construction Methods for Turbo Codes. 7.9 Other Decoding Algorithms for Turbo Codes. 7.10 EXIT Charts for Turbo Codes. Bibliography and References. Problems. 8 LOW-DENSITY PARITY-CHECK (LDPC) CODES. 8.1 Different Systematic Forms of a Block Code. 8.2 Description of LDPC Codes. 8.3 Construction of LDPC Codes. 8.4 The Sum-Product Algorithm. 8.5 Sum-Product Algorithm for LDPC Codes: An Example. 8.6 Simplifications of the Sum-Product Algorithm. 8.7 A Logarithmic LDPC Decoder. 8.8 EXIT Charts for LDPC Codes. 8.9 Fountain and LT Codes. 8.10 LDPC and Turbo Codes. Bibliography and References. Problems. APPENDIX A: Error Probability in the Transmission of Digital Signals. A.1 Digital Signalling. A.2 Bit Error Rate (BER). Bibliography. APPENDIX B: Galois Fields GF(q). B.1 Groups. B.2 Addition and Multiplication modulo-2. B.3 Fields. B.4 Polynomials over Binary Fields. B.5 Construction of a Galois Field GF(2m). B.6 Properties of Extended Galois Fields GF(2m). B.7 Minimal Polynomials. Bibliography. Answers to Problems. Index.

About the Author :
Jorge Castinera 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).