Viterbi Decoder in Hardware

Viterbi Decoder in Hardware

Mário Pereira Véstias (Instituto Politecnico de Lisboa, Portugal)
DOI: 10.4018/978-1-5225-7598-6.ch084
OnDemand PDF Download:
No Current Special Offers


Trellis decoding is used to recover encoded information that was corrupted during transmission over a noisy channel. The Viterbi algorithm is the most well-known trellis-based maximum likelihood decoding algorithm. The Viterbi algorithm is executed by a Viterbi decoder. Different hardware solutions may be considered to implement a Viterbi decoder with different design requirements in terms of area, performance, power consumption, among others. The most appropriate solution depends on the metric requirements of the application as well as on the target technology. Properties of the Viterbi algorithm are used to simplify and improve the architecture of the Viterbi decoder. In particular, statistical properties of the Viterbi algorithm are used to design parallel Viterbi decoders with very high data decoding rates. The chapter focuses on the implementation of a Viterbi decoder in hardware, including optimizations to improve the area and performance.
Chapter Preview


Generically, a communication system includes a channel encoder at the transmitter and a channel decoder at the receiver. Encoding the bit stream to be transmitted reduces the energy per data bit needed to achieve the same bit error rate (BER) over a noisy channel compared to a non-coded transmission. A better channel code needs lower energy to obtain a particular BER.

Convolutional Encoder

Two major classes of binary codes are block codes and convolution codes. In this article we are only concerned with convolution codes (P. Elias, 1955). Convolution codes operate over a continuous bit stream. A convolutional encoder is used to generate the encoded bitstream. A typical implementation consists on a shift register and a set of modulo-2 addition. The content of the shift register defines the state of the encoder (s bits), from which we obtain a finite state machine with 978-1-5225-7598-6.ch084.m01 states. Figure 1 shows an example of a convolution encoder with rate 1/2 (rate 1/c generates c bits for each input bit) and its state machine.

Figure 1.

Convolution encoder with rate 1/2


An alternative way to represent the behavior of the encoder was proposed by Forney (G. D. Forney, Jr., 1967) designated trellis representation. A trellis is one of the most convenient ways to visualize the behavior of the decoding algorithms (see Figure 2).

Figure 2.

Trellis diagram of the encoder in Figure 1


Each node in the trellis represents a state of the FSM. After m time steps, the trellis is full and the branch pattern repeats indefinitely.

Most work on trellis decoding was dedicated to the codes with a rate of 1/r. This type of codes will provide the simplest trellis decoding since there are only two nodes leaving and entering a state.

Complete Chapter List

Search this Book: