November  2010, 4(4): 567-578. doi: 10.3934/amc.2010.4.567

On $q$-ary linear completely regular codes with $\rho=2$ and antipodal dual

1. 

Department of Information and Communications Engineering, Universitat Autònoma de Barcelona, 08193-Bellaterra, Spain, Spain

2. 

Institute for Problems of Information Transmission, Russian Academy of Sciences, Bol’shoi Karetnyi per. 19, GSP-4, Moscow, 127994, Russian Federation

Received  February 2010 Published  November 2010

We characterize all $q$-ary linear completely regular codes with covering radius $\rho=2$ when the dual codes are antipodal. These completely regular codes are extensions of linear completely regular codes with covering radius 1, which we also classify. For $\rho=2$, we give a list of all such codes known to us. This also gives the characterization of two weight linear antipodal codes. Finally, for a class of completely regular codes with covering radius $\rho=2$ and antipodal dual, some interesting properties on self-duality and lifted codes are pointed out.
Citation: Joaquim Borges, Josep Rifà, Victor A. Zinoviev. On $q$-ary linear completely regular codes with $\rho=2$ and antipodal dual. Advances in Mathematics of Communications, 2010, 4 (4) : 567-578. doi: 10.3934/amc.2010.4.567
References:
[1]

L. A. Bassalygo, G. V. Zaitsev and V. A. Zinoviev, Uniformly close-packed codes, Problems Inform. Transmiss., 10 (1974), 9-14.

[2]

L. A. Bassalygo and V. A. Zinoviev, A remark on uniformly packed codes, Problems Inform. Transmiss., 13 (1977), 22-25.

[3]

G. Bogdanova, V. A. Zinoviev and T. J. Todorov, On construction of $q$-ary equidistant codes, Problems Inform. Transmiss., 43 (2007), 13-36. doi: 10.1134/S0032946007040023.

[4]

A. Bonisoli, Every equidistant linear code is a sequence of dual Hamming codes, Ars Combin., 18 (1984), 181-186.

[5]

J. Borges and J. Rifà, On the nonexistence of completely transitive codes, IEEE Trans. Inform. Theory, 46 (2000), 279-280. doi: 10.1109/18.817528.

[6]

J. Borges, J. Rifà and V. A. Zinoviev, Nonexistence of completely transitive codes with error-correcting capability $e > 3$, IEEE Trans. Inform. Theory, 47 (2001), 1619-1621. doi: 10.1109/18.923747.

[7]

J. Borges, J. Rifà and V. A. Zinoviev, On non-antipodal binary completely regular codes, Discrete Math., 308 (2008), 3508-3525. doi: 10.1016/j.disc.2007.07.008.

[8]

J. Borges, J. Rifà and V. A. Zinoviev, On linear completely regular codes with covering radius $\rho=1$, preprint, arXiv:0906.0550v1

[9]

A. E. Brouwer, A. M. Cohen and A. Neumaier, "Distance-Regular Graphs," Springer-Verlag, Berlin, 1989.

[10]

K. A. Bush, Orthogonal arrays of index unity, Ann. Math. Stat., 23 (1952), 426-434. doi: 10.1214/aoms/1177729387.

[11]

A. R. Calderbank and W. M. Kantor, The geometry of two-weight codes, Bull. London Math. Soc., 18 (1986), 97-122. doi: 10.1112/blms/18.2.97.

[12]

C. J. Colbourn and J. H. Dinitz, "The CRC Handbook of Combinatorial Designs," CRC Press, Boca Raton, FL, 1996. doi: 10.1201/9781420049954.

[13]

G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, "Covering Codes," Elsevier Science, The Nederlands, 1997.

[14]

P. Delsarte, Two-weight linear codes and strongly regular graphs, MBLE Research Laboratory, Report R160, 1971.

[15]

P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Research Reports Supplements, 10 (1973), vi+97.

[16]

D. G. Fon-Der-Flaas, Perfect $2$-coloring of hypercube, Siberian Math. J., 48 (2007), 923-930. doi: 10.1007/s11202-007-0075-4.

[17]

D. G. Fon-Der-Flaas, Perfect $2$-coloring of the $12$-cube that attain the bound on correlation immunity, Siberian Electronic Math. Reports, 4 (2007), 292-295.

[18]

M. Giudici and C. E. Praeger, Completely transitive codes in Hamming graphs, Europ. J. Combinatorics, 20 (1999), 647-662. doi: 10.1006/eujc.1999.0313.

[19]

J. M. Goethals and H. C. A. Van Tilborg, Uniformly packed codes, Philips Res., 30 (1975), 9-36.

[20]

J. H. Koolen, W. S. Lee and W. J. Martin, Arithmetic completely regular codes, preprint, arXiv:0911.1826v1

[21]

F. J. MacWilliams, A theorem on the distribution of weights in a systematic code, Bell System Techn. J., 42 (1963), 79-84.

[22]

F. J. MacWilliams and N. J. A. Sloane, "The Theory if Error-Correcting Codes," Elsevier, North-Holland, 1977.

[23]

A. Neumaier, Completely regular codes, Discrete Math., 106/107 (1992), 353-360. doi: 10.1016/0012-365X(92)90565-W.

[24]

J. Rifà and V. A. Zinoviev, On new completely regular $q$-ary codes, Problems Inform. Transmiss., 43 (2007), 97-112. doi: 10.1134/S0032946007020032.

[25]

J. Rifà and V. A. Zinoviev, New completely regular $q$-ary codes, based on Kronecker products, IEEE Trans. Inform. Theory, 56 (2010), 266-272. doi: 10.1109/TIT.2009.2034812.

[26]

J. Rifà and V. A. Zinoviev, On lifting perfect codes, preprint, arXiv:1002.0295

[27]

N. V. Semakov, V. A. Zinoviev and G. V. Zaitsev, Class of maximal equidistant codes, Problems Inform. Transmiss., 5 (1969), 84-87.

[28]

N. V. Semakov, V. A. Zinoviev and G. V. Zaitsev, Uniformly close-packed codes, Problems Inform. Transmiss., 7 (1971), 38-50.

[29]

J. Singer, A theorem in finite projective geometry, and some applications to number theory, Trans. Amer. Math. Soc., 43 (1938), 377-385.

[30]

P. Solé, Completely regular codes and completely transitive codes, Discrete Math., 81 (1990), 193-201. doi: 10.1016/0012-365X(90)90152-8.

[31]

A. Tietäväinen, On the non-existence of perfect codes over finite fields, SIAM J. Appl. Math., 24 (1973), 88-96. doi: 10.1137/0124010.

[32]

H. C. A. Van Tilborg, "Uniformly Packed Codes," Ph.D thesis, Eindhoven Univ. of Tech., 1976.

[33]

V. A. Zinoviev and V. K. Leontiev, The nonexistence of perfect codes over Galois fields, Problems Control Inform. Th., 2 (1973), 16-24.

show all references

References:
[1]

L. A. Bassalygo, G. V. Zaitsev and V. A. Zinoviev, Uniformly close-packed codes, Problems Inform. Transmiss., 10 (1974), 9-14.

[2]

L. A. Bassalygo and V. A. Zinoviev, A remark on uniformly packed codes, Problems Inform. Transmiss., 13 (1977), 22-25.

[3]

G. Bogdanova, V. A. Zinoviev and T. J. Todorov, On construction of $q$-ary equidistant codes, Problems Inform. Transmiss., 43 (2007), 13-36. doi: 10.1134/S0032946007040023.

[4]

A. Bonisoli, Every equidistant linear code is a sequence of dual Hamming codes, Ars Combin., 18 (1984), 181-186.

[5]

J. Borges and J. Rifà, On the nonexistence of completely transitive codes, IEEE Trans. Inform. Theory, 46 (2000), 279-280. doi: 10.1109/18.817528.

[6]

J. Borges, J. Rifà and V. A. Zinoviev, Nonexistence of completely transitive codes with error-correcting capability $e > 3$, IEEE Trans. Inform. Theory, 47 (2001), 1619-1621. doi: 10.1109/18.923747.

[7]

J. Borges, J. Rifà and V. A. Zinoviev, On non-antipodal binary completely regular codes, Discrete Math., 308 (2008), 3508-3525. doi: 10.1016/j.disc.2007.07.008.

[8]

J. Borges, J. Rifà and V. A. Zinoviev, On linear completely regular codes with covering radius $\rho=1$, preprint, arXiv:0906.0550v1

[9]

A. E. Brouwer, A. M. Cohen and A. Neumaier, "Distance-Regular Graphs," Springer-Verlag, Berlin, 1989.

[10]

K. A. Bush, Orthogonal arrays of index unity, Ann. Math. Stat., 23 (1952), 426-434. doi: 10.1214/aoms/1177729387.

[11]

A. R. Calderbank and W. M. Kantor, The geometry of two-weight codes, Bull. London Math. Soc., 18 (1986), 97-122. doi: 10.1112/blms/18.2.97.

[12]

C. J. Colbourn and J. H. Dinitz, "The CRC Handbook of Combinatorial Designs," CRC Press, Boca Raton, FL, 1996. doi: 10.1201/9781420049954.

[13]

G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, "Covering Codes," Elsevier Science, The Nederlands, 1997.

[14]

P. Delsarte, Two-weight linear codes and strongly regular graphs, MBLE Research Laboratory, Report R160, 1971.

[15]

P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Research Reports Supplements, 10 (1973), vi+97.

[16]

D. G. Fon-Der-Flaas, Perfect $2$-coloring of hypercube, Siberian Math. J., 48 (2007), 923-930. doi: 10.1007/s11202-007-0075-4.

[17]

D. G. Fon-Der-Flaas, Perfect $2$-coloring of the $12$-cube that attain the bound on correlation immunity, Siberian Electronic Math. Reports, 4 (2007), 292-295.

[18]

M. Giudici and C. E. Praeger, Completely transitive codes in Hamming graphs, Europ. J. Combinatorics, 20 (1999), 647-662. doi: 10.1006/eujc.1999.0313.

[19]

J. M. Goethals and H. C. A. Van Tilborg, Uniformly packed codes, Philips Res., 30 (1975), 9-36.

[20]

J. H. Koolen, W. S. Lee and W. J. Martin, Arithmetic completely regular codes, preprint, arXiv:0911.1826v1

[21]

F. J. MacWilliams, A theorem on the distribution of weights in a systematic code, Bell System Techn. J., 42 (1963), 79-84.

[22]

F. J. MacWilliams and N. J. A. Sloane, "The Theory if Error-Correcting Codes," Elsevier, North-Holland, 1977.

[23]

A. Neumaier, Completely regular codes, Discrete Math., 106/107 (1992), 353-360. doi: 10.1016/0012-365X(92)90565-W.

[24]

J. Rifà and V. A. Zinoviev, On new completely regular $q$-ary codes, Problems Inform. Transmiss., 43 (2007), 97-112. doi: 10.1134/S0032946007020032.

[25]

J. Rifà and V. A. Zinoviev, New completely regular $q$-ary codes, based on Kronecker products, IEEE Trans. Inform. Theory, 56 (2010), 266-272. doi: 10.1109/TIT.2009.2034812.

[26]

J. Rifà and V. A. Zinoviev, On lifting perfect codes, preprint, arXiv:1002.0295

[27]

N. V. Semakov, V. A. Zinoviev and G. V. Zaitsev, Class of maximal equidistant codes, Problems Inform. Transmiss., 5 (1969), 84-87.

[28]

N. V. Semakov, V. A. Zinoviev and G. V. Zaitsev, Uniformly close-packed codes, Problems Inform. Transmiss., 7 (1971), 38-50.

[29]

J. Singer, A theorem in finite projective geometry, and some applications to number theory, Trans. Amer. Math. Soc., 43 (1938), 377-385.

[30]

P. Solé, Completely regular codes and completely transitive codes, Discrete Math., 81 (1990), 193-201. doi: 10.1016/0012-365X(90)90152-8.

[31]

A. Tietäväinen, On the non-existence of perfect codes over finite fields, SIAM J. Appl. Math., 24 (1973), 88-96. doi: 10.1137/0124010.

[32]

H. C. A. Van Tilborg, "Uniformly Packed Codes," Ph.D thesis, Eindhoven Univ. of Tech., 1976.

[33]

V. A. Zinoviev and V. K. Leontiev, The nonexistence of perfect codes over Galois fields, Problems Control Inform. Th., 2 (1973), 16-24.

[1]

Joaquim Borges, Josep Rifà, Victor Zinoviev. Completely regular codes by concatenating Hamming codes. Advances in Mathematics of Communications, 2018, 12 (2) : 337-349. doi: 10.3934/amc.2018021

[2]

Joaquim Borges, Josep Rifà, Victor A. Zinoviev. Families of nested completely regular codes and distance-regular graphs. Advances in Mathematics of Communications, 2015, 9 (2) : 233-246. doi: 10.3934/amc.2015.9.233

[3]

Manish K. Gupta, Chinnappillai Durairajan. On the covering radius of some modular codes. Advances in Mathematics of Communications, 2014, 8 (2) : 129-137. doi: 10.3934/amc.2014.8.129

[4]

Tsonka Baicheva, Iliya Bouyukliev. On the least covering radius of binary linear codes of dimension 6. Advances in Mathematics of Communications, 2010, 4 (3) : 399-404. doi: 10.3934/amc.2010.4.399

[5]

Rafael Arce-Nazario, Francis N. Castro, Jose Ortiz-Ubarri. On the covering radius of some binary cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 329-338. doi: 10.3934/amc.2017025

[6]

Claude Carlet. Expressing the minimum distance, weight distribution and covering radius of codes by means of the algebraic and numerical normal forms of their indicators. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022047

[7]

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

[8]

Alexander A. Davydov, Stefano Marcugini, Fernanda Pambianco. Upper bounds on the length function for covering codes with covering radius $ R $ and codimension $ tR+1 $. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2021074

[9]

Otávio J. N. T. N. dos Santos, Emerson L. Monte Carmelo. A connection between sumsets and covering codes of a module. Advances in Mathematics of Communications, 2018, 12 (3) : 595-605. doi: 10.3934/amc.2018035

[10]

Rumi Melih Pelen. Three weight ternary linear codes from non-weakly regular bent functions. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022020

[11]

Masaaki Harada, Akihiro Munemasa. On the covering radii of extremal doubly even self-dual codes. Advances in Mathematics of Communications, 2007, 1 (2) : 251-256. doi: 10.3934/amc.2007.1.251

[12]

Olof Heden, Martin Hessler. On linear equivalence and Phelps codes. Advances in Mathematics of Communications, 2010, 4 (1) : 69-81. doi: 10.3934/amc.2010.4.69

[13]

Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005

[14]

Michela Procesi. Quasi-periodic solutions for completely resonant non-linear wave equations in 1D and 2D. Discrete and Continuous Dynamical Systems, 2005, 13 (3) : 541-552. doi: 10.3934/dcds.2005.13.541

[15]

Jingang Zhao, Chi Zhang. Finite-horizon optimal control of discrete-time linear systems with completely unknown dynamics using Q-learning. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1471-1483. doi: 10.3934/jimo.2020030

[16]

Xueting Tian. Topological pressure for the completely irregular set of birkhoff averages. Discrete and Continuous Dynamical Systems, 2017, 37 (5) : 2745-2763. doi: 10.3934/dcds.2017118

[17]

Răzvan M. Tudoran. On the control of stability of periodic orbits of completely integrable systems. Journal of Geometric Mechanics, 2015, 7 (1) : 109-124. doi: 10.3934/jgm.2015.7.109

[18]

Petr Lisoněk, Layla Trummer. Algorithms for the minimum weight of linear codes. Advances in Mathematics of Communications, 2016, 10 (1) : 195-207. doi: 10.3934/amc.2016.10.195

[19]

Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323

[20]

Fernando Hernando, Diego Ruano. New linear codes from matrix-product codes with polynomial units. Advances in Mathematics of Communications, 2010, 4 (3) : 363-367. doi: 10.3934/amc.2010.4.363

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (116)
  • HTML views (0)
  • Cited by (10)

Other articles
by authors

[Back to Top]