NDLI: Linear-Algebraic List Decoding for Variants of Reed

Content Provider	IEEE Xplore Digital Library
Author	Guruswami, V. Wang, C.
Copyright Year	1963
Abstract	Folded Reed-Solomon (RS) codes are an explicit family of codes that achieve the optimal tradeoff between rate and list error-correction capability: specifically, for any ε > 0, Guruswami and Rudra presented an n^{O(1/ ε)} time algorithm to list decode appropriate folded RS codes of rate R from a fraction 1-R-ε of errors. The algorithm is based on multivariate polynomial interpolation and root-finding over extension fields. It was noted by Vadhan that interpolating a linear polynomial suffices for a statement of the above form. Here, we give a simple linear-algebra-based analysis of this variant that eliminates the need for the computationally expensive root-finding step over extension fields (and indeed any mention of extension fields). The entire list-decoding algorithm is linear-algebraic, solving one linear system for the interpolation step, and another linear system to find a small subspace of candidate solutions. Except for the step of pruning this subspace, the algorithm can be implemented to run in quadratic time. We also consider a closely related family of codes, called (order m) derivative codes and defined over fields of large characteristic, which consist of the evaluations of f as well as its first m-1 formal derivatives at N distinct field elements. We show how our linear-algebraic methods for folded RS codes can be used to show that derivative codes can also achieve the above optimal tradeoff. The theoretical drawback of our analysis for folded RS codes and derivative codes is that both the decoding complexity and proven worst-case list-size bound are n^{Ω(1/ ε)}. By combining the above idea with a pseudorandom subset of all polynomials as messages, we get a Monte Carlo construction achieving a list-size bound of O(1/ ε²) which is quite close to the existential O(1/ ε) bound (however, the decoding complexity remains n^{Ω(1/ ε)}). Our work highlights that constructing an explicit subspace-evasive subset that has small intersection with low-dimensional subspaces-an interesting problem in pseudorandomness in its own right-could lead to explicit codes with better list-decoding guarantees.
Sponsorship	IEEE Information Theory Society
Starting Page	3257
Ending Page	3268
Page Count	12
File Size	2835626
File Format	PDF
ISSN	00189448
Volume Number	59
Issue Number	6
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Decoding Polynomials Interpolation Reed-Solomon codes Linear systems Encoding pseudorandomness Adversarial noise model algebraic codes channel coding linear systems list error-correction
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Algebraic List-Decoding of Subspace Codes

The Re-Encoding Transformation in Algebraic List-Decoding of Reed–Solomon Codes

Soft Decoding, Dual BCH Codes, and Better List-Decodable $varepsilon$-Biased Codes

Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy

On Systematic Generator Matrices for Reed–Solomon Codes

Limits to List Decoding Reed–Solomon Codes

On the Average Complexity of Reed–Solomon List Decoders

Linear diophantine equations over polynomials and soft decoding of Reed-Solomon codes

A Parametric Approach to List Decoding of Reed-Solomon Codes Using Interpolation

Linear-Algebraic List Decoding for Variants of Reed–Solomon Codes

Similar Documents

Algebraic List-Decoding of Subspace Codes

The Re-Encoding Transformation in Algebraic List-Decoding of Reed–Solomon Codes

Soft Decoding, Dual BCH Codes, and Better List-Decodable $varepsilon$-Biased Codes

Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy

On Systematic Generator Matrices for Reed–Solomon Codes

Limits to List Decoding Reed&#8211;Solomon Codes

On the Average Complexity of Reed–Solomon List Decoders

Linear diophantine equations over polynomials and soft decoding of Reed-Solomon codes

A Parametric Approach to List Decoding of Reed-Solomon Codes Using Interpolation

Linear-Algebraic List Decoding for Variants of Reed–Solomon Codes

Limits to List Decoding Reed–Solomon Codes