Gilbert-Shannon-Varshamov Bound

The Size of Largest Code satisfies:

Proof

Let be a code of length and minimum distance
of largest possible size.
Then there is no string s.t. for all .
Otherwise we would replace with
Then

Thus