Power error locating pairs

DOI10.1007/S10623-020-00774-3zbMATH Open1443.14027arXiv1907.11658OpenAlexW3040894587MaRDI QIDQ782853FDOQ782853

Isabella Panaccione, Alain Couvreur

Publication date: 29 July 2020

Published in: Designs, Codes and Cryptography (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1907.11658

zbMATH Keywords

cyclic codesReed-Solomon codesdecoding algorithmsalgebraic geometry codeserror-correcting codeerror correcting pairspower decoding

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Applications to coding theory and cryptography of arithmetic geometry (14G50) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Decoding (94B35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On decoding by error location and dependent sets of error positions
• Algebraic coding theory
• Algebraic Function Fields and Codes
• On generator matrices of MDS codes (Corresp.)
• List decoding of algebraic-geometric codes
• Collaborative Decoding of Interleaved Reed–Solomon Codes and Concatenated Code Designs
• On the edge-independence number and edge-covering number for regular graphs
• Varieties Defined by Quadratic Equations
• Introduction to Coding Theory
• Critical Pairs for the Product Singleton Bound
• Error-locating pairs for cyclic codes
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• Decoding of Reed Solomon codes beyond the error-correction bound
• Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard
• On the decoding of algebraic-geometric codes
• On the decoding of algebraic-geometric codes
• Highly resilient correctors for polynomials
• Algebraic Coding Theory
• Codes with prescribed permutation group
• A new lower bound for the minimum distance of a cyclic code
• A course in error-correcting codes.
• Sub-Quadratic Decoding of One-Point Hermitian Codes
• Construction and decoding of a class of algebraic geometry codes
• Cryptanalysis of McEliece Cryptosystem Based on Algebraic Geometry Codes and Their Subcodes
• Syndrome Decoding of Reed–Solomon Codes Beyond Half the Minimum Distance Based on Shift-Register Synthesis
• Improved power decoding of interleaved one-point Hermitian codes
• Power decoding Reed-Solomon codes up to the Johnson radius
• Polynomial Time Attack on Wild McEliece Over Quadratic Extensions
• Power Decoding of Reed–Solomon Codes Revisited
• Additive combinatorics methods in associative algebras
• Every list-decodable code for high noise has abundant near-optimal rate puncturings

Cited In (1)

• Algebraic-geometry codes and decoding by error-correcting pairs

Uses Software

• McEliece

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• List decoding of algebraic-geometric codes 👍 👎
• On a decoding algorithm for codes on maximal curves 👍 👎
• Improved decoding of Reed-Solomon and algebraic-geometry codes 👍 👎
• On the decoding of algebraic-geometric codes 👍 👎
• On the decoding of algebraic-geometric codes over F/sub q/ for q<or=16 👍 👎
• Fast decoding of codes from algebraic plane curves 👍 👎
• Algebraic decoding using special divisors 👍 👎
• Simplified understanding and efficient decoding of a class of algebraic-geometric codes 👍 👎

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)