1.
First, we may assume our quadratic is monic, just as for polynomials with real coefficients. So our goal is to solve
\begin{gather}
x^2+ax+b=0\tag{✶}
\end{gather}
where \(x,a,b\in \GF(16)\text{.}\)
Print preview
Worksheet Quadratics over GF(16) and a First Look at Reed-Solomon Codes
In this activity we will pick up a loose thread from our discussion last time about the 2-error correcting code constructed via \(\GF(16)\) from the binary Hamming code of length \(15\) regarding solving quadratic equations over a finite field of characteristic \(2\text{.}\) We will also take a first look at Reed-Solomon codes, from the perspective that Reed and Solomon used in their original paper in 1960.
To use Decoding Algorithm for the Double-Error-Correcting Alternant Code over GF(2), we need to be able to solve a quadratic equation in \(\GF(16)\text{.}\) The standard quadratic formula from polynomials over \(\R\) does not work, because we cannot divide by \(2\text{.}\) So we need to develop a different method. As we have in our previous problems, we will represent \(\GF(16)=\F_2[\alpha]/(\alpha^4+\alpha^2+1)\text{.}\)
2.
Now, suppose \(a\neq 0\text{.}\) Divide (✶) by \(a^2\) and make a suitable change of variables to show we can reduce this problem to solving equations of the form
\begin{gather}
y^2+y=c\text{.}\tag{✶✶}
\end{gather}
Keep track of how \(c\) is related to the coefficients of the original problem.
3.
Show that if \(\hat{y}\) is a solution to (✶✶) then so is \(\hat{y}+1\text{.}\) Hint: Use Frobenius linearity!
4.
Convince yourself that if we write two elements \(\bu,\bv \in \GF(16)\) in their coordinate form \((u_0\, u_1\, u_2\, u_3), (v_0\, v_1\, v_2\, v_3)\) where \(u_i,v_i\) are the coefficients of \(\alpha^i\) in the polynomial representation then it follows that the product \(\bu\cdot\bv \in \GF(16)\) has coordinate form
\begin{equation*}
\begin{pmatrix}
u_0v_0+(u_1v_3+u_2v_2+u_3v_1) \\
(u_0v_1+u_1v_0)+(u_1v_3+u_2v_2+u_3v_1)+(u_2v_3+u_3v_2)\\
(u_0v_2+u_1v_1+u_2v_0)+(u_2v_3+u_3v_2)+u_3v_3 \\
(u_0v_3+u_1v_2+u_2v_1+u_3v_0)+u_3v_3
\end{pmatrix}
\end{equation*}
by doing polynomial multiplication and replacing \(\alpha^4,\alpha^5,\) and \(\alpha^6\) by their polynomial representations. Please don’t do the whole calculation!
Solution.
This follows by computing the polynomial multiplication
\begin{equation*}
(u_0+u_1\alpha+u_2\alpha^2+u_3\alpha^3)(v_0+v_1\alpha+v_2\alpha^2+v_3\alpha^3)
\end{equation*}
and applying the relations \(\alpha^4=1+\alpha,\alpha^5=\alpha+\alpha^2,\alpha^6=\alpha^2+\alpha^3\text{.}\) The terms grouped in the given expression are the coefficients \(u_iv_j\) of \(\alpha^k\) where \(i+j=k\) and so the groups show up as given either naturally in the polynomial multiplication (the first term of each line) or from applying the reductions (the others).
5.
Use the calculation in the previous problem to write (✶✶) as a system of four linear equations in the four unknowns \(y_i\text{,}\) \(i=0,1,2,3\) over \(\F_2\) with \(c=(c_0\, c_1\, c_2\, c_3)\text{.}\)
Solution.
We apply the previous problem to find \(y^2=y\cdot y\text{,}\) remembering that \(y_iy_j+y_jy_i=0\) and \(y_i^2=y_i\) since the coefficients lie in \(\F_2\text{.}\)
\begin{equation*}
y^2=(y_0+y_2, y_2, y_1+y_3, y_3)\text{.}
\end{equation*}
Then plugging everything in and adding yields the vector equation
\begin{equation*}
\transpose{(y_2,y_1+y_2,y_1+y_2+y_3,0)}=\transpose{(c_0,c_1,c_2,c_3)}\text{.}
\end{equation*}
6.
Solve your system of equations. Which variable is free? Does that make sense in light of your answer to part 3? What condition do you find on \(c\) for the system to have a solution?
Solution.
Solving this system gives
\begin{equation*}
y_2=c_0 \qquad y_1=c_0+c_1 \qquad y_3=c_1+c_2 \qquad c_3 =0\text{.}
\end{equation*}
So \(y_0\) is free, which makes sense because we saw that adding one to a solution should also be a solution. We also see that the system has a solution if and only if \(c_3=0\text{,}\) so only half of the quadratics with nonzero linear term have roots in \(\GF(16)\text{.}\) The others are irreducible.
7.
Apply all of this to find the roots of the quadratic
\begin{equation*}
x^2+\alpha x + \alpha^{12}
\end{equation*}
in \(\GF(16)\text{.}\) A lookup table for \(\GF(16)\) follows.
Solution.
First we transform the equation as in problem 2 to get
\begin{equation*}
y^2+y+\alpha^{10}=0
\end{equation*}
with \(y=x/\alpha\text{.}\) Then \(\alpha^{10}=1+\alpha+\alpha^2\) so \((c_0\,c_1\,c_2\,c_3)=(1\,1\,1\,0)\text{.}\) Substituting into the result of the last problem shows that the two roots of the transformed equation are
\begin{equation*}
y_1=(0\,0\,1\,0)=\alpha^2 \quad y_2=(1\,0\,1\,0)=\alpha^8\text{.}
\end{equation*}
So the roots of the original equation are
\begin{equation*}
x_1=\alpha y_1 = \alpha^3 \quad x_2=\alpha y_2 = \alpha^9
\end{equation*}
and indeed a quick check shows that
\begin{equation*}
(x+\alpha^3)(x+\alpha^9)=x^2+(\alpha^3+\alpha^9)+\alpha^12 = x^2+ (\alpha^3+\alpha+\alpha^3)x+\alpha^12 = x^2+\alpha x + \alpha^12\text{.}
\end{equation*}
| Power of \(\alpha\) | Field element | Coordinates |
|---|---|---|
| \(\alpha^{-\infty}\) | \(0\) | \(0000\) |
| \(\alpha^{0}\) | \(1 \) | \(1000\) |
| \(\alpha^{1}\) | \(\alpha \) | \(0100\) |
| \(\alpha^{2}\) | \(\alpha^2 \) | \(0010\) |
| \(\alpha^{3}\) | \(\alpha^3 \) | \(0001\) |
| \(\alpha^{4}\) | \(1+\alpha \) | \(1100\) |
| \(\alpha^{5}\) | \(\alpha+\alpha^2 \) | \(0110\) |
| \(\alpha^{6}\) | \(\alpha^2+\alpha^3 \) | \(0011\) |
| \(\alpha^{7}\) | \(1+\alpha+\alpha^3 \) | \(1101\) |
| \(\alpha^{8}\) | \(1+\alpha^2\) | \(1010\) |
| \(\alpha^{9}\) | \(\alpha+\alpha^3 \) | \(0101\) |
| \(\alpha^{10}\) | \(1+\alpha+\alpha^2 \) | \(1110\) |
| \(\alpha^{11}\) | \(\alpha+\alpha^2+\alpha^3 \) | \(0111\) |
| \(\alpha^{12}\) | \(1+\alpha+\alpha^2+\alpha^3 \) | \(1111\) |
| \(\alpha^{13}\) | \(1+\alpha^2+\alpha^3 \) | \(1011\) |
| \(\alpha^{14}\) | \(1+\alpha^3 \) | \(1001\) |
8.
Use Lagrange interpolation to find your assigned decoded \(p(x)\) for the Reed-Solomon code over \(\GF(8)\) with received word
\begin{equation*}
\by=(1\, \alpha\, \alpha^3\, \alpha^3\, 1\, 1\, \alpha\, 0)\text{.}
\end{equation*}
Remember that we have
\begin{equation*}
p(x)=\sum_{i=0}^m \beta_i \frac{L_i(x)}{L_i(\alpha_i)}
\end{equation*}
as the polynomial interpolating the \(m\) points \((\alpha_i,\beta_i)\) with \(L_i(x)=\prod_{j\neq i}(x-\alpha_j)\text{.}\)
Solution.
Unfortunately I accidentally closed my tab with the random sets so I can’t get them back. So here is a new set of 12 random sets; I’ll do one in detail and give the computer assisted results for the others.
-
Set 1: 1, 2, 4
-
Set 2: 2, 3, 4
-
Set 3: 3, 7, 8
-
Set 4: 1, 6, 7
-
Set 5: 3, 5, 6
-
Set 6: 1, 6, 8
-
Set 7: 4, 5, 6
-
Set 8: 2, 6, 8
-
Set 9: 3, 4, 5
-
Set 10: 1, 4, 8
-
Set 11: 1, 6, 8
-
Set 12: 1, 5, 7
In Set 1 we choose positions \(1,2,4\text{.}\) So we need to find the polynomial satisfying
\begin{equation*}
p(0)=y_1=1 \qquad p(\alpha)=y_2=\alpha \qquad p(\alpha^3)=y_4=\alpha^3\text{.}
\end{equation*}
We compute
\begin{align*}
L_1(x) \amp = (x-\alpha)(x-\alpha^3)=x^2+(\alpha+\alpha^3)x+\alpha^4=x^2+x+\alpha+\alpha^2 \\
L_2(x) \amp = (x-0)(x-\alpha^3)=x^2+(1+\alpha) x\\
L_3(x) \amp = (x-0)(x-\alpha)=x^2+\alpha x
\end{align*}
and
\begin{align*}
L_1(0) \amp =\alpha+\alpha^2 \\
L_2(\alpha) \amp =\alpha^2 +\alpha+\alpha^2=\alpha\\
L_3(\alpha^3) \amp =\alpha^6+\alpha^4=1+\alpha^2+\alpha+\alpha^2=1+\alpha \text{.}
\end{align*}
Then
\begin{align*}
p(x) \amp = p(0)\frac{L_1(x)}{L_1(0)}+p(\alpha)\frac{L_2(x)}{L_2(\alpha)}+p(\alpha^3)\frac{L_3(x)}{L_3(\alpha)} \\
\amp = 1\frac{x^2+x+\alpha+\alpha^2}{\alpha+\alpha^2}+\alpha\frac{x^2+(1+\alpha) x}{\alpha}+\alpha^3\frac{x^2+\alpha x}{1+\alpha} \\
\amp = (\alpha^3 x^2+\alpha^3 x+ 1)+(x^2+(1+\alpha) x)+(x^2+\alpha x)\\
\amp = \alpha^3 x^2 + \alpha x + 1\text{.}
\end{align*}
The calculator tool at Calculation Tools gives us the further polynomials
-
\(\displaystyle p_1(x)=\alpha^3 x^2+\alpha x + 1\)
-
\(\displaystyle p_2(x)=\alpha^3 x^2+\alpha x + 1\)
-
\(\displaystyle p_3(x)=\alpha^3 x^2+\alpha x + 1\)
-
\(\displaystyle p_4(x)=\alpha^3 x^2+\alpha x + 1\)
-
\(\displaystyle p_5(x)=\alpha^4 x^2+\alpha^4 x + \alpha^2\)
-
\(\displaystyle p_6(x)=\alpha^3 x^2+\alpha x + 1\)
-
\(\displaystyle p_7(x)=x^2+x+\alpha^6\)
-
\(\displaystyle p_8(x)=\alpha^3 x^2+\alpha x + 1\)
-
\(\displaystyle p_9(x)=\alpha x^2 + \alpha^6 x + \alpha^4\)
-
\(\displaystyle p_{10}(x)=\alpha^3 x^2+\alpha x + 1\)
-
\(\displaystyle p_{11}(x)=\alpha^3 x^2+\alpha x + 1\)
-
\(\displaystyle p_{12}(x)=\alpha^2 x^2+\alpha^5 x+1\)
From these we see that the correct polynomial should be \(p(x)=\alpha^3 x^2+\alpha x + 1\text{.}\) We can then find the errors by re-encoding this polynomial and comparing with the received word. Doing this gives the same entries as \(\by\) except in the 5th position, which should have been a \(0\text{.}\) This agrees with the fact that only those choices of positions including the 5th coordinate gave different polynomials.
| Power of \(\alpha\) | Field Element | Coordinates |
|---|---|---|
| \(-\infty\) | \(0\) | 000 |
| \(\alpha^0\) | \(1\) | 100 |
| \(\alpha^1\) | \(\alpha\) | 010 |
| \(\alpha^2\) | \(\alpha^2\) | 001 |
| \(\alpha^3\) | \(1+\alpha \) | 110 |
| \(\alpha^4\) | \(\alpha + \alpha^2\) | 011 |
| \(\alpha^5\) | \(1 + \alpha + \alpha^2\) | 111 |
| \(\alpha^6\) | \(1+\alpha^2 \) | 101 |
