Xing Lin, Han Cai, Xiaohu Tang: On singleton-type bound of locally repairable codes

Journal:Discrete Mathematics

Abstract:The Singleton-type bound that offers an upper limit on the minimum Hamming distance for locally repairable codes (LRCs) has been studied by a lot of literatures. However, the work to determine tight Singleton-type bound for LRCs under all parameters is still incomplete. This paper focuses on the tightness of Singleton-type bound for general LRCs (linear and nonlinear). By exploring how the structure of repair sets affects the minimum Hamming distance, some properties for minimum Hamming distance of LRCs are derived. Through these properties, the following results are obtained: 1. The necessary conditions for LRCs whose minimum Hamming distance reaches the previous Singleton-type bound are provided. Due to these necessary conditions, the previous Singleton-type bound is proved to be unreachable under a number of parameters, and the tight Singleton-type bounds are given under some of these parameters. 2. Under a class of parameters where the previous Singleton-type bound for linear LRCs has been proved unreachable in the literatures, we improve Singleton-type bound and show that the new Singleton-type bound is tight. In addition, based on the existing LRC constructions, the previous Singleton-type bound for LRCs is shown to be tight under some other parameters. Finally, for an importance case of LRCs (i.e., every repair set is a 1-erasure correcting code), the Singleton-type bound under three classes of parameters is further improved.

Indexed by:SCI

Document Code:113987

Volume:347

Issue:7

Translation or Not:no

Date of Publication:2024-07-15

Included Journals:SCI

Links to published journals:https://www.sciencedirect.com/science/article/abs/pii/S0012365X24001183