| |
| |
| Preface | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| The discrete communication channel | |
| |
| |
| |
| The history of data-transmission codes | |
| |
| |
| |
| Applications | |
| |
| |
| |
| Elementary concepts | |
| |
| |
| |
| Elementary codes | |
| |
| |
| Problems | |
| |
| |
| |
| Introduction to Algebra | |
| |
| |
| |
| Fields of characteristic two | |
| |
| |
| |
| Groups | |
| |
| |
| |
| Rings | |
| |
| |
| |
| Fields | |
| |
| |
| |
| Vector spaces | |
| |
| |
| |
| Linear algebra | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Linear Block Codes | |
| |
| |
| |
| Structure of linear block codes | |
| |
| |
| |
| Matrix description of linear block codes | |
| |
| |
| |
| Hamming codes | |
| |
| |
| |
| The standard array | |
| |
| |
| |
| Hamming spheres and perfect codes | |
| |
| |
| |
| Simple modifications to a linear code | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| The Arithmetic of Galois Fields | |
| |
| |
| |
| The integer ring | |
| |
| |
| |
| Finite fields based on the integer ring | |
| |
| |
| |
| Polynomial rings | |
| |
| |
| |
| Finite fields based on polynomial rings | |
| |
| |
| |
| Primitive elements | |
| |
| |
| |
| The structure of finite fields | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Cyclic Codes | |
| |
| |
| |
| Viewing a code from an extension field | |
| |
| |
| |
| Polynomial description of cyclic codes | |
| |
| |
| |
| Minimal polynomials and conjugates | |
| |
| |
| |
| Matrix description of cyclic codes | |
| |
| |
| |
| Hamming codes as cyclic codes | |
| |
| |
| |
| Cyclic codes for correcting double errors | |
| |
| |
| |
| Quasi-cyclic codes and shortened cyclic codes | |
| |
| |
| |
| The Golay code as a cyclic code | |
| |
| |
| |
| Cyclic codes for correcting burst errors | |
| |
| |
| |
| The Fire codes as cyclic codes | |
| |
| |
| |
| Cyclic codes for error detection | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Codes Based on the Fourier Transform | |
| |
| |
| |
| The Fourier transform | |
| |
| |
| |
| Reed-Solomon codes | |
| |
| |
| |
| Conjugacy constraints and idempotents | |
| |
| |
| |
| Spectral description of cyclic codes | |
| |
| |
| |
| BCH codes | |
| |
| |
| |
| The Peterson-Gorenstein-Zierler decoder | |
| |
| |
| |
| The Reed-Muller codes as cyclic codes | |
| |
| |
| |
| Extended Reed-Solomon codes | |
| |
| |
| |
| Extended BCH codes | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Algorithms Based on the Fourier Transform | |
| |
| |
| |
| Spectral estimation in a finite field | |
| |
| |
| |
| Synthesis of linear recursions | |
| |
| |
| |
| Decoding of binary BCH codes | |
| |
| |
| |
| Decoding of nonbinary BCH codes | |
| |
| |
| |
| Decoding with erasures and errors | |
| |
| |
| |
| Decoding in the time domain | |
| |
| |
| |
| Decoding within the BCH bound | |
| |
| |
| |
| Decoding beyond the BCH bound | |
| |
| |
| |
| Decoding of extended Reed-Solomon codes | |
| |
| |
| |
| Decoding with the euclidean algorithm | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Implementation | |
| |
| |
| |
| Logic circuits for finite-field arithmetic | |
| |
| |
| |
| Shift-register encoders and decoders | |
| |
| |
| |
| The Meggitt decoder | |
| |
| |
| |
| Error trapping | |
| |
| |
| |
| Modified error trapping | |
| |
| |
| |
| Architecture of Reed-Solomon decoders | |
| |
| |
| |
| Multipliers and inverters | |
| |
| |
| |
| Bit-serial multipliers | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Convolutional Codes | |
| |
| |
| |
| Codes without a block structure | |
| |
| |
| |
| Trellis description of convolutional codes | |
| |
| |
| |
| Polynomial description of convolutional codes | |
| |
| |
| |
| Check matrices and inverse matrices | |
| |
| |
| |
| Error correction and distance notions | |
| |
| |
| |
| Matrix description of convolutional codes | |
| |
| |
| |
| The Wyner-Ash codes as convolutional codes | |
| |
| |
| |
| Syndrome decoding algorithms | |
| |
| |
| |
| Convolutional codes for correcting error bursts | |
| |
| |
| |
| Algebraic structure of convolutional codes | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Beyond BCH Codes | |
| |
| |
| |
| Product codes and interleaved codes | |
| |
| |
| |
| Bicyclic codes | |
| |
| |
| |
| Concatenated codes | |
| |
| |
| |
| Cross-interleaved codes | |
| |
| |
| |
| Turbo codes | |
| |
| |
| |
| Justesen codes | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Codes and Algorithms Based on Graphs | |
| |
| |
| |
| Distance, probability, and likelihood | |
| |
| |
| |
| The Viterbi algorithm | |
| |
| |
| |
| Sequential algorithms to search a trellis | |
| |
| |
| |
| Trellis description of linear block codes | |
| |
| |
| |
| Gallager codes | |
| |
| |
| |
| Tanner graphs and factor graphs | |
| |
| |
| |
| Posterior probabilities | |
| |
| |
| |
| The two-way algorithm | |
| |
| |
| |
| Iterative decoding of turbo codes | |
| |
| |
| |
| Tail-biting representations of block codes | |
| |
| |
| |
| The Golay code as a tail-biting code | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Performance of Error-Control Codes | |
| |
| |
| |
| Weight distributions of block codes | |
| |
| |
| |
| Performance of block codes | |
| |
| |
| |
| Bounds on minimum distance of block codes | |
| |
| |
| |
| Binary expansions of Reed-Solomon codes | |
| |
| |
| |
| Symbol error rates on a gaussian-noise channel | |
| |
| |
| |
| Sequence error rates on a gaussian-noise channel | |
| |
| |
| |
| Coding gain | |
| |
| |
| |
| Capacity of a gaussian-noise channel | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Codes and Algorithms for Majority Decoding | |
| |
| |
| |
| Reed-Muller codes | |
| |
| |
| |
| Decoding by majority vote | |
| |
| |
| |
| Circuits for majority decoding | |
| |
| |
| |
| Affine permutations for cyclic codes | |
| |
| |
| |
| Cyclic codes based on permutations | |
| |
| |
| |
| Convolutional codes for majority decoding | |
| |
| |
| |
| Generalized Reed-Muller codes | |
| |
| |
| |
| Euclidean-geometry codes | |
| |
| |
| |
| Projective-geometry codes | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| Bibliography | |
| |
| |
| Index | |