Advanced

BEAST decoding - asymptotic complexity

Bocharova, Irina LU ; Johannesson, Rolf LU and Kudryashov, Boris LU (2005) IEEE IT SOC Information Theory Workshop 2005 on Coding and Complexity In 2005 IEEE Information Theory Workshop
Abstract
BEAST is a bidirectional efficient algorithm for searching trees that performs soft-decision maximum-likelihood (ML) decoding of block codes. The decoding complexity of BEAST is significantly reduced compared to the Viterbi algorithm. An analysis of the asymptotic BEAST decoding complexity verifies BEAST's high efficiency compared to other algorithms. The best of the obtained asymptotic upper bounds on the BEAST decoding complexity is better than previously known bounds for ML decoding in a wide range of code rates.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
maximum likelihood decoding, tree searching, block codes, decision trees, computational complexity
in
2005 IEEE Information Theory Workshop
conference name
IEEE IT SOC Information Theory Workshop 2005 on Coding and Complexity
external identifiers
  • Scopus:33749079690
ISBN
0-7803-9480-1
DOI
10.1109/ITW.2005.1531846
language
English
LU publication?
yes
id
79279884-0ca2-4afb-8485-b0815ceec4b6 (old id 628993)
date added to LUP
2007-11-29 15:51:45
date last changed
2016-10-13 04:56:08
@misc{79279884-0ca2-4afb-8485-b0815ceec4b6,
  abstract     = {BEAST is a bidirectional efficient algorithm for searching trees that performs soft-decision maximum-likelihood (ML) decoding of block codes. The decoding complexity of BEAST is significantly reduced compared to the Viterbi algorithm. An analysis of the asymptotic BEAST decoding complexity verifies BEAST's high efficiency compared to other algorithms. The best of the obtained asymptotic upper bounds on the BEAST decoding complexity is better than previously known bounds for ML decoding in a wide range of code rates.},
  author       = {Bocharova, Irina and Johannesson, Rolf and Kudryashov, Boris},
  isbn         = {0-7803-9480-1},
  keyword      = {maximum likelihood decoding,tree searching,block codes,decision trees,computational complexity},
  language     = {eng},
  series       = {2005 IEEE Information Theory Workshop},
  title        = {BEAST decoding - asymptotic complexity},
  url          = {http://dx.doi.org/10.1109/ITW.2005.1531846},
  year         = {2005},
}