Asymptotic analysis of A∗ maximum-likelihood decoding with reliability reordering

O. Milenkovic; Bane V Vasic

doi:10.1109/ITW.2003.1216757

Asymptotic analysis of A∗ maximum-likelihood decoding with reliability reordering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We investigate the computational complexity of the A∗ algorithm with reliability reordering, applied to maximum-likelihood (ML) decoding of block codes. Extensive computer simulations show that A∗ decoding with reliability reordering offers good average computational performance, but up to date there is no accurate analytical description of the decoding complexity. By using the theory of order statistics, we derive asymptotic bounds for the maximum decoding complexity as well as approximations for the average decoding complexity of the algorithm for large noise levels. The analysis shows that reordering is a key feature of the algorithm that allows for substantial computational savings.

Original language	English (US)
Title of host publication	Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	316-319
Number of pages	4
ISBN (Electronic)	0780377990, 9780780377998
DOIs	https://doi.org/10.1109/ITW.2003.1216757
State	Published - 2003
Event	2003 IEEE Information Theory Workshop, ITW 2003 - Paris, France Duration: Mar 31 2003 → Apr 4 2003

Publication series

Name	Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003

Other

Other	2003 IEEE Information Theory Workshop, ITW 2003
Country/Territory	France
City	Paris
Period	3/31/03 → 4/4/03

ASJC Scopus subject areas

Computational Theory and Mathematics
Computer Networks and Communications
Information Systems
Electrical and Electronic Engineering

Access to Document

10.1109/ITW.2003.1216757

Cite this

Milenkovic, O., & Vasic, B. V. (2003). Asymptotic analysis of A∗ maximum-likelihood decoding with reliability reordering. In Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003 (pp. 316-319). Article 1216757 (Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ITW.2003.1216757

Asymptotic analysis of A∗ maximum-likelihood decoding with reliability reordering. / Milenkovic, O.; Vasic, Bane V.
Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003. Institute of Electrical and Electronics Engineers Inc., 2003. p. 316-319 1216757 (Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Milenkovic, O & Vasic, BV 2003, Asymptotic analysis of A∗ maximum-likelihood decoding with reliability reordering. in Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003., 1216757, Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003, Institute of Electrical and Electronics Engineers Inc., pp. 316-319, 2003 IEEE Information Theory Workshop, ITW 2003, Paris, France, 3/31/03. https://doi.org/10.1109/ITW.2003.1216757

@inproceedings{9a747407fddc4562ad06f2536d01b065,

title = "Asymptotic analysis of A∗ maximum-likelihood decoding with reliability reordering",

abstract = "We investigate the computational complexity of the A∗ algorithm with reliability reordering, applied to maximum-likelihood (ML) decoding of block codes. Extensive computer simulations show that A∗ decoding with reliability reordering offers good average computational performance, but up to date there is no accurate analytical description of the decoding complexity. By using the theory of order statistics, we derive asymptotic bounds for the maximum decoding complexity as well as approximations for the average decoding complexity of the algorithm for large noise levels. The analysis shows that reordering is a key feature of the algorithm that allows for substantial computational savings.",

author = "O. Milenkovic and Vasic, {Bane V}",

note = "Publisher Copyright: {\textcopyright} 2003 IEEE.; 2003 IEEE Information Theory Workshop, ITW 2003 ; Conference date: 31-03-2003 Through 04-04-2003",

year = "2003",

doi = "10.1109/ITW.2003.1216757",

language = "English (US)",

series = "Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "316--319",

booktitle = "Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003",

}

TY - GEN

T1 - Asymptotic analysis of A∗ maximum-likelihood decoding with reliability reordering

AU - Milenkovic, O.

AU - Vasic, Bane V

PY - 2003

Y1 - 2003

N2 - We investigate the computational complexity of the A∗ algorithm with reliability reordering, applied to maximum-likelihood (ML) decoding of block codes. Extensive computer simulations show that A∗ decoding with reliability reordering offers good average computational performance, but up to date there is no accurate analytical description of the decoding complexity. By using the theory of order statistics, we derive asymptotic bounds for the maximum decoding complexity as well as approximations for the average decoding complexity of the algorithm for large noise levels. The analysis shows that reordering is a key feature of the algorithm that allows for substantial computational savings.

AB - We investigate the computational complexity of the A∗ algorithm with reliability reordering, applied to maximum-likelihood (ML) decoding of block codes. Extensive computer simulations show that A∗ decoding with reliability reordering offers good average computational performance, but up to date there is no accurate analytical description of the decoding complexity. By using the theory of order statistics, we derive asymptotic bounds for the maximum decoding complexity as well as approximations for the average decoding complexity of the algorithm for large noise levels. The analysis shows that reordering is a key feature of the algorithm that allows for substantial computational savings.

UR - http://www.scopus.com/inward/record.url?scp=84939179277&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84939179277&partnerID=8YFLogxK

U2 - 10.1109/ITW.2003.1216757

DO - 10.1109/ITW.2003.1216757

M3 - Conference contribution

AN - SCOPUS:84939179277

T3 - Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003

SP - 316

EP - 319

BT - Proceedings - 2003 IEEE Information Theory Workshop, ITW 2003

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2003 IEEE Information Theory Workshop, ITW 2003

Y2 - 31 March 2003 through 4 April 2003

ER -

Asymptotic analysis of A∗ maximum-likelihood decoding with reliability reordering

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this