Zyablov, V. V.; Potapov, V. G.; Sidorenko, V. R. 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\). Cited in 1 Document MSC: 94B35 Decoding 94B10 Convolutional codes 94B12 Combined modulation schemes (including trellis codes) in coding theory 68W10 Parallel algorithms in computer science Keywords:list decoding; Viterbi algorithm; maximum-likelihood decoding; block code; convolutional code; trellis; Viterbi decoder; complexity PDF BibTeX XML Cite \textit{V. V. Zyablov} et al., Probl. Inf. Transm. 29, No. 4, 1 (1993; Zbl 0811.94036); translation from Probl. Pereda. Inf. 29, No. 4, 3--10 (1993)