Algebraic and Stochastic Coding Theory

Algebraic and Stochastic Coding Theory

by Dave K. Kythe, Prem K. Kythe
Released July 2017
Publisher(s): CRC Press
ISBN: 9781466505629

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Using a simple yet rigorous approach, Algebraic and Stochastic Coding Theory makes the subject of coding theory easy to understand for readers with a thorough knowledge of digital arithmetic, Boolean and modern algebra, and probability theory. It explains the underlying principles of coding theory and offers a clear, detailed description of each code. More advanced readers will appreciate its coverage of recent developments in coding theory and stochastic processes.

After a brief review of coding history and Boolean algebra, the book introduces linear codes, including Hamming and Golay codes. It then examines codes based on the Galois field theory as well as their application in BCH and especially the Reed–Solomon codes that have been used for error correction of data transmissions in space missions.

The major outlook in coding theory seems to be geared toward stochastic processes, and this book takes a bold step in this direction. As research focuses on error correction and recovery of erasures, the book discusses belief propagation and distributions. It examines the low-density parity-check and erasure codes that have opened up new approaches to improve wide-area network data transmission. It also describes modern codes, such as the Luby transform and Raptor codes, that are enabling new directions in high-speed transmission of very large data to multiple users.

This robust, self-contained text fully explains coding problems, illustrating them with more than 200 examples. Combining theory and computational techniques, it will appeal not only to students but also to industry professionals, researchers, and academics in areas such as coding theory and signal and image processing.

Table of contents

  1. Cover
  2. Title Page
  3. Copyright Page
  4. Dedication
  5. Table of Contents
  6. Preface
  7. Notations and Abbreviations
  8. 1 Historical Background
    1. 1.1 Codes Predating Hamming
    2. 1.2 Codes Leading to ASCII
      1. 1.2.1 Original Morse Code
      2. 1.2.2 Baudot’s Code
      3. 1.2.3 Murray’s Code
      4. 1.2.4 Bacon’s Telegraph Code
      5. 1.2.5 Gauss and Weber’s Telegraph Code
      6. 1.2.6 ITA2
      7. 1.2.7 US TTY
      8. 1.2.8 ASCII-1967 Code
    3. 1.3 BCD Codes
      1. 1.3.1 Four-Bit BCD Codes
      2. 1.3.2 Addition with 8421 and Excess-3 Codes
      3. 1.3.3 Codes Larger than Four Bits
      4. 1.3.4 Biquinary Code
  9. 2 Digital Arithmetic
    1. 2.1 Number Systems
      1. 2.1.1 Decimal Numbers
      2. 2.1.2 Division Algorithm
      3. 2.1.3 Base Conversion
      4. 2.1.4 Conversion of Integers
      5. 2.1.5 LCM and GCD
      6. 2.1.6 Modulo
    2. 2.2 Boolean and Bitwise Operations
      1. 2.2.1 Boolean Logical Operations
      2. 2.2.2 Bitwise Operations
      3. 2.2.3 Applications
      4. 2.2.4 XOR Swap Algorithm
      5. 2.2.5 XOR Linked Lists
      6. 2.2.6 Bit Shifts
      7. 2.2.7 Arithmetic Shifts
      8. 2.2.8 Logical Shifts
      9. 2.2.9 Circular Shifts
      10. 2.2.10 Shift Registers
      11. 2.2.11 Rotate through Carry
      12. 2.2.12 One’s and Two’s Complement Arithmetic
    3. 2.3 Checksum
      1. 2.3.1 Fletcher’s Checksum
      2. 2.3.2 Cyclic Redundancy Check (CRC)
    4. 2.4 Ring Counters
    5. 2.5 Residues, Residue Classes, and Congruences
    6. 2.6 Integral Approximations
    7. 2.7 Lexicographic Order
  10. 3 Linear Codes
    1. 3.1 Linear Vector Spaces over Finite Fields
    2. 3.2 Communication Channels
      1. 3.2.1 Shannon’s Theorems
      2. 3.3 Some Useful Definitions
      3. 3.3.1 Hamming Distance
      4. 3.3.2 Lee Distance
      5. 3.3.3 Hamming Cubes
      6. 3.3.4 Hamming Weight
      7. 3.3.5 Residual Code
      8. 3.2.6 Tree Algorithm
    3. 3.4 Linear Codes
      1. 3.4.1 Linear Code
      2. 3.4.2 Dual Codes
      3. 3.4.3 Dimension of a Code
      4. 3.4.4 Self-Dual Codes and Types
      5. 3.4.5 Advantages of Linear Codes
      6. 3.4.6 Popcount
      7. 3.4.7 Parity Bits
      8. 3.4.8 Uses of Parity Bits
      9. 3.4.9 Stop Bit
      10. 3.4.10 Parity-Check Matrix
      11. 3.4.11 Decoding
      12. 3.4.12 Decoding Methods
        1. 3.4.12.1 Ideal Observer Decoding
        2. 3.4.12.2 Maximum Likelihood Decoding
        3. 3.4.12.3 Minimum Distance Decoding
        4. 3.4.12.4 Nearest Neighbor Decoding
        5. 3.4.12.5 Standard Array Decoding
        6. 3.4.12.6 Syndrome Decoding
      13. 3.4.13 Syndrome Lookup Table
    4. 3.5 Vector Operations
      1. 3.5.1 Wedge Product
      2. 3.5.2 Bar Product
    5. 3.6 Sphere Packing
  11. 4 Hamming Codes
    1. 4.1 Error Correcting Codes
      1. 4.1.1 Binary Linear Hamming Codes
    2. 4.2 Hamming (7,4) Code
      1. 4.2.1 Encoding and Decoding
      2. 4.2.2 Computation of Parity Bits
      3. 4.2.3 Syndrome Method
      4. 4.2.4 Parity Check Method
      5. 4.2.5 Mapping Method
      6. 4.2.6 Systematic Hamming codes
      7. 4.2.7 Codeword Sequences
      8. 4.2.8 Multiple-Bit Errors
    3. 4.3 Hamming (11,7) Code
    4. 4.4 General Algorithm
      1. 4.4.1 All Sixteen Possible Hamming (7,4) Codes
      2. 4.4.2 Hamming Code for Longer Data
    5. 4.5 Hamming’s Original Algorithm
    6. 4.6 Equivalent Codes
    7. 4.7 q-ary Hamming Codes
  12. 5 Extended Hamming Codes
    1. 5.1 SEC-DED Codes
      1. 5.1.1 Extension of Hamming Codes
    2. 5.2 Hamming (8,4) Code
    3. 5.3 Hamming (13,8) Code
    4. 5.4 Hamming (32,26) Code
    5. 5.5 Hamming (72,64) Code
      1. 5.5.1 Modified Hamming (72,64) Code
      2. 5.5.2 Encoding of Hamming (72,64) Code
    6. 5.6 Hsiao Code
      1. 5.6.1 Parity Encoder and Decoder
    7. 5.7 Product Notes
    8. 5.8 Uses of Hamming Codes
  13. 6 Bounds in Coding Theory
    1. 6.1 Definitions
    2. 6.2 Sphere-Packing Bound
    3. 6.3 Johnson Bound
    4. 6.4 Gilbert-Varshamov Bound
    5. 6.5 Hamming Bound
    6. 6.6 Singleton Bound
    7. 6.7 Plotkin Bound
    8. 6.8 Griesmer Bound
    9. 6.9 Zyablov Bound
    10. 6.10 Bounds in Fn2
    11. 6.11 Reiger Bound
    12. 6.12 Krawtchouk Polynomials
    13. 6.13 Linear Programming Bound
    14. 6.14 Stochastic Bounds for SEC-DED Codes
  14. 7 Golay Codes
    1. 7.1 Perfect Codes
      1. 7.1.1 Repetition Code
      2. 7.1.2 Hamming (7,4,3) Code
      3. 7.1.3 Binary Golay Codes
      4. 7.1.4 Extended Binary Golay Codes
      5. 7.1.5 Ternary Golay Codes
    2. 7.2 Geometrical Representation
      1. 7.2.1 Construction of Golay Codes
    3. 7.3 Other Construction Methods
    4. 7.4 Finite-State Codes
    5. 7.5 MacWilliams’ Identity
    6. 7.6 Golay’s Original Algorithm
    7. 7.7 Structure of Linear Codes
      1. 7.7.1 Decoding of Linear Codes
  15. 8 Galois Fields
    1. 8.1 Finite Fields
      1. 8.1.1 Extension Fields
    2. 8.2 Construction of Galois Fields
    3. 8.3 Galois Fields of Order p
    4. 8.4 Prime Fields
    5. 8.5 Binary Fields
      1. 8.5.1 Polynomial Basis Representation
    6. 8.6 Arithmetic in Galois Fields
      1. 8.6.1 Addition in Extension Field GF(2m)
      2. 8.6.2 Primitive Polynomials
      3. 8.6.3 Simple Test for Primitiveness
      4. 8.6.4 Gauss Elimination Method
    7. 8.7 Polynomials
      1. 8.7.1 Division Algorithm
      2. 8.7.2 Euclidean Algorithm
      3. 8.7.3 Subfields
    8. 8.8 Polynomial Codes
  16. 9 Matrix Codes
    1. 9.1 Matrix Group Codes
    2. 9.2 Encoding and Decoding Matrices
    3. 9.3 Decoding Procedure
    4. 9.4 Hadamard Code
      1. 9.4.1 Hadamard Matrices
      2. 9.4.2 Nonlinear Codes
      3. 9.4.3 Hadamard Graph
      4. 9.4.4 Decoding
    5. 9.5 Hadamard Transform
    6. 9.6 Hexacode
    7. 9.7 Lexicodes
    8. 9.8 Octacode
    9. 9.9 Simplex Codes
      1. 9.9.1 n-Simplex
      2. 9.9.2 M-Sequences
    10. 9.10 Block Codes
  17. 10 Cyclic Codes
    1. 10.1 Definition
    2. 10.2 Construction of Cyclic Codes
    3. 10.3 Methods for Describing Cyclic Codes
    4. 10.4 Quadratic-Residue Codes
      1. 10.4.1 Generator Polynomials
      2. 10.4.2 Quadratic-Residue Codes
  18. 11 BCH Codes
    1. 11.1 Binary BCH Codes
    2. 11.2 Extended Finite Fields
    3. 11.3 Construction of BCH Codes
    4. 11.4 General Definition
    5. 11.5 General Algorithm
      1. 11.5.1 BCH (31,16) Code
  19. 12 Reed-Muller Codes
    1. 12.1 Boolean Polynomials
    2. 12.2 RM Encoding
      1. 12.2.1 Encoding Matrices
    3. 12.3 Generating Matrices for RM Codes
    4. 12.4 Properties of RM Codes
    5. 12.5 Classification of RM Codes
    6. 12.6 Decoding of RM Codes
      1. 12.6.1 Another Version
      2. 12.6.2 Decoding First-Order RM Codes
      3. 12.6.3 One More Algorithm
    7. 12.7 Recursive Definition
    8. 12.8 Probability Analysis
    9. 12.9 Burst Errors
      1. 12.9.1 Interleaving
      2. 12.9.2 Interleaving Method
      3. 12.9.3 Types of Interleavers
  20. 13 Reed–Solomon Codes
    1. 13.1 Definition
    2. 13.2 Reed-Solomon’s Original Approach
    3. 13.3 Parity Check Matrix
      1. 13.3.1 Properties of RS Codes
      2. 13.3.2 Extended RS Codes
      3. 13.3.3 Structure of RS Codes
      4. 13.3.4 Symbol Errors
      5. 13.3.5 Solution for Large Alphabet Size
    4. 13.4 RS Encoding and Decoding
      1. 13.4.1 Modified Peterson Algorithm
      2. 13.4.2 LSFR Encoder
      3. 13.4.3 Encoding and Decoding Architecture
      4. 13.4.4 Hardware Implementation
      5. 13.4.5 Software Implementation
    5. 13.5 Burst Errors
    6. 13.6 Erasures
      1. 13.6.1 Reconstruction Algorithm
    7. 13.7 Concatenated Systems
      1. 13.7.1 Types of Concatenated Codes
    8. 13.8 Applications
  21. 14 Belief Propagation
    1. 14.1 Rational Belief
    2. 14.2 Belief Propagation
      1. 14.2.1 Pairwise MRF
      2. 14.2.2 Messages
      3. 14.2.3 Belief Read-Out Equation
      4. 14.2.4 Sum-Product versus Max-Product
      5. 14.2.5 Complications and Pitfalls
    3. 14.3 Stopping Time
      1. 14.3.1 Continuous Local Martingales
    4. 14.4 Probability Density Function
    5. 14.5 Log-Likelihood Ratios
      1. 14.5.1 LLR Algebra
      2. 14.5.2 Message Passing Algorithm
      3. 14.5.3 Sum-Product Algorithm
  22. 15 LDPC Codes
    1. 15.1 Tanner Graphs
      1. 15.1.1 Row-Graph of a Tanner Graph
    2. 15.2 Optimal Cycle-Free Codes
      1. 15.2.1 Codes without Cycle-Free Tanner Graphs
    3. 15.3 LDPC Codes
      1. 15.3.1 Channel Capacity
      2. 15.3.2 Types of Communication Channels
        1. 15.3.2.1 BEC
        2. 15.3.2.2 BSC
    4. 15.4 Hard-Decision Decoding
    5. 15.5 Soft-Decision Decoding
    6. 15.6 Irregular LDPC Codes
      1. 15.6.1 Decoding
  23. 16 Special LDPC Codes
    1. 16.1 Classification of LDPC Codes
    2. 16.2 Gallager Codes
      1. 16.2.1 Construction of Gallager Codes
      2. 16.2.2 Gallager Decoding
    3. 16.3 IRA Codes
    4. 16.4 Systematic Codes
      1. 16.4.1 Nonsystematic Codes
      2. 16.4.2 Binary Convolutional Codes
      3. 16.4.3 Trellis Design
      4. 16.4.4 Recursive Systematic Codes
      5. 16.4.5 RSC Decoder
    5. 16.5 Turbo Codes
      1. 16.5.1 Log-Likelihood Ratio Method
    6. 16.6 BP Decoding
      1. 16.6.1 Probabilistic Shuffled Decoding
      2. 16.6.2 Probabilistic Check-Shuffled Decoding
    7. 16.7 Practical Evaluation of LDPC Codes
  24. 17 Discrete Distributions
    1. 17.1 Polynomial Interpolation
    2. 17.2 Chernoff Bound
    3. 17.3 Gaussian Distribution
    4. 17.4 Poisson Distribution
    5. 17.5 Degree Distribution
    6. 17.6 Probability Distributions
      1. 17.6.1 Discrete Probability Distributions
      2. 17.6.2 Continuous Probability Distributions
    7. 17.7 Probability Computation
    8. 17.8 Soliton Distributions
      1. 17.8.1 Solitons
      2. 17.8.2 Ideal Soliton Distribution
      3. 17.8.3 Robust Soliton Distribution
  25. 18 Erasure Codes
    1. 18.1 Erasure Codes
      1. 18.1.1 Forward Error Correcting Codes
      2. 18.1.2 Vandermonde Matrix
    2. 18.2. Tornado Codes
    3. 18.3 Rateless Codes
    4. 18.4 Online Codes
    5. 18.5 Fountain Codes
  26. 19 Luby Transform Codes
    1. 19.1 Transmission Methods
    2. 19.2 Luby Transform (LT) Codes
      1. 19.2.1 LT Encoding
      2. 19.2.2 Decoding of LT Codes
      3. 19.2.3 Decoder Recovery Rule
    3. 19.3 Performance
      1. 19.3.1 Error Floor Problem
    4. 19.4 Comparison of LT Codes with Other Codes
  27. 20 Raptor Codes
    1. 20.1 Evolution of Raptor Codes
      1. 20.1.1 Pre-Code Only Raptor Codes
      2. 20.1.2 Shokrollahi’s Condition
      3. 20.1.3 Asymptotically Good Raptor Codes
      4. 20.1.4 Proof of Asymptotic Performance
      5. 20.1.5 Finite-Length Raptor Codes
      6. 20.1.6 Design and Error Analysis of Pre-Code
      7. 20.1.7 Systematic Raptor Codes
    2. 20.2 Importance Sampling
    3. 20.3 Coupon Collector’s Algorithm
    4. 20.4 Open Problems
  28. A ASCII Table
  29. B Some Useful Groups
  30. C Tables in Finite Fields
  31. D Discrete Fourier Transform
  32. E Software Resources
  33. Bibliography
  34. Index

Product information

  • Title: Algebraic and Stochastic Coding Theory
  • Author(s): Dave K. Kythe, Prem K. Kythe
  • Release date: July 2017
  • Publisher(s): CRC Press
  • ISBN: 9781466505629