## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

1. Cover
2. Title Page
4. Dedication
6. Preface
7. Notations and Abbreviations
8. 1 Historical Background
1. 1.1 Codes Predating Hamming
2. 1.2 Codes Leading to ASCII
3. 1.3 BCD Codes
9. 2 Digital Arithmetic
1. 2.1 Number Systems
2. 2.2 Boolean and Bitwise Operations
3. 2.3 Checksum
4. 2.4 Ring Counters
5. 2.5 Residues, Residue Classes, and Congruences
6. 2.6 Integral Approximations
7. 2.7 Lexicographic Order
10. 3 Linear Codes
1. 3.1 Linear Vector Spaces over Finite Fields
2. 3.2 Communication Channels
3. 3.4 Linear Codes
1. 3.4.1 Linear Code
2. 3.4.2 Dual Codes
3. 3.4.3 Dimension of a Code
4. 3.4.4 Self-Dual Codes and Types
5. 3.4.5 Advantages of Linear Codes
6. 3.4.6 Popcount
7. 3.4.7 Parity Bits
8. 3.4.8 Uses of Parity Bits
9. 3.4.9 Stop Bit
10. 3.4.10 Parity-Check Matrix
11. 3.4.11 Decoding
12. 3.4.12 Decoding Methods
13. 3.4.13 Syndrome Lookup Table
4. 3.5 Vector Operations
5. 3.6 Sphere Packing
11. 4 Hamming Codes
1. 4.1 Error Correcting Codes
2. 4.2 Hamming (7,4) Code
3. 4.3 Hamming (11,7) Code
4. 4.4 General Algorithm
5. 4.5 Hamming’s Original Algorithm
6. 4.6 Equivalent Codes
7. 4.7 q-ary Hamming Codes
12. 5 Extended Hamming Codes
1. 5.1 SEC-DED Codes
2. 5.2 Hamming (8,4) Code
3. 5.3 Hamming (13,8) Code
4. 5.4 Hamming (32,26) Code
5. 5.5 Hamming (72,64) Code
6. 5.6 Hsiao Code
7. 5.7 Product Notes
8. 5.8 Uses of Hamming Codes
13. 6 Bounds in Coding Theory
14. 7 Golay Codes
1. 7.1 Perfect Codes
2. 7.2 Geometrical Representation
3. 7.3 Other Construction Methods
4. 7.4 Finite-State Codes
5. 7.5 MacWilliams’ Identity
6. 7.6 Golay’s Original Algorithm
7. 7.7 Structure of Linear Codes
15. 8 Galois Fields
1. 8.1 Finite Fields
2. 8.2 Construction of Galois Fields
3. 8.3 Galois Fields of Order p
4. 8.4 Prime Fields
5. 8.5 Binary Fields
6. 8.6 Arithmetic in Galois Fields
7. 8.7 Polynomials
8. 8.8 Polynomial Codes
16. 9 Matrix Codes
1. 9.1 Matrix Group Codes
2. 9.2 Encoding and Decoding Matrices
3. 9.3 Decoding Procedure
6. 9.6 Hexacode
7. 9.7 Lexicodes
8. 9.8 Octacode
9. 9.9 Simplex Codes
10. 9.10 Block Codes
17. 10 Cyclic Codes
1. 10.1 Definition
2. 10.2 Construction of Cyclic Codes
3. 10.3 Methods for Describing Cyclic Codes
18. 11 BCH Codes
1. 11.1 Binary BCH Codes
2. 11.2 Extended Finite Fields
3. 11.3 Construction of BCH Codes
4. 11.4 General Definition
5. 11.5 General Algorithm
19. 12 Reed-Muller Codes
1. 12.1 Boolean Polynomials
2. 12.2 RM Encoding
3. 12.3 Generating Matrices for RM Codes
4. 12.4 Properties of RM Codes
5. 12.5 Classification of RM Codes
6. 12.6 Decoding of RM Codes
7. 12.7 Recursive Definition
8. 12.8 Probability Analysis
9. 12.9 Burst Errors
20. 13 Reed–Solomon Codes
1. 13.1 Definition
2. 13.2 Reed-Solomon’s Original Approach
3. 13.3 Parity Check Matrix
4. 13.4 RS Encoding and Decoding
5. 13.5 Burst Errors
6. 13.6 Erasures
7. 13.7 Concatenated Systems
8. 13.8 Applications
21. 14 Belief Propagation
1. 14.1 Rational Belief
2. 14.2 Belief Propagation
3. 14.3 Stopping Time
4. 14.4 Probability Density Function
5. 14.5 Log-Likelihood Ratios
22. 15 LDPC Codes
1. 15.1 Tanner Graphs
2. 15.2 Optimal Cycle-Free Codes
3. 15.3 LDPC Codes
1. 15.3.1 Channel Capacity
2. 15.3.2 Types of Communication Channels
4. 15.4 Hard-Decision Decoding
5. 15.5 Soft-Decision Decoding
6. 15.6 Irregular LDPC Codes
23. 16 Special LDPC Codes
1. 16.1 Classification of LDPC Codes
2. 16.2 Gallager Codes
3. 16.3 IRA Codes
4. 16.4 Systematic Codes
5. 16.5 Turbo Codes
6. 16.6 BP Decoding
7. 16.7 Practical Evaluation of LDPC Codes
24. 17 Discrete Distributions
1. 17.1 Polynomial Interpolation
2. 17.2 Chernoff Bound
3. 17.3 Gaussian Distribution
4. 17.4 Poisson Distribution
5. 17.5 Degree Distribution
6. 17.6 Probability Distributions
7. 17.7 Probability Computation
8. 17.8 Soliton Distributions
25. 18 Erasure Codes
1. 18.1 Erasure Codes
3. 18.3 Rateless Codes
4. 18.4 Online Codes
5. 18.5 Fountain Codes
26. 19 Luby Transform Codes
1. 19.1 Transmission Methods
2. 19.2 Luby Transform (LT) Codes
3. 19.3 Performance
4. 19.4 Comparison of LT Codes with Other Codes
27. 20 Raptor Codes
1. 20.1 Evolution of Raptor Codes
2. 20.2 Importance Sampling
3. 20.3 Coupon Collector’s Algorithm
4. 20.4 Open Problems
28. A ASCII Table
29. B Some Useful Groups
30. C Tables in Finite Fields
31. D Discrete Fourier Transform
32. E Software Resources
33. Bibliography
34. Index