@inproceedings{7aa834cf49ff4e4196c1009d29cef408,
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 B. Vasic",
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",
address = "United States",
note = "2003 IEEE Information Theory Workshop, ITW 2003 ; Conference date: 31-03-2003 Through 04-04-2003",
}