Bounds on the maximal minimum distance of linear locally repairable codes

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

4 Citations (Scopus)
118 Downloads (Pure)

Abstract

Locally repairable codes (LRCs) are error correcting codes used in distributed data storage. Besides a global level, they enable errors to be corrected locally, reducing the need for communication between storage nodes. There is a close connection between almost affine LRCs and matroid theory which can be utilized to construct good LRCs and derive bounds on their performance. A generalized Singleton bound for linear LRCs with parameters (n; k; d; r; δ) was given in [N. Prakash et al., 'Optimal Linear Codes with a Local-Error-Correction Property', IEEE Int. Symp. Inf. Theory]. In this paper, a LRC achieving this bound is called perfect. Results on the existence and nonexistence of linear perfect (n; k; d; r; δ)-LRCs were given in [W. Song et al., 'Optimal locally repairable codes', IEEE J. Sel. Areas Comm.]. Using matroid theory, these existence and nonexistence results were later strengthened in [T. Westerbäck et al., 'On the Combinatorics of Locally Repairable Codes', Arxiv: 1501.00153], which also provided a general lower bound on the maximal achievable minimum distance dmax(n; k; r; δ) that a linear LRC with parameters (n; k; r; δ) can have. This article expands the class of parameters (n; k; d; r; δ) for which there exist perfect linear LRCs and improves the lower bound for dmax(n; k; r; δ). Further, this bound is proved to be optimal for the class of matroids that is used to derive the existence bounds of linear LRCs.

Original languageEnglish
Title of host publicationProceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
PublisherIEEE
Pages1586-1590
Number of pages5
Volume2016-August
ISBN (Electronic)978-1-5090-1806-2
DOIs
Publication statusPublished - 10 Aug 2016
MoE publication typeA4 Article in a conference publication
EventIEEE International Symposium on Information Theory - Barcelona, Spain
Duration: 10 Jul 201615 Jul 2016
http://www.isit2016.org/

Publication series

NameIEEE International Symposium on Information Theory
PublisherIEEE
ISSN (Print)2157-8095
ISSN (Electronic)2157-8117

Conference

ConferenceIEEE International Symposium on Information Theory
Abbreviated titleISIT
CountrySpain
CityBarcelona
Period10/07/201615/07/2016
Internet address

Fingerprint Dive into the research topics of 'Bounds on the maximal minimum distance of linear locally repairable codes'. Together they form a unique fingerprint.

Cite this