Loading...
Please wait, while we are loading the content...
Similar Documents
List Decoding of q-ary Reed-Muller Codes 1) (2004)
| Content Provider | CiteSeerX |
|---|---|
| Author | Pellikaan, Ruud Wu, Xin-Wen |
| Abstract | Abstract. The q-ary Reed-Muller codes RMq(u, m) of length n = qm are a generalization of Reed-Solomon 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 Reed-Muller 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 − � 2u/q) errors. In this paper, following [6], we show that q-ary Reed-Muller codes are subfield subcodes of Reed-Solomon codes over Fqm. Then, using the list-decoding algorithm in [5] for Reed-Solomon codes over Fqm, we present a list-decoding algorithm for q-ary Reed-Muller codes. This algorithm is applicable to codes of any rates, and achieves an error-correction bound n(1 − � (n − d)/n). The algorithm achieves a better error-correction bound than the algorithm in [15], since when u is small, n(1 − � (n − d)/n) = n(1 − � u/q). The implementation of the algorithm requires O(n) field operations in Fq and O(n3) field operations in Fqm under some minor assumption. 1. |
| File Format | |
| Publisher Date | 2004-01-01 |
| Access Restriction | Open |
| Subject Keyword | Q-ary Reed-muller Code List Decoding List-decoding Algorithm Reed-solomon Code Field Operation Error-correction Bound Univariate Case Length Qm Functional Encoding Q-ary Reed-muller Code Rmq Minor Assumption Reed-muller Code Subfield Subcodes Multivariate Case |
| Content Type | Text |
| Resource Type | Article |
