Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(6)
Bch Code
List Decoding
Rational Curve
reedsolomon code
berlekamp massey
Reed Solomon
Subscribe
Academic
Publications
New List Decoding Algorithms for ReedSolomon and BCH Codes
New List Decoding Algorithms for ReedSolomon and BCH Codes,10.1109/TIT.2008.926355,IEEE Transactions on Information Theory,Yingquan Wu
Edit
New List Decoding Algorithms for ReedSolomon and BCH Codes
(
Citations: 16
)
BibTex

RIS

RefWorks
Download
Yingquan Wu
Abstract In this paper we devise a
rational curve
fitting algorithm and apply it to the
list decoding
of ReedSolomon 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) ReedSolomon code, which matches the Johnson bound, where D ,/2 �
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 54, no. 8, pp. 36113630, 2008
DOI:
10.1109/TIT.2008.926355
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.
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
More »
Citation Context
(8)
...I have not attempted to compare my algorithm to Wu’s earlier algorithm [
29
] for a smaller family of codes, namely narrowsense 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 “onestepahead” 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 Ali
,
et al.
A Parametric Approach to List Decoding of ReedSolomon Codes Using Int...
...The most computationally intensive operation in the GuruswamiSudan 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 Ali
,
et al.
Minimal list decoding of ReedSolomon codes using a parameterization o...
...In [
12
], the author presented a new list decoding algorithm for ReedSolomon 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 bivariate polynomial Q(x;y) which is computed in the rational interpolation [
12
]...
Yingquan Wu
.
Erasureonly list decoding of ReedSolomon 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 GuruswamiSudan algorithm
References
(25)
Upper bounds for constantweight codes
(
Citations: 67
)
Erik Agrell
,
Alexander Vardy
,
Kenneth Zeger
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 46, no. 7, pp. 23732395, 2000
Bounded distance+1 softdecision ReedSolomon decoding
(
Citations: 59
)
Elwyn R. Berlekamp
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 42, no. 3, pp. 704720, 1996
Algebraic Codes For Data Transmission
(
Citations: 208
)
R. Blahut
Published in 1999.
Errorlocating pairs for cyclic codes
(
Citations: 18
)
Iwan M. Duursma
,
Ralf Kötter
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 40, no. 4, pp. 11081121, 1994
Errorcorrecting codes for list decoding
(
Citations: 71
)
Peter Elias
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 37, no. 1, pp. 512, 1991
Sort by:
Citations
(16)
List Decoding for Binary Goppa Codes
(
Citations: 14
)
Daniel J. Bernstein
Published in 2011.
A Parametric Approach to List Decoding of ReedSolomon Codes Using Interpolation
(
Citations: 1
)
Mortuza Ali
,
Margreta Kuijper
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 57, no. 10, pp. 67186728, 2011
Temperature effect on transport parameters and structure of regenerated cellulose membranes
L. Gelde
,
M. I. Vázquez
,
J. Benavente
Journal:
Polymer Testing  POLYM TEST
, vol. 30, no. 5, pp. 457462, 2011
Minimal list decoding of ReedSolomon codes using a parameterization of Gröbner bases
Mortuza Ali
,
Margreta Kuijper
Conference:
IEEE International Symposium on Information Theory  ISIT
, pp. 840844, 2011
Erasureonly list decoding of ReedSolomon and BCH codes with applications to their product codes
Yingquan Wu
Conference:
IEEE International Symposium on Information Theory  ISIT
, pp. 831834, 2011