• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Almost Affine Locally Repairable Codes and Matroid Theory

Thomas Westerbäck, Toni Ernvall, Camilla Hollanti, Almost Affine Locally Repairable Codes and Matroid Theory. In: Emanuele Viterbo, Urbashi Mitra, Jean-Claude Belfiore, Mathiew Bloch, Joseph Boutros, Giuseppe Caire, Ananthanarayanan Chockalingam, Soura Dasgupta, Lara Dolecek, Michelle Effros, Uri Erez, Lu Gan, Gastpar (Eds.), 2014 IEEE Information Theory Workshop (ITW), 621–625, IEEE, 2014.

http://dx.doi.org/10.1109/ITW.2014.6970906

Abstract:

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.

BibTeX entry:

@INPROCEEDINGS{inpWeErHo14a,
  title = {Almost Affine Locally Repairable Codes and Matroid Theory},
  booktitle = {2014 IEEE Information Theory Workshop (ITW)},
  author = {Westerbäck, Thomas and Ernvall, Toni and Hollanti, Camilla},
  editor = {Viterbo, Emanuele and Mitra, Urbashi and Belfiore, Jean-Claude and Bloch, Mathiew and Boutros, Joseph and Caire, Giuseppe and Chockalingam, Ananthanarayanan and Dasgupta, Soura and Dolecek, Lara and Effros, Michelle and Erez, Uri and Gan, Lu and Gastpar},
  publisher = {IEEE},
  pages = {621–625},
  year = {2014},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication