2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | A.4.3 | ||
| Paper Title | Distribution of the Minimum Distance of Random Linear Codes | ||
| Authors | Jing Hao, Han Huang, Galyna Livshyts, Konstantin Tikhomirov, Georgia Institute of Technology, United States | ||
| Session | A.4: Combinatorial Coding Theory I | ||
| Presentation | Lecture | ||
| Track | Algebraic and Combinatorial Coding Theory | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract |
In this paper, we study the distribution of the minimal 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 minimal 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 $\frac{1}{q}$ and $n$. The latter, in turn, converges to a Gumbel distribution at integer points when $\frac{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 minimal code weight. As a corollary of the main result, we obtain an asymptotic improvement of the Gilbert--Varshamov bound for $2 | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
