Constructions and bounds for mixed-dimension subspace codes

Previous Article
AMC Home
This Issue
Next Article
The weight distribution of the self-dual $[128,64]$ polarity design code

August 2016, 10(3): 649-682. doi: 10.3934/amc.2016033

Constructions and bounds for mixed-dimension subspace codes

Thomas Honold ^1, , Michael Kiermaier ^2, and Sascha Kurz ^3,

1.	Department of Information Science and Electronics Engineering, Zhejiang University, 38 Zheda Road, Hangzhou 310027
2.	Mathematisches Institut, Universität Bayreuth, D-95440 Bayreuth
3.	Institut für Mathematik, Universität Bayreuth, D-95440 Bayreuth

Received December 2015 Revised June 2016 Published August 2016

Abstract
Related Papers

Codes in finite projective spaces equipped with the subspace distance have been proposed for error control in random linear network coding. The resulting so-called Main Problem of Subspace Coding is to determine the maximum size $A_q(v,d)$ of a code in $PG(v-1,\mathbb{F}_q)$ with minimum subspace distance $d$. Here we completely resolve this problem for $d\ge v-1$. For $d=v-2$ we present some improved bounds and determine $A_q(5,3)=2q^3+2$ (all $q$), $A_2(7,5)=34$. We also provide an exposition of the known determination of $A_q(v,2)$, and a table with exact results and bounds for the numbers $A_2(v,d)$, $v\leq 7$.

Keywords: Galois geometry, network coding, subspace code, partial spread..

Mathematics Subject Classification: Primary: 94B05, 05B25, 51E20; Secondary: 51E14, 51E22, 51E2.

Citation: 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

References:

[1]	R. Ahlswede and H. Aydinian, On error control codes for random network coding, in IEEE Workshop Network Coding Theory Appl., 2009, 68-73. doi: 10.1109/NETCOD.2009.5191396.
[2]	C. Bachoc, A. Passuello, and F. Vallentin, Bounds for projective codes from semidefinite programming, Adv. Math. Commun., 7 (2013), 127-145. doi: 10.3934/amc.2013.7.127.
[3]	J. De Beule and L. Storme, Current Research Topics in Galois Geometry, Nova Science Publishers, 2011.
[4]	A. Beutelspacher, Partial spreads in finite projective spaces and partial designs, Math. Z., 145 (1975), 211-230. Corrigendum, ibid., 147 (1976), 303. doi: 10.1007/BF01215286.
[5]	M. Braun and J. Reichelt, $q$-analogs of packing designs, J. Combin. Des., 22 (2014), 306-321. doi: 10.1002/jcd.21376.
[6]	P. J. Cameron and J. H. van Lint, Graphs, Codes and Designs, Cambridge Univ. Press, 1980. A revised edition of these notes is [7].
[7]	P. J. Cameron and J. H. van Lint, Designs, Graphs, Codes and their Links, Cambridge Univ. Press, 1991. Revised edition of [6]. doi: 10.1017/CBO9780511623714.
[8]	A. Cossidente, F. Pavese and L. Storme, Optimal subspace codes in $PG(4,q)$,, in preparation., ().
[9]	T. Czerwinski and D. Oakden, The translation planes of order twenty-five, J. Combin. Theory Ser. A, 59 (1992), 193-217. doi: 10.1016/0097-3165(92)90065-3.
[10]	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.
[11]	P. Dembowski, Finite Geometries, Springer-Verlag, 1968. doi: 10.1007/978-3-642-62012-6.
[12]	U. Dempwolff, Translation planes of order 27, Des. Codes Cryptogr., 4 (1994), 105-121. Erratum, ibid., 5 (1995), 81. doi: 10.1007/BF01578865.
[13]	U. Dempwolff and A. Reifart, The classification of the translation planes of order 16, I, Geom. Dedicata, 15 (1983), 137-153. doi: 10.1007/BF00147760.
[14]	J. Eisfeld and L. Storme, (Partial) $t$-Spreads and Minimal $t$-Covers in Finite Projective Spaces, Lecture notes, Ghent Univ., 2000.
[15]	T. Etzion, Problems on $q$-analogs in coding theory,, preprint, ().
[16]	T. Etzion and N. Silberstein, Codes and designs related to lifted MRD codes, IEEE Trans. Inform. Theory, 59 (2013), 1004-1017. Erratum, ibid., 59 (2013), 4730. doi: 10.1109/TIT.2012.2220119.
[17]	T. Etzion and L. Storme, Galois geometries and coding theory, Des. Codes Cryptogr., 78 (2016), 311-350. doi: 10.1007/s10623-015-0156-5.
[18]	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.
[19]	T. Feulner, The automorphism groups of linear codes and canonical representatives of their semilinear isometry classes, Adv. Math. Commun., 3 (2009), 363-383. doi: 10.3934/amc.2009.3.363.
[20]	T. Feulner, Canonical forms and automorphisms in the projective space,, preprint, ().
[21]	T. Feulner, Eine kanonische Form zur Darstellung äquivalenter Codes - Computergestützte Berechnung und ihre Anwendung in der Codierungstheorie, Kryptographie und Geometrie, Ph.D thesis, Univ. Bayreuth, 2014. Available online at https://epub.uni-bayreuth.de/42/
[22]	E. M. Gabidulin and M. Bossert, Algebraic codes for network coding, Probl. Inform. Transm., 45 (2009), 343-356. doi: 10.1134/S003294600904005X.
[23]	J. Galambos and I. Simonelli, Bonferroni-Type Inequalities with Applications, Springer-Verlag, 1996.
[24]	N. A. Gordon, R. Shaw and L. H. Soicher, Classification of partial spreads in $\PG(4,2)$,, available online at , ().
[25]	X. Guang and Z. Zhang, Linear Network Error Correction Coding, Springer-Verlag, 2014. doi: 10.1007/978-1-4939-0588-1.
[26]	M. Hall, Jr., J. D. Swift and R. J. Walker, Uniqueness of the projective plane of order eight, Math. Comp., 10 (1956), 186-194. doi: 10.2307/2001913.
[27]	D. Heinlein, M. Kiermaier, S. Kurz and A. Wassermann, Tables of subspace codes,, preprint, ().
[28]	J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions, Oxford Univ. Press, 1985.
[29]	J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Oxford Univ. Press, 1998.
[30]	J. W. P. Hirschfeld and J. A. Thas, General Galois Geometries, Oxford Univ. Press, 1991. doi: 10.1007/978-1-4471-6790-7.
[31]	T. Honold and M. Kiermaier, On putative $q$-analogues of the Fano plane and related combinatorial structures, in Dynamical Systems, Number Theory and Applications: A Festschrift in Honor of Armin Leutbecher's 80th Birthday (eds. T. Hagen, F. Rupp and J. Scheurle), World Scientific, 2016, 141-175. Available online at arXiv:1504.06688 doi: 10.1142/9789814699877_0008.
[32]	T. Honold, M. Kiermaier and S. Kurz, Optimal binary subspace codes of length $6$, constant dimension $3$ and minimum subspace distance $4$, in 11th Int. Conf. Finite Fields Appl., 2013, Magdeburg, 2015, 157-176. doi: 10.1090/conm/632/12627.
[33]	T. Honold, M. Kiermaier and S. Kurz, Classification of large partial plane spreads in $\PG(6,\mathbbF_2)$ and related combinatorial objects, submitted., Available online at , ().
[34]	N. L. Johnson, V. Jha and M. Biliotti, Handbook of Finite Translation Planes, CRC Press, 2007. doi: 10.1201/9781420011142.
[35]	D. J. Kleitman, On an extremal property of antichains in partial orders. The LYM property and some of its implications and applications, in Combinatorics, Springer, 1975, 277-290. doi: 10.1007/978-94-010-1826-5_14.
[36]	R. Koetter and F. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3579-3591. doi: 10.1109/TIT.2008.926449.
[37]	J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge Univ. Press, 1992.
[38]	H. Liu and T. Honold, Poster: A new approach to the main problem of subspace coding, in 9th Int. Conf. Commun. Netw. China (ChinaCom 2014), 2014, 676-677. doi: 10.1109/CHINACOM.2014.7054392.
[39]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Publishing Company, Amsterdam, 1977.
[40]	R. Mathon and G. F. Royle, The translation planes of order 49, Des. Codes Cryptogr., 5 (1995), 57-72. doi: 10.1007/BF01388504.
[41]	B. D. McKay and A. Piperno, Practical graph isomorphism II, J. Symb. Comput., 60 (2014), 94-112. doi: 10.1016/j.jsc.2013.09.003.
[42]	G. E. Moorhouse, Two-graphs and skew two-graphs in finite geometries, Linear Algebra Appl., 226-228 (1995), 529-551. doi: 10.1016/0024-3795(95)00242-J.
[43]	S. Niskanen and P. R. J. Östergård, Cliquer User's Guide, Version 1.0, Commun. Lab., Helsinki Univ. Techn., Finland, Tech. Rep. T48, 2003.
[44]	D. Silva, F. Kschischang and R. Koetter, A rank-metric approach to error control in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3951-3967. doi: 10.1109/TIT.2008.928291.
[45]	D. Silva, F. Kschischang and R. Koetter, Communication over finite-field matrix channels, IEEE Trans. Inform. Theory, 56 (2010), 1296-1306. doi: 10.1109/TIT.2009.2039167.
[46]	A.-L. Trautmann, Isometry and automorphisms of constant dimension codes, Adv. Math. Commun., 7 (2013), 147-160. doi: 10.3934/amc.2013.7.147.
[47]	R. W. Yeung and N. Cai, Network error correction, part I: Basic concepts and upper bounds, Commun. Inform. Syst., 6 (2006), 19-35.
[48]	R. W. Yeung and N. Cai, Network error correction, part II: Lower bounds, Commun. Inform. Syst., 6 (2006), 37-54.

show all references

References:

[1]	R. Ahlswede and H. Aydinian, On error control codes for random network coding, in IEEE Workshop Network Coding Theory Appl., 2009, 68-73. doi: 10.1109/NETCOD.2009.5191396.
[2]	C. Bachoc, A. Passuello, and F. Vallentin, Bounds for projective codes from semidefinite programming, Adv. Math. Commun., 7 (2013), 127-145. doi: 10.3934/amc.2013.7.127.
[3]	J. De Beule and L. Storme, Current Research Topics in Galois Geometry, Nova Science Publishers, 2011.
[4]	A. Beutelspacher, Partial spreads in finite projective spaces and partial designs, Math. Z., 145 (1975), 211-230. Corrigendum, ibid., 147 (1976), 303. doi: 10.1007/BF01215286.
[5]	M. Braun and J. Reichelt, $q$-analogs of packing designs, J. Combin. Des., 22 (2014), 306-321. doi: 10.1002/jcd.21376.
[6]	P. J. Cameron and J. H. van Lint, Graphs, Codes and Designs, Cambridge Univ. Press, 1980. A revised edition of these notes is [7].
[7]	P. J. Cameron and J. H. van Lint, Designs, Graphs, Codes and their Links, Cambridge Univ. Press, 1991. Revised edition of [6]. doi: 10.1017/CBO9780511623714.
[8]	A. Cossidente, F. Pavese and L. Storme, Optimal subspace codes in $PG(4,q)$,, in preparation., ().
[9]	T. Czerwinski and D. Oakden, The translation planes of order twenty-five, J. Combin. Theory Ser. A, 59 (1992), 193-217. doi: 10.1016/0097-3165(92)90065-3.
[10]	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.
[11]	P. Dembowski, Finite Geometries, Springer-Verlag, 1968. doi: 10.1007/978-3-642-62012-6.
[12]	U. Dempwolff, Translation planes of order 27, Des. Codes Cryptogr., 4 (1994), 105-121. Erratum, ibid., 5 (1995), 81. doi: 10.1007/BF01578865.
[13]	U. Dempwolff and A. Reifart, The classification of the translation planes of order 16, I, Geom. Dedicata, 15 (1983), 137-153. doi: 10.1007/BF00147760.
[14]	J. Eisfeld and L. Storme, (Partial) $t$-Spreads and Minimal $t$-Covers in Finite Projective Spaces, Lecture notes, Ghent Univ., 2000.
[15]	T. Etzion, Problems on $q$-analogs in coding theory,, preprint, ().
[16]	T. Etzion and N. Silberstein, Codes and designs related to lifted MRD codes, IEEE Trans. Inform. Theory, 59 (2013), 1004-1017. Erratum, ibid., 59 (2013), 4730. doi: 10.1109/TIT.2012.2220119.
[17]	T. Etzion and L. Storme, Galois geometries and coding theory, Des. Codes Cryptogr., 78 (2016), 311-350. doi: 10.1007/s10623-015-0156-5.
[18]	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.
[19]	T. Feulner, The automorphism groups of linear codes and canonical representatives of their semilinear isometry classes, Adv. Math. Commun., 3 (2009), 363-383. doi: 10.3934/amc.2009.3.363.
[20]	T. Feulner, Canonical forms and automorphisms in the projective space,, preprint, ().
[21]	T. Feulner, Eine kanonische Form zur Darstellung äquivalenter Codes - Computergestützte Berechnung und ihre Anwendung in der Codierungstheorie, Kryptographie und Geometrie, Ph.D thesis, Univ. Bayreuth, 2014. Available online at https://epub.uni-bayreuth.de/42/
[22]	E. M. Gabidulin and M. Bossert, Algebraic codes for network coding, Probl. Inform. Transm., 45 (2009), 343-356. doi: 10.1134/S003294600904005X.
[23]	J. Galambos and I. Simonelli, Bonferroni-Type Inequalities with Applications, Springer-Verlag, 1996.
[24]	N. A. Gordon, R. Shaw and L. H. Soicher, Classification of partial spreads in $\PG(4,2)$,, available online at , ().
[25]	X. Guang and Z. Zhang, Linear Network Error Correction Coding, Springer-Verlag, 2014. doi: 10.1007/978-1-4939-0588-1.
[26]	M. Hall, Jr., J. D. Swift and R. J. Walker, Uniqueness of the projective plane of order eight, Math. Comp., 10 (1956), 186-194. doi: 10.2307/2001913.
[27]	D. Heinlein, M. Kiermaier, S. Kurz and A. Wassermann, Tables of subspace codes,, preprint, ().
[28]	J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions, Oxford Univ. Press, 1985.
[29]	J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Oxford Univ. Press, 1998.
[30]	J. W. P. Hirschfeld and J. A. Thas, General Galois Geometries, Oxford Univ. Press, 1991. doi: 10.1007/978-1-4471-6790-7.
[31]	T. Honold and M. Kiermaier, On putative $q$-analogues of the Fano plane and related combinatorial structures, in Dynamical Systems, Number Theory and Applications: A Festschrift in Honor of Armin Leutbecher's 80th Birthday (eds. T. Hagen, F. Rupp and J. Scheurle), World Scientific, 2016, 141-175. Available online at arXiv:1504.06688 doi: 10.1142/9789814699877_0008.
[32]	T. Honold, M. Kiermaier and S. Kurz, Optimal binary subspace codes of length $6$, constant dimension $3$ and minimum subspace distance $4$, in 11th Int. Conf. Finite Fields Appl., 2013, Magdeburg, 2015, 157-176. doi: 10.1090/conm/632/12627.
[33]	T. Honold, M. Kiermaier and S. Kurz, Classification of large partial plane spreads in $\PG(6,\mathbbF_2)$ and related combinatorial objects, submitted., Available online at , ().
[34]	N. L. Johnson, V. Jha and M. Biliotti, Handbook of Finite Translation Planes, CRC Press, 2007. doi: 10.1201/9781420011142.
[35]	D. J. Kleitman, On an extremal property of antichains in partial orders. The LYM property and some of its implications and applications, in Combinatorics, Springer, 1975, 277-290. doi: 10.1007/978-94-010-1826-5_14.
[36]	R. Koetter and F. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3579-3591. doi: 10.1109/TIT.2008.926449.
[37]	J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge Univ. Press, 1992.
[38]	H. Liu and T. Honold, Poster: A new approach to the main problem of subspace coding, in 9th Int. Conf. Commun. Netw. China (ChinaCom 2014), 2014, 676-677. doi: 10.1109/CHINACOM.2014.7054392.
[39]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Publishing Company, Amsterdam, 1977.
[40]	R. Mathon and G. F. Royle, The translation planes of order 49, Des. Codes Cryptogr., 5 (1995), 57-72. doi: 10.1007/BF01388504.
[41]	B. D. McKay and A. Piperno, Practical graph isomorphism II, J. Symb. Comput., 60 (2014), 94-112. doi: 10.1016/j.jsc.2013.09.003.
[42]	G. E. Moorhouse, Two-graphs and skew two-graphs in finite geometries, Linear Algebra Appl., 226-228 (1995), 529-551. doi: 10.1016/0024-3795(95)00242-J.
[43]	S. Niskanen and P. R. J. Östergård, Cliquer User's Guide, Version 1.0, Commun. Lab., Helsinki Univ. Techn., Finland, Tech. Rep. T48, 2003.
[44]	D. Silva, F. Kschischang and R. Koetter, A rank-metric approach to error control in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3951-3967. doi: 10.1109/TIT.2008.928291.
[45]	D. Silva, F. Kschischang and R. Koetter, Communication over finite-field matrix channels, IEEE Trans. Inform. Theory, 56 (2010), 1296-1306. doi: 10.1109/TIT.2009.2039167.
[46]	A.-L. Trautmann, Isometry and automorphisms of constant dimension codes, Adv. Math. Commun., 7 (2013), 147-160. doi: 10.3934/amc.2013.7.147.
[47]	R. W. Yeung and N. Cai, Network error correction, part I: Basic concepts and upper bounds, Commun. Inform. Syst., 6 (2006), 19-35.
[48]	R. W. Yeung and N. Cai, Network error correction, part II: Lower bounds, Commun. Inform. Syst., 6 (2006), 37-54.

[1]	Vincent Astier, Thomas Unger. Galois extensions, positive involutions and an application to unitary space-time coding. Advances in Mathematics of Communications, 2019, 13 (3) : 513-516. doi: 10.3934/amc.2019032
[2]	Ghislain Fourier, Gabriele Nebe. Degenerate flag varieties in network coding. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021027
[3]	Keisuke Minami, Takahiro Matsuda, Tetsuya Takine, Taku Noguchi. Asynchronous multiple source network coding for wireless broadcasting. Numerical Algebra, Control and Optimization, 2011, 1 (4) : 577-592. doi: 10.3934/naco.2011.1.577
[4]	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
[5]	Stefan Martignoli, Ruedi Stoop. Phase-locking and Arnold coding in prototypical network topologies. Discrete and Continuous Dynamical Systems - B, 2008, 9 (1) : 145-162. doi: 10.3934/dcdsb.2008.9.145
[6]	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
[7]	Daniel Heinlein, Michael Kiermaier, Sascha Kurz, Alfred Wassermann. A subspace code of size $ \bf{333} $ in the setting of a binary $ \bf{q} $-analog of the Fano plane. Advances in Mathematics of Communications, 2019, 13 (3) : 457-475. doi: 10.3934/amc.2019029
[8]	Susama Agarwala, Ben Dees, Andrew Gearheart, Corey Lowman. Geometry and Generalization: Eigenvalues as predictors of where a network will fail to generalize. Foundations of Data Science, 2022, 4 (2) : 217-242. doi: 10.3934/fods.2022004
[9]	María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021018
[10]	Zihui Liu. Galois LCD codes over rings. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022002
[11]	Kangkang Deng, Zheng Peng, Jianli Chen. Sparse probabilistic Boolean network problems: A partial proximal-type operator splitting method. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1881-1896. doi: 10.3934/jimo.2018127
[12]	Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1
[13]	Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003
[14]	Antonio Cossidente, Sascha Kurz, Giuseppe Marino, Francesco Pavese. Combining subspace codes. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021007
[15]	Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45
[16]	Michael Kiermaier, Reinhard Laue. Derived and residual subspace designs. Advances in Mathematics of Communications, 2015, 9 (1) : 105-115. doi: 10.3934/amc.2015.9.105
[17]	Claude Carlet, Juan Carlos Ku-Cauich, Horacio Tapia-Recillas. Bent functions on a Galois ring and systematic authentication codes. Advances in Mathematics of Communications, 2012, 6 (2) : 249-258. doi: 10.3934/amc.2012.6.249
[18]	Delphine Boucher, Patrick Solé, Felix Ulmer. Skew constacyclic codes over Galois rings. Advances in Mathematics of Communications, 2008, 2 (3) : 273-292. doi: 10.3934/amc.2008.2.273
[19]	Wendi Wang. Population dispersal and disease spread. Discrete and Continuous Dynamical Systems - B, 2004, 4 (3) : 797-804. doi: 10.3934/dcdsb.2004.4.797
[20]	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

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Thomas Honold Michael Kiermaier Sascha Kurz
on Google Scholar
Thomas Honold Michael Kiermaier Sascha Kurz

[Back to Top]