IEICE TRANSACTIONS on Fundamentals
Complexity Reduction of the Gazelle and Snyders Decoding Algorithm for Maximum Likelihood Decoding
Summary :
Several reliability based code search algorithms for maximum likelihood decoding have been proposed. These algorithms search the most likely codeword, using the most reliable information set where the leftmost k (the dimension of code) columns of generator matrix are the most reliable and linearly independent. Especially, D. Gazelle and J. Snyders have proposed an efficient decoding algorithm and this algorithm requires small number of candidate codewords to find out the most likely codeword. In this paper, we propose new efficient methods for both generating candidate codewords and computing metrics of candidate codewords to obtain the most likely codeword at the decoder. The candidate codewords constructed by the proposed method are identical those in the decoding algorithm of Gazelle et al. Consequently, the proposed decoding algorithm reduces the time complexity in total, compared to the decoding algorithm of Gazelle et al. without the degradation in error performance.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E86-A No.10 pp.2461-2472
- Publication Date
- 2003/10/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Information Theory and Its Applications)
- Category
- Coding Theory
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hideki YAGI, Manabu KOBAYASHI, Shigeichi HIRASAWA, "Complexity Reduction of the Gazelle and Snyders Decoding Algorithm for Maximum Likelihood Decoding" in IEICE TRANSACTIONS on Fundamentals,
vol. E86-A, no. 10, pp. 2461-2472, October 2003, doi: .
Abstract: Several reliability based code search algorithms for maximum likelihood decoding have been proposed. These algorithms search the most likely codeword, using the most reliable information set where the leftmost k (the dimension of code) columns of generator matrix are the most reliable and linearly independent. Especially, D. Gazelle and J. Snyders have proposed an efficient decoding algorithm and this algorithm requires small number of candidate codewords to find out the most likely codeword. In this paper, we propose new efficient methods for both generating candidate codewords and computing metrics of candidate codewords to obtain the most likely codeword at the decoder. The candidate codewords constructed by the proposed method are identical those in the decoding algorithm of Gazelle et al. Consequently, the proposed decoding algorithm reduces the time complexity in total, compared to the decoding algorithm of Gazelle et al. without the degradation in error performance.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e86-a_10_2461/_p
Copy
@ARTICLE{e86-a_10_2461,
author={Hideki YAGI, Manabu KOBAYASHI, Shigeichi HIRASAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Complexity Reduction of the Gazelle and Snyders Decoding Algorithm for Maximum Likelihood Decoding},
year={2003},
volume={E86-A},
number={10},
pages={2461-2472},
abstract={Several reliability based code search algorithms for maximum likelihood decoding have been proposed. These algorithms search the most likely codeword, using the most reliable information set where the leftmost k (the dimension of code) columns of generator matrix are the most reliable and linearly independent. Especially, D. Gazelle and J. Snyders have proposed an efficient decoding algorithm and this algorithm requires small number of candidate codewords to find out the most likely codeword. In this paper, we propose new efficient methods for both generating candidate codewords and computing metrics of candidate codewords to obtain the most likely codeword at the decoder. The candidate codewords constructed by the proposed method are identical those in the decoding algorithm of Gazelle et al. Consequently, the proposed decoding algorithm reduces the time complexity in total, compared to the decoding algorithm of Gazelle et al. without the degradation in error performance.},
keywords={},
doi={},
ISSN={},
month={October},}
Copy
TY - JOUR
TI - Complexity Reduction of the Gazelle and Snyders Decoding Algorithm for Maximum Likelihood Decoding
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2461
EP - 2472
AU - Hideki YAGI
AU - Manabu KOBAYASHI
AU - Shigeichi HIRASAWA
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E86-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2003
AB - Several reliability based code search algorithms for maximum likelihood decoding have been proposed. These algorithms search the most likely codeword, using the most reliable information set where the leftmost k (the dimension of code) columns of generator matrix are the most reliable and linearly independent. Especially, D. Gazelle and J. Snyders have proposed an efficient decoding algorithm and this algorithm requires small number of candidate codewords to find out the most likely codeword. In this paper, we propose new efficient methods for both generating candidate codewords and computing metrics of candidate codewords to obtain the most likely codeword at the decoder. The candidate codewords constructed by the proposed method are identical those in the decoding algorithm of Gazelle et al. Consequently, the proposed decoding algorithm reduces the time complexity in total, compared to the decoding algorithm of Gazelle et al. without the degradation in error performance.
ER -
English
