A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On the Combinatorics of Locally Repairable Codes via Matroid Theory
Tekijät: Westerback T, Freij-Hollanti R, Ernvall T, Hollanti C
Kustantaja: IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
Julkaisuvuosi: 2016
Lehti: IEEE Transactions on Information Theory
Tietokannassa oleva lehden nimi: IEEE TRANSACTIONS ON INFORMATION THEORY
Lehden akronyymi: IEEE T INFORM THEORY
Vuosikerta: 62
Numero: 10
Aloitussivu: 5296
Lopetussivu: 5315
Sivujen määrä: 20
ISSN: 0018-9448
DOI: https://doi.org/10.1109/TIT.2016.2598149
Tiivistelmä
This paper provides a link between matroid theory and locally repairable codes (LRCs) that are either linear or more generally almost affine. Using this link, new results on both LRCs and matroid theory are derived. The parameters (n, k, d, r, delta) of LRCs are generalized to matroids, and the matroid analog of the generalized singleton bound by Gopalan et al. for linear LRCs is given for matroids. It is shown that the given bound is not tight for certain classes of parameters, implying a nonexistence result for the corresponding locally repairable almost affine codes that are coined perfect in this paper. Constructions of classes of matroids with a large span of the parameters (n, k, d, r, delta) and the corresponding local repair sets are given. Using these matroid constructions, new LRCs are constructed with prescribed parameters. The existence results on linear LRCs and the nonexistence results on almost affine LRCs given in this paper strengthen the nonexistence and existence results on perfect linear LRCs given by Song et al.
This paper provides a link between matroid theory and locally repairable codes (LRCs) that are either linear or more generally almost affine. Using this link, new results on both LRCs and matroid theory are derived. The parameters (n, k, d, r, delta) of LRCs are generalized to matroids, and the matroid analog of the generalized singleton bound by Gopalan et al. for linear LRCs is given for matroids. It is shown that the given bound is not tight for certain classes of parameters, implying a nonexistence result for the corresponding locally repairable almost affine codes that are coined perfect in this paper. Constructions of classes of matroids with a large span of the parameters (n, k, d, r, delta) and the corresponding local repair sets are given. Using these matroid constructions, new LRCs are constructed with prescribed parameters. The existence results on linear LRCs and the nonexistence results on almost affine LRCs given in this paper strengthen the nonexistence and existence results on perfect linear LRCs given by Song et al.
Turun yliopiston Tutkimustietojärjestelmän portaali