| Preface |
|
xi | |
| 1 Introduction |
|
1 | (19) |
|
1.1 The discrete communication channel |
|
|
2 | (2) |
|
1.2 The history of data-transmission codes |
|
|
4 | (2) |
|
|
|
6 | (1) |
|
|
|
7 | (7) |
|
|
|
14 | (3) |
|
|
|
17 | (3) |
| 2 Introduction to Algebra |
|
20 | (29) |
|
2.1 Fields of characteristic two |
|
|
20 | (3) |
|
|
|
23 | (5) |
|
|
|
28 | (2) |
|
|
|
30 | (2) |
|
|
|
32 | (5) |
|
|
|
37 | (8) |
|
|
|
45 | (3) |
|
|
|
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) |
|
|
|
54 | (2) |
|
|
|
56 | (3) |
|
3.5 Hamming spheres and perfect codes |
|
|
59 | (3) |
|
3.6 Simple modifications to a linear code |
|
|
62 | (1) |
|
|
|
63 | (3) |
|
|
|
66 | (1) |
| 4 The Arithmetic of Galois Fields |
|
67 | (29) |
|
|
|
67 | (3) |
|
4.2 Finite fields based on the integer ring |
|
|
70 | (2) |
|
|
|
72 | (7) |
|
4.4 Finite fields based on polynomial rings |
|
|
79 | (4) |
|
|
|
83 | (3) |
|
4.6 The structure of finite fields |
|
|
86 | (6) |
|
|
|
92 | (3) |
|
|
|
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) |
|
|
|
128 | (2) |
|
|
|
130 | (1) |
| 6 Codes Based on the Fourier Transform |
|
131 | (48) |
|
6.1 The Fourier transform |
|
|
131 | (7) |
|
|
|
138 | (5) |
|
6.3 Conjugacy constraints and idempotents |
|
|
143 | (5) |
|
6.4 Spectral description of cyclic codes |
|
|
148 | (4) |
|
|
|
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) |
|
|
|
172 | (3) |
|
|
|
175 | (2) |
|
|
|
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) |
|
|
|
223 | (3) |
|
|
|
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) |
|
|
|
237 | (7) |
|
|
|
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) |
|
|
|
267 | (2) |
|
|
|
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) |
|
|
|
309 | (2) |
|
|
|
311 | (2) |
| 10 Beyond BCH Codes |
|
313 | (22) |
|
10.1 Product codes and interleaved codes |
|
|
314 | (4) |
|
|
|
318 | (3) |
|
|
|
321 | (2) |
|
10.4 Cross-interleaved codes |
|
|
323 | (3) |
|
|
|
326 | (3) |
|
|
|
329 | (3) |
|
|
|
332 | (2) |
|
|
|
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) |
|
|
|
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) |
|
|
|
372 | (2) |
|
|
|
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) |
|
|
|
406 | (5) |
|
12.8 Capacity of a gaussian-noise channel |
|
|
411 | (3) |
|
|
|
414 | (2) |
|
|
|
416 | (2) |
| 13 Codes and Algorithms for Majority Decoding |
|
418 | (45) |
|
|
|
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) |
|
|
|
460 | (1) |
|
|
|
461 | (2) |
| Bibliography |
|
463 | (10) |
| Index |
|
473 | |
Lisainfo e-raamatute kohta