# Fundamentals of Convolutional Coding, 2nd Edition

ISBN: 978-1-119-09879-9

Jul 2015, Wiley-IEEE Press

550 pages

Select type: O-Book

## Description

Fundamentals of Convolutional Coding, Second Edition, regarded as a bible of convolutional coding brings you a clear and comprehensive discussion of the basic principles of this field

• Two new chapters on low-density parity-check (LDPC) convolutional codes and iterative coding
• Viterbi, BCJR, BEAST, list, and sequential decoding of convolutional codes
• Distance properties of convolutional codes

Preface xi

Acknowledgement xiv

1 Introduction 1

1.1 Why error control? 1

1.2 Block codes—a primer 8

1.3 Codes on graphs 21

1.4 A first encounter with convolutional codes 28

1.5 Block codes versus convolutional codes 35

1.6 Capacity limits and potential coding gain revisited 36

Problems 41

2 Convolutional encoders—Structural properties 49

2.1 Convolutional codes and their encoders 49

2.2 The Smith form of polynomial convolutional generator matrices 58

2.3 Encoder inverses 67

2.4 Encoder and code equivalences 76

2.5 Basic encoding matrices 79

2.6 Minimalbasic encoding matrices 82

2.7 Minimal encoding matrices and minimal encoders 90

2.8 Canonical encoding matrices* 109

2.9 Minimality via the invariantfactor theorem* 127

2.10 Syndrome formers and dual encoders 131

2.11 Systematic convolutional encoders 139

2.12 Some properties of generator matrices—an overview 150

Problems 152

3 Distance properties of convolutional codes 161

3.1 Distance measures—a first encounter 161

3.2 Active distances 171

3.3 Properties of convolutional codes via the active distances 179

3.4 Lower bound on the distance profile 181

3.5 Upper bounds on the free distance 186

3.6 Timevarying convolutional codes 191

3.7 Lower bound on the free distance 195

3.8 Lower bounds on the active distances* 200

3.9 Distances of cascaded concatenated codes* 207

3.10 Path enumerators 213

Problems 221

4 Decoding of convolutional codes 225

4.1 The Viterbi algorithm revisited 226

4.2 Error bounds for timeinvariant convolutional codes 235

4.3 Tighter error bounds for timeinvariant convolutional codes 250

4.4 Exact bit error probability for Viterbi decoding 255

4.5 The BCJR algorithm for APP decoding 271

4.6 The oneway algorithm for APP decoding 283

4.7 A simple upper bound on the bit error probability for extremely noisy channels 288

4.8 Tailbiting trellises 293

4.9 Decoding of tailbiting codes 302

4.10 BEAST decoding of tailbiting codes 308

Problems 324

5 Random ensemble bounds for decoding error probability 333

5.1 Upper bounds on the output error burst lengths 333

5.2 Bounds for periodically timevarying convolutional codes 345

5.3 Lower error probability bounds for convolutional codes 355

5.4 General bounds for timevarying convolutional codes 363

5.5 Bounds for finite backsearch limits 375

5.6 Quantization of channel outputs 379

Problems 384

6 List decoding 387

6.1 List decoding algorithms 388

6.2 List decoding—performance 391

6.3 The list minimum weight 397

6.4 Upper bounds on the probability of correct path loss 407

6.5 Lower bound on the probability of correct path loss 416

6.6 Correct path loss for timeinvariant convolutional codes 418

Problems 423

7 Sequential decoding 425

7.1 The Fano metric 426

7.2 The stack algorithm 431

7.3 The Fano algorithm 433

7.4 The Creeper algorithm* 436

7.5 Simulations 448

7.6 Computational analysis of the stack algorithm 450

7.7 Error probability analysis of the stack algorithm 460

7.8 Analysis of the Fano algorithm 471

7.9 Analysis of Creeper* 477

Problems 481

8 Lowdensity paritycheck codes 485

8.1 LDPC block codes 486

8.2 LDPC convolutional codes 496

8.3 Block and convolutional permutors 508

8.4 Lower bounds on distances of LDPC codes 517

8.5 Iterative decoding of LDPC codes 529

8.6 Iterative limits and thresholds 538

8.7 Braided block codes* 553

Problems 562

9 Turbo coding 567

9.1 Parallel concatenation of two convolutional codes 567

9.2 Distance bounds of turbo codes 570

9.3 Parallel concatenation of three and more convolution codes 573

9.4 Iterative decoding of turbo codes 582

9.5 Braided convolutional codes* 586

Problems 591

10 Convolutional codes with good distance properties 593

10.1 Computing the Viterbi spectrum using FAST 594

10.2 The magnificient BEAST 598

10.3 Some classes of rate R = 1=2 convolutional codes 604

10.4 Low rate convolutional codes 608

10.5 High rate convolutional codes 621

10.6 Tailbiting trellis encoders 622