Constructions and bounds for mixed-dimension subspace codes

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

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. 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. 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. doi: 10.1007/BF01215286.
[5]	M. Braun and J. Reichelt, $q$-analogs of packing designs,, J. Combin. Des., 22 (2014), 306. doi: 10.1002/jcd.21376.
[6]	P. J. Cameron and J. H. van Lint, Graphs, Codes and Designs,, Cambridge Univ. Press, (1980).
[7]	P. J. Cameron and J. H. van Lint, Designs, Graphs, Codes and their Links,, Cambridge Univ. Press, (1991). 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. 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. 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. 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. doi: 10.1007/BF00147760.
[14]	J. Eisfeld and L. Storme, (Partial) $t$-Spreads and Minimal $t$-Covers in Finite Projective Spaces,, Lecture notes, (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. doi: 10.1109/TIT.2012.2220119.
[17]	T. Etzion and L. Storme, Galois geometries and coding theory,, Des. Codes Cryptogr., 78 (2016), 311. 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. 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. 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, (2014).
[22]	E. M. Gabidulin and M. Bossert, Algebraic codes for network coding,, Probl. Inform. Transm., 45 (2009), 343. 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. 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, (2016), 141. 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), 157. 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, (1975), 277. 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. 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. 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, (1977).
[40]	R. Mathon and G. F. Royle, The translation planes of order 49,, Des. Codes Cryptogr., 5 (1995), 57. doi: 10.1007/BF01388504.
[41]	B. D. McKay and A. Piperno, Practical graph isomorphism II,, J. Symb. Comput., 60 (2014), 94. 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), 226. 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., (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. 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. doi: 10.1109/TIT.2009.2039167.
[46]	A.-L. Trautmann, Isometry and automorphisms of constant dimension codes,, Adv. Math. Commun., 7 (2013), 147. 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.
[48]	R. W. Yeung and N. Cai, Network error correction, part II: Lower bounds,, Commun. Inform. Syst., 6 (2006), 37.

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. 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. 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. doi: 10.1007/BF01215286.
[5]	M. Braun and J. Reichelt, $q$-analogs of packing designs,, J. Combin. Des., 22 (2014), 306. doi: 10.1002/jcd.21376.
[6]	P. J. Cameron and J. H. van Lint, Graphs, Codes and Designs,, Cambridge Univ. Press, (1980).
[7]	P. J. Cameron and J. H. van Lint, Designs, Graphs, Codes and their Links,, Cambridge Univ. Press, (1991). 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. 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. 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. 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. doi: 10.1007/BF00147760.
[14]	J. Eisfeld and L. Storme, (Partial) $t$-Spreads and Minimal $t$-Covers in Finite Projective Spaces,, Lecture notes, (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. doi: 10.1109/TIT.2012.2220119.
[17]	T. Etzion and L. Storme, Galois geometries and coding theory,, Des. Codes Cryptogr., 78 (2016), 311. 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. 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. 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, (2014).
[22]	E. M. Gabidulin and M. Bossert, Algebraic codes for network coding,, Probl. Inform. Transm., 45 (2009), 343. 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. 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, (2016), 141. 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), 157. 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, (1975), 277. 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. 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. 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, (1977).
[40]	R. Mathon and G. F. Royle, The translation planes of order 49,, Des. Codes Cryptogr., 5 (1995), 57. doi: 10.1007/BF01388504.
[41]	B. D. McKay and A. Piperno, Practical graph isomorphism II,, J. Symb. Comput., 60 (2014), 94. 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), 226. 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., (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. 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. doi: 10.1109/TIT.2009.2039167.
[46]	A.-L. Trautmann, Isometry and automorphisms of constant dimension codes,, Adv. Math. Commun., 7 (2013), 147. 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.
[48]	R. W. Yeung and N. Cai, Network error correction, part II: Lower bounds,, Commun. Inform. Syst., 6 (2006), 37.

[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]	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
[3]	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
[4]	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
[5]	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
[6]	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
[7]	Kangkang Deng, Zheng Peng, Jianli Chen. Sparse probabilistic Boolean network problems: A partial proximal-type operator splitting method. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2018127
[8]	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
[9]	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
[10]	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
[11]	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
[12]	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
[13]	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
[14]	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
[15]	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
[16]	Wendi Wang. Population dispersal and disease spread. Discrete & Continuous Dynamical Systems - B, 2004, 4 (3) : 797-804. doi: 10.3934/dcdsb.2004.4.797
[17]	Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637
[18]	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
[19]	Miguel Mendes. A note on the coding of orbits in certain discontinuous maps. Discrete & Continuous Dynamical Systems - A, 2010, 27 (1) : 369-382. doi: 10.3934/dcds.2010.27.369
[20]	Shigui Ruan, Wendi Wang, Simon A. Levin. The effect of global travel on the spread of SARS. Mathematical Biosciences & Engineering, 2006, 3 (1) : 205-218. doi: 10.3934/mbe.2006.3.205

2018 Impact Factor: 0.879

American Institute of Mathematical Sciences