What are less computationally demanding alternatives to the Viterbi Decoder?

Ideally what I would like is a list of the most commonly used approximate methods, along with brief pros and cons.

  • $\begingroup$ Are you specifically asking with respect to the decoding of convolutional error correcting codes (probably the most well-known application)? The Viterbi algorithm can be used in a number of applications where maximum-likelihood sequence detection is desired. $\endgroup$ – Jason R Aug 26 '11 at 4:31
  • $\begingroup$ Yes, that's what I was thinking of. I would be interested both in algorithms that are specific to that application, and more general ML sequence detection methods. $\endgroup$ – gyroidben Aug 26 '11 at 4:53

An straightforward alternative to a Viterbi decoder for decoding convolutional codes is a Sequential Decoder. The algorithm is simpler, but the performance isn't as good. For example, the common constraint lengths for systems using Viterbi decoding are typically k = 7 or k = 9. A system decoded with a sequential decoder typically has a constraint length in the thirties or so. The complexity of a Viterbi decoder would be prohibitive at such a long constraint length, and the performance of a Sequential Decoder is very poor with the short constraint lengths used with a Viterbi decoder.

Another alternative would be to use an APP or MAP decoder, but those are more complex than a Viterbi decoder (since they're essentially two Viterbi decoders running together in opposite directions). But if you just want to say you're not using a "Viterbi" decoder that might qualify.


One (far from optimal) approach:

A half-rate convolutional code can be viewed as two multiplicatively scrambled channel coders multiplexed together. You could decode the two paths with the inverse multiplicative descramblers then combine the two paths. Even if you make the descramblers create soft decisions, the results will be far from optimal, but should be very fast.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.