nach oben

Designs, Codes and Cryptography

Erschienen in:

03.09.2018

Classifying optimal binary subspace codes of length 8, constant dimension 4 and minimum distance 6

verfasst von: Daniel Heinlein, Thomas Honold, Michael Kiermaier, Sascha Kurz, Alfred Wassermann

Erschienen in: Designs, Codes and Cryptography | Ausgabe 2-3/2019

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We determine the maximum size \(A_2(8,6;4)\) of a binary subspace code of packet length \(v=8\), minimum subspace distance \(d=6\), and constant dimension \(k=4\) to be 257. There are two isomorphism types of optimal codes. Both of them are extended LMRD codes. In finite geometry terms, the maximum number of solids in \({\text {PG}}(7,2)\) mutually intersecting in at most a point is 257. The result was obtained by combining the classification of substructures with integer linear programming techniques. This result implies that the maximum size \(A_2(8,6)\) of a binary mixed-dimension subspace code of packet length 8 and minimum subspace distance 6 is 257 as well.

Vorheriger Artikel Classification of optimal (v, k, 1) binary cyclically permutable constant weight codes with 6 and 7 and small lengths

Nächster Artikel The graph structure of Chebyshev polynomials over finite fields and applications

Nur mit Berechtigung zugänglich

As an example we consider \(A_2(9,6;4)\le \left\{ \left[ {\begin{matrix}{9}\\ {1}\end{matrix}}\right] _{2}A_2(8,6;3)/\left[ {\begin{matrix}{4}\\ {1}\end{matrix}}\right] _{2}\right\} _4= \left\{ \frac{17374}{15}\right\} _4\), using \(A_2(8,6;3)=34\). We have \(\left\lfloor \frac{17374}{15} \right\rfloor =1158\), \(17374-1158\cdot 15=4\), \(17374-1157\cdot 15=19\), and \(17374-1156\cdot 15=34\). Since 4 and 19 cannot be written as a non-negative linear combination of 8, 12, 14, and 15, but \(34=14+12+8\), we have \(A_2(9,6;4)\le 1156\), which improves upon the iterative Johnson bound by two. Let us remark that [19] contains an easy and fast algorithm to check the representability as non-negative integer linear combination as specified above.

Algorithmic methods taking into account known symmetries of integer linear programming formulations automatically are presented in the literature. However, we are not aware of any paper, where those approaches have been successfully applied to compute tightened upper bounds for CDCs.

Since \({\text {Stab}}_{{\text {GL}}\left( \mathbb {F}^{8}_{2}\right) }\left( \widetilde{H}\right) = \left\{ \left( {\begin{matrix}A &{} 0 \\ b &{} 1\end{matrix}}\right) \in {\text {GL}}\left( \mathbb {F}^{8}_{2}\right) \,\left| \, A \in {\text {GL}}\left( \mathbb {F}^{7}_{2}\right) \text { and } b\in \mathbb {F}_2^{7} \right. \right\} \), any point that is not incident with \(\widetilde{H}\), i.e., \(\langle (p\mid 1)\rangle \) with \(p \in \mathbb {F}_2^{7}\), can be mapped via \(\left( {\begin{matrix}I_7 &{} 0 \\ p &{} 1\end{matrix}}\right) ^{-1}\) to \(\widetilde{P}\).

We noticed that the order of the vertices makes a huge difference for the running time. For fast results, matrices with the same last row should be numbered consecutively.

http://www.hpc.uni-bayreuth.de.

Beutelspacher A.: Partial spreads in finite projective spaces and partial designs. Math. Z. 145(3), 211–229 (1975).MathSciNetCrossRefMATH

Braun M., Etzion T., Ostergård P.R.J., Vardy A., Wassermann A.: Existence of \(q\)-analogs of Steiner systems. Forum Math. Pi 4, e7–14 (2016). https://doi.org/10.1017/fmp.2016.5.MathSciNetCrossRefMATH

Delsarte P.: Bilinear forms over a finite field, with applications to coding theory. J. Comb. Theory Ser. A 25(3), 226–241 (1978).MathSciNetCrossRefMATH

Etzion T., Silberstein N.: Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams. IEEE Trans. Inform. Theory 55(7), 2909–2919 (2009).MathSciNetCrossRefMATH

Etzion T., Silberstein N.: Codes and designs related to lifted MRD codes. IEEE Trans. Inform. Theory 59(2), 1004–1017 (2013).MathSciNetCrossRefMATH

Etzion T., Storme L.: Galois geometries and coding theory. Des. Codes Cryptogr. 78(1), 311–350 (2016).MathSciNetCrossRefMATH

Etzion T., Vardy A.: Error-correcting codes in projective space. IEEE Trans. Inform. Theory 57(2), 1165–1173 (2011).MathSciNetCrossRefMATH

Gabidulin E.M.: Theory of codes with maximum rank distance. Probl. Pereda. Inform. 21(1), 3–16 (1985).MathSciNetMATH

Heinlein D., Kurz S.: Asymptotic bounds for the sizes of constant dimension codes and an improved lower bound. In: 5th International Castle Meeting on Coding Theory and Applications, pp. 1–30 (2017). arxiv:1703.08712.

10.

Heinlein D., Kurz S.: An upper bound for binary subspace codes of length \(8\), constant dimension \(4\) and minimum distance \(6\). In: The Tenth International Workshop on Coding and Cryptography. (2017). arxiv:1705.03835.

11.

Heinlein D., Kiermaier M., Kurz S., Wassermann A.: Tables of subspace codes. (2016). arxiv:1601.02864.

12.

Heinlein D., Honold T., Kiermaier M., Kurz S.: Classification of binary MRD codes. (in preparation).

13.

Honold T., Kiermaier M., Kurz S.: Optimal binary subspace codes of length \(6\), constant dimension \(3\) and minimum subspace distance \(4\). Contemp. Math. 632, 157–176 (2015).MathSciNetCrossRefMATH

14.

Honold T., Kiermaier M., Kurz S.: Classification of large partial plane spreads in PG(6, 2) and related combinatorial objects. (2016). arxiv:1606.07655.

15.

Honold T., Kiermaier M., Kurz S.: Constructions and bounds for mixed-dimension subspace codes. Adv. Math. Commun. 10(3), 649–682 (2016).MathSciNetCrossRefMATH

16.

Honold T., Kiermaier M., Kurz S.: Partial spreads and vector space partitions. In: Greferath M., Pavčević M., Silberstein N., Vazquez-Castro A. (eds.) Network Coding and Subspace Designs. Springer, New York. (2018). arxiv:1611.06328.

17.

IBM: IBM ILOG CPLEX Optimizer (2010). http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/.

18.

Johnson S.: A new upper bound for error-correcting codes. IRE Trans. Inform. Theory 8(3), 203–207 (1962).MathSciNetCrossRefMATH

19.

Kiermaier M., Kurz S.: An improvement of the Johnson bound for subspace codes. (2017). arxiv:1707.00650.

20.

Kötter R., Kschischang F.R.: Coding for errors and erasures in random network coding. IEEE Trans. Inform. Theory 54(8), 3579–3591 (2008).MathSciNetCrossRefMATH

21.

Kurz S.: Improved upper bounds for partial spreads. Des. Codes Cryptogr. 85(1), 97–106 (2017).MathSciNetCrossRefMATH

22.

Kurz S.: Packing vector spaces into vector spaces. Aust. J. Comb. 68(1), 122–130 (2017).MathSciNetMATH

23.

MacWilliams F.J., Sloane N.J.A.: The Theory of Error-correcting Codes. I, vol. 16. North-Holland Mathematical LibraryNorth-Holland Publishing Co, Amsterdam (1977).MATH

24.

Năstase E.L., Sissokho P.A.: The maximum size of a partial spread in a finite projective space. J. Comb. Theory Ser. A 152, 353–362 (2017).MathSciNetCrossRefMATH

25.

Niskanen S., Östergård P.R.J.: Cliquer user’s guide, version 1.0. Tech. Rep. T48, Communications Laboratory, Helsinki University of Technology, Espoo, Finland (2003).

26.

Roth R.M.: Maximum-rank array codes and their application to crisscross error correction. IEEE Trans. Inform. Theory 37(2), 328–336 (1991).MathSciNetCrossRefMATH

27.

Xia S.T., Fu F.W.: Johnson type bounds on constant dimension codes. Des. Codes Cryptogr. 50(2), 163–172 (2009).MathSciNetCrossRefMATH

Titel: Classifying optimal binary subspace codes of length 8, constant dimension 4 and minimum distance 6
verfasst von: Daniel Heinlein
Thomas Honold
Michael Kiermaier
Sascha Kurz
Alfred Wassermann
Publikationsdatum: 03.09.2018
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 2-3/2019
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-018-0544-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 2-3/2019

The covering radii of a class of binary cyclic codes and some BCH codes

Linear codes from weakly regular plateaued functions and their secret sharing schemes

Local distributions for eigenfunctions and perfect colorings of q-ary Hamming graph

Duplication-correcting codes

Evaluating Bernstein–Rabin–Winograd polynomials

Identifying an unknown code by partial Gaussian elimination