Asymptotic Improvement of the Binary Gilbert-Varshamov Bound on the Code Rate

2009/03/02 by Dejan Spasov, Spasov, Dejan, Marjan Gušev +2
Computer Science · Economics, Econometrics and Finance · Mathematics · Physics and Astronomy · #Chaos control and synchronization #FOS: Computer and information sciences #Information Theory (cs.IT) #Mathematical Dynamics and Fractals #Stochastic processes and financial applications #cs.IT #math.IT

paper · pdf · doi:10.48550/arxiv.0903.0302

This submission has been withdrawn by author [arXiv admin]

openalex publication_date 2009/03/02 · arxiv created 2009/03/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We compute the code parameters for binary linear codes obtained by greedy constructing the parity check matrix. Then we show that these codes improve the Gilbert-Varshamov (GV) bound on the code size and rate. This result counter proves the conjecture on the asymptotical exactness of the binary GV bound.

Related

• Proof of tightness of Varshamov - Gilbert bound for binary codes
• When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?
• Non-linear Cyclic Codes that Attain the Gilbert-Varshamov Bound
• Improved Bounds on the Parity-Check Density and Achievable Rates of Binary Linear Block Codes with Applications to LDPC Codes
• On the difficulty to beat the first linear programming bound for binary codes