Almost affine locally repairable codes and matroid theory
: Thomas Westerbäck, Toni Ernvall, Camilla Hollanti
: IEEE information theory workshop
: 2014
: 2014 IEEE Information Theory Workshop (ITW 2014)
: 621
: 625
: 5
: 978-1-4799-5999-0
: 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.