As the demand for data reliability increases, coding for error control becomes increasingly important in data transmission systems and has become an integral part of almost all data communication system designs. In recent years, various trellis-based soft-decoding algorithms for linear block codes have been devised. New ideas developed in the study of trellis structure of block codes can be used for improving decoding and analyzing the trellis complexity of convolutional codes. These recent developments provide practicing communication engineers with more choices when designing error control systems. Trellises and Trellis-based Decoding Algorithms for Linear Block Codes combines trellises and trellis-based decoding algorithms for linear codes together in a simple and unified form. The approach is to explain the material in an easily understood manner with minimal mathematical rigor. Trellises and Trellis-based Decoding Algorithms for Linear Block Codes is intended for practicing communication engineers who want to have a fast grasp and understanding of the subject. Only material considered essential and useful for practical applications is included. This book can also be used as a text for advanced courses on the subject.

A code trellis is a graphical representation of a code, block or convolutional, in which every path represents a codeword (or a code sequence for a convolutional code). This representation makes it possible to implement Maximum Likelihood Decoding (MLD) of a code with reduced decoding complexity. The most well known trellis-based MLD algorithm is the Viterbi algorithm. The trellis representation was first introduced and used for convolutional codes [23]. This representation, together with the Viterbi decoding algorithm, has resulted in a wide range of applications of convolutional codes for error control in digital communications over the last two decades. There are two major reasons for this inactive period of research in this area. First, most coding theorists at that time believed that block codes did not have simple trellis structure like convolutional codes and maximum likelihood decoding of linear block codes using the Viterbi algorithm was practically impossible, except for very short block codes. Second, since almost all of the linear block codes are constructed algebraically or based on finite geometries, it was the belief of many coding theorists that algebraic decoding was the only way to decode these codes. These two reasons seriously hindered the development of efficient soft-decision decoding methods for linear block codes and their applications to error control in digital communications. This led to a general belief that block codes are inferior to convolutional codes and hence, that they were not useful. Chapter 2 gives a brief review of linear block codes. The goal is to provide the essential background material for the development of trellis structure and trellis-based decoding algorithms for linear block codes in the later chapters. Chapters 3 through 6 present the fundamental concepts, finite-state machine model, state space formulation, basic structural properties, state labeling, construction procedures, complexity, minimality, and sectionaliza...

Trellis and turbo coding are used to compress and clean communications signals to allow greater bandwidth and clarity Presents the basics, theory, and applications of these techniques with a focus on potential standard state-of-the art methods in the future Provides a classic basis for anyone who works in the area of digital communications A Wiley-IEEE Press Publication

This book introduces the theoretical elements at the basis of various classes of algorithms commonly employed in the physical layer (and, in part, in MAC layer) of wireless communications systems. It focuses on single user systems, so ignoring multiple access techniques. Moreover, emphasis is put on single-input single-output (SISO) systems, although some relevant topics about multiple-input multiple-output (MIMO) systems are also illustrated. Comprehensive wireless specific guide to algorithmic techniques Provides a detailed analysis of channel equalization and channel coding for wireless applications Unique conceptual approach focusing in single user systems Covers algebraic decoding, modulation techniques, channel coding and channel equalisation

This book constitutes the refereed postworkshop proceedings of the Fourth Canadian Workshop on Information Theory, held in Lac Delage, Quebec, in May 1995. The book contains 18 revised full papers selected from 30 workshop presentations; also included are three invited contributions. The book is divided into sections on algebraic coding, cryptography and secure communications, decoding methods and techniques, coding and modulation for fading channels, and signal processing and pattern recognition.

Covering the full range of channel codes from the most conventional through to the most advanced, the second edition of Turbo Coding, Turbo Equalisation and Space-Time Coding is a self-contained reference on channel coding for wireless channels. The book commences with a historical perspective on the topic, which leads to two basic component codes, convolutional and block codes. It then moves on to turbo codes which exploit iterative decoding by using algorithms, such as the Maximum-A-Posteriori (MAP), Log-MAP and Soft Output Viterbi Algorithm (SOVA), comparing their performance. It also compares Trellis Coded Modulation (TCM), Turbo Trellis Coded Modulation (TTCM), Bit-Interleaved Coded Modulation (BICM) and Iterative BICM (BICM-ID) under various channel conditions. The horizon of the content is then extended to incorporate topics which have found their way into diverse standard systems. These include space-time block and trellis codes, as well as other Multiple-Input Multiple-Output (MIMO) schemes and near-instantaneously Adaptive Quadrature Amplitude Modulation (AQAM). The book also elaborates on turbo equalisation by providing a detailed portrayal of recent advances in partial response modulation schemes using diverse channel codes. A radically new aspect for this second edition is the discussion of multi-level coding and sphere-packing schemes, Extrinsic Information Transfer (EXIT) charts, as well as an introduction to the family of Generalized Low Density Parity Check codes. This new edition includes recent advances in near-capacity turbo-transceivers as well as new sections on multi-level coding schemes and of Generalized Low Density Parity Check codes Comparatively studies diverse channel coded and turbo detected systems to give all-inclusive information for researchers, engineers and students Details EXIT-chart based irregular transceiver designs Uses rich performance comparisons as well as diverse near-capacity design examples

For long linear block codes, maximum likelihood decoding based on full code trellises would be very hard to implement if not impossible. In this case, we may wish to trade error performance for the reduction in decoding complexity. Sub-optimum soft-decision decoding of a linear block code based on a low-weight sub-trellis can be devised to provide an effective trade-off between error performance and decoding complexity. This chapter presents such a suboptimal decoding algorithm for linear block codes. This decoding algorithm is iterative in nature and based on an optimality test. It has the following important features: (1) a simple method to generate a sequence of candidate code-words, one at a time, for test; (2) a sufficient condition for testing a candidate code-word for optimality; and (3) a low-weight sub-trellis search for finding the most likely (ML) code-word. Lin, Shu and Fossorier, Marc Goddard Space Flight Center NAG5-931; NAG5-2938...

This book is offers a comprehensive overview of information theory and error control coding, using a different approach then in existed literature. The chapters are organized according to the Shannon system model, where one block affects the others. A relatively brief theoretical introduction is provided at the beginning of every chapter, including a few additional examples and explanations, but without any proofs. And a short overview of some aspects of abstract algebra is given at the end of the corresponding chapters. The characteristic complex examples with a lot of illustrations and tables are chosen to provide detailed insights into the nature of the problem. Some limiting cases are presented to illustrate the connections with the theoretical bounds. The numerical values are carefully selected to provide in-depth explanations of the described algorithms. Although the examples in the different chapters can be considered separately, they are mutually connected and the conclusions for one considered problem relate to the others in the book.

For long linear block codes, maximum likelihood decoding based on full code trellises would be very hard to implement if not impossible. In this case, we may wish to trade error performance for the reduction in decoding complexity. Sub-optimum soft-decision decoding of a linear block code based on a low-weight sub-trellis can be devised to provide an effective trade-off between error performance and decoding complexity. This chapter presents such a suboptimal decoding algorithm for linear block codes. This decoding algorithm is iterative in nature and based on an optimality test. It has the following important features: (1) a simple method to generate a sequence of candidate code-words, one at a time, for test; (2) a sufficient condition for testing a candidate code-word for optimality; and (3) a low-weight sub-trellis search for finding the most likely (ML) code-word. Lin, Shu and Fossorier, Marc Goddard Space Flight Center NAG5-931; NAG5-2938

The AAECC Symposia Series was started in 1983 by Alain Poli (Toulouse), who, together with R. Desq, D. Lazard, and P. Camion, organized the ?rst conference. Originally the acronym AAECC meant “Applied Algebra and Error-Correcting Codes”. Over the years its meaning has shifted to “Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes”, re?ecting the growing importance of complexity in both decoding algorithms and computational algebra. AAECC aims to encourage cross-fertilization between algebraic methods and their applications in computing and communications. The algebraic orientation is towards ?nite ?elds, complexity, polynomials, and graphs. The applications orientation is towards both theoretical and practical error-correction coding, and, since AAECC 13 (Hawaii, 1999), towards cryptography. AAECC was the ?rst symposium with papers connecting Gr ̈obner bases with E-C codes. The balance between theoretical and practical is intended to shift regularly; at AAECC-14 the focus was on the theoretical side. The main subjects covered were: – Codes: iterative decoding, decoding methods, block codes, code construction. – Codes and algebra: algebraic curves, Gr ̈obner bases, and AG codes. – Algebra: rings and ?elds, polynomials. – Codes and combinatorics: graphs and matrices, designs, arithmetic. – Cryptography. – Computational algebra: algebraic algorithms. – Sequences for communications.