BEAST decoding - asymptotic complexity

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

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.

Details

Authors
Organisations
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Electrical Engineering, Electronic Engineering, Information Engineering

Keywords

  • maximum likelihood decoding, tree searching, block codes, decision trees, computational complexity
Original languageEnglish
Title of host publication2005 IEEE Information Theory Workshop
Publication statusPublished - 2005
Publication categoryResearch
Peer-reviewedYes
EventIEEE IT SOC Information Theory Workshop 2005 on Coding and Complexity - Rotorua, New Zealand
Duration: 2005 Aug 292005 Sep 1

Conference

ConferenceIEEE IT SOC Information Theory Workshop 2005 on Coding and Complexity
CountryNew Zealand
CityRotorua
Period2005/08/292005/09/01