| Abstract |
A list Viterbi algorithm (LVA) finds the 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, which significantly improves the performance of
a popular progressive source-channel coding system that protects
embedded data with a concatenation of an outer error detecting
code and an inner error correcting convolutional code. |