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.
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.