Code Word Polynomial , cyclic codes in digital electronics , Definition , Linearity Property , Cyclic Property :-
CYCLIC CODES
Definition
Cyclic codes are also linear block codes. Infact many important linear block codes are cyclic codes. A binary code is said to be a cyclic code if it exhibits the following properties :
(i) Linearity Property
(ii) Cyclic Property
(i) Linearity Property
A code is said to be linear if sum of any two code words also is a code word. This property states that the cyclic codes are linear block codes.
(ii) Cyclic Property
A code is said to be cyclic if any cyclic shift of a code word results in the formation of another code word. This is shown in figure 10.30. Let (x0, x1, ….,xn-1) be an n-bit (n, k) linear block codes. This code is shifted right by 1 bit everytime in order to get the other codewords as shown in figure 10.30. All the n bit words obtained by the circular right shifting are new code words. This is called as the cyclic property of the cyclic codes.
DIAGRAM
FIGURE 10.30 Illustration of cyclic property of the cyclic codes.
10.14.1. Code Word Polynomial
The cyclic property discussed earlier suggests that it is possible to treat the elements of code word of length n as the coefficients of a polynomial of a degree (n – 1). Thus, the code word :
[x0, x1, x2, …, xn-1]
can be expressed in the form of a code word polynomial as under:
[X(p) = x0 + x1 p + x2 p2 + … + xn-1 pn-1]
where p = An arbitrary real variable.
Some important conclusions from the code word polynomial of equation (10.29) are as under :
(i) For binary codes, the coefficients p, p2 … are l’s and 0s.
(ii) Each power of p in the polynomial X(p) represents a one bit cyclic shift in time. Thus multiplication of the polynomial X(p) by p is equivalent to a cyclic shift or rotation to right provided that pn = 1.
(iii) This special type of polynomial multiplication is known as Multiplication modulo pn – 1. Thus if the polynomial X(p) is given as :
X(p) = x0 + x1 p + x2 p2 + … + xn-1 pn-1
then a single cyclic shift can be obtained by multiplying X(p) by p i.e.,
p X(p) mod (pn-1) = xn-1 + x0 p + x1 p2 + …xn-2 pn-1 … (10.30)
where mod is the abbreviation for modulo. The code word polynomial of equation (10.30) is nothing else but the polynomial representation of the code word (xn -1, x0, xl, xn -2).
(iv) In order to have two cyclic shifts, we must multiply X(p) by p2 i.e.
p2 X(p) mod (pn-1) = xn-2 + xn-1 p + … + xn-3 pn-1
This polynomial represents the code word (xn-2, xn-1, x0 …, xn-3)
Thus, each shifted word represents a different code word.
10.14.2. Generator Polynomial for the Cyclic Code
The generator polynomial of cyclic code is represented by G(D). It is used for the generation of cyclic code words, from the message bits. The generation of code word polynomial can be represented as under:
X(p) = M(p) . G(p) … (10.31)
where M(p) = Message signal polynomial of degree ≤ k
G(p) = Generating polynomial of degree (n — k), which is given by,
G(p) = 1+ g1 p + g2 p2 +…+ gn-k-1 pn-k-1 + pn-k …(10.33)
The generator polynomial can be expressed in the summation form as under:
equation
This expression is quite useful while realizing the encoder for the cyclic codes. The other important point about the generator polynomial is that the degree of generator polynomial is equal to the number of parity bits (check bits) in the code word.
10.14.3. Generation of Non-systematic Code Words
The non-systematic code words can be obtained by multiplication of message polynomial with the generator polynomial as under :
X1(p) = M1(p) . G(p)
X2(p) = M2(p) . G(p)
X3(p) = M3(p) . G(p) … and so on.
10.14.4. Generation of Systematic Code Words
There are three steps involved in the encoding process for a systematic (n, k) cyclic code. They are as under :
(i) We multiply the message polynomial M(p) by pn- k to get pn- k M(p)
This multiplication is equivalent to shifting the message bits by (n – h) bits.
(ii) We divide the shifted message polynomial pn-k M(p) by the generator polynomial G(p) to obtain the remainder C(p).
equation
where Q(p) = Quotient. Note that all the additions are modulo – 2 additions.
(iii) We add the remainder polynomial C(p) to the shifted message polynomial pn- k M(p) to obtain the code word polynomial X(p).
Therefore, code word polynomial X(p) = [pn-k M(p)] Å C(p) … (10.35)
Therefore, the code word polynomial X(p) is exactly divisible by the generator polynomial G(p).
EXAMPLE 10.19. The generator polynomial for a (7.4) cyclic Hamming code is given by,
G(p) = 1 + p + p3
Determine all the systematic and non-systematic code vectors.
Solution : First, let us obtain the non-systematic code vectors.
(i) This is a (7, 4) cyclic Hamming code. Therefore, the message vectors are going to be 4 bit long. There will be total 24 = 16 message words. Let us consider any message code word as under 0
M= (m0 ml m2 m3) = (1 0 1 0)
Therefore, the message polynomial is given by,
M(p)= m0 + m1 p + m2 p2 + m3 p3
Substituting the values of m0 ml, m2, and m3, we obtain
M(p) = 1 + p2
(ii) The generator polynomial is given by,
G(p) = 1 + p + p3
(iii) The non-systematic cyclic code is given by,
X(p) = M(p) . G(p) = (1 + p2) (1 + p + p3) = 1 + p +p3 + p2 + p3 + p5
or X(p) = 1 + p + p2 + p3 (1 Å 1) +p5
But, 1 Å 2 = 0
Therefore, X(p) = 1 + p + p2 + 0 p3 + 0 p4 + p5 + 0 p6
Note that the degree of the code word polynomial is 6 i.e. (n – 1). The code word polynomial is given by,
X = (1 1 1 0 0 1 0)
This is the code word for the given message word. Similarly, we can obtain the other non-synthetic code words.
Now, let us obtain the systematic code vectors.
To obtain the systematic code words, let us follow the following procedure :
(i) We multiply M(p) by pn-k.
Therefore, pn-k M(p) = p3 (1 + p2)
or pn-k M(p) = p3 + p5
(ii) We divide by pn-k M(p) by the generator polynomial.
Therefore, equation
The division is carried out as under :
equation
Mod 2 addition p5 + 0p4 + p3 + p2
Å Å Å Å
0 + 0 + 0 + 0
p2 + 0p + 0
Remainder polynomial C(p)
FIGURE 10.31 Division of Dn-k M(p) by G(p)
Thus, the results of the division are as under :
Quotient polynomial Q(p) 0 + 0p + p2
Remainder polynomial C(p) = 0 + 0p + p2 ¬ Represents the parity bits.
(iii) We obtain the code word polynomial X(p).
The code word polynomial can be obtained by adding pn-k M(p) to the remainder polynomial C(p).
Therefore, X(p) = [pn-k M(p)] Å B(p)
= [0 + 0p + 0p2 + p3 + 0p4 + p5 + 0p6]
or X(p) = [0 + 0p + p2 + p3 + 0p4 + p5 + 0p6]
Therefore, the code word vector is given by : [0 0 1 : 1 0 1 0]
Therefore, codeword is given by
diagram
FIGURE 10.32 Code word.
Note that with this procedure, we get a code vector in the format as shown in figure 10.32 where the parity bits appear first followed by the message bits. This format of a code word is also a valid format. However, we can modify the code formats as shown in figure 10.33.
diagram
FIGURE 10.33 Alternate formats of the code vectors.
Figure 10.33 tells us that the values of m0, ml, m2, m3 or c0, c1 and c2 remain unchanged. Only the way they are arranged is different in different codeword formats.
We can follow the same procedure to generate the remaining code words.
10.145. Generator and Parity Check Matrices of the Cyclic Codes
The cyclic codes are linear block codes. Therefore, we can define the generator and parity check matrices for the cyclic codes as well. The generator matrix G(p) has a size of k x n i.e., it has k rows and n columns. Let the generator matrix G(p) is given by,
G(p) = pn-k-1 + pn-k gn-k-1 + … + g2 p2 + g1 p + 1 …(10.36)
We multiply both the sides by pi, i.e.,
pi G(p) = pn-k + i + pn-k gn-k-1 + … = g2 p2 + i + g1 p1 + i + pi …(10.37)
where i = (k – 1), (k – 2), …, 2, 1, 0
Equation (10.37) represents the polynomial for the rows of the generating polynomials. It is possible to obtain the generator matrix from this equation.
EXAMPLE 10.20. For a (7, 4) cyclic code, determine the generator matrix if G(p) = 1 + p + p3.
Solution : Here, n = 7 and k = 4, hence, n – k = 3
G(p) = 1 + p + p3
(i) We multiply both the sides of G(p) by pi where i = (k – 1) …, 1, 0.
⸫ pi G(p) + pi + p1+i + p3 + i, i = (k-1) …, 1, 0.
But, i = 4, ⸫ i = 3, 2, 1, 0.
(ii) By substituting these values of i into equation (i), we get four different polynomials as under: These polynomials correspond to the four rows of the generator matrix as under:
Row No. 1 : i = 3 → p3 G(p) = p3 + p4 + p6
Row No. 2 : i = 2 → p2 G(p) = p2 + p3 + p5
Row No. 3 : i = 1 → p G(p) = p + p2 + p4
Row No. 4 : i = 0 → G(p) = 1 + p + p3
The generator matrix for (n, k) code is of size k x n. Therefore, for the (7, 4) cyclic code, the generator matrix will be a 4 x 7 matrix. The polynomials corresponding to the four rows are therefore, as under :
Row No. 1 : i = 3 → p6 + 0p5 = p4 + p3 + 0p2 + 0p + 0
Row No. 2 : i = 2 → 0p6 + p5 = 0p4 + p3 + p2 + 0p + 0
Row No. 3 : i = 1 → 0p6 + 0p5 = p4 + 0p3 + p2 + p + 0
Row No. 4 : i = 0 → 0p6 + 0p5 = 0p4 + p3 + 0p2 + p + 1
These polynomials can be converted into generator matrix G as under:
G =
This is the required generator matrix.
The cyclic codes are basically block codes. Therefore, its code vectors can be obtained by using the generator matrix as under:
X = MG …(10.38)
where, M = 1 x k message vector.
EXAMPLE 10.21. For the generator matrix of the previous example, determine all the possible code vectors.
Solution : All the code vectors can be obtained by using the following expression:
X = M G
Let M = (m3 m2 ml m0) = (1 0 1 0)
X= [1 0 1 0]
Therefore, X = [1 Å 0 Å 0 Å 0 0 Å 0 Å 0 Å 0 1 Å 0 Å 1 Å 0 Å 0
0 Å 0 Å 1 Å 0 0 Å 0 Å 1 Å 0 0 Å 0 Å 0 Å 0]
Therefore, we have X = [1 0 0 1 : 1 1 0]
Similarly, the other code vectors can be obtained.
NOTE It may be noted that the generator matrix G is of non-systematic form and the code vector X also is of non-systematic form. Therefore, the first four bits of X are not the same as the message bits.
10.14.6. Systematic Form of Generator Matrix
We know that the generator matrix in the systematic form is given by
G = [Ik : Pkx(n-k)]kx(n-k) …(10.39)
This means that there are k number of rows in the generator matrix. Let us represent the row number (in general) by i. The ith row of the generator matrix is represented by,
ith row of G = p(n-i) + Ri(p) … where i = 1, 2, …, k. … (10.40)
Now, we divide p(n-1) by the generator matrix G(p). The result of the division is expressed as,
equation
Let Remainder = Ri(p)
Quotient = Qi(p)
Substituting this into equation (10.41), we obtain
equation
Simplifying this equation, we obtain
p(n-i) = Qi (p) G(p) Å Ri(p) ; where i = 1, 2, …, k …(10.43)
In mod-2 additions, the addition and subtraction will yield the same result.
⸫ p(n-i) Å Ri(p) = Qi(p) G(p) …(10.44)
From equation (10.40), the above expression represents the ith row of the systematic generator matrix.
EXAMPLE 10.22. For systematic (7, 4) cyclic code, determine the generator matrix and parity check matrix. Given : G(p) = p3 + p + 1.
Solution : (i) The ith row of the generator matrix is given by equation (10.44) as under:
p(n-i) Å Ri(p) = Qi(p) G(p) ; where i – 1, 2, …, k …(i)
(ii) It is given that the cyclic code is systematic (7, 4) code.
Therefore, n= 7, k= 4 and (n – k)= 3
Substituting these values into the above expression, we obtain
p(7-i) Å Ri(p) = Qi(p) (p3 + p +1) … i = 1, 2, …4 …(ii)
(iii) With i = 1, the above equation is given by,
p6 Å Ri(p) = Qi(p) (p3 + p + 1) …(iii)
Let us obtain the value of Qi(p). The quotient Qi(p) can be obtained by dividing p(n-i) by G(p) as per equation (10.41). Therefore, to obtain Qi(p), let us divide p6 by (p3 + p + 1).
The division takes place as under :
equation
equation
equation
Here the quotient polynomial Qi(p) = p3 + p +1
and the remainder polynomial Ri(p) = p2 + 0p +1
Substituting these values into equation (ii), we obtain
p6 Å Ri(p) = (p3 + p + 1) (p3 + p + 1)
= p6 + p4 + p3 + p4 + p2 + p + p3 + p + 1
or = p6 + 0p5 + (1 Å 1)p4 + (1 Å 1)p3+p2 + (1 Å 1) p + 1
= p6 + 0p5 + 0p4 + 0p3 + p2 + 0p + 1
⸫ 1st Row polynomial Þ p6 + 0p5 + Op4 + 0p3 + p2 + 0p + 1
⸫ 1st Row Elements 1 0 0 0 1 0 1
Using the same procedure, we can obtain the polynomials for the other rows of the generator matrix as under :
2nd Row polynomial Þ p5 + p2 + p + 1
3rd Row polynomial Þ p4 + p2 + p
4th Row polynomial Þ p3 + p + 1
These polynomials can be transformed into the generator matrix as under:
equation
This is the required generator matrix.
The parity check matrix is given by :
H = [PT : I3×3]
The transpose matrix PT is given by interchanging the rows and columns of the P matrix.
PT =
Hence, the parity check matrix is given by,
equation
This is the required parity check matrix.