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

DOIhttps://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.




Last updated on 2024-26-11 at 23:22