In 1948, Claude E Shannon laid the foundation for modern digital communications with his groundbreaking paper "A Mathematical Theory of Communications" (Ref 1). He determined that every communication channel has a maximum capacity for reliable information transmission. Transmit at a rate below that capacity with a "good" data code, and you can confidently achieve reliable communication. Conversely, transmit at a rate above that capacity and, even with the best code, your communications will be unreliable. Thus, modern digital communications began with a race to find "good" codes, and the error-correcting code (ECC) was born (Ref 2).

Shannon's theory seemed to promise that almost any code chosen at random would meet the definition of "good." Researchers quickly discovered, however, this wasn't the case. Soon the now famous saying was coined, "Almost every code is good -- except for the ones we know." Yet with conviction akin to religious fervor, researchers kept searching. Some suspected that forces larger than Shannon were at work, and they pointed to other testimony that the digital communications age was destined to be: "And in all your communications, let them be `Yeah, yeah' and `Nay, nay'" (Matthew 5:37).

Fifty years after Shannon published his theory, researchers are now closing in on their Holy Grail. Perhaps it was fate that led another Claude (and his colleagues) to make the biggest breakthrough in recent ECC history. In 1993, Claude Berrou, Alain Glavieux and Punja Thitimajshima published a now famous paper "Near Shannon limit error-correcting coding and decoding: Turbo Codes" (Ref 3). The Turbo Codes they introduced perform to within 0.7 dB of Shannon's limit for an additive white Gaussian noise (AWGN) channel, as opposed to 2 dB or more for other state-of-the-art techniques of similar complexity. Such a large improvement is remarkable and was initially greeted with considerable skepticism. That skepticism has vanished, however, as the results have been independently verified and even improved upon in several ways.

So, if Turbo Codes are so wonderful, why haven't you heard of them? Or if you have, why haven't you seen a Turbo Coding chip in your lab? In a nutshell: you will -- but it might take a few years. And even if Turbo Codes aren't the end-all in ECC, they've lead to new insights bound to impact many applications, primarily those that have traditionally used ECC and others as well. In the meantime, you have a chance to learn what makes them tick, what they can and can't do and when/where you might use them. To help facilitate this, I'm devoting several articles to Turbo Codes.

At first glance, Turbo Codes can be intimidating. Understanding them requires some grasp of complicated ECC fundamentals. Thus I'll start by reviewing the prerequisites, focusing on ECC terminology and when/why ECC is used (Ref 4). The goal is to provide enough background so that you can understand, at least at a high level, the building blocks that make up Turbo Codes. Subsequent installments will delve more deeply into those building blocks and describe the codes and their application. Along the way, we'll cover a variety of issues whose importance extends beyond Turbo Codes. Although we can't cover each of them in great detail, this series will describe their general importance along with their specific relevance to Turbo Codes.

Error control, correction

Let's begin by examining the general need and use of error-correcting codes. Fig 1a shows the components in a typical digital communication system.

Fig 1 -- A digital communications system (a) consists of digital source/sink, encoder/decoder and modulator/ demodulator pairs. To select appropriate components, consider the impact of channel type, noise and interference. To focus on channel coding, consider a simplified comm system (b) that provides digital data to the channel encoder and delivers encoded data imperfectly to the channel decoder.

The transmitter sends its input signal to a source encoder, which attempts to minimize the amount of data to be transmitted. For example, suppose it passes a video signal through an A/D and then feeds the samples into an MPEG source encoder, which compresses the data. At the receiver an MPEG decoder reverses the compression and converts the data back to its original form. If you connect an MPEG encoder directly to an MPEG decoder, the only loss of video fidelity arises due to the compression process. However, in most any other application the act of transmitting the source-encoded data introduces errors at the receiver. Obviously, you want to remove as many errors as possible from the received data before introducing it to the source decoder -- and in the case of MPEG, the error rate must be very low (less than 1 part in 10⁷ ).

The job of controlling errors falls upon the channel encoder, which can do its job in many ways (Ref 4). For example, it could append a cyclic redundancy check (CRC) field to each data packet. If the receiver detects an error, it could send a request for retransmission over a reverse channel. This type of bilateral exchange is called automatic repeat request (ARQ). Its chief advantage is that, when both forward- and reverse-channel communications are reliable, ARQ can minimize the amount of wasted effort/bandwidth needed to control errors. In many cases, though, reliable reverse channels are unavailable, expensive or a system can't tolerate the delay imposed by ARQ schemes. In such cases, error-correction methods must be based on the forward channel alone.

Forward error correction (FEC) adds redundancy to the datastream at the transmitter so the receiver can both detect and correct errors unilaterally. The simplest scheme repeats each data bit N times during transmission, and the receiver decodes the message by taking a majority vote for each bit. It seems ironic that, after the source coder goes to great lengths to remove redundancy, the channel coder adds so much redundancy back in. But not all redundancy is equal. This repeat-N scheme is simple but very inefficient. When FEC is implemented more carefully, the resulting redundancy can lead to tremendous system benefits, primarily power savings and higher reliability.

The classic tradeoff to consider before applying FEC is transmit power vs bandwidth. If you can reduce the error rate sufficiently by simply increasing transmit power, you might not need FEC at all. More power means an increased S/N ratio, which reduces the apparent error rate at the receiver. In many applications, such as mobile telephony, increased power also means reduced battery operating time or larger batteries, neither of which is acceptable to consumers. Engineers usually consider FEC in such power-limited cases in order to achieve higher reliability communications with the same amount of transmitted power.

Because FEC techniques add redundancy, however, they require expanded bandwidth to carry both the original information and the error-correcting redundancy. Because bandwidth can be a scarce commodity (regulated by the FCC and apportioned out during expensive auctions), you must use it carefully. For applications that are strictly bandwidth limited, FEC might be appropriate only if used in combination with a larger symbol alphabet, which adds complexity to the system but avoids bandwidth expansion. Telephone modems are an excellent example of a bandwidth-limited application that uses FEC in combination with large alphabets.

Turbo Code overview

Now let's focus on the channel coding/decoding blocks of Fig 1a and consider a simplified configuration as in Fig 1b. From the perspective of the channel coder, digital data appear at its input from some kind of digital data source, and the coder's output is accepted by a digital channel. This discussion overlooks details of the source and the channel. The channel decoder acts upon the possibly corrupted data and sends the result to a digital sink. During system testing, the sink compares received data with the originally transmitted data and determines an effective bit error rate (BER). Without the channel encoder/decoder, the characteristics of the channel determine the resulting "uncoded system" BER. Including FEC channel encoding/decoding reduces the BER to some extent, depending upon the type and effectiveness of the FEC.

Now let's consider the structure of a typical Turbo Code channel encoder (Fig 2a). It consists of two separate "constituent encoders" that operate in parallel. Both process the same input data, except that an interleaver scrambles the order of data input to Encoder #2. A multiplexer then combines the output of the two encoders into a single output stream.

Fig 2 -- A typical Turbo Code encoder (a) consists of two or more constituent RSC encoders. Each operates on the same input data but in a different order as specified by the interleaver. A multiplexer selectively combines the encoder outputs. The typical Turbo Code decoder (b) selectively demultiplexes the input stream and distributes parity-check information to each decoder. Interleavers reorder the data according to how it was encoded. Feedback from the last decoder allows multiple decoding iterations, which is a key to Turbo Code performance.

This type of encoder can be simple to implement, and even though more complex configurations are possible, this configuration produced the initial results that astounded the ECC community (Ref 3). The ingeniousness of Turbo Codes isn't readily apparent in the figure; instead, it lies in the appropriate selection of constituent encoders, interleaver and decoders. Later parts of this series will describe in detail the structure of both the encoder and decoder.

At the receiver, the Turbo Code decoder is significantly more complex than the encoder (Fig 2b). While the encoder processes the original datastream in parallel, the decoder processes its input serially in two stages. Decoder #1 produces its best estimate of the original uncoded data. The interleaver then shuffles this estimate in the same manner that the transmitter's interleaver shuffled the original data prior to Encoder #2. The shuffled estimate and additional redundancy information ("parity bits" generated at Encoder #2) then pass to Decoder #2. If Decoder #1 is successful, the number of errors entering Decoder #2 is smaller than the number of errors entering Decoder #1.

Decoder #2 processes the data and generates a refined estimate of the original data, which should contain even fewer errors. However, the receiver uses a deinterleaver to unshuffle the data back into its original order. If no further refinements are desired, the deinterleaver delivers the final output and passes it to the data sink (Fig 1b). If additional error reduction is desired, the receiver can feed the deinterleaver's output back to Decoder #1 and repeat the process any number of iterations. Of course, each iteration adds considerable delay and computational complexity, but it can also reduce errors significantly, especially during the first few iterations.

To take advantage of this feedback-and-iterate feature a system needs special "soft-input / soft-output" constituent decoders. The discovery of such decoders was a crucial breakthrough in the development of iterative decoding, which characterizes Turbo Codes. In fact, the iterative decoding feedback mechanism is so effective in achieving high performance that Turbo Codes got their name from it -- from an analogy with turbocharged automobile engines that feed back uncombusted but extremely volatile gases into a turbo charger.

Just how effective are Turbo Codes? Fig 3 shows the level of Bit Error Rate (BER) vs S/N ratio (Eb/ No) performance they can achieve. The dotted curves come from the original Turbo Code publication (Ref 3) and also appear in Ref 5. The leftmost dotted curve shows the Shannon Limit, and the rightmost dotted curve is the performance of a Turbo Code with R = 1/2, K = 5, N = 65536 and p = 18 (where R is defined as the code rate, K is defined as the constraint length, N is defined as interleaver size and p is defined as the number of decoder iterations). In addition, Turbo Code descriptions usually include the constituent encoder taps along with several other properties such as puncturing and trellis termination technique. At a BER of 10^-5 , the Rate 1/2 Turbo Code performs to within 0.7 dB of the Shannon Limit -- closer to the limit than any other practical code has ever come.

Fig 3 -- For a given amount of decoder complexity, Turbo Codes approach closer to the Shannon limit than any other known codes. (R is defined as the Rate of code, K is defined as the constraint length, N is defined as the interleaver size, p is defined as the number of iterations). Data from Ref 6.

Achieving such performance requires great computational effort. For space communications such effort can be well justified. Consider the case of the Galileo space mission, which requires a code that enables reliable communications to Jupiter. Fig 3 includes the performance of a Rate 1/4 Galileo code as well as two Rate 1/4 Turbo Codes. At a BER of 10^-4 , the Turbo Codes are approximately 1.3 and 1.5 dB better than the Galileo code, and they're only 0.8 to 1.0 dB from the Shannon Limit. Moreover, compared to the Galileo code, the Turbo Codes require only about 1/10th the computations!

Even so, all these high-performance codes are best simulated on supercomputers due to their large decoding complexity. But because Turbo Codes use an iterative decoding scheme, they automatically provide a means of trading BER performance for computational complexity. Fig 4 shows BER performance vs decoder iterations (again taken from the original Turbo Code data of Refs 3 and 5). After a single decoder pass, the Turbo Code achieves significant improvement over an uncoded system. The next few iterations also achieve large gains, but the increases become ever smaller. To achieve near-optimum results, you must perform a relatively large number of iterations (p = 10 to 20). Of course, in addition to increased computational complexity, every iteration causes a delay in the availability of output data. The delay is equal to the decoder's total memory length times the number of iterations. For Turbo Codes, memory length is dominated by the interleaver size, which for Figs 3 and 4 are N = 4096, 16,384, and 65,536 bits. In contrast, the Galileo code has a memory length of only 14 and thus a much lower latency.

Fig 4 -- To realize exceedingly large coding gain, Turbo Code decoders refine their estimates over several iterations.

At this point, it should be apparent that Turbo Codes represent a revolutionary breakthrough in FEC performance. Although such performance has long been anticipated, practical coding techniques to achieve it have eluded researchers for decades. In summary, you can describe Turbo Codes as systematic linear block codes that use recursive systematic convolutional encoding, with two or more parallel-concatenated constituent encoders (Fig 2a). Turbo Code decoders employ iterative decoding with two or more soft-input/soft-output constituent decoders. If that description sounds like a mouthful, then stay tuned for the next installment, which reviews the basic ECC building blocks that make up Turbo Codes. In it and later installments, you'll not only learn about Turbo Codes specifics but also about a wide variety of ECC topics.

References

1. Shannon, CE, "A Mathematical Theory of Communications, " Bell Systems Technical Journal, Vol 27, July 1948, pgs 379-423 (Part I), pgs 623-656 (Part II).
2. Hamming, RW, "Error Detecting and Error Correcting Codes," Bell Systems Technical Journal, Vol 29, April 1950, pgs 147-160.
3. Berrou, C, Glavieux, A and Thitimajshima, A, "Near Shannon limit error-correcting coding and decoding: Turbo codes," ICC `93, Geneva, Switzerland, May 1993, pgs 1064-1070.
4. Lin, S and Costello, DJ, Error Control Coding: Fundamentals and Applications, 1983, Prentice-Hall (Englewood Cliffs, NJ), ISBN 0-13-283796-X 
5. Berrou, C and Glavieux, A, "Near Optimum Error Correcting Coding and Decoding: Turbo Codes," IEEE Trans Communications, Vol 44, No 10, Oct 1996, pgs 1261-1271.
6. "Turbo Codes for Deep-Space Communications," by D Divsalar and F Pollara, TDA Progress Report 42-120, JPL, Pasadena, CA, pgs 29-39, 15 Feb 1995. http://tda.jpl.nasa.gov/tda/progress_report/42-120/120D.pdf

Charles (Chuck) Gumas serves as Project Lead/Communications Engineer at the MITRE Corp's Information Systems and Technology Div (Reston, VA). He received an MSEE from Lehigh Univ and a BS in physics from the Univ of Pennsylvania. He maintains a web site at www.dc.net/spartan/chuck.html and can be contacted via email at cgumas@mitre.org.

This article originally appeared in Personal Engineering & Instrumentation News, January 1998, pgs 61-66. Reprinted with permission of PEC Inc; all rights reserved.

		Click here to get your listing up.