Gilbert–Varshamov bound

In coding theory, the Gilbert–Varshamov bound (due to Edgar Gilbert and independently Rom Varshamov) is a limit on the parameters of a (not necessarily linear) code. It is occasionally known as the Gilbert–Shannon–Varshamov bound (or the GSV bound), but the name "Gilbert–Varshamov bound" is by far the most popular. Varshamov proved this bound by using the probabilistic method for linear codes. For more about that proof, see: GV-linear-code.

Let

denote the maximum possible size of a q-ary code ${\displaystyle C}$ with length n and minimum Hamming weight d (a q-ary code is a code over the field ${\displaystyle \mathbb {F} _{q}}$ of q elements).

Then:

Let ${\displaystyle C}$ be a code of length ${\displaystyle n}$ and minimum Hamming distance ${\displaystyle d}$ having maximal size:

...
Wikipedia