Abstract
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 article focuses on the implementation of a Viterbi decoder in hardware, including optimizations to improve the area and performance.
TopBackground
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 
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.
Key Terms in this Chapter
Branch Metric Unit (BMU): A unit to calculate the Euclidian distances associated with each branch of the Trellis diagram for each input symbol.
Trace-Back Unit (TBU): A unit of the VD that finds the state with the lowest value and returns the path ending in this state.
Convolutional Codes: A type of error correcting code used in telecommunications.
Convolutional Encoder: A module used to generate convolutional codes.
Viterbi Algorithm: An algorithm to decode convolutional codes with an optimum non-sequential algorithm. The computational complexity of the Viterbi algorithm increases linearly with the length of the bit stream. The algorithm has three main steps: branch metric calculation; trellis calculation; and traceback decoding.
Viterbi Decoder (VD): An implementation of the Viterbi algorithm consisting of three main functional units, one for each of the three steps of the Viterbi algorithm.
Add-Compare-Select Unit (ACSU): A unit that accumulates the branch metrics of each branch along the trellis diagram.
Trellis Diagram: A type of graph where nodes represent states and each node is connected to at least one previous node (state) and one next node (state).