Power error locating pairs
type: Item
instance of: scholarly article
title: Power error locating pairs
zbMATH Open document ID: 1443.14027
author: Alain Couvreur
author: Isabella Panaccione
published in: Designs, Codes and Cryptography
publication date: 2020-07-29T00:00:00Z
full work available at URL: https://arxiv.org/abs/1907.11658
review text: For many practical applications to data storage or transmission, some of the more widely used error-correcting codes are the Reed-Solomon codes. Hence, efficient decoding algorithms for these codes, such as the Welch-Berlekamp algorithm that can correct up to half the minimum distance for Reed-Solomon codes, are always welcome. For many theoretical developments, algebraic geometry codes on plane curves are some of the best with respect to the corresponding parameters. Decoding algorithms for algebraic geometry codes on plane curves have a long history: From syndrome decoding with a strong algebraic geometry component to more down-to-earth error correcting pair and list decoding algorithms. On the other hand, for decoding algorithms that can correct errors beyond half the minimum distance of the given code, \textit{M. Sudan} [J. Complex. 13, No. 1, 180--193 (1997; Zbl 0872.68026)] and \textit{V. Guruswami} and \textit{M. Sudan} [IEEE Trans. Inf. Theory 45, No. 6, 1757--1767 (1999; Zbl 0958.94036)] showed that Reed-Solomon codes and algebraic geometry codes over plane curves can be decoded in polynomial time with an asymptotic radius reaching the Johnson bound, \textit{S. M. Johnson} [IRE Trans. Inform. Theory IT 8 No. 3, 203--207 (1962; Zbl 0102.34602)], and decoding radius exceeding half the minimum distance, with a very limited drawback in practice. The main contribution of the article under review is a new algorithm that correct errors beyond half the minimum distance of the given code and that applies to any code with a power error locating pair. The unified approach of this new algorithm allows its application to Reed-Solomon codes and algebraic geometry codes on plane curves as an abstract reformulation of the power decoding algorithm, and also applies to many cyclic codes, with a correction error beyond the Roos bound, \textit{C. Roos} [IEEE Trans. Inf. Theory 29, 330--332 (1983; Zbl 0519.94010)]. In addition to providing a unified approach for decoding beyond…
Mathematics Subject Classification ID: 14G50
Mathematics Subject Classification ID: 94B35
Mathematics Subject Classification ID: 94B27
Mathematics Subject Classification ID: 11T71
zbMATH DE Number: 7225546
zbMATH Keywords: error-correcting code
zbMATH Keywords: Reed-Solomon codes
zbMATH Keywords: algebraic geometry codes
zbMATH Keywords: decoding algorithms
zbMATH Keywords: error correcting pairs
zbMATH Keywords: power decoding
zbMATH Keywords: cyclic codes
reviewed by: Felipe Zaldívar
describes a project that uses: McEliece
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W3040894587
arXiv ID: 1907.11658
cites work: Algebraic coding theory
cites work: Algebraic Coding Theory
cites work: Q3613962
cites work: Additive combinatorics methods in associative algebras
cites work: Cryptanalysis of McEliece Cryptosystem Based on Algebraic Geometry Codes and Their Subcodes
cites work: Polynomial Time Attack on Wild McEliece Over Quadratic Extensions
cites work: Error-locating pairs for cyclic codes
cites work: Q3134857
cites work: Highly resilient correctors for polynomials
cites work: Improved decoding of Reed-Solomon and algebraic-geometry codes
cites work: Q4495303
cites work: Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard
cites work: On the decoding of algebraic-geometric codes
cites work: A course in error-correcting codes.
cites work: Construction and decoding of a class of algebraic geometry codes
cites work: Q3285920
cites work: Codes with prescribed permutation group
cites work: Varieties Defined by Quadratic Equations
cites work: Critical Pairs for the Product Singleton Bound
cites work: Sub-Quadratic Decoding of One-Point Hermitian Codes
cites work: Power Decoding of Reed–Solomon Codes Revisited
cites work: Power decoding Reed-Solomon codes up to the Johnson radius
cites work: On decoding by error location and dependent sets of error positions
cites work: Improved power decoding of interleaved one-point Hermitian codes
cites work: A new lower bound for the minimum distance of a cyclic code
cites work: Introduction to Coding Theory
cites work: On generator matrices of MDS codes (Corresp.)
cites work: Every list-decodable code for high noise has abundant near-optimal rate puncturings
cites work: On the edge-independence number and edge-covering number for regular graphs
cites work: Collaborative Decoding of Interleaved Reed–Solomon Codes and Concatenated Code Designs
cites work: Syndrome Decoding of Reed–Solomon Codes Beyond Half the Minimum Distance Based on Shift-Register Synthesis
cites work: Algebraic Function Fields and Codes
cites work: Decoding of Reed Solomon codes beyond the error-correction bound
cites work: List decoding of algebraic-geometric codes
cites work: Q5393666
cites work: Q3596012
DOI: 10.1007/S10623-020-00774-3
Recommended article: Simplified understanding and efficient decoding of a class of algebraic-geometric codes
Recommended article: On the decoding of algebraic-geometric codes
Recommended article: Fast decoding of codes from algebraic plane curves
Recommended article: Q4003255
Recommended article: On a decoding algorithm for codes on maximal curves
Recommended article: Q4542542
Recommended article: List decoding of algebraic-geometric codes
Recommended article: Algebraic decoding using special divisors
Recommended article: On the decoding of algebraic-geometric codes over F/sub q/ for q&lt;or=16
Recommended article: Improved decoding of Reed-Solomon and algebraic-geometry codes
description: scientific article