1.
True/False: The minimum distance of a binary linear code is equal to the minimum weight of its non-zero codewords.
Print preview
Worksheet Weekly Practice 2
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 credit 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.
True/False, Multiple Choice, & Fill-In.
For these problems a justification is not required for credit, but it may be useful for your own understanding to include one. True/False problems should be marked True if the statement is always true, and False otherwise. Multiple choice problems may have more than one correct answer if that is indicated in the problem statement; be sure to select all that apply. Fill-in problems require a short answer such as a number, word, or phrase.
2.
3.
Fill-In: A subspace \(V\) of \(\F_q^n\) satisfies the three properties that for any \(\mathbf{u},\mathbf{v}\in V \) and \(a\in \F_q\) we have
-
\(\displaystyle \fillinmath{V\neq \emptyset}\)
-
\(\displaystyle \fillinmath{\mathbf{u}+\mathbf{v}\in V}\)
-
\(\displaystyle \fillinmath{a\mathbf{v}\in V}\)
Short Response.
Your responses to these questions should be complete solutions with justifications, as per the Grading Specifications.
4.
Compute the minimum distance of the binary linear code \(C\) with codewords
\begin{align*}
\{ \amp (0, 0, 0, 0, 0, 0, 0, 0),(1, 0, 0, 1, 1, 0, 1, 1),(0, 1, 0, 1, 0, 1, 1, 0),(0, 0, 1, 0, 1, 1, 1, 1) \\
\amp (1, 1, 0, 0, 1, 1, 0, 1),(1, 0, 1, 1, 0, 1, 0, 0),(0, 1, 1, 1, 1, 0, 0, 1),(1, 1, 1, 0, 0, 0, 1, 0)) \}
\end{align*}
5.
Give an example computation that proves that \(\Z_{12}\) is not a field. Explain why your computation shows this.
Solution.
There are a variety of examples that can be chosen. All fundamentally show that some nonzero element does not have a multiplicative inverse (one of the numbers in \(\{0,1,\ldots,11\}\) that is not coprime to 12). For example, since \(4\cdot 3 = 12 \equiv 0 \pmod 12,\) there is no way to multiply 4 by any other element of \(\Z_{12}\) to get 1. Thus, 4 does not have a multiplicative inverse, so \(\Z_{12}\) is not a field.
6.
Find the additive and multiplicative inverses of each nonzero element in \(\F_{11}\text{.}\)
Solution.
The additive inverses of each \(a\in \F_{11}\setminus\{0\}\) are given by \(11 - a.\) The multiplicative inverse of each nonzero element can be found by testing each element until one is found that gives product 1 modulo 11. For compactness, only half the inverses are listed below since the rest can be found by symmetry.
| \(a\) | \(-a\) |
|---|---|
| \(1\) | \(10\) |
| \(2\) | \(9\) |
| \(3\) | \(8\) |
| \(4\) | \(7\) |
| \(5\) | \(6\) |
| \(a\) | \(a^{-1}\) |
|---|---|
| \(1\) | \(1\) |
| \(2\) | \(6\) |
| \(3\) | \(4\) |
| \(5\) | \(9\) |
| \(7\) | \(8\) |
| \(10\) | \(10\) |
7.
Compute a generator matrix and a parity check matrix for the subspace of \(\F_7^5\) generated by the set
\begin{equation*}
\{ (1,6,5,5,4), (2,3,5,4,4), (3,2,3,2,1), (1,1,2,2,0), (3,6,5,5,1) \}
\end{equation*}
Solution.
To find a generator matrix for this subspace, we can row reduce the matrix whose rows are the given vectors over \(\F_7.\) Doing so gives the following row echelon form:
\begin{align*}
\begin{bmatrix}
1 \amp 0 \amp 0 \amp 0 \amp 2 \\
0 \amp 1 \amp 0 \amp 5 \amp 3 \\
0 \amp 0 \amp 1 \amp 2 \amp 1 \\
0 \amp 0 \amp 0 \amp 0 \amp 0 \\
0 \amp 0 \amp 0 \amp 0 \amp 0 \\
\end{bmatrix}
\end{align*}
So the matrix
\begin{align*}
G = \begin{bmatrix}
1 \amp 0 \amp 0 \amp 0 \amp 2 \\
0 \amp 1 \amp 0 \amp 5 \amp 3 \\
0 \amp 0 \amp 1 \amp 2 \amp 1 \\
\end{bmatrix}
\end{align*}
is a generator matrix for this subspace.
We can find the parity check matrix as we did in class by using these relations and choosing free variables \(x_4,x_5\text{.}\) This gives the parity check matrix
\begin{align*}
H = \begin{bmatrix}
0 \amp 2 \amp 5 \amp 1 \amp 0 \\
5 \amp 4 \amp 6 \amp 0 \amp 1
\end{bmatrix}
\end{align*}
