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.


Counter
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).