Print preview
Worksheet Weekly Practice 13
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: Cyclic codes of length \(n\) over \(\F_q\) are in 1-to-1 correspondence with of \(x^n-1\) over \(\F_q\text{.}\)
3.
True/False: All cyclic codes have a systematic generator matrix.
Short Response.
Your responses to these questions should be complete solutions with justifications, as per the Grading Specifications.
4.
Hint.
\(x^{21}-1\) factors over \(\F_2\) as the product of irreducible polynomials which are minimal polynomials for elements of order \(1,3,7,21\text{.}\) We have handled the first three of these already this semester; so you just need to work out what degree the polynomials for the order \(21\) elements (which first lie in \(\F_{2^6}\) but are not primitive in that field) are. Remember that for this problem you do not actually need to know the factors; just how many there are.
Solution.
Per the hint we need to determine the structure of the factors of \(x^{21}-1\) over \(\F_2\text{,}\) which are all of the minimal polynomials for elements of order dividing \(21\text{.}\)
- Order 1
-
Here we have just \(x+1\text{.}\)
- Order 3
-
Here we have just the single quadratic minimal polynomial \(x^2+x+1\text{.}\)
- Order 7
-
There are two minimal polynomials for elements of order 7, each of degree 3: \(x^3+x+1\) and \(x^3+x^2+1\text{.}\)
- Order 21
-
These elements first lie in \(\F_{2^6}\) so they have minimal polynomials of degree 6. There must be two of these since the total degree of the factors must be 21 and we have accounted for 1+2+3+3=9 so far. Call them \(f_1(x)\) and \(f_2(x)\text{.}\)
Now to generate a cyclic subspace of dimension \(9\) we need to select factors of \(x^{21}-1\) whose degrees sum to \(21-9=12\text{.}\) We can do this in the following ways:
\begin{equation*}
6+6, 6+3+3,6+3+2+1\text{.}
\end{equation*}
There is one way to do the first
\begin{equation*}
g(x)=f_1(x)f_2(x)\text{,}
\end{equation*}
two ways to do the second
\begin{gather*}
g(x)=f_1(x)(x^3+x+1)(x^3+x^2+1)\\
g(x)=f_2(x)(x^3+x+1)(x^3+x^2+1)
\end{gather*}
and four ways to do the third:
\begin{gather*}
g(x)=f_1(x)(x^3+x+1)(x^2+x+1)(x+1) \\
g(x)=f_1(x)(x^3+x^2+1)(x^2+x+1)(x+1) \\
g(x)=f_2(x)(x^3+x+1)(x^2+x+1)(x+1) \\
g(x)=f_2(x)(x^3+x^2+1)(x^2+x+1)(x+1) \text{.}
\end{gather*}
So there are a total of 7 cyclic subspaces of dimension 9 in \(\F_2^{21}\text{.}\)
5.
Determine the generator polynomial, check polynomial, and dimension of the smallest cyclic code containing the vector \(\vec{v}=(112\, 110)\) in \(\F_3^6\text{.}\)
Solution.
A cyclic code in \(\F_3^6\) is generated by a factor of \(x^6-1\) over \(\F_3\text{.}\) Now \(6\) is not relatively prime to \(3\) so we get repeated irreducible factors. Since \(6=2\cdot 3\) in fact we have:
\begin{equation*}
x^6-1=(x^2-1)^3=(x-1)^3(x-2)^3\text{.}
\end{equation*}
Now the vector \(\vec{v}\) corresponds to the polynomial \(v(x)=x^4+x^3+2x^2+x+1\text{.}\) So we need find to find the highest degree factor of \(x^6-1\) that also divides \(v(x)\text{.}\) In other words, we need to find the greatest common divisor of \(v(x)\) and \(x^6-1\text{.}\) We can do this using the Euclidean algorithm:
\begin{align*}
\gcd(x^6-1,x^4+x^3+2x^2+x+1) \amp = \gcd(2x^3+2x^2+2x,x^4+x^3+2x^2+x+1) \\
\amp = \gcd(2x^3+2x^2+2x,x^2+x+1)\\
\amp = \gcd(0,x^2+x+1) \\
\amp = x^2+x+1=(x+2)^2\text{.}
\end{align*}
So the generator polynomial of the smallest cyclic code containing \(\vec{v}\) is \(g(x)=x^2+x+1\text{,}\) the check polynomial is \(h(x)=(x^6-1)/g(x)=(x+2)(x+1)^3\text{,}\) and the dimension is \(6-\deg(g)=4\text{.}\)
6.
Let \(C_1 \) and \(C_2\) be cyclic codes of length \(n\) over \(\F_q\) with generator polynomials \(g_1(x)\) and \(g_2(x)\text{.}\)
(a)
Solution.
Let \(c(x)\in C_1 \cap C_2\text{.}\) Then \(g_1(x)\) divides \(c(x)\) and \(g_2(x)\) divides \(c(x)\text{,}\) so \(\lcm(g_1(x),g_2(x))\) divides \(c(x)\text{.}\) Conversely, if we have any \(c(x)\in \F_q[x]\) such that \(\lcm(g_1(x),g_2(x))\) divides \(c(x)\text{,}\) then both \(g_1(x)\) and \(g_2(x)\) divide \(c(x)\text{,}\) so \(c(x)\in C_1 \cap C_2\text{.}\) So
\begin{equation*}
C_1\cap C_2 = \{c(x) \in \F_q[x] : \lcm(g_1(x),g_2(x))\mid c(x)\}\text{.}
\end{equation*}
Since \(\lcm(g_1(x),g_2(x))\) is also a monic divisor of \(x^n-1\) (since both \(g_1\) and \(g_2\) are) this shows that \(C_1\cap C_2\) is a cyclic code of length \(n\) and its generator polynomial is \(\lcm(g_1(x),g_2(x))\text{.}\)
(b)
Show that \(C_1 + C_2 = \{\vec{c}_1+\vec{c}_2 \mid \vec{c}_1\in C_1, \vec{c}_2\in C_2\}\) is a cyclic code of length \(n\) and find its generator polynomial.
Solution.
Let \(c(x)\in C_1 + C_2\text{.}\) Then \(c(x)=c_1(x)+c_2(x)\) for some \(c_1(x)\in C_1\) and \(c_2(x)\in C_2\text{.}\) Since \(g_1(x)\) divides \(c_1(x)\) and \(g_2(x)\) divides \(c_2(x)\text{,}\) we have that \(\gcd(g_1(x),g_2(x))\) divides \(c(x)\text{.}\)
Conversely, suppose we have some \(c(x)\in \F_q[x]\) such that \(\gcd(g_1(x),g_2(x))\) divides \(c(x)\text{.}\) Then there is some \(f(x)\in \F_q[x]\) such that \(c(x)=f(x)\gcd(g_1(x),g_2(x))\text{.}\) Now by Bezout’s theorem there exist polynomials \(u_1(x)\) and \(u_2(x)\) such that \(\gcd(g_1(x),g_2(x))=u_1(x)g_1(x)+u_2(x)g_2(x)\text{.}\) So we have:
\begin{align*}
c(x)\amp=f(x)\gcd(g_1(x),g_2(x))\\
\amp =f(x)u_1(x)g_1(x)+f(x)u_2(x)g_2(x)\text{.}
\end{align*}
So
\begin{equation*}
C_1+C_2 = \{c(x) \in \F_q[x] : \gcd(g_1(x),g_2(x))\mid c(x)\}\text{.}
\end{equation*}
Since \(\gcd(g_1(x),g_2(x))\) is also a monic divisor of \(x^n-1\) (since both \(g_1\) and \(g_2\) are) this shows that \(C_1+C_2\) is a cyclic code of length \(n\) and its generator polynomial is \(\gcd(g_1(x),g_2(x))\text{.}\)
