Algebraic Codes for Data Transmission

by Richard E. Blahut

• ISBN13: 9780521553742
• ISBN10: 0521553741
• Format: Hardcover
• Copyright: 2003-03-10
• Publisher: Cambridge University Press

Summary

The need to transmit and store massive amounts of data reliably and without error is a vital part of modern communications systems. Error-correcting codes play a fundamental role in minimizing data corruption caused by defects such as noise, interference, crosstalk and packet loss. This book provides an accessible introduction to the basic elements of algebraic codes, and discusses their use in a variety of applications. The author describes a range of important coding techniques, including Reed-Solomon codes, BCH codes, trellis codes, and turbocodes. Throughout the book, mathematical theory is illustrated by reference to many practical examples. The book is aimed at graduate students of electrical and computer engineering, and at practising engineers whose work involves communications or signal processing.

Table of Contents

Preface	xi
1 Introduction	1	(19)
1.1 The discrete communication channel	2	(2)
1.2 The history of data-transmission codes	4	(2)
1.3 Applications	6	(1)
1.4 Elementary concepts	7	(7)
1.5 Elementary codes	14	(3)
Problems	17	(3)
2 Introduction to Algebra	20	(29)
2.1 Fields of characteristic two	20	(3)
2.2 Groups	23	(5)
2.3 Rings	28	(2)
2.4 Fields	30	(2)
2.5 Vector spaces	32	(5)
2.6 Linear algebra	37	(8)
Problems	45	(3)
Notes	48	(1)
3 Linear Block Codes	49	(18)
3.1 Structure of linear block codes	49	(1)
3.2 Matrix description of linear block codes	50	(4)
3.3 Hamming codes	54	(2)
3.4 The standard array	56	(3)
3.5 Hamming spheres and perfect codes	59	(3)
3.6 Simple modifications to a linear code	62	(1)
Problems	63	(3)
Notes	66	(1)
4 The Arithmetic of Galois Fields	67	(29)
4.1 The integer ring	67	(3)
4.2 Finite fields based on the integer ring	70	(2)
4.3 Polynomial rings	72	(7)
4.4 Finite fields based on polynomial rings	79	(4)
4.5 Primitive elements	83	(3)
4.6 The structure of finite fields	86	(6)
Problems	92	(3)
Notes	95	(1)
5 Cyclic Codes	96	(35)
5.1 Viewing a code from an extension field	96	(3)
5.2 Polynomial description of cyclic codes	99	(5)
5.3 Minimal polynomials and conjugates	104	(7)
5.4 Matrix description of cyclic codes	111	(2)
5.5 Hamming codes as cyclic codes	113	(3)
5.6 Cyclic codes for correcting double errors	116	(2)
5.7 Quasi-cyclic codes and shortened cyclic codes	118	(1)
5.8 The Golay code as a cyclic code	119	(4)
5.9 Cyclic codes for correcting burst errors	123	(2)
5.10 The Fire codes as cyclic codes	125	(2)
5.11 Cyclic codes for error detection	127	(1)
Problems	128	(2)
Notes	130	(1)
6 Codes Based on the Fourier Transform	131	(48)
6.1 The Fourier transform	131	(7)
6.2 Reed-Solomon codes	138	(5)
6.3 Conjugacy constraints and idempotents	143	(5)
6.4 Spectral description of cyclic codes	148	(4)
6.5 BCH codes	152	(7)
6.6 The Peterson-Gorenstein-Zierler decoder	159	(7)
6.7 The Reed-Muller codes as cyclic codes	166	(3)
6.8 Extended Reed-Solomon codes	169	(3)
6.9 Extended BCH codes	172	(3)
Problems	175	(2)
Notes	177	(2)
7 Algorithms Based on the Fourier Transform	179	(49)
7.1 Spectral estimation in a finite field	179	(4)
7.2 Synthesis of linear recursions	183	(8)
7.3 Decoding of binary BCH codes	191	(2)
7.4 Decoding of nonbinary BCH codes	193	(8)
7.5 Decoding with erasures and errors	201	(5)
7.6 Decoding in the time domain	206	(4)
7.7 Decoding within the BCH bound	210	(3)
7.8 Decoding beyond the BCH bound	213	(3)
7.9 Decoding of extended Reed-Solomon codes	216	(1)
7.10 Decoding with the euclidean algorithm	217	(6)
Problems	223	(3)
Notes	226	(2)
8 Implementation	228	(42)
8.1 Logic circuits for finite-field arithmetic	228	(7)
8.2 Shift-register encoders and decoders	235	(2)
8.3 The Meggitt decoder	237	(7)
8.4 Error trapping	244	(6)
8.5 Modified error trapping	250	(4)
8.6 Architecture of Reed-Solomon decoders	254	(4)
8.7 Multipliers and inverters	258	(4)
8.8 Bit-serial multipliers	262	(5)
Problems	267	(2)
Notes	269	(1)
9 Convolutional Codes	270	(43)
9.1 Codes without a block structure	270	(3)
9.2 Trellis description of convolutional codes	273	(5)
9.3 Polynomial description of convolutional codes	278	(4)
9.4 Check matrices and inverse matrices	282	(5)
9.5 Error correction and distance notions	287	(2)
9.6 Matrix description of convolutional codes	289	(2)
9.7 The Wyner-Ash codes as convolutional codes	291	(3)
9.8 Syndrome decoding algorithms	294	(4)
9.9 Convolutional codes for correcting error bursts	298	(5)
9.10 Algebraic structure of convolutional codes	303	(6)
Problems	309	(2)
Notes	311	(2)
10 Beyond BCH Codes	313	(22)
10.1 Product codes and interleaved codes	314	(4)
10.2 Bicyclic codes	318	(3)
10.3 Concatenated codes	321	(2)
10.4 Cross-interleaved codes	323	(3)
10.5 Turbo codes	326	(3)
10.6 Justesen codes	329	(3)
Problems	332	(2)
Notes	334	(1)
11 Codes and Algorithms Based on Graphs	335	(40)
11.1 Distance, probability, and likelihood	336	(4)
11.2 The Viterbi algorithm	340	(3)
11.3 Sequential algorithms to search a trellis	343	(7)
11.4 Trellis description of linear block codes	350	(4)
11.5 Gallager codes	354	(1)
11.6 Tanner graphs and factor graphs	355	(2)
11.7 Posterior probabilities	357	(2)
11.8 The two-way algorithm	359	(3)
11.9 Iterative decoding of turbo codes	362	(2)
11.10 Tail-biting representations of block codes	364	(4)
11.11 The Golay code as a tail-biting code	368	(4)
Problems	372	(2)
Notes	374	(1)
12 Performance of Error-Control Codes	375	(43)
12.1 Weight distributions of block codes	375	(8)
12.2 Performance of block codes	383	(3)
12.3 Bounds on minimum distance of block codes	386	(8)
12.4 Binary expansions of Reed-Solomon codes	394	(5)
12.5 Symbol error rates on a gaussian-noise channel	399	(4)
12.6 Sequence error rates on a gaussian-noise channel	403	(3)
12.7 Coding gain	406	(5)
12.8 Capacity of a gaussian-noise channel	411	(3)
Problems	414	(2)
Notes	416	(2)
13 Codes and Algorithms for Majority Decoding	418	(45)
13.1 Reed-Muller codes	418	(8)
13.2 Decoding by majority vote	426	(4)
13.3 Circuits for majority decoding	430	(3)
13.4 Affine permutations for cyclic codes	433	(4)
13.5 Cyclic codes based on permutations	437	(4)
13.6 Convolutional codes for majority decoding	441	(1)
13.7 Generalized Reed-Muller codes	442	(5)
13.8 Euclidean-geometry codes	447	(9)
13.9 Projective-geometry codes	456	(4)
Problems	460	(1)
Notes	461	(2)
Bibliography	463	(10)
Index	473