CHAPTER-7

Cyclic Codes

7.1 Introduction Cyclic codes are a sub-class of linear block codes, considered to be the most
important class. An advantage of the cyclic codes over the most other types of codes is that they
possess a well-defined mathematical structure that leads to strong correcting capabilities and to
computationally efficient encoding and decoding algorithms. Important sub classes of the cyclic codes
are the binary Bose, Chaudhary and Hocquenghem (BCH) codes and the non-binary Reed Solomon
(RS) codes.

A block code is said to be cyclic if it has following two basic properties:

1. Linearity Property: The sum of any two codewords in the code C is also a codeword in C.

2. Cyclic Property: Any cyclic shift of a code word in the code C is also a codeword in C.

For example, if (𝑐0 , 𝑐1 − − − −, 𝑐𝑛−1 ) is a codeword in C, then (𝑐𝑛−1 , 𝑐0 , 𝑐1 − − − −, 𝑐𝑛−2 )

is also a codeword in C.

A cyclic code can be easily created by performing a ‘right cyclic shift’ on an initial code word,
developing a new codeword with each shift which continues until the original codeword is obtained.
For example
𝐶 = [000, 011, 101, 110]
is an example of a cyclic code.

Code Polynomial

A rich set of properties and structure can be extracted from this simple characteristic of cyclic
shift. The cyclic code properties are best understood by mapping the code word (𝑐0 , 𝑐1 − − − −, 𝑐𝑛−1 )
to a polynomial in the indeterminate 𝑥 , called the code polynomial. The code polynomial using the
elements of the codeword (𝑐0 , 𝑐1 − − − −, 𝑐𝑛−1 ) is

c(𝑥) = 𝑐0 + 𝑐1 𝑥 + 𝑐2 𝑥 2 + 𝑐3 𝑥 3 + − − − − − + 𝑐𝑛−1 𝑥 𝑛−1

Here 𝑥 is an indeterminate and for a binary code the coefficients 𝑐𝑖 are 0 and 1.
For example, mapping the codeword in the code C given above, the corresponding code polynomials,
we are:
{0, 𝑥 + 𝑥 2 , 1 + 𝑥 2 , 1 + 𝑥}

We observe that multiplication of the polynomial c(x) by x may be viewed as a shift to the
right. The key problem is how to make such a shift cyclic.

In order to perform the right circular shift in polynomial form, we use multiplication modulo
corresponding to the code word (𝑐0 , 𝑐1 − − − −, 𝑐𝑛−1 ).

Let the code polynomial c(𝑥) be multiplied by 𝑥 𝑖 , and then we can show that

𝑥 𝑖 𝑐(𝑥) = 𝑞(𝑥)(𝑥 𝑛 + 1) + 𝑐 (𝑖) (𝑥) (7.1)

where 𝑐 (𝑖) (𝑥) is the code polynomial of the codeword (𝑐𝑛−𝑖 , − − −, 𝑐𝑛−1 , 𝑐0 , 𝑐1 − − − −, 𝑐𝑛−𝑖−1 )
obtained by applying 𝑖 right cyclic shifts to the codeword (𝑐0 , 𝑐1 − − − −, 𝑐𝑛−1 )
The equation (7.1) implies that

𝑐 (𝑖) (𝑥) = 𝑥 𝑖 𝑐(𝑥)𝑚𝑜𝑑(𝑥 𝑛 + 1) (7.2)

Thus the code polynomial 𝑐 (𝑖) (𝑥) is simply the remainder resulting from dividing the polynomial
𝑥 𝑖 𝑐(𝑥) 𝑏𝑦 (𝑥 𝑛 + 1) .
The modulo (𝑥 𝑛 + 1) expression is sometimes seen in the literature as modulo (𝑥 𝑛 − 1). In
the binary field both are identical since +1 = −1.
Say we need to apply two right cyclic shifts, we have to a code word 00101. The codeword
00101 has code polynomial 𝑥 2 + 𝑥 4 multiplying it by 𝑥 2

𝑥 2 (𝑥 2 + 𝑥 4 ) = 𝑥 4 + 𝑥 6
5
Dividing algorithm by 𝑥 + 1, we obtain

𝑥 6 +𝑥 4 𝑥+𝑥 4
𝑥 5 +1
= 𝑥 + 𝑥 5 +1
Thus
𝑥 + 𝑥 4 = (𝑥 4 + 𝑥 6 )mod (𝑥 5 + 1)
Hence 𝑐 (2) (𝑥) = 𝑥 + 𝑥 4 . The corresponding codeword is (01001), which is the result of two, right
cyclic shifts to the code word 00101.

We observe that 𝑐 (𝑖) (𝑥) can be obtained from 𝑥 𝑖 𝑐(𝑥) subject to the constraint 𝑥 𝑛 = 1. In the
above example the constraint is 𝑥 5 = 1.

Next, we state a few important algebraic properties of a cyclic code which simplify the
encoding and decoding algorithms. (For proof refer to Error Control Coding: Fundamentals and
Applications by Suline. Daniel J. Costello, Jr. P. H. Series in CA in EE)

𝑷𝟏 : The nonzero code polynomial of minimum degree in a cyclic code C is unique.

𝑷𝟐 : 𝐼𝑓 𝑔(𝑥) = 𝑔0 + 𝑔1 𝑥 + 𝑔𝑟−1 𝑥 𝑟−1 + 𝑥 𝑟 is code polynomial of minimum degree in an (n, k) cyclic

code C, then the constant term g 0 = 1.

Thus 𝑃1 and 𝑃2 imply that ‘The nonzero code polynomial of minimum degree in an (n, k)
cyclic code C is unique and is of the form’.

𝑔(𝑥) = 1 + 𝑔1 𝑥 + 𝑔2 𝑥 𝑟−1 𝑔𝑟−1 𝑥 𝑟−1 + 𝑥 𝑟 . (7.3)

For example for a (7,4) cyclic code given below, the nonzero code polynomial with minimum
degree is 𝑔(𝑥) = 1 + 𝑥 + 𝑥 3
Table 7.1
Messages Code words Code polynomials
0000 0000000 0
1000 1101000 1 + 𝑥 + 𝑥3
0100 0110100 𝑥 + 𝑥2 + 𝑥4
1100 1011100 1 + 𝑥2 + 𝑥3 + 𝑥4
0010 0011010 𝑥2 + 𝑥3 + 𝑥5
1010 1110010 1 + 𝑥 + 𝑥2 + 𝑥5
0110 0101110 𝑥 + 𝑥3 + 𝑥4 + 𝑥5
1110 1000110 1 + 𝑥4 + 𝑥5
0001 0001101 𝑥3 + 𝑥4 + 𝑥6
1001 1100101 1 + 𝑥 + 𝑥4 + 𝑥6
0101 0111001 𝑥 + 𝑥2 + 𝑥3 + 𝑥6
1101 1010001 1 + 𝑥2 + 𝑥6
 0011 0010111 𝑥2 + 𝑥4 + 𝑥5+ 𝑥6
1011 1111111 1 + 𝑥 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5+ 𝑥6
0111 0100011 𝑥 + 𝑥5+ 𝑥6
1111 1001011 1 + 𝑥3 + 𝑥5+ 𝑥6

When 𝑔(𝑥) is given by (7.3) the polynomials 𝑥𝑔(𝑥), 𝑥 2 𝑔(𝑥), − − −, 𝑥 𝑛−𝑟−1 𝑔(𝑥), are of degrees
(r + 1), (r + 2), − − −, (n − 1) respectively. Also from (7.2) 𝑥𝑔(𝑥) = 𝑔(1) (𝑥), 𝑥 2 𝑔(𝑥) = 𝑔(2) (𝑥),
and 𝑥 𝑛−𝑟−1 𝑔(𝑥) = 𝑔(𝑛−𝑟−1) (𝑥). Thus these are cyclic shifts of the code polynomial 𝑔(𝑥) and
therefore, are code polynomials in C.
Since C is a linear block code also, thus combination of 𝑔(𝑥), 𝑥𝑔(𝑥), − − −, 𝑥 𝑛−𝑟−1 𝑔(𝑥),
given by
𝑐(𝑥) = 𝑐0 𝑔(𝑥) + 𝑐1 𝑥𝑔(𝑥) + − − +𝑐 𝑛−𝑟−1 𝑥 𝑛−𝑟−1 𝑔(𝑥),
= (𝑐0 + 𝑐1 𝑥 + − − +𝑐 𝑛−𝑟−1 𝑥 𝑛−𝑟−1 )𝑔(𝑥), (7.4)
where 𝑐𝑖 = 0 𝑜𝑟 1, is also a code polynomial.

𝑷𝟑 : Let 𝑔(𝑥) = 1 + 𝑔1 𝑥 + − − − + 𝑔𝑟−1 𝑥 𝑛−𝑟−1 + 𝑥 𝑟 be the nonzero code polynomial of minimum

degree in an (n, k) cyclic code C. A binary polynomial of degree (n-1) or less is a code polynomial
if, and only if it is a multiple of 𝑔(𝑥).

Now the number of binary polynomials of degree (n-1) or less that are multiple of
𝑔(𝑥) 𝑖𝑠 2𝑛−𝑟 and from 𝑃3 these polynomials will form all the code polynomial of (n, k) cyclic code C
only when 𝑛 − 𝑟 = 𝑘, that is, 𝑟 = 𝑛 = 𝑘. Hence we have the following result:

In an (n, k) cyclic code there exists one and only one code polynomial of degree (n-k),
𝑔(𝑥) = 1 + 𝑔1 𝑥 + 𝑔2 𝑥 2 + − − − + 𝑔𝑛−𝑘−1 𝑥 𝑛−𝑘−1 + 𝑥 𝑛−𝑘 (7.5)
Every code polynomial is a multiple of 𝑔(𝑥)and every binary polynomial of degree (n-k) or less that is
a multiple of 𝑔(𝑥) is a code polynomial.

The Generator Polynomial

We have seen that every code polynomial 𝑐(𝑥) in an (n, k) cyclic code can be expressed in the form
𝑐(𝑥) = 𝑚(𝑥)𝑔(𝑥)
= (𝑚0 + 𝑚1 𝑥 + − − − + 𝑚𝑘−1 𝑥 𝑘−1 )𝑔(𝑥) (7.6)
where 𝑚𝑖 = 0 𝑜𝑟 1.

Now if 𝑚0 , 𝑚1 − − −, 𝑚𝑘−1 are the 𝑘 information digits to be encoded then 𝑐(𝑥) is the
corresponding code polynomial. Hence, an (n, k) cyclic code can be completely specified by its non-
zero code polynomial 𝑔(𝑥) of minimum degree given by (7.5). The polynomial 𝑔(𝑥) is called the
generator polynomial of the code. Its degree is equal to the number of parity-check bits of the code.
Referring to the example of the (7,4) code discussed above in table 7.1, the code polynomials
multiple of 𝑔(𝑥) = 1 + 𝑥 + 𝑥 3 can be represented as follows:

Table 7.2
Code polynomials 𝒄(𝒙) 𝒄(𝒙) = 𝒎(𝒙)𝒈(𝒙)
0 0. 𝑔(𝑥)
1 + 𝑥 + 𝑥3 1. 𝑔(𝑥)
𝑥 + 𝑥2 + 𝑥4 (𝑥). 𝑔(𝑥)
1 + 𝑥2 + 𝑥3 + 𝑥4 (1 + 𝑥). 𝑔(𝑥)
𝑥2 + 𝑥3 + 𝑥5 (𝑥 2 )𝑔(𝑥)
1 + 𝑥 + 𝑥2 + 𝑥5 (1 + 𝑥 2 ). 𝑔(𝑥)
𝑥 + 𝑥3 + 𝑥4 + 𝑥5 (𝑥 + 𝑥 2 ). 𝑔(𝑥)
1 + 𝑥4 + 𝑥5 (1 + 𝑥 + 𝑥 2 ). 𝑔(𝑥)
𝑥3 + 𝑥4 + 𝑥6 𝑥 3 . 𝑔(𝑥)
1 + 𝑥 + 𝑥4 + 𝑥6 (1 + 𝑥 3 ). 𝑔(𝑥)
𝑥 + 𝑥2 + 𝑥3 + 𝑥6 (𝑥 + 𝑥 3 ). 𝑔(𝑥)
1 + 𝑥2 + 𝑥6 (1 + 𝑥 + 𝑥 3 ). 𝑔(𝑥)
𝑥2 + 𝑥4 + 𝑥5+ 𝑥6 (𝑥 2 + 𝑥 3 ). 𝑔(𝑥)
1 + 𝑥 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥 5+ 𝑥6 (1 + 𝑥 2 + 𝑥 3 ). 𝑔(𝑥)
𝑥 + 𝑥5+ 𝑥6 (𝑥 + 𝑥 2 + 𝑥 3 ). 𝑔(𝑥)
1 + 𝑥3 + 𝑥5+ 𝑥6 (1 + 𝑥 + 𝑥 2 + 𝑥 3 ). 𝑔(𝑥)

𝑷𝟒 : The generator polynomial 𝑔(𝑥) of an (n, k) cyclic code is a factor of 𝑥 𝑛 + 1.

An obvious question of interest is: Whether for any n and k, there exists an (n, k) cyclic code?
The answer is: No it is clarified by the following result:
If 𝑔(𝑥) is a polynomial of degree (n, k) and is a factor of 𝑥 𝑛 + 1, then 𝑔(𝑥)generates an (n-k)
cyclic code.

Thus any factor of 𝑥 𝑛 + 1 with degree (n- k) generates an (n, k) cyclic code. For large n,
𝑛
𝑥 + 1 may have more than one factors of degree (n-k). Some of these polynomials generate good
codes and some generate bed code. How to select polynomials generating good codes is a very
difficult problem and has been a problem of interest for the coding theorists.
For example, the polynomial 𝑥 7 + 1 can be factored as follows:
𝑥 7 + 1 = (1 + 𝑥)(1 + 𝑥 + 𝑥 3 )(1 + 𝑥 2 + 𝑥 3 )
There are two factors of degree 3, each generates a (7,4) cyclic code.
The code given in Table (7.1) is generated by 𝑔(𝑥) = 1 + 𝑥 + 𝑥 3 , with 𝑑𝑚𝑖𝑛 = 3, and hence it
is a single-error-correcting code.
If 𝑚 = (1 0 0 1) is the message to be encoded, then the message polynomial is 1 + 𝑥 3 . The
corresponding code polynomial is given by
𝑐(𝑥) = (1 + 𝑥 3 ). 𝑔(𝑥)
= (1 + 𝑥 3 )(1 + 𝑥 + 𝑥 3 )
= 1 + 𝑥 + 𝑥4 + 𝑥6
Hence the code word is ( 1 1 0 0 1 0 1), as can be verified from the Table 7.1

Systematic cyclic code

We observe that the (7,4) code generated by the polynomial 𝑔(𝑥) = (1 + 𝑥 2 + 𝑥 3 ), as given
in Table (7.1), is not in systematic form. However, given the generator polynomial 𝑔(𝑥) of an (n, k)
cyclic code, the same generator can be used to design a systematic form of the code word polynomials.
We know that a code polynomial is a multiple of 𝑔(𝑥), and thus, division of a code polynomial by
𝑔(𝑥) yields a quotient equal to the message 𝑚(𝑥) and a zero remainder. In general, if a polynomial
𝑐(𝑥) is divided by a polynomial 𝑔(𝑥) then remainder must be a polynomial of degree less than or
equal to (n-k-1).
We can encode a message polynomial 𝑚(𝑥) into systematic code word polynomial by first
multiplying 𝑚(𝑥) by 𝑥 𝑛−𝑘 and than dividing by 𝑔(𝑥). If 𝑎(𝑥) and 𝑏(𝑥) are respectively the quotient
and the remainder, then by Euclidian division algorithm
𝑥 𝑛−𝑘 𝑚(𝑥) = 𝑎(𝑥)𝑔(𝑥) + 𝑏(𝑥) (7.7)
How the b(𝑥) must be of the form
𝑏(𝑥) + 𝑏0 + 𝑏1 𝑥 + − − − + 𝑏𝑛−𝑘−1 𝑥 𝑛−𝑘−1 (7.8)
Adding 𝑏(𝑥) to both sides of (7.7) and we obtain
𝑏(𝑥) + 𝑥 𝑛−𝑘 𝑚(𝑥) = 𝑎(𝑥)𝑔(𝑥) (7.9)
We observe that 𝑟. ℎ. 𝑠. of (7.9), is polynomial of degree (n-1) or less. Being a multiple of 𝑔(𝑥) it is
code polynomial of the cyclic code (n, k) generated by 𝑔(𝑥) , and is given by

𝑎(𝑥)𝑔(𝑥) = 𝑏0 + 𝑏1 𝑥 + − − − + 𝑏𝑛−𝑘−1 𝑥 𝑛−𝑘−1 + 𝑥 𝑛−𝑘 (𝑚0 + 𝑚1 + − − − + 𝑚𝑘−1 )

 = 𝑏0 + 𝑏1 𝑥 + − − − + 𝑏𝑛−𝑘−1 𝑥 𝑛−𝑘−1 + 𝑚0 𝑥 𝑛−𝑘 + 𝑚1 𝑥 𝑛−𝑘+1 + − − +𝑚𝑘−1 𝑥 𝑛−1

This corresponds to the systematic code vector

(𝑏0 , 𝑏1 − −, 𝑏𝑛−𝑘−1 , 𝑚0 + 𝑚1 + − − − + 𝑚𝑘−1 )
How the first (n-k) symbols are parity –check bits and the next k symbols are the message bits. The (n-
k) parity bits are simply the coefficients of the remainder polynomial obtained from the division of
𝑥 𝑛−𝑘 𝑚(𝑥) by the generator polynomial 𝑔(𝑥).

Thus encoding of an (n, k) cyclic systematic code consists of the following three steps:
I. Multiply the message polynomial 𝑚(𝑥) by 𝑥 𝑛−𝑘 .
II. Divide 𝑥 𝑛−𝑘 𝑚(𝑥) by the generator polynomial 𝑔(𝑥) and obtain the remainder
polynomial 𝑏(𝑥).
III. Add 𝑏(𝑥) to 𝑥 𝑛−𝑘 𝑚(𝑥) to obtain the code polynomial 𝑏(𝑥) + 𝑥 𝑛−𝑘 𝑚(𝑥) .
Example7.1

Consider the (7,4) code generated by the polynomial 𝑔(𝑥) = (1 + 𝑥 + 𝑥 3 ). Let 𝑚(𝑥) = 1 + 𝑥 be the
message polynomial to be encoded.
Divide 𝑥 3 𝑚(𝑥) = 𝑥 3 + 𝑥 4 by 𝑔(𝑥), we have
𝑥 4 + 𝑥 3 = (𝑥 3 + 1)𝑔(𝑥) + (𝑥 2 + 1)

Thus 𝑏(𝑥) = 𝑥 2 + 1, and hence the code polynomial is

𝑏(𝑥) + 𝑥 𝑛−𝑘 𝑚(𝑥) = (1 + 𝑥 2 ) + 𝑥 3 (1 + 𝑥)
= 1 + 𝑥2 + 𝑥3 + 𝑥4
Thus the corresponding codeword is (1 0 1 1 1 0 0)
We observe that four right most bits 1 1 0 0 are the message bits and the three left most bits 1 0 1
are the parity-check bits.

Generator Matrix of cyclic codes

In the preceding section we have seen that in case of an (n, k) cyclic code C with generator
polynomial 𝑔(𝑥) = 𝑔0 + 𝑔1 𝑥 + 𝑔2 𝑥 2 + − − − + 𝑔𝑛−𝑘 𝑥 𝑛−𝑘 , the 𝑘 code polynomials
𝑔(𝑥), 𝑥𝑔(𝑥), − − −, 𝑥 𝑘−1 𝑔(𝑥) span C. If the 𝑘 code vectors corresponding to these k code
polynomials are used as the row vectors of a 𝑘 × 𝑛 matrix, we obtain the generator matrix for the
cyclic code C given by

𝑔0 𝑔1 𝑔2 − − − 𝑔𝑛−𝑘 0 0 − − − 0
0 𝑔0 𝑔1 𝑔2 − − − 𝑔𝑛−𝑘 0 − − − 0
𝐺 = 0 0 𝑔0 𝑔1 𝑔2 − − − 𝑔𝑛−𝑘 − − − 0
: ∶ ∶
[0 0 − − − 0 𝑔1 𝑔2 − − − − − 𝑔𝑛−𝑘 ]
Hence 𝑔 0 = 𝑔𝑔−𝑘 = 1
In general G is not in systematic form but can be put into systematic form using row operations.
For the (7.4) code given in Table 7.1 with generator polynomial 𝑔(𝑥) = 1 + 𝑥 + 𝑥 3 , the
generator matrix G is given by

1 1 0 1 0 0 0
0 1 1 0 1 0 0
𝐺=[ ]
0 0 1 1 0 1 0
0 0 0 1 1 0 1 4×7
Obviously G is not in systematic form. Applying the elementary row operations 𝑅3 → 𝑅1 + 𝑅3 and
𝑅4 → 𝑅1 + 𝑅2 + 𝑅4 the resultant generator matrix.

1 1 0 1 0 0 0
0 1 1 0 1 0 0
𝐺=[ ] = [𝑃: 𝐼4 ]
1 1 1 0 0 1 0
1 0 1 0 0 0 1

is in the systematic form. Here the sub matrix P is the parity-check matrix and thus sub matrix 𝐼4 is
the identity matrix of order 4 × 4. We must note that the generates matrix 𝐺 ′ generator the same code
as generated by G. In general, as incase of linear block code, the desired cyclic code can be obtained
by the matrix equation 𝑐 = 𝑚𝐺
Where 𝑐 = (𝑐0 , 𝑐1 , − − −, 𝑐𝑛−1 )the code vector and 𝑚 = (𝑚0 , − − −, 𝑚𝑘−1 ) is the message
vector and 𝐺 = [𝑃: 𝐼𝑘 ]𝑘×𝑛 is the generator matrix.

Parity-check Matrix

We know that the generator polynomial of an (n, k) code divides 𝑥 𝑛 + 1, and say
𝑥 𝑛 + 1 = 𝑔(𝑥)ℎ(𝑥) (7.10)
where ℎ(𝑥) is the polynomial of the form
ℎ(𝑥) = ℎ0 + ℎ1 𝑥 + ℎ2 𝑥 2 + − − − + ℎ𝑘 𝑥 𝑘 (7.11)
with ℎ0 = ℎ𝑘 = 1.
Next, let 𝒄 = (𝑐0 , 𝑐1 , − − −, 𝑐𝑛−1 ) be a code vector in the cyclic code C with the code
polynomial 𝑐(𝑥), then 𝑐(𝑥) = 𝑚(𝑥)𝑔(𝑥). This gives
𝑐(𝑥)ℎ(𝑥) = 𝑚(𝑥)𝑔(𝑥)ℎ(𝑥)
= 𝑚(𝑥)(𝑥 𝑛 + 1)
= 𝑚(𝑥) + 𝑥 𝑛 𝑚(𝑥), (7.12)
where the degree of 𝑚(𝑥) is less than or equal to 𝑘 − 1. Thus the expression on the 𝑟. ℎ. 𝑠.. of (7.12)
does not consist of the powers 𝑥 𝑘 , 𝑥 𝑘+1 , − − −−, 𝑥 𝑛−1 . hence the coefficients of these terms, in the
expansion of the 𝑙. ℎ. 𝑠. in powers of x, must be zeros, that is,
∑𝑘𝑖=0 ℎ𝑖 𝑐𝑛−𝑖−𝑗 = 0, for 1 ≤ 𝑗 ≤ 𝑛 − 𝑘 (7.13)
Next, we define reciprocal of ℎ(𝑥) as
𝑥 𝑘 ℎ(𝑥 −1 ) = ℎ𝑘 + ℎ𝑘−1 𝑥 + ℎ𝑘−2 𝑥 2 + − − − + ℎ𝑥 𝑘 (7.14)
Also from (7.10)
1 + 𝑥 𝑛 = 𝑥 𝑛 𝑔(𝑥 −1 )ℎ(𝑥 −1 )
= 𝑥 𝑛−𝑘 𝑔(𝑥 −1 )𝑥 𝑘 ℎ(𝑥 −1 ).
Since the expression 𝑥 𝑛−𝑘 𝑔(𝑥 −1 ) is also a polynomial, thus the reciprocal polynomial 𝑥 𝑘 ℎ(𝑥 −1 ) is
also a factor of 𝑥 𝑛 + 1. The polynomial 𝑥 𝑘 ℎ(𝑥 −1 ) generates an (𝑛, 𝑛 − 𝑘) cyclic code with the
generator matrix of the order (𝑛 − 𝑘) × 𝑛 given by
ℎ𝑘 ℎ𝑘−1 ℎ𝑘−2 − − − ℎ0 0 − − − 0
0 ℎ𝑘 ℎ𝑘−1 ℎ𝑘−2 − − − ℎ0 0 − −0
𝐻 = 0 0 ℎ𝑘 ℎ𝑘−1 ℎ𝑘−2 − − − ℎ0 − − 0
: ∶
[0 0 − − − − − 0 ℎ𝑘 ℎ𝑘−1 − − − ℎ0 ]𝑛−𝑘×𝑛
From the set of equations (7.13), it follows that any code vector c in C is orthogonal to every row of H.
Therefore H is a parity-check matrix of the cyclic code C. The cyclic code 𝐶′ generated by H is a dual
to the cyclic code C and is denoted by 𝐶 ⊥ . The polynomial ℎ(𝑥) is called the parity polynomial of 𝐶.
Thus we have the following result:
Let C be an (n, k) cyclic code with generator polynomial 𝑔(𝑥). The dual code 𝐶 ⊥ of C is also cyclic
and is generated by the polynomial 𝑥 𝑘 ℎ(𝑥 −1 ), where ℎ(𝑥) = (𝑥 𝑛 + 1)/𝑔(𝑥).
For example, in case of a (7,4) cyclic code generated by the code polynomial 𝑔(𝑥) = 1 + 𝑥 +
3
𝑥 , the parity polynomial ℎ(𝑥) is given by
ℎ(𝑥) = (𝑥 7 + 1)/(1 + 𝑥 + 𝑥 3 ) = 1 + 𝑥 + 𝑥 2 + 𝑥 4 .
The reciprocal of ℎ(𝑥) is
𝑥 4 ℎ(𝑥 −1 ) = 𝑥 4 (1 + 𝑥 −1 + 𝑥 −2 + 𝑥 −4 )
= 𝑥 4 + 𝑥 3 + 𝑥 2 + 1.

We have 𝑥 7 + 1 = (𝑥 4 + 𝑥 3 +𝑥 2 + 1)(𝑥 3 +𝑥 2 + 1)

Thus 𝑥 4 ℎ(𝑥 −1 ) divides 𝑥 7 + 1, hence the parity check matrix H is given by

1 0 1 1 1 0 0
𝐻 = [0 1 0 1 1 1 0]
0 0 1 0 1 1 1 3×7
The following table gives the (7,3) cyclic code 𝐶 ⊥ generated by H.

Table (7.3)
Messages word(m) Code words 𝒄(𝒙) = 𝒎(𝒙)𝒉(𝒙)
0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 1 1 1 0 0
0 1 0 0 1 0 1 1 1 0
0 0 1 0 0 1 0 1 1 1
1 1 0 1 1 1 0 0 1 0
1 0 1 1 0 0 1 0 1 1
0 1 1 0 1 1 1 0 0 1
1 1 1 1 1 0 0 1 0 1

We can check that any code word c given in Table 7.3 is orthogonal to any code word in 𝐶 ⊥ given in
Table 7.1. Also we note that here 𝑑𝑚𝑖𝑛 = 𝑤𝑚𝑖𝑛 = 4. Thus the dual code is single error correcting and
doble error detecting code.

Generator Matrix in Systematic Form

This can be obtained as follows:
Dividing 𝑥 𝑛−𝑘−𝑖 by the generator polynomial 𝑔(𝑥) we obtain
𝑥 𝑛−𝑘−𝑖 = 𝑞𝑖 (𝑥)𝑔(𝑥) + 𝑏𝑖 (𝑥), 𝑖 = 0,1, − − −, 𝑘 − 1. (7.15)
where
𝑏𝑖 (𝑥) = 𝑏𝑖0 + 𝑏𝑖1 (𝑥), + − − − +𝑏𝑥 𝑛−𝑘−1
is the remainder polynomial.
Adding 𝑏𝑖 (𝑥) to both sides of (7.15), we obtain
𝑏𝑖 (𝑥) + 𝑥 𝑛−𝑘−𝑖 = 𝑞𝑖 (𝑥)𝑔(𝑥), 𝑖 = 0,1,2, − − −, 𝑘 − 1. (7.16)
𝑛−𝑘−𝑖
The set of equations (7.16) imply that 𝑏𝑖 (𝑥) + 𝑥 , being multiple of 𝑔(𝑥), are code polynomials.
Arranging these 𝑘 code polynomials as the row vectors of a 𝑘 × 𝑛 matrix, we obtain the generator
matrix G in the systematic form given by
 𝑏00 𝑏01 𝑏02 − − − 𝑏0,𝑛−𝑘−1 1 0 0−−−0
𝑏10 𝑏11 𝑏12 − − − 𝑏1,𝑛−𝑘−1 0 1 0−−−0
𝐺 = 𝑏20 𝑏21 𝑏22 − − − 𝑏2,𝑛−𝑘−1 0 0 1−−−0 = [𝑃: 𝐼𝑘 ]
: ∶
𝑏𝑘−1,0 𝑏𝑘−1,1 𝑏𝑘−2,2 − − − 𝑏𝑘−1,𝑛−𝑘−1 0 0 0 − − − 1
[ ]𝑘×𝑛
The corresponding parity check matrix is for the cyclic code C is

1 0 0 − − − 0 𝑏00 𝑏10 𝑏20 − − − − − 𝑏𝑘−1,0

0 1 0 − − − 0 𝑏01 𝑏11 𝑏21 − − − − − 𝑏𝑘−1,1
𝐻 = 0 0 1 − − − 0 𝑏02 𝑏12 𝑏22 ∶
: ∶
[0 0 0 − − − 1 𝑏0,𝑛−𝑘−1 𝑏1,𝑛−𝑘−1 𝑏2,𝑛−𝑘− − − − 𝑏𝑘−1,𝑛−𝑘−1 ]

As an example consider the (7, 4) cyclic code as given as in Table 7.1. Here generating polynomial is
𝑔(𝑥) = 1 + 𝑥 + 𝑥 3 .
Dividing 𝑥 3 , 𝑥 4 , 𝑥 5 𝑎𝑛𝑑 𝑥 6 𝑏𝑦 𝑔(𝑥) we obtain
𝑥 3 = 𝑔(𝑥)(1 + 𝑥)
𝑥 4 = 𝑥𝑔(𝑥) + (𝑥 + 𝑥 2 )
𝑥 5 = (𝑥 2 + 1)𝑔(𝑥) + (1 + 𝑥 + 𝑥 2 )
𝑥 6 = (𝑥 3 + 𝑥 2 + 1)𝑔(𝑥) + (1 + 𝑥 2 )
Thus the four code polynomials, refer ( ), are
𝐶0 (𝑥) = 1 + 𝑥 + 𝑥 3
𝐶1 (𝑥) = 1 + 𝑥 2 + 𝑥 4
𝐶2 (𝑥) = 1 + 𝑥 + 𝑥 2 + 𝑥 5
𝐶3 (𝑥) = 1 + 𝑥 2 + 𝑥 6
Taking these as the four row vectors of a 4 × 7 matrix we obtain the generator matrix in systematic
form given by

1 1 0 1 0 0 0
0 1 1 0 1 0 0
𝐺=[ ]
1 1 1 0 0 1 0
1 0 1 0 0 0 1

which is the same as obtained in ( ).

Syndrome Decoding of Cyclic Codes

Suppose that a code vector 𝐶 = (𝑐0 , − − −, 𝑐𝑛−1 ) is transmitted over a noisy channel and it is
received as 𝑟 = (𝑟0 , 𝑟1 , − − −, 𝑟𝑛−1 ). Because of the channel noise, the received vector 𝑟 may not be
the same as the transmitted code vector 𝑐. So, as a first step, we compute the syndrome 𝑠 = 𝑟𝐻 𝑇 ,
where H is the parity check matrix. If the syndrome is a null vector, then the received vector 𝑟 is a
code vector. In case 𝑠 is non-zero, then 𝑟 is not a code vector and the presence of error is detected.
For a systematic cyclic code, the syndrome can be computed easily. The received vector 𝑟 can
be represented by a polynomial 𝑟(𝑥) of degree (𝑛 − 1) or less given by 𝑟(𝑥) = (𝑟0 + 𝑟1 𝑥 +
− − − + 𝑟𝑛−1 𝑥 𝑛−1 )
If 𝑞(𝑥) and 𝑠(𝑥) respectively are the quotient and the remainder when 𝑟(𝑥) is divided by the
generator polynomial 𝑔(𝑥), then by division algorithm
 𝑟(𝑥) = 𝑞(𝑥)𝑔(𝑥) + 𝑠(𝑥) (7.17)
The remainder 𝑠(𝑥), which is a polynomial of degree (n-k-1) or less is called the syndrome
polynomial. The (n-k) coefficients of 𝑟(𝑥) form the syndrome S. Obviously 𝑠(𝑥) will be a zero
polynomial if, and only if 𝑠(𝑥) is a code polynomial.
Because of the cyclic characteristics of the code, the syndrome (polynomial) 𝑠(𝑥) has the
following properties which are useful in decoding and error correction of the cyclic codes.

1. The syndrome of a received vector polynomial is also the syndrome of the corresponding error
polynomial.
Let 𝑟(𝑥) = 𝑐(𝑥) + 𝑒(𝑥) (7.18)
where 𝑟(𝑥)the transmitted code word polynomial and 𝑒(𝑥) is the error polynomial.
Adding 𝑐(𝑥) to both sides of (7.18), we obtain
𝑒(𝑥) = 𝑐(𝑥) + 𝑟(𝑥) (7.19)
Also
𝑐(𝑥) = 𝑎(𝑥)𝑔(𝑥) (7.20)
Using (7.17) and (7.18) in (7.19) we obtain
𝑒(𝑥) = 𝑢(𝑥)𝑔(𝑥) + 𝑠(𝑥) (7.21)
where 𝑢(𝑥) = 𝑎(𝑥) + 𝑞(𝑥)
From (7.21), it is evident that 𝑠(𝑥) is also the syndrome of the error polynomial 𝑒(𝑥).

2. If 𝑠(𝑥) is the syndrome of a received code vector polynomial 𝑟(𝑥), then the syndrome of
𝑥 𝑖 𝑟(𝑥), an 𝑖-cyclic shift of 𝑟(𝑥), is 𝑥 𝑖 𝑠(𝑥).
Multiplying both sides of (7.17) by 𝑥 𝑖 , we obtain
𝑥 𝑖 𝑟(𝑥) = 𝑥 𝑖 𝑞(𝑥)𝑔(𝑥) + 𝑥 𝑖 𝑠(𝑥)
= 𝑞 ′ (𝑥)𝑔(𝑥) + 𝑥 𝑖 𝑠(𝑥) (7.22)
′ (𝑥) 𝑖
𝑤ℎ𝑒𝑟𝑒 𝑞 = 𝑥 𝑞(𝑥)
From (7.22), it is evident that 𝑥 𝑖 𝑠(𝑥) is the syndrome of 𝑥 𝑖 𝑟(𝑥).

3. If the errors are confined to the (n-k) parity-check bits of the received vector polynomial 𝑟(𝑥),
then the syndrome polynomial 𝑠(𝑥) is the same as the error polynomial 𝑒(𝑥).

In case errors are confined to the (n-k) parity-check bits, then the degree of the error
polynomial e(𝑥), is less than or equal to (n-k-1). Since the generator polynomial 𝑔(𝑥) is of degree n-k,
thus Eq (7.21) is satisfied only if 𝑢(𝑥) = 0, which gives 𝑒(𝑥) = 𝑠(𝑥).
Thus in case the error is confined only to the parity check bits, then the received vector can be
corrected simply by adding syndrome to it.
From the above properties we conclude that the syndrome can be computed from the received
vector. In fact, it is equal to the remainder resulting from dividing the error pattern by the generator
polynomial. Since the error pattern 𝑒(𝑥)is unknown to the decoder, therefore, the decoder has to
estimate 𝑒(𝑥) based on the syndrome 𝑠(𝑥). If 𝑒(𝑥) is a coset leader in the standard array, then 𝑒(𝑥)
can be correctly determined from the syndrome.
As example, again consider the decoding of (7,4) cyclic code generated by the polynomial
𝑔(𝑥) = 1 + 𝑥 + 𝑥 3 . Here 𝑑𝑚𝑖𝑛 = 3 and the code is single error correcting code. The possible error
patterns are:
0000000, 1000000, 0100000, 0010000, 0001000, 0000100, 0000010 and 0000001.
 The syndromes for the various error patterns can be computed using Eq (7.21) Table 7.4 given
below lists the various error patterns and their respective syndromes.

Table 7.4
Error pattern, 𝒆(𝒙) Syndrome, 𝒔(𝒙)
1 1 , since 1 = 0. 𝑔(𝑥) + 1
𝑥2 𝑥 2
, since 𝑥 = 0. 𝑔(𝑥) + 𝑥
𝑥3 1+𝑥 , since 𝑥 2 = 0. 𝑔(𝑥) + 𝑥 2
𝑥4 𝑥 + 𝑥2 , since 𝑥 3 = 0. 𝑔(𝑥) + (1 + 𝑥)
𝑥5 1 + 𝑥 + 𝑥 , since 𝑥 5 = (𝑥 2 + 1)𝑔(𝑥) + (1 + 𝑥 + 𝑥 2 )
2

𝑥6 1 + 𝑥2 , since 𝑥 6 = (𝑥 3 + 𝑥 + 1)𝑔(𝑥) + (1 + 𝑥 2 )

The Table 7.4 corresponds to the Table 6. as in case of linear block code.
Next, let us suppose that a vector 0 1 1 1 1 0 0 has been received at the receiver. Therefore
𝑟(𝑥) = 𝑥 + 𝑥 2 + 𝑥 3 + 𝑥 4
We have
𝑥 + 𝑥 2 + 𝑥 3 + 𝑥 4 = (1 + 𝑥)𝑔(𝑥) + (1 + 𝑥)
𝑠(𝑥) = 1 + 𝑥. Hence the received vector is not a code vector. Syndrome vector is (1 1 0),
Thus therefore the error pattern is 0 0 0 1 0 0 0, and hence the code vector is
0 1 1 1 1 0 0 + 0 0 0 1 0 0 0 = 0 1 1 0 1 0 0.

Burst Error Detection

On memory less channels the noise affects each transmitted symbol independently and hence
transmission errors occur randomly in the received sequence for example in case of a binary
symmetric channel with transition probability p. Incase of channels with memory, the noise effect is
not independent from transmission to transmission. For example the channel model may contain two
states, a good state in which probability transmission errors occur rarely, that is, 𝑝 ≃ 0, and a bad state
in which transmission errors are highly probable, that is, 𝑝 ≃ 0.5 and the channel occasionally shifts
to the ‘bad state’ and as a result, transmission errors occur in cluster or bursts because of high
transition probability, e.g. mobile communications channels are burst-error channels. The codes
devised for correcting burst errors are called burst-error-correcting codes. The cyclic codes are very
effective for burst-error detection.
A burst of length 𝑡 is defined as a vector whose non-zero components is confined to 𝑡
consecutive digit positions, the first and last of which are non-zero. For example the error vector 𝑒 =
(0 0 0 1 0 1 1 1 0 1 0 1 0 0 0) is a burst of length q. A linear code that is capable of correcting all
error bursts up to length 𝑡 or less is called 𝑡 − 𝑏𝑢𝑟𝑠𝑡𝑠 − 𝑒𝑟𝑟𝑜𝑟 − 𝑐𝑜𝑟𝑟𝑒𝑐𝑡𝑖𝑛𝑔 𝑐𝑜𝑑𝑒.
Now we consider the error-detecting capability of an (n, k) cyclic code. Suppose that the error
pattern 𝑒(𝑥) is a burst of length (n-k) or less, then 𝑒(𝑥) can be described as
𝑒(𝑥) = 𝑥 𝑖 𝑏(𝑥)
where 0 ≤ 𝑖 ≤ 𝑛 − 1 and 𝑙(𝑥) is a polynomial of degree 𝑛 − 𝑘 − 1 or less. Since the degree of 𝑏(𝑥) is
less than the degree of 𝑔(𝑥), thus 𝑏(𝑥) is not divisible by 𝑔(𝑥). Since 𝑔(𝑥)is a factor of 𝑥 𝑛 + 1and 𝑥
is not a factor of 𝑔(𝑥), thus 𝑔(𝑥)and 𝑥 𝑖 are relatively prime. Therefore 𝑒(𝑥) = 𝑥 𝑖 𝑏(𝑥) is not divisible
by 𝑔(𝑥) and hence the remainder (syndrome) obtained by dividing 𝑒(𝑥) by 𝑔(𝑥) is nonzero. Thus an
(n, k) cyclic code is capable of detecting any error burst of length (n-k) or less. Also we must note that
for a cyclic code, an error pattern with errors confined to 𝑙 low-order positions and 𝑡 − 𝑙 high-order
positions is also considered as a burst of length 𝑡. Such a burst is called end-around burst.
For example
 𝑒 = (1 0 1 1 0 0 0 0 0 0 1 0 0 1 1 )
is an end-around burst of length q.

An (n, k) cyclic code is also capable of detecting all the end-around error bursts of length (n-k)
or less. In fact, a large percentage of error bursts of length (n-k+1) or longer can be detected.
As an example, the (7, 4) cyclic code generated by 𝑔(𝑥) = 1 + 𝑥 + 𝑥 2 has 𝑑𝑚𝑖𝑛 = 3. It is
capable of correcting one error, detecting any combination of two or less random errors or any burst-
error up to length 3. However, it may also detect many burst-errors of length greater than 3.

Exercise

Generate the (7, 4) code by the generator polynomial 𝑔(𝑥) = (1 + 𝑥 2 + 𝑥 3 )

Enlist all the (7.4) systematic cyclic code word when the generator polynomial is 𝑔(𝑥) = 1 + 𝑥 + 𝑥 3

1. Construct a systematic (7,4) cyclic code generated by1 + 𝑥 + 𝑥 3 . Also find the codeword for
1001.
2. Is (5,2) a linear block code with generator matrix

1 0 1 1 1
G=
0 1 1 0 1
cyclic?
3. Discuss encoding and decoding of (1,0,1,0) for a (7,4) systematic cyclic code.
4. Find all binary cyclic codes of length 3.