Fundamentals of Error-Correcting Codes

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

ISBN: 9780521782807 | 0521782805
Cover: Hardcover
Copyright: 8/11/2003

eBook

Available Instantly

Online: 180 Days

Downloadable: 180 Days

*To support the delivery of the digital material to you, a digital delivery fee of $3.99 will be charged on each digital item.

$96.96*

Fundamentals of Error Correcting Codes is an in-depth introduction to coding theory from both an engineering and mathematical viewpoint. It reviews classical topics, and gives much coverage of recent techniques which could previously only be found in specialist 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.

Preface

xiii

1 Basic concepts of linear codes

(52)

1.1 Three fields

(1)

1.2 Linear codes, generator and parity check matrices

(2)

1.3 Dual codes

(2)

1.4 Weights and distances

(6)

1.5 New codes from old

(6)

1.5.1 Puncturing codes

(1)

1.5.2 Extending codes

(2)

1.5.3 Shortening codes

(2)

1.5.4 Direct sums

(1)

1.5.5 The (u | u + v) construction

(1)

1.6 Permutation equivalent codes

(4)

1.7 More general equivalence of codes

(6)

1.8 Hamming codes

(2)

1.9 The Golay codes

(2)

1.9.1 The binary Golay codes

(1)

1.9.2 The ternary Golay codes

(1)

1.10 Reed-Muller codes

(3)

1.11 Encoding, decoding, and Shannon's Theorem

(12)

1.11.1 Encoding

(2)

1.11.2 Decoding and Shannon's Theorem

(9)

1.12 Sphere Packing Bound, covering radius, and perfect codes

(5)

2 Bounds on the size of codes

(47)

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

(5)

2.2 The Plotkin Upper Bound

(2)

2.3 The Johnson Upper Bounds

(11)

2.3.1 The Restricted Johnson Bound

(2)

2.3.2 The Unrestricted Johnson Bound

(2)

2.3.3 The Johnson Bound for Aq(n,d)

(3)

2.3.4 The Nordstrom-Robinson code

(1)

2.3.5 Nearly perfect binary codes

(2)

2.4 The Singleton Upper Bound and MDS codes

(1)

2.5 The Elias Upper Bound

(3)

2.6 The Linear Programming Upper Bound

(5)

2.7 The Griesmer Upper Bound

(6)

2.8 The Gilbert Lower Bound

(1)

2.9 The Varshamov Lower Bound

(1)

2.10 Asymptotic bounds

(7)

2.10.1 Asymptotic Singleton Bound

(1)

2.10.2 Asymptotic Plotkin Bound

(1)

2.10.3 Asymptotic Hamming Bound

(2)

2.10.4 Asymptotic Elias Bound

(1)

2.10.5 The MRRW Bounds

(1)

2.10.6 Asymptotic Gilbert-Varshamov Bound

(1)

2.11 Lexicodes

(5)

3 Finite fields

100

(21)

3.1 Introduction

100

(1)

3.2 Polynomials and the Euclidean Algorithm

101

(3)

3.3 Primitive elements

104

(2)

3.4 Constructing finite fields

106

(4)

3.5 Subfields

110

(1)

3.6 Field automorphisms

111

(1)

3.7 Cyclotomic cosets and minimal polynomials

112

(4)

3.8 Trace and subfield subcodes

116

(5)

4 Cyclic codes

121

(47)

4.1 Factoring xn -1

122

(2)

4.2 Basic theory of cyclic codes

124

(8)

4.3 Idempotents and multipliers

132

(9)

4.4 Zeros of a cyclic code

141

(10)

4.5 Minimum distance of cyclic codes

151

(7)

4.6 Meggitt decoding of cyclic codes

158

(4)

4.7 Affine-invariant codes

162

(6)

5 BCH and Reed-Solomon codes

168

(41)

5.1 BCH codes

168

(5)

5.2 Reed-Solomon codes

173

(2)

5.3 Generalized Reed-Solomon codes

175

(3)

5.4 Decoding BCH codes

178

(22)

5.4.1 The Peterson-Gorenstein-Zierler Decoding Algorithm

179

(7)

5.4.2 The Berlekamp-Massey Decoding Algorithm

186

(4)

5.4.3 The Sugiyama Decoding Algorithm

190

(5)

5.4.4 The Sudan-Guruswami Decoding Algorithm

195

(5)

5.5 Burst errors, concatenated codes, and interleaving

200

(3)

5.6 Coding for the compact disc

203

(6)

5.6.1 Encoding

204

(3)

5.6.2 Decoding

207

(2)

6 Duadic codes

209

(43)

6.1 Definition and basic properties

209

(8)

6.2 A bit of number theory

217

(3)

6.3 Existence of duadic codes

220

(2)

6.4 Orthogonality of duadic codes

222

(7)

6.5 Weights in duadic codes

229

(8)

6.6 Quadratic residue codes

237

(15)

6.6.1 QR codes over fields of characteristic 2

238

(3)

6.6.2 QR codes over fields of characteristic 3

241

(4)

6.6.3 Extending QR codes

245

(3)

6.6.4 Automorphisms of extended QR codes

248

(4)

7 Weight distributions

252

(39)

7.1 The MacWilliams equations

252

(3)

7.2 Equivalent formulations

255

(4)

7.3 A uniqueness result

259

(3)

7.4 MDS codes

262

(3)

7.5 Coset weight distributions

265

(6)

7.6 Weight distributions of punctured and shortened codes

271

(2)

7.7 Other weight enumerators

273

(2)

7.8 Constraints on weights

275

(4)

7.9 Weight preserving transformations

279

(3)

7.10 Generalized Hamming weights

282

(9)

8 Designs

291

(47)

8.1 t-designs

291

(4)

8.2 Intersection numbers

295

(3)

8.3 Complementary, derived, and residual designs

298

(5)

8.4 The Assmus-Mattson Theorem

303

(5)

8.5 Codes from symmetric 2-designs

308

(7)

8.6 Projective planes

315

(6)

8.7 Cyclic projective planes

321

(8)

8.8 The nonexistence of a projective plane of order 10

329

(1)

8.9 Hadamard matrices and designs

330

(8)

9 Self-dual codes

338

(59)

9.1 The Gleason-Pierce-Ward Theorem

338

(2)

9.2 Gleason polynomials

340

(4)

9.3 Upper bounds

344

(7)

9.4 The Balance Principle and the shadow

351

(8)

9.5 Counting self-orthogonal codes

359

(6)

9.6 Mass formulas

365

(1)

9.7 Classification

366

(10)

9.7.1 The Classification Algorithm

366

(4)

9.7.2 Gluing theory

370

(6)

9.8 Circulant constructions

376

(2)

9.9 Formally self-dual codes

378

(5)

9.10 Additive codes over F4

383

(6)

9.11 Proof of the Gleason-Pierce-Ward Theorem

389

(4)

9.12 Proofs of some counting formulas

393

(4)

10 Some favorite self-dual codes

397

(35)

10.1 The binary Golay codes

397

(5)

10.1.1 Uniqueness of the binary Golay codes

397

(4)

10.1.2 Properties of binary Golay codes

401

(1)

10.2 Permutation decoding

402

(3)

10.3 The hexacode

405

(8)

10.3.1 Uniqueness of the hexacode

405

(1)

10.3.2 Properties of the hexacode

406

(1)

10.3.3 Decoding the Golay code with the hexacode

407

(6)

10.4 The ternary Golay codes

413

(7)

10.4.1 Uniqueness of the ternary Golay codes

413

(5)

10.4.2 Properties of ternary Golay codes

418

(2)

10.5 Symmetry codes

420

(2)

10.6 Lattices and self-dual codes

422

(10)

11 Covering radius and cosets

432

(35)

11.1 Basics

432

(3)

11.2 The Norse Bound and Reed-Muller codes

435

(4)

11.3 Covering radius of BCH codes

439

(5)

11.4 Covering radius of self-dual codes

444

(3)

11.5 The length function

447

(7)

11.6 Covering radius of subcodes

454

(5)

11.7 Ancestors, descendants, and orphans

459

(8)

12 Codes over Z4

467

(50)

12.1 Basic theory of Z4-linear codes

467

(5)

12.2 Binary codes from Z4-linear codes

472

(3)

12.3 Cyclic codes over Z4

475

(13)

12.3.1 Factoring xn -1 over Z4

475

(5)

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

480

(2)

12.3.3 Generating polynomials of cyclic codes over Z4

482

(3)

12.3.4 Generating idempotents of cyclic codes over Z4

485

(3)

12.4 Quadratic residue codes over Z4

488

(7)

12.4.1 Z4-quadratic residue codes: p = -1 (mod 8)

490

(2)

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

492

(1)

12.4.3 Extending Z4-quadratic residue codes

492

(3)

12.5 Self-dual codes over Z4

495

(10)

12.5.1 Mass formulas

498

(4)

12.5.2 Self dual cyclic codes

502

(1)

12.5.3 Lattices from self dual codes over Z4

503

(2)

12.6 Galois rings

505

(4)

12.7 Kerdock codes

509

(6)

12.8 Preparata codes

515

(2)

13 Codes from algebraic geometry

517

(29)

13.1 Affine space, projective space, and homogenization

517

(3)

13.2 Some classical codes

520

(6)

13.2.1 Generalized Reed-Solomon codes revisited

520

(1)

13.2.2 Classical Goppa codes

521

(3)

13.2.3 Generalized Reed-Solomon codes

524

(2)

13.3 Algebraic curves

526

(6)

13.4 Algebraic geometry codes

532

(9)

13.5 The Gilbert-Varshamov Bound revisited

541

(5)

13.5.1 Goppa codes meet the Gilbert-Varshamov Bound

541

(2)

13.5.2 Algebraic geometry codes exceed the Gilbert-Varshamov Bound

543

(3)

14 Convolutional codes

546

(27)

14.1 Generator matrices and encoding

546

(5)

14.2 Viterbi decoding

551

(7)

14.2.1 State diagrams

551

(3)

14.2.2 Trellis diagrams

554

(1)

14.2.3 The Viterbi Algorithm

555

(3)

14.3 Canonical generator matrices

558

(4)

14.4 Free distance

562

(6)

14.5 Catastrophic encoders

568

(5)

15 Soft decision and iterative decoding

573

(42)

15.1 Additive white Gaussian noise

573

(7)

15.2 A Soft Decision Viterbi Algorithm

580

(4)

15.3 The General Viterbi Algorithm

584

(3)

15.4 Two-way APP decoding

587

(6)

15.5 Message passing decoding

593

(5)

15.6 Low density parity check codes

598

(4)

15.7 Turbo codes

602

(5)

15.8 Turbo decoding

607

(4)

15.9 Some space history

611

(4)

References

615

(15)

Symbol index

630

(3)

Subject index

633

Please wait while the item is added to your bag...

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Fundamentals of Error-Correcting Codes

Summary

Table of Contents

Supplemental Materials

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Fundamentals of Error-Correcting Codes

Summary

Table of Contents

Supplemental Materials

Digital License