Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRepairable Fountain Codes
113
0
0.0
(
0
)
Added by
Megasthenis Asteris
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We introduce a new family of Fountain codes that are systematic and also have sparse parities. Given an input of $k$ symbols, our codes produce an unbounded number of output symbols, generating each parity independently by linearly combining a logarithmic number of randomly selected input symbols. The construction guarantees that for any $epsilon>0$ accessing a random subset of $(1+epsilon)k$ encoded symbols, asymptotically suffices to recover the $k$ input symbols with high probability. Our codes have the additional benefit of logarithmic locality: a single lost symbol can be repaired by accessing a subset of $O(log k)$ of the remaining encoded symbols. This is a desired property for distributed storage systems where symbols are spread over a network of storage nodes. Beyond recovery upon loss, local reconstruction provides an efficient alternative for reading symbols that cannot be accessed directly. In our code, a logarithmic number of disjoint local groups is associated with each systematic symbol, allowing multiple parallel reads. Our main mathematical contribution involves analyzing the rank of sparse random matrices with specific structure over finite fields. We rely on establishing that a new family of sparse random bipartite graphs have perfect matchings with high probability.
rate research
Read More
Network-coded multiple access (NCMA) is a communication scheme for wireless multiple-access networks where physical-layer network coding (PNC) is employed. In NCMA, a user encodes and spreads its message into multiple packets. Time is slotted and multiple users transmit packets (one packet each) simultaneously in each timeslot. A sink node aims to decode the messages of all the users from the sequence of receptions over successive timeslots. For each timeslot, the NCMA receiver recovers multiple linear combinations of the packets transmitted in that timeslot, forming a system of linear equations. Different systems of linear equations are recovered in different timeslots. A message decoder then recovers the original messages of all the users by jointly solving multiple systems of linear equations obtained over different timeslots. We propose a low-complexity digital fountain approach for this coding problem, where each source node encodes its message into a sequence of packets using a fountain code. The aforementioned systems of linear equations recovered by the NCMA receiver effectively couple these fountain codes together. We refer to the coupling of the fountain codes as a linearly-coupled (LC) fountain code. The ordinary belief propagation (BP) decoding algorithm for conventional fountain codes is not optimal for LC fountain codes. We propose a batched BP decoding algorithm and analyze the convergence of the algorithm for general LC fountain codes. We demonstrate how to optimize the degree distributions and show by numerical results that the achievable rate region is nearly optimal. Our approach significantly reduces the decoding complexity compared with the previous NCMA schemes based on Reed-Solomon codes and random linear codes, and hence has the potential to increase throughput and decrease delay in computation-limited NCMA systems.
In this work it is shown that locally repairable codes (LRCs) can be list-decoded efficiently beyond the Johnson radius for a large range of parameters by utilizing the local error-correction capabilities. The corresponding decoding radius is derived and the asymptotic behavior is analyzed. A general list-decoding algorithm for LRCs that achieves this radius is proposed along with an explicit realization for LRCs that are subcodes of Reed--Solomon codes (such as, e.g., Tamo--Barg LRCs). Further, a probabilistic algorithm of low complexity for unique decoding of LRCs is given and its success probability is analyzed. The second part of this work considers error decoding of LRCs and partial maximum distance separable (PMDS) codes through interleaved decoding. For a specific class of LRCs the success probability of interleaved decoding is investigated. For PMDS codes, it is shown that there is a wide range of parameters for which interleaved decoding can increase their decoding radius beyond the minimum distance such that the probability of successful decoding approaches $1$ when the code length goes to infinity.
This paper aims to go beyond resilience into the study of security and local-repairability for distributed storage systems (DSS). Security and local-repairability are both important as features of an efficient storage system, and this paper aims to understand the trade-offs between resilience, security, and local-repairability in these systems. In particular, this paper first investigates security in the presence of colluding eavesdroppers, where eavesdroppers are assumed to work together in decoding stored information. Second, the paper focuses on coding schemes that enable optimal local repairs. It further brings these two concepts together, to develop locally repairable coding schemes for DSS that are secure against eavesdroppers. The main results of this paper include: a. An improved bound on the secrecy capacity for minimum storage regenerating codes, b. secure coding schemes that achieve the bound for some special cases, c. a new bound on minimum distance for locally repairable codes, d. code construction for locally repairable codes that attain the minimum distance bound, and e. repair-bandwidth-efficient locally repairable codes with and without security constraints.
We consider error decoding of locally repairable codes (LRC) and partial MDS (PMDS) codes through interleaved decoding. For a specific class of LRCs we investigate the success probability of interleaved decoding. For PMDS codes we show that there is a wide range of parameters for which interleaved decoding can increase their decoding radius beyond the minimum distance with the probability of successful decoding approaching $1$, when the code length goes to infinity.
Locally repairable codes with locality $r$ ($r$-LRCs for short) were introduced by Gopalan et al. cite{1} to recover a failed node of the code from at most other $r$ available nodes. And then $(r,delta)$ locally repairable codes ($(r,delta)$-LRCs for short) were produced by Prakash et al. cite{2} for tolerating multiple failed nodes. An $r$-LRC can be viewed as an $(r,2)$-LRC. An $(r,delta)$-LRC is called optimal if it achieves the Singleton-type bound. It has been a great challenge to construct $q$-ary optimal $(r,delta)$-LRCs with length much larger than $q$. Surprisingly, Luo et al. cite{3} presented a construction of $q$-ary optimal $r$-LRCs of minimum distances 3 and 4 with unbounded lengths (i.e., lengths of these codes are independent of $q$) via cyclic codes. In this paper, inspired by the work of cite{3}, we firstly construct two classes of optimal cyclic $(r,delta)$-LRCs with unbounded lengths and minimum distances $delta+1$ or $delta+2$, which generalize the results about the $delta=2$ case given in cite{3}. Secondly, with a slightly stronger condition, we present a construction of optimal cyclic $(r,delta)$-LRCs with unbounded length and larger minimum distance $2delta$. Furthermore, when $delta=3$, we give another class of optimal cyclic $(r,3)$-LRCs with unbounded length and minimum distance $6$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
