2023/10/07 by Haihua Deng, Hexiang Huang, Deng, Haihua +5
Computer Science · #Caching and Content Delivery #Combinatorics (math.CO) #Cooperative Communication and Network Coding #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2310.04820
openalex publication_date 2023/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let Γ be a simple connected graph on n vertices, and let C be a code of length n whose coordinates are indexed by the vertices of Γ. We say that C is a storage code on Γ if for any codeword c ∈ C, one can recover the information on each coordinate of c by accessing its neighbors in Γ. The main problem here is to construct high-rate storage codes on triangle-free graphs. In this paper, we solve an open problem posed by Barg and Zémor in 2022, showing that the BCH family of storage codes is of unit rate. Furthermore, we generalize the construction of the BCH family and obtain more storage codes of unit rate on triangle-free graphs.