GV-linear-code

In coding theory, the bound of parameters such as rate R, relative distance, block length, etc. is usually concerned. Here Gilbert–Varshamov bound theorem claims the lower bound of the rate of the general code. Gilbert–Varshamov bound is the best in terms of relative distance for codes over alphabets of size less than 49.

Here ${\displaystyle H_{q}}$ is the q-ary entropy function defined as follows:

The above result was proved by Edgar Gilbert for general code using the greedy method as here. For linear code, Rom Varshamov proved using the probabilistic method for the random linear code. This proof will be shown in the following part.

High-level proof:

To show the existence of the linear code that satisfies those constraints, the probabilistic method is used to construct the random linear code. Specifically the linear code is chosen randomly by choosing the random generator matrix ${\displaystyle G}$ in which the element is chosen uniformly over the field ${\displaystyle \mathbb {F} _{q}^{n}}$. Also the Hamming distance of the linear code is equal to the minimum weight of the codeword. So to prove that the linear code generated by ${\displaystyle G}$ has Hamming distance ${\displaystyle d}$, we will show that for any ${\displaystyle m\in \mathbb {F} _{q}^{k}\backslash \left\{0\right\},wt(mG)\geq d}$ . To prove that, we prove the opposite one; that is, the probability that the linear code generated by ${\displaystyle G}$ has the Hamming distance less than ${\displaystyle d}$ is exponentially small in ${\displaystyle n}$. Then by probabilistic method, there exists the linear code satisfying the theorem.

...
Wikipedia