I'm finding the algebra behind cyclic codes somewhat tricky. The starting point is easy enough: $C\subseteq \mathbb F_q^n$ is cyclic if any cyclic shift of a codeword $c\in \mathbb F_q^n$ is still in $C$. Then I got hit with this: cyclic codes correspond to the ideals of $$\mathbb F_q[x]/(x^n-1). $$ Now, I have some background in abstract algebra, mostly from group theory. I can recognize a ring and a quotient, but I'm having trouble to see the equivalence. Can anyone explain it to me in very simple terms?
2 Answers
The ideal property gives an equivalence of polynomials upon division modulo $(x^n-1).$ $$p(x) \equiv q(x) \text{ iff } p(x) - q(x) = 0 \pmod{(x^n-1)}$$
Thinking of multiplication by $x$ as the shift operator, $$c(x)=c_0+c_1 x+\cdots+ c_{n-1} x^{n-1}$$ this says that after $n$ cyclic shifts you get the same polynomial back. Here $c(x)$ represents the codeword $$(c_0,c_1,\ldots,c_{n-1})$$
Edit: Thanks for the helpful comment, @JyrkiLahtonen:
Note that $$ x c(x)=c_{n-1}+c_0 x+ c_1 x^2+\cdots+c_{n-2} x^{n-1} +c_{n-1}(x^n-1)\equiv $$ $$ \equiv c_{n-1}+c_0 x+ c_1 x^2+\cdots+c_{n-2} x^{n-1} \pmod{x^n-1} $$ explaining why multiplication by $x$ in the quotient ring $\mathbb{F}_q[x]/(x^n−1)$ exactly corresponds to the cyclic shift $$ (c_0,c_1,\ldots,c_{n-1})\mapsto (c_{n-1},c_0,c_1,\ldots,c_{n-2}). $$
-
1$\begingroup$ I would make this perhaps a bit more concrete by adding the observation that $$xc(x)=c_{n-1}+c_0x+c_1x^2+\cdots+c_{n-2}x^{n-1}+c_{n-1}(x^n-1) \equiv c_{n-1}+c_0x+c_1x^2+\cdots+c_{n-2}x^{n-1}\pmod {x^n-1}.$$ This explains why multiplication by $x$ precisely in the quotient ring $\Bbb{F}_q[x]/(x^n-1)$ corresponds to the cyclic shift $$(c_0,c_1,\ldots,c_{n-1})\mapsto (c_{n-1},c_0,c_1,\ldots,c_{n-2}).$$ $\endgroup$ Feb 24, 2022 at 21:40
Recall that an ideal of a ring is a set of elements from the ring, such that (this is not a complete list of properties, just those important for my answer):
- We can add any two elements in the ideal together, and get back an element in the ideal (closed under addition).
- We can multiply any element of the ideal by any element of the ring, and get back an element in the ideal.
Now recall that a cyclic code is also a linear code, with the extra property that a cyclic shift still gives a codeword (as you mention in the question).
The other answer has explained the importance of the modulus $(x^n-1)$ in the ring to achieve the cyclic part. Now the fact that a valid code is an ideal in this quotient ring corresponds to it being a linear code - adding two codewords together gives another valid codeword. It's also worth noting that this is a principal ideal ring, which means every ideal can be generated by a single element. That element is exactly the generator polynomial $g$ of the code. Property #2 above means that every multiple of the generator $g$ by another polynomial (mod $(x^n-1)$) still gives a valid codeword.