IPM - Institute for Research in Fundamental Sciences

“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

Abstract:

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

“School of Mathematics”

People

Schools

Centers

Groups

E-Services

Publications