Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields

DOI10.1109/TIT.2020.2988459MaRDI QIDQ5138799zbMATH OpenOpenAlexFDO

Authors Lingfei Jin, Chaoping Xing, Venkatesan Guruswami

Publication date 4 December 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.04539

zbMATH Keywords

function fieldslocal reconstruction codes (LRC)

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Decoding (94B35)

Abstract: Local Reconstruction Codes (LRCs) allow for recovery from a small number of erasures in a local manner based on just a few other codeword symbols. A maximally recoverable (MR) LRC offers the best possible blend of such local and global fault tolerance, guaranteeing recovery from all erasure patterns which are information-theoretically correctable given the presence of local recovery groups. In an $(n,r,h,a)$-LRC, the $n$ codeword symbols are partitioned into $r$ disjoint groups each of which include $a$ local parity checks capable of locally correcting $a$ erasures. MR LRCs have received much attention recently, with many explicit constructions covering different regimes of parameters. Unfortunately, all known constructions require a large field size that exponential in $h$ or $a$, and it is of interest to obtain MR LRCs of minimal possible field size. In this work, we develop an approach based on function fields to construct MR LRCs. Our method recovers, and in most parameter regimes improves, the field size of previous approaches. For instance, for the case of small $rllepsilonlogn$ and large $hgeOmega(n^{1-epsilon})$, we improve the field size from roughly $n^h$ to $n^{epsilonh}$. For the case of $a=1$ (one local parity check), we improve the field size quadratically from $r^{h(h+1)}$ to $r^{hlfloor(h+1)/2floor}$ for some range of $r$. The improvements are modest, but more importantly are obtained in a unified manner via a promising new idea.

Cited in

(10)

• A construction of maximally recoverable codes
• On good polynomials over finite fields for optimal locally recoverable codes
• Construction of global function fields from linear codes and vice versa
• Constructing Partial MDS Codes from Reducible Algebraic Curves
• A general family of MSRD codes and PMDS codes with smaller field sizes from extended Moore matrices
• Codes for Distributed Storage
• Codes in the sum-rank metric: fundamentals and applications
• Locally maximal recoverable codes and LMR-LCD codes
• A new construction of maximally recoverable codes with hierarchical locality
• Locally maximal recoverable codes with unequal localities and LMR codes with hierarchical locality

This page was built for publication: Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5138799)