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