Algebraic and Combinatorial Coding Theory
A.4.3
Lecture
Combinatorial Coding Theory I

# Distribution of the Minimum Distance of Random Linear Codes

Jing Hao, Han Huang, Galyna Livshyts, Konstantin Tikhomirov

## Date & Time

01:00 am – 01:00 am

## 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<q<49$.

## Presenters

#### Jing Hao

Georgia Institute of Technology

#### Han Huang

Georgia Institute of Technology

#### Galyna Livshyts

Georgia Institute of Technology

#### Konstantin Tikhomirov

Georgia Institute of Technology

Paper

## Session Chair

#### Navin Kashyap

Indian Institute of Science