Algebraic and Stochastic Coding Theory  book cover
1st Edition

Algebraic and Stochastic Coding Theory

ISBN 9781439881811
Published March 5, 2012 by CRC Press
512 Pages 130 B/W Illustrations

FREE Standard Shipping
USD $180.00

Prices & shipping based on shipping country


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

Historical Background
Codes Predating Hamming
Codes Leading to ASCII
BCD Codes

Digital Arithmetic
Number Systems
Boolean and Bitwise Operations
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
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
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
Polynomial Codes

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

Cyclic Codes
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
Reed–Solomon’s Original Approach
Parity Check Matrix
RS Encoding and Decoding
Burst Errors
Concatenated Systems

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
Comparison of LT Codes with Other Codes

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

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


View More


"... 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