Gröbner bases and distance of cyclic codes
type: Item
instance of: scholarly article
title: Gröbner bases and distance of cyclic codes
zbMATH Open document ID: 1034.94013
author: Massimiliano Sala
published in: Applicable Algebra in Engineering, Communication and Computing
publication date: 2002-07-29T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 94B15
Mathematics Subject Classification ID: 13P10
zbMATH DE Number: 1773420
zbMATH Keywords: Gröbner basis
zbMATH Keywords: cyclic code
zbMATH Keywords: minimum distance
reviewed by: Robert F. Lax
MaRDI profile type: Publication
full work available at URL: s002000200096
OpenAlex ID: W2005153931
DOI: 10.1007/S002000200096
description: scientific article; zbMATH DE number 1773420