Asymptotic Improvement of the Gilbert–Varshamov Bound for Linear Codes

The Gilbert-Varshamov (GV) bound states that the maximum size A₂(n, d) of a binary code of length n and minimum distance d satisfies A₂(n, d)ges2ⁿ/V(n, d-1) where V(n, d)=Sigma_i=0 ^d(_i ⁿ) stands for the volume of a Hamming ball of radius d. Recently, Jiang and Vardy showed that for binary nonlinear codes this bound can be improved to A₂(n, d)gescn2ⁿ/(V(n, d-1)) for c a constant and d/nges0.499. In this paper, we show that certain asymptotic families of linear binary [n, n/2] random double circulant codes satisfy the same improved GV bound.