1.
How many vectors are in a subspace of dimension \(k\) over the finite field \(\F_q\text{?}\) Justify your answer.
Print preview
Worksheet Linear Codes
Throughout this activity, we’ll deepen our understanding of linear codes with hands-on examples. We’ll explore equivalent codes, systematic form, converting between generator and parity-check matrices, and determining the minimum distance of a code from a parity-check matrix.
2.
How many ordered bases are there for a subspace of dimension \(k\) over the finite field \(\F_q\text{?}\) Justify your answer.
3.
How many \(k\)-dimensional subspaces are there of \(\F_q^n\text{?}\) Justify your answer. This number is called the “Gaussian binomial coefficient” or “\(q\)-binomial coefficient” and is often denoted
\begin{equation*}
\begin{bmatrix} n \\ k \end{bmatrix}_q
\end{equation*}
4.
Proposition 2.3.7 in the GRS text states the following.
For every \([n,k,d]_q\) code \(C\) with parity-check matrix \(H\text{,}\) \(d\) equals the size of the smallest subset of columns of \(H\) that are linearly dependent.
In this problem, we’ll explore an example to understand this proposition better and generate questions about it.
(a)
Let \(H\) be the following parity-check matrix for a code over \(\F_3\text{.}\)
\begin{align*}
\begin{bmatrix}
1 \amp 0 \amp 1 \amp 1 \\
0 \amp 1 \amp 1 \amp 2 \\
\end{bmatrix}
\end{align*}
What does it mean for a subset of 1 column of \(H\) to be linearly dependent? Are there any such subsets?
(b)
What does it mean for a subset of 2 columns of \(H\) to be linearly dependent? Are there any such subsets?
(c)
What does it mean for a subset of 3 columns of \(H\) to be linearly dependent? Are there any such subsets?
(d)
Use a linear combination of the columns you found in the previous step to produce a non-zero codeword in the code with parity-check matrix \(H\text{.}\) What is the weight of this codeword?
5.
Repeat the previous problem for the following parity-check matrix over \(\F_3\text{.}\)
\begin{align*}
\begin{bmatrix}
1 \amp 0 \amp 2 \amp 1 \\
0 \amp 1 \amp 1 \amp 2 \\
\end{bmatrix}
\end{align*}
6.
What questions do you have about Proposition 2.3.7 based on your work in the previous problems or your reading of the text?
7.
Discuss in your groups whether the two matrices below generate the same code over \(\F_3\text{.}\) If not, why not? Are they related in any way? What coding theoretic properties do they share or not share?
\begin{align*}
G_1=\begin{bmatrix}
1 \amp 0 \amp 2 \amp 1\\
0 \amp 1 \amp 1 \amp 1 \\
\end{bmatrix} \amp \amp
G_2 = \begin{bmatrix}
1 \amp 2 \amp 0 \amp 1\\
0 \amp 2 \amp 2 \amp 2 \\
\end{bmatrix}
\end{align*}
8.
We can encode messages of length 2 using the generator matrices in the previous problem by matrix multiplication:
\begin{gather*}
\mathbf{x}=(m_1 m_2)G_i
\end{gather*}
