February  2011, 5(1): 119-147. doi: 10.3934/amc.2011.5.119

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, Russian Federation

2. 

Dipartimento di Matematica e Informatica, Università degli Studi di Perugia, 06123, Perugia, Italy, Italy, Italy

Received  September 2010 Published  February 2011

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(0), $\mathcal A$R,q(1), $\ldots$, $\mathcal A$R,q(R-1) such that, for all $u\geq u$0, 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$0 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.
Citation: Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119
References:
[1]

Electr. J. Combin., 13 (2006), 12.  Google Scholar

[2]

Des. Codes Crypt., 27 (2002), 261-269. doi: 10.1023/A:1019995105405.  Google Scholar

[3]

IEEE Trans. Inform. Theory, 43 (1997), 2057-2061; correction: 44 (1998), 2032.  Google Scholar

[4]

Finite Fields Appl., 2 (1996), 125-137. doi: 10.1006/ffta.1996.9999.  Google Scholar

[5]

Finite Fields Appl., 11 (2005), 326-336. doi: 10.1016/j.ffa.2005.04.002.  Google Scholar

[6]

Chapman & Hall/CRC, 2005.  Google Scholar

[7]

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.  Google Scholar

[8]

Discrete Math., 303 (2005), 17-31. doi: 10.1016/j.disc.2004.12.015.  Google Scholar

[9]

in "Handbook of Coding Theory'' (eds. V.S. Pless, W.C. Huffman and R.A. Brualdi), Elsevier, Amsterdam, The Netherlands, (1998), 755-826.  Google Scholar

[10]

IEEE Trans. Inform. Theory, 35 (1989), 99-109. doi: 10.1109/18.42181.  Google Scholar

[11]

North-Holland, Amsterdam, The Netherlands, 1997.  Google Scholar

[12]

IEEE Trans. Inform. Theory, 31 (1985), 328-343. doi: 10.1109/TIT.1985.1057043.  Google Scholar

[13]

Adv. Math. Commun., 1 (2007), 93-97. doi: 10.3934/amc.2007.1.93.  Google Scholar

[14]

Problems Inform. Transmiss., 26 (1990), 317-331.  Google Scholar

[15]

IEEE Trans. Inform. Theory, 41 (1995), 2071-2080. doi: 10.1109/18.476339.  Google Scholar

[16]

in "Proc. 5th Int. Workshop Algebraic Combin. Coding Theory, ACCT-V,'' Unicorn, Shumen, Bulgaria, (1996), 105-110. Google Scholar

[17]

IEEE Trans. Inform. Theory, 45 (1999), 1679-1686. doi: 10.1109/18.771244.  Google Scholar

[18]

Des. Codes Crypt., 22 (2001), 305-316. doi: 10.1023/A:1008302507816.  Google Scholar

[19]

IEEE Trans. Inform. Theory, 40 (1994), 1270-1279. doi: 10.1109/18.335937.  Google Scholar

[20]

J. Geom., 82 (2005), 50-62. doi: 10.1007/s00022-004-1719-1.  Google Scholar

[21]

IEEE Trans. Inform. Theory, 51 (2005), 4378-4387. doi: 10.1109/TIT.2005.859297.  Google Scholar

[22]

A. A. Davydov, G. Faina, S. Marcugini and F. Pambianco, On sizes of complete arcs in $PG(2,q)$,, preprint , ().   Google Scholar

[23]

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 Google Scholar

[24]

in "Proc. Workshop Coding Theory Days in St. Petersburg,'' St. Petersburg, Russia, (2008), 12-17; available online at http://k36.org/codingdays/proceedings.pdf Google Scholar

[25]

J. Combin. Des., 18 (2010), 176-201.  Google Scholar

[26]

J. Combin. Theory Ser. A, 103 (2003), 1-15. doi: 10.1016/S0097-3165(03)00052-9.  Google Scholar

[27]

IEEE Trans. Inform. Theory, 50 (2004), 537-541. doi: 10.1109/TIT.2004.825503.  Google Scholar

[28]

Des. Codes Crypt., 16 (1999), 29-39. doi: 10.1023/A:1008370224461.  Google Scholar

[29]

Finite Fields Appl., 6 (2000), 164-174. doi: 10.1006/ffta.1999.0271.  Google Scholar

[30]

European J. Combin., 21 (2000), 563-570. doi: 10.1006/eujc.1999.0373.  Google Scholar

[31]

IEEE Trans. Inform. Theory, 47 (2001), 416-421. doi: 10.1109/18.904551.  Google Scholar

[32]

Des. Codes Crypt., 54 (2010), 253-271. doi: 10.1007/s10623-009-9322-y.  Google Scholar

[33]

IEEE Trans. Inform. Theory, 51 (2005), 3938-3946. doi: 10.1109/TIT.2005.856944.  Google Scholar

[34]

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 Google Scholar

[35]

IEEE Trans. Inform. Theory, 45 (1999), 2534-2536. doi: 10.1109/18.796399.  Google Scholar

[36]

in "Proc. IEEE Inform. Theory Workshop, Paris,'' (2003), 151-154. Google Scholar

[37]

Electr. J. Combin., 14 (2007), 75.  Google Scholar

[38]

J. Combin. Des., 15 (2007), 420-436. doi: 10.1002/jcd.20131.  Google Scholar

[39]

M. Giulietti, G. Korchmáros, S. Marcugini and F. Pambianco, Arcs in $PG(2,q)$ left invariant by $A_6$,, in preparation., ().   Google Scholar

[40]

Ars. Combin., 72 (2004), 33-40.  Google Scholar

[41]

IEEE Trans. Inform. Theory, 31 (1985), 385-401. doi: 10.1109/TIT.1985.1057039.  Google Scholar

[42]

Oxford University Press, Oxford, 1998.  Google Scholar

[43]

J. Statist. Planning Infer., 72 (1998), 355-380. doi: 10.1016/S0378-3758(98)00043-3.  Google Scholar

[44]

IEEE Trans. Computers, 47 (1998), 1326-1340. doi: 10.1109/12.737680.  Google Scholar

[45]

Discrete Math., 106/107 (1992), 291-295. doi: 10.1016/0012-365X(92)90556-U.  Google Scholar

[46]

Problems Inform. Transmiss., 24 (1988), 261-272.  Google Scholar

[47]

Studia Univ. Babeş-Bolyai Math., 54 (2009), 77-84.  Google Scholar

[48]

Rend. Mat. Ser. VII, 12 (1992), 157-164.  Google Scholar

[49]

Discrete Math., 213 (2000), 211-244. doi: 10.1016/S0012-365X(99)00183-1.  Google Scholar

[50]

A. Lobstein, Covering radius,, a bibliography, ().   Google Scholar

[51]

North-Holland, Amsterdam, The Netherlands, 1977.  Google Scholar

[52]

Australas. J. Combin., 28 (2003), 161-169.  Google Scholar

[53]

Ars Combin., 52 (1999), 51-63.  Google Scholar

[54]

in "Handbook of Coding Theory'' (eds. V.S. Pless, W.C. Huffman and R.A. Brualdi), Elsevier, Amsterdam, The Netherlands, (1998), 3-139.  Google Scholar

[55]

Ph.D thesis, Eindhoven University of Technology, 1994.  Google Scholar

[56]

European J. Combin., 8 (1987), 325-334.  Google Scholar

show all references

References:
[1]

Electr. J. Combin., 13 (2006), 12.  Google Scholar

[2]

Des. Codes Crypt., 27 (2002), 261-269. doi: 10.1023/A:1019995105405.  Google Scholar

[3]

IEEE Trans. Inform. Theory, 43 (1997), 2057-2061; correction: 44 (1998), 2032.  Google Scholar

[4]

Finite Fields Appl., 2 (1996), 125-137. doi: 10.1006/ffta.1996.9999.  Google Scholar

[5]

Finite Fields Appl., 11 (2005), 326-336. doi: 10.1016/j.ffa.2005.04.002.  Google Scholar

[6]

Chapman & Hall/CRC, 2005.  Google Scholar

[7]

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.  Google Scholar

[8]

Discrete Math., 303 (2005), 17-31. doi: 10.1016/j.disc.2004.12.015.  Google Scholar

[9]

in "Handbook of Coding Theory'' (eds. V.S. Pless, W.C. Huffman and R.A. Brualdi), Elsevier, Amsterdam, The Netherlands, (1998), 755-826.  Google Scholar

[10]

IEEE Trans. Inform. Theory, 35 (1989), 99-109. doi: 10.1109/18.42181.  Google Scholar

[11]

North-Holland, Amsterdam, The Netherlands, 1997.  Google Scholar

[12]

IEEE Trans. Inform. Theory, 31 (1985), 328-343. doi: 10.1109/TIT.1985.1057043.  Google Scholar

[13]

Adv. Math. Commun., 1 (2007), 93-97. doi: 10.3934/amc.2007.1.93.  Google Scholar

[14]

Problems Inform. Transmiss., 26 (1990), 317-331.  Google Scholar

[15]

IEEE Trans. Inform. Theory, 41 (1995), 2071-2080. doi: 10.1109/18.476339.  Google Scholar

[16]

in "Proc. 5th Int. Workshop Algebraic Combin. Coding Theory, ACCT-V,'' Unicorn, Shumen, Bulgaria, (1996), 105-110. Google Scholar

[17]

IEEE Trans. Inform. Theory, 45 (1999), 1679-1686. doi: 10.1109/18.771244.  Google Scholar

[18]

Des. Codes Crypt., 22 (2001), 305-316. doi: 10.1023/A:1008302507816.  Google Scholar

[19]

IEEE Trans. Inform. Theory, 40 (1994), 1270-1279. doi: 10.1109/18.335937.  Google Scholar

[20]

J. Geom., 82 (2005), 50-62. doi: 10.1007/s00022-004-1719-1.  Google Scholar

[21]

IEEE Trans. Inform. Theory, 51 (2005), 4378-4387. doi: 10.1109/TIT.2005.859297.  Google Scholar

[22]

A. A. Davydov, G. Faina, S. Marcugini and F. Pambianco, On sizes of complete arcs in $PG(2,q)$,, preprint , ().   Google Scholar

[23]

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 Google Scholar

[24]

in "Proc. Workshop Coding Theory Days in St. Petersburg,'' St. Petersburg, Russia, (2008), 12-17; available online at http://k36.org/codingdays/proceedings.pdf Google Scholar

[25]

J. Combin. Des., 18 (2010), 176-201.  Google Scholar

[26]

J. Combin. Theory Ser. A, 103 (2003), 1-15. doi: 10.1016/S0097-3165(03)00052-9.  Google Scholar

[27]

IEEE Trans. Inform. Theory, 50 (2004), 537-541. doi: 10.1109/TIT.2004.825503.  Google Scholar

[28]

Des. Codes Crypt., 16 (1999), 29-39. doi: 10.1023/A:1008370224461.  Google Scholar

[29]

Finite Fields Appl., 6 (2000), 164-174. doi: 10.1006/ffta.1999.0271.  Google Scholar

[30]

European J. Combin., 21 (2000), 563-570. doi: 10.1006/eujc.1999.0373.  Google Scholar

[31]

IEEE Trans. Inform. Theory, 47 (2001), 416-421. doi: 10.1109/18.904551.  Google Scholar

[32]

Des. Codes Crypt., 54 (2010), 253-271. doi: 10.1007/s10623-009-9322-y.  Google Scholar

[33]

IEEE Trans. Inform. Theory, 51 (2005), 3938-3946. doi: 10.1109/TIT.2005.856944.  Google Scholar

[34]

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 Google Scholar

[35]

IEEE Trans. Inform. Theory, 45 (1999), 2534-2536. doi: 10.1109/18.796399.  Google Scholar

[36]

in "Proc. IEEE Inform. Theory Workshop, Paris,'' (2003), 151-154. Google Scholar

[37]

Electr. J. Combin., 14 (2007), 75.  Google Scholar

[38]

J. Combin. Des., 15 (2007), 420-436. doi: 10.1002/jcd.20131.  Google Scholar

[39]

M. Giulietti, G. Korchmáros, S. Marcugini and F. Pambianco, Arcs in $PG(2,q)$ left invariant by $A_6$,, in preparation., ().   Google Scholar

[40]

Ars. Combin., 72 (2004), 33-40.  Google Scholar

[41]

IEEE Trans. Inform. Theory, 31 (1985), 385-401. doi: 10.1109/TIT.1985.1057039.  Google Scholar

[42]

Oxford University Press, Oxford, 1998.  Google Scholar

[43]

J. Statist. Planning Infer., 72 (1998), 355-380. doi: 10.1016/S0378-3758(98)00043-3.  Google Scholar

[44]

IEEE Trans. Computers, 47 (1998), 1326-1340. doi: 10.1109/12.737680.  Google Scholar

[45]

Discrete Math., 106/107 (1992), 291-295. doi: 10.1016/0012-365X(92)90556-U.  Google Scholar

[46]

Problems Inform. Transmiss., 24 (1988), 261-272.  Google Scholar

[47]

Studia Univ. Babeş-Bolyai Math., 54 (2009), 77-84.  Google Scholar

[48]

Rend. Mat. Ser. VII, 12 (1992), 157-164.  Google Scholar

[49]

Discrete Math., 213 (2000), 211-244. doi: 10.1016/S0012-365X(99)00183-1.  Google Scholar

[50]

A. Lobstein, Covering radius,, a bibliography, ().   Google Scholar

[51]

North-Holland, Amsterdam, The Netherlands, 1977.  Google Scholar

[52]

Australas. J. Combin., 28 (2003), 161-169.  Google Scholar

[53]

Ars Combin., 52 (1999), 51-63.  Google Scholar

[54]

in "Handbook of Coding Theory'' (eds. V.S. Pless, W.C. Huffman and R.A. Brualdi), Elsevier, Amsterdam, The Netherlands, (1998), 3-139.  Google Scholar

[55]

Ph.D thesis, Eindhoven University of Technology, 1994.  Google Scholar

[56]

European J. Combin., 8 (1987), 325-334.  Google Scholar

[1]

Emily McMillon, Allison Beemer, Christine A. Kelley. Extremal absorbing sets in low-density parity-check codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021003

[2]

Dean Crnković, Nina Mostarac, Bernardo G. Rodrigues, Leo Storme. $ s $-PD-sets for codes from projective planes $ \mathrm{PG}(2,2^h) $, $ 5 \leq h\leq 9 $. Advances in Mathematics of Communications, 2021, 15 (3) : 423-440. doi: 10.3934/amc.2020075

[3]

Tuvi Etzion, Alexander Vardy. On $q$-analogs of Steiner systems and covering designs. Advances in Mathematics of Communications, 2011, 5 (2) : 161-176. doi: 10.3934/amc.2011.5.161

[4]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349

[5]

Yun Gao, Shilin Yang, Fang-Wei Fu. Some optimal cyclic $ \mathbb{F}_q $-linear $ \mathbb{F}_{q^t} $-codes. Advances in Mathematics of Communications, 2021, 15 (3) : 387-396. doi: 10.3934/amc.2020072

[6]

Antonio Cossidente, Sascha Kurz, Giuseppe Marino, Francesco Pavese. Combining subspace codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021007

[7]

Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133

[8]

Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79

[9]

Ricardo A. Podestá, Denis E. Videla. The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021002

[10]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265

[11]

Raj Kumar, Maheshanand Bhaintwal. Duadic codes over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020135

[12]

Joe Gildea, Adrian Korban, Abidin Kaya, Bahattin Yildiz. Constructing self-dual codes from group rings and reverse circulant matrices. Advances in Mathematics of Communications, 2021, 15 (3) : 471-485. doi: 10.3934/amc.2020077

[13]

Muhammad Ajmal, Xiande Zhang. New optimal error-correcting codes for crosstalk avoidance in on-chip data buses. Advances in Mathematics of Communications, 2021, 15 (3) : 487-506. doi: 10.3934/amc.2020078

[14]

Jennifer D. Key, Bernardo G. Rodrigues. Binary codes from $ m $-ary $ n $-cubes $ Q^m_n $. Advances in Mathematics of Communications, 2021, 15 (3) : 507-524. doi: 10.3934/amc.2020079

[15]

Julian Koellermeier, Giovanni Samaey. Projective integration schemes for hyperbolic moment equations. Kinetic & Related Models, 2021, 14 (2) : 353-387. doi: 10.3934/krm.2021008

[16]

Johannes Kellendonk, Lorenzo Sadun. Conjugacies of model sets. Discrete & Continuous Dynamical Systems, 2017, 37 (7) : 3805-3830. doi: 10.3934/dcds.2017161

[17]

Jesús A. Álvarez López, Ramón Barral Lijó, John Hunton, Hiraku Nozawa, John R. Parker. Chaotic Delone sets. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3781-3796. doi: 10.3934/dcds.2021016

[18]

Mario Pulvirenti, Sergio Simonella. On the cardinality of collisional clusters for hard spheres at low density. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3903-3914. doi: 10.3934/dcds.2021021

[19]

Guillermo Reyes, Juan-Luis Vázquez. Long time behavior for the inhomogeneous PME in a medium with slowly decaying density. Communications on Pure & Applied Analysis, 2009, 8 (2) : 493-508. doi: 10.3934/cpaa.2009.8.493

[20]

Krzysztof A. Krakowski, Luís Machado, Fátima Silva Leite. A unifying approach for rolling symmetric spaces. Journal of Geometric Mechanics, 2021, 13 (1) : 145-166. doi: 10.3934/jgm.2020016

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (48)
  • HTML views (0)
  • Cited by (20)

[Back to Top]