2017/06/15 by Ling-Hua Chang, Chang, Ling-Hua, Po‐Ning Chen +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1706.04709
openalex publication_date 2017/06/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We establish a general formula for the maximum size of finite length block codes with minimum pairwise distance no less than d. The achievability argument involves an iterative construction of a set of radius-d balls, each centered at a codeword. We demonstrate that the number of such balls that cover the entire code alphabet cannot exceed this maximum size. Our approach can be applied to codes i) with elements over arbitrary code alphabets, and ii) under a broad class of distance measures, thereby ensuring the generality of our formula. Our formula indicates that the maximum code size can be fully characterized by the cumulative distribution function of the distance measure evaluated at two independent and identically distributed random codewords. When the two random codewords assume a uniform distribution over the entire code alphabet, our formula recovers and obtains a natural generalization of the Gilbert-Varshamov (GV) lower bound. We also establish a general formula for the zero-error capacity of any sequence of channels. Finally, we extend our study to the asymptotic setting, where we establish first- and second-order bounds on the asymptotic code rate subject to a normalized minimum distance constraint.