Constructions and bounds for mixed-dimension subspace codes

Thomas Honold; Michael Kiermaier; Sascha Kurz

doi:10.3934/amc.2016033

Article Contents

2016, Volume 10, Issue 3: 649-682. Doi: 10.3934/amc.2016033

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

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: November 30, 2015

Revised: May 31, 2016

Published: July 2016

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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, arXiv:1305.6126
[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, arXiv:1305.1193
[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 http://www.maths.qmul.ac.uk/~leonard/partialspreads/PG42new.pdf
[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, arXiv:1601.02864
[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.06688doi: 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 arXiv:1606.07655
[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.