Academic
Publications
New List Decoding Algorithms for Reed-Solomon and BCH Codes

New List Decoding Algorithms for Reed-Solomon and BCH Codes,10.1109/TIT.2008.926355,IEEE Transactions on Information Theory,Yingquan Wu

New List Decoding Algorithms for Reed-Solomon and BCH Codes   (Citations: 16)
BibTex | RIS | RefWorks Download
Abstract In this paper we devise a rational curve fitting algorithm and apply it to the list decoding of Reed-Solomon and BCH codes. The proposed list decoding algorithms exhibit the following significant properties. • The algorithm corrects up to n(1 − √ 1 − D) errors for a (generalized) (n,k,d = n − k + 1) Reed-Solomon code, which matches the Johnson bound, where D ,/2 �
Journal: IEEE Transactions on Information Theory - TIT , vol. 54, no. 8, pp. 3611-3630, 2008
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...I have not attempted to compare my algorithm to Wu’s earlier algorithm [29] for a smaller family of codes, namely narrow-sense binary BCH codes...

    Daniel J. Bernstein. List Decoding for Binary Goppa Codes

    • ...Clearly, the algorithmic complexity of the interpolation step is dominated by the multiplicity . Recently Wu [29] transformed the interpolation problem to a ‘rational interpolation problem’ which involves smaller multiplicity...
    • ...Note that the example is an instance of “one-step-ahead” list decoding [29]...
    • ...interpolation problem has been addressed by Wu in [29]...
    • ...Wu, in [29], has proposed suitable choices for the values of ,a nd satisfying (17) and (20) as...
    • ...On the other hand, the rational factorization step can be done in time using Wu’s rational factorization procedure [29]...
    • ...According to (28) any feasible must satisfy the following inequality which was also derived in Wu [29]...
    • ...Moreover, an upper bound on was derived in [29] as...
    • ...After constructing the bivariate polynomial, the solutions to the rational interpolation problem can be obtained by the rational factorization procedure of [29]...
    • ...4) Compute all factors of of the form using the rational interpolation algorithm from [29]...
    • ...The Kötter algorithm used in step 3 involves operations [12], where is the number of constraints as defined in (18) and is the -degree of the interpolating polynomial . The rational factorization in step 4 can be done in time [29]...

    Mortuza Aliet al. A Parametric Approach to List Decoding of Reed-Solomon Codes Using Int...

    • ...The most computationally intensive operation in the Guruswami-Sudan algorithm is the construction of the bivariate polynomial Q(x;y) whose complexity is dominated by the multiplicity s. Recently, Wu [3] transformed the interpolation problem to a ‘rational interpolation problem’ which involves smaller multiplicity...
    • ...Recently, this rational interpolation problem has been addressed by Wu in [3]...
    • ...= ts Mk2 1: (11) For more details on Wu’s algorithm see [3], [11]...
    • ...According to (15) any feasible s must satisfy the following inequality which was also derived in Wu [3] s 2 (t 2 2(t t0)n) 2s(n t)(t t0) + (t t0) 2 > 0: (16)...
    • ...An upper bound on s was also derived in [3] as...
    • ...C. Computation of the message polynomial After constructing the bivariate polynomial, the solutions to the rational interpolation problem can be obtained by the rational factorization procedure of [3]...
    • ...Firstly, the minimality of L(y) ensures that all solutions correspond to valid codewords and thus we do not need to check for validity as in [2], [3]...

    Mortuza Aliet al. Minimal list decoding of Reed-Solomon codes using a parameterization o...

    • ...In [12], the author presented a new list decoding algorithm for Reed-Solomon and binary BCH codes...
    • ...where the polynomials (x) and b (x) are to be determined [12]...
    • ...algorithm determines all valid error locator polynomials 0 (x) with degree up to t < 1 n p n(n 2d) [12]...
    • ...We observe that the list size of erasing 2d bits is upper bounded by twice (due to applying twice the rational curve fitting algorithm) the degree of y in the bi-variate polynomial Q(x;y) which is computed in the rational interpolation [12]...

    Yingquan Wu. Erasure-only list decoding of Reed-Solomon and BCH codes with applicat...

    • ...Another interesting problem is to generalize the proposed algorithm to the case rational curve fitting problem considered in [22]...

    Peter V. Trifonov. Efficient interpolation in the Guruswami-Sudan algorithm

Sort by: