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 Weekly Practice 9

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.
🔗

1.

True/False: When defining a GRS code over \(\GF(q)\text{,}\) any choice of \(n\) evaluation points \(\alpha_1,\alpha_2,\ldots,\alpha_n\) and nonzero weights \(v_1,v_2,\ldots,v_n\) and dimension \(k\) will yield a code with the same parameters.
🔗
Solution.
True. The parameters of a GRS code are determined by the number of evaluation points and the dimension, and the choice of evaluation points and weights does not affect the parameters. However, the choice of evaluation points and weights can affect the specific codewords in the code, so different choices can yield different codes with the same parameters.
🔗
🔗
🔗

2.

True/False: When defining a RS code over \(\GF(q)\text{,}\) we can choose any length \(n\leq q-1\text{.}\)
🔗
Solution.
False. The length of an RS code over \(\GF(q)\) must be a divisor of \(q-1\) because the evaluation points must be distinct powers of a nonzero element of the field, and the order of any nonzero element divides \(q-1\text{.}\)
🔗
🔗
🔗
🔗

Short Response.

Your responses to these questions should be complete solutions with justifications, as per the Grading Specifications. The polynomial computation tools from SageMath may be helpful once you understand how to do the computations.
🔗

3.

Construct the generator polynomial \(g(x)\) for the narrow-sense primitive Reed-Solomon code over \(F=\GF(16)=\F_2[\alpha]/(\alpha^4+\alpha+1)\) with length \(n=15\) and distance \(d=7\) and generator element \(\alpha\text{.}\)
🔗
Solution.
This code has length \(n=15\) since it is primitive and and dimension \(k=n-d+1=9\text{.}\) For the code to be narrow-sense we take \(b=1\text{.}\) So the generator polynomial is
\begin{align*} g(x)\amp =\prod_{i=0}^{5} (x-\alpha^{1+i})\\ \amp =(x-\alpha)(x-\alpha^2)(x-\alpha^3)(x-\alpha^4)(x-\alpha^5)(x-\alpha^6)\\ \amp x^6+\alpha^{10}x^5+\alpha^{14}x^4+\alpha^4 x^3+\alpha^6x^2+\alpha^9x + \alpha^6 \text{.} \end{align*}
🔗
🔗
🔗

4.

Construct the generator matrix for the encoding of the code from the previous problem using the encoding map \(\mathcal{E}\) that sends \(m(x)\mapsto m(x)g(x)\) and records the coefficent sequence of the resulting polynomial as \((c_0\, c_1\, \dots\, c_{n-1})\text{.}\)
🔗
Note: if you are using to write your solution and are using the bmatrix or pmatrix environment, you will need to add 
\setcounter{MaxMatrixCols}{15}
to your preamble to allow for more than 10 columns in the matrix.
🔗
Solution.
This generator matrix is \(9\times 15\) and has rows given by the shifts of the coefficients of the generator polynomial:
\begin{equation*} G=\begin{bmatrix} \alpha^6 \amp \alpha^9 \amp \alpha^6 \amp \alpha^4 \amp \alpha^{14} \amp \alpha^{10} \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \\ 0 \amp \alpha^6 \amp \alpha^9 \amp \alpha^6 \amp \alpha^4 \amp \alpha^{14} \amp \alpha^{10} \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp \alpha^6 \amp \alpha^9 \amp \alpha^6 \amp \alpha^4 \amp \alpha^{14} \amp \alpha^{10} \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \amp \alpha^6 \amp \alpha^9 \amp \alpha^6 \amp \alpha^4 \amp \alpha^{14} \amp \alpha^{10} \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \amp \alpha^6 \amp \alpha^9 \amp \alpha^6 \amp \alpha^4 \amp \alpha^{14} \amp \alpha^{10} \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp \alpha^6 \amp \alpha^9 \amp \alpha^6 \amp \alpha^4 \amp \alpha^{14} \amp \alpha^{10} \amp 1 \amp 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp \alpha^6 \amp \alpha^9 \amp \alpha^6 \amp \alpha^4 \amp \alpha^{14} \amp \alpha^{10} \amp 1 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp \alpha^6 \amp \alpha^9 \amp \alpha^6 \amp \alpha^4 \amp \alpha^{14} \amp \alpha^{10} \amp 1 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp \alpha^6 \amp \alpha^9 \amp \alpha^6 \amp \alpha^4 \amp \alpha^{14} \amp \alpha^{10} \amp 1 \\ \end{bmatrix} \end{equation*}
🔗
🔗
🔗

5.

Encode the messages \(m_1(x)=\alpha+x^2+x^4\) and \(m_2(x)=x^7+\alpha^3x^3+\alpha^7x\text{.}\)
🔗
Solution.
We compute the codewords as \(c_i(x)=m_i(x)g(x)\) for \(i=1,2\text{.}\) We have
\begin{align*} c_1(x)\amp=x^{10}+\alpha^{10}x^9+ \alpha^3 x^8+\alpha^2 x^7 + \alpha^{10}x^6 + \alpha^{10} x^5+x^4+\alpha^6 x^3 + \alpha^{10} x^2+\alpha^{10} x+ \alpha^7\\ c_2(x) \amp = x^{13}+\alpha^{10} x^{12} + \alpha^{14} x^{11} +\alpha^4 x^{10}+\alpha^2 x^{9} +\alpha^{10} x^8+\alpha^4 x^7 + \alpha^{12} x^6+\alpha^5 x^5+ x^4 + \alpha^{10} x^3 + \alpha x^2+\alpha^{13} x \end{align*}
or as coefficient vectors
\begin{gather*} c_1 = (\alpha^7, \alpha^{10}, \alpha^{10}, \alpha^6, 1, \alpha^{10},\alpha^{10}, \alpha^2, \alpha^3,\alpha^{10},1,0,0,0,0) \\ c_2 = (0, \alpha^{13}, \alpha, \alpha^{10}, 1, \alpha^5, \alpha^{12},\alpha^4, \alpha^{10},\alpha^2, \alpha^4, \alpha^{14},\alpha^{10},1,0) \end{gather*}
🔗
🔗
🔗

6.

Encode the messages \(m_1(x)\) and \(m_2(x)\) using the encoding map \(\mathcal{E}^*\) that sends \(m(x)\mapsto x^{n-k}m(x)-r_m(x)\) where \(r_m(x)\) is the remainder on division of \(x^{n-k}m(x)\) by \(g(x)\) and records the coefficent sequence of the resulting polynomial as \((c_0\, c_1\, \dots\, c_{n-1})\text{.}\)
🔗
Solution.
We compute the remainders as \(r_{m_i}(x)=x^{n-k}m_i(x) \mod g(x)\) for \(i=1,2\text{.}\) Note that the degree of \(g(x)\) is exactly \(n-k=6\text{,}\) so the remainders will have degree less than 6 and therefore the coefficients of \(c_i(x)\) in exponents \(6\) and higher will be the same as those of \(x^{n-k}m_i(x)\text{.}\) We have
\begin{align*} r_{m_1} \amp = \alpha^{12}x^5+\alpha^5 x^3+\alpha^9 x^2+\alpha^5 x+\alpha^9\\ r_{m_2} \amp = \alpha x^5 + \alpha^9 x^4 + \alpha^2 x^3+\alpha^{11} x^2+\alpha^{10} x+\alpha^{12}\text{.} \end{align*}
So the corresponding coefficient vectors are
\begin{align*} c_1 \amp= (\alpha^9, \alpha^5, \alpha^9, \alpha^4, 0, \alpha^{12},\alpha,0,1,0,1,0,0,0,0) \amp \\ c_2 \amp =(\alpha^{12}, \alpha^{10}, \alpha^{11}, \alpha^2, \alpha^9, \alpha, \alpha^7, 0, \alpha^3, 0, 0, 0, 1,0,0) \end{align*}
🔗
🔗
🔗
🔗
🔗
PrevTopNext