Abstract: We present a new decoding algorithm based on error locating pairs and correcting an amount of errors exceeding half the minimum distance. When applied to Reed--Solomon or algebraic geometry codes, the algorithm is a reformulation of the so--called {em power decoding} algorithm. Asymptotically, it corrects errors up to Sudan's radius. In addition, this new framework applies to any code benefiting from an error locating pair. Similarly to Pellikaan's and K"otter's approach for unique algebraic decoding, our algorithm provides a unified point of view for decoding codes with an algebraic structure beyond the half minimum distance. It permits to get an abstract description of decoding using only codes and linear algebra and without involving the arithmetic of polynomial and rational function algebras used for the definition of the codes themselves. Such algorithms can be valuable for instance for cryptanalysis to construct a decoding algorithm of a code without having access to the hidden algebraic structure of the code.
Recommendations
- Simplified understanding and efficient decoding of a class of algebraic-geometric codes
- On the decoding of algebraic-geometric codes
- Fast decoding of codes from algebraic plane curves
- scientific article; zbMATH DE number 52992
- On a decoding algorithm for codes on maximal curves
- scientific article; zbMATH DE number 1775409
- List decoding of algebraic-geometric codes
- Algebraic decoding using special divisors
- On the decoding of algebraic-geometric codes over F/sub q/ for q<or=16
- Improved decoding of Reed-Solomon and algebraic-geometry codes
Cites work
- scientific article; zbMATH DE number 417878 (Why is no real title available?)
- scientific article; zbMATH DE number 3167429 (Why is no real title available?)
- scientific article; zbMATH DE number 5529001 (Why is no real title available?)
- scientific article; zbMATH DE number 1488179 (Why is no real title available?)
- A course in error-correcting codes.
- A new lower bound for the minimum distance of a cyclic code
- Additive combinatorics
- Additive combinatorics methods in associative algebras
- Algebraic Function Fields and Codes
- Algebraic coding theory
- Algebraic coding theory
- Algebraic geometric codes. Basic notions
- Codes with prescribed permutation group
- Collaborative Decoding of Interleaved Reed–Solomon Codes and Concatenated Code Designs
- Construction and decoding of a class of algebraic geometry codes
- Critical Pairs for the Product Singleton Bound
- Cryptanalysis of McEliece Cryptosystem Based on Algebraic Geometry Codes and Their Subcodes
- Decoding of Reed Solomon codes beyond the error-correction bound
- Error-locating pairs for cyclic codes
- Every list-decodable code for high noise has abundant near-optimal rate puncturings
- Highly resilient correctors for polynomials
- Improved decoding of Reed-Solomon and algebraic-geometry codes
- Improved power decoding of interleaved one-point Hermitian codes
- Introduction to Coding Theory
- List decoding of algebraic-geometric codes
- Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard
- On decoding by error location and dependent sets of error positions
- On generator matrices of MDS codes (Corresp.)
- On the decoding of algebraic-geometric codes
- On the decoding of algebraic-geometric codes
- On the edge-independence number and edge-covering number for regular graphs
- Polynomial Time Attack on Wild McEliece Over Quadratic Extensions
- Power Decoding of Reed–Solomon Codes Revisited
- Power decoding Reed-Solomon codes up to the Johnson radius
- Sub-Quadratic Decoding of One-Point Hermitian Codes
- Syndrome Decoding of Reed–Solomon Codes Beyond Half the Minimum Distance Based on Shift-Register Synthesis
- Varieties Defined by Quadratic Equations
Cited in
(2)
This page was built for publication: Power error locating pairs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q782853)
