On Extremal Rates of Storage over Graphs

2022/10/12 by Zhou Li, Li, Zhou, Sun Hua +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Coding theory and cryptography #Cooperative Communication and Network Coding #DNA and Biological Computing #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · pdf · doi:10.48550/arxiv.2210.06363

openalex publication_date 2022/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A storage code over a graph maps K independent source symbols, each of L_w bits, to N coded symbols, each of L_v bits, such that each coded symbol is stored in a node of the graph and each edge of the graph is associated with one source symbol. From a pair of nodes connected by an edge, the source symbol that is associated with the edge can be decoded. The ratio L_w/L_v is called the symbol rate of a storage code and the highest symbol rate is called the capacity. We show that the three highest capacity values of storage codes over graphs are 2, 3/2, 4/3. We characterize all graphs over which the storage code capacity is 2 and 3/2, and for capacity value of 4/3, necessary condition and sufficient condition (that do not match) on the graphs are given.

Cited by

• On the Capacity of Distributed Quantum Storage

Related

• On Extremal Rates of Secure Storage over Graphs
• Construction of storage codes of rates approaching one on triangle-free graphs
• Storage codes on coset graphs with asymptotically unit rate
• Storage Capacity as an Information-Theoretic Vertex Cover and the Index Coding Rate
• The BCH Family of Storage Codes on Triangle-Free Graphs is of Unit Rate