## Table of contents for Error correction coding : mathematical methods and algorithms / Todd K. Moon.

Bibliographic record and links to related information available from the Library of Congress catalog.

Note: Contents data are machine generated based on pre-publication provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.

```Contents
Preface iii
List of Program Files xxiv
List of Laboratory Exercises xxv
List of Algorithms xxvii
List of Figures xxxiii
List of Tables xxxv
List of Boxes xxxvi
Part I Introduction and Foundations 1
1 A Context for Error Correction Coding 2
1.1 Purpose of this Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Introduction: Where are Codes? . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 The Communications System . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Basic Digital Communications . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4.1 Binary Phase-Shift Keying . . . . . . . . . . . . . . . . . . . . . . 10
1.4.2 More General Digital Modulation . . . . . . . . . . . . . . . . . . 11
1.5 Signal Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5.1 The Gaussian Channel . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5.2 MAP and ML Detection . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.3 Special Case: Binary Detection . . . . . . . . . . . . . . . . . . . 18
1.5.4 Probability of Error for Binary Detection . . . . . . . . . . . . . . 19
1.5.5 Bounds on Performance: The Union Bound . . . . . . . . . . . . . 21
1.5.6 The Binary Symmetric Channel . . . . . . . . . . . . . . . . . . . 23
1.5.7 The BSC and the Gaussian Channel Model . . . . . . . . . . . . . 24
1.6 Memoryless Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.7 Energy Considerations for Coded Signals; Simulation . . . . . . . . . . . . 25
1.8 Some Important Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.8.1 Detection of Repetition Codes Over a BSC . . . . . . . . . . . . . 28
1.8.2 Soft-Decision Decoding of Repetition Codes Over the AWGN . . . 31
1.8.3 Simulation of Results . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.8.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.9 Hamming Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.9.1 Hard-input Decoding Hamming Codes . . . . . . . . . . . . . . . . 34
1.9.2 Other Representations of the Hamming Code . . . . . . . . . . . . 36
An Algebraic Representation . . . . . . . . . . . . . . . . . . . . . 36
A Polynomial Representation . . . . . . . . . . . . . . . . . . . . 37
Copyright 2004 by Todd K. Moon
x CONTENTS
A Trellis Representation . . . . . . . . . . . . . . . . . . . . . . . 37
The Tanner Graph Representation . . . . . . . . . . . . . . . . . . 38
1.10 The Basic Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.11 A Bit of Information Theory . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.11.1 Definitions for Discrete Random Variables . . . . . . . . . . . . . . 39
Entropy and Conditional Entropy . . . . . . . . . . . . . . . . . . 39
Relative Entropy, Mutual Information, and Channel Capacity . . . . 40
1.11.2 Definitions for Continuous Random Variables . . . . . . . . . . . . 41
1.11.3 The Channel Coding Theorem . . . . . . . . . . . . . . . . . . . . 43
1.11.4 "Proof" of the Channel Coding Theorem . . . . . . . . . . . . . . . 44
1.11.5 Transmission at Capacity with Errors . . . . . . . . . . . . . . . . 48
1.11.6 The Implication of the Channel Coding Theorem . . . . . . . . . . 49
1.12 Historical Milestones of Coding Theory . . . . . . . . . . . . . . . . . . . 49
Lab 1 Simulating a Communications Channel . . . . . . . . . . . . . . . 49
Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Use of Coding in Conjunction with the BSC . . . . . . . . . . . . . . . . . 51
Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Preliminary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . 51
Programming Part . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Resources and Implementation Suggestions . . . . . . . . . . . . . . . . . 52
1.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
1.14 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Part II Block Codes 59
2 Groups and Vector Spaces 60
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.2 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.2.1 Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.2.2 Cyclic Groups; Order of an Element . . . . . . . . . . . . . . . . . 64
2.2.3 Cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
2.2.4 Lagrange's Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 66
2.2.5 Induced Operations; Isomorphism . . . . . . . . . . . . . . . . . . 67
2.2.6 Homomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.3 Fields: A Prelude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
2.4 Review of Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
2.6 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3 Linear Block Codes 81
3.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.2 The Generator Matrix Description of Linear Block Codes . . . . . . . . . . 82
3.2.1 Rudimentary Implementation . . . . . . . . . . . . . . . . . . . . . 84
3.3 The Parity Check Matrix and Dual Codes . . . . . . . . . . . . . . . . . . 84
3.3.1 Some Simple Bounds on Block Codes . . . . . . . . . . . . . . . . 86
3.4 Error Detection and Correction over Hard-Input Channels . . . . . . . . . . 88
Copyright 2004 by Todd K. Moon
CONTENTS xi
3.4.1 Error Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.4.2 Error Correction: The Standard Array . . . . . . . . . . . . . . . . 88
3.5 Weight Distributions of Codes and Their Duals . . . . . . . . . . . . . . . 93
3.6 Hamming Codes and Their Duals . . . . . . . . . . . . . . . . . . . . . . . 95
3.7 Performance of Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.7.1 Error detection performance . . . . . . . . . . . . . . . . . . . . . 97
3.7.2 Error Correction Performance . . . . . . . . . . . . . . . . . . . . 98
3.7.3 Performance for Soft-Decision Decoding . . . . . . . . . . . . . . 101
3.8 Erasure Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.8.1 Binary Erasure Decoding . . . . . . . . . . . . . . . . . . . . . . . 103
3.9 Modifications to Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . 103
3.10 Best Known Linear Block Codes . . . . . . . . . . . . . . . . . . . . . . . 105
3.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.12 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4 Cyclic Codes, Rings, and Polynomials 111
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.2 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.3 Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.3.1 Rings of Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.4 Quotient Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
4.5 Ideals in Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
4.6 Algebraic Description of Cyclic Codes . . . . . . . . . . . . . . . . . . . . 118
4.7 Nonsystematic Encoding and Parity Check . . . . . . . . . . . . . . . . . . 119
4.8 Systematic Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
4.9 Some Hardware Background . . . . . . . . . . . . . . . . . . . . . . . . . 124
4.9.1 Computational Building Blocks . . . . . . . . . . . . . . . . . . . 124
4.9.2 Sequences and Power series . . . . . . . . . . . . . . . . . . . . . 125
4.9.3 Polynomial Multiplication . . . . . . . . . . . . . . . . . . . . . . 126
Last-Element-First Processing . . . . . . . . . . . . . . . . . . . . 126
First-Element-First Processing . . . . . . . . . . . . . . . . . . . . 126
4.9.4 Polynomial division . . . . . . . . . . . . . . . . . . . . . . . . . . 127
Last-Element First Processing . . . . . . . . . . . . . . . . . . . . 127
4.9.5 Simultaneous Polynomial Division and Multiplication . . . . . . . 130
First-Element-First Processing . . . . . . . . . . . . . . . . . . . . 130
4.10 Cyclic Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.11 Syndrome Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
4.12 Shortened Cyclic Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
Method 1: Simulating the extra clock shifts . . . . . . . . . . . . . 141
Method 2: Changing the Error Pattern Detection Circuit . . . . . . 142
4.13 Binary CRC Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
4.13.1 Byte-Oriented Encoding and Decoding Algorithms . . . . . . . . . 147
4.13.2 CRC Protecting Data Files or Data Packets . . . . . . . . . . . . . 151
Appendix 4.ALinear Feedback Shift Registers . . . . . . . . . . . . . . . . . . . . 152
Appendix 4.A.1Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . 152
Appendix 4.A.2Connection With Polynomial Division . . . . . . . . . . . . 155
Appendix 4.A.3Some Algebraic Properties of Shift Sequences . . . . . . . . 158
Copyright 2004 by Todd K. Moon
xii CONTENTS
Lab 2 Polynomial Division and Linear Feedback Shift Registers . . . . 159
Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
Preliminary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
Programming Part: BinLFSR . . . . . . . . . . . . . . . . . . . . . . . . 159
Resources and Implementation Suggestions . . . . . . . . . . . . . . . . . 159
Programming Part: BinPolyDiv . . . . . . . . . . . . . . . . . . . . . . 160
Follow-On Ideas and Problems . . . . . . . . . . . . . . . . . . . . . . . . 160
Lab 3 CRC Encoding and Decoding . . . . . . . . . . . . . . . . . . . . . 160
Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
Programming Part . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
Resources and Implementation Suggestions . . . . . . . . . . . . . . . . . 161
Static Member Variables . . . . . . . . . . . . . . . . . . . . . . . 161
Command Line Arguments . . . . . . . . . . . . . . . . . . . . . . 162
Picking Out All the Bits in a File . . . . . . . . . . . . . . . . . . . 162
4.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
4.15 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
5 Rudiments of Number Theory and Algebra 169
5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
5.2 Number Theoretic Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 173
5.2.1 Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
5.2.2 The Euclidean Algorithm and Euclidean Domains . . . . . . . . . . 175
5.2.3 The Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . . 175
5.2.4 The Sugiyama Algorithm . . . . . . . . . . . . . . . . . . . . . . . 180
5.2.5 Congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
5.2.6 The A Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
5.2.7 Some Cryptographic Payoff . . . . . . . . . . . . . . . . . . . . . 184
Fermat's Little Theorem . . . . . . . . . . . . . . . . . . . . . . . 184
RSA Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
5.3 The Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . 186
5.3.1 The CRT and Interpolation . . . . . . . . . . . . . . . . . . . . . . 188
The Evaluation Homomorphism . . . . . . . . . . . . . . . . . . . 188
The Interpolation Problem . . . . . . . . . . . . . . . . . . . . . . 189
5.4 Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
5.4.1 An examination of R and C . . . . . . . . . . . . . . . . . . . . . 192
5.4.2 Galois Field Construction: An Example . . . . . . . . . . . . . . . 194
5.4.3 Connection with Linear Feedback Shift Registers . . . . . . . . . . 197
5.5 Galois Fields: Mathematical Facts . . . . . . . . . . . . . . . . . . . . . . 198
5.6 Implementing Galois Field Arithmetic . . . . . . . . . . . . . . . . . . . . 202
5.6.1 Zech Logarithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
5.6.2 Hardware Implementations . . . . . . . . . . . . . . . . . . . . . . 203
5.7 Subfields of Galois Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
5.8 Irreducible and Primitive polynomials . . . . . . . . . . . . . . . . . . . . 205
5.9 Conjugate Elements and Minimal Polynomials . . . . . . . . . . . . . . . . 207
5.9.1 Minimal Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . 210
5.10 Factoring xn _ 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
Copyright 2004 by Todd K. Moon
CONTENTS xiii
5.11 Cyclotomic Cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
Appendix 5.AHow Many Irreducible Polynomials Are There? . . . . . . . . . . . 216
Appendix 5.A.1Solving for Im Explicitly: The Moebius Function . . . . . . 220
Lab 4 Programming the Euclidean Algorithm . . . . . . . . . . . . . . . 220
Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
Preliminary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
Programming Part . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
Lab 5 Programming Galois Field Arithmetic . . . . . . . . . . . . . . . . 222
Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
Preliminary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
Programming Part . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
5.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
5.13 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
6 BCH and Reed-Solomon Codes: Designer Cyclic Codes 233
6.1 BCH Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
6.1.1 Designing BCH Codes . . . . . . . . . . . . . . . . . . . . . . . . 233
6.1.2 The BCH Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
6.1.3 Weight Distributions For Some Binary BCH Codes . . . . . . . . . 238
6.1.4 Asymptotic Results For BCH Codes . . . . . . . . . . . . . . . . . 239
6.2 Reed-Solomon Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
6.2.1 Reed-Solomon Construction 1 . . . . . . . . . . . . . . . . . . . . 240
6.2.2 Reed-Solomon Construction 2 . . . . . . . . . . . . . . . . . . . . 241
6.2.3 Encoding Reed-Solomon Codes . . . . . . . . . . . . . . . . . . . 242
6.2.4 MDS Codes and Weight Distributions for RS Codes . . . . . . . . . 243
6.3 Decoding BCH and RS Codes: The General Outline . . . . . . . . . . . . . 245
6.3.1 Computation of the Syndrome . . . . . . . . . . . . . . . . . . . . 245
6.3.2 The Error Locator Polynomial . . . . . . . . . . . . . . . . . . . . 246
6.3.3 Chien Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
6.4 Finding the Error Locator Polynomial . . . . . . . . . . . . . . . . . . . . 247
6.4.1 Simplifications for Binary Codes and Peterson's Algorithm . . . . . 249
6.4.2 Berlekamp-Massey Algorithm . . . . . . . . . . . . . . . . . . . . 251
6.4.3 Characterization of LFSR Length in Massey's Algorithm . . . . . . 253
6.4.4 Simplifications for Binary Codes . . . . . . . . . . . . . . . . . . . 257
6.5 Non-Binary BCH and RS Decoding . . . . . . . . . . . . . . . . . . . . . 259
6.5.1 Forney's Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 260
6.6 Euclidean Algorithm for Error Locator Polynomial . . . . . . . . . . . . . 264
6.7 Erasure Decoding for Nonbinary BCH or RS codes . . . . . . . . . . . . . 265
6.8 Galois Field Fourier Transform Methods . . . . . . . . . . . . . . . . . . . 267
6.8.1 Equivalence of the Two Reed-Solomon Code Constructions . . . . 272
6.8.2 Frequency-Domain Decoding . . . . . . . . . . . . . . . . . . . . 273
6.9 Variations and Extensions of Reed-Solomon Codes . . . . . . . . . . . . . 274
6.9.1 Simple Modifications . . . . . . . . . . . . . . . . . . . . . . . . . 274
6.9.2 Generalized Reed-Solomon Codes and Alternant Codes . . . . . . . 274
6.9.3 Goppa Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
6.9.4 Decoding Alternant Codes . . . . . . . . . . . . . . . . . . . . . . 278
Copyright 2004 by Todd K. Moon
xiv CONTENTS
6.9.5 The McEliece Public Key Cryptosystem . . . . . . . . . . . . . . . 278
Lab 6 Programming the Berlekamp-Massey Algorithm . . . . . . . . . . 279
Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
Preliminary exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
Programming Part . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
Resources and Implementation Suggestions . . . . . . . . . . . . . . . . . 280
Lab 7 Programming the BCH Decoder . . . . . . . . . . . . . . . . . . . . 280
Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
Preliminary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
Programming Part . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
Resources and Implementation Suggestions . . . . . . . . . . . . . . . . . 281
Follow-On Ideas and Problems . . . . . . . . . . . . . . . . . . . . . . . . 281
Lab 8 Reed-Solomon Encoding and Decoding . . . . . . . . . . . . . . . 282
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
Programming Part . . . . . . . . . . . . . . . . . . . . . . . . . . 282
Appendix 6.AProof of Newton's Identities . . . . . . . . . . . . . . . . . . . . . . 282
6.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
6.11 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
7 Alternate Decoding Algorithms for Reed-Solomon Codes 291
7.1 Introduction: Workload for Reed-Solomon Decoding . . . . . . . . . . . . 291
7.2 Derivations of Welch-Berlekamp Key Equation . . . . . . . . . . . . . . . 292
7.2.1 The Welch-Berlekamp Derivation of the WB Key Equation . . . . . 292
7.2.2 Derivation From the Conventional Key Equation . . . . . . . . . . 296
7.3 Finding the Error Values . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
7.4 Methods of Solving the WB Key Equation . . . . . . . . . . . . . . . . . . 300
7.4.1 Background: Modules . . . . . . . . . . . . . . . . . . . . . . . . 300
7.4.2 The Welch-Berlekamp Algorithm . . . . . . . . . . . . . . . . . . 301
7.4.3 Modular Solution of the WB Key Equation . . . . . . . . . . . . . 308
7.5 Erasure Decoding with the Welch-Berlekamp Key Equation . . . . . . . . . 319
7.6 The Guruswami-Sudan Decoding Algorithm and Soft RS Decoding . . . . . 320
7.6.1 Bounded Distance, ML, and List Decoding . . . . . . . . . . . . . 320
7.6.2 Error Correction by Interpolation . . . . . . . . . . . . . . . . . . . 320
7.6.3 Polynomials in Two Variables . . . . . . . . . . . . . . . . . . . . 322
Degree and Monomial Order . . . . . . . . . . . . . . . . . . . . . 322
Zeros and Multiple Zeros . . . . . . . . . . . . . . . . . . . . . . . 326
7.6.4 The GS Decoder: The Main Theorems . . . . . . . . . . . . . . . . 328
The Interpolation Theorem . . . . . . . . . . . . . . . . . . . . . . 328
The Factorization Theorem . . . . . . . . . . . . . . . . . . . . . . 329
The Correction Distance . . . . . . . . . . . . . . . . . . . . . . . 330
The Number of Polynomials in the Decoding List . . . . . . . . . . 332
7.6.5 Algorithms for Computing the Interpolation Step . . . . . . . . . . 334
Finding Linearly Dependent Columns: The Feng-Tzeng Algorithm 335
Finding the Intersection of Kernels: The Kötter Algorithm . . . . . 340
7.6.6 A Special Case: m _ 1 and L _ 1 . . . . . . . . . . . . . . . . . . 346
Copyright 2004 by Todd K. Moon
CONTENTS xv
7.6.7 The Roth-Ruckenstein Algorithm . . . . . . . . . . . . . . . . . . 347
What To Do with Lists of Factors? . . . . . . . . . . . . . . . . . . 351
7.6.8 Soft-Decision Decoding of Reed-Solomon Codes . . . . . . . . . . 355
Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
A Factorization Theorem . . . . . . . . . . . . . . . . . . . . . . . 357
Mapping from Reliability to Multiplicity . . . . . . . . . . . . . . 358
The Geometry of the Decoding Regions . . . . . . . . . . . . . . . 360
Computing the Reliability Matrix . . . . . . . . . . . . . . . . . . 361
7.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
7.8 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
8 Other Important Block Codes 366
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
8.2 Hadamard Matrices, Codes, and Transforms . . . . . . . . . . . . . . . . . 366
8.2.1 Introduction to Hadamard matrices . . . . . . . . . . . . . . . . . . 366
8.2.2 The Paley Construction of Hadamard Matrices . . . . . . . . . . . 368
8.2.3 Hadamard Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
8.3 Reed-Muller Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
8.3.1 Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 372
8.3.2 Definition of the Reed-Muller Codes . . . . . . . . . . . . . . . . . 373
8.3.3 Encoding and Decoding Algorithms for First-Order RM Codes . . . 376
Encoding RM.1;m/ Codes . . . . . . . . . . . . . . . . . . . . . 376
Decoding RM.1;m/ Codes . . . . . . . . . . . . . . . . . . . . . 376
Expediting Decoding Using the Fast Hadamard Transform . . . . . 379
8.3.4 The Reed Decoding Algorithm for RM.r;m/ Codes, r _ 1 . . . . . 380
Details for an RM.2; 4/ Code . . . . . . . . . . . . . . . . . . . . 381
A Geometric Viewpoint . . . . . . . . . . . . . . . . . . . . . . . 384
8.3.5 Other Constructions of Reed-Muller Codes . . . . . . . . . . . . . 388
8.4 Building Long Codes from Short Codes: The Squaring Construction . . . . 388
8.5 Quadratic Residue Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
8.6 Golay Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396
8.6.1 Decoding the Golay Code . . . . . . . . . . . . . . . . . . . . . . 397
Algebraic Decoding of the G23 Golay Code . . . . . . . . . . . . . 398
Arithmetic Decoding of the G24 Code . . . . . . . . . . . . . . . . 399
8.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400
8.8 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
9 Bounds on Codes 403
9.1 The Gilbert-Varshamov Bound . . . . . . . . . . . . . . . . . . . . . . . . 406
9.2 The Plotkin Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
9.3 The Griesmer Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
9.4 The Linear Programming and Related Bounds . . . . . . . . . . . . . . . . 410
9.4.1 Krawtchouk Polynomials . . . . . . . . . . . . . . . . . . . . . . . 412
9.4.2 Character . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
9.4.3 Krawtchouk Polynomials and Characters . . . . . . . . . . . . . . 413
9.5 The McEliece-Rodemich-Rumsey-Welch Bound . . . . . . . . . . . . . . . 416
9.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
9.7 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421
Copyright 2004 by Todd K. Moon
xvi CONTENTS
10 Bursty Channels, Interleavers, and Concatenation 422
10.1 Introduction to Bursty Channels . . . . . . . . . . . . . . . . . . . . . . . 422
10.2 Interleavers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
10.3 An Application of Interleaved RS Codes: Compact Discs . . . . . . . . . . 424
10.4 Product Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427
10.5 Reed-Solomon Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
10.6 Concatenated Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
10.7 Fire Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
10.7.1 Fire Code Definition . . . . . . . . . . . . . . . . . . . . . . . . . 430
10.7.2 Decoding Fire codes: Error Trapping Decoding . . . . . . . . . . . 432
10.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
10.9 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
11 Soft-Decision Decoding Algorithms 436
11.1 Introduction and General Notation . . . . . . . . . . . . . . . . . . . . . . 436
11.2 Generalized Minimum Distance Decoding . . . . . . . . . . . . . . . . . . 438
11.2.1 Distance Measures and Properties . . . . . . . . . . . . . . . . . . 439
11.3 The Chase Decoding Algorithms . . . . . . . . . . . . . . . . . . . . . . . 442
11.4 Halting the Search: An Optimality Condition . . . . . . . . . . . . . . . . 442
11.5 Ordered Statistic Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . 444
11.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
11.7 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
Part III Codes on Graphs 448
12 Convolutional Codes 449
12.1 Introduction and Basic Notation . . . . . . . . . . . . . . . . . . . . . . . 449
12.1.1 The State . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
12.2 Definition of Codes; Equivalent Codes . . . . . . . . . . . . . . . . . . . . 455
12.2.1 Catastrophic Codes . . . . . . . . . . . . . . . . . . . . . . . . . . 458
12.2.2 Polynomial and Rational Encoders . . . . . . . . . . . . . . . . . . 461
12.2.3 Constraint Length and Minimal Encoders . . . . . . . . . . . . . . 462
12.2.4 Systematic Encoders . . . . . . . . . . . . . . . . . . . . . . . . . 465
12.3 Decoding Convolutional Codes . . . . . . . . . . . . . . . . . . . . . . . . 466
12.3.1 Introduction and Notation . . . . . . . . . . . . . . . . . . . . . . 466
12.3.2 The Viterbi Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 469
12.3.3 Some Implementation Issues . . . . . . . . . . . . . . . . . . . . . 478
The Basic Operation: Add-Compare-Select . . . . . . . . . . . . . 478
Decoding Streams of Data: Windows on the Trellis . . . . . . . . . 479
Output Decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
Hard and Soft Decoding; Quantization . . . . . . . . . . . . . . . . 482
Synchronization Issues . . . . . . . . . . . . . . . . . . . . . . . . 484
12.4 Some Performance Results . . . . . . . . . . . . . . . . . . . . . . . . . . 484
12.5 Error Analysis for Convolutional Codes . . . . . . . . . . . . . . . . . . . 489
12.5.1 Enumerating Paths Through the Trellis . . . . . . . . . . . . . . . . 491
Enumerating on More Complicated Graphs: Mason's Rule . . . . . 495
Copyright 2004 by Todd K. Moon
CONTENTS xvii
12.5.2 Characterizing the Node Error Probability Pe and the Bit Error Rate
Pb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
12.5.3 A Bound on Pd for Discrete Channels . . . . . . . . . . . . . . . . 500
Performance Bound on the BSC . . . . . . . . . . . . . . . . . . . 501
12.5.4 A Bound on Pd for BPSK Signaling Over the AWGN Channel . . . 501
12.5.5 Asymptotic Coding Gain . . . . . . . . . . . . . . . . . . . . . . . 503
12.6 Tables of Good Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504
12.7 Puncturing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
12.7.1 Puncturing to Achieve Variable Rate . . . . . . . . . . . . . . . . . 508
12.8 Suboptimal Decoding Algorithms for Convolutional Codes . . . . . . . . . 509
12.8.1 Tree Representations . . . . . . . . . . . . . . . . . . . . . . . . . 509
12.8.2 The Fano Metric . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
12.8.3 The Stack Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 513
12.8.4 The Fano Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 514
12.8.5 Other Issues for Sequential Decoding . . . . . . . . . . . . . . . . 519
12.8.6 A Variation on the Viterbi Algorithm: the M Algorithm . . . . . . . 520
12.9 Convolutional Codes as Block Codes . . . . . . . . . . . . . . . . . . . . . 520
12.10 Trellis Representations of Block and Cyclic Codes . . . . . . . . . . . . . . 521
12.10.1 Block Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522
12.10.2 Cyclic Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522
12.10.3 Trellis Decoding of Block Codes . . . . . . . . . . . . . . . . . . . 523
Lab 9 Programming Convolutional Encoders . . . . . . . . . . . . . . . . 523
Lab 10Convolutional decoders: The Viterbi Algorithm . . . . . . . . . . 525
12.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527
12.12 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533
13 Trellis Coded Modulation 534
13.1 Adding Redundancy by Adding Signals . . . . . . . . . . . . . . . . . . . 534
13.2 Background on Signal Constellations . . . . . . . . . . . . . . . . . . . . . 534
13.3 TCM Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536
13.3.1 The General Ungerboeck Coding Framework . . . . . . . . . . . . 544
13.3.2 The Set Partitioning Idea . . . . . . . . . . . . . . . . . . . . . . . 544
13.4 Some Error Analysis for TCM Codes . . . . . . . . . . . . . . . . . . . . . 545
13.4.1 General Considerations . . . . . . . . . . . . . . . . . . . . . . . . 545
13.4.2 A Description of the Error Events . . . . . . . . . . . . . . . . . . 547
13.4.3 Known Good TCM Codes . . . . . . . . . . . . . . . . . . . . . . 551
13.5 Decoding TCM Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552
13.6 Rotational Invariance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556
Differential Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 557
Constellation Labels and Partitions . . . . . . . . . . . . . . . . . . 559
13.7 Multidimensional TCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 561
13.7.1 Some Advantages of Multidimensional TCM . . . . . . . . . . . . 561
13.7.2 Lattices and Sublattices . . . . . . . . . . . . . . . . . . . . . . . . 562
Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
Common Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . 565
Sublattices and Cosets . . . . . . . . . . . . . . . . . . . . . . . . 566
The Lattice Code Idea . . . . . . . . . . . . . . . . . . . . . . . . 567
Copyright 2004 by Todd K. Moon
xviii CONTENTS
Sources of Coding Gain in Lattice Codes . . . . . . . . . . . . . . 568
Some Good Lattice Codes . . . . . . . . . . . . . . . . . . . . . . 570
13.8 The V.34 Modem Standard . . . . . . . . . . . . . . . . . . . . . . . . . . 570
Lab 11Trellis-Coded Modulation Encoding and Decoding . . . . . . . . 577
13.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578
13.10 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579
Part IV Iteratively Decoded Codes 581
14 Turbo Codes 582
14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 582
14.2 Encoding Parallel Concatenated Codes . . . . . . . . . . . . . . . . . . . . 584
14.3 Turbo Decoding Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 586
14.3.1 The MAP Decoding Algorithm . . . . . . . . . . . . . . . . . . . . 588
14.3.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588
14.3.3 Posterior Probability . . . . . . . . . . . . . . . . . . . . . . . . . 590
14.3.4 Computing (r)t and _t . . . . . . . . . . . . . . . . . . . . . . . . . 592
14.3.5 Computing °t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593
14.3.6 Normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594
14.3.7 Summary of the BCJR Algorithm . . . . . . . . . . . . . . . . . . 596
14.3.8 A Matrix/Vector Formulation . . . . . . . . . . . . . . . . . . . . . 597
14.3.9 Comparison of the Viterbi and BCJR Algorithms . . . . . . . . . . 598
14.3.10 The BCJR Algorithm for Systematic Codes . . . . . . . . . . . . . 598
14.3.11 Turbo Decoding Using the BCJR Algorithm . . . . . . . . . . . . . 600
The Terminal State of the Encoders . . . . . . . . . . . . . . . . . 602
14.3.12 Likelihood Ratio Decoding . . . . . . . . . . . . . . . . . . . . . . 602
Log Prior Ratio ,p;t . . . . . . . . . . . . . . . . . . . . . . . . . 603
Log Posterior ,
.0/
s;t . . . . . . . . . . . . . . . . . . . . . . . . . . . 605
14.3.13 Statement of the Turbo Decoding Algorithm . . . . . . . . . . . . . 605
14.3.14 Turbo Decoding Stopping Criteria . . . . . . . . . . . . . . . . . . 605
The Cross Entropy Stopping Criterion . . . . . . . . . . . . . . . . 606
The Sign Change Ratio (SCR) Criterion . . . . . . . . . . . . . . . 607
The Hard Decision Aided (HDA) Criterion . . . . . . . . . . . . . 608
14.3.15 Modifications of the MAP Algorithm . . . . . . . . . . . . . . . . 608
The Max-Log-MAP Algorithm . . . . . . . . . . . . . . . . . . . . 608
14.3.16 Corrections to the Max-Log-MAP Algorithm . . . . . . . . . . . . 609
14.3.17 The Soft Output Viterbi Algorithm . . . . . . . . . . . . . . . . . . 610
14.4 On the Error Floor and Weight Distributions . . . . . . . . . . . . . . . . . 612
14.4.1 The Error Floor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612
14.4.2 Spectral Thinning and Random Interleavers . . . . . . . . . . . . . 614
14.4.3 On Interleavers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618
14.5 EXIT Chart Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 619
14.5.1 The EXIT Chart . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622
14.6 Block Turbo Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623
14.7 Turbo Equalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 626
14.7.1 Introduction to Turbo Equalization . . . . . . . . . . . . . . . . . . 626
14.7.2 The Framework for Turbo Equalization . . . . . . . . . . . . . . . 627
Copyright 2004 by Todd K. Moon
CONTENTS xix
Lab 12Turbo Code Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . 628
Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 628
14.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629
14.9 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631
15 Low-Density Parity-Check Codes 633
15.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633
15.2 LDPC Codes: Construction and Notation . . . . . . . . . . . . . . . . . . . 634
15.3 Tanner Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637
15.4 Transmission Through a Gaussian Channel . . . . . . . . . . . . . . . . . . 637
15.5 Decoding LDPC Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 639
15.5.1 The Vertical Step: Updating qmn.x/ . . . . . . . . . . . . . . . . . 640
15.5.2 Horizontal Step: Updating rmn.x/ . . . . . . . . . . . . . . . . . . 643
15.5.3 Terminating and Initializing the Decoding Algorithm . . . . . . . . 646
15.5.4 Summary of the Algorithm . . . . . . . . . . . . . . . . . . . . . . 647
15.5.5 Message Passing Viewpoint . . . . . . . . . . . . . . . . . . . . . 648
15.5.6 Likelihood Ratio Decoder Formulation . . . . . . . . . . . . . . . 648
15.6 Why Low-Density Parity-Check Codes? . . . . . . . . . . . . . . . . . . . 652
15.7 The Iterative Decoder on General Block Codes . . . . . . . . . . . . . . . . 653
15.8 Density Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654
15.9 Irregular LDPC Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658
15.9.1 Degree Distribution Pairs . . . . . . . . . . . . . . . . . . . . . . . 658
15.9.2 Some Good Codes . . . . . . . . . . . . . . . . . . . . . . . . . . 659
15.9.3 Density Evolution for Irregular Codes . . . . . . . . . . . . . . . . 660
15.9.4 Computation and Optimization of Density Evolution . . . . . . . . 663
15.9.5 Using Irregular Codes . . . . . . . . . . . . . . . . . . . . . . . . 663
15.10 More on LDPC Code Construction . . . . . . . . . . . . . . . . . . . . . . 663
15.10.1 A Construction Based on Finite Geometries . . . . . . . . . . . . . 664
15.10.2 Constructions Based on Other Combinatoric Objects . . . . . . . . 664
15.11 Encoding LDPC Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665
15.12 A Variation: Low Density Generator Matrix Codes . . . . . . . . . . . . . 666
15.13 Serial Concatenated Codes; Repeat-Accumulate Codes . . . . . . . . . . . 667
15.13.1 Irregular RA Codes . . . . . . . . . . . . . . . . . . . . . . . . . . 669
Lab 13Programming an LDPC Decoder . . . . . . . . . . . . . . . . . . . . 670
Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 670
Background - Sparse Matrices . . . . . . . . . . . . . . . . . . . . . . . . 670
Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671
Numerical Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . 671
15.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 672
15.15 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675
16 Decoding Algorithms on Graphs 676
16.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 676
16.2 Operations in Semirings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677
16.3 Functions on Local Domains . . . . . . . . . . . . . . . . . . . . . . . . . 677
16.4 Factor Graphs and Marginalization . . . . . . . . . . . . . . . . . . . . . . 682
16.4.1 Marginalizing on a Single Variable . . . . . . . . . . . . . . . . . . 683
16.4.2 Marginalizing on All Individual Variables . . . . . . . . . . . . . . 687
Copyright 2004 by Todd K. Moon
xx CONTENTS
16.5 Applications to Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 690
16.5.1 Block Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 690
16.5.2 Modifications to Message Passing for Binary Variables . . . . . . . 691
16.5.3 Trellis Processing and the Forward/Backward Algorithm . . . . . . 692
16.5.4 Turbo Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695
16.6 Summary of Decoding Algorithms on Graphs . . . . . . . . . . . . . . . . 695
16.7 Transformations of Factor Graphs . . . . . . . . . . . . . . . . . . . . . . . 696
16.7.1 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 696
16.7.2 Stretching Variable Nodes . . . . . . . . . . . . . . . . . . . . . . 697
16.7.3 Exact Computation of Graphs with Cycles . . . . . . . . . . . . . . 698
16.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700
16.9 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702
Part V Space-Time Coding 703
17 Fading Channels and Space-Time Codes 704
17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704
17.2 Fading Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704
17.2.1 Rayleigh Fading . . . . . . . . . . . . . . . . . . . . . . . . . . . 706
17.3 Diversity Transmission and Reception: The MIMO Channel . . . . . . . . 708
17.3.1 The Narrowband MIMO Channel . . . . . . . . . . . . . . . . . . 710
17.3.2 Diversity Performance with Maximal-Ratio Combining . . . . . . . 711
17.4 Space-Time Block Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 713
17.4.1 The Alamouti Code . . . . . . . . . . . . . . . . . . . . . . . . . . 713
17.4.2 A More General Formulation . . . . . . . . . . . . . . . . . . . . . 715
17.4.3 Performance Calculation . . . . . . . . . . . . . . . . . . . . . . . 715
Real Orthogonal Designs . . . . . . . . . . . . . . . . . . . . . . . 717
Encoding and Decoding Based on Orthogonal Designs . . . . . . . 718
Generalized Real Orthogonal Designs . . . . . . . . . . . . . . . . 720
17.4.4 Complex Orthogonal Designs . . . . . . . . . . . . . . . . . . . . 721
Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 722
17.5 Space-Time Trellis Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 722
17.5.1 Concatenation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 726
17.6 How Many Antennas? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 726
17.7 Estimating Channel Information . . . . . . . . . . . . . . . . . . . . . . . 727
17.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 727
17.9 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 728
A Log likelihood algebra 729
A.1 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 731
Index 744
```

Library of Congress Subject Headings for this publication:

Engineering mathematics.
Error-correcting codes (Information theory).