Linear covering codes and error-correcting codes for limited-magnitude errors (Q398936): Difference between revisions

A set \(S\subset \mathbb{Z}_q^{\,r}\) is called a \((k_+, k_-, r; q)\)-packing set if, for \(M=\{-k_-, -k_-+1, \ldots, k_+\}\setminus \{0\}\), the linear code \(C_S\subset \mathbb{Z}_q^{\,n}\), using the vectors in S as columns of a parity-check matrix, can correct any single limited-magnitude error from \(M\) (this is the case if all syndroms of the form \(es\) with \(e\in M\) and \(s\in S\) are distinct and non-zero). And \(S\) is called a \((k_+, k_-, r; q)\)-covering set if any vector in \(\mathbb{Z}_q^{\,n}\) can be obtained from a codeword by a single limited-magnitude error from \(M\); (this means that \(\{es\,|\,e\in M, s\in S\}\cup \{0\}=\mathbb{Z}_q^{\;r}\).) In the present paper, a number of covering set constructions are given and the maximal size of a \((k_+, k_-, r; q)\)-packing set and the minimal size of a \((k_+, k_-, r; q)\)-covering set are determined for \(k_+=2\), \(k_-\in\{0,1,2\}\) and all \(q\) and \(r\). (The formula of Theorem 9 is corrected in an erratum, see [ibid. 73, No. 3, 1029 (2014; Zbl 06340020)]). The constructed optimal \((2, k_-, r; q)\)-coverings are used to partially answer a question by \textit{S. Stein} (cf. [Rocky Mt. J. Math. 16, 277--321 (1986; Zbl 0603.52007)], see as well \textit{S. K. Stein} and \textit{S. Szabó} [Algebra and tiling: homomorphisms in the service of geometry. The Carus Mathematical Monographs. 25. Washington, DC: Mathematical Association of America. (1994; Zbl 0930.52003) Chapter 4, Problem 7], namely whether the smallest covering of an abelian group with (the less general) \(M=\{1,\ldots,k_+\}\) is always attainable with a cyclic group. (For \(k_+=2\), the question was answered in the affirmative by \textit{S. Szabó} [Eur. J. Comb. 12, No. 3, 263--266 (1991; Zbl 0728.20045)]).