Algebraic and Stochastic Coding Theory

Algebraic and Stochastic Coding Theory

Published:
Content:
Author(s):
Free Standard Shipping

Purchasing Options

Hardback
$93.95
ISBN 9781439881811
Cat# K13864
Add to cart
eBook
ISBN 9781466505629
Cat# KE16075
 

Features

  • Explains the underlying principles in coding theory, including recent developments in stochastic processes
  • Describes each code clearly, along with its applications, advantages, and disadvantages
  • Includes more than 200 examples that explain how the codes are encoded and decoded
  • Simplifies the mathematical theory, while still providing sufficient rigor
  • Puts codes in historical context by describing their developments during the past sixty years
  • Includes appendices with background material and more than 110 illustrations
  • Offers some computer programs in C, contained in the book, and a list of useful online software resources

Summary

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

Editorial Reviews

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

Textbooks
Other CRC Press Sites
Featured Authors
STAY CONNECTED
Facebook Page for CRC Press Twitter Page for CRC Press You Tube Channel for CRC Press LinkedIn Page for CRC Press Google Plus Page for CRC Press
Sign Up for Email Alerts
© 2014 Taylor & Francis Group, LLC. All Rights Reserved. Privacy Policy | Cookie Use | Shipping Policy | Contact Us