The DOI matches its Crossref record; 16 of the 16 references it cites were found in a registry or an index.
Improved decoding of Reed-Solomon and algebraic-geometry codes
Abstract
Given an error-correcting code over strings of length n and an arbitrary input string also of length n, the list decoding problem is that of finding all codewords within a specified Hamming distance from the input string. We present an improved list decoding algorithm for decoding Reed-Solomon codes. The list decoding problem for Reed-Solomon codes reduces to the following "curve-fitting" problem over a field F: given n points ((x/sub i//spl middot/y/sub i/))/sub i=1//sup n/, x/sub i/, y/sub i//spl isin/F, and a degree parameter k and error parameter e, find all univariate polynomials p of degree at most k such that y/sub i/=p(x/sub i/) for all but at most e values of i/spl isin/(1,...,n). We give an algorithm that solves this problem for e1/3, where the result yields the first asymptotic improvement in four decades. The algorithm generalizes to solve the list decoding problem for other algebraic codes, specifically alternant codes (a class of codes including BCH codes) and algebraic-geometry codes. In both cases, we obtain a list decoding algorithm that corrects up to n-/spl radic/(n(n-d')) errors, where n is the block length and d' is the designed distance of the code. The improvement for the case of algebraic-geometry codes extends the methods of Shokrollahi and Wasserman (see in Proc. 29th Annu. ACM Symp. Theory of Computing, p.241-48, 1998) and improves upon their bound for every choice of n and d'. We also present some other consequences of our algorithm including a solution to a weighted curve-fitting problem, which may be of use in soft-decision decoding algorithms for Reed-Solomon codes.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Theory of Error-Correcting Codes
(1977) · North-Holland Mathematical Library · doi:10.1016/s0924-6509(08)x7030-8 · Cited by 10,760
A Course in Computational Algebraic Number Theory
Cohen, H. (1993) · Graduate Texts in Mathematics · doi:10.1007/978-3-662-02945-9 · Cited by 2,567
Algebraic Coding Theory: Revised Edition
Berlekamp, E. R. (2015) · WORLD SCIENTIFIC eBooks · doi:10.1142/9407 · Cited by 2,474
Theory and practice of error control codes
Blahut, R. E. (1983) · Virtual Defense Library (Ministerio de Defensa) · Cited by 2,066
Algebraic Function Fields and Codes
Stichtenoth, H. (2009) · Graduate Texts in Mathematics · doi:10.1007/978-3-540-76878-4 · Cited by 1,938
Decoding of Reed Solomon Codes beyond the Error-Correction Bound
Sudan, M. (1997) · Journal of Complexity · doi:10.1006/jcom.1997.0439 · Cited by 723
Self-citationThe theory of error-correcting codes
Massey, J. L. (1980) · Proceedings of the IEEE · doi:10.1109/proc.1980.11608 · Cited by 676
van Lint, J. H. (1982) · Graduate Texts in Mathematics · doi:10.1007/978-3-662-07998-0 · Cited by 668
Generalized minimum distance decoding
Forney, G. (1966) · IEEE Transactions on Information Theory · doi:10.1109/tit.1966.1053873 · Cited by 565
Modular curves, Shimura curves, and Goppa codes, better than Varshamov‐Gilbert bound
Tsfasman, M. A., Vlădutx, S. G., & Zink, T. (1982) · Mathematische Nachrichten · doi:10.1002/mana.19821090103 · Cited by 534
SAKATA, S. (2008) · IEICE ESS Fundamentals Review · doi:10.1587/essfr.1.3_44 · Cited by 347
Blake, I., Heegard, C., Hoholdt, T., & Wei, V. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720550 · Cited by 265
Highly resilient correctors for polynomials
Gemmell, P., & Sudan, M. (1992) · Information Processing Letters · doi:10.1016/0020-0190(92)90195-2 · Cited by 169
Self-citationLearning polynomials with queries: The highly noisy case
Goldreich, O., Rubinfeld, R., & Sudan, M. (2002) · Proceedings of IEEE 36th Annual Foundations of Computer Science · doi:10.1109/sfcs.1995.492485 · Cited by 167
Self-citationAlgorithmic complexity in coding theory and the minimum distance problem
Vardy, A. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258559 · Cited by 116
Reconstructing Algebraic Functions from Mixed Data
Ar, S., Lipton, R. J., Rubinfeld, R., & Sudan, M. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539796297577 · Cited by 59
Self-citation
Cited by
Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
Dodis, Y., Reyzin, L., & Smith, A. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24676-3_31 · Cited by 2,038
Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
Dodis, Y., Ostrovsky, R., Reyzin, L., & Smith, A. (2008) · SIAM Journal on Computing · doi:10.1137/060651380 · Cited by 1,717
Biggs, N. L. (2008) · Springer Undergraduate Mathematics Series · doi:10.1007/978-1-84800-273-9_9 · Cited by 751
Algebraic soft-decision decoding of reed-solomon codes
Koetter, R., & Vardy, A. (2003) · IEEE Transactions on Information Theory · doi:10.1109/tit.2003.819332 · Cited by 607
An algebraic approach to IP traceback
Dean, D., Franklin, M., & Stubblefield, A. (2002) · ACM Transactions on Information and System Security · doi:10.1145/505586.505588 · Cited by 447
Metadata
- Authors
- Guruswami, V., & Sudan, M.
- Venue
- IEEE Transactions on Information Theory
- Published
- 1999
- Volume
- 45
- Issue
- 6
- Pages
- 1757-1767
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2032431003
- Cited by
- 998
- References
- 16
- FWCI
- 26.86
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.