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.

[2]

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

[3]

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

[4]

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

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

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

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

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

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

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

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

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

[13]

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

[14]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[29]

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

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

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

show all references

References:
[1]

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

[2]

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

[3]

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

[4]

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

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

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

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

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

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

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

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

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

[13]

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

[14]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[29]

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

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

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

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

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

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

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

2017 Impact Factor: 0.564

Metrics

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

Other articles
by authors

[Back to Top]