crc calculation step by step , Cyclic Redundancy Check (CRC) , what is polynomial code circuit

Cyclic Redundancy Check (CRC) , crc calculation step by step , what is polynomial code circuit ?
Cyclic Redundancy Check (CRC)
            This is a type of polynomial code is which a bit string is represented in the form of polynomials with coefficients of 0 and 1 only. Polynomial arithmetic uses a modulo-2 arithmetic i.e., addition and subtraction are identical to E-XOR. For CRC code, the sender and receiver must agree upon a generator polynomial G(x). A codeword can be generated for a given dataword (message) polynomial M(x) with the help of long division. This technique is more powerful than the parity check and checksum error detection. CRC is based on binary division. A sequence of redundant bits called CRC or CRC remainder is appended at the end of a data unit such as byte. The resulting data unit after adding CRC remainder becomes exactly divisible by another predetermined binary number. At the receiver, this data unit is divided by the same binary number There is no error if this division does not yield any remainder. But, a non-zero remainder indicates presence of errors in the received data unit. Such an erroneous data unit is then rejected.
Procedure to obtain CRC
The redundancy bits used by CRC may be derived by following the procedure given below :
(i)         We divide the data unit by a predetermined divisor.
(ii)        We obtain the remainder. It is the CRC.
Requirements of CRC
A CRC will be valid if and only if it satisfies the following requirements:
(i)         It must have exactly one less bit than divisor.
(ii)        Appending the CRC to the end of the data unit must result in the bit sequence which is exactly divisible by the divisor.
CRC generator
The CRC generator is shown in figure 10.42.
diagram
FIGURE 10.42 CRC generator.
The procedure for CRC generation is as under :
(i)         We append a string of n 0s to the data unit where n is 1 less than the number of bits in the predecided divisor (n + 1 bit long).
(ii)        We divide the newly generated data unit in step (i) by the divisor. This is a binary division.
(iii)       The remainder obtained after the division in step (ii) is the n bit CRC.
(iv)       This CRC will replace the n 0s appended to the data unit in step (i), to get the codeword to be transmitted as shown in figure 10.42.
CRC checker
Figure 10.43 shows the CRC checker.
diagram
FIGURE 10.43 CRC checker.
The codeword received at the receiver consists of data and CRC. The receiver treats it as one unit and divides it by the same (n + 1) bit divisor which was used at the transmitter. The remainder of this division is then checked. If the remainder is zero, then the received codeword is error free and hence must be accepted. But a non-zero remainder indicates presence of errors hence the corresponding codeword must be rejected.
EXAMPLE 10.29. A codeword is received as 1100 1001 01011. Check whether there are errors in the received codeword, if the divisor is 10101. (The divisor corresponds to the generator polynomial).
Solution : We know that the codeword is formed by adding the dividend and the remainder. This codeword will have an important property that it will be completely divisible by the divisor. Thus, at the receiver we have to divide the received codeword by the same divisor and check for the remainder. If there is no remainder then there are no errors. But, if there is remainder after division, then there are errors in the received codeword. Let us use this technique and find if there are errors.
Data word : 1 1 0 0 1 0 0 1 0 1 0 1 1
Divisor : 1 0 1 0 1
diagram
The non zero remainder shows that there are errors in the received codeword.
Generation of CRC code
The generation of CRC code is obvious after solving the following example.
EXAMPLE 10.30. Generate the CRC code for the data word of 1 1 0 0 1 0 1 0 1. The divisor is 1 0 1 0 1.
Solution : Given that
Data word : 1 1 0 0 1 0 1 0 1
Divisor : 1 0 1 0 1
The number of data bits = m = 9
The number of bits in the codeword = N
Dividend = Data word number of zeros.
diagram
Now, let us carry out the division as under :
diagram
Codeword
In CRC the required codeword may be obtained by writing the data word followed by the remainder
Therefore, we have
1 1 0 0 1 0 1 0 1 0 0 0 0 0
                                       1 1 0
Codeword      =           1 1 0 0 1 0 1 0 1 0 0 1 1 0
Undetected errors in CRC
CRC cannot detect all types of errors. The probability of error detection and the types of detectable errors depends on the choice of divisor.
EXAMPLE 10.31. Write the steps to compute the check sum in CRC code. Determine CRC for the frame 1 1 0 1 0 1 0 1 1 and the generator polynomial = x⁴ + x + 1 and write the transmitted frame.
Solution: The generator polynomial actually acts as the divisor in the process of CRC generation.
Therefore,                    Data word : 1 1 0 1 0 1 0 1 1
Divisor    : x⁴ + 0 x³ + 0 x² + x + 1 = 1 0 0 1 1
The number of data bits = m = 9
The number of bits in the codeword = N
Dividend = Data word + (N – m) number of zeros.
diagram
Let us carry out the division as under :
1 1 0 0 0 0 1 1 1 1
diagram
equation
equation
equation
Codeword
The codeword is given by
diagram
EXAMPLE 10.32. If the frame is 110101011 and generator polynomial is x⁴ + x + 1. Determine the transmitted frame.
Solution : Given that Data word : 1 1 0 1 0 1 0 1 1
Generator polynomial : x⁴ + x + 1 = x⁴ + 0 x³ + 0 x² + x + 1 = 10011
(i)         First, let us add five zeros at the end of the data word.
We add five zeros (equal to number of generator bits) at the end of the data word to get the dividend as under :
diagram
(ii)        Next, we carryout the long division as under :
equation and diagram
equation
equation
(iii)       Next, let us write the transmitted frame.
The transmitted frame may be obtained by writing the data word followed by the remainder as under :
1 1 0 1 0 1 1 0 1 1 0 0 0 0 0    ←        Dividend
+                                          0 1 1 1 1          ←        Remainder
Transmitted frame →         1 1 0 1 0 1 1 0 1 1 0 1 1 1 1
Therefore, the transmitted codeword may be written as under :
1 1 0 1 0 1 1 0 1 1 | 0 1 1 1 1
EXAMPLE 10.33. Determine the remainder obtained by dividing x⁷ + x⁵ + 1 by the generator polynomial x³ + 1 ?
Solution : Given dividend
x⁷ + x⁵ + 1 = x⁷ + 0x⁶ + x⁵ + 0x⁴ + 0x³ + 0x² + 0x + 1
= 10100001
Divisor :          x³ + 1 = x³ + 0x² + 0x + 1  = 1001
The long division is as under :
equation
equation
The remainder is 00111 = x² + x + 1 in the polynomial form.
EXAMPLE 10.34. A bit stream 10011101 is transmitted using the standard CRC method. The generator polynomial is x³ + 1. Show the actual bit string transmitted. Suppose the third bit from left is inverted during transmission. Show that this error is detected at the receiver’s end.
Solution : Given that, data word (Bit string) : 1 0 0 1 1 1 0 1
Generator polynomial : x³ + 1 = x³ + 0x² + 0x + 1 = 1 0 0 1
We know that
Dividend = Data word + 4 zeros.
The dividend will be as under :
Dividend → 1 0 0 1 1 1 0 1 | 0 0 0 0
Now, let us carry out the division as under :
diagram and equation
equation
equation
The transmitted word may be obtained by writing the data word followed by the remainder as under :
Transmitted word = 1 0 0 1 1 1 0 1 | 0 0 0 1
Next let us write the erroneous received word.
The received word = 1 0 j 1 1 1 0 1 0 0 0 1
At the receiver, this word is deivided by the same divider used at the transmitter i.e., 1001.
equation
equation
equation
A non zero remainder shows that there is an error in the received codeword.
EXAMPLE 10.35. Construct a systematic (7,4) cyclic code using the generator polynomial G(x) = x³ + x + 1. What are the error correcting capabilities of this code ? Construct the decoding table and for the received codeword 1 1 0 1 1 0 0, determine the transmitted data word.
Solution: From the given data, it is quite obvious that n = 7 and k = 4 for this code.
We can use equation (10.44) to obtain the generator matrix for the given generator polynomial. This will be as under :
G =                              …(i)
The generator matrix obtained in equation (i), may be used to calculate the code vector, because
X = MG
Where              M = Message vector.
As an example if the message vector is M = 1 0 1 0 then the corresponding codeword may be obtained as under :
X = [ 1 0 1 0 ]
Therefore,                    X = [ 1 0 1 0 :  0 1 1]
Û         Û
Message   Parity bits
Similarly, we can obtain the code word for other message vectors.
From all the codewords, it is clear that the minimum distance is d_min = 3. Therefore, this code will be able to detect upto 2 errors and correct upto only 1 errors.
Now, let us obtain transpose matrix P^T. We know that
G = [I_n : P_nx(n-k)]
But                                G =
Therefore,                    P =
The transpose of this matrix may be obtained by interchanging the rows and columns as under :
P^T =
Now, the parity check matrix is given by
H = [P^T : I_n-k] =
We can obtian the transpose matrix H^T by interchanging the rows and columns of H matrix as under :
H^T =
We can obtain the decoding table from the transpose of the parity check matrix, H^T because each row of H^T represents a syndrome and an unique error pattern as discussed earlier (in linear block code). Table 10.15 shows the error pattern and syndrome vectors.
Table 10.15. Decoding Table

 
Now, let us decode the input word.
The input word Y= 1 1 0 1 1 0 0
The received word can be expressed in the polynomial form as under :
Y(x) = + x⁵ + x³ + x²
The syndrome vector is given by
S(x) = remainder
Hence, let us perform the division as under :
Y(x) = x⁶ + x⁵ + 0 x⁴ + x³ + x² + 0 x + 0
and                              G(x) = x³ + 0x² + x + 1
The division takes place as under :
equation
Mod-2 addition           →        equation
Mod-2 addition           →        equation
Mod-2 addition           →        equation
Mod-2 addition           →        equation
 
The remainder polynomial is given by : x² + 0x + 1
Therefore,
S = [1 0 1]
The non zero syndrome shows that there exists an error in the received codeword. The decoding table shows that the error vector corresponding to the syndrome S = 1 0 1 is given as
E = [ 1 0 0 0 0 0 0 ]
Therefore, the corrected codeword is given by
X   = Y Å E
= [ 1 1 0 1 1 0 0 ] Å [ 1 0 0 0 0 0 0 ]
Hence,
X   = [ 0 1 0 1 1 0 0 ]
EXAMPLE 10.36. Why are cyclic codes effective in detecting error bursts ? The message 1001001010 is to be transmitted in a cyclic code with a generator polynomial g(x) = x² + 1.
            (i)         How many check bits does the encoded message contain ?
            (ii)        Obtain the transmitted code word.
            (iii)       Draw encoding arrangement to obtian remainder bits.
            (iv)       After the received word is clocked into the decoder input, what should be the content of the register stores ?
Solution : The message polynomial M(p) corresponds to the given message signal (1 0 0 1 0 0 1 0 1 0). This means that there are 10 message bits.
Hence, k = 10                                                                                                   …(i)
Thus, the message polynomial is given by
M(p) = m₀ + m₁p + m₂p² + m₃p³ + m₄p⁴ + m₅p⁵ + m₆p⁶ + m₇p⁷ + m₈p⁸ + m₉p⁹.
= 0 + p + 0p² + 1p³ + 0p⁴ + 0p⁵ + 1p⁶ + 0p⁷ + 0p⁸ + 1p⁹
or         M(p) = p⁹ + p⁶ + p³ + p                                                                                     …(ii)
The generator polynomial is given by
G(p) = p² + 1                                                                                       …(iii)
Hence, the degree of generator polynomial is 2. The degree of generator polynomial is equal to the number of parity (check) bits in the code.
so,        number of check bits = (n – k) = 2                                                       …(iv)
Hence, length of the codeword = n = k + 2
n = 10 + 2 = 12                                                                         …(v)
Now, let us multiply M(p) by p^{n – k} i.e., by p² as under :
p^{n – k}. M(p) = p² [p⁹ + p⁶ + p³ + p]
= p^l1 + p⁸ + p⁵ + p³                                                          …(vi)
Next, we divide p^n-k M(p) by the generator polynomial as under :
EQUATION
EQUATION
The codeword polynomial may be obtained by adding p^n-k M(p) to the remainder polynomial C(p).
Thus,                                       X(p) = D² M(p) + C(p)                                                …(vii)
The remainder polynomial C(p) = p + 1
Therefore,                                X(p) + [p¹¹ + p⁸ + p⁵ + p³] + [p + 1]             …(viii)
Hence, the corresponding codeword is given by,
EQUATION
Now let us draw the encoder for the cyclic code.
The given generator polynomial is
G(p) = p² + 1 = p² + 0p + 1                             …(ix)
We know that the general form of the generator polynomial expressed as
EQUATION
EQUATION
or                                             G(p) = p² + g₁ p + 1                                          …(x)
Comparing equations (ix) and (x), we obtain
g₁ = 0, g₂ =1
Therefore, the encoder has been shown in figure 10.44.
DIAGRAM
FIGURE 10.44. Encoder for the cyclic code