1.
True/False: Every quadratic equation \(y^2+y+c=0\) over \(\GF(16)\) has a solution in \(\GF(16)\text{.}\)
Print preview
Worksheet Weekly Practice 8
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.
True/False: In original Reed-Solomon codes, the code locators include all the elements of the field including zero.
3.
Fill-In: In an original \([q,k,d]_q \) Reed-Solomon code, the decoding algorithm requires computing \(\fillinmath{\binom{q}{k}}\) polynomial interpolations.
Short Response.
Your responses to these questions should be complete solutions with justifications, as per the Grading Specifications.
4.
Adapt the technique of Quadratics over GF(16) and a First Look at Reed-Solomon Codes to give a general method for solving any quadratic equation of the form \(x^2+ax+b\) over \(\GF(8)=\F_2[\alpha]/(\alpha^3+\alpha+1).\)
Solution.
As in the activity, we let \(y=x/a\) and then we have \(x^2+ax+b=0\) if and only if \(y^2+y=c=b/a^2\text{.}\) Now in this field we have
\begin{align*}
(y_0+y_1\alpha+y_2\alpha^2)^2 \amp = y_0^2+(y_0y_1+y_1y_0)\alpha+(y_0y_2+y_1^2+y_2y_1)\alpha^2+(y_1y_2+y_2y_1)\alpha^3+y_2^2\alpha^4\\
\amp = y_0 + y_1\alpha^2 +y_2(\alpha+\alpha^2)\\
\amp = y_0 + y_2\alpha + (y_1+y_2)\alpha^2\text{.}
\end{align*}
Setting up the system of equations in the coefficients \(y_i\) from the equation \(y^2+y=c\) gives
\begin{equation*}
\begin{bmatrix} y_0\\y_2\\y_1+y_2 \end{bmatrix} +\begin{bmatrix} y_0\\y_1\\y_2\end{bmatrix}= \begin{bmatrix} c_0\\c_1\\c_2 \end{bmatrix}
\end{equation*}
which yields the system of equations
\begin{equation*}
\begin{cases}
0 \amp = c_0 \\
y_1+y_2 \amp = c_1\\
y_1 \amp = c_2
\text{.}\end{cases}
\end{equation*}
So the quadratic \(y^2+y+c=0\) has solutions if and only if \(c_0=0\text{,}\) and in that case the solutions are \(y=c_2\alpha+(c_1+c_2)\alpha^2\) and \(y=1+c_2\alpha+(c_1+c_2)\alpha^2\text{.}\)
5.
Use your method to solve the equation \(x^2+\alpha^4 x + \alpha^3=0\text{.}\)
Solution.
Rewriting with \(y=x/\alpha^4\text{,}\) we have \(y^2+y=\alpha^3/\alpha^8=\alpha^2\text{.}\) So the roots are \(y=\alpha+\alpha^2=\alpha^4\) and \(y=1+\alpha+\alpha^2=\alpha^5\text{.}\) So the roots of the original equation are \(x=\alpha^8=\alpha\) and \(x=\alpha^9=\alpha^2\text{.}\) A quick check confirms that \(\alpha\alpha^2=\alpha^3\) and \(\alpha+\alpha^2=\alpha^4\) as desired.
6.
Give a parity-check matrix for the (modern-perspective) \([5,3]_{11}\) generalized Reed-Solomon code over \(\GF(11)\) with code locators \(1,3,5,7,9\) and column multipliers \(9,7,5,3,1\text{.}\)
Solution.
The GRS code with these code locators and column multipliers has parity-check matrix
\begin{align*}
H\amp =\begin{bmatrix}
1 \amp 1 \amp 1 \amp 1 \amp 1 \\
1 \amp 3 \amp 5 \amp 7 \amp 9
\end{bmatrix}
\begin{bmatrix}
9 \amp 0 \amp 0 \amp 0 \amp 0 \\
0 \amp 7 \amp 0 \amp 0 \amp 0 \\
0 \amp 0 \amp 5 \amp 0 \amp 0 \\
0 \amp 0 \amp 0 \amp 3 \amp 0 \\
0 \amp 0 \amp 0 \amp 0 \amp 1
\end{bmatrix} \\
\amp = \begin{bmatrix} 9 \amp 7 \amp 5 \amp 3 \amp 1 \\
9 \amp 10 \amp 4 \amp 10 \amp 9
\end{bmatrix}
\end{align*}
