Note 40.
Recall from the Daily Prep that the Hamming bound says that for an \((n,M,d)_q\) code we have
\begin{equation*}
M\cdot V_q(n, \lfloor (d-1)/2\rfloor) \leq q^n\text{.}
\end{equation*}
Print preview
Worksheet Bounds on Codes
Today we will explore some key bounds on the parameters of error-correcting codes to help us quantify the trade-offs between code length, dimension, and minimum distance.
1.
Give a statement of the Hamming bound for linear binary codes in terms of their parameters \([n,k,d]\text{.}\)
Definition 41. Perfect Code.
A code is called perfect if it attains the Hamming bound.
2.
Explain why the Hamming \([7,4,3]\) code is a perfect code.
3.
Explain why the general \(q\)-ary Hamming code is a perfect code. Remember that this code has parameters \([n, n - r, 3]_q\) where \(n = (q^r - 1)/(q - 1)\text{.}\)
4.
Explain why all perfect codes must have odd minimum distance.
The next exercises walk you through three ways of understanding the Singleton bound for codes. Throughout them, let \(C\) be an \((n,M,d)_q\) code (not necessarily linear).
5.
Construct a new code \(C'\) by deleting the last \(d-1\) symbols from each codeword in \(C\text{.}\)
Does this code have the same number of codewords as \(C\text{?}\) Why or why not? What is the maximum possible number of codewords in \(C'\text{?}\) Use this to give a bound on \(M\) in terms of \(n,q\text{,}\) and \(d\text{.}\)
Hint.
6.
Consider the integer \(\ell=\lceil \log_q M \rceil-1\text{.}\) Explain why there must be two codewords in \(C\) that agree on the first \(\ell\) symbols. Use this to give a bound on \(d\) in terms of \(n,q\text{,}\) and \(M\text{.}\)
7.
For linear codes, things are nicer. Now suppose \(C\) is a linear \([n,k,d]_q\) code with parity-check matrix \(H\text{.}\) What can you say about any set of \(n-k+1\) columns of \(H\text{?}\) Use this with Proposition 2.3.7 to give a bound on \(d\) in terms of \(n,q\) and \(k\text{.}\)
8.
Can you rearrange all of these bounds to get the same bound on the parameters of a code (excluding the bound from 7 if \(C\) is not linear)?
9.
[Challenge/Optional:] Show that the Singleton bound is achieved by the linear code over \(\F_7\) with parity-check matrix
\begin{equation*}
H=\begin{bmatrix}
3^0 \amp 3^1 \amp 3^2 \amp 3^3 \amp 3^4 \amp 3^5 \\
3^0 \amp 3^2 \amp 3^4 \amp 3^6 \amp 3^8 \amp 3^{10} \\
3^0 \amp 3^3 \amp 3^6 \amp 3^9 \amp 3^{12} \amp 3^{15} \\
3^0 \amp 3^4 \amp 3^8 \amp 3^{12} \amp 3^{16} \amp 3^{20}
\end{bmatrix}=\begin{bmatrix}
1 \amp 3 \amp 2 \amp 6 \amp 4 \amp 5 \\
1 \amp 2 \amp 4 \amp 1 \amp 2 \amp 4 \\
1 \amp 6 \amp 1 \amp 6 \amp 1 \amp 6 \\
1 \amp 4 \amp 2 \amp 1 \amp 4 \amp 2
\end{bmatrix}\text{.}
\end{equation*}
Hint.
Think about the form of the square matrix formed by selecting any 4 columns of \(H\) and calculating its determinant. I do not recommend doing this manually for all 15 possible choices.
\begin{equation*}
\begin{pmatrix}
3^i \amp 3^j \amp 3^k \amp 3^\ell \\
3^{2i} \amp 3^{2j} \amp 3^{2k} \amp 3^{2\ell} \\
3^{3i} \amp 3^{3j} \amp 3^{3k} \amp 3^{3\ell} \\
3^{4i} \amp 3^{4j} \amp 3^{4k} \amp 3^{4\ell} \\
\end{pmatrix} \qquad 0\leq i \lt j\lt k \lt \ell \leq 5
\end{equation*}
