zbMATH — the first resource for mathematics

On the minimum distance of cyclic codes. (English) Zbl 0616.94012
A new lower bound for the minimum distance of cyclic codes is given that includes the earlier BCH, Hartmann-Tzeng and Roos bounds. For n-vectors \b{a} and ḇ let \b{a}\({}^*\underline b\) be the Hadamard product. For an \(m\times n\) matrix \b{A} and \(k\times n\) matrix Ḇ, \b{A}\({}^*\underline B\) is the matrix that has as rows all the products \b{a}\({}^*\underline b\) where \b{a} is a row of \b{A} and ḇ is a row of Ḇ. For \(I\subset \{1,2,...,n\}\) let \b{M}\({}_ I\) be the submatrix of a matrix of \b{M} consisting of the columns designated by I. One of the main tools used in the work is the following Theorem: Let \b{A} and Ḇ be matrices with entries from the field F and let \b{A}\({}^*\underline B\) be a parity check matrix for the code C over F. If I is the support of a codeword in C, then rank(\b{A}\({}_ I)+rank(\underline B_ I)\leq | I|\). In particular, C has minimum distance \(\geq \delta\) if rank(\b{A}\({}_ I)+rank(\underline B_ I)\leq | I|\) for every subset I of \(\{\) 1,2,...,n\(\}\) for which \(| I| <\delta.\)
If \(\alpha\) is a primitive nth root of unity in an extension field \(F_{q^ m}\) over \(F_ q\), the set \(A=\{\alpha^{i_ 1},...,\alpha^{i_{\ell}}\}\) is called a defining set of a code C iff \(c(\xi)=0\) for all \(\xi\in A\) and for all c(x)\(\in C\). The matrix \b{M}(A) is the \(\ell \times n\) matrix whose jth row is \((1,\alpha^{i_ j},...,\alpha^{(n-1)i_ j})\). The results of the paper are obtained by applying the theorem to matrices of the form \b{M}(A). For all binary cyclic codes of length less than or equal to 63, with wo exceptions, the methods obtained yield the true minimum distance. Some results for longer length codes are also given.
Reviewer: I.F.Blake

94B15 Cyclic codes
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
Full Text: DOI