×

Constructions and bounds for mixed-dimension subspace codes. (English) Zbl 1402.94086

Summary: 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 \(\mathrm{PG}(v-1,\mathbb{F}_q)\) with minimum subspace distance \(d\). Here we completely resolve this problem for \(d\geq 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\).

MSC:

94B05 Linear codes (general theory)
05B25 Combinatorial aspects of finite geometries
51E20 Combinatorial structures in finite projective spaces
51E14 Finite partial geometries (general), nets, partial spreads
51E22 Linear codes and caps in Galois spaces
51E23 Spreads and packing problems in finite geometry

Software:

Cliquer
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] R. Ahlswede, On error control codes for random network coding,, in IEEE Workshop Network Coding Theory Appl., 68 (2009)
[2] C. Bachoc, Bounds for projective codes from semidefinite programming,, Adv. Math. Commun., 7, 127 (2013) · Zbl 1317.94164
[3] J. De Beule, <em>Current Research Topics in Galois Geometry</em>,, Nova Science Publishers (2011) · Zbl 1298.51007
[4] A. Beutelspacher, Partial spreads in finite projective spaces and partial designs,, Math. Z., 145, 211 (1975) · Zbl 0297.50018
[5] M. Braun, \(q\)-analogs of packing designs,, J. Combin. Des., 22, 306 (2014) · Zbl 1301.05060
[6] P. J. Cameron, <em>Graphs, Codes and Designs</em>,, Cambridge Univ. Press (1980) · Zbl 0427.05001
[7] P. J. Cameron, <em>Designs, Graphs, Codes and their Links</em>,, Cambridge Univ. Press (1991) · Zbl 0743.05004
[8] A. Cossidente, Optimal subspace codes in \(PG(4,q)\),, in preparation.
[9] T. Czerwinski, The translation planes of order twenty-five,, J. Combin. Theory Ser. A, 59, 193 (1992) · Zbl 0764.51004
[10] P. Delsarte, Bilinear forms over a finite field, with applications to coding theory,, J. Combin. Theory Ser. A, 25, 226 (1978) · Zbl 0397.94012
[11] P. Dembowski, <em>Finite Geometries</em>,, Springer-Verlag (1968) · Zbl 0159.50001
[12] U. Dempwolff, Translation planes of order 27,, Des. Codes Cryptogr., 4, 105 (1994) · Zbl 0798.51003
[13] U. Dempwolff, The classification of the translation planes of order 16, I,, Geom. Dedicata, 15, 137 (1983) · Zbl 0532.51003
[14] J. Eisfeld, <em>(Partial) \(t\)-Spreads and Minimal \(t\)-Covers in Finite Projective Spaces</em>,, Lecture notes (2000)
[15] T. Etzion, Problems on \(q\)-analogs in coding theory,, preprint
[16] T. Etzion, Codes and designs related to lifted MRD codes,, IEEE Trans. Inform. Theory, 59, 1004 (2013) · Zbl 1364.94597
[17] T. Etzion, Galois geometries and coding theory,, Des. Codes Cryptogr., 78, 311 (2016) · Zbl 1387.94129
[18] T. Etzion, Error-correcting codes in projective space,, IEEE Trans. Inform. Theory, 57, 1165 (2011) · Zbl 1366.94589
[19] T. Feulner, The automorphism groups of linear codes and canonical representatives of their semilinear isometry classes,, Adv. Math. Commun., 3, 363 (2009) · Zbl 1205.05247
[20] T. Feulner, Canonical forms and automorphisms in the projective space,, preprint · Zbl 1205.05247
[21] T. Feulner, <em>Eine kanonische Form zur Darstellung äquivalenter Codes - Computergestützte Berechnung und ihre Anwendung in der Codierungstheorie, Kryptographie und Geometrie</em>,, Ph.D thesis (2014)
[22] E. M. Gabidulin, Algebraic codes for network coding,, Probl. Inform. Transm., 45, 343 (2009) · Zbl 1190.94040
[23] J. Galambos, <em>Bonferroni-Type Inequalities with Applications</em>,, Springer-Verlag (1996) · Zbl 0869.60014
[24] N. A. Gordon, Classification of partial spreads in \(¶G(4,2)\),, available online at <a href=
[25] X. Guang, <em>Linear Network Error Correction Coding</em>,, Springer-Verlag (2014)
[26] M. Hall, Uniqueness of the projective plane of order eight,, Math. Comp., 10, 186 (1956) · Zbl 0073.36502
[27] D. Heinlein, Tables of subspace codes,, preprint · Zbl 1018.68681
[28] J. W. P. Hirschfeld, <em>Finite Projective Spaces of Three Dimensions</em>,, Oxford Univ. Press (1985) · Zbl 0574.51001
[29] J. W. P. Hirschfeld, <em>Projective Geometries over Finite Fields</em>,, Oxford Univ. Press (1998) · Zbl 0899.51002
[30] J. W. P. Hirschfeld, <em>General Galois Geometries</em>,, Oxford Univ. Press (1991) · Zbl 1358.51002
[31] T. Honold, On putative \(q\)-analogues of the Fano plane and related combinatorial structures,, in Dynamical Systems, 141 (2016) · Zbl 1357.51004
[32] T. Honold, Optimal binary subspace codes of length \(6\), constant dimension \(3\) and minimum subspace distance \(4\),, in 11th Int. Conf. Finite Fields Appl., 157 (2013) · Zbl 1355.94094
[33] T. Honold, Classification of large partial plane spreads in \(¶G(6,\mathbbF_2)\) and related combinatorial objects, submitted., Available online at <a href=
[34] N. L. Johnson, <em>Handbook of Finite Translation Planes</em>,, CRC Press (2007) · Zbl 1136.51001
[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, 277 (1975) · Zbl 0297.05005
[36] R. Koetter, Coding for errors and erasures in random network coding,, IEEE Trans. Inform. Theory, 54, 3579 (2008) · Zbl 1318.94111
[37] J. H. van Lint, <em>A Course in Combinatorics</em>,, Cambridge Univ. Press (1992) · Zbl 0769.05001
[38] H. Liu, Poster: A new approach to the main problem of subspace coding,, in 9th Int. Conf. Commun. Netw. China (ChinaCom 2014), 676 (2014)
[39] F. J. MacWilliams, <em>The Theory of Error-Correcting Codes</em>,, North-Holland Publishing Company (1977) · Zbl 0369.94008
[40] R. Mathon, The translation planes of order 49,, Des. Codes Cryptogr., 5, 57 (1995) · Zbl 0819.51003
[41] B. D. McKay, Practical graph isomorphism II,, J. Symb. Comput., 60, 94 (2014) · Zbl 1394.05079
[42] G. E. Moorhouse, Two-graphs and skew two-graphs in finite geometries,, Linear Algebra Appl., 226-228, 226 (1995) · Zbl 0839.05024
[43] S. Niskanen, <em>Cliquer User’s Guide</em>, Version 1.0,, Commun. Lab. (2003)
[44] D. Silva, A rank-metric approach to error control in random network coding,, IEEE Trans. Inform. Theory, 54, 3951 (2008) · Zbl 1318.94119
[45] D. Silva, Communication over finite-field matrix channels,, IEEE Trans. Inform. Theory, 56, 1296 (2010) · Zbl 1366.94769
[46] A.-L. Trautmann, Isometry and automorphisms of constant dimension codes,, Adv. Math. Commun., 7, 147 (2013) · Zbl 1271.94036
[47] R. W. Yeung, Network error correction, part I: Basic concepts and upper bounds,, Commun. Inform. Syst., 6, 19 (2006) · Zbl 1161.94452
[48] R. W. Yeung, Network error correction, part II: Lower bounds,, Commun. Inform. Syst., 6, 37 (2006) · Zbl 1161.94451
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.