Subspace packings: constructions and bounds
- PDF / 498,418 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 24 Downloads / 186 Views
Subspace packings: constructions and bounds Tuvi Etzion1 · Sascha Kurz2 · Kamil Otal3 · Ferruh Özbudak4 Received: 27 August 2019 / Revised: 31 December 2019 / Accepted: 1 February 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Grassmannian Gq (n, k) is the set of all k-dimensional subspaces of the vector space Fqn . Kötter and Kschischang showed that codes in Grassmannian space can be used for error-correction in random network coding. On the other hand, these codes are q-analogs of codes in the Johnson scheme, i.e. constant dimension codes. These codes of the Grassmannian Gq (n, k) also form a family of q-analogs of block designs and they are called subspace designs. In this paper, we examine one of the last families of q-analogs of block designs which was not considered before. This family called subspace packings is the q-analog of packings, and was considered recently for network coding solution for a family of multicast networks called the generalized combination networks. A subspace packing t-(n, k, λ)q is a set S of k-subspaces from Gq (n, k) such that each t-subspace of Gq (n, t) is contained in at most λ elements of S. The goal of this work is to consider the largest size of such subspace packings. We derive a sequence of lower and upper bounds on the maximum size of such packings, analyse these bounds, and identify the important problems for further research in this area. Keywords Subspace packings · Generalized combination networks · Vector network coding · q-analogs of designs · Grassmannian codes · Rank-metric codes Mathematics Subject Classification 94B65 · 94B60 · 51E20
This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Coding and Cryptography 2019”.
B
Ferruh Özbudak [email protected] Tuvi Etzion [email protected] Sascha Kurz [email protected] Kamil Otal [email protected]
1
Computer Science Department, Technion, 3200003 Haifa, Israel
2
University of Bayreuth, Bayreuth, Germany
3
TÜB˙ITAK B˙ILGEM UEKAE, Gebze, Turkey
4
Middle East Technical University, Ankara, Turkey
123
T. Etzion et al.
1 Introduction Network coding has been attracting increasing attention in the last fifteen years. The seminal work of Ahlswede et al. [1] and Li et al. [59] introduced the basic concepts of network coding and how network coding outperforms the well-known routing. This research area was developed rapidly in the last fifteen years and has a significant influence on other research areas as well. Random network coding which was introduced in [43,44] was an important step in the evolution of the research in network coding. One of the direction which was in the first line of research following the introduction of random network coding was the design of error-correcting codes for random network coding. Kötter and Kschischang [55] introduced a framework for error-correction in random network coding. Their model for the problem introduced a new type of error-correcting codes, so-called constant-dim
Data Loading...
