A4 Refereed article in a conference publication
Almost affine locally repairable codes and matroid theory
Authors: Thomas Westerbäck, Toni Ernvall, Camilla Hollanti
Conference name: IEEE information theory workshop
Publication year: 2014
Book title : 2014 IEEE Information Theory Workshop (ITW 2014)
First page : 621
Last page: 625
Number of pages: 5
ISBN: 978-1-4799-5999-0
ISSN: 2475-420X
DOI: https://doi.org/10.1109/ITW.2014.6970906
In this paper we provide a link between matroid theory and locally repairable codes (LRCs) that are almost affine. The parameters (n,k,d,r) of LRCs are generalized to matroids. A bound on the parameters (n,k,d,r), similar to the bound in [P. Gopalan et al., "On the locality of codeword symbols," IEEE Trans. Inf. Theory] for linear LRCs, is given for matroids. We prove that the given bound is not tight for a certain class of parameters, which implies a non-existence result for a certain class of optimal locally repairable almost affine codes. Constructions of optimal LRCs over small finite fields were stated as an open problem in [I. Tamo et al., "Optimal locally repairable codes and connections to matroid theory", 2013 IEEE ISIT}. In this paper optimal LRCs which do not require a large field are constructed for certain classes of parameters.