An Integer Programming-Based Bound for Locally Repairable Codes

Anyu Wang, Zhifang Zhang

IEEE Transactions on Information Theory · 2015 · 70 citations · 21 references

Concepts

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 <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> > n <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> , where n <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> = ⌈(n/r + 1)⌉ and n2 = n <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> (r +1)-n. Finally, an explicit construction for LRCs attaining this upper bound is presented over the finite field F <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sub> ,where m ≥ n <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> r. Based on these r ≤ √n - 1 has been definitely determined, which is of great results, the largest possible minimum distance for all LRCs with significance in practical use.

References

21