Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Construction of Maximally Recoverable Codes with Order-Optimal Field Size
212
0
0.0
(
0
)
Added by
Han Cai
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We construct maximally recoverable codes (corresponding to partial MDS codes) which are based on linearized Reed-Solomon codes. The new codes have a smaller field size requirement compared with known constructions. For certain asymptotic regimes, the constructed codes have order-optimal alphabet size, asymptotically matching the known lower bound.
rate research
Read More
Recently, it was discovered by several authors that a $q$-ary optimal locally recoverable code, i.e., a locally recoverable code archiving the Singleton-type bound, can have length much bigger than $q+1$. This is quite different from the classical $q$-ary MDS codes where it is conjectured that the code length is upper bounded by $q+1$ (or $q+2$ for some special case). This discovery inspired some recent studies on length of an optimal locally recoverable code. It was shown in cite{LXY} that a $q$-ary optimal locally recoverable code is unbounded for $d=3,4$. Soon after, it was proved that a $q$-ary optimal locally recoverable code with distance $d$ and locality $r$ can have length $Omega_{d,r}(q^{1 + 1/lfloor(d-3)/2rfloor})$. Recently, an explicit construction of $q$-ary optimal locally recoverable codes for distance $d=5,6$ was given in cite{J18} and cite{BCGLP}. In this paper, we further investigate construction optimal locally recoverable codes along the line of using parity-check matrices. Inspired by classical Reed-Solomon codes and cite{J18}, we equip parity-check matrices with the Vandermond structure. It is turns out that a parity-check matrix with the Vandermond structure produces an optimal locally recoverable code must obey certain disjoint property for subsets of $mathbb{F}_q$. To our surprise, this disjoint condition is equivalent to a well-studied problem in extremal graph theory. With the help of extremal graph theory, we succeed to improve all of the best known results in cite{GXY} for $dgeq 7$. In addition, for $d=6$, we are able to remove the constraint required in cite{J18} that $q$ is even.
Streaming codes are a class of packet-level erasure codes that ensure packet recovery over a sliding window channel which allows either a burst erasure of size $b$ or $a$ random erasures within any window of size $(tau+1)$ time units, under a strict decoding-delay constraint $tau$. The field size over which streaming codes are constructed is an important factor determining the complexity of implementation. The best known explicit rate-optimal streaming code requires a field size of $q^2$ where $q ge tau+b-a$ is a prime power. In this work, we present an explicit rate-optimal streaming code, for all possible ${a,b,tau}$ parameters, over a field of size $q^2$ for prime power $q ge tau$. This is the smallest-known field size of a general explicit rate-optimal construction that covers all ${a,b,tau}$ parameter sets. We achieve this by modifying the non-explicit code construction due to Krishnan et al. to make it explicit, without change in field size.
An $(m,n,a,b)$-tensor code consists of $mtimes n$ matrices whose columns satisfy `$a$ parity checks and rows satisfy `$b$ parity checks (i.e., a tensor code is the tensor product of a column code and row code). Tensor codes are useful in distributed storage because a single erasure can be corrected quickly either by reading its row or column. Maximally Recoverable (MR) Tensor Codes, introduced by Gopalan et al., are tensor codes which can correct every erasure pattern that is information theoretically possible to correct. The main questions about MR Tensor Codes are characterizing which erasure patterns are correctable and obtaining explicit constructions over small fields. In this paper, we study the important special case when $a=1$, i.e., the columns satisfy a single parity check equation. We introduce the notion of higher order MDS codes (MDS$(ell)$ codes) which is an interesting generalization of the well-known MDS codes, where $ell$ captures the order of genericity of points in a low-dimensional space. We then prove that a tensor code with $a=1$ is MR iff the row code is an MDS$(m)$ code. We then show that MDS$(m)$ codes satisfy some weak duality. Using this characterization and duality, we prove that $(m,n,a=1,b)$-MR tensor codes require fields of size $q=Omega_{m,b}(n^{min{b,m}-1})$. Our lower bound also extends to the setting of $a>1$. We also give a deterministic polynomial time algorithm to check if a given erasure pattern is correctable by the MR tensor code (when $a=1$).
A locally recoverable code is an error-correcting code such that any erasure in a coordinate of a codeword can be recovered from a set of other few coordinates. In this article we introduce a model of local recoverable codes that also includes local error detection. The cases of the Reed-Solomon and Locally Recoverable Reed-Solomon codes are treated in some detail.
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 $r ll epsilon log n$ and large $h ge Omega(n^{1-epsilon})$, we improve the field size from roughly $n^h$ to $n^{epsilon h}$. For the case of $a=1$ (one local parity check), we improve the field size quadratically from $r^{h(h+1)}$ to $r^{h lfloor (h+1)/2 rfloor}$ for some range of $r$. The improvements are modest, but more importantly are obtained in a unified manner via a promising new idea.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
