American Institute of Mathematical Sciences

Advanced
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

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. Google Scholar

[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. Google Scholar

[3]

J. De Beule and L. Storme, Current Research Topics in Galois Geometry,, Nova Science Publishers, (2011). Google Scholar

[4]

A. Beutelspacher, Partial spreads in finite projective spaces and partial designs,, Math. Z., 145 (1975), 211. doi: 10.1007/BF01215286. Google Scholar

[5]

M. Braun and J. Reichelt, $q$-analogs of packing designs,, J. Combin. Des., 22 (2014), 306. doi: 10.1002/jcd.21376. Google Scholar

[6]

P. J. Cameron and J. H. van Lint, Graphs, Codes and Designs,, Cambridge Univ. Press, (1980). Google Scholar

[7]

P. J. Cameron and J. H. van Lint, Designs, Graphs, Codes and their Links,, Cambridge Univ. Press, (1991). doi: 10.1017/CBO9780511623714. Google Scholar

[8]

A. Cossidente, F. Pavese and L. Storme, Optimal subspace codes in $PG(4,q)$,, in preparation., (). Google Scholar

[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. Google Scholar

[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. Google Scholar

[11]

P. Dembowski, Finite Geometries,, Springer-Verlag, (1968). doi: 10.1007/978-3-642-62012-6. Google Scholar

[12]

U. Dempwolff, Translation planes of order 27,, Des. Codes Cryptogr., 4 (1994), 105. doi: 10.1007/BF01578865. Google Scholar

[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. Google Scholar

[14]

J. Eisfeld and L. Storme, (Partial) $t$-Spreads and Minimal $t$-Covers in Finite Projective Spaces,, Lecture notes, (2000). Google Scholar

[15]

T. Etzion, Problems on $q$-analogs in coding theory,, preprint, (). Google Scholar

[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. Google Scholar

[17]

T. Etzion and L. Storme, Galois geometries and coding theory,, Des. Codes Cryptogr., 78 (2016), 311. doi: 10.1007/s10623-015-0156-5. Google Scholar

[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. Google Scholar

[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. Google Scholar

[20]

T. Feulner, Canonical forms and automorphisms in the projective space,, preprint, (). Google Scholar

[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). Google Scholar

[22]

E. M. Gabidulin and M. Bossert, Algebraic codes for network coding,, Probl. Inform. Transm., 45 (2009), 343. doi: 10.1134/S003294600904005X. Google Scholar

[23]

J. Galambos and I. Simonelli, Bonferroni-Type Inequalities with Applications,, Springer-Verlag, (1996). Google Scholar

[24]

N. A. Gordon, R. Shaw and L. H. Soicher, Classification of partial spreads in $\PG(4,2)$,, available online at , (). Google Scholar

[25]

X. Guang and Z. Zhang, Linear Network Error Correction Coding,, Springer-Verlag, (2014). doi: 10.1007/978-1-4939-0588-1. Google Scholar

[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. Google Scholar

[27]

D. Heinlein, M. Kiermaier, S. Kurz and A. Wassermann, Tables of subspace codes,, preprint, (). Google Scholar

[28]

J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions,, Oxford Univ. Press, (1985). Google Scholar

[29]

J. W. P. Hirschfeld, Projective Geometries over Finite Fields,, Oxford Univ. Press, (1998). Google Scholar

[30]

J. W. P. Hirschfeld and J. A. Thas, General Galois Geometries,, Oxford Univ. Press, (1991). doi: 10.1007/978-1-4471-6790-7. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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 , (). Google Scholar

[34]

N. L. Johnson, V. Jha and M. Biliotti, Handbook of Finite Translation Planes,, CRC Press, (2007). doi: 10.1201/9781420011142. Google Scholar

[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. Google Scholar

[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. Google Scholar

[37]

J. H. van Lint and R. M. Wilson, A Course in Combinatorics,, Cambridge Univ. Press, (1992). Google Scholar

[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. Google Scholar

[39]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes,, North-Holland Publishing Company, (1977). Google Scholar

[40]

R. Mathon and G. F. Royle, The translation planes of order 49,, Des. Codes Cryptogr., 5 (1995), 57. doi: 10.1007/BF01388504. Google Scholar

[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. Google Scholar

[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. Google Scholar

[43]

S. Niskanen and P. R. J. Östergård, Cliquer User's Guide, Version 1.0,, Commun. Lab., (2003). Google Scholar

[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. Google Scholar

[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. Google Scholar

[46]

A.-L. Trautmann, Isometry and automorphisms of constant dimension codes,, Adv. Math. Commun., 7 (2013), 147. doi: 10.3934/amc.2013.7.147. Google Scholar

[47]

R. W. Yeung and N. Cai, Network error correction, part I: Basic concepts and upper bounds,, Commun. Inform. Syst., 6 (2006), 19. Google Scholar

[48]

R. W. Yeung and N. Cai, Network error correction, part II: Lower bounds,, Commun. Inform. Syst., 6 (2006), 37. Google Scholar

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. Google Scholar

[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. Google Scholar

[3]

J. De Beule and L. Storme, Current Research Topics in Galois Geometry,, Nova Science Publishers, (2011). Google Scholar

[4]

A. Beutelspacher, Partial spreads in finite projective spaces and partial designs,, Math. Z., 145 (1975), 211. doi: 10.1007/BF01215286. Google Scholar

[5]

M. Braun and J. Reichelt, $q$-analogs of packing designs,, J. Combin. Des., 22 (2014), 306. doi: 10.1002/jcd.21376. Google Scholar

[6]

P. J. Cameron and J. H. van Lint, Graphs, Codes and Designs,, Cambridge Univ. Press, (1980). Google Scholar

[7]

P. J. Cameron and J. H. van Lint, Designs, Graphs, Codes and their Links,, Cambridge Univ. Press, (1991). doi: 10.1017/CBO9780511623714. Google Scholar

[8]

A. Cossidente, F. Pavese and L. Storme, Optimal subspace codes in $PG(4,q)$,, in preparation., (). Google Scholar

[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. Google Scholar

[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. Google Scholar

[11]

P. Dembowski, Finite Geometries,, Springer-Verlag, (1968). doi: 10.1007/978-3-642-62012-6. Google Scholar

[12]

U. Dempwolff, Translation planes of order 27,, Des. Codes Cryptogr., 4 (1994), 105. doi: 10.1007/BF01578865. Google Scholar

[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. Google Scholar

[14]

J. Eisfeld and L. Storme, (Partial) $t$-Spreads and Minimal $t$-Covers in Finite Projective Spaces,, Lecture notes, (2000). Google Scholar

[15]

T. Etzion, Problems on $q$-analogs in coding theory,, preprint, (). Google Scholar

[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. Google Scholar

[17]

T. Etzion and L. Storme, Galois geometries and coding theory,, Des. Codes Cryptogr., 78 (2016), 311. doi: 10.1007/s10623-015-0156-5. Google Scholar

[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. Google Scholar

[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. Google Scholar

[20]

T. Feulner, Canonical forms and automorphisms in the projective space,, preprint, (). Google Scholar

[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). Google Scholar

[22]

E. M. Gabidulin and M. Bossert, Algebraic codes for network coding,, Probl. Inform. Transm., 45 (2009), 343. doi: 10.1134/S003294600904005X. Google Scholar

[23]

J. Galambos and I. Simonelli, Bonferroni-Type Inequalities with Applications,, Springer-Verlag, (1996). Google Scholar

[24]

N. A. Gordon, R. Shaw and L. H. Soicher, Classification of partial spreads in $\PG(4,2)$,, available online at , (). Google Scholar

[25]

X. Guang and Z. Zhang, Linear Network Error Correction Coding,, Springer-Verlag, (2014). doi: 10.1007/978-1-4939-0588-1. Google Scholar

[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. Google Scholar

[27]

D. Heinlein, M. Kiermaier, S. Kurz and A. Wassermann, Tables of subspace codes,, preprint, (). Google Scholar

[28]

J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions,, Oxford Univ. Press, (1985). Google Scholar

[29]

J. W. P. Hirschfeld, Projective Geometries over Finite Fields,, Oxford Univ. Press, (1998). Google Scholar

[30]

J. W. P. Hirschfeld and J. A. Thas, General Galois Geometries,, Oxford Univ. Press, (1991). doi: 10.1007/978-1-4471-6790-7. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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 , (). Google Scholar

[34]

N. L. Johnson, V. Jha and M. Biliotti, Handbook of Finite Translation Planes,, CRC Press, (2007). doi: 10.1201/9781420011142. Google Scholar

[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. Google Scholar

[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. Google Scholar

[37]

J. H. van Lint and R. M. Wilson, A Course in Combinatorics,, Cambridge Univ. Press, (1992). Google Scholar

[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. Google Scholar

[39]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes,, North-Holland Publishing Company, (1977). Google Scholar

[40]

R. Mathon and G. F. Royle, The translation planes of order 49,, Des. Codes Cryptogr., 5 (1995), 57. doi: 10.1007/BF01388504. Google Scholar

[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. Google Scholar

[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. Google Scholar

[43]

S. Niskanen and P. R. J. Östergård, Cliquer User's Guide, Version 1.0,, Commun. Lab., (2003). Google Scholar

[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. Google Scholar

[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. Google Scholar

[46]

A.-L. Trautmann, Isometry and automorphisms of constant dimension codes,, Adv. Math. Commun., 7 (2013), 147. doi: 10.3934/amc.2013.7.147. Google Scholar

[47]

R. W. Yeung and N. Cai, Network error correction, part I: Basic concepts and upper bounds,, Commun. Inform. Syst., 6 (2006), 19. Google Scholar

[48]

R. W. Yeung and N. Cai, Network error correction, part II: Lower bounds,, Commun. Inform. Syst., 6 (2006), 37. Google Scholar

[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, 2019, 15 (4) : 1881-1896. 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]

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
[13]

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
[14]

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
[15]

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
[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]

Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems & Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (5)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences