Skip to main content

Algebraic Coding Theory MATH 4012 Spring 2026

Dr. Hunter Lehmann

Print preview

Paper size
Additional printing options
Print headers
Print footers

Worksheet GRS and RS Codes

Today we’ll look at generalized Reed-Solomon (GRS) and Reed-Solomon (RS) codes in more detail. We’ll see that their duals are also GRS/RS codes respectively, and talk about a different encoding perspective from the one we discussed in the previous activity.
🔗

1.

Show that when a GRS code \(\GRS_{n,k}(\balpha,\bv)\) is primitive, then a set of column multipliers of its dual code are \(u_i=-\alpha_i/v_i\text{.}\)
🔗
Hint.
Recall from Daily Prep 13 that when \(\{\alpha_i\}_i=F^*\) we have \(L_i(\alpha_i)=-\alpha_i^{-1}\)
🔗
🔗
Solution.
A primitive GRS code satisfies the condition of the hint, so we have
\begin{equation*} u_i^{-1}=v_i L_i(\alpha_i)=-v_i\alpha_i^{-1} \end{equation*}
and thus
\begin{equation*} u_i=-\alpha_i/v_i\text{.} \end{equation*}
🔗
🔗
🔗

2.

Last time we considered the (singly-extended) \(\RS_{8,3}\) code over \(F=\GF(8)\) with \(p(x)\in F_3[x]\mapsto (p(0),p(\alpha),\ldots,p(\alpha^7)) \text{.}\) Give a set of code locators and column multipliers for the non-extended version of this code, i.e.
\begin{equation*} p(x) \mapsto (p(1),p(\alpha), p(\alpha^2),\ldots, p(\alpha^6))\text{.} \end{equation*}
🔗
Solution.
The code locators are given:
\begin{equation*} \vec{\alpha}=(1,\alpha,\alpha^2,\ldots,\alpha^6)\text{.} \end{equation*}
The column multipliers here are found by noting that we gave above the generator description of the code with \(u_i=1\) for all \(i\text{.}\) Substituting into the formula from the previous part gives \(v_i=\alpha_i\) for each \(i\) since we are working in characteristic 2.
🔗
🔗
🔗

3.

Give the canonical generator and parity check matrices for the code in the last exercise.
🔗
Solution.
\begin{equation*} G_{\GRS}=\begin{bmatrix} 1 \amp 1 \amp 1 \amp 1 \amp 1 \amp 1 \amp 1 \\ 1 \amp \alpha \amp \alpha^2 \amp \alpha^3 \amp \alpha^4 \amp \alpha^5 \amp \alpha^6 \\ 1 \amp \alpha^2 \amp \alpha^4 \amp \alpha^6 \amp \alpha \amp \alpha^3 \amp \alpha^5 \\ \end{bmatrix} \end{equation*}
\begin{equation*} H_{\GRS}=\begin{bmatrix} 1 \amp \alpha \amp \alpha^2 \amp \alpha^3 \amp \alpha^4 \amp \alpha^5 \amp \alpha^6 \\ 1 \amp \alpha^2 \amp \alpha^4 \amp \alpha^6 \amp \alpha \amp \alpha^3 \amp \alpha^5 \\ 1 \amp \alpha^3 \amp \alpha^6 \amp \alpha^2 \amp \alpha^5 \amp \alpha \amp \alpha^4 \\ 1 \amp \alpha^4 \amp \alpha \amp \alpha^5 \amp \alpha^2 \amp \alpha^6 \amp \alpha^3 \\ 1 \amp \alpha^5 \amp \alpha^3 \amp \alpha \amp \alpha^6 \amp \alpha^4 \amp \alpha^2 \\ \end{bmatrix} \end{equation*}
🔗
🔗
🔗

4.

Is this code primitive? Narrow-sense? Normalized?
🔗
Solution.
This code is primitive since its code locators are all non-zero elements of the field. It is narrow-sense because its column multipliers \(v_i\) are equal to \(\alpha_i\) for all \(i\text{.}\) It is not normalized because the column multipliers are not always 1.
🔗
🔗
🔗

5.

Compute the generator polynomial \(g(x)\) for the code in the last exercise.
🔗
Solution.
We have
\begin{equation*} g(x)=(x-\alpha)(x-\alpha^2)(x-\alpha^3)(x-\alpha^4)(x-\alpha^5) = \alpha + \alpha^4 x + \alpha^6 x^2 + \alpha^3 x^3 + \alpha^2 x^4 + x^5 \text{.} \end{equation*}
🔗
🔗
🔗

6.

Encode the message polynomial \(m(x)=1+\alpha x^2\) by multiplication by \(g(x)\text{.}\)
🔗
Solution.
We have
\begin{equation*} c(x)=m(x)g(x)=\alpha + \alpha^4 x + x^2 + \alpha^2 x^3 + \alpha^6 x^4 + \alpha^5 x^5 +\alpha^3 x^6 + \alpha x^7\text{.} \end{equation*}
🔗
🔗
🔗

7.

Encode the message polynomial \(m(x)=1+\alpha 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{.}\)
🔗
Solution.
We have
\begin{equation*} c(x)=x^5m(x)-r_m(x) = \alpha^4 x + \alpha^6 x^2 +\alpha^3 x^3 + \alpha^2 x^4 + x^5+\alpha x^7 \end{equation*}
🔗
🔗
🔗

8.

What do you notice about the second encoding?
🔗
Solution.
The coefficients of the message are preserved as part of the codeword (in this case in the last three positions/degrees).
🔗
🔗
🔗
Table 90. Representation of \(\GF(2^3)\) as \(\mathbb{F}_2[\alpha]/(\alpha^3+\alpha+1)\)
🔗
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
🔗
PrevTopNext