**1. Asymptotically good codes and Gilbert-Varshamov bound **

We begin by answering the question raised at the end of the previous notes on the existence of asymptotically good codes.

Suppose we are interested in -ary codes (not necessarily linear) of block length and minimum distance that have many codewords. What is the largest size such a code can have? This is a fundamental quantity for which we define a notation below.

Definition 1Let be the largest size of a -ary code of block length and minimum distance . The binary case is of special importance, and in this case is denoted simply as .

There is a natural greedy approach to construct a code of distance at least : start with any codeword, and keep on adding codewords which have distance at least from all previously chosen codewords, until we can proceed no longer. Suppose this procedure halts after picking a code . Then Hamming balls in of radius centered at the codewords of must cover the whole space. (Otherwise, we can pick one more codeword which has distance at least from every element of , and the process would not have terminated.)

Definition 2For integers , denote by the volume of (i.e., the number of strings in) a Hamming ball of radius in . Note that this number does not depend on where the ball is centered and equals

Therefore, the greedy procedure terminates with a code satisfying

We therefore have the following lower bound.

Lemma 3 (Gilbert-Varshamov bound)The maximal size of a -ary code of block length and distance satisfies

There also exist linear codes of size given by the Gilbert-Varshamov bound:

Exercise 1By a suitable adaptation of the greedy procedure, prove that there also exists a linear code over of dimension at least .

The Gilbert-Varshamov bound was actually proved in two independent works (Gilbert, 1952) and (Varshamov, 1957). The latter actually proved the existence of *linear codes* and in fact got a slightly sharper bound stated below. (You can verify that the Hamming code in fact attains this bound for .)

Exercise 2For every prime power , and integers , prove that there exists an linear code with

In fact, one can prove that a random linear code almost matches the Gilbert-Varshamov bound with high probability, so such linear codes exist in abundance. But before stating this, we will switch to the asymptotic viewpoint, expressing the lower bound in terms of the rate vs. relative distance trade-off.

** 1.1. Entropy function and volume of Hamming balls **

We now give an asymptotic estimate of the volume when for held fixed and growing. This volume turns out to be very well approximated by the exponential where is the “entropy function” defined below.

Definition 4 (Entropy function)For a positive integer , define the -ary entropy function as follows:

Of special interest is the binary entropy function

where we use the notational convention that .

If is the -valued random variable such that and , then the Shannon entropy of , , equals . In other words, is the uncertainty in the outcome of a -biased coin toss (which lands heads with probability and tails with probability ). The function is continuous and increasing in the interval with and . The binary entropy function is symmetric around the line: .

We can define the inverse of the entropy function as follows. For , the inverse is equal to the unique satisfying .

Lemma 5For an integer and ,

*Proof:* We have

Since , , and therefore the above quantity is at most

The latter sum is at most

by the binomial theorem.

The above upper bound is tight up to lower order terms. The quantity is at least as large as . By Stirling’s formula , it follows that

and therefore

For a self-contained derivation of the entropy estimate for the binomial coefficients, we can work with a crude estimate of given by the integral estimate

which gives

This immediately gives the lower bound

We summarize the above discussion in the following important estimate.

Lemma 6For positive integers and real , ,

** 1.2. Asymptotic form of GV bound **

Combining the greedy construction of Lemma 3 with the estimate of the Hamming volume from Lemma 6 gives the following asymptotic version of the Gilbert-Varshamov bound.

Theorem 7 (Asymptotic Gilbert-Varshamov bound)For every and , there exists an infinite family of -ary codes with rate

(In fact, such codes exist for every block length.)

Since for , the above implies that for every there exists an asymptotically good family of -ary codes of rate at least and relative distance at least . By Exercises 1 and 2 this also holds for linear codes over . We now give an alternate proof based on the probabilistic method.

** 1.3. Random linear codes attain the GV bound **

Theorem 8For every prime power , , , and sufficiently large positive integer , the following holds for . If is chosen uniformly at random, then the linear code with as generator matrix has rate at least and relative distance at least with probability at least .

*Proof:* The claim about rate follows whenever has full column rank. The probability that the ‘th column is in the span of the first columns is at most . By a union bound, has rank with probability at least .

For each nonzero , the vector is a uniformly random element of . (Indeed, say that , then conditioned on the choice of the first columns of , is uniformly distributed since the ‘th column is chosen uniformly at random from .) Therefore the probability that is at most

Now a union bound over all nonzero implies that the probability that the code generated by the columns of has distance at most is bounded from above by

We conclude that with probability at least , the code generated by has relative distance at least and rate at least .

Exercise 3Establish a similar result by picking a random parity check matrix for the code.

** 1.4. Some comments on attaining/beating the GV bound **

We have seen that there exist binary linear codes that meet the Gilbert-Varshamov bound, and thus have rate approaching for a target relative distance of , . The proof of this was non-constructive, based on an exponential time algorithm to construct such a code (by a greedy algorithm), or by picking a generator matrix (or a parity check matrix) at random. The latter leads to a polynomial time randomized Monte Carlo construction. If there were a way to ascertain if a randomly chosen linear code has the claimed relative distance, then this would be a practical method to construct codes of good distance; we will have a Las Vegas construction that picks a random linear code and then checks that it has good minimum distance. Unfortunately, given a linear code, computing (or even approximating) the value of its minimum distance is NP-hard.

A natural challenge therefore is to give an explicit (i.e., deterministic polynomial time) construction of a code that meets the Gilbert-Varshamov bound (i.e., has rate and relative distance close to ). Giving such a construction of binary codes (even non-linear ones) remains an outstanding open question.

For prime powers for , explicit constructions of -ary linear codes that not only attain but surpass the GV bound are known! These are based on algebraic geometry and a beautiful construction of algebraic curves with many rational points and small genus. This is also one of the rare examples in combinatorics where we know an explicit construction that beats the parameters obtained by the probabilistic method. (Another notable example is the Lubotzky-Phillips-Sarnak construction of Ramanujan graphs whose girth surpasses the probabilistic bound.)

What about codes over smaller alphabets, and in particular binary codes? The Hamming upper bound on size of codes (Lemma 13 in Notes 1) leads to the asymptotic upper bound on the rate. This is off by a factor of in the coefficient of compared to the achievable rate. We will later see improvements to the Hamming bound, but the best bound will still be far from the Gilbert-Varshamov bound. Determining the largest rate possible for binary codes of relative distance is another fundamental open problem in the subject. The popular conjecture seems to be that the Gilbert-Varshamov bound on rate is asymptotically tight (i.e., a binary code of relative distance must have rate ), but arguably there is no strong evidence that this must be the case.

While we do not know explicit constructions of binary codes approaching the GV bound, it is still interesting to construct codes which achieve good trade-offs. This leads to the following questions, which are the central questions in coding theory for any noise model (once some existential bounds are established on the trade-offs, the questions below pertaining to the worst-case or adversarial noise model where we impose no restriction on the channel other than a limit on the total number of errors caused):

- Can one explicitly construct an asymptotically good family of binary codes with a “good” rate vs. relative distance trade-off?
- Can one construct such codes together with an efficient algorithm to correct a fraction of errors approaching half-the-relative distance (or even beyond)?

We will answer both the questions in the affirmative in this course.

## Leave a Reply