×

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
PDF BibTeX XML Cite