On the square-root bound for QR-codes (Q1106810)

Recently, \textit{W. Heise} and \textit{H. Kellerer} [J. Inform. Process. Cybernet. 23, 113-124 (1987)] gave restrictive necessary conditions on the characteristic p of the underlying field of a quadratic-residue code \({\mathcal Q}\) of length \(n\equiv -1(mod 4)\) if its minimum distance d has the smallest value possible by the square-root bound \(n\leq d(d-1)+1.\) To achieve this goal they introduced the so called minimal graph of the code \({\mathcal Q}.\) In the present paper it is shown that with a slight modification of the graph used the concept of minimal graph applies also to the case when the code length satisfies \(n\equiv 1(mod 4)\). We obtain \(n\leq d(d-1)+1\) if \(n\leq p\quad 2+p+1\) and \(n+p\leq d\quad 2\) if \(n\geq p\quad 2+p+1.\) In the special case when p is not a square modulo n, i.e. when the smallest field of characteristic p over which the QR-code \({\mathcal Q}\) of length n is defined is GF(p 2), it is shown that the bound \(d(d-3)+5\geq n\) obtained in the above mentioned paper by Heise and Kellerer for \(n\equiv -1(mod 4)\) is valid in general. In the proof of this statement it is used that in those QR-codes over GF(p 2) a codeword \(a\) can have at most one entry in \(GF(p\quad 2)\setminus GF(p)\) only if its weight wt(\(a)\) is 0, \((n+1)/2\) or n.