Technical Program

Paper Detail

Paper IDA.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

Visit Website!