اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRepairable Fountain Codes
119
0
0.0
(
0
)
نشر من قبل
Megasthenis Asteris
تاريخ النشر
2014
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 mul
tiple 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 u
nderstand 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$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
