Distribution of the Minimum Distance of Random Linear Codes

摘要

In this paper, we study the distribution of the minimum distance (in the Hamming metric) of a random linear code of dimension k in $mathbb{F}_q^n$. We provide quantitative estimates showing that the distribution function of the minimum distance is close (superpolynomially in n) to the cumulative distribution function of the minimum of (q^k -1)/(q-1) independent binomial random variables with parameters $rac{1}{q}$ and n. The latter, in turn, converges to a Gumbel distribution at integer points when $rac{k}{n}$ converges to a fixed number in (0, 1). In a sense, our result shows that apart from identification of the weights of parallel codewords, the probabilistic dependencies introduced by the linear structure of the random code, produce a negligible effect on the minimum code weight. As a corollary of the main result, we obtain an asymptotic improvement of the Gilbert-Varshamov bound for 2 < q < 49.