| Abstract |
A list Viterbi algorithm (LVA) finds n best paths in a trellis. We propose a new implementation of
the tree-trellis LVA. Instead of storing all paths in a single sorted list, we show that it is more efficient
to use several lists, where all paths of the same list have the same metric. For an integer metric, both
the time and space complexity of our implementation are linear in n. Experimental results show that
our implementation is much faster than all previous LVAs. This allows us to consider a large number of
paths in acceptable time. As an application, we show that by increasing the number of candidate paths,
one can significantly improve the performance of a popular progressive source-channel coding system that
protects an embedded image code with a concatenation of an outer error detecting code and an inner error
correcting convolutional code. |