Algebraic codes for data transmission / Richard E. Blahut.

Format:

Book

Author/Creator:

Blahut, Richard E.

Contributor:

Class of 1924 Book Fund.

Language:

English

Subjects (All):

Data transmission systems--Mathematical models.

Data transmission systems.

Signal processing--Mathematics.

Signal processing.

Physical Description:

xii, 482 pages : illustrations ; 26 cm

Place of Publication:

Cambridge, UK ; New York : Cambridge University Press, 2003.

Summary:

An accessible introduction to the basic elements of algebraic codes including Reed-Solomon, trellis, turbocodes etc.

Contents:

1.1 The discrete communication channel 2

1.2 The history of data-transmission codes 4

1.3 Applications 6

1.5 Elementary codes 14

2 Introduction to Algebra 20

2.1 Fields of characteristic two 20

2.2 Groups 23

2.3 Rings 28

2.4 Fields 30

2.5 Vector spaces 32

2.6 Linear algebra 37

3 Linear Block Codes 49

3.1 Structure of linear block codes 49

3.2 Matrix description of linear block codes 50

3.3 Hamming codes 54

3.4 The standard array 56

3.5 Hamming spheres and perfect codes 59

3.6 Simple modifications to a linear code 62

4 The Arithmetic of Galois Fields 67

4.1 The integer ring 67

4.2 Finite fields based on the integer ring 70

4.3 Polynomial rings 72

4.4 Finite fields based on polynomial rings 79

4.5 Primitive elements 83

4.6 The structure of finite fields 86

5 Cyclic Codes 96

5.1 Viewing a code from an extension field 96

5.2 Polynomial description of cyclic codes 99

5.3 Minimal polynomials and conjugates 104

5.4 Matrix description of cyclic codes 111

5.5 Hamming codes as cyclic codes 113

5.6 Cyclic codes for correcting double errors 116

5.7 Quasi-cyclic codes and shortened cyclic codes 118

5.8 The Golay code as a cyclic code 119

5.9 Cyclic codes for correcting burst errors 123

5.10 The Fire codes as cyclic codes 125

5.11 Cyclic codes for error detection 127

6 Codes Based on the Fourier Transform 131

6.2 Reed-Solomon codes 138

6.3 Conjugacy constraints and idempotents 143

6.4 Spectral description of cyclic codes 148

6.5 BCH codes 152

6.6 The Peterson-Gorenstein-Zierler decoder 159

6.7 The Reed-Muller codes as cyclic codes 166

6.8 Extended Reed-Solomon codes 169

6.9 Extended BCH codes 172

7 Algorithms Based on the Fourier Transform 179

7.1 Spectral estimation in a finite field 179

7.2 Synthesis of linear recursions 183

7.3 Decoding of binary BCH codes 191

7.4 Decoding of nonbinary BCH codes 193

7.5 Decoding with erasures and errors 201

7.6 Decoding in the time domain 206

7.7 Decoding within the BCH bound 210

7.8 Decoding beyond the BCH bound 213

7.9 Decoding of extended Reed-Solomon codes 216

7.10 Decoding with the euclidean algorithm 217

8 Implementation 228

8.1 Logic circuits for finite-field arithmetic 228

8.2 Shift-register encoders and decoders 235

8.3 The Meggitt decoder 237

8.4 Error trapping 244

8.5 Modified error trapping 250

8.6 Architecture of Reed-Solomon decoders 254

8.7 Multipliers and inverters 258

8.8 Bit-serial multipliers 262

9 Convolutional Codes 270

9.1 Codes without a block structure 270

9.2 Trellis description of convolutional codes 273

9.3 Polynomial description of convolutional codes 278

9.4 Check matrices and inverse matrices 282

9.5 Error correction and distance notions 287

9.6 Matrix description of convolutional codes 289

9.7 The Wyner-Ash codes as convolutional codes 291

9.8 Syndrome decoding algorithms 294

9.9 Convolutional codes for correcting error bursts 298

9.10 Algebraic structure of convolutional codes 303

10 Beyond BCH Codes 313

10.1 Product codes and interleaved codes 314

10.2 Bicyclic codes 318

10.3 Concatenated codes 321

10.4 Cross-interleaved codes 323

10.5 Turbo codes 326

10.6 Justesen codes 329

11 Codes and Algorithms Based on Graphs 335

11.1 Distance, probability, and likelihood 336

11.2 The Viterbi algorithm 340

11.3 Sequential algorithms to search a trellis 343

11.4 Trellis description of linear block codes 350

11.5 Gallager codes 354

11.6 Tanner graphs and factor graphs 355

11.7 Posterior probabilities 357

11.8 The two-way algorithm 359

11.9 Iterative decoding of turbo codes 362

11.10 Tail-biting representations of block codes 364

11.11 The Golay code as a tail-biting code 368

12 Performance of Error-Control Codes 375

12.1 Weight distributions of block codes 375

12.2 Performance of block codes 383

12.3 Bounds on minimum distance of block codes 386

12.4 Binary expansions of Reed-Solomon codes 394

12.5 Symbol error rates on a gaussian-noise channel 399

12.6 Sequence error rates on a gaussian-noise channel 403

12.7 Coding gain 406

12.8 Capacity of a gaussian-noise channel 411

13 Codes and Algorithms for Majority Decoding 418

13.1 Reed-Muller codes 418

13.2 Decoding by majority vote 426

13.3 Circuits for majority decoding 430

13.4 Affine permutations for cyclic codes 433

13.5 Cyclic codes based on permutations 437

13.6 Convolutional codes for majority decoding 441

13.7 Generalized Reed-Muller codes 442

13.8 Euclidean-geometry codes 447

13.9 Projective-geometry codes 456.

Notes:

Includes bibliographical references (pages 463-471) and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Class of 1924 Book Fund.

ISBN:

0521553741

OCLC:

58997336

Online:

Publisher description