Optimum Linear Codes With Support-Constrained Generator Matrices Over Small Fields

Hikmet Yildiz, Babak Hassibi

Abstract

We consider the problem of designing optimal linear codes (in terms of having the largest minimum distance) subject to a support constraint on the generator matrix. We show that the largest minimum distance can be achieved by a subcode of a Reed–Solomon code of small field size and with the same minimum distance. In particular, if the code has length <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> , and maximum minimum distance <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d$ </tex-math></inline-formula> (over all generator matrices with the given support), then an optimal code exists for any field size <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q\geq 2n-d$ </tex-math></inline-formula> . As a by-product of this result, we settle the GM–MDS conjecture in the affirmative.
BibTeX
@article{yildiz2019optimum,
  author = {Hikmet Yildiz and Babak Hassibi},
  title = {{Optimum Linear Codes With Support-Constrained Generator Matrices Over Small Fields}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  doi = {10.1109/tit.2019.2932663},
}

Loading related content...

Figure