# Introduction to Coding Theory

Cambridge University Press, Feb 23, 2006 - Computers - 566 pages
Error-correcting codes constitute one of the key ingredients in achieving the high degree of reliability required in modern data transmission and storage systems. This book introduces the reader to the theoretical foundations of error-correcting codes, with an emphasis on Reed-Solomon codes and their derivative codes. After reviewing linear codes and finite fields, Ron Roth describes Reed-Solomon codes and various decoding algorithms. Cyclic codes are presented, as are MDS codes, graph codes, and codes in the Lee metric. Concatenated, trellis, and convolutional codes are also discussed in detail.

### What people are saying -Write a review

We haven't found any reviews in the usual places.

### Contents

 Introduction 1 12 Channel coding 3 13 Block codes 5 14 Decoding 7 15 Levels of error handling 11 Problems 17 Notes 22 Linear Codes 26
 List Decoding of ReedSolomon Codes 266 91 List decoding 267 92 Bivariate polynomials 268 93 GRS decoding through bivariate polynomials 269 94 Sudans algorithm 271 95 The GuruswamiSudan algorithm 276 96 List decoding of alternant codes 280 97 Finding linear bivariate factors 284

 22 Encoding of linear codes 28 23 Paritycheck matrix 29 24 Decoding of linear codes 32 Problems 36 Notes 47 Introduction to Finite Fields 50 32 Polynomials 51 33 Extension fields 56 34 Roots of polynomials 59 35 Primitive elements 60 36 Field characteristic 62 37 Splitting field 64 double errorcorrecting codes 66 Problems 70 Notes 90 Bounds on the Parameters of Codes 93 41 The Singleton bound 94 42 The spherepacking bound 95 43 The GilbertVarshamov bound 97 44 MacWilliams identities 99 45 Asymptotic bounds 104 46 Converse Coding Theorem 110 47 Coding Theorem 115 Problems 119 Notes 136 ReedSolomon and Related Codes 147 51 Generalized ReedSolomon codes 148 52 Conventional ReedSolomon codes 151 53 Encoding of RS codes 152 54 Concatenated codes 154 55 Alternant codes 157 56 BCH codes 162 Problems 163 Notes 177 Decoding of ReedSolomon Codes 183 62 Syndrome computation 184 63 Key equation of GRS decoding 185 64 Solving the key equation by Euclids algorithm 191 65 Finding the error values 194 66 Summary of the GRS decoding algorithm 195 67 The BerlekampMassey algorithm 197 Problems 204 Notes 215 Structure of Finite Fields 218 72 Enumeration of irreducible polynomials 224 73 Isomorphism of finite fields 227 75 Cyclotomic cosets 229 Problems 232 Notes 240 Cyclic Codes 242 82 Generator polynomial and check polynomial 244 83 Roots of a cyclic code 247 84 BCH codes as cyclic codes 250 85 The BCH bound 253 Problems 256 Notes 265
 98 Bounds on the decoding radius 289 Problems 291 Notes 295 Codes in the Lee Metric 298 102 Newtons identities 300 103 Leemetric alternant codes and GRS codes 302 104 Decoding alternant codes in the Lee metric 306 105 Decoding GRS codes in the Lee metric 312 106 Berlekamp codes 314 107 Bounds for codes in the Lee metric 316 Problems 321 Notes 327 MDS Codes 333 112 GRS codes and their extensions 335 113 Bounds on the length of linear MDS codes 338 114 GRS codes and the MDS conjecture 342 115 Uniqueness of certain MDS codes 347 Problems 351 Notes 361 Concatenated Codes 365 121 Definition revisited 366 122 Decoding of concatenated codes 367 123 The Zyablov bound 371 124 Justesen codes 374 125 Concatenated codes that attain capacity 378 Problems 381 Notes 392 Graph Codes 395 131 Basic concepts from graph theory 396 132 Regular graphs 401 133 Graph expansion 402 134 Expanders from codes 406 135 Ramanujan graphs 409 136 Codes from expanders 411 137 Iterative decoding of graph codes 414 138 Graph codes in concatenated schemes 420 Problems 426 Notes 445 Trellis and Convolutional Codes 452 141 Labeled directed graphs 453 142 Trellis codes 460 143 Decoding of trellis codes 466 144 Linear finitestate machines 471 145 Convolutional codes 477 146 Encoding of convolutional codes 479 147 Decoding of convolutional codes 485 148 Noncatastrophic generator matrices 495 Problems 501 Notes 518 Basics in Modern Algebra 521 Problems 522 Bibliography 527 List of Symbols 553 Index 559 Copyright

### Popular passages

Page 529 - Near Optimum Error Correcting Coding and Decoding: Turbo-Codes,
Page 533 - P. Delsarte, Four fundamental parameters of a code and their combinatorial significance, Info.