You are previewing Algebraic Codes for Data Transmission.
O'Reilly logo
Algebraic Codes for Data Transmission

Book Description

The need to transmit and store massive amounts of data reliably and without error is a vital part of modern communications systems. Error-correcting codes play a fundamental role in minimising data corruption caused by defects such as noise, interference, crosstalk and packet loss. This book provides an accessible introduction to the basic elements of algebraic codes, and discusses their use in a variety of applications. The author describes a range of important coding techniques, including Reed-Solomon codes, BCH codes, trellis codes, and turbocodes. Throughout the book, mathematical theory is illustrated by reference to many practical examples. The book was first published in 2003 and is aimed at graduate students of electrical and computer engineering, and at practising engineers whose work involves communications or signal processing.

Table of Contents

  1. Cover
  2. Title Page
  3. Copyright Page
  4. Contents
  5. Preface
  6. 1 Introduction
    1. 1.1 The discrete communication channel
    2. 1.2 The history of data-transmission codes
    3. 1.3 Applications
    4. 1.4 Elementary concepts
    5. 1.5 Elementary codes
    6. Problems
  7. 2 Introduction to Algebra
    1. 2.1 Fields of characteristic two
    2. 2.2 Groups
    3. 2.3 Rings
    4. 2.4 Fields
    5. 2.5 Vector spaces
    6. 2.6 Linear algebra
    7. Problems
    8. Notes
  8. 3 Linear Block Codes
    1. 3.1 Structure of linear block codes
    2. 3.2 Matrix description of linear block codes
    3. 3.3 Hamming codes
    4. 3.4 The standard array
    5. 3.5 Hamming spheres and perfect codes
    6. 3.6 Simple modifications to a linear code
    7. Problems
    8. Notes
  9. 4 The Arithmetic of Galois Fields
    1. 4.1 The integer ring
    2. 4.2 Finite fields based on the integer ring
    3. 4.3 Polynomial rings
    4. 4.4 Finite fields based on polynomial rings
    5. 4.5 Primitive elements
    6. 4.6 The structure of finite fields
    7. Problems
    8. Notes
  10. 5 Cyclic Codes
    1. 5.1 Viewing a code from an extension field
    2. 5.2 Polynomial description of cyclic codes
    3. 5.3 Minimal polynomials and conjugates
    4. 5.4 Matrix description of cyclic codes
    5. 5.5 Hamming codes as cyclic codes
    6. 5.6 Cyclic codes for correcting double errors
    7. 5.7 Quasi-cyclic codes and shortened cyclic codes
    8. 5.8 The Golay code as a cyclic code
    9. 5.9 Cyclic codes for correcting burst errors
    10. 5.10 The Fire codes as cyclic codes
    11. 5.11 Cyclic codes for error detection
    12. Problems
    13. Notes
  11. 6 Codes Based on the Fourier Transform
    1. 6.1 The Fourier transform
    2. 6.2 Reed–Solomon codes
    3. 6.3 Conjugacy constraints and idempotents
    4. 6.4 Spectral description of cyclic codes
    5. 6.5 BCH codes
    6. 6.6 The Peterson–Gorenstein–Zierler decoder
    7. 6.7 The Reed–Muller codes as cyclic codes
    8. 6.8 Extended Reed–Solomon codes
    9. 6.9 Extended BCH codes
    10. Problems
    11. Notes
  12. 7 Algorithms Based on the Fourier Transform
    1. 7.1 Spectral estimation in a finite field
    2. 7.2 Synthesis of linear recursions
    3. 7.3 Decoding of binary BCH codes
    4. 7.4 Decoding of nonbinary BCH codes
    5. 7.5 Decoding with erasures and errors
    6. 7.6 Decoding in the time domain
    7. 7.7 Decoding within the BCH bound
    8. 7.8 Decoding beyond the BCH bound
    9. 7.9 Decoding of extended Reed–Solomon codes
    10. 7.10 Decoding with the euclidean algorithm
    11. Problems
    12. Notes
  13. 8 Implementation
    1. 8.1 Logic circuits for finite-field arithmetic
    2. 8.2 Shift-register encoders and decoders
    3. 8.3 The Meggitt decoder
    4. 8.4 Error trapping
    5. 8.5 Modified error trapping
    6. 8.6 Architecture of Reed–Solomon decoders
    7. 8.7 Multipliers and inverters
    8. 8.8 Bit-serial multipliers
    9. Problems
    10. Notes
  14. 9 Convolutional Codes
    1. 9.1 Codes without a block structure
    2. 9.2 Trellis description of convolutional codes
    3. 9.3 Polynomial description of convolutional codes
    4. 9.4 Check matrices and inverse matrices
    5. 9.5 Error correction and distance notions
    6. 9.6 Matrix description of convolutional codes
    7. 9.7 The Wyner–Ash codes as convolutional codes
    8. 9.8 Syndrome decoding algorithms
    9. 9.9 Convolutional codes for correcting error bursts
    10. 9.10 Algebraic structure of convolutional codes
    11. Problems
    12. Notes
  15. 10 Beyond BCH Codes
    1. 10.1 Product codes and interleaved codes
    2. 10.2 Bicyclic codes
    3. 10.3 Concatenated codes
    4. 10.4 Cross-interleaved codes
    5. 10.5 Turbo codes
    6. 10.6 Justesen codes
    7. Problems
    8. Notes
  16. 11 Codes and Algorithms Based on Graphs
    1. 11.1 Distance, probability, and likelihood
    2. 11.2 The Viterbi algorithm
    3. 11.3 Sequential algorithms to search a trellis
    4. 11.4 Trellis description of linear block codes
    5. 11.5 Gallager codes
    6. 11.6 Tanner graphs and factor graphs
    7. 11.7 Posterior probabilities
    8. 11.8 The two-way algorithm
    9. 11.9 Iterative decoding of turbo codes
    10. 11.10 Tail-biting representations of block codes
    11. 11.11 The Golay code as a tail-biting code
    12. Problems
    13. Notes
  17. 12 Performance of Error-Control Codes
    1. 12.1 Weight distributions of block codes
    2. 12.2 Performance of block codes
    3. 12.3 Bounds on minimum distance of block codes
    4. 12.4 Binary expansions of Reed–Solomon codes
    5. 12.5 Symbol error rates on a gaussian-noise channel
    6. 12.6 Sequence error rates on a gaussian-noise channel
    7. 12.7 Coding gain
    8. 12.8 Capacity of a gaussian-noise channel
    9. Problems
    10. Notes
  18. 13 Codes and Algorithms for Majority Decoding
    1. 13.1 Reed–Muller codes
    2. 13.2 Decoding by majority vote
    3. 13.3 Circuits for majority decoding
    4. 13.4 Affine permutations for cyclic codes
    5. 13.5 Cyclic codes based on permutations
    6. 13.6 Convolutional codes for majority decoding
    7. 13.7 Generalized Reed–Muller codes
    8. 13.8 Euclidean-geometry codes
    9. 13.9 Projective-geometry codes
    10. Problems
    11. Notes
  19. Bibliography
  20. Index