Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
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
; and
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
host publication
2005 IEEE Information Theory Workshop
conference name
IEEE IT SOC Information Theory Workshop 2005 on Coding and Complexity
conference location
Rotorua, New Zealand
conference dates
2005-08-29 - 2005-09-01
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
2016-04-04 13:34:23
date last changed
2022-01-30 00:29:51
@inproceedings{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}},
  booktitle    = {{2005 IEEE Information Theory Workshop}},
  isbn         = {{0-7803-9480-1}},
  keywords     = {{maximum likelihood decoding; tree searching; block codes; decision trees; computational complexity}},
  language     = {{eng}},
  title        = {{BEAST decoding - asymptotic complexity}},
  url          = {{http://dx.doi.org/10.1109/ITW.2005.1531846}},
  doi          = {{10.1109/ITW.2005.1531846}},
  year         = {{2005}},
}