2015/04/20 by Peter Nelson, Nelson, Peter, Stefan H. M. van Zwam +1
Computer Science · #Coding theory and cryptography #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.1504.05225
openalex publication_date 2015/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a class C of binary linear codes, we write θC\colon (0,1) → [0,(1)/(2)] for the maximum-likelihood decoding threshold function of C, the function whose value at R ∈ (0,1) is the largest bit-error rate p that codes in C can tolerate with a negligible probability of maximum-likelihood decoding error across a binary symmetric channel. We show that, if C is the class of cycle codes of graphs, then θC(R) ≤ ((1-√(R))2)/(2(1+R)) for each R, and show that equality holds only when R is asymptotically achieved by cycle codes of regular graphs.