Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Decoding Reed-Solomon codes by solving a bilinear system with a Gröbner basis approach

Abstract : Decoding a Reed-Solomon code can be modeled by a bilinear system which can be solved by Gr\"obner basis techniques. We will show that in this particular case, these techniques are much more efficient than for generic bilinear systems with the same number of unknowns and equations (where these techniques have exponential complexity). Here we show that they are able to solve the problem in polynomial time up to the Sudan radius. Moreover, beyond this radius these techniques recover automatically polynomial identities that are at the heart of improvements of the power decoding approach for reaching the Johnson decoding radius. They also allow to derive new polynomial identities that can be used to derive new algebraic decoding algorithms for Reed-Solomon codes. We provide numerical evidence that this sometimes allows to correct efficiently slightly more errors than the Johnson radius.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Jean-Pierre Tillich Connect in order to contact the contributor
Submitted on : Saturday, February 6, 2021 - 12:43:45 PM
Last modification on : Friday, January 21, 2022 - 3:17:01 AM
Long-term archiving on: : Friday, May 7, 2021 - 6:07:18 PM


Files produced by the author(s)


  • HAL Id : hal-03133484, version 1
  • ARXIV : 2102.02544


Magali Bardet, Rocco Mora, Jean-Pierre Tillich. Decoding Reed-Solomon codes by solving a bilinear system with a Gröbner basis approach. 2021. ⟨hal-03133484⟩



Les métriques sont temporairement indisponibles