American Institute of Mathematical Sciences

August  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. Google Scholar [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. Google Scholar [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. Google Scholar [4] J. Borges, J. Rifà and F. I. Solov'eva, On properties of propelinear and transitive binary codes,, in, 5 (2011), 65. Google Scholar [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. Google Scholar [6] M. Hall, Jr., "The Theory of Groups,'', The Macmillan Company, (1959). Google Scholar [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. Google Scholar [8] D. S. Krotov, $\mathbb Z_4$-linear perfect codes (in Russian),, Discrete Analysis Oper. Res., 7 (2000), 78. Google Scholar [9] S. A. Malyugin, On equivalent classes of perfect binary codes of length 15 (in Russian),, Inst. of Mathematics of SB RAS, (2004). Google Scholar [10] S. A. Malyugin, Private communication,, 2004., (). Google Scholar [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. Google Scholar [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. Google Scholar [13] P. R. J. Östergå rd and O. Pottonen, The perfect binary one-error-correcting codes of length 15: Part I - Classification,, preprint, (). Google Scholar [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. Google Scholar [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. Google Scholar [16] J. Rifà, J. M. Basart and L. Huguet, On completely regular propelinear codes,, in, (1989), 341. Google Scholar [17] J. Rifà and J. Pujol, Translation invariant propelinear codes,, IEEE Trans. Inform. Theory, 43 (1997), 590. doi: 10.1109/18.556115. Google Scholar [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. Google Scholar [19] F. I. Solov'eva, On the construction of transitive codes,, Probl. Inform. Trans., 41 (2005), 204. doi: 10.1007/s11122-005-0025-3. Google Scholar [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. Google Scholar [21] Y. L. Vasil'ev, On nongroup close-packed codes,, Probl. Kybernetik, 8 (1962), 92. Google Scholar

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. Google Scholar [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. Google Scholar [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. Google Scholar [4] J. Borges, J. Rifà and F. I. Solov'eva, On properties of propelinear and transitive binary codes,, in, 5 (2011), 65. Google Scholar [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. Google Scholar [6] M. Hall, Jr., "The Theory of Groups,'', The Macmillan Company, (1959). Google Scholar [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. Google Scholar [8] D. S. Krotov, $\mathbb Z_4$-linear perfect codes (in Russian),, Discrete Analysis Oper. Res., 7 (2000), 78. Google Scholar [9] S. A. Malyugin, On equivalent classes of perfect binary codes of length 15 (in Russian),, Inst. of Mathematics of SB RAS, (2004). Google Scholar [10] S. A. Malyugin, Private communication,, 2004., (). Google Scholar [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. Google Scholar [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. Google Scholar [13] P. R. J. Östergå rd and O. Pottonen, The perfect binary one-error-correcting codes of length 15: Part I - Classification,, preprint, (). Google Scholar [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. Google Scholar [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. Google Scholar [16] J. Rifà, J. M. Basart and L. Huguet, On completely regular propelinear codes,, in, (1989), 341. Google Scholar [17] J. Rifà and J. Pujol, Translation invariant propelinear codes,, IEEE Trans. Inform. Theory, 43 (1997), 590. doi: 10.1109/18.556115. Google Scholar [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. Google Scholar [19] F. I. Solov'eva, On the construction of transitive codes,, Probl. Inform. Trans., 41 (2005), 204. doi: 10.1007/s11122-005-0025-3. Google Scholar [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. Google Scholar [21] Y. L. Vasil'ev, On nongroup close-packed codes,, Probl. Kybernetik, 8 (1962), 92. Google Scholar
 [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] 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 [3] 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 [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] 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 [7] 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 [8] 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 [9] 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 [10] 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 [11] 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 [12] 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 [13] 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 [14] 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 [15] 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 [16] 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 [17] 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 [18] 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 [19] 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 [20] 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

2018 Impact Factor: 0.879