1.
Again we will consider \(F=\GF(8)=\GF(2)[\beta]/(\beta^3+\beta+1)\text{.}\) What are the possible choices of \(n\) for an RS code over this field?
Print preview
Worksheet GRS and RS Codes Take 2
Today we’ll try again with generalized Reed-Solomon (GRS) and Reed-Solomon (RS) codes in more detail. We’ll emphasize this different encoding perspective from the one we discussed originally, make sure we have time for hands-on computation, and start to discuss the practicality of using GRS/RS codes as binary codes.
2.
Let’s choose \(n\) to be the useful option in the last exercise. To define an RS code with this length, we also need to choose a dimension \(k\text{,}\) multiplier \(b\text{,}\) and element \(\alpha\) of order \(n\) in \(F\text{.}\) Make a set of choices that will allow the resulting RS code to correct any two errors that occur. I suggest making your life simple and picking \(b\in \{0,1\}\) (although you can pick anything in \(\{0,1,\ldots,6\}\text{.}\))
3.
Give the canonical generator and parity check matrices for the code with the parameters you chose.
4.
Is this code primitive? Narrow-sense? Normalized?
5.
Compute the roots and generator polynomial \(g(x)\) for the code you created.
6.
7.
You can compute a generator matrix for the multiplication by \(g(x)\) encoding procedure by recording the effect of this procedure on a basis of the polynomials of degree \(k-1\) or less. A particularly nice basis for doing this is \(\{1,x,x^2,\ldots,x^{k-1}\}\text{.}\) What matrix do you get when you do that? Multiplication by a matrix of this form is particularly straightforward to implement efficiently in hardware; see Roth § 5.3 for a description.
8.
Encode the message polynomial \(m(x)=1+ x^2\) by remaindering:
\begin{equation*}
m(x)\mapsto x^{n-k}m(x)-r_m(x)
\end{equation*}
where \(r_m(x)\) is the remainder on division of \(x^{n-k}m(x)\) by \(g(x)\text{.}\)
9.
What do you notice about the second encoding?
