2004/09/07 by Alexander Barg, Gilles Zemor, Barg, Alexander +2
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Coding theory and cryptography #DNA and Biological Computing #Discrete Mathematics (cs.DM) #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.DM #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.cs/0409010
19 pages, 7 figures
arxiv created 2004/09/07 · openalex publication_date 2004/09/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the minimum distance of codes defined on bipartite graphs. Weight spectrum and the minimum distance of a random ensemble of such codes are computed. It is shown that if the vertex codes have minimum distance ≥ 3, the overall code is asymptotically good, and sometimes meets the Gilbert-Varshamov bound. Constructive families of expander codes are presented whose minimum distance asymptotically exceeds the product bound for all code rates between 0 and 1.