0
$\begingroup$

In cyclic codes, a code vector can be obtained from another by simple circular shift. Why then the other method is taught that is a bit round about? Take the code polynomial. Multiply it by the polynomial with power equal to the circular shift amount and then take the modulo of another polynomial and then convert this resulting polynomial to the codevector to find that the code vector obtained by circular shift and this polynomial method are the same. Apart from this interesting property is there any advantage of the polynomial method in implementation or in any other way?

$\endgroup$
1
$\begingroup$

While it's true that a circular shift of a codeword is another codeword, it's not true that you can generate all codewords by shifting one codeword. Consider the all-zeros or all-ones codewords; they can't be generated by shifting any of the other codewords.

For very large codes, it is important to have simple algorithms to generate a codeword based on the input. Even if the algorithm seems to operate on a "roundabout" way for small codes, try to implement your idea using a code with $(n,k)=(100,50)$, just to give one example. You'll find that the "roundabout" way is actually much easier to implement!

$\endgroup$
  • $\begingroup$ @DilipSarwate Thanks for catching that! Fixed. $\endgroup$ – MBaz Mar 14 '16 at 16:03
0
$\begingroup$

A codeword of a cyclic code is usually denoted: $a_0 a_1\ldots a_{n -1}$, and to each such a codeword the polynomial $a_0 + a_1 x_1 + a_2 x_2 + \ldots + a_{n -1} x_{n -1}$ is associated.

  • $\mathbf{F}_q[x]$ denotes the set of all polynomials over $\mathrm{GF}(q)$. $G$ is the generator matrix. $\text{deg}(f(x ))$ = the largest $m$ such that $x_m$ has a non-zero coefficient in $f(x)$.

Multiplication of polynomials:

If $f(x)$, $g(x)$ belong to $\mathbf{F}_q[x]$, then $\text{deg}(f(x) g(x)) = \text{deg}(f(x)) + \text{deg}(g(x))$.

Division of polynomials:

For every pair of polynomials $a(x)$, $b(x)$ different from $0$ in $\mathbf{F}_q[x]$ there exists a unique pair of polynomials $q(x)$, $r(x)$ in $\mathbf{F}_q[x]$ such that $a(x) = q(x)b(x) + r(x), \text{deg}(r(x)) < \text{deg}(b(x))$.

For more information, maybe this document is useful.

$\endgroup$
  • 1
    $\begingroup$ It's not clear how this answers the OP's question. $\endgroup$ – Jason R Mar 14 '16 at 15:35
0
$\begingroup$

The "other method" that you refer to is in the "frequency domain" or transform domain in some sense.

Suppose that $\mathbf C = (C_0, C_1, \cdots, C_{n-1})$ is the codeword under consideration. A cyclic right shift by $m$ places results in the codeword $\hat{\mathbf C} = (C_{n-m}, C_{n-m+1}, \cdots, C_{n-2}, C_{n-1}, C_0, C_1, \cdots, C_{n-m-1})$. As you cogently observe, this shifting is easy to understand and implement etc. Why, then, is the other, more complicated, method taught or used?

Recall that there are many things in DSP that are easy to do in one domain that in the other. Now, the codeword $\mathbf C$, which can thought of as being in the time domain has a corresponding representation as a polynomial $C(x)$ in the transform domain: $$\mathbf C = (C_0, C_1, \cdots, C_{n-1}) \longleftrightarrow C(x) = C_0 + C_1x + \cdots + C_{n-1}x^{n-1}.$$ (Any resemblance to a $z$-transform is strictly unintentional). So, what is the polynomial $\hat{C}(x)$ corresponding to $\hat{\mathbf C}$, the right cyclic shift of $\mathbf C$ by $m$ places? Well, first of all, note that the desired polynomial is \begin{align} \hat{C}(x) = C_{n-m} +C_{n-m+1}x + \cdots + C_{n-1}x^{m-1} + C_0x^m + C_1x^{m+1} \cdots + C_{n-m-1}x^{n-1}.\tag{1} \end{align} Now, note that \begin{align} x^m C(x) &= 0 + 0x + 0x^2 + \cdots + 0x^{m-1}\\ & \qquad + C_0x^m + C_1x^{m+1} + \cdots + C_{n-m-1}x^{n-1}\\ & \qquad\qquad + C_{n-m}x^{n} + C_{n-m+1}x^{n+1} + \cdots + C_{n-2}x^{n+m-2} + C_{n-1}x^{n+m-1} \end{align} which in comparison to $(1)$ has $m$ leading $0$'s, then $C_0$ through $C_{n-m-1}$ in the proper place, and then extra stuff at the high order end. So, how can we massage $x^mC(x)$ to produce $\hat{C}(x)$? Well, adding and subtracting the quantity $C_{n-m} +C_{n-m+1}x + \cdots + C_{n-1}x^{m-1}$ to $x^mC(x)$, we can write \begin{align} x^mC(x) &= \left(C_{n-m} + C_{n-m+1}x + \cdots + C_{n-2}x^{m-2} + C_{n-1}x^{m-1}\right)(x^n-1)\\ & \qquad + C_0x^m + C_1x^{m+1} + \cdots + C_{n-m-1}x^{n-1}\\ & \qquad\qquad + C_{n-m} + C_{n-m+1}x^{1} + \cdots + C_{n-2}x^{m-2} + C_{n-1}x^{m-1}. \end{align} The terms on the second and third lines above are all of degree smaller than $n$, and have all the coefficients in their proper place. We conclude that $$\hat{C}(x) = x^m C(x) \bmod (x^n-1).$$

Thus, as you have noted, cyclic shifts are easy to do in the "time domain" and much harder in the transform domain. Think of it as payback for the fact that convolutions are easy to do in the transform domain and harder in the time domain.

$\endgroup$
  • $\begingroup$ Thanks for the explanation. But I think there is an error. x^m C(x) &= 0 + 0x + 0x^2 + \cdots + 0x^{m-1}\\ & \qquad + C_0x^m + C_1x^{m+1} + \cdots + C_{n-m-1}x^{n-1}\\ & \qquad\qquad + C_{n-m}x^{n} + C_{n-m+1}x^{n+1} + \cdots + C_{n-2}x^{n-m-2} + C_{n-1}x^{n-m-1} \end{align} has to be corrected as x^m C(x) &= 0 + 0x + 0x^2 + \cdots + 0x^{m-1}\\ & \qquad + C_0x^m + C_1x^{m+1} + \cdots + C_{n-m-1}x^{n-1}\\ & \qquad\qquad + C_{n-m}x^{n} + C_{n-m+1}x^{n+1} + \cdots + C_{n-2}x^{n+m-2} + C_{n-1}x^{n+m-1} \end{align} $\endgroup$ – Seetha Rama Raju Sanapala Mar 15 '16 at 11:53
  • $\begingroup$ Sorry. I did not know how to format correctly. $\endgroup$ – Seetha Rama Raju Sanapala Mar 15 '16 at 11:59
  • $\begingroup$ Also instead of taking mod with x^-1, if we take it x^n+1, we will get the same resutl, isn't it, since in GF(2), -1 = 1. $\endgroup$ – Seetha Rama Raju Sanapala Mar 15 '16 at 12:01

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.