Über die Autorin bzw. den Autor

Robert H. Morelos-Zaragoza received BSEE and MSEE degrees from the National Autonomous University of Mexico (UNAM) in 1985 and 1987 respectively, and a PhD in Electrical Engineering from the University of Hawaii at Manoa in 1992. He has held numerous research posts in Mexico and Japan. In 2002, Robert joined the Department of Electrical Engineering at San José State University, as an Associate Professor. His current research interests include error correcting coding (ECC/FEC), advanced digital communication receiver design, software-defined radio (SDR), space-time signal processing techniques and ultra-wideband (UWB) communication systems. Prof. Morelos-Zaragoza is a senior member of IEEE, and member of IEICE (Japan) and of Eta Kappa Nu.

Von der hinteren Coverseite

Building on the success of the first edition, which offered a practical introductory approach to the techniques of error concealment, this book, now fully revised and updated, provides a comprehensive treatment of the subject and includes a wealth of additional features. The Art of Error Correcting Coding, Second Edition explores intermediate and advanced level concepts as well as those which will appeal to the novice.

All key topics are discussed, including Reed-Solomon codes, Viterbi decoding, soft-output decoding algorithms, MAP, log-MAP and MAX-log-MAP. Reliability-based algorithms GMD and Chase are examined, as are turbo codes, both serially and parallel concatenated, as well as low-density parity-check (LDPC) codes and their iterative decoders.

• Features additional problems at the end of each chapter and an instructor’s solutions manual
• Updated companion website offers new C/C ++programs and MATLAB scripts, to help with the understanding and implementation of basic ECC techniques
• Easy to follow examples illustrate the fundamental concepts of error correcting codes
• Basic analysis tools are provided throughout to help in the assessment of the error performance block and convolutional codes of a particular error correcting coding (ECC) scheme for a selection of the basic channel models

This edition provides an essential resource to engineers, computer scientists and graduate students alike for understanding and applying ECC techniques in the transmission and storage of digital information.

Aus dem Klappentext

Building on the success of the first edition, which offered a practical introductory approach to the techniques of error concealment, this book, now fully revised and updated, provides a comprehensive treatment of the subject and includes a wealth of additional features. The Art of Error Correcting Coding, Second Edition explores intermediate and advanced level concepts as well as those which will appeal to the novice.

All key topics are discussed, including Reed-Solomon codes, Viterbi decoding, soft-output decoding algorithms, MAP, log-MAP and MAX-log-MAP.  Reliability-based algorithms GMD and Chase are examined, as are turbo codes, both serially and parallel concatenated, as well as low-density parity-check (LDPC) codes and their iterative decoders.

• Features additional problems at the end of each chapter and an instructor’s solutions manual
• Updated companion website offers new C/C ++programs and MATLAB scripts, to help with the understanding and implementation of basic ECC techniques
• Easy to follow examples illustrate the fundamental concepts of error correcting codes
• Basic analysis tools are provided throughout to help in the assessment of the error performance block and convolutional codes of a particular error correcting coding (ECC) scheme for a selection of the basic channel models

This edition provides an essential resource to engineers, computer scientists and graduate students alike for understanding and applying ECC techniques in the transmission and storage of digital information.

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

The Art of Error Correcting Coding

John Wiley & Sons

Chapter One

The history of error correcting coding (ECC) started with the introduction of the Hamming codes (Hamming 1974), at or about the same time as the seminal work of Shannon (1948). Shortly after, Golay codes were invented (Golay 1974). These two first classes of codes are optimal, and will be defined in a subsequent section.

Figure 1.1 shows the block diagram of a canonical digital communications/storage system. This is the famous Figure 1 in most books on the theory of ECC and digital communications (Benedetto and Biglieri 1999). The information source and destination will include any source coding scheme matched to the nature of the information. The ECC encoder takes as input the information symbols from the source and adds redundant symbols to it, so that most of the errors - introduced in the process of modulating a signal, transmitting it over a noisy medium and demodulating it - can be corrected (Massey 1984; McEliece 1977; Moon 2005).

Usually, the channel is assumed to be such that samples of an additive noise process are added to the modulated symbols (in their equivalent complex baseband representation). The noise samples are assumed to be independent from the source symbols. This model is relatively easy to track mathematically and includes additive white Gaussian noise (AWGN) channels, flat Rayleigh fading channels, and binary symmetric channels (BSC). The case of frequency-selective channels can also be included, as techniques such as spread-spectrum and multicarrier modulation (MCM) effectively transform them into either AWGN channels or flat Rayleigh fading channels.

At the receiver end, the ECC decoder utilizes the redundant symbols and their relationship with the information symbols in order to correct channel errors. In the case of error detection, the ECC decoder can be best thought of as a reencoder of the received information, followed by a check that the redundant symbols generated are the same as those received.

In classical ECC theory, the combination of modulation, noisy medium and demodulation was modeled as a discrete memoryless channel with input [bar.v] and output [bar.r]. An example of this is binary transmission over an AWGN channel, which is modeled as a BSC. This is illustrated in Figure 1.2. The BSC has a probability of channel error p - or transition probability - equal to the probability of a bit error for binary signaling over an AWGN channel,

p = Q ([square root of 2[E.sub.b]/[N.sub.0]]), (1.1)

where [E.sub.b]/[N.sub.0] is the energy-per-bit-to-noise ratio - also referred to as the bit signal-to-noise ratio (SNR) or SNR per bit - and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.2)

is the Gaussian Q-function. In terms of the complementary error function, the Q-function can be written as

Q(x) = 1/2 erfc (x/[square root of 2]). (1.3)

Equation (1.2) is useful in analytical derivations and Equation (1.3) is used in the computation with C programs or Matlab scripts of performance bounds and approximations.

Massey (1974) suggested considering ECC and modulation as a single entity, known in modern literature as coded modulation. This approach provides a higher efficiency and coding gain rather than the serial concatenation of ECC and modulation, by joint design of codes and signal constellations. Several methods of combining coding and modulation are covered in this book, including the following: trellis-coded modulation (TCM) (Ungerboeck 1982) and multilevel coded modulation (MCM) (Imai and Hirakawa 1977). In a coded modulation system, the (soft-decision) channel outputs are directly processed by the decoder. In contrast, in a classical ECC system, the hard-decision bits from the demodulator are fed to a binary decoder.

Codes can be combined in several ways. An example of serial concatenation (that is, concatenation in the classical sense) is the following. For years, the most popular concatenated ECC scheme has been the combination of an outer Reed-Solomon (RS) code, through intermediate interleaving, and an inner binary convolutional code. This scheme has been used in numerous applications, ranging from space communications to digital broadcasting of high definition television. The basic idea is that the soft-decision decoder of the convolutional code produces bursts of errors that can be broken into smaller pieces by the deinterleaving process and handled effectively by the RS decoder. RS codes are nonbinary codes that work with symbols composed of several bits, and can deal with multiple bursts of errors. Serial concatenation has the advantage that it requires two separate decoders, one for the inner code and one for the outer code, instead of a single but very complex decoder for the overall code.

This book examines these types of ECC systems. First, basic code constructions and their decoding algorithms, in the Hamming space (that is, dealing with bits), are presented. In the second part of the book, important soft-decision decoding (SDD) algorithms for binary transmission are introduced. These algorithms work over the Euclidean space and achieve a reduction in the required transmitted power per bit of at least 2 dB, compared with Hamming-space (hard-decision) decoders. Several kinds of soft-decision decoders are considered, with attention given to their algorithmic aspects (the "how" they work), rather than to their theoretical aspects (the 'why' they work). Finally, combinations of codes and interleaving for iterative decoding and of coding and modulation for bandwidth-efficient transmission are the topic of the last part of the book.

1.1 Error correcting coding: Basic concepts

All error correcting codes are based on the same basic principle: redundancy is added to information in order to correct any errors that may occur in the process of transmission or storage. In a basic (and practical) form, redundant symbols are appended to information symbols to obtain a coded sequence or code word. For the purpose of illustration, a code word obtained by encoding with a block code is shown in Figure 1.3. Such an encoding is said to be systematic. Systematic encoding means that the information symbols always appear in the first (leftmost) k positions of a code word. The remaining (rightmost) n - k symbols in a code word are a function of the information symbols, and provide redundancy that can be used for error correction and/or detection purposes. The set of all code sequences is called an error correcting code, and will henceforth be denoted by ITLITL.

1.1.1 Block codes and convolutional codes

According to the manner in which redundancy is added to messages, ECC can be divided into two classes: block and convolutional. Both types of coding schemes have found practical applications. Historically, convolutional codes have been preferred, apparently because of the availability of the soft-decision Viterbi decoding algorithm and the belief over many years that block codes could not be efficiently decoded with soft-decisions. However, recent developments in the theory and design of SDD algorithms for linear block codes have helped to dispel this belief. Moreover, the best ECC known to date remain block codes (long irregular low-density parity-check (LDPC) codes).

...