Error Control Coding (PRENTICE-HALL COMPUTER APPLICATIONS IN ELECTRICAL ENGINEERING SERIES) - Hardcover

Lin, Shu; Costello, Daniel J.

Hardcover

ISBN 10: 013283796X ISBN 13: 9780132837965

Publisher: Prentice Hall, 1983

Synopsis

Using a minimum of mathematics, this volume covers the fundamentals of coding and the applications of codes to the design of real error control systems.

About this title

From the Back Cover

This popular textbook on error control coding has been thoroughly revised and updated to include all the important new developments in the field over the past 20 years. Three major new topics in the theory and application of coding are highlighted in this second edition:

• trellis and block coded modulation to achieve bandwidth efficiency;
• practical soft-decision decoding methods for block codes;
• soft-input, soft-output iterative decoding techniques for block and convolutional codes.

A total of seven completely new chapters are devoted to these three topics.

• Chapter 9: Trellises for Linear Block Codes
• Chapter 10: Reliability-Based Soft-Decision Decoding Algorithms for Linear Block Codes
• Chapter 14: Trellis-Based Soft-Decision Decoding Algorithms for Linear Block Codes
• Chapter 16: Turbo Coding
• Chapter 17: Low-Density Parity Check Codes
• Chapter 18: Trellis Coded Modulation
• Chapter 19: Block Coded Modulation

Continuing with the style that made the first edition so successful, the authors present the essential aspects of complex material in an easily understood manner requiring only a minimum of mathematical background. Many examples and performance curves are included to help illustrate important concepts. Extensive sets of exercises and references are given at the end of each chapter. This makes the book well suited as a text for a first course in coding theory at either the beginning graduate or advanced undergraduate level. Various choices of topics can be included in one semester. Alternately, most of the book can be covered in a two-semester sequence. Because of its comprehensive coverage of the fundamental theory and practical application of error control coding systems and its many lists of optimum codes, the book is also ideal as a reference for practicing digital system designers.

Excerpt. © Reprinted by permission. All rights reserved.

This book owes its beginnings to the pioneering work of Claude Shannon in 1948 on reliable communication over noisy transmission channels. Shannon's central theme was that if the signaling rate of the system is less than the channel capacity, reliable communication can be achieved if one chooses proper encoding and decoding techniques. The design of good codes and of efficient decoding methods, initiated by Hamming, Golay, and others in the late 1940s, has since occupied the energies of many researchers. Much of this work is highly mathematical in nature, and a thorough understanding requires an extensive background in modern algebra and probability theory. This requirement has impeded many engineers and computer scientists who are interested in applying these techniques to practical systems. One of the purposes of this book is to present the essentials of this highly complex material in such a manner that it can be understood and applied with only a minimum of mathematical background.

Coding research in the 1950s and 1960s was devoted primarily to developing the theory of efficient encoders and decoders. In 1970 the first author published a book entitled An Introduction to Error-Correcting Codes, which presented the fundamentals of the previous two decades of work covering both block and convolutional codes. The approach was to explain the material in an easily understood manner, with a minimum of mathematical rigor. Then, in 1983, the authors published the first edition of this book. The approach again stressed the fundamentals of coding. In addition, new material on many of the practical applications of coding developed during the 1970s was introduced. Other major additions included a comprehensive treatment of the error-detecting capabilities of block codes and an emphasis on soft decoding methods for convolutional codes.

In the 1980s and 1990s, the coding field exploded with new theoretical developments, several of which have had significant practical consequences. Three of these new developments stand out in particular: the application of binary convolutional and block codes to expanded (nonbinary) modulation alphabets, the development of practical soft decoding methods for block codes, and the discovery of soft-input, soft-output iterative decoding techniques for block and convolutional codes. These new developments have revolutionized the way coding is applied to practical systems, affecting the design of high-speed data modems, digital mobile cellular telephony, satellite and space communications, and high-density data storage, to name just a few. A total of seven new chapters covering these topics have been added to this edition: two chapters on trellis- and block-coded modulation techniques, three chapters on soft decoding methods for block codes, and two chapters on turbo and low-density parity-check codes and iterative decoding.

Because of the significant amount of new material and the need to maintain an emphasis on coding fundamentals, it was not possible to include certain topics in this edition. For example, the new developments in algebraic geometry codes and erasure correcting codes are not covered. Also, although the codes developed in the book can be applied to data storage systems, the specific peculiarities of the storage channel are not directly addressed. Similarly, it was not possible to give a comprehensive treatment of coding for fading channels. In addition to the new chapters noted, all the chapters in the first edition have been thoroughly revised and updated in the second edition. A brief description of each chapter follows, highlighting changes from the first edition.

Chapter 1 presents an overview of coding for error control in data transmission and storage systems. A brief discussion of modulation and demodulation serves to place coding in the context of a complete system. Two new sections, introducing the concepts of coded modulation, coding gain, and the Shannon limit, have been added. Chapter 2 develops those concepts from modern algebra that are necessary to understand the material in later chapters. The presentation is at a level that can be understood by students in the senior year as well as by practicing engineers and computer scientists.

Chapters 3 through 10 cover in detail the fundamentals of block codes. Linear block codes are presented in Chapter 3. Included is material on the error detection capability of linear codes. Several important classes of linear codes are introduced in Chapter 4. New material on Reed-Muller codes has been added to this chapter. The basic structure and properties of cyclic codes are presented in Chapter 5, and syndrome-based decoding methods are introduced. The important class of BCH codes is presented in detail in Chapter 6. A discussion of hardware and software implementation of BCH decoders is included, as well as the use of BCH codes for error detection. Chapter 7 includes an expanded coverage of Reed-Solomon codes. New material on the Euclidean algorithm and frequency-domain decoding has been added. Chapter 8 provides detailed coverage of majority-logic decodable codes, including the important classes of Euclidean and projective geometry codes. Chapters 9 and 10 are both completely new. Chapter 9 develops the theory of the trellis structure of block codes, laying the groundwork for the introduction of trellis-based soft decoding algorithms in Chapter 14. Chapter 10, written by Professor Marc Fossorier, presents comprehensive coverage of reliability-based soft decoding methods for block codes and includes an introduction to iterative decoding techniques.

Chapters 11 through 13 are devoted to the presentation of the fundamentals of convolutional codes. Convolutional codes are introduced in Chapter 11, with the encoder state diagram serving as the basis for studying code structure and distance properties. New material on feedback encoders and input-output weight enumerating functions has been added. Chapter 12 covers optimum decoding methods for convolutional codes, with an emphasis on the (maximum likelihood) Viterbi decoding algorithm for both hard and soft demodulator decisions. New material has been added on the soft-output Viterbi algorithm, the (maximum a posteriori probability) BCJR algorithm, and the code modification techniques of puncturing and tail-biting. A detailed performance analysis based on encoder weight enumerating functions is also included. Chapter 13 covers suboptimum decoding methods for convolutional codes, with an emphasis on sequential decoding, using both the ZJ (stack) and Fano algorithms, and majority-logic decoding. The analytically difficult problem of the computational performance of sequential decoding is discussed without including detailed proofs, and new material on soft-decision versions of sequential and majority-logic decoding has been added.

Chapter 14 extends the soft decoding methods introduced for convolutional codes in Chapter 12 to block codes. This completely new chapter makes extensive use of the block code trellis structures introduced in Chapter 9.

Chapters 15 through 19 cover the important advances in the field since the publication of the first edition. Chapter 15 discusses the important concepts of code concatenation, multistage decoding, and code decomposition. These topics lay the groundwork for the new coding techniques presented in the next four chapters. Chapters 16 through 19 are completely new. Chapter 16 introduces the area of parallel concatenation, or turbo coding, and its related iterative decoding techniques based on the BCJR algorithm presented in Chapter 12. Performance analysis based on the uniform interleaver technique and the EXIT chart concept is included. Chapter 17 presents a thorough coverage of low-density parity-check codes based on algebraic, random, and combinatoric construction methods. Several decoding methods are discussed, and a complete development of soft-decision belief propagation decoding is included. The area of coded modulation is covered in Chapters 18 and 19. The fundamentals of trellis-coded modulation are presented in Chapter 18. Sections on rotationally invariant codes and multidimensional signal sets are included. Block-coded modulation is covered in Chapter 19. The important concepts of multilevel modulation and multistage decoding are included.

The book concludes with three chapters on burst-error correction and automatic-repeat-request (ARQ) strategies. Chapters 20 and 21 cover methods for correcting the burst errors and combinations of burst and random errors commonly encountered on fading channels. Both block (Chapter 20) and convolutional (Chapter 21) burst-error-correcting codes are included. Chapter 22 is devoted to the ARQ error control schemes used on two-way communication channels. Both pure ARQ (error detection with retransmission) and hybrid ARQ (a combination of error correction and error detection with retransmission) are discussed.

Several additional features make the book useful both as a classroom text and as a comprehensive reference for engineers and computer scientists involved in the design of error control systems. Three appendices include the algebraic background used in the construction of most block codes. Many tables of the best known block and convolutional codes for various decoding methods are presented throughout the book. These tables can be used by system designers to select the best code for a given application. In this edition, a consistent octal notation has been adopted for the generator and parity-check polynomials that define the codes listed in these tables. Many examples of codes used in practical applications and computer simulated performance curves for specific coding systems are also included. A set of homework problems is given at the end of each chapter. Most of these problems are relatively straightforward applications of material covered in the text, although some more advanced problems are included. Instructors can obtain solutions to selected problems from the publisher. References are also given at the end of each chapter. Although no attempt was made to compile a complete bibliography on coding, the references listed serve to provide additional detail on topics covered in the book.

The book can be used as a text for an introductory course on coding at the senior or beginning graduate level or a more comprehensive full-year graduate course. It also can be used as a self-study guide for engineers and computer scientists in industry who want to learn the fundamentals of coding and how they can be applied to the design of error control systems.

As a text the book can be used as the basis for a two-semester sequence in coding theory, with Chapters 1-10 on the fundamentals of block codes covered in one semester and the remaining chapters on convolutional codes and advanced block code topics in a second semester. Another possibility is to cover Chapters 1-8 and 11-13, which include the fundamentals of both block and convolutional codes, in one semester, followed by a second semester devoted to advanced topics. Alternatively portions of the book can be covered in a one-semester course. A course on block codes comprise Chapters 1-7 plus selected topics from Chapters 8-10, 14-15, 17, 19-20, and 22, whereas Chapters 1, 11-13, 16, 18, and 21 provide a thorough coverage of convolutional codes.

We would like to express our sincere appreciation to Professor Marc Fossorier, who, in addition to writing Chapter 10, spent many long hours reading and rereading drafts of various chapters. We also wish to thank the many graduate students and postdoctoral associates who offered their comments and helped in the preparation of the book, including running computer simulations, drafting figures, compiling tables, and converting the manuscript to LaTeX format. These persons include Yu Kou, Cathy Liu, Rose Shao, Diana Stojanovic, Jun Xu, Lei Chen, Oscar Takeshita, Gil Shamir, Adrish Banerjee, Arvind Sridharan, Ching He, Wei Zhang, and Ali Pusane. In particular, Yu Kou, Cathy Liu, and Adrish Banerjee deserve special mention for overseeing the preparation of the final version of the manuscript.

We are grateful to the National Science Foundation and to the National Aeronautics and Space Administration for their continuing support of our research in the coding field. Without their assistance, our interest in coding could never have developed to the point of writing this book. We also thank the University of Hawaii, Manoa, the University of California, Davis, the University of Notre Dame, and the Humboldt Foundation of Germany for their support of our efforts in writing this book and for providing facilities.

Finally, we would like to give special thanks to our wives, children, and grandchildren for their continuing love and affection throughout this project.

Edition details

• Publisher: Prentice Hall
• Publication date: 1983
• ISBN 10: 013283796X
• ISBN 13: 9780132837965
• Binding: Hardcover
• Language: English
• Number of pages: 603