On binary matroid minors and applications to data storage over small fields

Matthias Grezet*, Ragnar Freij-Hollanti, Thomas Westerbäck, Camilla Hollanti

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)

Abstract

Locally repairable codes for distributed storage systems have gained a lot of interest recently, and various constructions can be found in the literature. However, most of the constructions result in either large field sizes and hence too high computational complexity for practical implementation, or in low rates translating into waste of the available storage space. In this paper we address this issue by developing theory towards code existence and design over a given field. This is done via exploiting recently established connections between linear locally repairable codes and matroids, and using matroid-theoretic characterisations of linearity over small fields. In particular, nonexistence can be shown by finding certain forbidden uniform minors within the lattice of cyclic flats. It is shown that the lattice of cyclic flats of binary matroids have additional structure that significantly restricts the possible locality properties of F2-linear storage codes. Moreover, a collection of criteria for detecting uniform minors from the lattice of cyclic flats of a given matroid is given, which is interesting in its own right.

Original languageEnglish
Title of host publicationCoding Theory and Applications
Subtitle of host publication5th International Castle Meeting, ICMCTA 2017, Vihula, Estonia, August 28-31, 2017, Proceedings
Pages139-153
Number of pages15
DOIs
Publication statusPublished - 2017
MoE publication typeA4 Article in a conference publication
EventInternational Castle Meeting on Coding Theory and Applications - Vihula, Estonia
Duration: 28 Aug 201731 Aug 2017
Conference number: 5

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Volume10495 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Castle Meeting on Coding Theory and Applications
Abbreviated titleICMCTA
CountryEstonia
CityVihula
Period28/08/201731/08/2017

Keywords

  • Binary matroids
  • Distributed storage systems
  • Lattice of cyclic flats
  • Locally repairable codes
  • Uniform minors

Fingerprint Dive into the research topics of 'On binary matroid minors and applications to data storage over small fields'. Together they form a unique fingerprint.

Cite this