CYCLIC CODE

3.1- CHARACTERISTICS OF CYCLIC CODES

 In dealing with cyclic codes, it is convenient to associate with a code word C = [c_n-1 c_n-2 . . . c₁ c₀] a polynomial C(x) of degree ≤ n-1, defined as

                        C(x) = c_n-1 x ^n-1 + c_n-2 x ^n-2 +  . . . +c₁ x + c₀                   (3.1)             

For a binary code, each of the coefficients of the polynomial is either zero or one.

Now suppose we form the polynomial

x C(x) = c_n-1 x ⁿ + c_n-2 x ^n-1 +  . . . + c₁ x ² + c₀ x                (3.2)

This polynomial cannot represent a code word, since its degree may be equal to n (when c_n-1 = 1). However, if we divide x C(x) by  x ⁿ + 1, we obtain

x C(x) / ( x ⁿ + 1) = c_n-1 + C₁(x) / (x ⁿ + 1)                    (3.3)

where

                   C₁(x) = c_n-2 x ^n-1 + c_n-3 x ^n-2 + . . . + c₀ x+ c_n-1                   (3.4)                                   

Which represents the code word C₁₌ [c_n-2 c_n-3 . . . c₀ c_n-1], which is just the code word C shifted cyclicly by one position.

Since C₁(x) is the remainder obtained by dividing x C(x) by xⁿ + 1, we say that

                   C₁(x) = x C(x) mod (x ⁿ + l)                               (3.5)

In a similar manner, if C(x) represents a code word in a cyclic code, then

x ⁱ C(x) mod (x ⁿ + 1) is also a code word of the cyclic code. Thus we may write.         

               x ⁱ C(x) = Q(x) (x ⁿ +1) +C_i(x)                      (3.6) 

Where the remainder polynomial C_i(x) represents a code word of the cyclic code and Q(x) is the quotient.

We can generate a cyclic code by using a generator polynomial g(x) of degree n - k. The generator polynomial of an (n, k) cyclic code is a factor of x ⁿ + 1 and has the general form

                      g(x) =  x ^n-k + g_n-k-1 x ^n-k-1 + . . . + g₁ x+ 1                    (3.7)

We also define a message polynomial D(x) as

                    D (x) = d_k-1 x ^k-1 + d_k-2 x ^k-2 + . . . + d₁ x + d₀                              (3.8)

Where [d_k-1 d_k-2 . . . d₁ d₀] represent the k information bits. Clearly, the product D(x) g(x) is a polynomial of degree less than or equal to n - 1, which may represent a code word. We note that there are 2 ^k polynomials and, hence, there are 2 ^k possible code words that can be formed from a given g(x).

Suppose we denote these code words as

                        C_m(x) =D_m(x) g(x).         m= 1, 2, . . . , 2 ^k                        (3.9)

To show that the code words in above Equation satisfy the cyclic property, consider any code word C(x) in above Equation. A cyclic shift of C(x) produces

                      C₁(x) = x C (x) + c_n-1(x ⁿ +1)                            (3.10)

 and, since g(x) divides both x ⁿ + 1 and C(x). It also divides C₁(x);

i.e., C₁(x) can be represented as

                 C₁(x) = x₁(x) g(x)                                     (3.11)

Therefore, a cyclic shift of any code word C(x) generated by Equation (3.9) yields another code word.

From the above, we see that code words possessing the cyclic property can be generated by multiplying the 2^k message polynomials with a unique polynomial g(x), called the generator polynomial of the (n, k) cyclic code, which divides x ⁿ+ 1 and has degree (n- k).