Top Ad unit 728 × 90

10: Ethernet - How to calculate CRC (Cyclic Redundancy Check) ? part 14

Real scenario : CRC calculation

Note : the previous explanation is adequate for CCNA candidates !
After laying the ground for a little harder CRC, it is time to delve more profoundly in how CRC is calculated and how errors are detected by using binary system, which is the actual language of computers, as well as its representation in mathematical forms that are designed for human beings.

CRC, error detection mechanism, is based on binary division, and it is often represented in algebraic polynomial for the reasons that it is shorter than the act of writing zeroes and ones to prove the concept mathematically, and also the capacity of being able to be represented in binary pattern. Nevertheless, our explanation will include both CRC code’s representations.

Let us first explain how to transform from polynomial to binary representation by considering this example :

Rule : The power of each term shows the position of the bit; the coefficient shows the value of the bit. To make this rule more easier to understand, follow these steps.

The transformation above has been done by first looking at the left where we have X8, then we start counting. If we have X to the power of any number (x8), we write ‘1’ which is the case above. Next, we see if the number before the power ‘8’  is there, which is, in this case, ‘7’, so we add another ‘1’ (if a number does not exist, we put in its place a zero).Then, we look at the number that comes before 7, which is 6, and the above example does not have X6, so we put ‘0’. After, we add ‘1’ because X5 exists.

Afterwards, we add another ‘1’ because x4 is there. After that, we put ‘0’ because there is no X3.  Subsequently, we add ‘1’ because we have x2. Following that we add another ‘1’ because we have x, and whenever you see x without a power, it automatically equals x1. Finally, we put ‘1’ because we have 1 ; in the same way, whenever you see 1, it automatically equals x0. This figure summaries all that.

Now, after knowing how to transform from polynomial to binary, let us employ all that in a CRC operation.

To calculate CRC value we need a generator value along with the message to be transmitted. The generator (or divisor) is the binary number by which the message’s binary number + appended number (or dividend) is to be divided to get the CRC value. For example, 1010100111+0000 is the message to be transmitted, and 01100 is the generator. However, the division here is a litle bit different. Consider this example.

 Suppose we have :

- CRC generator/ generator polynomial = x5+ x2+1.

- Data unit to be transmitted =  x9 + x6 + x4 + x2 + x

- ‘n’ is a string of 0’s appended to the data unit to be transmitted where n is one less than the number of bits in the CRC generator.

Through what statements given we can calculate the CRC value.

First, we transform the generator polynomial x5+ x2+1 into binary, which gives 100101. Then, we transform the data unit to be transmitted from the polynomial x9 + x6 + x4 + x2 + x into binary, which gives 1001010110 .

Second, we add ‘n’ string of zeroes to the data unit to be transmitted. As written in the third statement, n is one less than the number of bits in the CRC generator. So we take CRC generator which is 100101 and count how many bits there are, and detract one bit. The number of bits is 6 and by detracting 1 bits, it becomes 5 bits, which is the final number of zeroes to be appended at the end of data unit. The whole data unit becomes 100101011000000.

Third, we divide the newly formed data unit by the divisor (CRC generator) using binary division. The remainder is called CRC (Cyclic Redundancy Check).

The CRC calculation is done as what follows:

We first take the data unit to be transmitted plus the appended zeroes in binary, which is the dividend, along with the divisor binary number as arranged in the above figure. Then, we start performing XOR (Exclusive OR) operation which is explained below.

 First step : we take the divisor 100101 and put it in the left under the data unit 100101011000000 (dividend) in this way:
Second step : we perform XOR operation. 1 + 1 = 0 /  0 + 0 = 0 /  0 + 0 = 0 / 1 + 1 = 0 / 0 + 0 = 0 / 1 + 1 = 0.   The result is :

Note : During the calculation we have to ignore the first bit in the left in all XOR operations and put down the bits that have no divisor beneath.

Third step : we have to look at the first bit in the results. If itstarts with 0, we need to put the divisor’s bit numbers in zeroes 000000; but if the first bit starts with 1, we need to put the actual divisor 100101.

Final step : we keep following the same technique until we put down the last appended zero as appeared below
After getting the CRC,  the last five zeroes of data unit are replaced with the CRC value ; thus 100101011000000 becomes 100101011011110. This latter is the data plus CRC value that is going to be sent to the receiver. Here the role of the sender is finished.

When the receiver gets the frame, it takes the data unit along with the CRC value and repeat the same calculation using the same divisor. If the final result equals 00000, the data is said to be intact, but if the result is another number, the data would be said to be damaged. Look at the following figure.

I hope you have understood the lesson. If so, please do not forget to give your feedback by commenting on the lesson.
10: Ethernet - How to calculate CRC (Cyclic Redundancy Check) ? part 14 Reviewed by BOUFTIRA on 11:13:00 AM Rating: 5

No comments:

All Rights Reserved by Computer Networks For All © 2015 - 2017

Contact Form


Email *

Message *

Powered by Blogger.