Forward Error-Correction Coding

Charles Wang, Dean Sklar, and Diana Johnson

Digital communication systems, particularly for military use, need to perform accurately and reliably in the presence of noise and interference. Among many possible ways to achieve this goal, forward error-correction coding is the most effective and economical.

Forward error-correction coding (also called channel coding) is a type of digital signal processing that improves data reliability by introducing a known structure into a data sequence prior to transmission or storage. This structure enables a receiving system to detect and possibly correct errors caused by corruption from the channel and the receiver. As the name implies, this coding technique enables the decoder to correct errors without requesting retransmission of the original information (see sidebar, How Forward Error-Correcting Codes Work).

The Aerospace Corporation has devoted considerable effort to research and development of forward error-correction techniques, with particular emphasis on one method known as turbo coding. This work has played an important role in supporting several government programs, including the Advanced Extremely High Frequency program, the Advanced Wideband System, and the Geostationary Operational Environmental Satellite System.

The Evolution of Forward Error Correction

In a communication system that employs forward error-correction coding, a digital information source sends a data sequence to an encoder. The encoder inserts redundant (or parity) bits, thereby outputting a longer sequence of code bits, called a codeword. Such codewords can then be transmitted to a receiver, which uses a suitable decoder to extract the original data sequence.

An example of a (6, 3) algebraic encoder that produces a six-bit codeword for every three-bit message sequence. In this example, each six-bit output codeword is composed of the original three-bit message sequence and a three-bit parity sequence. This codeword format is known as systematic.

Codes that introduce a large measure of redundancy convey relatively little information per each individual code bit. This is advantageous because it reduces the likelihood that all of the original data will be wiped out during a single transmission. On the other hand, the addition of parity bits will generally increase transmission bandwidth requirements or message delay (or both).

Algebraic coding (also known as block coding) was the only type of forward error-correction coding in use when Claude Shannon published his seminal Mathematical Theory of Communication in 1948. With this technique, the encoder intersperses parity bits into the data sequence using a particular algebraic algorithm. On the receiving end, the decoder applies an inverse of the algebraic algorithm to identify and correct any errors caused by channel corruption.

Another forward error-correcting technique, known as convolutional coding, was first introduced in 1955. Convolutional codes process the incoming bits in streams rather than in blocks. The paramount feature of such codes is that the encoding of any bit is strongly influenced by the bits that preceded it (that is, the memory of past bits). A convolutional decoder takes into account such memory when trying to estimate the most likely sequence of data that produced the received sequence of code bits. Historically, the first type of convolutional decoding, known as sequential decoding, used a systematic procedure to search for a good estimate of the message sequence; however, such procedures require a great deal of memory, and typically suffer from buffer overflow and nongraceful degradation.

In 1967, Andrew Viterbi developed a decoding technique that has since become the standard for decoding convolutional codes. At each bit-interval, the Viterbi decoding algorithm compares the actual received code bits with the code bits that might have been generated for each possible memory-state transition. It chooses, based on metrics of similarity, the most likely sequence within a specific time frame. The Viterbi decoding algorithm requires less memory than sequential decoding because unlikely sequences are dismissed early, leaving a relatively small number of candidate sequences that need to be stored.

Some types of algebraic coding are most effective in combating "bursty" errors (errors that arrive in bursts). Convolutional coding is generally more robust when faced with random errors or white noise; however, any decoding errors occurring in the convolutional decoder are likely to occur in bursts. In 1974, Joseph Odenwalder combined these two coding techniques to form a concatenated code. In this arrangement, the encoder linked together an algebraic code followed by a convolutional code. The decoder, a mirror image of the encoding operation, consisted of a convolutional decoder followed by an algebraic decoder. Thus, any bursty errors resulting from the convolutional decoder could be effectively corrected by the algebraic decoder. Performance was further enhanced by using an interleaver between the two encoding stages to mitigate any bursts that might be too long for the algebraic decoder to handle. This particular structure demonstrated significant improvement over previous coding systems and is currently being used in the Deep Space Network and Air Force Satellite Control Network as well as in commercial broadcasting services.

In 1993, Claude Berrou and his associates developed the turbo code, the most powerful forward error-correction code yet. Using the turbo code, communication systems can approach the theoretical limit of channel capacity, as characterized by the so-called Shannon Limit, which had been considered unreachable for more than four decades.

Turbo Coding

One of the requirements of a turbo coder-decoder (or codec) configuration is that the encoder must include some arrangement of at least two component encoders. Although each component encoder may employ algebraic coding or convolutional coding, the overall encoder can be considered a block encoder because data are processed in blocks. The size of these blocks is dictated by the length of the interleaver that separates each component encoder.

turbo encoder using parallel concatenation

An example of a turbo encoder using parallel concatenated component codes (the most commonly implemented configuration). Although the figure shows a block size of four bits for discussion purposes, typical block sizes are on the order of hundreds or thousands of bits. Bit times are indicated by subscripts. The figure represents a rate-1/3 turbo encoder (that is, one data bit produces a three-bit codeword), but other rates are possible with this identical configuration by the careful elimination of selected code bits.

The interleaver in a turbo encoder serves a different purpose than interleavers used by other parts of a communication system. Standard interleavers scramble code bits among multiple blocks so that they are not contiguous when transmitted; as a result, any bursty errors caused by channel corruption are transformed, or spread out, into more-random errors after deinterleaving. The interleaver in a turbo encoder, on the other hand, is designed so that the second encoder gets an interleaved version of the same data block that went into the first encoder; thus, the second encoder generates an independent set of code bits. Doing so provides diversity to the coded sequence being transmitted. Although any interleaving pattern can be adopted, different patterns can result in significant differences in the bit-error rate; therefore, the interleaver design contributes significantly to the overall error performance of the turbo-code system.

The turbo codec must have as many component decoders on the receiving end as component encoders on the transmitting end. These decoders are concatenated in serial fashion and are joined by a series of interleavers and deinterleavers in a feedback loop.

In a typical decoding operation, the first decoder generates statistical information based on the data received from the first component encoder. This information is then fed to the second decoder, which processes it along with the data received from the second component encoder. After decoding, the improved and updated statistical information is fed back to the first decoder, which starts the process again. This process typically continues for six to ten iterations for each block of data, at which point a switch is triggered and the actual data estimates are produced.

Turbo decoders have an iterative structure, composed of as many component decoders as there are component encoders, concatenated in a serial fashion. The interleavers and deinterleavers are used to ensure the correct ordering among the various types of information processed.

Thanks to the iterative decoding process, turbo codes can achieve a bit-error rate that approaches the Shannon limit. For example, at a desired bit-error rate of 10^-6, convolutional codes can typically provide a 5.5-decibel improvement (72 percent power savings) and concatenated codes a 7.75-decibel improvement (83 percent power savings) over an uncoded system. Using a turbo code, an additional 2.25-decibel improvement over the concatenated code can be attained, resulting in a total coding gain of 10 decibels (90 percent power savings) compared with the uncoded system. For a rate-1/2 turbo-coded system, the error performance comes within about 1 decibel of the Shannon limit.

Aerospace Achievement in Turbo-Code Development

During the last five years, Aerospace has made significant contributions to the advancement of turbo codes, which can potentially benefit all government satellite programs. For example, because a turbo code's performance is sensitive to elements in the code's structure (such as component code configuration and interleaving pattern), Aerospace has developed software that searches for optimal turbo-code structures. The bit-error rate improvement of turbo codes tends to saturate beyond some range of signal-to-noise ratio; beyond this point, known as the error floor, the bit-error rate cannot be reduced by simply increasing the signal-to-noise ratio. Aerospace has developed various schemes to mitigate this error-floor problem (resulting in three U.S. patents).

The bit-error rate of a rate-1/2 turbo coded system after 10 iterations as compared with systems that use no coding, convolutional coding, and concatenated coding. In this example, at a desired bit-error rate of 10^-6, the use of convolutional and concatenated codes provides a 5.5-decibel (72 percent power savings) and 7.75-decibel (83 percent power savings) respective improvement compared with the uncoded system. Here, the use of a turbo code imparts an additional 2.25-decibel improvement compared with the concatenated code, resulting in a total coding gain of 10 decibels (90 percent power savings) compared with the uncoded system. With the use of a rate-1/2 turbo code, system error performance can approach levels within about 1 decibel of the Shannon limit.

Aerospace's work in turbo codes has been directly applied in support of the Advanced Extremely High Frequency program, the Advanced Wideband System, the Global Positioning System, and the Geostationary Operational Environmental Satellite System. These efforts have culminated in the development of a powerful computer simulation tool to evaluate the end-to-end user bit-error rate over a processed or unprocessed satellite channel that uses turbo codes. This simulation tool models the turbo codec, different channel disturbances (e.g., Gaussian noise, scintillation, and jamming), and various modulation schemes (such as phase-shift keying, frequency-shift keying, quadrature amplitude modulation, and Gaussian minimum shift keying) that can be independently selected for either the uplink or downlink channel. Furthermore, Aerospace showed that using conventional demodulation schemes for most of these waveforms prevents turbo codes from achieving their optimal performance. Aerospace therefore developed and is patenting various unique demodulation schemes that permit better turbo-code performance.

Some programs, such as the Advanced Wideband System, require high-data-rate transmission as well as good bit-error-rate performance. To achieve this goal, Aerospace began investigating turbo codes involving high-rate component codes. It turned out, however, that most common decoding algorithms were unsuitable because they were originally developed for turbo codes employing low-rate component codes. Low-rate codes introduce more parity bits than do high-rate codes, and therefore require faster transmission and larger bandwidth to compensate (for real-time applications). Aerospace therefore developed a decoding algorithm specifically optimized for high-rate component codes.

Such developments have made significant—in some cases, critical—contributions to the success of these programs.

Conclusion

Forward error-correction coding represents the most efficient, economical, and predictable way of improving the reliability of transmitted or stored data. The turbo code in particular offers designers a powerful tool for ensuring robust communications despite adverse conditions. As concerns over spectrum management and bandwidth efficiency increase, the ability to maximize channel capacity without sacrificing data reliability becomes all the more important. Thanks in part to Aerospace developments, forward error-correcting codes should play a larger role in helping military communication satellites to keep up with increasing system demands.