×

Introduction to coding theory. (English) Zbl 1092.94001

Cambridge: Cambridge University Press (ISBN 0-521-84504-1/hbk). xi, 566 p. (2006).
The textbook under review provides an introduction to error-correcting codes at the senior undergraduate or graduate level for students of computer science, electrical engineering, and mathematics with prior knowledge in probability, linear algebra, abstract algebra, and discrete mathematics. The author finds a nice balance between mathematical rigor, practical applications and computational aspects, making the book most suitable for its intended audience. A nice feature is the inclusion of codes used in spatial communication applications (e.g. binary BCH codes) as well as codes used in modern temporal communication applications (e.g. generalized Reed-Solomon (GRS) codes).
The book begins with an introductory chapter that provides a setting for the subsequent material. Communication systems, channel coding, block codes, decoding, and levels of error handling are all briefly discussed. After a basic treatment of linear codes (encoding, parity-check matrices, decoding) in Chapter 2, the necessary theory of finite fields needed for the next three chapters (including prime fields, polynomials, extension fields, roots of polynomials, primitive elements, field characteristic, and splitting fields) is developed in Chapter 3.
The fourth chapter deals with bounds on the parameters of codes. Not only are the usual topics of the Singleton bound and the sphere-packing bound included, but also information theoretic bounds (Shannon Coding Theorem, Converse Coding Theorem) are presented. RS codes are the focal point of Chapter 5. Interestingly, the author defines these before BCH codes and even before cyclic codes. His motivation was to introduce the reader to families of codes that cover a wide range of minimal distances as early as possible and to provide a clearer treatment of the decoding algorithms contained in Chapter 6 (syndrome computation, GRS decoding, Berlekamp-Massey algorithm).
The structure of finite fields (minimal polynomials, enumeration of irreducible polynomials, isomorphisms of finite fields, primitive polynomials, cyclotomic cosets) is presented in Chapter 7. Chapter 8 deals with cyclic codes and BCH codes, and would perhaps mark the end of a one-semester course.
A second-semester course could then consist of the following topics (Chapters 9–14): List decoding of RS codes (including the Sudan and the Guruswami-Sudan algorithm, list decoding of alternant codes, and bounds on the decoding radius), Codes in the Lee metric (Lee-metric alternant codes, GRS codes, and their decoding, Berlekamp codes, bounds), MDS codes (GRS codes and their extensions, bounds on the length of linear MDS codes, GRS codes and the MDS conjecture, uniqueness of some MDS codes), concatenated codes (decoding, the Zyablov bound, Justesen codes, concatenated codes that attain capacity), graph codes (expanders from codes, Ramanujan graphs, codes from expanders, iterative decoding of graph codes, graph codes in concantenated schemes), and trellis and convolutional codes (decoding trellis codes, linear finite-state machines, encoding/decoding convolutional codes, non-catastrophic generator matrices).
The reader will find many well-chosen examples throughout the book and will be challenged by over 300 exercises, many of which have hints. Some of the exercises develop concepts that are not contained within the main body of the text. For example, the very first problem of the book, filling up more than an entire page of the text, introduces the AWGN channel and requires the reader to check the crossover probability of a memoryless binary symmetric channel.
Notes to the material can be found at the end of each chapter. The author provides useful references (405 in all) and discussions on computational aspects (algorithms and time complexity) within these notes. Overall, the book is an appealing option for use in an introductory coding theory course that combines issues in mathematics, computer science, and electrical engineering.

MSC:

94-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory
94B05 Linear codes (general theory)
94B35 Decoding
94B65 Bounds on codes
94B15 Cyclic codes
94B10 Convolutional codes
94B12 Combined modulation schemes (including trellis codes) in coding theory
PDF BibTeX XML Cite
Full Text: DOI