Algebraic and Stochastic Coding Theory: 1st Edition (Hardback) book cover

Algebraic and Stochastic Coding Theory

1st Edition

By Dave K. Kythe, Prem K. Kythe

CRC Press

512 pages | 130 B/W Illus.

Purchasing Options:$ = USD
Hardback: 9781439881811
pub: 2012-03-05
SAVE ~$18.00
$120.00
$102.00
x


FREE Standard Shipping!

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.

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

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

Subject Categories

BISAC Subject Codes/Headings:
COM083000
COMPUTERS / Security / Cryptography
MAT003000
MATHEMATICS / Applied