American Institute of Mathematical Sciences

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

Constructions and bounds for mixed-dimension subspace codes

 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

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

2017 Impact Factor: 0.564