### Read more

## W. Cary Huffman & Vera Pless

#### Fundamentals of Error-Correcting Codes

is an in-depth introduction to coding theory fromboth an engineering and mathematical viewpoint. As well as covering classical topics, much

coverage is included of recent techniques that until now could only be found in specialist

journals and book publications. Numerous exercises and examples and an accessible

writing style make this a lucid and effective introduction to coding theory for advanced

undergraduate and graduate students, researchers and engineers, whether approaching the

subject from a mathematical, engineering, or computer science background.

### Professor W. Cary Huffman

graduated with a PhDin mathematics from the California Institute of Technology in 1974. He taught at Dartmouth College and Union College until he joined the Department of Mathematics and Statistics at Loyola in 1978, serving as chair of the department from 1986 through 1992. He is an author of approximately 40 research papers in finite group theory, combinatorics, and coding theory, which have appeared in journals such as the Journal of Algebra, IEEE Transactions on Information Theory, and the Journal of Combinatorial Theory.### Professor Vera

Pless was an undergraduate at the University of Chicago and received herPhDfrom Northwestern in 1957. After ten years at the Air Force Cambridge Research

Laboratory, she spent a few years at MIT’s project MAC. She joined the University of

Illinois-Chicago’s Department of Mathematics, Statistics, and Computer Science as a full

professor in 1975 and has been there ever since. She is a University of Illinois Scholar and

has published over 100 papers.

Preface

**C**oding theory originated with the 1948 publication of the paper “A mathematical theory

of communication” by Claude Shannon. For the past half century, coding theory has grown

into a discipline intersecting mathematics and engineering with applications to almost every

area of communication such as satellite and cellular telephone transmission, compact disc

recording, and data storage.

During the 50th anniversary year of Shannon’s seminal paper, the two volume Handbook

of Coding Theory, edited by the authors of the current text, was published by Elsevier

Science. That Handbook, with contributions from 33 authors, covers a wide range of topics

at the frontiers of research. As editors of the Handbook, we felt it would be appropriate

to produce a textbook that could serve in part as a bridge to the Handbook. This textbook

is intended to be an in-depth introduction to coding theory from both a mathematical and

engineering viewpoint suitable either for the classroom or for individual study. Several of

the topics are classical, while others cover current subjects that appear only in specialized

books and journal publications.We hope that the presentation in this book, with its numerous

examples and exercises, will serve as a lucid introduction that will enable readers to pursue

some of the many themes of coding theory.

Fundamentals of Error-Correcting Codes is a largely self-contained textbook suitable

for advanced undergraduate students and graduate students at any level. A prerequisite for

this book is a course in linear algebra. A course in abstract algebra is recommended, but not

essential. This textbook could be used for at least three semesters.Awide variety of examples

illustrate both theory and computation. Over 850 exercises are interspersed at points in the

text where they are most appropriate to attempt. Most of the theory is accompanied by

detailed proofs, with some proofs left to the exercises. Because of the number of examples

and exercises that directly illustrate the theory, the instructor can easily choose either to

emphasize or deemphasize proofs.

In this preface we briefly describe the contents of the 15 chapters and give a suggested

outline for the first semester. We also propose blocks of material that can be combined in a

variety of ways to make up subsequent courses. Chapter 1 is basic with the introduction of

linear codes, generator and parity check matrices, dual codes, weight and distance, encoding

and decoding, and the Sphere Packing Bound. The Hamming codes, Golay codes, binary

Reed–Muller codes, and the hexacode are introduced. Shannon’s Theorem for the binary

symmetric channel is discussed. Chapter 1 is certainly essential for the understanding of

the remainder of the book.

Chapter 2 covers the main upper and lower bounds on the size of linear and nonlinear

codes. These include the Plotkin, Johnson, Singleton, Elias, Linear Programming, Griesmer,

Gilbert, and Varshamov Bounds. Asymptotic versions of most of these are included. MDS

codes and lexicodes are introduced.

Chapter 3 is an introduction to constructions and properties of finite fields, with a few

proofs omitted. A quick treatment of this chapter is possible if the students are familiar

with constructing finite fields, irreducible polynomials, factoring polynomials over finite

fields, and Galois theory of finite fields. Much of Chapter 3 is immediately used in the study

of cyclic codes in Chapter 4. Even with a background in finite fields, cyclotomic cosets

(Section 3.7) may be new to the student.

Chapter 4 gives the basic theory of cyclic codes. Our presentation interrelates the concepts

of idempotent generator, generator polynomial, zeros of a code, and defining sets.

Multipliers are used to explore equivalence of cyclic codes. Meggitt decoding of cyclic

codes is presented as are extended cyclic and affine-invariant codes.

Chapter 5 looks at the special families of BCH and Reed–Solomon cyclic codes as well as

generalized Reed–Solomon codes. Four decoding algorithms for these codes are presented.

Burst errors and the technique of concatenation for handling burst errors are introduced

with an application of these ideas to the use of Reed–Solomon codes in the encoding and

decoding of compact disc recorders.

Continuing with the theory of cyclic codes, Chapter 6 presents the theory of duadic

codes, which include the family of quadratic residue codes. Because the complete theory of

quadratic residue codes is only slightly simpler than the theory of duadic codes, the authors

have chosen to present the more general codes and then apply the theory of these codes

to quadratic residue codes. Idempotents of binary and ternary quadratic residue codes are

explicitly computed. As a prelude to Chapter 8, projective planes are introduced as examples

of combinatorial designs held by codewords of a fixed weight in a code.

Chapter 7e xpands on the concept of weight distribution defined in Chapter 1. Six equivalent

forms of the MacWilliams equations, including the Pless power moments, that relate

the weight distributions of a code and its dual, are formulated. MDS codes, introduced in

Chapter 2, and coset weight distributions, introduced in Chapter 1, are revisited in more

depth. A proof of a theorem of MacWilliams on weight preserving transformations is given

in Section 7.9.

Chapter 8 delineates the basic theory of block designs particularly as they arise from

the supports of codewords of fixed weight in certain codes. The important theorem of

Assmus–Mattson is proved. The theory of projective planes in connection with codes, first

introduced in Chapter 6, is examined in depth, including a discussion of the nonexistence

of the projective plane of order 10.

Chapter 9 consolidates much of the extensive literature on self-dual codes. The Gleason–

Pierce–Ward Theorem is proved showing why binary, ternary, and quaternary self-dual

codes are the most interesting self-dual codes to study. Gleason polynomials are introduced

and applied to the determination of bounds on the minimum weight of self-dual codes.

Techniques for classifying self-dual codes are presented. Formally self-dual codes and additive

codes over F4, used in correcting errors in quantum computers, share many properties

of self-dual codes; they are introduced in this chapter.

The Golay codes and the hexacode are the subject of Chapter 10. Existence and uniqueness

of these codes are proved. The Pless symmetry codes, which generalize the ternary Golay

codes, are defined and some of their properties are given. The connection between codes

and lattices is developed in the final section of the chapter.

The theory of the covering radius of a code, first introduced in Chapter 1, is the topic

of Chapter 11. The covering radii of BCH codes, Reed–Muller codes, self-dual codes, and

subcodes are examined. The length function, a basic tool in finding bounds on the covering

radius, is presented along with many of its properties.

Chapter 12 examines linear codes over the ring Z4 of integers modulo 4. The theory of

these codes is compared and contrasted with the theory of linear codes over fields. Cyclic,

quadratic residue, and self-dual linear codes overZ4 are defined and analyzed. The nonlinear

binary Kerdock and Preparata codes are presented as the Gray image of certain linear codes

over Z4, an amazing connection that explains many of the remarkable properties of these

nonlinear codes. To study these codes, Galois rings are defined, analogously to extension

fields of the binary field.

Chapter 13 presents a brief introduction to algebraic geometry which is sufficient for a

basic understanding of algebraic geometry codes. Goppa codes, generalized Reed–Solomon

codes, and generalized Reed–Muller codes can be realized as algebraic geometry codes.

A family of algebraic geometry codes has been shown to exceed the Gilbert–Varshamov

Bound, a result that many believed was not possible.

Until Chapter 14, the codes considered were block codes where encoding depended only

upon the current message. In Chapter 14 we look at binary convolutional codes where

each codeword depends not only on the current message but on some messages in the

past as well. These codes are studied as linear codes over the infinite field of binary rational

functions. State and trellis diagrams are developed for theViterbi Algorithm, one of the main

decoding algorithms for convolutional codes. Their generator matrices and free distance are

examined.

Chapter 15 concludes the textbook with a look at soft decision and iterative decoding.

Until this point, we had only examined hard decision decoding. We begin with a more

detailed look at communication channels, particularly those subject to additive white Gaussian

noise. A soft decision Viterbi decoding algorithm is developed for convolutional codes.

Low density parity check codes and turbo codes are defined and a number of decoders for

these codes are examined. The text concludes with a brief history of the application of codes

to deep space exploration.

The following chapters and sections of this book are recommended as an introductory

one-semester course in coding theory:

*Chapter 1 (except Section 1.7),*

*Sections 2.1, 2.3.4, 2.4, 2.7–2.9,*

*Chapter 3 (except Section 3.8),*

*Chapter 4 (except Sections 4.6 and 4.7),*

*Chapter 5 (except Sections 5.4.3, 5.4.4, 5.5, and 5.6), and*

*Sections 7.1–7.3.*

If it is unlikely that a subsequent course in coding theory will be taught, the material in

Chapter 7can be replaced by the last two sections of Chapter 5. This material will show

how a compact disc is encoded and decoded, presenting a nice real-world application that

students can relate to.

For subsequent semesters of coding theory, we suggest a combination of some of the

following blocks of material.With each block we have included sections that will hopefully

make the blocks self-contained under the assumption that the first course given above has

been completed. Certainly other blocks are possible. A semester can be made up of more

than one block. Later we give individual chapters or sections that stand alone and can be

used in conjunction with each other or with some of these blocks. The sections and chapters

are listed in the order they should be covered.

**Sections 1.7, 8.1–8.4, 9.1–9.7, and Chapter 10. Sections 8.1–8.4 of this block present the**

essential material relating block designs to codes with particular emphasis on designs

arising from self-dual codes. The material from Chapter 9 gives an in-depth study of selfdual

codes with connections to designs. Chapter 10 studies the Golay codes and hexacode

in great detail, again using designs to help in the analysis. Section 2.11 can be added to

this block as the binary Golay codes are lexicodes.

**Sections 1.7, 7.4–7.10, Chapters 8, 9, and 10, and Section 2.11. This is an extension of**

the above block with more on designs from codes and codes from designs. It also looks

at weight distributions in more depth, part of which is required in Section 9.12. Codes

closely related to self-dual codes are also examined. This block may require an entire

semester.

**Sections 4.6, 5.4.3, 5.4.4, 5.5, 5.6, and Chapters 14 and 15. This block covers most of the**

decoding algorithms described in the text but not studied in the first course, including both

hard and soft decision decoding. It also introduces the important classes of convolutional

and turbo codes that are used in many applications particularly in deep space communication.

This would be an excellent block for engineering students or others interested in

applications.

**Sections 2.2, 2.3, 2.5, 2.6, 2.10, and Chapter 13. This block finishes the nonasymptotic**

bounds not covered in the first course and presents the asymptotic versions of these bounds.

The algebraic geometry codes and Goppa codes are important for, among other reasons,

their relationship to the bounds on families of codes.

**Section 1.7and Chapters 6 and 12. This block studies two families of codes extensively:**

duadic codes, which include quadratic residue codes, and linear codes over Z4. There

is some overlap between the two chapters to warrant studying them together. When

presenting Section 12.5.1, ideas from Section 9.6 should be discussed. Similarly it is

helpful to examine Section 10.6 before presenting Section 12.5.3.

The following mini-blocks and chapters could be used in conjunction with one another

or with the above blocks to construct a one-semester course.

Section 1.7and Chapter 6. Chapter 6 can stand alone after Section 1.7is covered.

Sections 1.7, 8.1–8.4, Chapter 10, and Section 2.11. This mini-block gives an in-depth

study of the Golay codes and hexacode with the prerequisite material on designs covered first.

Section 1.7and Chapter 12. After Section 1.7is covered, Chapter 12 can be used alone

with the exception of Sections 12.4 and 12.5. Section 12.4 can either be omitted or

supplemented with material from Section 6.6. Section 12.5 can either be skipped or

supplemented with material from Sections 9.6 and 10.6.

Chapter 11. This chapter can stand alone.

Chapter 14. This chapter can stand alone.

The authors would like to thank a number of people for their advice and suggestions

for this book. Philippe Gaborit tested portions of the text in its earliest form in a coding

theory course he taught at the University of Illinois at Chicago resulting in many helpful

insights. Philippe also provided some of the data used in the tables in Chapter 6. Judy

Walker’s monograph [343] on algebraic geometry codes was invaluable when we wrote

Chapter 13; Judy kindly read this chapter and offered many helpful suggestions. Ian Blake

and Frank Kschischang read and critiqued Chapters 14 and 15 providing valuable direction.

Bob McEliece provided data for some of the figures in Chapter 15. The authors also wish

to thank the staff and associates of Cambridge University Press for their valuable assistance

with production of this book. In particular we thank editorial manager Dr. Philip Meyler,

copy editor Dr. Lesley J. Thomas, and production editor Ms. Lucille Murby. Finally, the

authors would like to thank their students in coding theory courses whose questions and

comments helped refine the text. In particular Jon Lark Kim at the University of Illinois at

Chicago and Robyn Canning at Loyola University of Chicago were most helpful.

We have taken great care to read and reread the text, check the examples, and work the

exercises in an attempt to eliminate errors. As with all texts, errors are still likely to exist.

The authors welcome corrections to any that the readers find. We can be reached at our

e-mail addresses below.

**W. Cary Huffman**

wch@math.luc.edu

**Vera Pless**

pless@math.uic.edu

February 1, 2003

Preface page xiii

**1 Basic concepts of linear codes**1

1.1 Three fields 2

1.2 Linear codes, generator and parity check matrices 3

1.3 Dual codes 5

1.4 Weights and distances 7

1.5 New codes from old 13

1.5.1 Puncturing codes 13

1.5.2 Extending codes 14

1.5.3 Shortening codes 16

1.5.4 Direct sums 18

1.5.5 The (u | u + v) construction 18

1.6 Permutation equivalent codes 19

1.7More general equivalence of codes 23

1.8 Hamming codes 29

1.9 The Golay codes 31

1.9.1 The binary Golay codes 31

1.9.2 The ternary Golay codes 32

1.10 Reed–Muller codes 33

1.11 Encoding, decoding, and Shannon’s Theorem 36

1.11.1 Encoding 37

1.11.2 Decoding and Shannon’s Theorem 39

1.12 Sphere Packing Bound, covering radius, and perfect codes 48

**2 Bounds on the size of codes**53

2.1 Aq (n, d) and Bq (n, d) 53

2.2 The Plotkin Upper Bound 58

2.3 The Johnson Upper Bounds 60

2.3.1 The Restricted Johnson Bound 61

2.3.2 The Unrestricted Johnson Bound 63

2.3.3 The Johnson Bound for Aq (n, d) 65

2.3.4 The Nordstrom–Robinson code 68

2.3.5 Nearly perfect binary codes 69

2.4 The Singleton Upper Bound and MDS codes 71

2.5 The Elias Upper Bound 72

2.6 The Linear Programming Upper Bound 75

2.7The Griesmer Upper Bound 80

2.8 The Gilbert Lower Bound 86

2.9 The Varshamov Lower Bound 87

2.10 Asymptotic bounds 88

2.10.1 Asymptotic Singleton Bound 89

2.10.2 Asymptotic Plotkin Bound 89

2.10.3 Asymptotic Hamming Bound 90

2.10.4 Asymptotic Elias Bound 92

2.10.5 The MRRW Bounds 93

2.10.6 Asymptotic Gilbert–Varshamov Bound 94

2.11 Lexicodes 95

**3 Finite fields**100

3.1 Introduction 100

3.2 Polynomials and the Euclidean Algorithm 101

3.3 Primitive elements 104

3.4 Constructing finite fields 106

3.5 Subfields 110

3.6 Field automorphisms 111

3.7Cyclotomic cosets and minimal polynomials 112

3.8 Trace and subfield subcodes 116

**4 Cyclic codes**121

4.1 Factoring xn − 1 122

4.2 Basic theory of cyclic codes 124

4.3 Idempotents and multipliers 132

4.4 Zeros of a cyclic code 141

4.5 Minimum distance of cyclic codes 151

4.6 Meggitt decoding of cyclic codes 158

4.7Af fine-invariant codes 162

**5 BCH and Reed–Solomon codes**168

5.1 BCH codes 168

5.2 Reed–Solomon codes 173

5.3 Generalized Reed–Solomon codes 175

5.4 Decoding BCH codes 178

5.4.1 The Peterson–Gorenstein–Zierler Decoding Algorithm 179

5.4.2 The Berlekamp–Massey Decoding Algorithm 186

5.4.3 The Sugiyama Decoding Algorithm 190

5.4.4 The Sudan–Guruswami Decoding Algorithm 195

5.5 Burst errors, concatenated codes, and interleaving 200

5.6 Coding for the compact disc 203

5.6.1 Encoding 204

5.6.2 Decoding 207

**6 Duadic codes**209

6.1 Definition and basic properties 209

6.2 A bit of number theory 217

6.3 Existence of duadic codes 220

6.4 Orthogonality of duadic codes 222

6.5 Weights in duadic codes 229

6.6 Quadratic residue codes 237

6.6.1 QR codes over fields of characteristic 2 238

6.6.2 QR codes over fields of characteristic 3 241

6.6.3 Extending QR codes 245

6.6.4 Automorphisms of extended QR codes 248

**7 Weight distributions**252

7.1 The MacWilliams equations 252

7.2 Equivalent formulations 255

7.3 A uniqueness result 259

7.4 MDS codes 262

7.5 Coset weight distributions 265

7.6 Weight distributions of punctured and shortened codes 271

7.7 Other weight enumerators 273

7.8 Constraints on weights 275

7.9 Weight preserving transformations 279

7.10 Generalized Hamming weights 282

**8 Designs**291

8.1 t-designs 291

8.2 Intersection numbers 295

8.3 Complementary, derived, and residual designs 298

8.4 The Assmus–Mattson Theorem 303

8.5 Codes from symmetric 2-designs 308

8.6 Projective planes 315

8.7Cyclic projective planes 321

8.8 The nonexistence of a projective plane of order 10 329

8.9 Hadamard matrices and designs 330

**9 Self-dual codes**338

9.1 The Gleason–Pierce–Ward Theorem 338

9.2 Gleason polynomials 340

9.3 Upper bounds 344

9.4 The Balance Principle and the shadow 351

9.5 Counting self-orthogonal codes 359

9.6 Mass formulas 365

9.7Classification 366

9.7.1 The Classification Algorithm 366

9.7.2 Gluing theory 370

9.8 Circulant constructions 376

9.9 Formally self-dual codes 378

9.10 Additive codes over F4 383

9.11 Proof of the Gleason–Pierce–Ward Theorem 389

9.12 Proofs of some counting formulas 393

**10 Some favorite self-dual codes**397

10.1 The binary Golay codes 397

10.1.1 Uniqueness of the binary Golay codes 397

10.1.2 Properties of binary Golay codes 401

10.2 Permutation decoding 402

10.3 The hexacode 405

10.3.1 Uniqueness of the hexacode 405

10.3.2 Properties of the hexacode 406

10.3.3 Decoding the Golay code with the hexacode 407

10.4 The ternary Golay codes 413

10.4.1 Uniqueness of the ternary Golay codes 413

10.4.2 Properties of ternary Golay codes 418

10.5 Symmetry codes 420

10.6 Lattices and self-dual codes 422

**11 Covering radius and cosets**432

11.1 Basics 432

11.2 The Norse Bound and Reed–Muller codes 435

11.3 Covering radius of BCH codes 439

11.4 Covering radius of self-dual codes 444

11.5 The length function 447

11.6 Covering radius of subcodes 454

11.7Ancestors, descendants, and orphans 459

**12 Codes over Z4**467

12.1 Basic theory of Z4-linear codes 467

12.2 Binary codes from Z4-linear codes 472

12.3 Cyclic codes over Z4 475

12.3.1 Factoring xn − 1 over Z4 475

12.3.2 The ring Rn = Z4[x]/(xn − 1) 480

12.3.3 Generating polynomials of cyclic codes over Z4 482

12.3.4 Generating idempotents of cyclic codes over Z4 485

12.4 Quadratic residue codes over Z4 488

12.4.1 Z4-quadratic residue codes: p ≡ −1 (mod 8) 490

12.4.2 Z4-quadratic residue codes: p ≡ 1 (mod 8) 492

12.4.3 Extending Z4-quadratic residue codes 492

12.5 Self-dual codes over Z4 495

12.5.1 Mass formulas 498

12.5.2 Self-dual cyclic codes 502

12.5.3 Lattices from self-dual codes over Z4 503

12.6 Galois rings 505

12.7K erdock codes 509

12.8 Preparata codes 515

**13 Codes from algebraic geometry**517

13.1 Affine space, projective space, and homogenization 517

13.2 Some classical codes 520

13.2.1 Generalized Reed–Solomon codes revisited 520

13.2.2 Classical Goppa codes 521

13.2.3 Generalized Reed–Solomon codes 524

13.3 Algebraic curves 526

13.4 Algebraic geometry codes 532

13.5 The Gilbert–Varshamov Bound revisited 541

13.5.1 Goppa codes meet the Gilbert–Varshamov Bound 541

13.5.2 Algebraic geometry codes exceed the Gilbert–Varshamov Bound 543

**14 Convolutional codes**546

14.1 Generator matrices and encoding 546

14.2 Viterbi decoding 551

14.2.1 State diagrams 551

14.2.2 Trellis diagrams 554

14.2.3 The Viterbi Algorithm 555

14.3 Canonical generator matrices 558

14.4 Free distance 562

14.5 Catastrophic encoders 568

**15 Soft decision and iterative decoding**573

15.1 Additive white Gaussian noise 573

15.2 A Soft Decision Viterbi Algorithm 580

15.3 The General Viterbi Algorithm 584

15.4 Two-way APP decoding 587

15.5 Message passing decoding 593

15.6 Low density parity check codes 598

15.7T urbo codes 602

15.8 Turbo decoding 607

15.9 Some space history 611

References 615

Symbol index 630

Subject index 633