August  2016, 10(3): 525-540. doi: 10.3934/amc.2016023

Construction of subspace codes through linkage

1. 

University of Kentucky, Department of Mathematics, Lexington, KY 40506-0027

2. 

Department of Mathematics, Viterbo University, La Crosse, WI, United States

Received  May 2015 Revised  September 2015 Published  August 2016

A construction is discussed that allows to produce subspace codes of long length using subspace codes of shorter length in combination with a rank metric code. The subspace distance of the resulting linkage code is as good as the minimum subspace distance of the constituent codes. As a special application, the construction of the best known partial spreads is reproduced. Finally, for a special case of linkage, a decoding algorithm is presented which amounts to decoding with respect to the smaller constituent codes and which can be parallelized.
Citation: Heide Gluesing-Luerssen, Carolyn Troha. Construction of subspace codes through linkage. Advances in Mathematics of Communications, 2016, 10 (3) : 525-540. doi: 10.3934/amc.2016023
References:
[1]

A. Beutelspacher, Partial spreads in finite projective spaces and partial designs, Math. Zeit., 145 (1975), 211-229.  Google Scholar

[2]

M. Braun, T. Etzion, P. Östergård, A. Vardy and A. Wassermann, Existence of $q$-analogs of Steiner systems,, Forum Math. PI, ().   Google Scholar

[3]

M. Braun and J. Reichelt, $q$-analogs of packing designs, J. Comb. Designs, 22 (2014), 306-321. doi: 10.1002/jcd.21376.  Google Scholar

[4]

T. Bu, Partitions of a vector space, Discr. Math., 31 (1980), 79-83. doi: 10.1016/0012-365X(80)90174-0.  Google Scholar

[5]

J. de la Cruz, M. Kiermaier, A. Wassermann and W. Willems, Algebraic structures of MRD Codes, Adv. Math. Commun., 10 (2016), 499-510. doi: 10.3934/amc.2016021.  Google Scholar

[6]

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

[7]

D. A. Drake and J. W. Freeman, Partial $t$-spreads and group constructible $(s,r,\mu)$-nets, J. Geom., 13 (1979), 210-216. doi: 10.1007/BF01919756.  Google Scholar

[8]

S. El-Zanati, H. Jordon, G. Seelinger, P. Sissokho and L. Spence, The maximum size of a partial $3$-spread in a finite vector space over $\mathbb F_2$ Des. Codes Cryptogr., 54 (2010), 101-107. doi: 10.1007/s10623-009-9311-1.  Google Scholar

[9]

A. Elsenhans, A. Kohnert and A. Wassermann, Construction of codes for network coding, in Proc. 19th Int. Symp. Math. Theory Netw. Syst., Budapest, 2010, 1811-1814. Google Scholar

[10]

T. Etzion and N. Silberstein, Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams, IEEE Trans. Inform. Theory, IT-55 (2009), 2909-2919. doi: 10.1109/TIT.2009.2021376.  Google Scholar

[11]

T. Etzion and N. Silberstein, Codes and designs related to lifted MRD codes, IEEE Trans. Inform. Theory, IT-59 (2013), 1004-1017. doi: 10.1109/TIT.2012.2220119.  Google Scholar

[12]

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

[13]

E. M. Gabidulin, Theory of codes with maximal rank distance, Probl. Inf. Transm., 21 (1985), 1-12.  Google Scholar

[14]

E. M. Gabidulin and M. Bossert, Algebraic codes for network coding, Probl. Inf. Trans. (Engl. Transl.), 45 (2009), 343-356. doi: 10.1134/S003294600904005X.  Google Scholar

[15]

E. M. Gabidulin and N. I. Pilipchuk, Rank subcodes in multicomponent network coding, Probl. Inf. Trans. (Engl. Transl.), 49 (2013), 40-53. doi: 10.1134/S0032946013010043.  Google Scholar

[16]

E. M. Gabidulin, N. I. Pilipchuk and M. Bossert, Decoding of random network codes, Probl. Inf. Trans. (Engl. Transl.), 46 (2010), 300-320. doi: 10.1134/S0032946010040034.  Google Scholar

[17]

H. Gluesing-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

[18]

E. Gorla, F. Manganiello and J. Rosenthal, An algebraic approach for decoding spread codes, Adv. Math. Commun., 6 (2012), 443-466. doi: 10.3934/amc.2012.6.443.  Google Scholar

[19]

E. Gorla and A. Ravagnani, Partial spreads in random network coding, Finite Fields Appl., 26 (2014), 104-115. doi: 10.1016/j.ffa.2013.11.007.  Google Scholar

[20]

B. S. Hernandez and V. P. Sison, Grassmannian codes as lifts of matrix codes derived as images of linear block codes over finite fields, Global J. Pure Appl. Math., 12 (2016), 1801-1820. Google Scholar

[21]

T. Honold, M. Kiermaier and S. Kurz, Optimal binary subspace codes of length $6$, constant dimension $3$ and minimum subspace distance $4$, Contemp. Math., 632 (2015), 157-176. doi: 10.1090/conm/632/12627.  Google Scholar

[22]

A. Khaleghi, D. Silva and F. R. Kschischang, Subspace codes, in Proc. 12th IMA Conf. Crypt. Coding, Cirencester, 2009, 1-21. doi: 10.1007/978-3-642-10868-6_1.  Google Scholar

[23]

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

[24]

A. Kohnert and S. Kurz, Construction of large constant dimension codes with a prescribed minimum distance, in Mathematical Methods in Computer Science (eds. J. Calmet, W. Geiselmann and J. Müller-Quade), Springer, Berlin, 2008, 31-42. doi: 10.1007/978-3-540-89994-5_4.  Google Scholar

[25]

J. Rosenthal and A.-L. Trautmann, A complete characterization of irreducible cyclic orbit codes and their Plücker embedding, Des. Codes Cryptogr., 66 (2013), 275-289. doi: 10.1007/s10623-012-9691-5.  Google Scholar

[26]

N. Silberstein and A.-L. Trautmann, Subspace codes based on graph matchings, Ferrers diagrams, and pending blocks, IEEE Trans. Inform. Theory, IT-61 (2015), 3937-3953. doi: 10.1109/TIT.2015.2435743.  Google Scholar

[27]

D. Silva and F. R. Kschischang, On metrics for error correction in network coding, IEEE Trans. Inform. Theory, IT-55 (2009), 5479-5490. doi: 10.1109/TIT.2009.2032817.  Google Scholar

[28]

D. Silva, F. R. Kschischang and R. Kötter, A rank-metric approach to error control in random network coding, IEEE Trans. Inform. Theory, IT-54 (2008), 3951-3967. doi: 10.1109/TIT.2008.928291.  Google Scholar

[29]

V. Skachek, Recursive code construction for random networks, IEEE Trans. Inform. Theory, IT-56 (2010), 1378-1382. doi: 10.1109/TIT.2009.2039163.  Google Scholar

[30]

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

[31]

A.-L. Trautmann and J. Rosenthal, New improvements on the Echelon Ferrers construction, in Proc. 19th Int. Symp. Math. Theory Netw. Syst., Budapest, 2010, 405-408. Google Scholar

show all references

References:
[1]

A. Beutelspacher, Partial spreads in finite projective spaces and partial designs, Math. Zeit., 145 (1975), 211-229.  Google Scholar

[2]

M. Braun, T. Etzion, P. Östergård, A. Vardy and A. Wassermann, Existence of $q$-analogs of Steiner systems,, Forum Math. PI, ().   Google Scholar

[3]

M. Braun and J. Reichelt, $q$-analogs of packing designs, J. Comb. Designs, 22 (2014), 306-321. doi: 10.1002/jcd.21376.  Google Scholar

[4]

T. Bu, Partitions of a vector space, Discr. Math., 31 (1980), 79-83. doi: 10.1016/0012-365X(80)90174-0.  Google Scholar

[5]

J. de la Cruz, M. Kiermaier, A. Wassermann and W. Willems, Algebraic structures of MRD Codes, Adv. Math. Commun., 10 (2016), 499-510. doi: 10.3934/amc.2016021.  Google Scholar

[6]

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

[7]

D. A. Drake and J. W. Freeman, Partial $t$-spreads and group constructible $(s,r,\mu)$-nets, J. Geom., 13 (1979), 210-216. doi: 10.1007/BF01919756.  Google Scholar

[8]

S. El-Zanati, H. Jordon, G. Seelinger, P. Sissokho and L. Spence, The maximum size of a partial $3$-spread in a finite vector space over $\mathbb F_2$ Des. Codes Cryptogr., 54 (2010), 101-107. doi: 10.1007/s10623-009-9311-1.  Google Scholar

[9]

A. Elsenhans, A. Kohnert and A. Wassermann, Construction of codes for network coding, in Proc. 19th Int. Symp. Math. Theory Netw. Syst., Budapest, 2010, 1811-1814. Google Scholar

[10]

T. Etzion and N. Silberstein, Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams, IEEE Trans. Inform. Theory, IT-55 (2009), 2909-2919. doi: 10.1109/TIT.2009.2021376.  Google Scholar

[11]

T. Etzion and N. Silberstein, Codes and designs related to lifted MRD codes, IEEE Trans. Inform. Theory, IT-59 (2013), 1004-1017. doi: 10.1109/TIT.2012.2220119.  Google Scholar

[12]

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

[13]

E. M. Gabidulin, Theory of codes with maximal rank distance, Probl. Inf. Transm., 21 (1985), 1-12.  Google Scholar

[14]

E. M. Gabidulin and M. Bossert, Algebraic codes for network coding, Probl. Inf. Trans. (Engl. Transl.), 45 (2009), 343-356. doi: 10.1134/S003294600904005X.  Google Scholar

[15]

E. M. Gabidulin and N. I. Pilipchuk, Rank subcodes in multicomponent network coding, Probl. Inf. Trans. (Engl. Transl.), 49 (2013), 40-53. doi: 10.1134/S0032946013010043.  Google Scholar

[16]

E. M. Gabidulin, N. I. Pilipchuk and M. Bossert, Decoding of random network codes, Probl. Inf. Trans. (Engl. Transl.), 46 (2010), 300-320. doi: 10.1134/S0032946010040034.  Google Scholar

[17]

H. Gluesing-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

[18]

E. Gorla, F. Manganiello and J. Rosenthal, An algebraic approach for decoding spread codes, Adv. Math. Commun., 6 (2012), 443-466. doi: 10.3934/amc.2012.6.443.  Google Scholar

[19]

E. Gorla and A. Ravagnani, Partial spreads in random network coding, Finite Fields Appl., 26 (2014), 104-115. doi: 10.1016/j.ffa.2013.11.007.  Google Scholar

[20]

B. S. Hernandez and V. P. Sison, Grassmannian codes as lifts of matrix codes derived as images of linear block codes over finite fields, Global J. Pure Appl. Math., 12 (2016), 1801-1820. Google Scholar

[21]

T. Honold, M. Kiermaier and S. Kurz, Optimal binary subspace codes of length $6$, constant dimension $3$ and minimum subspace distance $4$, Contemp. Math., 632 (2015), 157-176. doi: 10.1090/conm/632/12627.  Google Scholar

[22]

A. Khaleghi, D. Silva and F. R. Kschischang, Subspace codes, in Proc. 12th IMA Conf. Crypt. Coding, Cirencester, 2009, 1-21. doi: 10.1007/978-3-642-10868-6_1.  Google Scholar

[23]

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

[24]

A. Kohnert and S. Kurz, Construction of large constant dimension codes with a prescribed minimum distance, in Mathematical Methods in Computer Science (eds. J. Calmet, W. Geiselmann and J. Müller-Quade), Springer, Berlin, 2008, 31-42. doi: 10.1007/978-3-540-89994-5_4.  Google Scholar

[25]

J. Rosenthal and A.-L. Trautmann, A complete characterization of irreducible cyclic orbit codes and their Plücker embedding, Des. Codes Cryptogr., 66 (2013), 275-289. doi: 10.1007/s10623-012-9691-5.  Google Scholar

[26]

N. Silberstein and A.-L. Trautmann, Subspace codes based on graph matchings, Ferrers diagrams, and pending blocks, IEEE Trans. Inform. Theory, IT-61 (2015), 3937-3953. doi: 10.1109/TIT.2015.2435743.  Google Scholar

[27]

D. Silva and F. R. Kschischang, On metrics for error correction in network coding, IEEE Trans. Inform. Theory, IT-55 (2009), 5479-5490. doi: 10.1109/TIT.2009.2032817.  Google Scholar

[28]

D. Silva, F. R. Kschischang and R. Kötter, A rank-metric approach to error control in random network coding, IEEE Trans. Inform. Theory, IT-54 (2008), 3951-3967. doi: 10.1109/TIT.2008.928291.  Google Scholar

[29]

V. Skachek, Recursive code construction for random networks, IEEE Trans. Inform. Theory, IT-56 (2010), 1378-1382. doi: 10.1109/TIT.2009.2039163.  Google Scholar

[30]

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

[31]

A.-L. Trautmann and J. Rosenthal, New improvements on the Echelon Ferrers construction, in Proc. 19th Int. Symp. Math. Theory Netw. Syst., Budapest, 2010, 405-408. Google Scholar

[1]

Thomas Honold, Michael Kiermaier, Sascha Kurz. Constructions and bounds for mixed-dimension subspace codes. Advances in Mathematics of Communications, 2016, 10 (3) : 649-682. doi: 10.3934/amc.2016033

[2]

Anna-Lena Trautmann. Isometry and automorphisms of constant dimension codes. Advances in Mathematics of Communications, 2013, 7 (2) : 147-160. doi: 10.3934/amc.2013.7.147

[3]

Natalia Silberstein, Tuvi Etzion. Large constant dimension codes and lexicodes. Advances in Mathematics of Communications, 2011, 5 (2) : 177-189. doi: 10.3934/amc.2011.5.177

[4]

Roland D. Barrolleta, Emilio Suárez-Canedo, Leo Storme, Peter Vandendriessche. On primitive constant dimension codes and a geometrical sunflower bound. Advances in Mathematics of Communications, 2017, 11 (4) : 757-765. doi: 10.3934/amc.2017055

[5]

Daniele Bartoli, Matteo Bonini, Massimo Giulietti. Constant dimension codes from Riemann-Roch spaces. Advances in Mathematics of Communications, 2017, 11 (4) : 705-713. doi: 10.3934/amc.2017051

[6]

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

[7]

Ghislain Fourier, Gabriele Nebe. Degenerate flag varieties in network coding. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021027

[8]

Ernst M. Gabidulin, Pierre Loidreau. Properties of subspace subcodes of Gabidulin codes. Advances in Mathematics of Communications, 2008, 2 (2) : 147-157. doi: 10.3934/amc.2008.2.147

[9]

Keisuke Minami, Takahiro Matsuda, Tetsuya Takine, Taku Noguchi. Asynchronous multiple source network coding for wireless broadcasting. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 577-592. doi: 10.3934/naco.2011.1.577

[10]

Min Ye, Alexander Barg. Polar codes for distributed hierarchical source coding. Advances in Mathematics of Communications, 2015, 9 (1) : 87-103. doi: 10.3934/amc.2015.9.87

[11]

Frédéric Vanhove. A geometric proof of the upper bound on the size of partial spreads in $H(4n+1,$q2$)$. Advances in Mathematics of Communications, 2011, 5 (2) : 157-160. doi: 10.3934/amc.2011.5.157

[12]

Daniel Heinlein, Ferdinand Ihringer. New and updated semidefinite programming bounds for subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 613-630. doi: 10.3934/amc.2020034

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

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

[15]

Stefan Martignoli, Ruedi Stoop. Phase-locking and Arnold coding in prototypical network topologies. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 145-162. doi: 10.3934/dcdsb.2008.9.145

[16]

Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln, Muriel Médard. The one-out-of-k retrieval problem and linear network coding. Advances in Mathematics of Communications, 2016, 10 (1) : 95-112. doi: 10.3934/amc.2016.10.95

[17]

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

[18]

T. Jäger. Neuronal coding of pacemaker neurons -- A random dynamical systems approach. Communications on Pure & Applied Analysis, 2011, 10 (3) : 995-1009. doi: 10.3934/cpaa.2011.10.995

[19]

Federico Rodriguez Hertz, María Alejandra Rodriguez Hertz, Raúl Ures. Partial hyperbolicity and ergodicity in dimension three. Journal of Modern Dynamics, 2008, 2 (2) : 187-208. doi: 10.3934/jmd.2008.2.187

[20]

Lisa Hernandez Lucas. Properties of sets of subspaces with constant intersection dimension. Advances in Mathematics of Communications, 2021, 15 (1) : 191-206. doi: 10.3934/amc.2020052

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (151)
  • HTML views (0)
  • Cited by (21)

Other articles
by authors

[Back to Top]