Gopalan, Klivans, and Zuckerman proposed a list-decoding algorithm for Reed-Muller codes. Their algorithm works up to a given list-decoding radius. Dumer, Kabatiansky, and Tavernier improved the complexity of the algorithm for binary Reed-Muller codes by using the well-known Plotkin construction. In this study, we propose a list-decoding algorithm for non-binary Reed-Muller codes as a generalization of Dumer et al.'s algorithm. Our algorithm is based on a generalized Plotkin construction, and is more suitable for parallel computation than the algorithm of Gopalan et al. Since the list-decoding algorithms of Gopalan et al., Dumer et al., and ours can be applied to more general codes than Reed-Muller codes, we give a condition for codes under which these list-decoding algorithms works.
Kenji YASUNAGA
Kanazawa University
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.
Copy
Kenji YASUNAGA, "List Decoding of Reed-Muller Codes Based on a Generalized Plotkin Construction" in IEICE TRANSACTIONS on Fundamentals,
vol. E96-A, no. 7, pp. 1662-1666, July 2013, doi: 10.1587/transfun.E96.A.1662.
Abstract: Gopalan, Klivans, and Zuckerman proposed a list-decoding algorithm for Reed-Muller codes. Their algorithm works up to a given list-decoding radius. Dumer, Kabatiansky, and Tavernier improved the complexity of the algorithm for binary Reed-Muller codes by using the well-known Plotkin construction. In this study, we propose a list-decoding algorithm for non-binary Reed-Muller codes as a generalization of Dumer et al.'s algorithm. Our algorithm is based on a generalized Plotkin construction, and is more suitable for parallel computation than the algorithm of Gopalan et al. Since the list-decoding algorithms of Gopalan et al., Dumer et al., and ours can be applied to more general codes than Reed-Muller codes, we give a condition for codes under which these list-decoding algorithms works.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E96.A.1662/_p
Copy
@ARTICLE{e96-a_7_1662,
author={Kenji YASUNAGA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={List Decoding of Reed-Muller Codes Based on a Generalized Plotkin Construction},
year={2013},
volume={E96-A},
number={7},
pages={1662-1666},
abstract={Gopalan, Klivans, and Zuckerman proposed a list-decoding algorithm for Reed-Muller codes. Their algorithm works up to a given list-decoding radius. Dumer, Kabatiansky, and Tavernier improved the complexity of the algorithm for binary Reed-Muller codes by using the well-known Plotkin construction. In this study, we propose a list-decoding algorithm for non-binary Reed-Muller codes as a generalization of Dumer et al.'s algorithm. Our algorithm is based on a generalized Plotkin construction, and is more suitable for parallel computation than the algorithm of Gopalan et al. Since the list-decoding algorithms of Gopalan et al., Dumer et al., and ours can be applied to more general codes than Reed-Muller codes, we give a condition for codes under which these list-decoding algorithms works.},
keywords={},
doi={10.1587/transfun.E96.A.1662},
ISSN={1745-1337},
month={July},}
Copy
TY - JOUR
TI - List Decoding of Reed-Muller Codes Based on a Generalized Plotkin Construction
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1662
EP - 1666
AU - Kenji YASUNAGA
PY - 2013
DO - 10.1587/transfun.E96.A.1662
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E96-A
IS - 7
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - July 2013
AB - Gopalan, Klivans, and Zuckerman proposed a list-decoding algorithm for Reed-Muller codes. Their algorithm works up to a given list-decoding radius. Dumer, Kabatiansky, and Tavernier improved the complexity of the algorithm for binary Reed-Muller codes by using the well-known Plotkin construction. In this study, we propose a list-decoding algorithm for non-binary Reed-Muller codes as a generalization of Dumer et al.'s algorithm. Our algorithm is based on a generalized Plotkin construction, and is more suitable for parallel computation than the algorithm of Gopalan et al. Since the list-decoding algorithms of Gopalan et al., Dumer et al., and ours can be applied to more general codes than Reed-Muller codes, we give a condition for codes under which these list-decoding algorithms works.
ER -