2012, 6(3): 329-346. doi: 10.3934/amc.2012.6.329

Structural properties of binary propelinear codes

1. 

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

2. 

Sobolev Institute of Mathematics, Novosibirsk State University, Novosibirsk, Russian Federation, Russian Federation

3. 

Department of Information and Communications Engineering, Universitat Autònoma de Barcelona, 08193-Bellaterra, Cerdanyola del Vallès, Spain

Received  September 2011 Revised  March 2012 Published  August 2012

The paper deals with some structural properties of propelinear binary codes, in particular propelinear perfect binary codes. We consider the connection of transitive codes with propelinear codes and show that there exists a binary code, the Best code of length 10, size 40 and minimum distance 4, which is transitive but not propelinear. We propose several constructions of propelinear codes and introduce a new large class of propelinear perfect binary codes, called normalized propelinear perfect codes. Finally, based on the different values for the rank and the dimension of the kernel, we give a lower bound on the number of nonequivalent propelinear perfect binary codes.
Citation: Joaquim Borges, Ivan Yu. Mogilnykh, Josep Rifà, Faina I. Solov'eva. Structural properties of binary propelinear codes . Advances in Mathematics of Communications, 2012, 6 (3) : 329-346. doi: 10.3934/amc.2012.6.329
References:
[1]

M. R. Best, Binary codes with a minimum distance of four,, IEEE Trans. Inform. Theory, 26 (1980) , 738. doi: 10.1109/TIT.1980.1056269.

[2]

J. Borges, C. Fernández, J. Pujol, J. Rifà and M. Villanueva, $\mathbb Z_2\mathbb Z_4$-linear codes: generator matrices and duality,, Des. Codes Cryptogr., 54 (2010) , 167. doi: 10.1007/s10623-009-9316-9.

[3]

J. Borges and J. Rifà, A characterization of 1-perfect additive codes,, IEEE Trans. Inform. Theory, 45 (1999) , 1688. doi: 10.1109/18.771247.

[4]

J. Borges, J. Rifà and F. I. Solov'eva, On properties of propelinear and transitive binary codes,, in, 5 (2011) , 65.

[5]

J. H. Conway and N. J. A. Sloane, Quaternary constructions for the binary single-error-correcting codes of Julin, Best and others,, Des. Codes Cryptogr., 4 (1994) , 31.

[6]

M. Hall, Jr., "The Theory of Groups,'', The Macmillan Company, (1959) .

[7]

A. R. Hammons, P. V. Kumar, A. R. Calderbank, N. J. A. Sloane and P. Solé, The $\mathbb Z_4$-linearity of Kerdock, Preparata, Goethals and related codes,, IEEE Trans. Inform. Theory, 40 (1994) , 301. doi: 10.1109/18.312154.

[8]

D. S. Krotov, $\mathbb Z_4$-linear perfect codes (in Russian),, Discrete Analysis Oper. Res., 7 (2000) , 78.

[9]

S. A. Malyugin, On equivalent classes of perfect binary codes of length 15 (in Russian),, Inst. of Mathematics of SB RAS, (2004) .

[10]

S. A. Malyugin, Private communication,, 2004., () .

[11]

M. Mollard, A generalized parity function and its use in the construction of perfect codes,, SIAM J. Alg. Disc. Meth., 7 (1986) , 113. doi: 10.1137/0607013.

[12]

P. R. J. Östergå rd and O. Pottonen, The perfect binary one-error-correcting codes of length 15: Part I - Classification,, IEEE Trans. Inform. Theory, 55 (2009) , 4657. doi: 10.1109/TIT.2009.2027525.

[13]

P. R. J. Östergå rd and O. Pottonen, The perfect binary one-error-correcting codes of length 15: Part I - Classification,, preprint, () .

[14]

K. T. Phelps and J. Rifà, On binary 1-perfect additive codes: some structural properties,, IEEE Trans. Inform. Theory, 48 (2002) , 2587. doi: 10.1109/TIT.2002.801474.

[15]

V. N. Potapov, A lower bound for the number of transitive perfect codes,, J. Appl. Industrial Math., 1 (2007) , 373. doi: 10.1134/S199047890703012X.

[16]

J. Rifà, J. M. Basart and L. Huguet, On completely regular propelinear codes,, in, (1989) , 341.

[17]

J. Rifà and J. Pujol, Translation invariant propelinear codes,, IEEE Trans. Inform. Theory, 43 (1997) , 590. doi: 10.1109/18.556115.

[18]

J. Rifà, J. Pujol and J. Borges, 1-perfect uniform and distance invariant partitions,, Appl. Algebra Engin. Commun. Comp., 11 (2001) , 297. doi: 10.1007/PL00004224.

[19]

F. I. Solov'eva, On the construction of transitive codes,, Probl. Inform. Trans., 41 (2005) , 204. doi: 10.1007/s11122-005-0025-3.

[20]

F. I. Solov'eva and S. T. Topalova, On automorphism groups of perfect binary codes and Steiner triple systems,, Probl. Inform. Trans., 36 (2000) , 331.

[21]

Y. L. Vasil'ev, On nongroup close-packed codes,, Probl. Kybernetik, 8 (1962) , 92.

show all references

References:
[1]

M. R. Best, Binary codes with a minimum distance of four,, IEEE Trans. Inform. Theory, 26 (1980) , 738. doi: 10.1109/TIT.1980.1056269.

[2]

J. Borges, C. Fernández, J. Pujol, J. Rifà and M. Villanueva, $\mathbb Z_2\mathbb Z_4$-linear codes: generator matrices and duality,, Des. Codes Cryptogr., 54 (2010) , 167. doi: 10.1007/s10623-009-9316-9.

[3]

J. Borges and J. Rifà, A characterization of 1-perfect additive codes,, IEEE Trans. Inform. Theory, 45 (1999) , 1688. doi: 10.1109/18.771247.

[4]

J. Borges, J. Rifà and F. I. Solov'eva, On properties of propelinear and transitive binary codes,, in, 5 (2011) , 65.

[5]

J. H. Conway and N. J. A. Sloane, Quaternary constructions for the binary single-error-correcting codes of Julin, Best and others,, Des. Codes Cryptogr., 4 (1994) , 31.

[6]

M. Hall, Jr., "The Theory of Groups,'', The Macmillan Company, (1959) .

[7]

A. R. Hammons, P. V. Kumar, A. R. Calderbank, N. J. A. Sloane and P. Solé, The $\mathbb Z_4$-linearity of Kerdock, Preparata, Goethals and related codes,, IEEE Trans. Inform. Theory, 40 (1994) , 301. doi: 10.1109/18.312154.

[8]

D. S. Krotov, $\mathbb Z_4$-linear perfect codes (in Russian),, Discrete Analysis Oper. Res., 7 (2000) , 78.

[9]

S. A. Malyugin, On equivalent classes of perfect binary codes of length 15 (in Russian),, Inst. of Mathematics of SB RAS, (2004) .

[10]

S. A. Malyugin, Private communication,, 2004., () .

[11]

M. Mollard, A generalized parity function and its use in the construction of perfect codes,, SIAM J. Alg. Disc. Meth., 7 (1986) , 113. doi: 10.1137/0607013.

[12]

P. R. J. Östergå rd and O. Pottonen, The perfect binary one-error-correcting codes of length 15: Part I - Classification,, IEEE Trans. Inform. Theory, 55 (2009) , 4657. doi: 10.1109/TIT.2009.2027525.

[13]

P. R. J. Östergå rd and O. Pottonen, The perfect binary one-error-correcting codes of length 15: Part I - Classification,, preprint, () .

[14]

K. T. Phelps and J. Rifà, On binary 1-perfect additive codes: some structural properties,, IEEE Trans. Inform. Theory, 48 (2002) , 2587. doi: 10.1109/TIT.2002.801474.

[15]

V. N. Potapov, A lower bound for the number of transitive perfect codes,, J. Appl. Industrial Math., 1 (2007) , 373. doi: 10.1134/S199047890703012X.

[16]

J. Rifà, J. M. Basart and L. Huguet, On completely regular propelinear codes,, in, (1989) , 341.

[17]

J. Rifà and J. Pujol, Translation invariant propelinear codes,, IEEE Trans. Inform. Theory, 43 (1997) , 590. doi: 10.1109/18.556115.

[18]

J. Rifà, J. Pujol and J. Borges, 1-perfect uniform and distance invariant partitions,, Appl. Algebra Engin. Commun. Comp., 11 (2001) , 297. doi: 10.1007/PL00004224.

[19]

F. I. Solov'eva, On the construction of transitive codes,, Probl. Inform. Trans., 41 (2005) , 204. doi: 10.1007/s11122-005-0025-3.

[20]

F. I. Solov'eva and S. T. Topalova, On automorphism groups of perfect binary codes and Steiner triple systems,, Probl. Inform. Trans., 36 (2000) , 331.

[21]

Y. L. Vasil'ev, On nongroup close-packed codes,, Probl. Kybernetik, 8 (1962) , 92.

[1]

Michael Braun. On lattices, binary codes, and network codes. Advances in Mathematics of Communications, 2011, 5 (2) : 225-232. doi: 10.3934/amc.2011.5.225

[2]

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

[3]

Olof Heden, Fabio Pasticci, Thomas Westerbäck. On the existence of extended perfect binary codes with trivial symmetry group. Advances in Mathematics of Communications, 2009, 3 (3) : 295-309. doi: 10.3934/amc.2009.3.295

[4]

Olof Heden. A survey of perfect codes. Advances in Mathematics of Communications, 2008, 2 (2) : 223-247. doi: 10.3934/amc.2008.2.223

[5]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399

[6]

Steven T. Dougherty, Esengül Saltürk, Steve Szabo. Codes over local rings of order 16 and binary codes. Advances in Mathematics of Communications, 2016, 10 (2) : 379-391. doi: 10.3934/amc.2016012

[7]

Olof Heden, Fabio Pasticci, Thomas Westerbäck. On the symmetry group of extended perfect binary codes of length $n+1$ and rank $n-\log(n+1)+2$. Advances in Mathematics of Communications, 2012, 6 (2) : 121-130. doi: 10.3934/amc.2012.6.121

[8]

Markku Lehtinen, Baylie Damtie, Petteri Piiroinen, Mikko Orispää. Perfect and almost perfect pulse compression codes for range spread radar targets. Inverse Problems & Imaging, 2009, 3 (3) : 465-486. doi: 10.3934/ipi.2009.3.465

[9]

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

[10]

Stefka Bouyuklieva, Anton Malevich, Wolfgang Willems. On the performance of binary extremal self-dual codes. Advances in Mathematics of Communications, 2011, 5 (2) : 267-274. doi: 10.3934/amc.2011.5.267

[11]

Olof Heden, Denis S. Krotov. On the structure of non-full-rank perfect $q$-ary codes. Advances in Mathematics of Communications, 2011, 5 (2) : 149-156. doi: 10.3934/amc.2011.5.149

[12]

Helena Rifà-Pous, Josep Rifà, Lorena Ronquillo. $\mathbb{Z}_2\mathbb{Z}_4$-additive perfect codes in Steganography. Advances in Mathematics of Communications, 2011, 5 (3) : 425-433. doi: 10.3934/amc.2011.5.425

[13]

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

[14]

Christine Bachoc, Gilles Zémor. Bounds for binary codes relative to pseudo-distances of $k$ points. Advances in Mathematics of Communications, 2010, 4 (4) : 547-565. doi: 10.3934/amc.2010.4.547

[15]

Yael Ben-Haim, Simon Litsyn. A new upper bound on the rate of non-binary codes. Advances in Mathematics of Communications, 2007, 1 (1) : 83-92. doi: 10.3934/amc.2007.1.83

[16]

Washiela Fish, Jennifer D. Key, Eric Mwambene. Binary codes from reflexive uniform subset graphs on $3$-sets. Advances in Mathematics of Communications, 2015, 9 (2) : 211-232. doi: 10.3934/amc.2015.9.211

[17]

Suat Karadeniz, Bahattin Yildiz. New extremal binary self-dual codes of length $68$ from $R_2$-lifts of binary self-dual codes. Advances in Mathematics of Communications, 2013, 7 (2) : 219-229. doi: 10.3934/amc.2013.7.219

[18]

Ettore Fornasini, Telma Pinho, Raquel Pinto, Paula Rocha. Composition codes. Advances in Mathematics of Communications, 2016, 10 (1) : 163-177. doi: 10.3934/amc.2016.10.163

[19]

Andreas Klein, Leo Storme. On the non-minimality of the largest weight codewords in the binary Reed-Muller codes. Advances in Mathematics of Communications, 2011, 5 (2) : 333-337. doi: 10.3934/amc.2011.5.333

[20]

Tsonka Baicheva. All binary linear codes of lengths up to 18 or redundancy up to 10 are normal. Advances in Mathematics of Communications, 2011, 5 (4) : 681-686. doi: 10.3934/amc.2011.5.681

2016 Impact Factor: 0.8

Metrics

  • PDF downloads (0)
  • HTML views (0)
  • Cited by (11)

[Back to Top]