Structural properties of binary propelinear codes

Previous Article
Cycle structure of permutation functions over finite fields and their applications
AMC Home
This Issue
Next Article
Canonical- systematic form for codes in hierarchical poset metrics

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

Structural properties of binary propelinear codes

Joaquim Borges ^1, , Ivan Yu. Mogilnykh ^2, , Josep Rifà ^3, and Faina I. Solov'eva ^2,

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

Abstract
Related Papers

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.

Keywords: transitive codes, Propelinear codes, binary perfect codes..

Mathematics Subject Classification: Primary: 94B60; Secondary: 94B2.

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-742. 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-179. 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-1697. doi: 10.1109/18.771247.
[4]	J. Borges, J. Rifà and F. I. Solov'eva, On properties of propelinear and transitive binary codes, in "3rd International Castle Meeting on Coding Theory and Applications (3ICMCTA),'' Servei de Publicacions UAB, 5 (2011), 65-70.
[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-42.
[6]	M. Hall, Jr., "The Theory of Groups,'' The Macmillan Company, New York, 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-319. doi: 10.1109/18.312154.
[8]	D. S. Krotov, $\mathbb Z_4$-linear perfect codes (in Russian), Discrete Analysis Oper. Res., 7 (2000), 78-90; English translation available at arXiv:0710.0198
[9]	S. A. Malyugin, On equivalent classes of perfect binary codes of length 15 (in Russian), Inst. of Mathematics of SB RAS, Novosibirsk, 2004, 34 pp.
[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-115. 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-4660. 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-2592. 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-379. doi: 10.1134/S199047890703012X.
[16]	J. Rifà, J. M. Basart and L. Huguet, On completely regular propelinear codes, in "Proc. 6th Int. Conference, AAECC-6,'' (1989), 341-355.
[17]	J. Rifà and J. Pujol, Translation invariant propelinear codes, IEEE Trans. Inform. Theory, 43 (1997), 590-598. 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-311. doi: 10.1007/PL00004224.
[19]	F. I. Solov'eva, On the construction of transitive codes, Probl. Inform. Trans., 41 (2005), 204-211. 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-335.
[21]	Y. L. Vasil'ev, On nongroup close-packed codes, Probl. Kybernetik, 8 (1962), 92-95.

show all references

References:

[1]	M. R. Best, Binary codes with a minimum distance of four, IEEE Trans. Inform. Theory, 26 (1980), 738-742. 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-179. 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-1697. doi: 10.1109/18.771247.
[4]	J. Borges, J. Rifà and F. I. Solov'eva, On properties of propelinear and transitive binary codes, in "3rd International Castle Meeting on Coding Theory and Applications (3ICMCTA),'' Servei de Publicacions UAB, 5 (2011), 65-70.
[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-42.
[6]	M. Hall, Jr., "The Theory of Groups,'' The Macmillan Company, New York, 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-319. doi: 10.1109/18.312154.
[8]	D. S. Krotov, $\mathbb Z_4$-linear perfect codes (in Russian), Discrete Analysis Oper. Res., 7 (2000), 78-90; English translation available at arXiv:0710.0198
[9]	S. A. Malyugin, On equivalent classes of perfect binary codes of length 15 (in Russian), Inst. of Mathematics of SB RAS, Novosibirsk, 2004, 34 pp.
[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-115. 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-4660. 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-2592. 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-379. doi: 10.1134/S199047890703012X.
[16]	J. Rifà, J. M. Basart and L. Huguet, On completely regular propelinear codes, in "Proc. 6th Int. Conference, AAECC-6,'' (1989), 341-355.
[17]	J. Rifà and J. Pujol, Translation invariant propelinear codes, IEEE Trans. Inform. Theory, 43 (1997), 590-598. 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-311. doi: 10.1007/PL00004224.
[19]	F. I. Solov'eva, On the construction of transitive codes, Probl. Inform. Trans., 41 (2005), 204-211. 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-335.
[21]	Y. L. Vasil'ev, On nongroup close-packed codes, Probl. Kybernetik, 8 (1962), 92-95.

[1]	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
[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]	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
[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]	Luciano Panek, Jerry Anderson Pinheiro, Marcelo Muniz Alves, Marcelo Firer. On perfect poset codes. Advances in Mathematics of Communications, 2020, 14 (3) : 477-489. doi: 10.3934/amc.2020061
[6]	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
[7]	B. K. Dass, Namita Sharma, Rashmi Verma. Characterization of extended Hamming and Golay codes as perfect codes in poset block spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 629-639. doi: 10.3934/amc.2018037
[8]	Markku Lehtinen, Baylie Damtie, Petteri Piiroinen, Mikko Orispää. Perfect and almost perfect pulse compression codes for range spread radar targets. Inverse Problems and Imaging, 2009, 3 (3) : 465-486. doi: 10.3934/ipi.2009.3.465
[9]	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
[10]	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
[11]	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
[12]	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
[13]	Daniel Heinlein, Sascha Kurz. Binary subspace codes in small ambient spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 817-839. doi: 10.3934/amc.2018048
[14]	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
[15]	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
[16]	Xiang Wang, Wenjuan Yin. New nonexistence results on perfect permutation codes under the hamming metric. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021058
[17]	Maura B. Paterson, Douglas R. Stinson. Splitting authentication codes with perfect secrecy: New results, constructions and connections with algebraic manipulation detection codes. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021054
[18]	Ivan Bailera, Joaquim Borges, Josep Rifà. On Hadamard full propelinear codes with associated group $ C_{2t}\times C_2 $. Advances in Mathematics of Communications, 2021, 15 (1) : 35-54. doi: 10.3934/amc.2020041
[19]	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
[20]	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

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Joaquim Borges Ivan Yu. Mogilnykh Josep Rifà Faina I. Solov'eva
on Google Scholar
Joaquim Borges Ivan Yu. Mogilnykh Josep Rifà Faina I. Solov'eva

[Back to Top]