Abstract
The Viterbi algorithm is the most well-known trellis-based maximum likelihood decoding algorithm. Trellis decoding is used to recover encoded information that was corrupted during transmission over a noisy channel. The Viterbi algorithm is implemented with a Viterbi decoder. High-speed applications require high-speed Viterbi decoders. Therefore, many hardware solutions have been proposed to improve the performance of Viterbi decoders. These hardware solutions explore the properties of the Viterbi algorithm to simplify and improve the architecture of the decoder. In particular, statistical properties of the algorithm are used to design parallel Viterbi decoders with very high data decoding rates. The article focuses on the implementation of high-speed Viterbi decoders.
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, the authors 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 a finite state machine with m=2s states is obtained. 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
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.
Branch Metric Unit (BMU): A unit to calculate the Euclidian distances associated with each branch of the Trellis diagram for each input symbol.
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).
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.
Add-Compare-Select Unit (ACSU): A unit that accumulates the branch metrics of each branch along the trellis diagram.
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 Encoder: A module used to generate convolutional codes.
Convolutional Codes: A type of error correcting code used in telecommunications.