Optimal RS-like LRC codes of arbitrary length

Abstract

RS-like locally recoverable (LRC) codes have construction based on the classical construction of Reed–Solomon (RS) codes, where codewords are obtained as evaluations of suitably chosen polynomials. These codes were introduced by Tamo and Barg (IEEE Trans Inf Theory 60(8):4661–4676, 2014) where they assumed that the length n of the code is divisible by r+1r+1, where r is the locality of the code. They also proposed a construction with this condition lifted to n≠1mod(r+1)n≠1mod(r+1). In a recent paper, Kolosov et al. (Optimal LRC codes for all lenghts n≤qn≤q, arXiv:1802.00157, 2018) have given an explicit construction of optimal LRC codes with this lifted condition on n. In this paper we remove any such restriction on n completely, i.e., we propose constructions for q-ary RS-like LRC codes of any length n≤qn≤q. Further, we show that the codes constructed by the proposed construction are optimal LRC codes for their parameters.