1.
Fill-In: Fill in the missing part of the statement of Proposition 2.3.7.
For every \([n,k,d]_q\) code \(C\) with parity check matrix \(H\text{,}\) the minimum distance \(d\) of \(C\) is equal to .
Print preview
Worksheet Weekly Practice 3
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.
Fill-In: The number of elements in a vector space of dimension \(k\) over the finite field \(GF(q)\) is \(\fillinmath{q^k} \)
3.
True/False: The binary Hamming code \(C_{H,r}\) has parameters \([2^r - 1, 2^r - r - 1, 3]_2\text{.}\)
4.
Multiple Choice: Which statement below about decoding a linear 1-error-correcting code with generator matrix \(G\) and parity-check matrix \(H\) is true?
-
To decode a received word \(\mathbf{y}\text{,}\) we must check the distance from \(\mathbf{y}\) to every codeword.
-
If \(\mathbf{y}\) is the received word, then no errors have occurred if \(H\transpose{\mathbf{y}} \neq \mathbf{0}\text{.}\)
-
If \(\mathbf{y}\) is the received word, then no errors have occurred if \(\mathbf{y}G =\mathbf{0}\text{.}\)
-
If \(\mathbf{y}\) is the received word, then \(H\transpose{\mathbf{y}}\) is a multiple of a column of \(H\) if one error has occurred.
Solution.
(d) is correct. (a) is a valid decoding method, but is not required for these codes since we have more efficient methods. (b) and (c) are both incorrect statements of the error-detection condition. When one error has occurred the error vector has weight 1 so computing \(H\transpose{\mathbf{y}}\) will produce a multiple of a column of \(H\text{.}\)
Short Response.
Your responses to these questions should be complete solutions with justifications, as per the Grading Specifications.
5.
Determine the parameters \([n,k,d]_q\) of the code with parity-check matrix over \(GF(3)\)
\begin{equation*}
H= \begin{bmatrix}
1 \amp 0 \amp 1 \amp 1 \amp 2 \amp 0 \\
0 \amp 1 \amp 2 \amp 2 \amp 1 \amp 0 \\
0 \amp 0 \amp 1 \amp 0 \amp 2 \amp 2
\end{bmatrix}\text{.}
\end{equation*}
Solution.
This is an \([6,3,2]_3\) code. The alphabet is \(GF(3)\) so \(q=3\text{.}\) The block length is \(n=6\) since there are 6 columns in \(H\text{.}\) The dimension is \(k=n-\rk(H)=6-3=3\) since the rank of \(H\) is 3 (columns 1,2, and 6 are linearly independent). The minimum distance is \(d=2\) since the smallest set of linearly dependent columns of \(H\) has size 2 (columns 3 and 5 are multiples of each other).
6.
Solution.
This is the 4×15 matrix whose columns are all the nonzero binary 4-tuples:
\begin{equation*}
\begin{bmatrix}
0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 1 \amp 1 \amp 1 \amp 1 \amp 1\\
0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 1\\
0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 1 \amp 1\\
1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1\\
\end{bmatrix}
\end{equation*}
7.
Use the efficient decoding algorithm for 1-error-correcting codes (Efficient Decoding Algorithm for 1-error Correcting Linear Codes) to decode the received words \((1111111)\) and \((1110011)\) using the binary Hamming code \(C_{H,3}\text{.}\)
Solution.
For each word \(\mathbf{y}\text{,}\) we compute \(H_3\transpose{\mathbf{y}}\) to find the error pattern and correct it. The parity-check matrix for \(C_{H,3}\) is
\begin{equation*}
H_3=\begin{bmatrix}
0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 1 \\
0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 1 \amp 1 \\
1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \\
\end{bmatrix}\text{.}
\end{equation*}
So we compute
\begin{equation*}
H\transpose{(1111111)}=\begin{bmatrix}0\\0\\0\end{bmatrix}
\end{equation*}
and
\begin{equation*}
H\transpose{(1110011)}=\begin{bmatrix} 0 \\ 0 \\1\end{bmatrix}\text{.}
\end{equation*}
The first result indicates no errors, so the decoded word is \((1111111)\text{.}\) The second result matches the first column of \(H_3\text{,}\) indicating an error in the first position. Correcting this gives the decoded word \((0110011)\text{.}\)
