BEAST decoding of block codes obtained via convolutional codes

Summary, in English

BEAST is a bidirectional efficient algorithm for searching trees. In this correspondence, BEAST is extended to maximum-likelihood (ML) decoding of block codes obtained via convolutional codes. First it is shown by simulations that the decoding complexity of BEAST is significantly less than that of the Viterbi algorithm. Then asymptotic upper bounds on the BEAST decoding complexity for three important ensembles of codes are derived. They verify BEAST's high efficiency compared to other algorithms. For high rates, the new asymptotic bound for the best ensemble is in fact better than previously known bounds.

• Author: Irina Bocharova; Marc Handlery; Rolf Johannesson; Boris Kudryashov
• Department/s: Department of Electrical and Information Technology
• Publishing year: 2005
• Language: English
• Pages: 1880-1891
• Publication/Series: IEEE Transactions on Information Theory
• Volume: 51
• Issue: 5
• Links: http://dx.doi.org/10.1109/TIT.2005.846448
• Document type: Journal article
• Publisher: IEEE - Institute of Electrical and Electronics Engineers Inc.
• Topic: Electrical Engineering, Electronic Engineering, Information Engineering
• Keywords: bidirectional search of trees; asymptotical decoding complexity; decoding of block codes; decoding; convolutional codes; maximum-likelihood (ML)
• Status: Published
• ISBN/ISSN/Other: ISSN: 0018-9448