Fundamentals of Convolutional Coding

Cover......Page 1
Title Page......Page 3
Copyright Page......Page 4
Dedication......Page 5
Contents......Page 7
Preface......Page 11
Acknowledgments......Page 13
1.1 Why Error Control?......Page 15
1.2 Block Codes-A Primer......Page 20
1.3 A First Encounter with Convolutional Codes......Page 30
1.4 Block Codes versus Convolutional Codes......Page 35
1.5 Capacity Limits and Potential Coding Gain Revisited......Page 37
1.6 Comments......Page 39
Problems......Page 40
2.1 Convolutional Codes and Their Encoders......Page 45
2.2 The Smith Form of Polynomial Convolutional Generator Matrices......Page 52
2.3 Encoder Inverses......Page 59
2.4 Equivalent and Basic Encoding Matrices......Page 66
2.5 Minimal-Basic Encoding Matrices......Page 69
2.6 Minimal Encoding Matrices and Minimal Encoders......Page 75
2.7 Canonical Encoding Matrices*......Page 87
2.8 Minimality via the Invariant-Factor Theorem*......Page 101
2.9 Syndrome Formers and Dual Encoders......Page 105
2.10 Systematic Convolutional Encoders......Page 110
Problems......Page 117
3.1 Distance Measures-A First Encounter......Page 123
3.2 Active Distances......Page 131
3.3 Properties of Convolutional Codes via the Active Distances......Page 137
3.4 Lower Bound on the Distance Profile......Page 142
3.5 Upper Bounds on the Free Distance......Page 146
3.6 Time-Varying Convolutional Codes......Page 150
3.7 Lower Bound on the Free Distance......Page 153
3.8 Lower Bounds on the Active Distances*......Page 157
3.9 Distances of Cascaded Concatenated Codes*......Page 163
3.10 Path Enumerators......Page 167
3.11 Comments......Page 172
Problems......Page 173
4.1 The Viterbi Algorithm Revisited......Page 177
4.2 Error Bounds for Time-Invariant Convolutional Codes......Page 182
4.3 Tighter Error Bounds for Time-Invariant Convolutional Codes......Page 195
4.4 Upper Bounds on the Output Error Burst Lengths......Page 200
4.5 Error Bounds for Periodically Time-Varying Convolutional Codes......Page 209
4.6 Lower Error Bounds for Convolutional Codes......Page 217
4.7 Error Bounds for Time-Varying Convolutional Codes......Page 225
4.8 Error Bounds for Finite Back-Search Limits......Page 234
4.9 Tailbiting Trellises......Page 237
4.10 Quantization of Channel Outputs......Page 244
4.11 Comments......Page 247
Problems......Page 248
5.1 List Decoding Algorithms......Page 253
5.2 List Decoding-Performance......Page 256
5.3 The List Minimum Weight......Page 261
5.4 Upper Bounds on the Probability of Correct Path Loss......Page 269
5.5 Lower Bound on the Probability of Correct Path Loss......Page 275
5.6 Correct Path Loss for Time-Invariant Convolutional Codes......Page 278
5.7 Comments......Page 280
Problems......Page 281
6.1 The Fano Metric......Page 283
6.2 The Stack Algorithm......Page 288
6.3 The Fano Algorithm......Page 290
6.4 The Creeper Algorithm*......Page 292
6.5 Simulations......Page 302
6.6 Computational Analysis of the Stack Algorithm......Page 303
6.7 Error Probability Analysis of the Stack Algorithm......Page 310
6.8 Analysis of the Fano Algorithm......Page 319
6.9 Analysis of Creeper*......Page 324
Problems......Page 327
7.1 Iterative Decoding-A Primer......Page 331
7.2 The Two-Way Algorithm for APP Decoding......Page 335
7.3 The Two-Way Algorithm for Tailbiting Trellises......Page 344
7.4 The One-Way Algorithm for APP Decoding......Page 348
7.5 Low-Density Parity-Check Convolutional Codes......Page 351
Problems......Page 358
8.1 Computing the Distance Spectrum......Page 361
8.2 Some Classes of Rate R = 1/2 Convolutional Codes......Page 365
8.3 Low-Rate Convolutional Codes......Page 371
8.4 High-Rate Convolutional Codes......Page 374
8.5 Tailbiting Trellis Encoders......Page 376
8.6 Comments......Page 384
CHAPTER 9 MODULATION CODES......Page 385
9.1 Bandlimited Channels and QAM......Page 387
9.2 Coding Fundamentals......Page 392
9.4 Geometrically Uniform Trellis Codes......Page 398
9.5 Decoding of Modulation Codes......Page 401
9.6 Comments......Page 402
Problems......Page 403
APPENDIX A MINIMAL ENCODERS......Page 407
APPENDIX B WALD'S IDENTITY......Page 413
BIBLIOGRAPHY......Page 421
INDEX......Page 433
ABOUT THE AUTHORS......Page 441