Improved decoding of Reed-Solomon and algebraic-geometry codes

DOI10.1109/18.782097zbMath0958.94036OpenAlexW2032431003WikidataQ56081976 ScholiaQ56081976MaRDI QIDQ4503371

Venkatesan Guruswami

Publication date: 7 September 2000

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/0269083a2194f257bdb81bef84790dcf51947772

zbMATH Keywords

Reed-Solomon codesalgebraic-geometry codeserror-correcting codepolynomial time algorithmslist decoding algorithmweighted curve-fitting problem

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Decoding (94B35)

Related Items (only showing first 100 items - show all)

Soft decoding of short/medium length codes using ordered statistics for quantum key distribution ⋮ Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius ⋮ Asymptotically-good arithmetic secret sharing over \(\mathbb{Z}/p^{\ell }\mathbb{Z}\) with strong multiplication and its applications to efficient MPC ⋮ Weight distributions for projective binary linear codes from Weil sums ⋮ Computing minimal interpolation bases ⋮ Almost separating and almost secure frameproof codes over \(q\)-ary alphabets ⋮ Decoding interleaved Reed-Solomon codes over noisy channels ⋮ Factors of low individual degree polynomials ⋮ On the evaluation codes given by simple \(\delta \)-sequences ⋮ Parallel Hashing via List Recoverability ⋮ Linear-time list recovery of high-rate expander codes ⋮ Parameter choices and a better bound on the list size in the Guruswami-Sudan algorithm for algebraic geometry codes ⋮ On the Doubly Sparse Compressed Sensing Problem ⋮ On the Error-Correcting Radius of Folded Reed–Solomon Code Designs ⋮ Construction of deletion correcting codes using generalized Reed-Solomon codes and their subcodes ⋮ Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice ⋮ On the error distance of extended Reed-Solomon codes ⋮ Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes ⋮ List Decoding of Binary Codes–A Brief Survey of Some Recent Results ⋮ List decoding of repeated codes ⋮ ECC\(^2\): error correcting code and elliptic curve based cryptosystem ⋮ A Decoding Approach to Reed–Solomon Codes from Their Definition ⋮ Multi-point codes from the GGS curves ⋮ A modified Guruswami-Sudan algorithm for decoding Reed-Solomon codes ⋮ List-decoding Barnes-Wall lattices ⋮ Revisiting approximate polynomial common divisor problem and noisy multipolynomial reconstruction ⋮ NP-Hardness of Reed--Solomon Decoding, and the Prouhet--Tarry--Escott Problem ⋮ Generalization of the Lee-O'Sullivan list decoding for one-point AG codes ⋮ Improved probabilistic decoding of interleaved Reed-Solomon codes and folded Hermitian codes ⋮ Multi-trial Guruswami-Sudan decoding for generalised Reed-Solomon codes ⋮ List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques ⋮ Weighted Reed-Muller codes revisited ⋮ On deep holes of standard Reed-Solomon codes ⋮ An Hybrid Approach for Efficient Multicast Stream Authentication over Unsecured Channels ⋮ A two-dimensional improvement for Farr-Gao algorithm ⋮ Multi-point codes over Kummer extensions ⋮ Sudan-decoding generalized geometric Goppa codes. ⋮ Multitrial decoding of concatenated codes using fixed thresholds ⋮ Unnamed Item ⋮ Asymptotic single-trial strategies for GMD decoding with arbitrary error-erasure tradeoff ⋮ On Reed-Solomon codes ⋮ Local List Recovery of High-Rate Tensor Codes and Applications ⋮ Bounds on collaborative decoding of interleaved Hermitian codes and virtual extension ⋮ Computational aspects of retrieving a representation of an algebraic geometry code ⋮ On multi-trial Forney-Kovalev decoding of concatenated codes ⋮ Polynomial root finding over local rings and application to error correcting codes ⋮ Amplification and Derandomization without Slowdown ⋮ Decoding interleaved Reed-Solomon codes beyond their joint error-correcting capability ⋮ List decoding of wavelet codes ⋮ Nonbinary quantum error-correcting codes from algebraic curves ⋮ Interpolation in list decoding of Reed-Solomon codes ⋮ A Syndrome Formulation of the Interpolation Step in the Guruswami-Sudan Algorithm ⋮ Efficient List Decoding of Explicit Codes with Optimal Redundancy ⋮ Improved power decoding of interleaved one-point Hermitian codes ⋮ List decoding of Reed-Solomon codes from a Gröbner basis perspective ⋮ Generic interpolation polynomial for list decoding ⋮ A matrix based list decoding algorithm for linear codes over integer residue rings ⋮ Asymmetric information embedding ⋮ Group homomorphisms as error correcting codes ⋮ Gröbner basis approach to list decoding of algebraic geometry codes ⋮ List Decoding for Binary Goppa Codes ⋮ LIST DECODING OF THE BIORTHOGONAL WAVELET CODE WITH PREDETERMINED CODE DISTANCE ON A FIELD OF ODD CHARACTERISTIC ⋮ ON APPLICATION OF ALGEBRAIC GEOMETRY CODES OF L-CONSTRUCTION IN COPY PROTECTION ⋮ ON LIST DECODING OF WAVELET CODES OVER FINITE FIELDS OF CHARACTERISTIC TWO ⋮ Parameter choices on Guruswami-Sudan algorithm for polynomial reconstruction ⋮ List decoding algorithm based on voting in Gröbner bases for general one-point AG codes ⋮ Row reduction applied to decoding of rank-metric and subspace codes ⋮ More results on the number of zeros of multiplicity at least \(r\) ⋮ List decoding of number field codes ⋮ A fuzzy vault scheme ⋮ Key equations for list decoding of Reed-Solomon codes and how to solve them ⋮ Noisy interpolation of sparse polynomials in finite fields ⋮ Privacy-preserving verifiable delegation of polynomial and matrix functions ⋮ New constructions for IPP codes ⋮ Power decoding Reed-Solomon codes up to the Johnson radius ⋮ Explicit list-decodable codes with optimal rate for computationally bounded channels ⋮ On 2-dimensional insertion-deletion Reed-Solomon codes with optimal asymptotic error-correcting capability ⋮ The Vanishing Ideal of a Finite Set of Points with Multiplicity Structures ⋮ List decoding codes on Garcia-Stichtenoth tower using Gröbner basis ⋮ List decoding of Hermitian codes using Gröbner bases ⋮ Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding ⋮ Separable collusion-secure multimedia codes ⋮ An improved list decoding algorithm for the second order Reed-Muller codes and its applications ⋮ Wild McEliece ⋮ Optimal Rate List Decoding via Derivative Codes ⋮ A Highly Scalable RFID Authentication Protocol ⋮ Improvements on the Johnson bound for Reed-Solomon codes ⋮ Key masking using biometry ⋮ Simplified High-Speed High-Distance List Decoding for Alternant Codes ⋮ A class of I.P.P. codes with efficient identification ⋮ Noisy Chinese remaindering in the Lee norm ⋮ Integer polynomial recovery from outputs and its application to cryptanalysis of a protocol for secure sorting ⋮ On error distance of Reed-Solomon codes ⋮ Power error locating pairs ⋮ Contemporary coding theory. Abstracts from the workshop held March 17--23, 2019 ⋮ On deep holes of generalized Reed-Solomon codes ⋮ Some results on deep holes of generalized projective Reed-Solomon codes ⋮ Scalable secure storage when half the system is faulty ⋮ Formally verified certificate checkers for hardest-to-round computation ⋮ Gröbner basis solutions of constrained interpolation problems

This page was built for publication: Improved decoding of Reed-Solomon and algebraic-geometry codes