1. MDS Codes.
(a)
Show that \(C\) is MDS if and only if every set of \(k\) columns in its generator matrix is linearly independent.
Print preview
Worksheet Problem Set M3
Instructions: You may type up or handwrite your work, but it must be neat, professional, and organized and it must be saved as a PDF file and uploaded to the appropriate Gradescope assignment. Use a scanner or scanning app to convert handwritten work on paper to PDF. I encourage you to type your work using the provided template.
All tasks below must have a complete solution that represents a good-faith attempt at being right to receive engagement credits. If your submission is complete and turned in on time, you will receive full engagement credits for the assignment. All other submissions will receive zero engagement credit. Read the guidelines at Grading Specifications carefully.
To abide by the class’ academic honesty policy, your work should represent your own understanding in your own words. If you work with other students, you must clearly indicate who you worked with in your submission. The same is true for using tools like generative AI although I strongly discourage you from using such tools since you need to build your own understanding here to do well on exams.
2. An Interesting Code.
(a)
Determine whether or not \(C\) is perfect.
(b)
Determine whether or not \(C\) is MDS.
(c)
Give example generator matrices for such codes for \(q=2,3,5\text{.}\)
(d)
Show that there is exactly one codeword of \(C\) which contains \(\alpha \in F\) in positions \(i\) and \(j\) for each pair of distinct positions \(i,j\) and each non-zero element \(\alpha\in F\text{.}\)
(e)
Show that each non-zero codeword contains precisely one zero coordinate.
Note 52.
The previous problem shows that such a code can be used to construct a set of \(q-1\) mutually orthogonal Latin squares of order \(q\text{.}\)
3. The Plotkin Bound for Linear Codes.
This series of exercises will guide you through a proof of the Plotkin bound.
(a)
Let \(C\) be a linear \([n, k, d]\) code over \(F=GF(q)\) and let \(T\) be a \(q^k\times n\) array whose rows are the codewords of \(C\text{.}\) Show that each element of \(F\) appears in every nonzero column in \(T\) exactly \(q^{k-1}\) times.
(b)
Show that the total Hamming weight of the \(q^k-1\) nonzero codewords in a linear \([n,k,d]\) code over \(F=GF(q)\) is at most \(n(q-1)q^{k-1}\text{.}\)
(c) The Plotkin Bound.
Show that every linear \([n,k,d]\) code over \(F=GF(q)\) satisfies the inequality
\begin{equation*}
d\leq \frac{n(q-1)q^{k-1}}{q^k-1}\text{.}
\end{equation*}
4. The Griesmer Bound for Linear Codes [Optional].
This series of exercises will guide you through a proof of the Griesmer bound. Throughout, denote by \(N_q(k,d)\) the length of a shortest linear code of dimension \(k\) and minimum distance \(d\) over \(F=GF(q)\text{.}\)
(a)
Let \(C\) be a linear \([n,k,d]\) code over \(F=GF(q)\) with \(k>1\) and a generator matrix of the form
\begin{equation*}
G=\left(\begin{array}{c|c}
0\,0\,\ldots\,0 \amp 1\, 1\, \ldots\, 1 \\
\hline G_1 \amp G_2
\end{array}\right)
\end{equation*}
where the number of 1’s in the first row is equal to the minimum distance \(d\) of the code. Let \(C_1\) be the linear \([n_1=n-d,k_1,d_1]\) code over \(F\) spanned by the rows of the \((k-1)\times(n-d)\) matrix \(G_1\text{.}\)
(i)
Show that \(\rank(G_1)=k-1\) and so \(k_1=k-1\) by showing that otherwise you could find a nonzero codeword in \(C\) with the first \(n-d\) entries zero which is a linear combination of the last \(k-1\) rows of \(G\) and considering linear combinations of this codeword with the first row of \(G\text{.}\)
(ii)
Let \(\bc_1\) be a codeword of \(C_1\text{.}\) Show that there are exactly \(q\) words \(\bc_2 \in F^d\) such that the concatenation \((\bc_1\mid \bc_2)\) is a codeword of \(C\text{.}\)
(iii)
Let \(\bc_1\) be a nonzero codeword of \(C_1\text{.}\) Show that there is a word \(\bc_2 \in F^d\) of Hamming weight at most \(d-\lceil d/q\rceil\) such that \((\bc_1\mid \bc_2)\) is a codeword of \(C\text{.}\)
(iv)
Show that \(d_1\geq d-\lceil d/q\rceil\) by selecting in the previous part a codeword \(\bc_1\) of Hamming weight \(d_1\text{.}\)
(b)
Use the previous problem to show that
\begin{equation*}
N_q(k,d) \geq d + N_q(k-1,\lceil d/q \rceil)
\end{equation*}
for every \(k>1\text{.}\)
(c) The Griesmer Bound.
Show by induction on \(k\) that
\begin{equation*}
N_q(k,d) \geq \sum_{i=0}^{k-1}
\left\lceil \frac{d}{q^i}\right\rceil\text{.}
\end{equation*}
