CaltechAUTHORS
  A Caltech Library Service

Gabidulin Codes with Support Constrained Generator Matrices

Yildiz, Hikmet and Hassibi, Babak (2019) Gabidulin Codes with Support Constrained Generator Matrices. IEEE Transactions on Information Theory . ISSN 0018-9448. (In Press) https://resolver.caltech.edu/CaltechAUTHORS:20190401-161416001

[img] PDF - Submitted Version
See Usage Policy.

261Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190401-161416001

Abstract

Gabidulin codes are the first general construction of linear codes that are maximum rank distant (MRD). They have found applications in linear network coding, for example, when the transmitter and receiver are oblivious to the inner workings and topology of the network (the so-called incoherent regime). The reason is that Gabidulin codes can be used to map information to linear subspaces, which in the absence of errors cannot be altered by linear operations, and in the presence of errors can be corrected if the subspace is perturbed by a small rank. Furthermore, in distributed coding and distributed systems, one is led to the design of error correcting codes whose generator matrix must satisfy a given support constraint. In this paper, we give necessary and sufficient conditions on the support of the generator matrix that guarantees the existence of Gabidulin codes and general MRD codes. When the rate of the code is not very high, this is achieved with the same field size necessary for Gabidulin codes with no support constraint. When these conditions are not satisfied, we characterize the largest possible rank distance under the support constraints and show that they can be achieved by subcodes of Gabidulin codes. The necessary and sufficient conditions are identical to those that appear for MDS codes which were recently proven by Yildiz et al. and Lovett in the context of settling the GM-MDS conjecture.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/tit.2019.2955106DOIArticle
https://arxiv.org/abs/1903.09360arXivDiscussion Paper
ORCID:
AuthorORCID
Yildiz, Hikmet0000-0002-0891-3352
Additional Information:© 2019 IEEE. This work was supported in part by the National Science Foundation under Grant CNS-0932428, Grant CCF-1018927, Grant CCF-1423663, and Grant CCF-1409204, in part by Qualcomm Inc., in part by the NASAs Jet Propulsion Laboratory through the President and Directors Fund, and in part by the King Abdullah University of Science and Technology. This paper was presented in part at the Information Theory Workshop.
Funders:
Funding AgencyGrant Number
NSFCNS-0932428
NSFCCF-1018927
NSFCCF-1423663
NSFCCF-1409204
Qualcomm Inc.UNSPECIFIED
JPL President and Director's FundUNSPECIFIED
King Abdullah University of Science and Technology (KAUST)UNSPECIFIED
Subject Keywords:Gabidulin codes, rank distance, network coding, distributed systems
Record Number:CaltechAUTHORS:20190401-161416001
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190401-161416001
Official Citation:H. Yildiz and B. Hassibi, "Gabidulin Codes with Support Constrained Generator Matrices," in IEEE Transactions on Information Theory. doi: 10.1109/TIT.2019.2955106
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94336
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:01 Apr 2019 23:39
Last Modified:04 Dec 2019 21:47

Repository Staff Only: item control page