American Institute of Mathematical Sciences

Advanced
November  2020, 14(4): 631-650. doi: 10.3934/amc.2020035

Abelian non-cyclic orbit codes and multishot subspace codes

Gustavo Terra Bastos 1, , Reginaldo Palazzo Júnior 2, and  Marinês Guerreiro 3,

1. 

Department of Mathematics and Statistics, Federal University of São João del-Rei, Praça Frei Orlando, 170, Centro, São João del-Rei - MG, 36307-352, Brazil
2. 

Department of Communications, FEEC, State University of Campinas, Cidade Universitária Zeferino Vaz - Barão Geraldo, Campinas - SP, 13083-852, Brazil
3. 

Department of Mathematics, Federal University of Viçosa, Avenida Peter Henry Rolfs, s/n, Viçosa - MG, 36570-900, Brazil

Received  November 2018 Revised  June 2019 Published  November 2019

Fund Project: The first author was supported by CAPES and CNPq PhD scholarships

In this paper we characterize the orbit codes as geometrically uniform codes. This characterization is based on the description of all isometries over a projective geometry. In addition, Abelian orbit codes are defined and a construction of Abelian non-cyclic orbit codes is presented. In order to analyze their structures, the concept of geometrically uniform partitions have to be reinterpreted. As a consequence, a substantial reduction in the number of computations needed to obtain the minimum subspace distance of these codes is achieved and established.

An application of orbit codes to multishot subspace codes obtained according to a multi-level construction is provided.

Keywords: Geometrically uniform codes, abelian orbit codes, multishot subspace codes and geometrically uniform partitions.
Mathematics Subject Classification: Primary: 11T71, 94B60; Secondary: 51E99.
Citation: Gustavo Terra Bastos, Reginaldo Palazzo Júnior, Marinês Guerreiro. Abelian non-cyclic orbit codes and multishot subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 631-650. doi: 10.3934/amc.2020035
References:
[1]

R. Ahlswede, N. Cai, R. Li and R. W. Yeung, Network information flow, IEEE Trans. Inform. Theory, 46 (2000), 1204-1216.  doi: 10.1109/18.850663.  Google Scholar

[2]

R. Baer, Linear Algebra and Projective Geometry, Academic Press Inc., New York, 1952.  Google Scholar

[3]

F. Bardestani and A. Iranmanesh, Cyclic orbit codes with the normalizer of a singer subgroup, J. Sci. Islam. Repub. Iran, 26 (2015), 49-55.   Google Scholar

[4]

E. Biglieri and M. Elia, Multidimensional modulation and coding for band-limited digital channels, IEEE Trans. Inform. Theory, 34 (1988), 803-809.  doi: 10.1109/18.9777.  Google Scholar

[5]

A. R. Calderbank, Multilevel codes and multistage decoding, IEEE Trans. Comm., 37 (1989), 222-229.  doi: 10.1109/26.20095.  Google Scholar

[6]

B. Chen and H. Liu, Constructions of cyclic constant dimension codes, Des. Codes Cryptogr., 86 (2018), 1267-1279.  doi: 10.1007/s10623-017-0394-9.  Google Scholar

[7]

J.-J. Climent, V. Requena and X. S.-Escrivà, A construction of Abelian non-cyclic orbit codes, Cryptogr. Commun., 11 (2019), 839-852.  doi: 10.1007/s12095-018-0306-5.  Google Scholar

[8]

J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, Fundamental Principles of Mathematical Sciences, 290, Springer-Verlag, New York, 1999. doi: 10.1007/978-1-4757-6568-7.  Google Scholar

[9]

P. Delsarte, Bilinear forms over a finite field, with applications to coding theory, J. Combin. Theory Ser. A, 25 (1978), 226-241.  doi: 10.1016/0097-3165(78)90015-8.  Google Scholar

[10]

T. Etzion and A. Vardy, Error-correcting codes in projective space, IEEE Trans. Inform. Theory, 57 (2011), 1165-1173.  doi: 10.1109/TIT.2010.2095232.  Google Scholar

[11]

G. Forney Jr., Geometrically uniform codes, IEEE Trans. Inform. Theory, 37 (1991), 1241-1260.  doi: 10.1109/18.133243.  Google Scholar

[12]

È. M. Gabidulin, Theory of codes with maximum rank distance, Problemy Peredachi Informatsii, 21 (1985), 3-16.   Google Scholar

[13]

J. T. Goozeff, Abelian p-subgroups of the general linear group, J. Austral. Math. Soc., 11 (1970), 257-259.  doi: 10.1017/S1446788700006613.  Google Scholar

[14]

D. Heinlein, M. Kiermaier, S. Kurz and A. Wassermann, Tables of subspace codes, preprint, arXiv: 1601.02864. Google Scholar

[15]

H. Imai and S. Hirakawa, A new multilevel coding method using error-correcting codes, IEEE Trans. Inform. Theory, 23 (1977), 371-377.  doi: 10.1109/TIT.1977.1055718.  Google Scholar

[16]

I. M. Isaacs, Finite Group Theory, Graduate Studies in Mathematics, 92, American Mathematical Society, Providence, RI, 2008. doi: 10.1090/gsm/092.  Google Scholar

[17]

A. Khaleghi, D. Silva and F. R. Kschischang, Subspace codes, in Cryptography and Coding, Lecture Notes in Comput. Sci., 5921, Springer, Berlin, 2009, 1-21. doi: 10.1007/978-3-642-10868-6_1.  Google Scholar

[18]

R. Köetter and F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3579-3591.  doi: 10.1109/TIT.2008.926449.  Google Scholar

[19]

A. Kohnert and S. Kurz, Construction of large constant dimension codes with a prescribed minimum distance, in Mathematical Methods in Computer Science, Lecture Notes in Comput. Sci., 5393, Springer, Berlin, 2008, 31-42. doi: 10.1007/978-3-540-89994-5_4.  Google Scholar

[20]

H. A. Loeliger, Signal sets matched to groups, IEEE Trans. Inform. Theory, 37 (1991), 1675-1682.  doi: 10.1109/18.104333.  Google Scholar

[21]

H. G-Luerssen, K. Morrison and C. Troha, Cyclic orbit codes and stabilizer subfields, Adv. Math. Commun., 9 (2015), 177-197.  doi: 10.3934/amc.2015.9.177.  Google Scholar

[22]

F. Manganiello, E. Gorla and J. Rosenthal, Spread codes and spread decoding in network coding, IEEE International Symposium on Information Theory, (2008), 881-885.  doi: 10.1109/ISIT.2008.4595113.  Google Scholar

[23]

R. W. Nobrega and B. F. Uchoa-Filho, Multishot codes for network coding: Bounds and a multilevel construction, IEEE International Symposium on Information Theory, (2009), 428-432.  doi: 10.1109/ISIT.2009.5205750.  Google Scholar

[24]

J. J. Rotman, An Introduction to the Theory of Groups, Graduate Texts in Mathematics, 148, Springer-Verlag, New York, 1995. doi: 10.1007/978-1-4612-4176-8.  Google Scholar

[25]

D. Slepian, Group codes for the Gaussian channel, Bell System Tech. J., 47 (1968), 575-602.  doi: 10.1002/j.1538-7305.1968.tb02486.x.  Google Scholar

[26]

D. A. Suprunenko, Matrix Groups, Translations of Mathematical Monographs, 45, American Mathematical Society, Providence, RI, 1976.  Google Scholar

[27]

A.-L. Trautmann, Isometry and automorphisms of constant dimension codes, Adv. Math. Commun., 7 (2013), 147-160.  doi: 10.3934/amc.2013.7.147.  Google Scholar

[28]

A.-L. Trautmann, F. Manganiello, M. Braun and J. Rosenthal, Cyclic orbit codes, IEEE Trans. Inform. Theory, 59 (2013), 7386-7404.  doi: 10.1109/TIT.2013.2274266.  Google Scholar

[29]

A.-L. Trautmann, F. Manganiello and J. Rosenthal, Orbit codes - A new concept in the area of network coding, IEEE Information Theory Workshop, Dublin, Ireland, 2010, 1-4. doi: 10.1109/CIG.2010.5592788.  Google Scholar

[30]

Z. Wan, On geometrically uniform signal sets and signal sets matched to groups, IEEE International Symposium on Information Theory, San Antonio, 1993,179pp. doi: 10.1109/ISIT.1993.748493.  Google Scholar

show all references

References:
[1]

R. Ahlswede, N. Cai, R. Li and R. W. Yeung, Network information flow, IEEE Trans. Inform. Theory, 46 (2000), 1204-1216.  doi: 10.1109/18.850663.  Google Scholar

[2]

R. Baer, Linear Algebra and Projective Geometry, Academic Press Inc., New York, 1952.  Google Scholar

[3]

F. Bardestani and A. Iranmanesh, Cyclic orbit codes with the normalizer of a singer subgroup, J. Sci. Islam. Repub. Iran, 26 (2015), 49-55.   Google Scholar

[4]

E. Biglieri and M. Elia, Multidimensional modulation and coding for band-limited digital channels, IEEE Trans. Inform. Theory, 34 (1988), 803-809.  doi: 10.1109/18.9777.  Google Scholar

[5]

A. R. Calderbank, Multilevel codes and multistage decoding, IEEE Trans. Comm., 37 (1989), 222-229.  doi: 10.1109/26.20095.  Google Scholar

[6]

B. Chen and H. Liu, Constructions of cyclic constant dimension codes, Des. Codes Cryptogr., 86 (2018), 1267-1279.  doi: 10.1007/s10623-017-0394-9.  Google Scholar

[7]

J.-J. Climent, V. Requena and X. S.-Escrivà, A construction of Abelian non-cyclic orbit codes, Cryptogr. Commun., 11 (2019), 839-852.  doi: 10.1007/s12095-018-0306-5.  Google Scholar

[8]

J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, Fundamental Principles of Mathematical Sciences, 290, Springer-Verlag, New York, 1999. doi: 10.1007/978-1-4757-6568-7.  Google Scholar

[9]

P. Delsarte, Bilinear forms over a finite field, with applications to coding theory, J. Combin. Theory Ser. A, 25 (1978), 226-241.  doi: 10.1016/0097-3165(78)90015-8.  Google Scholar

[10]

T. Etzion and A. Vardy, Error-correcting codes in projective space, IEEE Trans. Inform. Theory, 57 (2011), 1165-1173.  doi: 10.1109/TIT.2010.2095232.  Google Scholar

[11]

G. Forney Jr., Geometrically uniform codes, IEEE Trans. Inform. Theory, 37 (1991), 1241-1260.  doi: 10.1109/18.133243.  Google Scholar

[12]

È. M. Gabidulin, Theory of codes with maximum rank distance, Problemy Peredachi Informatsii, 21 (1985), 3-16.   Google Scholar

[13]

J. T. Goozeff, Abelian p-subgroups of the general linear group, J. Austral. Math. Soc., 11 (1970), 257-259.  doi: 10.1017/S1446788700006613.  Google Scholar

[14]

D. Heinlein, M. Kiermaier, S. Kurz and A. Wassermann, Tables of subspace codes, preprint, arXiv: 1601.02864. Google Scholar

[15]

H. Imai and S. Hirakawa, A new multilevel coding method using error-correcting codes, IEEE Trans. Inform. Theory, 23 (1977), 371-377.  doi: 10.1109/TIT.1977.1055718.  Google Scholar

[16]

I. M. Isaacs, Finite Group Theory, Graduate Studies in Mathematics, 92, American Mathematical Society, Providence, RI, 2008. doi: 10.1090/gsm/092.  Google Scholar

[17]

A. Khaleghi, D. Silva and F. R. Kschischang, Subspace codes, in Cryptography and Coding, Lecture Notes in Comput. Sci., 5921, Springer, Berlin, 2009, 1-21. doi: 10.1007/978-3-642-10868-6_1.  Google Scholar

[18]

R. Köetter and F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3579-3591.  doi: 10.1109/TIT.2008.926449.  Google Scholar

[19]

A. Kohnert and S. Kurz, Construction of large constant dimension codes with a prescribed minimum distance, in Mathematical Methods in Computer Science, Lecture Notes in Comput. Sci., 5393, Springer, Berlin, 2008, 31-42. doi: 10.1007/978-3-540-89994-5_4.  Google Scholar

[20]

H. A. Loeliger, Signal sets matched to groups, IEEE Trans. Inform. Theory, 37 (1991), 1675-1682.  doi: 10.1109/18.104333.  Google Scholar

[21]

H. G-Luerssen, K. Morrison and C. Troha, Cyclic orbit codes and stabilizer subfields, Adv. Math. Commun., 9 (2015), 177-197.  doi: 10.3934/amc.2015.9.177.  Google Scholar

[22]

F. Manganiello, E. Gorla and J. Rosenthal, Spread codes and spread decoding in network coding, IEEE International Symposium on Information Theory, (2008), 881-885.  doi: 10.1109/ISIT.2008.4595113.  Google Scholar

[23]

R. W. Nobrega and B. F. Uchoa-Filho, Multishot codes for network coding: Bounds and a multilevel construction, IEEE International Symposium on Information Theory, (2009), 428-432.  doi: 10.1109/ISIT.2009.5205750.  Google Scholar

[24]

J. J. Rotman, An Introduction to the Theory of Groups, Graduate Texts in Mathematics, 148, Springer-Verlag, New York, 1995. doi: 10.1007/978-1-4612-4176-8.  Google Scholar

[25]

D. Slepian, Group codes for the Gaussian channel, Bell System Tech. J., 47 (1968), 575-602.  doi: 10.1002/j.1538-7305.1968.tb02486.x.  Google Scholar

[26]

D. A. Suprunenko, Matrix Groups, Translations of Mathematical Monographs, 45, American Mathematical Society, Providence, RI, 1976.  Google Scholar

[27]

A.-L. Trautmann, Isometry and automorphisms of constant dimension codes, Adv. Math. Commun., 7 (2013), 147-160.  doi: 10.3934/amc.2013.7.147.  Google Scholar

[28]

A.-L. Trautmann, F. Manganiello, M. Braun and J. Rosenthal, Cyclic orbit codes, IEEE Trans. Inform. Theory, 59 (2013), 7386-7404.  doi: 10.1109/TIT.2013.2274266.  Google Scholar

[29]

A.-L. Trautmann, F. Manganiello and J. Rosenthal, Orbit codes - A new concept in the area of network coding, IEEE Information Theory Workshop, Dublin, Ireland, 2010, 1-4. doi: 10.1109/CIG.2010.5592788.  Google Scholar

[30]

Z. Wan, On geometrically uniform signal sets and signal sets matched to groups, IEEE International Symposium on Information Theory, San Antonio, 1993,179pp. doi: 10.1109/ISIT.1993.748493.  Google Scholar

Table 1.  Interdistance sets $ D\left( {\left\{ V \right\},{C_H}\left( {{\alpha ^i}V} \right)} \right)$, for $ 1 \leq i \leq 4 $
$ d_S (.,.) $ $ \alpha^1 $ $ \alpha^{10} $ $ \alpha^{19} $ $ \alpha^{28} $ $ \alpha^{37} $ $ \alpha^{46} $ $ \alpha^{55} $
$ \alpha^0 $ 4 4 6 6 6 4 6
$ d_S (.,.) $ $ \alpha^2 $ $ \alpha^{11} $ $ \alpha^{20} $ $ \alpha^{29} $ $ \alpha^{38} $ $ \alpha^{47} $ $ \alpha^{56} $
$ \alpha^0 $ 4 6 4 4 6 4 6
$ d_S (.,.) $ $ \alpha^3 $ $ \alpha^{12} $ $ \alpha^{21} $ $ \alpha^{30} $ $ \alpha^{39} $ $ \alpha^{48} $ $ \alpha^{57} $
$ \alpha^0 $ 4 4 6 4 4 4 4
$ d_S (.,.) $ $ \alpha^4 $ $ \alpha^{13} $ $ \alpha^{22} $ $ \alpha^{31} $ $ \alpha^{40} $ $ \alpha^{49} $ $ \alpha^{58} $
$ \alpha^0 $ 4 6 6 4 4 6 4
Table Options

Download as excel

$ d_S (.,.) $ $ \alpha^1 $ $ \alpha^{10} $ $ \alpha^{19} $ $ \alpha^{28} $ $ \alpha^{37} $ $ \alpha^{46} $ $ \alpha^{55} $
$ \alpha^0 $ 4 4 6 6 6 4 6
$ d_S (.,.) $ $ \alpha^2 $ $ \alpha^{11} $ $ \alpha^{20} $ $ \alpha^{29} $ $ \alpha^{38} $ $ \alpha^{47} $ $ \alpha^{56} $
$ \alpha^0 $ 4 6 4 4 6 4 6
$ d_S (.,.) $ $ \alpha^3 $ $ \alpha^{12} $ $ \alpha^{21} $ $ \alpha^{30} $ $ \alpha^{39} $ $ \alpha^{48} $ $ \alpha^{57} $
$ \alpha^0 $ 4 4 6 4 4 4 4
$ d_S (.,.) $ $ \alpha^4 $ $ \alpha^{13} $ $ \alpha^{22} $ $ \alpha^{31} $ $ \alpha^{40} $ $ \alpha^{49} $ $ \alpha^{58} $
$ \alpha^0 $ 4 6 6 4 4 6 4
[1]

Antonio Cossidente, Sascha Kurz, Giuseppe Marino, Francesco Pavese. Combining subspace codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021007
[2]

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
[3]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349
[4]

Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79
[5]

Emily McMillon, Allison Beemer, Christine A. Kelley. Extremal absorbing sets in low-density parity-check codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021003
[6]

Ricardo A. Podestá, Denis E. Videla. The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021002
[7]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265
[8]

Raj Kumar, Maheshanand Bhaintwal. Duadic codes over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020135
[9]

Joe Gildea, Adrian Korban, Abidin Kaya, Bahattin Yildiz. Constructing self-dual codes from group rings and reverse circulant matrices. Advances in Mathematics of Communications, 2021, 15 (3) : 471-485. doi: 10.3934/amc.2020077
[10]

Muhammad Ajmal, Xiande Zhang. New optimal error-correcting codes for crosstalk avoidance in on-chip data buses. Advances in Mathematics of Communications, 2021, 15 (3) : 487-506. doi: 10.3934/amc.2020078
[11]

Yun Gao, Shilin Yang, Fang-Wei Fu. Some optimal cyclic $ \mathbb{F}_q $-linear $ \mathbb{F}_{q^t} $-codes. Advances in Mathematics of Communications, 2021, 15 (3) : 387-396. doi: 10.3934/amc.2020072
[12]

Xinyuan Liao, Caidi Zhao, Shengfan Zhou. Compact uniform attractors for dissipative non-autonomous lattice dynamical systems. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1087-1111. doi: 10.3934/cpaa.2007.6.1087
[13]

Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133
[14]

Jennifer D. Key, Bernardo G. Rodrigues. Binary codes from $ m $-ary $ n $-cubes $ Q^m_n $. Advances in Mathematics of Communications, 2021, 15 (3) : 507-524. doi: 10.3934/amc.2020079
[15]

Ademir Fernando Pazoto, Lionel Rosier. Uniform stabilization in weighted Sobolev spaces for the KdV equation posed on the half-line. Discrete & Continuous Dynamical Systems - B, 2010, 14 (4) : 1511-1535. doi: 10.3934/dcdsb.2010.14.1511
[16]

Vandana Sharma. Global existence and uniform estimates of solutions to reaction diffusion systems with mass transport type boundary conditions. Communications on Pure & Applied Analysis, 2021, 20 (3) : 955-974. doi: 10.3934/cpaa.2021001
[17]

Izumi Takagi, Conghui Zhang. Existence and stability of patterns in a reaction-diffusion-ODE system with hysteresis in non-uniform media. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3109-3140. doi: 10.3934/dcds.2020400
[18]

Dean Crnković, Nina Mostarac, Bernardo G. Rodrigues, Leo Storme. $ s $-PD-sets for codes from projective planes $ \mathrm{PG}(2,2^h) $, $ 5 \leq h\leq 9 $. Advances in Mathematics of Communications, 2021, 15 (3) : 423-440. doi: 10.3934/amc.2020075
[19]

V. Kumar Murty, Ying Zong. Splitting of abelian varieties. Advances in Mathematics of Communications, 2014, 8 (4) : 511-519. doi: 10.3934/amc.2014.8.511
[20]

Skyler Simmons. Stability of Broucke's isosceles orbit. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3759-3779. doi: 10.3934/dcds.2021015

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (145)
  • HTML views (559)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences