Cyclic codes as ideals of a quotient ring

Question

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?

Answer 1

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}). $$

Answer 2

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):

1. We can add any two elements in the ideal together, and get back an element in the ideal (closed under addition).
2. 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.