Decoding error-correcting codes with Gröbner bases

The decoding of arbitrary linear block codes is accomplished by solving a system of quadratic equations by means of Buchberger’s algorithm for finding a Gröbner basis. This generalizes the algorithm of Berlekamp-Massey for decoding Reed Solomon, Goppa and cyclic codes up to half the true minimum distance by intro ducing the unknown syndromes as variables. The complexity of this algorithm is exponential and the complexity coefficient is measured under the assumption that the over-determined system of quadratic equations is semi-regular using the results of Bardet et al. [5]. The complexity is compared to existing bounded distance decoding algorithms. Our method can be extended to complete and generic decoding, and to finding the minimum distance and the complete weight distribution.