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

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