Comparative study of turbo codes in AWGN channel using MAP and SOVA decoding

International Journal of Electrical Engineering Education, Apr 2001 by Soyjaudah, K M S, Russool, M T

Abstract A final-year undergraduate project in error-control coding is discussed. The project consists of the study, software implementation and computer simulation of turbo codes using two different decoding approaches, the Maximum a Posteriori (MAP) and Soft-Output Viterbi Algorithm (SOVA). It combines theory with computer-aided design and provides hands-on experience in the field of channel coding.

Keywords MAP and SOVA decoding; turbo coding

A software-based project in error-control coding combines theory and design with computer simulation. It helps engineering undergraduate students to grasp the principles of communication systems, the need to add controlled redundancy via a channel encoder and to exploit this redundancy at the receiver side, in order to recover the transmitted information through a channel decoder. Further, it helps students to understand Shannon's theorem and the concept of the Shannon limit. This paper presents a project which consists of a study of turbo codes as an error-control code and the software implementation of two different decoders, namely the Maximum a Posteriori (MAP)1 and Soft-- Output Viterbi Algorithm (SOVA) decoders. A comparison of their performances is made against that of the classical Viterbi decoder.

Turbo codes were introduced in 1993 by Berrou et al.2 and are perhaps the most exciting and potentially important development in coding theory in recent years. They achieve near-Shannon-limit error correction performance with relatively simple component codes and large interleavers. They can be constructed by concatenating at least two component codes in a parallel fashion, separated by an interleaver. One feature of turbo codes is that the constituent codes need not be complex. Simple (2,1,4) convolutional codes can achieve very good results. In order for a concatenated scheme such as a turbo code to work properly, the decoding algorithm must effect an exchange of soft information between component decoders. The concept behind turbo decoding is to pass soft information from the output of one decoder to the input of the succeeding one, and to iterate this process several times to produce better decisions. Turbo codes are still in the process of standardisation but future applications will include mobile communication systems, deep space communications, telemetry3 and multimedia. Hence, the understanding of turbo encoding and decoding and their performance is of utmost importance to engineering students.

All software implementation of the turbo codecs has been done in C since it is a flexible and structured programming language. Furthermore, undergraduate students have already acquired a systematic approach to C programming earlier in their course.

The paper is partitioned as follows. The next section describes the constituent encoder, the turbo encoder and the interleaver. The MAP and SOVA decoding algorithms are then outlined, followed by a discussion of the educational benefits derived from such a project. Typical results obtained are then presented, followed by a short conclusion.

Turbo code encoder

A turbo encoder is the parallel concatenation of recursive systematic convolutional (RSC) codes, separated by an interleaver, as shown in Fig. 1. The data flow d^sub k^ goes into the first elementary RSC encoder, and after interleaving, it feeds a second elementary RSC encoder. The input stream is also systematically transmitted as X^sub k^, and the redundancies produced by encoders 1 and 2 are transmitted as Y^sub 1k^ and Y^sub 2k^. For turbo codes, the main reason of using RSC encoders as constituent encoders instead of the traditional non-recursive nonsystematic convolutional codes, is to use their recursive nature and not the fact that they are systematic.5

The global rate of the turbo encoder in Fig. 1 is one-third. To achieve a higher rate, the parity outputs can be punctured. In order to obtain a rate half encoder, the parity bits at the encoder outputs are selected alternately, i.e., one bit from encoder 1 and then one bit from encoder 2, as illustrated in Fig. 2.

The interleaver is an important design parameter in a turbo code. It takes a particular stream at its input and produces a different sequence as output. Its main purpose at the encoder side is to increase the free distance of the turbo code,5 hence improving its error-correction performance.6

There are different types of interleavers, such as the block, pseudo-random, simile, and odd-even interleavers. They differ in the way they shuffle the input symbols. As an example, the block interleaver is explained below. A sequence of L bits is written into an N x M matrix row by row starting from the first row of the matrix. Block interleaving then consists of reading the matrix elements column by column starting from the first one. The resulting sequence is written to an array of length L as shown in Fig. 3.

Design and simulation

The aim of this project is to enable the student to have hands-on experience of:

(a) generation of a pseudorandom sequence,