\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

The interplay of different metrics for the construction of constant dimension codes

Abstract Full Text(HTML) Figure(0) / Table(3) Related Papers Cited by
  • A basic problem for constant dimension codes is to determine the maximum possible size $ A_q(n,d;k) $ of a set of $ k $-dimensional subspaces in $ \mathbb{F}_q^n $, called codewords, such that the subspace distance satisfies $ d_S(U,W): = 2k-2\dim(U\cap W)\ge d $ for all pairs of different codewords $ U $, $ W $. Constant dimension codes have applications in e.g. random linear network coding, cryptography, and distributed storage. Bounds for $ A_q(n,d;k) $ are the topic of many recent research papers. Providing a general framework we survey many of the latest constructions and show the potential for further improvements. As examples we give improved constructions for the cases $ A_q(10,4;5) $, $ A_q(11,4;4) $, $ A_q(12,6;6) $, and $ A_q(15,4;4) $. We also derive general upper bounds for subcodes arising in those constructions.

    Mathematics Subject Classification: Primary: 51E23, 05B40; Secondary: 11T71, 94B25.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Table 1.  Notation and abbreviations

    CDC constant dimension code
    MRD maximum rank distance
    FDRM Ferrers diagram rank metric
    $ d_S(U,W) $ subspace distance between codewords $ U $ and $ W $
    $ d_S( \mathcal{C}) $ minimum subspace distance of a CDC $ \mathcal{C} $
    $ d_H(u,w) $ Hamming distance between codewords $ u $ and $ w $
    $ d_H( \mathcal{S}) $ minimum Hamming distance of $ \mathcal{S} $
    $ d_H( \mathcal{V}, \mathcal{V}') $ minimum Hamming distance between a codeword in $ \mathcal{V} $ and
    a codeword in $ \mathcal{V}' $
    $ d_R(A,B) $ rank distance between two matrices $ A $ and $ B $
    $ \operatorname{rk}(A) $ rank of a matrix $ A $
    $ \mathcal{G}_1(n,k) $ set of binary vectors of length $ n $ and Hamming weight $ k $
    $ \mathcal{G}_q(n,k) $ set of $ k $-dimensional subspaces in $ \mathbb{F}_q^n $
    $\left[\begin{array}{l} n \\ k \end{array}\right]_{q} $ Gaussian binomial coefficient; $ \# \mathcal{G}_q(n,k) $
    $ A_q(n,d;k) $ maximum possible cardinality of a CDC $ \mathcal{C}\subseteq \mathcal{G}_{q}(n,k) $
    with minimum subspace distance at least $ d $
    $ m(q,m,n, d_R) $ number of codewords of an $ (m\times n, d_R)_q $-MRD code
    $ a(q,m,n, d_R,r) $ number of codewords of rank $ r $ in an additive $ (m\times n, d_R)_q $-MRD code
    $ E(U) $, $ E(M) $ matrix $ M $ or generator matrix of $ U $ in reduced row echelon form
    $ v(U) $, $ v(M) $ pivot vector
    $ {n_1 \choose k_1},\dots, {n_l \choose k_l} $ set of binary vectors
    $ T(U) $ Ferrers tableaux
    $ \mathcal{F}(U) $, $ \mathcal{F}(v) $ Ferrers diagram
    $ A_q(n,d;k; \mathcal{V}) $ max. possible cardinality of a CDC $ \mathcal{C}\subseteq \mathcal{G}_{q}(n,k) $ with min.
    subspace distance at least $ d $ whose codewords have pivot vectors in $ \mathcal{V} $
    $ I_k $ $ k\times k $ unit matrix
    $ e_i $ unit vector with a one at position $ i $
     | Show Table
    DownLoad: CSV

    Table 2.  Data for Lemma 3.4 with $ \mathcal{F}\in \mathcal{G}_1(5,2) $

    pivot vector size $ m(q, \mathcal{F},2) $ $ \# $ of cosets $ m(q, \mathcal{F},1)/m(q, \mathcal{F},2) $
    $ 11000 $ $ q^3 $ $ q^3 $
    $ 10100 $ $ q^2 $ $ q^3 $
    $ 10010 $ $ q $ $ q^3 $
    $ 10001 $ $ 1 $ $ q^3 $
    $ 01100 $ $ q^2 $ $ q^2 $
    $ 01010 $ $ q $ $ q^2 $
    $ 01001 $ $ 1 $ $ q^2 $
    $ 00110 $ $ 1 $ $ q^2 $
    $ 00101 $ $ 1 $ $ q $
    $ 00011 $ $ 1 $ $ 1 $
     | Show Table
    DownLoad: CSV

    Table 3.  Packing scheme for Proposition 3.7

    skeleton code size $ \# $ of used cosets
    $ \{11000,00110\} $ $ q^3+1 $ $ q^2 $
    $ \{11000,00101\} $ $ q^3+1 $ $ q $
    $ \{11000,00011\} $ $ q^3+1 $ $ 1 $
    $ \{11000\} $ $ q^3 $ $ q^3-q^2-q-1 $
    $ \{10100,01010\} $ $ q^2+q $ $ q^2 $
    $ \{10100,01001\} $ $ q^2+1 $ $ q^2 $
    $ \{10100\} $ $ q^2 $ $ q^3-2q^2 $
    $ \{01100,10010\} $ $ q^2+q $ $ q^2 $
    $ \{10010\} $ $ q $ $ q^3-q^2 $
    $ \{10001\} $ $ 1 $ $ q^3 $
     | Show Table
    DownLoad: CSV
  • [1] J. Antrobus and H. Gluesing-Luerssen, Maximal Ferrers diagram codes: Constructions and genericity considerations, IEEE Transactions on Information Theory, 65 (2019), 6204-6223.  doi: 10.1109/TIT.2019.2926256.
    [2] M. BraunP. R. J. Östergård and A. Wassermann, New lower bounds for binary constant-dimension subspace codes, Experimental Mathematics, 27 (2018), 179-183.  doi: 10.1080/10586458.2016.1239145.
    [3] H. ChenX. HeJ. Weng and L. Xu, New constructions of subspace codes using subsets of MRD codes in several blocks, IEEE Transactions on Information Theory, 66 (2020), 5317-5321.  doi: 10.1109/TIT.2020.2975776.
    [4] A. Cossidente, S. Kurz, G. Marino and F. Pavese, Combining subspace codes, Advances in Mathematics of Communications, (to appear), 15 pp.
    [5] A. Cossidente and F. Pavese, Subspace codes in PG(2n-1, q), Combinatorica, 37 (2017), 1073-1095.  doi: 10.1007/s00493-016-3354-5.
    [6] Ph. Delsarte, Bilinear forms over a finite field, with applications to coding theory, Journal of Combinatorial Theory, Series A, 25 (1978), 226-241.  doi: 10.1016/0097-3165(78)90015-8.
    [7] T. Etzion and N. Silberstein, Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams, IEEE Transactions on Information Theory, 55 (2009), 2909-2919.  doi: 10.1109/TIT.2009.2021376.
    [8] T. Etzion and A. Vardy, Error-correcting codes in projective space, IEEE Transactions on Information Theory, 57 (2011), 1165-1173.  doi: 10.1109/TIT.2010.2095232.
    [9] T. Feng, S. Kurz and S. Liu, Bounds for the multilevel construction, arXiv preprint, arXiv: 2011.06937, (2020), 95 pp.
    [10] M. Gadouleau and Z. Yan, Constant-rank codes and their connection to constant-dimension codes, IEEE Transactions on Information Theory, 56 (2010), 3207-3216.  doi: 10.1109/TIT.2010.2048447.
    [11] H. Gluesing-LuerssenK. Morrison and C. Troha, Cyclic orbit codes and stabilizer subfields, Advances in Mathematics of Communications, 9 (2015), 177-197.  doi: 10.3934/amc.2015.9.177.
    [12] H. Gluesing-Luerssen and C. Troha, Construction of subspace codes through linkage, Advances in Mathematics of Communications, 10 (2016), 525-540.  doi: 10.3934/amc.2016023.
    [13] M. Greferath, M. O. Pavčevi$\acute{\rm c} $, N. Silberstein and M. Á. Vázquez-Castro, Network Coding and Subspace Designs, Springer, 2018. doi: 10.1007/978-3-319-70293-3.
    [14] X. He, Construction of constant dimension codes from two parallel versions of linkage construction, IEEE Communications Letters, 24 (2020), 2392-2395.  doi: 10.1109/LCOMM.2020.3012488.
    [15] X. HeY. Chen and Z. Zhang, Improving the linkage construction with Echelon-Ferrers for constant-dimension codes, IEEE Communications Letters, 24 (2020), 1875-1879.  doi: 10.1109/LCOMM.2020.2997928.
    [16] X. HeY. ChenZ. Zhang and K. Zhou, New construction for constant dimension subspace codes via a composite structure, IEEE Communications Letters, 25 (2021), 1422-1426.  doi: 10.1109/LCOMM.2021.3052734.
    [17] D. Heinlein, Generalized linkage construction for constant-dimension codes, IEEE Transactions on Information Theory, 67 (2020), 705-715.  doi: 10.1109/TIT.2020.3038272.
    [18] D. Heinlein, M. Kiermaier, S. Kurz and A. Wassermann, Tables of subspace codes, arXiv preprint, arXiv: 1601.02864, (2016), 44 pp.
    [19] D. HeinleinM. KiermaierS. Kurz and A. Wassermann, A subspace code of size 333 in the setting of a binary q-analog of the Fano plane, Advances in Mathematics of Communications, 13 (2019), 457-475.  doi: 10.3934/amc.2019029.
    [20] D. Heinlein and S. Kurz, Asymptotic bounds for the sizes of constant dimension codes and an improved lower bound, in International Castle Meeting on Coding Theory and Applications, Springer, 2017,163–191. doi: 10.1007/978-3-319-66278-7_15.
    [21] D. Heinlein and S. Kurz, Coset construction for subspace codes, IEEE Transactions on Information Theory, 63 (2017), 7651-7660.  doi: 10.1109/TIT.2017.2753822.
    [22] 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, World Scientific, 2016,141–175.
    [23] T. HonoldM. Kiermaier and S. Kurz, Optimal binary subspace codes of length 6, constant dimension 3 and minimum distance 4, Contemp. Math., 632 (2015), 157-176.  doi: 10.1090/conm/632/12627.
    [24] T. HonoldM. Kiermaier and S. Kurz, Classification of large partial plane spreads in PG(6, 2) and related combinatorial objects, Journal of Geometry, 110 (2019), 1-31.  doi: 10.1007/s00022-018-0459-6.
    [25] M. Kiermaier and S. Kurz, On the lengths of divisible codes, IEEE Transactions on Information Theory, 66 (2020), 4051-4060.  doi: 10.1109/TIT.2020.2968832.
    [26] S. Kurz, A note on the linkage construction for constant dimension codes, arXiv preprint, arXiv: 1906.09780, (2019), 13 pp.
    [27] S. Kurz, Generalized LMRD code bounds for constant dimension codes, IEEE Communications Letters, 24 (2020), 2100-2103.  doi: 10.1109/LCOMM.2020.3003132.
    [28] S. Kurz, Lifted codes and the multilevel construction for constant dimension codes, arXiv preprint, arXiv: 2004.14241, (2020), 40 pp.
    [29] S. Kurz, Subspaces intersecting in at most a point, Designs, Codes and Cryptography, 88 (2020), 595-599.  doi: 10.1007/s10623-019-00699-6.
    [30] H. Lao, H. Chen, J. Weng and X. Tan, Parameter-controlled inserting constructions of constant dimension subspace codes, arXiv preprint, arXiv: 2008.09944, (2020), 48 pp.
    [31] F. Li, Construction of constant dimension subspace codes by modifying linkage construction, IEEE Transactions on Information Theory, 66 (2019), 2760-2764.  doi: 10.1109/TIT.2019.2960343.
    [32] S. LiuY. Chang and T. Feng, Constructions for optimal Ferrers diagram rank-metric codes, IEEE Transactions on Information Theory, 65 (2019), 4115-4130.  doi: 10.1109/TIT.2019.2894401.
    [33] S. LiuY. Chang and T. Feng, Parallel multilevel constructions for constant dimension codes, IEEE Transactions on Information Theory, 66 (2020), 6884-6897.  doi: 10.1109/TIT.2020.3004315.
    [34] Y. NiuQ. Yue and D. Huang, New constant dimension subspace codes from generalized inserting construction, IEEE Communications Letters, 25 (2020), 1066-1069.  doi: 10.1109/LCOMM.2020.3046042.
    [35] J. Sheekey, MRD codes: Constructions and connections, in Combinatorics and Finite Fields: Difference Sets, Polynomials, Pseudorandomness and Applications, vol. 23 of Radon Series on Computational and Applied Mathematics doi: 10.1515/9783110642094-013.
    [36] N. Silberstein and T. Etzion, Large constant dimension codes and lexicodes, Advances in Mathematics of Communications, 5 (2011), 177-189.  doi: 10.3934/amc.2011.5.177.
    [37] N. Silberstein and A.-L. Trautmann, Subspace codes based on graph matchings, Ferrers diagrams, and pending blocks, IEEE Transactions on Information Theory, 61 (2015), 3937-3953.  doi: 10.1109/TIT.2015.2435743.
    [38] A.-L. Trautmann and J. Rosenthal, New improvements on the Echelon-Ferrers construction, in Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems–MTNS, vol. 5.9, 2010, 405-408
    [39] S.-T. Xia and F.-W. Fu, Johnson type bounds on constant dimension codes, Designs, Codes and Cryptography, 50 (2009), 163-172.  doi: 10.1007/s10623-008-9221-7.
    [40] L. Xu and H. Chen, New constant-dimension subspace codes from maximum rank distance codes, IEEE Transactions on Information Theory, 64 (2018), 6315-6319.  doi: 10.1109/TIT.2018.2839596.
  • 加载中

Tables(3)

SHARE

Article Metrics

HTML views(2169) PDF downloads(409) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return