Use Forward Error Correction To Improve Data Communications

Using Constraint Length
The encoder in Figure 2 has a constraint length of K = 3 and a memory of K-1 or K-2. For this code, the optimal decoder, otherwise known as the Viterbi decoder, has 2^K-1, or four states. A number of values are computed for each state. As K increases, so does the performance of the code—but at a diminishing rate. The complexity of the decoder, though, increases exponentially with K. Today, popular convolutional codes in use employ K = 7 or K = 9.

Block codes are a little more straightforward. A block code will take k information bits and generate one or more "parity " bits. These parity bits are appended to the information bits, resulting in a group of n bits where n > k. The encoded pattern of n bits is referred to as a code word, and this code word is transmitted in its entirety. Figure 3 illustrates a simple (n,k) = (8,4) block-code encoder. The receiver obtains n channel metrics and the decoder estimates the most likely sequence (of which there are 2^k) from these estimates. Block decoders are usually rich in algebraic structure that can be used to facilitate decoding. Perhaps the most popular block codes presently implemented are Reed Solomon codes. Often, these are a shortened version of an n = 2040 code (255 bytes). Until very recently, the most powerful codes were built from the concatenation of a convolutional code and a Reed Solomon code.

The latest advance in FEC is a class of codes called Turbo Codes. These are very powerful codes built from two or more smaller, simpler constituent codes. The constituent codes could be either systematic convolutional or block type. The idea behind Turbo Codes is to encode the data once via encoder 1, in some way scramble the order of these output bits known to the receiver, and then encode these bits with a second encoder, decoder 2. The twice-encoded bits are then transmitted.

At the receiver, decoding proceeds in the reverse order of the encoding process. The first decoding is as per encoder 2 and the second decoding is as per encoder 1. Between the two decodings, the scrambling operation is reversed.

What makes a Turbo Code unique is that the decoding process can be performed again. The second constituent decoder addresses errors left from the first. The second pass of the first decoder then addresses errors left from the second decoder. The scrambling or interleaving operation ensures that errors from one decoder are "spread out" as seen by the other decoder. In order to maximize performance, this decoding process is typically iterated several times.

For this iterative process to work optimally, each constituent decoder must take soft decision metrics as its input in addition to generating soft outputs. Every decoder has to generate an output of n soft decision metrics corresponding to the likelihood of each bit in the encoded sequence. These n output metrics take into account the code redundancy as well as the n soft inputs. This decoder property of utilizing soft inputs and generating soft outputs is unique to Turbo Codes and significantly increases the complexity of the constituent decoders.

The fact that one decoder's output feeds the input to the next decoder is somewhat analogous to a turbocharger in a high-performance engine. The turbocharger uses engine exhaust (output) to power an air intake blower, thus enhancing the input. This is where the term "turbo " in Turbo Code comes from. Turbo codes are iteratively decoded codes.

Turbo Code technology can best be illustrated with an example that uses block codes as the constituent codes. Consider the (8,4) extended Hamming code of Figure 3. This code takes 4 information bits, computes 4 parity bits, and appends these 4 parity bits to the information bits to create an 8-bit code word for transmission:

I I I I P P P P

Here, I corresponds to an information bit and P corresponds to the parity or redundancy bits. A two-dimensional product code constructed from this (8,4) extended Hamming code might be as follows:

where I corresponds to information bits, P_H are the parity bits with each code word constructed horizontally, P_V are the parity bits with each code word constructed vertically, and P_VH are the parity bits of the encoded parity bits.