List decoding of q-ary Reed-Muller codes

doi:10.1109/TIT.2004.825043

CSpace

	List decoding of q-ary Reed-Muller codes
	Pellikaan, R ; Wu, XW
	2004-04-01
发表期刊	IEEE TRANSACTIONS ON INFORMATION THEORY
ISSN	0018-9448
卷号	50 期号:4 页码:679-682
摘要	The q-ary Reed-Muller (RM) codes RMq(u,m) of length n = q(m) are a generalization of Reed-Solomon (RS) codes, which use polynomials in m variables to encode messages through functional encoding. Using an idea of reducing the multivariate case to the univariate case, randomized list-decoding algorithms for RM codes were given in [1] and [15]. The algorithm in [15] is an improvement of the algorithm in [1], it is applicable to codes RMq(u,m) with u < q/2 and works for up to E < n (1-root2u/q) errors. In this correspondence, following [6], we show that q-ary RM codes are subfield subcodes; of RS codes over F-qm. Then, using the list-decoding algorithm in [5] for RS codes over F,m, we present a list-decoding algorithm for q-ary RM codes. This algorithm is applicable to codes of any rates, and achieves an error-correction bound n(1-root(n-d)/n). The algorithm achieves a better error-correction bound than the algorithm in [15], since when u is small n (1-root/(n-d)/n) = n(1-1rootu/q) The implementation of the algorithm requires O (n) field operations in F-q and O(n(3)) field operations in F-qm under some assumption.
关键词	Guruswami-Sudan algorithm list decoding order domain q-ary Reed-Muller (RM) codes subfield subcodes
DOI	10.1109/TIT.2004.825043
语种	英语
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Information Systems ; Engineering, Electrical & Electronic
WOS记录号	WOS:000220475700010
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/483
专题	中国科学院数学与系统科学研究院
通讯作者	Pellikaan, R
作者单位	1.Tech Univ Eindhoven, Dept Math & Comp Sci, NL-5600 MB Eindhoven, Netherlands 2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Pellikaan, R,Wu, XW. List decoding of q-ary Reed-Muller codes[J]. IEEE TRANSACTIONS ON INFORMATION THEORY,2004,50(4):679-682.
APA	Pellikaan, R,&Wu, XW.(2004).List decoding of q-ary Reed-Muller codes.IEEE TRANSACTIONS ON INFORMATION THEORY,50(4),679-682.
MLA	Pellikaan, R,et al."List decoding of q-ary Reed-Muller codes".IEEE TRANSACTIONS ON INFORMATION THEORY 50.4(2004):679-682.