Cyclic Redundancy Check (CRC) Calculation
Cyclic redundancy check (CRC) codes are an error-detection technique that is widely used in today’s computer networks. Consider a d-bit piece of data, denoted as D, that will be sent from one node to the other. Both nodes must have an agreed upon an r+1 bit pattern, known as a generator, which will be denoted as G. However, there is a requirement for G that the leftmost bit has to be a one. We will also denote D' being the original D times 2 to the power r. The goal of CRC is to tack on r additional bits to D, these r-bits will be the remaining bits when G is divided into D', denoted by R (the remainder). When the R is added to D', that will be the bit pattern that is exactly divisible with G using modulo-2 arithmetic.
To show this process more clearly, we will walk through an example.
Suppose G = 10011 and D = 1010101010
- Since G is an agreed upon from both nodes, it will be given. Since G is 5 bits long, then r is |G|-1=4, r=4.
- D will be now shifted left by 4-bits and zero will be inserted into those places, and the new pattern will be denotes by D' = 10101010100000
- Now we will divide G into D' using an “exclusive or” operation. This is shown in Figure 1.
- The remainder from the division, R, will be the bit pattern need to add to D' such that the resulting bit pattern will be exactly divisible with G.
Figure 1: Initial Division
To divide one binary number into another (as shown in Figure 1 and 2). The exclusive or operation is used. If you don’t know how to compute this type of operation consider the example:
Suppose you would like to take the exclusive or of these two binary numbers: 10101 10011 First compare each number in the same positions in the two strings starting from the right to the left. 10101 10011 The first compare is between 1 and 1: an exclusive or between the two will result in 0. This is because they are the same number and the operation between the two will result in false. In exclusive or you can only have one or the other, not both. The second comparison is between 0 and 1: an exclusive or between the two will result in 1. This is because they are both different numbers, therefore will result in true. The fourth comparison is between 0 and 0: an exclusive or between the two will result in 0 for the same reason that the first comparison was a 0. You should continue these comparisons for all the bits in the string, and result with 00110 or just 110.
If you are not quite sure whether you computed the correct remainder R. This is a simple way to check your work.
- From the example about the resulting bit pattern when R is added to D' is D'' = 10101010100100
- Then divide G into D''.
- If you computed the correct R then the resulting remainder will be 0. This is shown in Figure 2.
