# zbMATH — the first resource for mathematics

Maximum-likelihood list decoding using trellises. (English. Russian original) Zbl 0811.94036
Probl. Inf. Transm. 29, No. 4, 299-305 (1993); translation from Probl. Pereda. Inf. 29, No. 4, 3-10 (1993).
Summary: Let the Viterbi algorithm be applied for maximum-likelihood decoding of a block code or a terminated convolutional code using a code trellis. We propose an additional procedure that constructs a list of $$L$$ most likely code words, rather than a single estimate. The procedure uses information from the Viterbi decoder. The complexity of the procedure is of order $$nL(L+t)$$, where $$n$$ is the length of a codeword, $$t$$ is the number of branches that enter one node of the code trellis, $$L\ll n$$.

##### MSC:
 94B35 Decoding 94B10 Convolutional codes 94B12 Combined modulation schemes (including trellis codes) in coding theory 68W10 Parallel algorithms in computer science