Gröbner bases and distance of cyclic codes (Q1606071)

Gröbner bases may be used for decoding a linear code by finding rational points of a zero-dimensional algebraic variety associated to the syndrome, error locations, and error magnitudes of \(t\) errors. This has been done by \textit{X. Chen, I. S. Reed, T. Helleseth} and \textit{K. Truong} [IEEE Trans. Inf. Theory 40, No. 5, 1661--1663 (1994; Zbl 0824.94026)], \textit{J. Fitzgerald} and the reviewer [Des. Codes Cryptography 13, No. 2, 147--158 (1998; Zbl 0905.94027)], and \textit{P. Loustaunau} and \textit{E. Von York} [Appl. Algebra Eng. Commun. Comput. 8, No. 6, 469--483 (1997; Zbl 0916.94013)]. By taking the syndrome to be the zero vector, this method may be used to find the minimum distance of a code, thus improving a method first used by \textit{D. Augot} [Finite Fields Appl. 2, No. 2, 138--152 (1996; Zbl 0896.94015)]. When the syndrome is the zero vector, the set of equations defining the variety have ``spurious'' solutions that do not correspond to nonzero codewords. The author computes the number of spurious solutions by a recursive combinatorial formula. By finding a Gröbner basis, one gets the total number of solutions to this system of equations. If this number is greater than the number of spurious solutions, then there exists a nonzero codeword with weight at most \(t\). The author gives examples involving BCH codes and the binary Golay code. Most of the main ideas in this article appear in an unpublished chapter of the dissertation of \textit{J. Fitzgerald} [Applications of Gröbner bases to linear codes, Louisiana State University, Baton Rouge, LA, USA (1996)].