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.

[2]

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

[3]

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

[4]

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

[5]

J. Borges and J. Rifà, On the nonexistence of completely transitive codes,, IEEE Trans. Inform. Theory, 46 (2000), 279. 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. 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. 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, ().

[9]

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

[10]

K. A. Bush, Orthogonal arrays of index unity,, Ann. Math. Stat., 23 (1952), 426. 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. doi: 10.1112/blms/18.2.97.

[12]

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

[13]

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

[14]

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

[15]

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

[16]

D. G. Fon-Der-Flaas, Perfect $2$-coloring of hypercube,, Siberian Math. J., 48 (2007), 923. 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.

[18]

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

[19]

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

[20]

J. H. Koolen, W. S. Lee and W. J. Martin, Arithmetic completely regular codes,, preprint, ().

[21]

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

[22]

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

[23]

A. Neumaier, Completely regular codes,, Discrete Math., 106/107 (1992), 353. 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. 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. doi: 10.1109/TIT.2009.2034812.

[26]

J. Rifà and V. A. Zinoviev, On lifting perfect codes,, preprint, ().

[27]

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

[28]

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

[29]

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

[30]

P. Solé, Completely regular codes and completely transitive codes,, Discrete Math., 81 (1990), 193. 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. doi: 10.1137/0124010.

[32]

H. C. A. Van Tilborg, "Uniformly Packed Codes,", Ph.D thesis, (1976).

[33]

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

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.

[2]

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

[3]

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

[4]

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

[5]

J. Borges and J. Rifà, On the nonexistence of completely transitive codes,, IEEE Trans. Inform. Theory, 46 (2000), 279. 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. 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. 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, ().

[9]

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

[10]

K. A. Bush, Orthogonal arrays of index unity,, Ann. Math. Stat., 23 (1952), 426. 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. doi: 10.1112/blms/18.2.97.

[12]

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

[13]

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

[14]

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

[15]

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

[16]

D. G. Fon-Der-Flaas, Perfect $2$-coloring of hypercube,, Siberian Math. J., 48 (2007), 923. 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.

[18]

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

[19]

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

[20]

J. H. Koolen, W. S. Lee and W. J. Martin, Arithmetic completely regular codes,, preprint, ().

[21]

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

[22]

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

[23]

A. Neumaier, Completely regular codes,, Discrete Math., 106/107 (1992), 353. 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. 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. doi: 10.1109/TIT.2009.2034812.

[26]

J. Rifà and V. A. Zinoviev, On lifting perfect codes,, preprint, ().

[27]

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

[28]

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

[29]

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

[30]

P. Solé, Completely regular codes and completely transitive codes,, Discrete Math., 81 (1990), 193. 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. doi: 10.1137/0124010.

[32]

H. C. A. Van Tilborg, "Uniformly Packed Codes,", Ph.D thesis, (1976).

[33]

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

[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

Xueting Tian. Topological Pressure for the Completely Irregular Set of Birkhoff Averages. Discrete & Continuous Dynamical Systems - A, 2017, 37 (5) : 2745-2763. doi: 10.3934/dcds.2017118

[13]

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

[14]

Nuh Aydin, Nicholas Connolly, Markus Grassl. Some results on the structure of constacyclic codes and new linear codes over $GF(7)$ from quasi-twisted codes. Advances in Mathematics of Communications, 2017, 11 (1) : 245-258. doi: 10.3934/amc.2017016

[15]

John Sheekey. A new family of linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 475-488. doi: 10.3934/amc.2016019

[16]

Peter Vandendriessche. LDPC codes associated with linear representations of geometries. Advances in Mathematics of Communications, 2010, 4 (3) : 405-417. doi: 10.3934/amc.2010.4.405

[17]

Olof Heden, Martin Hessler. On linear equivalence and Phelps codes. Addendum. Advances in Mathematics of Communications, 2011, 5 (3) : 543-546. doi: 10.3934/amc.2011.5.543

[18]

Thomas Feulner. Canonization of linear codes over $\mathbb Z$4. Advances in Mathematics of Communications, 2011, 5 (2) : 245-266. doi: 10.3934/amc.2011.5.245

[19]

Tatsuya Maruta, Yusuke Oya. On optimal ternary linear codes of dimension 6. Advances in Mathematics of Communications, 2011, 5 (3) : 505-520. doi: 10.3934/amc.2011.5.505

[20]

Gérard Cohen, Sihem Mesnager, Hugues Randriam. Yet another variation on minimal linear codes. Advances in Mathematics of Communications, 2016, 10 (1) : 53-61. doi: 10.3934/amc.2016.10.53

2016 Impact Factor: 0.8

Metrics

  • PDF downloads (1)
  • HTML views (0)
  • Cited by (8)

Other articles
by authors

[Back to Top]