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.   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.  doi: 10.1002/jcd.21376.  Google Scholar

[4]

T. Bu, Partitions of a vector space,, Discr. Math., 31 (1980), 79.  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.  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.  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.  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.  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., (2010), 1811.   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.  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.  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.  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.   Google Scholar

[14]

E. M. Gabidulin and M. Bossert, Algebraic codes for network coding,, Probl. Inf. Trans. (Engl. Transl.), 45 (2009), 343.  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.  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.  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.  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.  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.  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.   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.  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, (2009), 1.  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.  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, (2008), 31.  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.  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.  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.  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.  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.  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.  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., (2010), 405.   Google Scholar

show all references

References:
[1]

A. Beutelspacher, Partial spreads in finite projective spaces and partial designs,, Math. Zeit., 145 (1975), 211.   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.  doi: 10.1002/jcd.21376.  Google Scholar

[4]

T. Bu, Partitions of a vector space,, Discr. Math., 31 (1980), 79.  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.  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.  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.  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.  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., (2010), 1811.   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.  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.  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.  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.   Google Scholar

[14]

E. M. Gabidulin and M. Bossert, Algebraic codes for network coding,, Probl. Inf. Trans. (Engl. Transl.), 45 (2009), 343.  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.  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.  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.  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.  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.  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.   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.  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, (2009), 1.  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.  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, (2008), 31.  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.  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.  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.  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.  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.  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.  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., (2010), 405.   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]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505

[17]

Al-hassem Nayam. Constant in two-dimensional $p$-compliance-network problem. Networks & Heterogeneous Media, 2014, 9 (1) : 161-168. doi: 10.3934/nhm.2014.9.161

[18]

Deena Schmidt, Janet Best, Mark S. Blumberg. Random graph and stochastic process contributions to network dynamics. Conference Publications, 2011, 2011 (Special) : 1279-1288. doi: 10.3934/proc.2011.2011.1279

[19]

Łukasz Struski, Jacek Tabor, Tomasz Kułaga. Cone-fields without constant orbit core dimension. Discrete & Continuous Dynamical Systems - A, 2012, 32 (10) : 3651-3664. doi: 10.3934/dcds.2012.32.3651

[20]

Gokhan Calis, O. Ozan Koyluoglu. Architecture-aware coding for distributed storage: Repairable block failure resilient codes. Advances in Mathematics of Communications, 2018, 12 (3) : 465-503. doi: 10.3934/amc.2018028

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (15)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]