An Integer Programming-Based Bound for Locally Repairable Codes

Author

Wang, Anyu ; Zhang, Zhifang

Author_Institution

State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China

Volume

61

Issue

10

fYear

2015

Firstpage

5280

Lastpage

5294

Abstract

The locally repairable code (LRC) studied in this paper is an $[n,k]$ linear code of which the value at each coordinate can be recovered by a linear combination of at most $r$ other coordinates. The central problem in this paper is to determine the largest possible minimum distance for LRCs. First, an integer programming-based upper bound is derived for any LRC. Then, by solving the programming problem under certain conditions, an explicit upper bound is obtained for LRCs with parameters $n_{1}>n_{2}$ , where $n_{1} = \\lceil ({n}/{r+1}) \\rceil$ and $n_{2} = n_{1} (r+1) - n$ . Finally, an explicit construction for LRCs attaining this upper bound is presented over the finite field $mathbb {F}_{2^{m}}$ , where $m\\geq n_{1}r$ . Based on these results, the largest possible minimum distance for all LRCs with $r \\le \\sqrt {n}-1$ has been definitely determined, which is of great significance in practical use.

Keywords

Generators; Linear codes; Linear programming; Maintenance engineering; Optimization; Silicon; Upper bound; Distributed storage; erasure codes; linear codes; locally repairable codes;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2015.2472515

Filename

7222428