Skip to main content

Algebraic Coding Theory MATH 4012 Spring 2026

Dr. Hunter Lehmann

Print preview

Paper size
Additional printing options
Print headers
Print footers

Worksheet The Gilbert-Varshamov Bound

Today we will dive in to the existence result of the Gilbert-Varshamov bound for linear codes to build intuition for why this construction works.
🔗

1.

The goal of the proof of this result is to construct the code by finding a parity-check matrix with the desired properties. To produce a linear \([n,k]_q\) code with minimum distance at least \(d\text{,}\) what size matrix \(H\) do we need to find, and what property do its columns need to have?
🔗
Solution.
\(H\) should be \((n-k)\times n\) and every set of \(d-1\) columns of \(H\) should be linearly independent.
🔗
🔗
🔗

2.

We want this matrix \(H\) to have full rank. What \(n-k\) columns should we begin by choosing that will satisfy the conditions from the last question?
🔗
Solution.
We can pick the standard basis vectors in \(F^{n-k}\) as the first \(n-k\) columns. These will certainly be linearly independent, so \(H\) will be guaranteed to have full rank and no matter what \(d\) is it will be true that \(d-1\) of these will be linearly independent.
🔗
🔗
🔗

3.

For the next part, we want to give a general description of how to choose the remaining \(k\) columns based on those already chosen. We want to maintain the property that any \(d-1\) columns are linearly independent. So let’s think about which vectors would cause this property to fail.
🔗
If our matrix has \(\ell-1\) columns chosen, \(\bh_1,\ldots,\bh_{\ell-1}\text{,}\) a new prospective vector \(\bh_{\ell}\) could cause this property to fail if it is in the span of a set of \(\fillinmath{d-2}\) columns chosen already.
🔗
Solution.
The property would fail if the new vector was in the span of any \(d-2\) of the already chosen columns.
🔗
🔗
🔗

4.

Let’s work out how many vectors satisfy this condition by thinking about linear combinations where all coefficients are non-zero. Let \(W_{\ell-1}\) be the set of all vectors in \(F^{n-k}\) spanned by any subset of the size you found above from \(\bh_1,\ldots,\bh_{\ell-1}\text{,}\) coefficients zero or not.
🔗
First, think about the vectors in \(W_{\ell-1}\) with exactly one non-zero coefficient. How many ways are there to create such a vector?
🔗
Solution.
We need to pick one vector from our set of columns, then choose one non-zero coefficient for it. So there are
\begin{equation*} \binom{\ell-1}{1}(q-1) \end{equation*}
ways.
🔗
🔗
🔗

5.

How many vectors in \(W_{\ell-1}\) with exactly two non-zero coefficients? With three? What is the total size of \(W_{\ell-1}\text{?}\)
🔗
Solution.
Following the same logic, we can produce a vector with exactly two non-zero coefficients by picking two columns, then picking non-zero coefficients for each of them to get
\begin{equation*} \binom{\ell-1}{2}(q-1)^2 \end{equation*}
vectors. Then for three we get
\begin{equation*} \binom{\ell-1}{3}(q-1)^3\text{.} \end{equation*}
By continuing this chain of thought the total size of \(W_{\ell-1}\) is
\begin{equation*} \sum_{i=0}^{d-2} \binom{\ell-1}{i}(q-1)^i\text{.} \end{equation*}
🔗
🔗
🔗

6.

The expression you found in the previous part should be the volume of a Hamming sphere of some size. How is that volume related to the one in the condition of the theorem? What does the condition given in the theorem tell you about the possibility of finding a new vector \(\bh_{\ell}\) to add?
🔗
Solution.
We see that \(|W|=V_q(\ell-1,d-2)\text{.}\) This sphere is certainly smaller than \(V_q(n-1,d-2)\) in the statement of the theorem since we have \(n-k\lt \ell \leq n\text{.}\) Since that larger sphere is required to be smaller than \(|F^{n-k}|=q^{n-k}\) it follows that there is a new vector \(\bh_{\ell}\) in \(F^{n-k}\) to pick for each of the remaining \(k\) columns of \(H\text{.}\)
🔗
🔗
🔗

7.

Why do you think the theorem says the resulting code has distance at least \(d\) rather than exactly \(d\text{?}\)
🔗
Solution.
We have picked our columns so that any \(d-1\) of them are linearly independent. We did not check at all what happens with any \(d\) or more of them, so it might happen that subsets of those sizes also happen to be linearly independent and so the code may have distance larger than \(d\text{.}\)
🔗
🔗
🔗

8.

Another way of thinking about the size of the set \(W_{\ell}\) is by using the reasoning of Proposition 2.3.7. If a vector \(\by\) is in \(W\) then it can be written as
\begin{equation*} \begin{bmatrix} \bh_1 \amp \bh_2 \amp \ldots \amp \bh_{\ell-1} \end{bmatrix}\bx\text{,} \end{equation*}
where \(\bx\) has weight at most \(\fillinmath{d-2}\text{.}\) Having weight at most \(t\) for any \(t\) means lying inside the sphere of radius \(t\) centered at and the size of this sphere for the weight here is \(\fillinmath{V_q(\ell-1,d-2)}\)
🔗
Solution.
Here the weight is at most \(d-2\text{,}\) the sphere is centered at the zero vector, and the size of this sphere is again \(V_q(\ell-1,d-2)\text{.}\)
🔗
🔗
🔗
🔗
PrevTopNext