See
discussions, stats, and author profiles for this publication at:
https://www.researchgate.net/publication/236157522
Error Control Coding
Book January 2004
DOI: 10.1007/978-1-4615-3998-8_3
CITATIONS
READS
1,038
4,489
2 authors, including:
Shu Lin
University of California, Davis
364 PUBLICATIONS 13,916
CITATIONS
SEE PROFILE
Available from: Shu Lin
Retrieved on: 19 July 2016
Error Control Coding
Fundamentals and Applications
Second Edition
Shu Lin
University of California, Davis
University of Hawaii, Manoa
Daniel J. Costello
University of Notre Dame
PEARSON
Prentice
Hall
Pearson Education International
Contents
Preface
ix
Coding for Reliable Digital Transmission and Storage
1.1
Introduction
1.2
Types of Codes
1.3
Modulation and Coding
1.4
Maximum Likelihood Decoding
1.5
Types of Errors
1.6
Error Control Strategies
1.7
Performance Measures
1.8
Coded Modulation
Bibliography
1
1
3
5
10
13
14
15
21
23
Introduction to Algebra
2.1
Groups
2.2
Fields
2.3
Binary Field Arithmetic
2.4
Construction of Galois Field GF(2m)
2.5
Basic Properties of a Galois Field GF(2'")
2.6
Computations Using Galois Field GF{2'") Arithmetic
2.7
Vector Spaces
2.8
Matrices
Problems
Bibliography
25
25
31
37
42
47
54
55
61
63
65
Linear Block Codes
3.1
Introduction to Linear Block Codes
3.2
Syndrome and Error Detection
3.3
The Minimum Distance of a Block Code
3.4
Error-Detecting and Error-Correcting Capabilities of a Block
Code
3.5
Standard Array and Syndrome Decoding
3.6
Probability of an Undetected Error for Linear Codes
overaBSC
3.7
Single-Parity-Check Codes, Repetition Codes, and Self-Dual
Codes
Problems
Bibliography
66
66
72
76
Important Linear Block Codes
4.1
Hamming Codes
4.2
A Class of Single-Error-Correcting and Double-Error-Detecting
Codes
4.3
Reed-Muller Codes
4.4
Other Constructions for Reed-Muller Codes
78
82
90
94
95
97
99
100
102
105
114
in
iv
Contents
4.5
4.6
4.7
4.8
The Squaring Construction of Codes
The (24.12) Golay Code
Product Codes
Interleaved Codes
Problems
Bibliography
119
125
128
131
132
134
Cyclic Codes
5.1
Description of Cyclic Codes
5.2
Generator and Parity-Check Matrices of Cyclic Codes
5.3
Encoding of Cyclic Codes
5.4
Syndrome Computation and Error Detection
5.5
Decoding of Cyclic Codes
5.6
Cyclic Hamming Codes
5.7
Error-Trapping Decoding
5.8
Improved Error-Trapping Decoding
5.9
The (23,12) Golay Code
5.10 Shortened Cyclic Codes
5.11 Cyclic Product Codes
5.12 Quasi-Cyclic Codes
Problems
Bibliography
136
136
143
146
150
155
162
166
173
175
179
184
185
188
192
Binary BCH Codes
6.1
Binary Primitive BCH Codes
6.2
Decoding of BCH Codes
6.3
Iterative Algorithm for Finding the Error-Location
Polynomial a{X)
6.4
Simplified Iterative Algorithm for Finding the Error-Location
Polynomial a(X)
6.5
Finding the Error-Location Numbers and Error Correction . . .
6.6
Correction of Errors and Erasures
6.7
Implementation of Galois Field Arithmetic
6.8
Implementation of Error Correction
6.9
Weight Distribution and Error Detection of Binary BCH Codes .
6.10 Remarks
Problems
Bibliography
194
194
205
Nonbinary BCH Codes, Reed-Solomon Codes, and Decoding Algorithms
7.1
q-ary Linear Block Codes
7.2
Primitive BCH Codes over GF(q)
7.3
Reed-Solomon Codes
7.4
Decoding of Nonbinary BCH and RS Codes: The Berlekamp
Algorithm
7.5
Decoding with the Euclidean Algorithm
7.6
Frequency-Domain Decoding
7.7
Correction of Errors and Erasures
209
212
215
217
217
224
227
230
230
231
234
234
236
237
241
248
255
263
Contents
Problems
Bibliography
269
270
8 Majority-Logic Decodable and Finite Geometry Codes
8.1
One-Step Majority-Logic Decoding
8.2
A Class of One-Step Majority-Logic Decodable Codes
8.3
Other One-Step Majority-Logic Decodable Codes
8.4
Multiple-Step Majority-Logic Decoding
8.5
Euclidean Geometry
8.6
Euclidean Geometry Codes
8.7
Twofold EG Codes
8.8
Projective Geometry and Projective Geometry Codes
8.9
Remarks
Problems
Bibliography
273
273
282
290
296
304
309
319
325
331
332
335
9 Trellises for Linear Block Codes
9.1
Finite-State Machine Model and Trellis Representation
of a Code
9.2
Bit-Level Trellises for Binary Linear Block Codes
9.3
State Labeling
9.4
Structural Properties of Bit-Level Trellises
9.5
State Labeling and Trellis Construction Based on the
Parity-Check Matrix
9.6
Trellis Complexity and Symmetry
9.7
Trellis Sectionalization and Parallel Decomposition
9.8
Low-Weight Subtrellises
9.9
Cartesian Product
Problems
Bibliography
338
10 Reliability-Based Soft-Decision Decoding Algorithms for Linear
Block Codes {Contributed by Marc P. C. Fossorier)
10.1 Soft-Decision Decoding
10.2 Reliability Measures and General Reliability-Based Decoding
Schemes
10.3 Sufficient Conditions on the Optimality of a Decoded
Codeword
10.4 Generalized Minimum Distance and Chase Decoding
Algorithms
10.5 Weighted Erasure Decoding
10.6 A Maximum Likelihood Decoding Algorithm Based on Iterative
Processing of the Least Reliable Positions
10.7 Reduced List Syndrome Decoding Algorithm
10.8 Most Reliable Independent Position Reprocessing Decoding
Algorithms
10.9 Weighted Majority-Logic Decoding
10.10 Iterative Reliability-Based Decoding of One-Step Majority-Logic
Decodable Codes
338
342
351
354
360
367
374
380
382
390
391
395
395
400
402
407
413
417
419
422
439
442
vi
Contents
Problems
Bibliography
447
448
11 Convolutional Codes
11.1 Encoding of Convolutional Codes
11.2 Structural Properties of Convolutional Codes
11.3 Distance Properties of Convolutional Codes
Problems
Bibliography
453
454
486
506
510
513
12 Optimum Decoding of Convolutional Codes
12.1 The Viterbi Algorithm
12.2 Performance Bounds for Convolutional Codes
12.3 Construction of Good Convolutional Codes
12.4 Implementation and Performance of the Viterbi Algorithm . . .
12.5 The Soft-Output Viterbi Algorithm (SOVA)
12.6 The BCJR algorithm
12.7 Punctured and Tail-Biting Convolutional Codes
Problems
Bibliography
515
516
525
538
544
558
563
582
598
602
13 Suboptimum Decoding of Convolutional Codes
13.1 The ZJ (Stack) Sequential Decoding Algorithm
13.2 The Fano Sequential Decoding Algorithm
13.3 Performance Characteristics of Sequential Decoding
13.4 Code Construction for Sequential Decoding
13.5 Majority-Logic Decoding
13.6 Performance Characteristics of Majority-Logic Decoding
13.7 Code Construction for Majority-Logic Decoding
Problems
Bibliography
605
606
620
626
640
645
670
677
685
688
14 Trellis-Based Soft-Decision Decoding Algorithms
14.1 The Viterbi Decoding Algorithm
14.2 A Recursive Maximum Likelihood Decoding Algorithm
14.3 A Suboptimum Iterative Decoding Algorithm Based on a
Low-Weight Subtrellis
14.4 The MAP Decoding Algorithm
14.5 MAP Decoding Based on a Sectionalized Trellis
14.6 Max-log-MAP Decoding Algorithm
Problems
Bibliography
691
691
695
704
711
718
726
734
735
15 Concatenated Coding, Code Decomposition, and Multistage Decoding
15.1 Single-Level Concatenated Codes
15.2 Multilevel Concatenated Codes
15.3 A Soft-Decision Multistage Decoding
15.4 Decomposition of Codes
15.5 An Iterative Multistage MLD Algorithm
739
739
743
748
750
754
Contents vii
15.6
15.7
Concatenated Coding Schemes with Convolutional Inner
Codes
Binary Concatenation
Problems
Bibliography
760
761
763
764
16 Turbo Coding
16.1 Introduction to Turbo Coding
16.2 Distance Properties of Turbo Codes
16.3 Performance Analysis of Turbo Codes
16.4 Design of Turbo Codes
16.5 Iterative Decoding of Turbo Codes
Problems
Bibliography
766
767
783
807
814
826
844
847
17 Low-Density Parity-Check Codes
17.1 Introduction to LDPC Codes
17.2 Tanner Graphs for Linear Block Codes
17.3 A Geometric Construction of LDPC Codes
17.4 EG-LDPC Codes
17.5 PG-LDPC Codes
17.6 Decoding of LDPC Codes
17.7 Code Construction by Column and Row Splitting
17.8 Breaking Cycles in Tanner Graphs
17.9 Shortened Finite-Geometry LDPC Codes
17.10 Construction of Gallager LDPC Codes
17.11 Masked EG-Gallager LDPC Codes
17.12 Construction of Quasi-Cyclic Codes by Circulant
Decomposition
17.13 Construction of LDPC Codes Based on Finite Geometries
over GF(ps)
17.14 Random LDPC Codes
17.15 Irregular LDPC Codes
17.16 Graph-Theoretic LDPC Codes
17.17 Construction of LDPC Codes Based on Balanced Incomplete
Block Designs
17.18 Construction of LDPC Codes Based on Shortened RS Codes
with Two Information Symbols
17.19 Concatenations with LDPC and Turbo Codes
Problems
Bibliography
851
852
855
858
860
866
871
885
892
898
902
906
18 Trellis-Coded Modulation
18.1 Introduction to Trellis-Coded Modulation
18.2 TCM Code Construction
18.3 TCM Performance Analysis
18.4 Rotationally Invariant TCM
18.5 Multidimensional TCM
952
953
980
992
998
1015
912
917
920
922
929
935
938
944
945
947
viii
Contents
19 Block
19.1
19.2
19.3
19.4
19.5
19.6
Problems
Bibliography
1056
1059
Coded Modulation
Distance Concepts
Multilevel Block Modulation Codes
Multistage Decoding of Multilevel BCM Codes
Concatenated Coded Modulation
Product Coded Modulation
Multilevel Coded Modulation for Unequal Error Protection . . .
Problems
Bibliography
1063
1063
1064
1075
1081
1088
1090
1100
1101
20 Burst-Error-Correcting Codes
20.1 Introduction
20.2 Decoding of Single-Burst-Error-Correcting Cyclic Codes
20.3 Single-Burst-Error-Correcting Codes
20.4 Phased-Burst-Error-Correcting Codes
20.5 Burst-and-Random-Error-Correcting Codes
Problems
Bibliography
1104
1104
1105
1107
1118
1119
1124
1125
21 Burst-Error-Correcting Convolutional Codes
21.1 Bounds on Burst-Error-Correcting Capability
21.2 Burst-Error-Correcting Convolutional Codes
21.3 Interleaved Convolutional Codes
21.4 Burst-and-Random-Error-Correcting Convolutional Codes . . .
Problems
Bibliography
1127
1127
1128
1139
1142
1153
1154
22 Automatic-Repeat-Request Strategies
22.1 Basic A R Q Schemes
22.2 Selective-Repeat A R Q System with Finite Receiver Buffer . . .
22.3 A R Q Schemes with Mixed Modes of Retransmission
22.4 Hybrid A R Q Schemes
22.5 A Class of Half-Rate Invertible Codes
22.6 Type-II Hybrid Selective-Repeat A R Q with Finite Receiver
Buffer
22.7 Hybrid A R Q Systems Using Convolutional Codes
22.8 A Concatenated Coded Modulation Hybrid A R Q System . . . .
Problems
Bibliography
1156
1156
1163
1171
1174
1178
A Tables of Galois Fields
1204
B Minimal Polynomials of Elements in GF(2m)
1227
C Generator Polynomials of Binary Primitive BCH Codes of Length
up to 2 1 0 - 1
1231
Index
1181
1190
1192
1197
1198
1249
