On the square-root bound for QR-codes
type: Item
instance of: scholarly article
title: On the square-root bound for QR-codes
zbMATH Open document ID: 0651.94013
DOI: 10.1007/BF01222398
author: Ludwig Staiger
published in: Journal of Geometry
publication date: 1988-01-01T00:00:00Z
review text: 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.
reviewed by: Ludwig Staiger
Mathematics Subject Classification ID: 94B15
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4062995
zbMATH Keywords: quadratic-residue code
zbMATH Keywords: minimum distance
zbMATH Keywords: square-root bound
zbMATH Keywords: minimal graph
MaRDI profile type: Publication
cites work: New 5-designs
cites work: On the minimum distance of some quadratic residue codes (Corresp.)
cites work: Q3773828
cites work: Über die Quadratwurzel-Schranke für quadratische-Rest-Codes. (On the square root bound for quadratic-residue codes)
cites work: Über die Wurzelschranke für das Minimalgewicht von Codes
cites work: On minimum weight codewords in QR codes
description: scientific article; zbMATH DE number 4062995