2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Multiplication by $x$ in this quotient ring amounts to cyclically shifting the codeword. See my comment under kodlu's answer for a bit more details. $\endgroup$ Feb 24 at 21:42

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
  • 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 at 21:40
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.