Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Combinatorial View of the Service Rates of Codes Problem, its Equivalence to Fractional Matching and its Connection with Batch Codes
72
0
0.0
(
0
)
Added by
Fatemeh Kazemi
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We propose a novel technique for constructing a graph representation of a code through which we establish a significant connection between the service rate problem and the well-known fractional matching problem. Using this connection, we show that the service capacity of a coded storage system equals the fractional matching number in the graph representation of the code, and thus is lower bounded and upper bounded by the matching number and the vertex cover number, respectively. This is of great interest because if the graph representation of a code is bipartite, then the derived upper and lower bounds are equal, and we obtain the capacity. Leveraging this result, we characterize the service capacity of the binary simplex code whose graph representation, as we show, is bipartite. Moreover, we show that the service rate problem can be viewed as a generalization of the multiset primitive batch codes problem.
rate research
Read More
Service rate is an important, recently introduced, performance metric associated with distributed coded storage systems. Among other interpretations, it measures the number of users that can be simultaneously served by the storage system. We introduce a geometric approach to address this problem. One of the most significant advantages of this approach over the existing approaches is that it allows one to derive bounds on the service rate of a code without explicitly knowing the list of all possible recovery sets. To illustrate the power of our geometric approach, we derive upper bounds on the service rates of the first order Reed-Muller codes and simplex codes. Then, we show how these upper bounds can be achieved. Furthermore, utilizing the proposed geometric technique, we show that given the service rate region of a code, a lower bound on the minimum distance of the code can be obtained.
Guo, Kopparty and Sudan have initiated the study of error-correcting codes derived by lifting of affine-invariant codes. Lifted Reed-Solomon (RS) codes are defined as the evaluation of polynomials in a vector space over a field by requiring their restriction to every line in the space to be a codeword of the RS code. In this paper, we investigate lifted RS codes and discuss their application to batch codes, a notion introduced in the context of private information retrieval and load-balancing in distributed storage systems. First, we improve the estimate of the code rate of lifted RS codes for lifting parameter $mge 3$ and large field size. Second, a new explicit construction of batch codes utilizing lifted RS codes is proposed. For some parameter regimes, our codes have a better trade-off between parameters than previously known batch codes.
In this paper we present a new class of convolutional codes that admits an efficient al- gebraic decoding algorithm. We study some of its properties and show that it can decode interesting sequences of errors patterns. The second part of the paper is devoted to in- vestigate its use in a variant of the McEliece cryptosystem. In contrast to the classical McEliece cryptosystems, where block codes are used, we propose the use of a convolu- tional encoder to be part of the public key. In this setting the message is a sequence of messages instead of a single block message and the errors are added randomly throughout the sequence. We conclude the paper providing some comments on the security. Although there is no obvious security threats to this new scheme, we point out several possible adaptations of existing attacks and discuss the difficulties of such attacks to succeed in breaking this cryptosystem.
A new approach for the approximation of the channel log-likelihood ratio (LLR) for wireless channels based on Taylor series is proposed. The approximation is applied to the uncorrelated flat Rayleigh fading channel with unknown channel state information at the receiver. It is shown that the proposed approximation greatly simplifies the calculation of channel LLRs, and yet provides results almost identical to those based on the exact calculation of channel LLRs. The results are obtained in the context of bit-interleaved coded modulation (BICM) schemes with low-density parity-check (LDPC) codes, and include threshold calculations and error rate performance of finite-length codes. Compared to the existing approximations, the proposed method is either significantly less complex, or considerably more accurate.
Fractional repetition (FR) codes are a class of repair efficient erasure codes that can recover a failed storage node with both optimal repair bandwidth and complexity. In this paper, we study the minimum distance of FR codes, which is the smallest number of nodes whose failure leads to the unrecoverable loss of the stored file. We consider upper bounds on the minimum distance and present several families of explicit FR codes attaining these bounds. The optimal constructions are derived from regular graphs and combinatorial designs, respectively.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
