Linear nonbinary covering codes and saturating sets in projective spaces

Alexander A. Davydov; Massimo Giulietti; Stefano Marcugini; Fernanda Pambianco

doi:10.3934/amc.2011.5.119

Article Contents

2011, Volume 5, Issue 1: 119-147. Doi: 10.3934/amc.2011.5.119

This issue Previous Article Some remarks on the construction of class polynomials Next Article

Linear nonbinary covering codes and saturating sets in projective spaces

1.
Institute for Information Transmission Problems (Kharkevich institute), Russian Academy of Sciences, GSP-4, Moscow, 127994
2.
Dipartimento di Matematica e Informatica, Università degli Studi di Perugia, 06123, Perugia

Received: September 2010

Published: February 2011

Abstract Related Papers Cited by

Abstract

Let $\mathcal A$_R,q denote a family of covering codes, in which the covering radius $R$ and the size $q$ of the underlying Galois field are fixed, while the code length tends to infinity. The construction of families with small asymptotic covering densities is a classical problem in the area of Covering Codes.
   In this paper, infinite sets of families $\mathcal A$_R,q, where $R$ is fixed but $q$ ranges over an infinite set of prime powers are considered, and the dependence on $q$ of the asymptotic covering densities of $\mathcal A$_R,q is investigated. It turns out that for the upper limit $\mu$_q^*(R,$\mathcal A$_R,q) of the covering density of $\mathcal A$_R,q, the best possibility is $\mu$_q^*(R,$\mathcal A$_R,q)=$O(q)$. The main achievement of the present paper is the construction of optimal infinite sets of families $\mathcal A$_R,q, that is, sets of families such that relation $\mu$_q^*(R,$\mathcal A$_R,q)=$O(q)$ holds, for any covering radius $R\geq 2$.
   We first showed that for a given $R$, to obtain optimal infinite sets of families it is enough to construct $R$ infinite families $\mathcal A$_R,q⁽⁰⁾, $\mathcal A$_R,q⁽¹⁾, $\ldots$, $\mathcal A$_R,q^(R-1) such that, for all $u\geq u$₀, the family $\mathcal A$_R,q^($\gamma$) contains codes of codimension $r$_u$=Ru + \gamma$ and length $f$_q^($\gamma$)($r$_u) where $f$_q^($\gamma$)$(r)=O(q$^(r-R)/R$)$ and $u$₀ is a constant. Then, we were able to construct the necessary families $\mathcal A$_R,q^($\gamma$) for any covering radius $R\geq 2$, with $q$ ranging over the (infinite) set of $R$-th powers. A result of independent interest is that in each of these families $\mathcal A$_R,q^($\gamma$), the lower limit of the covering density is bounded from above by a constant independent of $q$.
   The key tool in our investigation is the design of new small saturating sets in projective spaces over finite fields, which are used as the starting point for the $q$^m-concatenating constructions of covering codes. A new concept of $N$-fold strong blocking set is introduced. As a result of our investigation, many new asymptotic and finite upper bounds on the length function of covering codes and on the smallest sizes of saturating sets, are also obtained. Updated tables for these upper bounds are provided. An analysis and a survey of the known results are presented.

Keywords:

Mathematics Subject Classification: Primary: 94B05, 51E22; Secondary: 94B25, 94B27, 94B65, 51E21.

Citation:

Related Papers

Cited by

References

[1]	S. Aravamuthan and S. Lodha, Covering codes for hats-on-a-line, Electr. J. Combin., 13 (2006), 12.
[2]	A. Ashikhmin and A. Barg, Bounds on the covering radius of linear codes, Des. Codes Crypt., 27 (2002), 261-269.doi: 10.1023/A:1019995105405.
[3]	T. S. Baicheva and E. D. Velikova, Covering radii of ternary linear codes of small dimensions and codimensions, IEEE Trans. Inform. Theory, 43 (1997), 2057-2061; correction: 44 (1998), 2032.
[4]	S. Ball and A. Blokhuis, On the size of a double blocking set in $PG(2,q)$, Finite Fields Appl., 2 (1996), 125-137.doi: 10.1006/ffta.1996.9999.
[5]	S. Ball and J. W. P. Hirschfeld, Bounds on $(n,r)$-arcs and their application to linear codes, Finite Fields Appl., 11 (2005), 326-336.doi: 10.1016/j.ffa.2005.04.002.
[6]	J. Bierbrauer, "Introduction to Coding Theory,'' Chapman & Hall/CRC, 2005.
[7]	J. Bierbrauer and J. Fridrich, Constructing good covering codes for applications in steganography, in "Lecture Notes in Computer Science, Trans. Data Hiding Multimedia Security III'' (ed. Y.Q. Shi), Springer-Verlag, (2008), 1-22.doi: 10.1007/978-3-540-69019-1_1.
[8]	E. Boros, T. Szőnyi and K. Tichler, On defining sets for projective planes, Discrete Math., 303 (2005), 17-31.doi: 10.1016/j.disc.2004.12.015.
[9]	R. A. Brualdi, S. Litsyn and V. S. Pless, Covering radius, in "Handbook of Coding Theory'' (eds. V.S. Pless, W.C. Huffman and R.A. Brualdi), Elsevier, Amsterdam, The Netherlands, (1998), 755-826.
[10]	R. A. Brualdi, V. S. Pless and R. M. Wilson, Short codes with a given covering radius, IEEE Trans. Inform. Theory, 35 (1989), 99-109.doi: 10.1109/18.42181.
[11]	G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, "Covering Codes,'' North-Holland, Amsterdam, The Netherlands, 1997.
[12]	G. Cohen, M. G. Karpovsky, H. F. Mattson, Jr. and J. R. Shatz, Covering radius - Survey and recent results, IEEE Trans. Inform. Theory, 31 (1985), 328-343.doi: 10.1109/TIT.1985.1057043.
[13]	G. Cohen and A. Vardy, Duality between packings and coverings of the Hamming space, Adv. Math. Commun., 1 (2007), 93-97.doi: 10.3934/amc.2007.1.93.
[14]	A. A. Davydov, Construction of linear covering codes, Problems Inform. Transmiss., 26 (1990), 317-331.
[15]	A. A. Davydov, Constructions and families of covering codes and saturated sets of points in projective geometry, IEEE Trans. Inform. Theory, 41 (1995), 2071-2080.doi: 10.1109/18.476339.
[16]	A. A. Davydov, On nonbinary linear codes with covering radius two, in "Proc. 5th Int. Workshop Algebraic Combin. Coding Theory, ACCT-V,'' Unicorn, Shumen, Bulgaria, (1996), 105-110.
[17]	A. A. Davydov, Constructions and families of nonbinary linear codes with covering radius 2, IEEE Trans. Inform. Theory, 45 (1999), 1679-1686.doi: 10.1109/18.771244.
[18]	A. A. Davydov, New constructions of covering codes, Des. Codes Crypt., 22 (2001), 305-316.doi: 10.1023/A:1008302507816.
[19]	A. A. Davydov and A. Y. Drozhzhina-Labinskaya, Constructions, families and tables of binary linear covering codes, IEEE Trans. Inform. Theory, 40 (1994), 1270-1279.doi: 10.1109/18.335937.
[20]	A. A. Davydov, G. Faina, S. Marcugini and F. Pambianco, Computer search in projective planes for the sizes of complete arcs, J. Geom., 82 (2005), 50-62.doi: 10.1007/s00022-004-1719-1.
[21]	A. A. Davydov, G. Faina, S. Marcugini and F. Pambianco, Locally optimal (nonshortening) linear covering codes and minimal saturating sets in projective spaces, IEEE Trans. Inform. Theory, 51 (2005), 4378-4387.doi: 10.1109/TIT.2005.859297.
[22]	A. A. Davydov, G. Faina, S. Marcugini and F. Pambianco, On sizes of complete arcs in $PG(2,q)$, preprint arXiv:1011.3347v2
[23]	A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Linear covering codes over nonbinary finite fields, in "Proc. XI Int. Workshop Algebraic Combin. Coding Theory, ACCT2008,'' Pamporovo, Bulgaria, (2008), 70-75; available online at http://www.moi.math.bas.bg/acct2008/b12.pdf
[24]	A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Linear Covering Codes of Radius 2 and 3, in "Proc. Workshop Coding Theory Days in St. Petersburg,'' St. Petersburg, Russia, (2008), 12-17; available online at http://k36.org/codingdays/proceedings.pdf
[25]	A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, New inductive constructions of complete caps in $PG(N,q)$, $q$ even, J. Combin. Des., 18 (2010), 176-201.
[26]	A. A. Davydov, S. Marcugini and F. Pambianco, On saturating sets in projective spaces, J. Combin. Theory Ser. A, 103 (2003), 1-15.doi: 10.1016/S0097-3165(03)00052-9.
[27]	A. A. Davydov, S. Marcugini and F. Pambianco, Linear codes with covering radius 2,3 and saturating sets in projective geometry, IEEE Trans. Inform. Theory, 50 (2004), 537-541.doi: 10.1109/TIT.2004.825503.
[28]	A. A. Davydov and P. R. J. Östergård, New linear codes with covering radius 2 and odd basis, Des. Codes Crypt., 16 (1999), 29-39.doi: 10.1023/A:1008370224461.
[29]	A. A. Davydov and P. R. J. Östergård, New quaternary linear codes with covering radius 2, Finite Fields Appl., 6 (2000), 164-174.doi: 10.1006/ffta.1999.0271.
[30]	A. A. Davydov and P. R. J. Östergård, On saturating sets in small projective geometries, European J. Combin., 21 (2000), 563-570.doi: 10.1006/eujc.1999.0373.
[31]	A. A. Davydov and P. R. J. Östergård, Linear codes with covering radius $R=2,3$ and codimension $tR$, IEEE Trans. Inform. Theory, 47 (2001), 416-421.doi: 10.1109/18.904551.
[32]	A. A. Davydov and P. R. J. Östergård, Linear codes with covering radius 3, Des. Codes Crypt., 54 (2010), 253-271.doi: 10.1007/s10623-009-9322-y.
[33]	T. Etzion and B. Mounits, Quasi-perfect codes with small distance, IEEE Trans. Inform. Theory, 51 (2005), 3938-3946.doi: 10.1109/TIT.2005.856944.
[34]	G. Exoo, V. Junnila, T. Laihonen and S. Ranto, Constructions for identifying codes, in "Proc. XI Int. Workshop Algebraic Combin. Coding Theory, ACCT2008,'' Pamporovo, Bulgaria, (2008), 92-98; available online at http://www.moi.math.bas.bg/acct2008/b16.pdf
[35]	E. M. Gabidulin and T. Kløve, On the Newton and covering radii of linear codes, IEEE Trans. Inform. Theory, 45 (1999), 2534-2536.doi: 10.1109/18.796399.
[36]	F. Galand and G. Kabatiansky, Information hiding by coverings, in "Proc. IEEE Inform. Theory Workshop, Paris,'' (2003), 151-154.
[37]	M. Giulietti, On small dense sets in Galois planes, Electr. J. Combin., 14 (2007), 75.
[38]	M. Giulietti, Small complete caps in $PG(N,q)$, $q$ even, J. Combin. Des., 15 (2007), 420-436.doi: 10.1002/jcd.20131.
[39]	M. Giulietti, G. Korchmáros, S. Marcugini and F. Pambianco, Arcs in $PG(2,q)$ left invariant by $A_6$, in preparation.
[40]	M. Giulietti and F. Torres, On dense sets related to plane algebraic curves, Ars. Combin., 72 (2004), 33-40.
[41]	R. L. Graham and N. J. A. Sloane, On the covering radius of codes, IEEE Trans. Inform. Theory, 31 (1985), 385-401.doi: 10.1109/TIT.1985.1057039.
[42]	J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'' $2^{nd}$ edition, Oxford University Press, Oxford, 1998.
[43]	J. W. P. Hirschfeld and L. Storme, The packing problem in statistics, coding theory and finite projective spaces, J. Statist. Planning Infer., 72 (1998), 355-380.doi: 10.1016/S0378-3758(98)00043-3.
[44]	C. T. Ho, J. Bruck and R. Agrawal, Partial-sum queries in OLAP data cubes using covering codes, IEEE Trans. Computers, 47 (1998), 1326-1340.doi: 10.1109/12.737680.
[45]	I. S. Honkala, On lengthening of covering codes, Discrete Math., 106/107 (1992), 291-295.doi: 10.1016/0012-365X(92)90556-U.
[46]	G. A. Kabatyansky and V. I. Panchenko, Unit sphere packings and coverings of the Hamming space, Problems Inform. Transmiss., 24 (1988), 261-272.
[47]	G. Kiss, I. Kovács, K. Kutnar, J. Ruff and P. Šparl, A note on a geometric construction of large Cayley graphs of given degree and diameter, Studia Univ. Babeş-Bolyai Math., 54 (2009), 77-84.
[48]	S. J. Kovács, Small saturated sets in finite projective planes, Rend. Mat. Ser. VII, 12 (1992), 157-164.
[49]	I. N. Landjev, Linear codes over finite fields and finite projective geometries, Discrete Math., 213 (2000), 211-244.doi: 10.1016/S0012-365X(99)00183-1.
[50]	A. Lobstein, Covering radius, a bibliography, available online at http://www.infres.enst.fr/~lobstein/bib-a-jour.pdf
[51]	F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'' North-Holland, Amsterdam, The Netherlands, 1977.
[52]	S. Marcugini and F. Pambianco, Minimal 1-saturating sets in $PG(2,q)$, $q\leq 16$, Australas. J. Combin., 28 (2003), 161-169.
[53]	P. R. J. Östergård, New constructions for $q$-ary covering codes, Ars Combin., 52 (1999), 51-63.
[54]	V. S. Pless, W. C. Huffman and R. A. Brualdi, An introduction to algebraic codes, in "Handbook of Coding Theory'' (eds. V.S. Pless, W.C. Huffman and R.A. Brualdi), Elsevier, Amsterdam, The Netherlands, (1998), 3-139.
[55]	R. Struik, "Covering Codes,'' Ph.D thesis, Eindhoven University of Technology, 1994.
[56]	E. Ughi, Saturated configurations of points in projective Galois spaces, European J. Combin., 8 (1987), 325-334.