Turbo Codes

Summary

Turbo codes significantly outperform the codes currently used in the Deep Space Network, most notably the concatenated (255,223) Reed-Solomon and (15,1/6) convolutional code. We expect that many missions launched around 2003 and thereafter will use the CCSDS standardized turbo codes or slight variants of them for downlink. This requires turbo encoders onboard the spacecraft, and high speed turbo decoders at each of the DSN ground stations. My work has included facilitating the encoder implementation where possible, and building the prototype decoder.

Turbo Encoder

Turbo encoding is pretty straightforward. The CCSDS codes come in a variety of rates (1/2, 1/3, 1/4, and 1/6) and block lengths (1784, 3568, 7136, 8920, and perhaps 16384); see the CCSDS 101.0-B-4 Blue Book for the full details. The encoder consists of two 16-state convolutional codes and an interleaver. The convolutional codes are readily implemented with small look-up tables, and the interleaver is most easily implemented with a large table describing the permutation.

Here is an example rate 1/4 turbo encoder function 23 lines long, optimized for speed and simplicity:

encfast.c

As input, this function requires a message of N bits (where N is the block length), stored one bit per integer, an array describing the permutation, and a pointer to an array of integers, where the codeword should be stored.

To demonstrate its use, here is a complete stand-alone program in somewhat under two pages:

encoder.c

This pre-computes the CCSDS standard interleaver, generates a sample message randomly, saves it to the file "message", turbo-encodes it, and saves the resulting codeword to the file "codeword". For completeness, this program supports all the standard block lengths and code rates. For amusement, it also contains two equivalent methods for pre-computing the interleaver: one method is obvious from the standard, while the other is faster and perhaps simpler.

Turbo Decoder

Turbo decoding is far more complicated than encoding. Even today, seven years after the discovery of turbo codes, many details in the decoding algorithm remain topics of active research. Variations in these details can change the error rate slightly, change decoding speed substantially, and change the necessary computation and memory resources in various ways.

For the Deep Space Network implementation, I have tried to select methods which provide the best tradeoff between speed and performance within the constraints of the hardware commercially available today. For the curious, I have made much of the software available here, with some explanatory comments.

DSP Based Turbo Decoder Software

References

Deep Space Network Turbo Decoder Implementation, to be presented at the IEEE 2001 Aerospace conference in March. This is a semi-technical summary of the implementation effort, primarily for management types.

Turbo Decoder Implementation for the DSN, a draft TMO progress report. This is a fairly technical description of the turbo decoder algorithms and software implementation.

home
Last modified 11/8/00