Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userVisible Rank and Codes with Locality
101
0
0.0
(
0
)
Added by
Omar Alrabiah
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We propose a framework to study the effect of local recovery requirements of codeword symbols on the dimension of linear codes, based on a combinatorial proxy that we call emph{visible rank}. The locality constraints of a linear code are stipulated by a matrix $H$ of $star$s and $0$s (which we call a stencil), whose rows correspond to the local parity checks (with the $star$s indicating the support of the check). The visible rank of $H$ is the largest $r$ for which there is a $r times r$ submatrix in $H$ with a unique generalized diagonal of $star$s. The visible rank yields a field-independent combinatorial lower bound on the rank of $H$ and thus the co-dimension of the code. We prove a rank-nullity type theorem relating visible rank to the rank of an associated construct called emph{symmetric spanoid}, which was introduced by Dvir, Gopi, Gu, and Wigderson~cite{DGGW20}. Using this connection and a construction of appropriate stencils, we answer a question posed in cite{DGGW20} and demonstrate that symmetric spanoid rank cannot improve the currently best known $widetilde{O}(n^{(q-2)/(q-1)})$ upper bound on the dimension of $q$-query locally correctable codes (LCCs) of length $n$. We also study the $t$-Disjoint Repair Group Property ($t$-DRGP) of codes where each codeword symbol must belong to $t$ disjoint check equations. It is known that linear $2$-DRGP codes must have co-dimension $Omega(sqrt{n})$. We show that there are stencils corresponding to $2$-DRGP with visible rank as small as $O(log n)$. However, we show the second tensor of any $2$-DRGP stencil has visible rank $Omega(n)$, thus recovering the $Omega(sqrt{n})$ lower bound for $2$-DRGP. For $q$-LCC, however, the $k$th tensor power for $kle n^{o(1)}$ is unable to improve the $widetilde{O}(n^{(q-2)/(q-1)})$ upper bound on the dimension of $q$-LCCs by a polynomial factor.
rate research
Read More
Locally recoverable codes were introduced by Gopalan et al. in 2012, and in the same year Prakash et al. introduced the concept of codes with locality, which are a type of locally recoverable codes. In this work we introduce a new family of codes with locality, which are subcodes of a certain family of evaluation codes. We determine the dimension of these codes, and also bounds for the minimum distance. We present the true values of the minimum distance in special cases, and also show that elements of this family are optimal codes, as defined by Prakash et al.
In this work we present a class of locally recoverable codes, i.e. codes where an erasure at a position $P$ of a codeword may be recovered from the knowledge of the entries in the positions of a recovery set $R_P$. The codes in the class that we define have availability, meaning that for each position $P$ there are several distinct recovery sets. Also, the entry at position $P$ may be recovered even in the presence of erasures in some of the positions of the recovery sets, and the number of supported erasures may vary among the various recovery sets.
A new type of spatially coupled low-density parity-check (SC-LDPC) codes motivated by practical storage applications is presented. SC-LDPCL codes (suffix L stands for locality) can be decoded locally at the level of sub-blocks that are much smaller than the full code block, thus offering flexible access to the coded information alongside the strong reliability of the global full-block decoding. Toward that, we propose constructions of SC-LDPCL codes that allow controlling the trade-off between local and global correction performance. In addition to local and global decoding, the paper develops a density-evolution analysis for a decoding mode we call semi-global decoding, in which the decoder has access to the requested sub-block plus a prescribed number of sub-blocks around it. SC-LDPCL codes are also studied under a channel model with variability across sub-blocks, for which decoding-performance lower bounds are derived.
Node failures are inevitable in distributed storage systems (DSS). To enable efficient repair when faced with such failures, two main techniques are known: Regenerating codes, i.e., codes that minimize the total repair bandwidth; and codes with locality, which minimize the number of nodes participating in the repair process. This paper focuses on regenerating codes with locality, using pre-coding based on Gabidulin codes, and presents constructions that utilize minimum bandwidth regenerating (MBR) local codes. The constructions achieve maximum resilience (i.e., optimal minimum distance) and have maximum capacity (i.e., maximum rate). Finally, the same pre-coding mechanism can be combined with a subclass of fractional-repetition codes to enable maximum resilience and repair-by-transfer simultaneously.
This paper extends the study of rank-metric codes in extension fields $mathbb{L}$ equipped with an arbitrary Galois group $G = mathrm{Gal}(mathbb{L}/mathbb{K})$. We propose a framework for studying these codes as subspaces of the group algebra $mathbb{L}[G]$, and we relate this point of view with usual notions of rank-metric codes in $mathbb{L}^N$ or in $mathbb{K}^{Ntimes N}$, where $N = [mathbb{L} : mathbb{K}]$. We then adapt the notion of error-correcting pairs to this context, in order to provide a non-trivial decoding algorithm for these codes. We then focus on the case where $G$ is abelian, which leads us to see codewords as elements of a multivariate skew polynomial ring. We prove that we can bound the dimension of the vector space of zeroes of these polynomials, depending of their degree. This result can be seen as an analogue of Alon-Furedi theorem -- and by means, of Schwartz-Zippel lemma -- in the rank metric. Finally, we construct the counterparts of Reed-Muller codes in the rank metric, and we give their parameters. We also show the connection between these codes and classical Reed-Muller codes in the case where $mathbb{L}$ is a Kummer extension.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
