“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 17578
School of Mathematics
  Title:   Locally Recoverable Codes over $Z_{P^S}$
  Author(s):  Hassan Khodaiemehr ( Joint with N. Abdi Kourani and M. J. Nikmehr)
  Status:   Published
  Journal: IEEE Transactions on Communications
  Vol.:  72
  Year:  2024
  Pages:   1-16
  Supported by:  IPM
Locally recoverable codes (LRCs) play a vital role in distributed storage systems where the failure or unavailability of storage devices is a common occurrence. The purpose of LRCs is to facilitate the repair processes required to recover lost or damaged data in such systems. A code $C$ will be said $\left(r,\delta\right)$-LRC if for each $i$, the $i$th component of codewords have locality $(r, \delta)$, that is, there exists a punctured subcode of $C$ with support containing $i$, whose length is at most $r + \delta - 1$, and whose minimum distance is at least $\delta$. An $(r, \delta)$-LRC with locality $(r, \delta)$ allows for the local recovery of any $\delta-1$ nodes by accessing information from $r$ other nodes. In this paper, we present new constructions of $\left(r,\delta\right)$-LRCs, with $2\leq\delta \leq \frac{p-1}{t}$ over $\mathbb{Z}_{p^s}$, where $t$ divides $p-1$ and $t\neq p-1$. Initially, we provide generator matrices for $\left(r,2\right)$-LRCs, among which one instance is considered as Singleton-Type Bound (STB)-optimal, a notion introduced in this paper. Also, we present a method for recovering an erased symbol in a codeword of our $\left(r,2\right)$-LRC. \textcolor{mycolor2}{For this aim, we use the polynomial interpolation over $\mathbb{Z}_{p^s}$ proposed by Gopalan. Next, we present the parity-check matrices for another family of $\left(r,\delta\right)$-LRCs over $\mathbb{Z}_{p^s}$, and construct two instances of STB-optimal $\left(r,\delta\right)$-LRCs. To the best of our knowledge, this paper presents the first study on ring-based LRCs. The proposed LRCs over $\mathbb{Z}_{p^s}$ exhibit certain design restrictions compared to LRCs over $\mathbb{F}_{p^s}$. \textcolor{mycolor2_rev2}{However, we provide two advantages for LRCs over $\mathbb{Z}_{p^s}$. First, we analyze Boolean circuits for arithmetic operations and demonstrate that the complexity of implementing multiplication in $\mathbb{Z}_{p^s}$, the operation with the highest cost in our algorithms, is considerably lower than in $\mathbb{F}_{p^s}$. This highlights the superior performance of our LRCs in terms of implementation speed and cost-efficiency compared to their counterparts. Next, we offer an example illustrating that the Gray image of particular $\mathbb{Z}_{p^{s+1}}$-LRCs of length $n$ results in LRCs of length $np^s$ over $\mathbb{F}_{p}$, which may not necessarily be linear. This introduces a novel class of LRCs, prompting further exploration of the connections between existing nonlinear LRCs in finite fields and linear ring-based LRCs.

Download TeX format
back to top
scroll left or right