Title: 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öbner 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.
