Viterbi Decoder Software Generator

What Is It?

The Spiral Viterbi Software Generator automatically generates high-performance software implementations for decoders for a large class of convolutional codes. The user specifies the code and the target architecture; the generator returns the source code (Intel compatible) for an encoder and a high-performance decoder using the Viterbi algorithm.

We reuse the infrastructure, the encoder, and the traceback of the decoder from Phil Karn's implementation (slightly modified). We only generated the (most costly) forward part of the Viterbi decoder.

Background

Convolutional codes [2] are a common type of error-correcting code where encoding is traditionally done in hardware using a shifting register and modulo-2 adders. Every cycle, a new value enters the register and the modulo-2 additions of some values inside the register constitute the output bits. The inverse of the number of adders describes the ratio of meaningful data within the message and is called the rate r of the code. The length of the shifting register constitutes the "memory" of the code and is called the constraint-length, usually denoted as K. The actual wiring of the adders are called the polynomials. There are as many polynomials as the inverse of the rate and each one is an integer between 1 and 2^K - 1. Because of the finiteness of K, the encoding operation can be equivalently represented as a finite state machine (FSM) with 2^(K-1) states.

The Viterbi algorithm [3,4] implements a maximum likelihood decoder: Given a corrupted encoded bitstream, its purpose is to return the most probable original data. Using a representation called the Viterbi trellis, the algorithm maintains the cost of being in every state of the FSM based on the Hamming distance to the message. It resolves conflicts locally during the forward pass and reads off results during the traceback.

Generator

Input: parameters specifying the convolutional code and the target architecture

Output: C code, or C code with Intel compatible SSE vector instructions, for a Viterbi decoder for the specified code. Longer vector length means higher performance (see benchmark below).

Benchmarks

Below we benchmark our generated implementations of Viterbi decoding for four different convolutional codes and for different degrees of SIMD vectorization (scalar, 4-way, 8-way, 16-way) against Phil Karn's implementation. The base line is Karn's C code, which is normalized to 1. Higher is better. A missing bar means that the vector length is not provided by Karn (e.g., 4-way for the Voyager code).

Blue = Karn's implementations, red = Spiral-generated implementations, darker = longer vectors = higher performance

References

We have not published this work yet. Here are a few standard references cited above.

1. Frédéric de Mesmay, Srinivas Chellappa, Franz Franchetti and Markus Püschel
   Computer Generation of Efficient Software Viterbi Decoders
   submitted for publication
2. W.W. Peterson and E.J. Weldon, Jr.
   Error-Correcting Codes
   2nd edition, MIT Press: Cambridge, Mass.
3. A. Viterbi
   Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
   IEEE Trans. Inform. Theory, IT-13:260–269, Apr.1967
4. G.D. Forney Jr.
   The Viterbi algorithm
   Proceedings of the IEEE, 61(3),  March 1973 Page(s):268 - 278

More Information

This generator is part of the Spiral library generation system and was created by Frédéric de Mesmay based on earlier work by Srinivas Chellappa.

Contact: Frédéric de Mesmay, fdemesma (at) xxxece.cmu.edu (delete xxx)