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

Sascha Kurz

doi:10.3934/amc.2021069

Article Contents

2023, Volume 17, Issue 1: 152-171. Doi: 10.3934/amc.2021069

This issue Previous Article Construction for both self-dual codes and LCD codes Next Article Classification of $ \mathbf{(3 \!\mod 5)} $ arcs in $ \mathbf{ \operatorname{PG}(3,5)} $

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

Sascha Kurz

Mathematisches Institut, Universität Bayreuth, D-95440 Bayreuth, Germany

Received: August 2021

Revised: November 2021

Early access: January 2022

Published: December 2022

Abstract / Introduction Full Text(HTML) Figure(0) / Table(3) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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

Related Papers

Cited by

References

[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. Braun, P. 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. Chen, X. He, J. 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-Luerssen, K. 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. He, Y. 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. He, Y. Chen, Z. 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. Heinlein, M. Kiermaier, S. 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. Honold, M. 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. Honold, M. 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. Liu, Y. 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. Liu, Y. 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. Niu, Q. 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.