On the Combinatorics of Locally Repairable Codes via Matroid Theory

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; ) of LRCs are generalized to matroids, and the matroid analogue of the generalized Singleton bound in [P. Gopalan et al., 'On the locality of codeword symbols,' IEEE Trans. Inf. Theory] 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; ) 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 in [W. Song et al., 'Optimal locally repairable codes,' IEEE J. Sel. Areas Comm.].

DOI

10.1109/TIT.2016.2598149

Citation

Westerbäck, T, Freij-Hollanti, R, Ernvall, T & Hollanti, C 2016, 'On the Combinatorics of Locally Repairable Codes via Matroid Theory', IEEE Transactions on Information Theory, vol. 62, no. 10, 7555340, pp. 5296-5315. https://doi.org/10.1109/TIT.2016.2598149

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-201705315119

Collections

[article-cris] Perustieteiden korkeakoulu / SCI

Show all metadata

On the Combinatorics of Locally Repairable Codes via Matroid Theory

Access rights

URL

Journal Title

Journal ISSN

Volume Title

Authors

Date

Department

Major/Subject

Mcode

Degree programme

Language

Pages

Series

Abstract

Description

Keywords

Other note

DOI

Citation

Permanent link to this item

Collections