1.
True/False: The roots of \(Q(x)=x^{p^n}-x\) in a splitting field of \(Q(x)\) over \(\F_p\) form the field \(\F_{p^n}\text{.}\)
Solution.
True. This is the content of Fields of Order \(p^n\) Exist.
Print preview
Worksheet Weekly Practice 7
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: An element of \(\GF(q)\) is if it generates the multiplicative group of the field; i.e. if its distinct powers are all nonzero elements of \(\GF(q)\text{.}\)
3.
True/False: Every finite field has a primitive element.
Solution.
True. This is the content of Finite Fields have a Primitive Element.
Short Response.
Your responses to these questions should be complete solutions with justifications, as per the Grading Specifications.
4.
Construct the Zech’s log table for the field \(F=\F_2[\alpha]/(\alpha^4+\alpha+1)\) with primitive element \(\alpha\text{.}\)
Solution.
| Power of \(\alpha\) | Field element | Coordinates | Zech’s log correspondence \(1+\alpha^i\) |
|---|---|---|---|
| \(\alpha^{-\infty}\) | \(0\) | \(0000\) | \(1+\alpha^{0}\) |
| \(\alpha^{0}\) | \(1 \) | \(1000\) | \(1+\alpha^{-\infty}\) |
| \(\alpha^{1}\) | \(\alpha \) | \(0100\) | \(1+\alpha^{4}\) |
| \(\alpha^{2}\) | \(\alpha^2 \) | \(0010\) | \(1+\alpha^{8}\) |
| \(\alpha^{3}\) | \(\alpha^3 \) | \(0001\) | \(1+\alpha^{14}\) |
| \(\alpha^{4}\) | \(1+\alpha \) | \(1100\) | \(1+\alpha^{1}\) |
| \(\alpha^{5}\) | \(\alpha+\alpha^2 \) | \(0110\) | \(1+\alpha^{10}\) |
| \(\alpha^{6}\) | \(\alpha^2+\alpha^3 \) | \(0011\) | \(1+\alpha^{13}\) |
| \(\alpha^{7}\) | \(1+\alpha+\alpha^3 \) | \(1101\) | \(1+\alpha^{9}\) |
| \(\alpha^{8}\) | \(1+\alpha^2\) | \(1010\) | \(1+\alpha^{2}\) |
| \(\alpha^{9}\) | \(\alpha+\alpha^3 \) | \(0101\) | \(1+\alpha^{7}\) |
| \(\alpha^{10}\) | \(1+\alpha+\alpha^2 \) | \(1110\) | \(1+\alpha^{5}\) |
| \(\alpha^{11}\) | \(\alpha+\alpha^2+\alpha^3 \) | \(0111\) | \(1+\alpha^{12}\) |
| \(\alpha^{12}\) | \(1+\alpha+\alpha^2+\alpha^3 \) | \(1111\) | \(1+\alpha^{11}\) |
| \(\alpha^{13}\) | \(1+\alpha^2+\alpha^3 \) | \(1011\) | \(1+\alpha^{6}\) |
| \(\alpha^{14}\) | \(1+\alpha^3 \) | \(1001\) | \(1+\alpha^{3}\) |
5.
Compute \(\alpha^{3}+\alpha^{5}\text{,}\) \(\alpha^{12}\alpha^{11}\text{,}\) and \((\alpha+\alpha^2)^3\text{.}\) Write all answers as powers \(\alpha^i\) with \(i\in\{0,1,\ldots,14\}\text{.}\)
6.
In this problem you will finish working through the example of coding with the \(2\)-error correcting code from Frobenius Maps & a 2-Error Correcting Code. This code is a double-error-correcting (narrow sense) alternant code over \(\F_2\). Remember that we defined this code with the parity check matrix
\begin{equation*}
H = \begin{bmatrix}
1 \amp \alpha \amp \alpha^2 \amp \ldots \amp \alpha^{14} \\
1 \amp \alpha^3 \amp \alpha^6 \amp \ldots \amp\alpha^{12} \\
\end{bmatrix}
\end{equation*}
where \(\alpha\) is the primitive generator of \(F\) in problem 1, the entries of the second row are the cubes of the entries of the first row, and we write the elements \(\alpha^i\) as vectors of length 4 over \(\F_2\) to get a binary code.
In class, we worked out the decoding algorithm for this code, which is given at the end of the assignment.
(a)
Explicitly write out the full matrix \(H\text{,}\) both in terms of the powers of \(\alpha\) and in terms of the corresponding vectors over \(\F_2\text{.}\) The first of these matrices should be a 2 by 15 matrix with entries that are powers of \(\alpha\text{,}\) and the second should be a 8 by 15 matrix with entries in \(\F_2\text{.}\)
Note: if you are using LaTeX to write your solution and are using the to your preamble to allow for more than 10 columns in the matrix.
bmatrix or pmatrix environment, you will need to add \setcounter{MaxMatrixCols}{15}
Solution.
First, here is \(H\) written as a \(2\times 15\) matrix over \(\GF(16)\text{.}\)
\begin{equation*}
H = \left(\begin{array}{lllllllllllllll}
1 \amp \alpha \amp \alpha^2 \amp \alpha^3 \amp \alpha^4\amp \alpha^5 \amp \alpha^6\amp \alpha^7\amp \alpha^8\amp \alpha^9 \amp \alpha^{10} \amp \alpha^{11}\amp \alpha^{12}\amp \alpha^{13} \amp \alpha^{14} \\
1 \amp \alpha^3 \amp \alpha^6 \amp \alpha^9 \amp\alpha^{12} \amp 1 \amp \alpha^3 \amp \alpha^6 \amp \alpha^9 \amp\alpha^{12} \amp 1 \amp \alpha^3 \amp \alpha^6 \amp \alpha^9 \amp\alpha^{12} \\
\end{array} \right)
\end{equation*}
And here is \(H\) written as an \(8\times 15\) matrix over \(\GF(2)\text{.}\)
\begin{equation*}
H = \left(\begin{array}{lllllllllllllll}
1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 1 \amp 1 \\
0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 1 \amp 1 \amp 1 \amp 0 \amp 0 \\
0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 1 \amp 1 \amp 1 \amp 0 \\
0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 1 \amp 1 \amp 1 \\
\hline 1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 1 \\
0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \\
0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \\
0 \amp 1 \amp 1 \amp 1 \amp 1 \amp 0 \amp 1 \amp 1 \amp 1 \amp 1 \amp 0 \amp 1 \amp 1 \amp 1 \amp 1
\end{array}\right)\text{.}
\end{equation*}
(b)
Find the locations of any errors that occurred if the syndrome is \(\bs_1=\transpose{(0111\, 0110)}\text{.}\)
Solution.
First, we write \(\bs_1\) as a vector in \(\GF(16)^2\) to get \((s_1,s_2)=(\alpha^{11},\alpha^5)\text{.}\) Because the syndrome is non-zero and
\begin{equation*}
s_1^3=\alpha^{33}=\alpha^3\neq \alpha^5=s_2\text{,}
\end{equation*}
we know neither zero nor one error occurred and we attempt to decode for the two-error case. We form the quadratic
\begin{align*}
x^2+s_1 x + \left(\frac{s_2}{s_1}+s_1^2\right)\amp = x^2+ \alpha^{11} x + (\alpha^{-6}+\alpha^{22})\\
\amp =x^2+\alpha^{11}x+(\alpha^9+\alpha^7)\\
\amp = x^2+\alpha^{11}x + \alpha^7(1+\alpha^2)\\
\amp = x^2+ \alpha^{11}x + 1\text{.}
\end{align*}
Now we can solve this quadratic in a variety of ways. We could plug in powers of \(\alpha\) until we find a root. We could apply the conditions given at the end of Decoding Algorithm for the Double-Error-Correcting Alternant Code over GF(2) to turn this into a problem of mod 15 arithmetic. Or we can use the technique in Quadratics over GF(16) and a First Look at Reed-Solomon Codes. From that we make the substitution \(y=\alpha^{4}x\) and convert to solve the equation
\begin{equation*}
y^2 + y + \alpha^8 = 0\text{.}
\end{equation*}
This gives the result
\begin{equation*}
y_0 \in \{0,1\} \qquad y_1=1 \qquad y_2 = 1 \qquad y_3= 1
\end{equation*}
so \(y=\alpha^{11}\) or \(y=\alpha^{12}\text{.}\) Thus we have \(x=\alpha^7\) or \(x=\alpha^8\) and so the errors occurred in positions \(7\) and \(8\) (0-indexed). We can check that indeed
\begin{equation*}
\alpha^7+\alpha^8=\alpha^7(1+\alpha)=\alpha^7\alpha^4=\alpha^{11}
\end{equation*}
and
\begin{equation*}
\alpha^7\alpha^8=\alpha^{15}=1\text{.}
\end{equation*}
(c)
Find the locations of any errors that occurred if the syndrome is \(\bs_2=\transpose{(0101\, 1111)}\)
Algorithm 71. Decoding Algorithm for the Double-Error-Correcting Alternant Code over GF(2).
Given a received word \(\by=(y_0\, y_1\, \ldots\, y_{14}) \in \F_2^{15}\)
-
Compute the syndrome \(\bs=H\transpose{\by}\text{.}\) Express the syndrome as \((s_1,s_2)\in F^2\) where \(F\) is the field from problem 1.
-
If \(\bs=(0,0)\text{,}\) declare that there are no errors and output \(\by\) as the decoded codeword.
-
If \(s_1^3=s_2\text{,}\) declare that there is a single error and find the location of the error by finding the unique \(i\in\{0,1,\ldots,14\}\) such that \(\alpha^i=s_1\text{.}\) Output the vector obtained from \(\by\) by flipping the bit in position \(i\text{.}\)
-
If \(s_1^3\neq s_2,\) form the quadratic equation\begin{equation*} x^2+s_1x+\left( \frac{s_2}{s_1}+s_1^2 \right) \end{equation*}and find its roots in \(F\text{.}\) If there are two distinct roots, \(\alpha^i\) and \(\alpha^j\) then the locations of the errors are \(i\) and \(j\text{.}\) Output the vector obtained from \(\by\) by flipping the bits in positions \(i\) and \(j\text{.}\) Otherwise, declare that there are more than 2 errors and that the decoding has failed.
Note that if \(x^2+\alpha^a x+\alpha^b=(x+\alpha^i)(x+\alpha^j)\) over \(F\text{,}\) then \(\alpha^a=\alpha^i+\alpha^j\) and \(\alpha^b=\alpha^i\alpha^j\text{.}\) Using Zech’s logs, we have \(\alpha^a=\alpha^i(1+\alpha^{j-i})=\alpha^{i+z(j-i)}.\) So \(\alpha^i,\alpha^j\) are roots of this quadratic if and only if
\begin{equation*}
a \equiv i+z(j-i) \pmod{15} \qquad \text{and}\qquad b\equiv i+j \pmod{15}\text{.}
\end{equation*}
