Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

BEAST decoding of block codes obtained via convolutional codes

Bocharova, Irina LU ; Handlery, Marc LU ; Johannesson, Rolf LU and Kudryashov, Boris LU (2005) In IEEE Transactions on Information Theory 51(5). p.1880-1891
Abstract
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.
Please use this url to cite or link to this publication:
author
; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
bidirectional search of trees, asymptotical decoding complexity, decoding of block codes, decoding, convolutional codes, maximum-likelihood (ML)
in
IEEE Transactions on Information Theory
volume
51
issue
5
pages
1880 - 1891
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • wos:000228650900025
  • scopus:18544379331
ISSN
0018-9448
DOI
10.1109/TIT.2005.846448
language
English
LU publication?
yes
id
6582cda2-8576-438d-ab88-f2f95e7bf9e5 (old id 244441)
date added to LUP
2016-04-01 15:24:03
date last changed
2022-01-28 05:10:39
@article{6582cda2-8576-438d-ab88-f2f95e7bf9e5,
  abstract     = {{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       = {{Bocharova, Irina and Handlery, Marc and Johannesson, Rolf and Kudryashov, Boris}},
  issn         = {{0018-9448}},
  keywords     = {{bidirectional search of trees; asymptotical decoding complexity; decoding of block codes; decoding; convolutional codes; maximum-likelihood (ML)}},
  language     = {{eng}},
  number       = {{5}},
  pages        = {{1880--1891}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  series       = {{IEEE Transactions on Information Theory}},
  title        = {{BEAST decoding of block codes obtained via convolutional codes}},
  url          = {{http://dx.doi.org/10.1109/TIT.2005.846448}},
  doi          = {{10.1109/TIT.2005.846448}},
  volume       = {{51}},
  year         = {{2005}},
}