1st Edition

Algebraic and Stochastic Coding Theory

By Dave K. Kythe, Prem K. Kythe Copyright 2012
    512 Pages 130 B/W Illustrations
    by CRC Press

    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.

    Historical Background
    Codes Predating Hamming
    Codes Leading to ASCII
    BCD Codes

    Digital Arithmetic
    Number Systems
    Boolean and Bitwise Operations
    Checksum
    Ring Counters
    Residues, Residue Classes, and Congruences
    Integral Approximations
    Lexicographic Order

    Linear Codes
    Linear Vector Spaces over Finite Fields
    Communication Channels
    Some Useful Definitions
    Linear Codes
    Vector Operations
    Sphere Packing

    Hamming Codes
    Error Correcting Codes
    Hamming (7,4) Code
    Hamming (11,7) Code
    General Algorithm
    Hamming's Original Algorithm
    Equivalent Codes
    q-ary Hamming Codes

    Extended Hamming Codes
    SEC-DED Codes
    Hamming (8,4) Code
    Hamming (13,8) Code
    Hamming (32,26) Code
    Hamming (72,64) Code
    Hsiao Code
    Product Notes
    Uses of Hamming Codes

    Bounds in Coding Theory
    Definitions
    Sphere-Packing Bound
    Johnson Bound
    Gilbert–Varshamov Bound
    Hamming Bound
    Singleton Bound
    Plotkin Bound
    Griesmer Bound
    Zyablov Bound
    Bounds in F2n
    Reiger Bound
    Krawtchouk Polynomials
    Linear Programming Bound
    Stochastic Bounds for SEC-DED Codes

    Golay Codes
    Perfect Codes
    Geometrical Representation
    Other Construction Methods
    Finite-State Codes
    MacWilliams’ Identity
    Golay's Original Algorithm
    Structure of Linear Codes

    Galois Fields
    Finite Fields
    Construction of Galois Fields
    Galois Fields of Order p
    Prime Fields
    Binary Fields
    Arithmetic in Galois Fields
    Polynomials
    Polynomial Codes

    Matrix Codes
    Matrix Group Codes
    Encoding and Decoding Matrices
    Decoding Procedure
    Hadamard Code
    Hadamard Transform
    Hexacode
    Lexicodes
    Octacode
    Simplex Codes
    Block Codes

    Cyclic Codes
    Definition
    Construction of Cyclic Codes
    Methods for Describing Cyclic Codes
    Quadratic-Residue Codes

    BCH Codes
    Binary BCH Codes
    Extended Finite Fields
    Construction of BCH Codes
    General Definition
    General Algorithm

    Reed–Muller Codes
    Boolean Polynomials
    RM Encoding
    Generating Matrices for RM Codes
    Properties of RM Codes
    Classification of RM Codes
    Decoding of RM Codes
    Recursive Definition
    Probability Analysis
    Burst Errors

    Reed–Solomon Codes
    Definition
    Reed–Solomon’s Original Approach
    Parity Check Matrix
    RS Encoding and Decoding
    Burst Errors
    Erasures
    Concatenated Systems
    Applications

    Belief Propagation
    Rational Belief
    Belief Propagation
    Stopping Time
    Probability Density Function
    Log-Likelihood Ratios

    LDPC Codes
    Tanner Graphs
    Optimal Cycle-Free Codes
    LDPC Codes
    Hard-Decision Decoding
    Soft-Decision Decoding
    Irregular LDPC Codes

    Special LDPC Codes
    Classification of LDPC Codes
    Gallager Codes
    IRA Codes
    Systematic Codes
    Turbo Codes
    BP Decoding
    Practical Evaluation of LDPC Codes

    Discrete Distributions
    Polynomial Interpolation
    Chernoff Bound
    Gaussian Distribution
    Poisson Distribution
    Degree Distribution
    Probability Distributions
    Probability Computation
    Soliton Distributions

    Erasure Codes
    Erasure Codes
    Tornado Codes
    Rateless Codes
    Online Codes
    Fountain Codes

    Luby Transform Codes
    Transmission Methods
    Luby Transform (LT) Codes
    Performance
    Comparison of LT Codes with Other Codes

    Raptor Codes
    Evolution of Raptor Codes
    Importance Sampling
    Coupon Collector’s Algorithm
    Open Problems

    Appendices
    A ASCII Table
    B Some Useful Groups
    C Tables in Finite Fields
    D Discrete Fourier Transform
    E Software Resources

    Bibliography
    Index

    Biography

    Dave K. Kythe, Prem K. Kythe

    "... examines both classical error-correcting codes (those developed in the first few decades of the discipline) and newer codes (those developed within a few decades of the book’s publication). ... With each code being studied, the book describes encoding and decoding procedures, sometimes including performance analysis. For certain codes, such as Reed-Solomon codes, hardware and software implementations of encoding and decoding are considered. Discussions of efficiency are also presented in some cases."
    —William Cary Huffman, Mathematical Reviews Clippings, December 2013