Viterbi Detection

Abstract - Turbo codes allow engineers to implement systems that use a low energy quantity for the emitter and still can reach the absolute maximum capacity of the channel (as defined by Shannon). This paper presents a practical software implementation of a turbo encoder-decoder and analyzes its performances against other encoding and recording solutions, such as PRML [1] channels and MTR-RLL [5] codes. Simulations confirmed the significant performance gains introduced by turbo codes and proved that a future hardware implementation of the turbo encoder and decoder components would be useful.

1. INTRODUCTION

Within a coding scheme it is important to find a compromise between the coding gain and the encoder complexity. Usually this is done through concatenation. A concatenated code is a code that uses two levels of encoding, an interior one and an exterior one, linked by an interleaver, as seen in figure 1.

Figure 1. Block diagram for a typical turbo encoder-decoder. [8]

The main advantage of a concatenated code is obtaining a minimum bit error rate (BER) with a smaller general decoding complexity as compared to a standard code

with the same performance. The small complexity is obtained by decoding each code component separately.

A turbo code extends the properties of concatenated codes through the fact that it concatenates two convolutional codes in parallel. The convolutional codes are systematic. The exterior code does not transmit the input bits, which reduces the code rate. The interleaver has a very important role in the efficient functionality of the encoder. It prevents the decoder from receiving block errors, which are difficult to correct, by spreading these errors inside the input sequence, increasing the distance between them and decorelating the input symbols. The interleaver size is an important parameter, as the coding gain is directly proportional to it.

Two decoders, connected through the same interleaver, perform the decoding process. Turbo decoding is based on decoding algorithms used for systematic convolutional recursive codes used by the turbo encoder. There are two main decoding algorithms: MAP - maximum a posteriori algorithm and SOVA - soft output Viterbi algorithm. Decoding is based on an iterative process that ensures a flow of information between the two decoders. As the number of iterations raises so does the decoder performance and the Shannon limit is reached.

2. THE TURBO ENCODER

The encoder is based on two RSC (recursive systematic code) encoders linked by an interleaver, detailed in figure 2. The generating matrix for a RSC can be written as:

(1)

Figure 2. Block diagram for a typical turbo encoder. [8]

where g0(D) and g1(D) are polynomials corresponding to positive and negative reactions. Inside the turbo encoder, information is encoded twice through the interleaver. The first RSC encoder has two outputs, one for information bits, v0 and one for parity bits, v1.

v0 = (v , v ... v )

v1 = (v , v ... v ) (2)

The output from the first encoder will be processed by the interleaver and fed into the second RSC encoder. This one will produce at output only the parity check sequence, shown next.

v2 = (v , v ... v ) (3)

The final encoded sequence is obtained by multiplexing the three output sequences from the two encoders. The code rate will be 1/3.

v=(v , v , v , v , v , v ,...v , v , v ) (4)

Due to the sequential bit processing of the interleaver, the turbo encoder can be considered a block encoder. The trellis associated to the code can only be considered to be completed, when it leads to the "0" state. This is necessary because the initial state for the next block is also "0". In order to lead the trellis into a "0" state, 'v' final bits are introduced after the 'n' information bits. The final bits depend on the encoder state after the information bits are processed.

3. THE TURBO DECODER

Most turbo decoding algorithms are based on linear code trellis decoding methods. These are recursive algorithms that estimate the input sequence. One such algorithm is the Viterbi algorithm, which minimizes the error probability of the data sequence. Its output is a hard estimation of transmitted symbols that have the highest probability of appearing in a code sequence. Inside concatenated systems, with multiple stages for signal processing, soft estimation produces better results at reception.

Another decoder class is based on minimizing bit error rate probability. The decoder generates optimum safety estimates as a posteriori symbol estimates. This is known as the MAP - maximum a posteriori probability algorithm. The most efficient variants of this algorithm are: Max-Log-MAP, and Log-MAP. Both decoder classes are efficient for relatively small and medium interleaver sizes. If the interleaver size is too big then the decoder complexity will be unacceptable. Since MAP decoding has offered better results compared to the Viterbi variant, it was the one used in the software implementation and it will be detailed next.

The block diagram for MAP decoding is shown in the next figure.

Figure 3. Block diagram for the iterative MAP decoder. [8]

The decoder is composed of two serially concatenated MAP decoders linked by an interleaver identical to the one in the encoder. The decoders use an extended version of the generating matrix of the RSC (D is the delay operator):

(5)

The first MAP decoder receives the information sequence r0 and the parity check sequence r1. The decoder produces a soft output that is interleaved and used for improving the apriori probability estimate for the second decoder. The other two inputs for the second decoder are; the interleaved information sequence and the parity check sequence produced by the second decoder. The soft output of the second MAP decoder