The CRC algorithm as presented in this chapter requires lots of bit manipulations. It is, however, possible to do polynomial long division taking multiple bits at a time, via a table-driven method, that enables efficient software implementations of CRC.We outline the strategy here for long division 3 bits at a time (see Table 2.5); in practice, we would divide 8 bits at a time, and the table would have 256 entries. Let the divisor polynomial C-C(x) be x3 +x2 +1, or 1101. To build the table for C, we take each 3-bit sequence, p, append three trailing Os, and then find the quotient q p 000C, ignoring the remainder. The third column is the product C X q, the first 3 bits of which should equal p. Table 2.5 Table-Driven CRC Calculation 001 101 010 011 100011 101 110 110 001 001 010 011 100 101 110 011 110 100 (a) Verify, for p 110, that the quotients p 000-Cand p-111-C are the same; that is, it doesn't matter what the trailing bits are (b) Fill in the missing entries in the table (c) Use the table to divide 101 001 011 001 100 by C. Hint: The first 3 bits of the dividend are p = 101, so from the table the corresponding first 3 bits of the quotient are q 110.Write the 110 above the second 3 bits of the dividend, and subtract C Xq 101 110, again from the table, from the first 6 bits of the dividend. Keep going in groups of 3 bits. There should be no remainder Hints/Help a) by adding 000 or 111 to the 3 bits making up p, it is shown that both bit additions are valid for the procedure. The same value for q is obtained (remainders are different, but those are ignored for this method) b) For the table, calculate the two missing q values by taking the corresponding value for p appending 3 O's to p and then dividing that by C to get q for that p. For the missing Cxq values multiply C by the q given or calculated. When multiplying C and q, the results will be a 1 from 1x1 or 0 from 0x1 or 0x0. The addition is performed modulo two with no carry: 1+10 no carry 1+1+1 - 1 no carry. Arithmetic is done at the bit level c) Division is performed 3 bits at a time. Take the first three bits of the number that is being divided that corresponds to a p in the table. For that value of p there is a q and a Cxq value. o is the quotient and goes over bits 4,5 and 6 of the number being divided. The Cxq value goes beneath the first 6 bits. The first 3 bits of both match and result in 0. The last three bits have to be added as explained in part b. The resulting 3 bits from this addition make up the next p which is used to access the table. Bring down the next 3 bits of the number being divided and put them next to the 3 bits just determined. q for the value of p just found is put next to the first q, and Cxq is placed below the current 6 bits. This process continues until all numbers are divided. The resulting quotient is at the top and the remainder should be 0 for this problem. This is a faster method for verifying the CRC at the receiver (see if there is an error) Example, divide 100010101 by 1101 using the table in the problem Red represents p100 and 001 Blue represents g111 and o01 Purple represent Cxq - 100011 and 001101 1101 100010101 100011 001101 001101 The CRC algorithm as presented in this chapter requires lots of bit manipulations. It is, however, possible to do polynomial long division taking multiple bits at a time, via a table-driven method, that enables efficient software implementations of CRC.We outline the strategy here for long division 3 bits at a time (see Table 2.5); in practice, we would divide 8 bits at a time, and the table would have 256 entries. Let the divisor polynomial C-C(x) be x3 +x2 +1, or 1101. To build the table for C, we take each 3-bit sequence, p, append three trailing Os, and then find the quotient q p 000C, ignoring the remainder. The third column is the product C X q, the first 3 bits of which should equal p. Table 2.5 Table-Driven CRC Calculation 001 101 010 011 100011 101 110 110 001 001 010 011 100 101 110 011 110 100 (a) Verify, for p 110, that the quotients p 000-Cand p-111-C are the same; that is, it doesn't matter what the trailing bits are (b) Fill in the missing entries in the table (c) Use the table to divide 101 001 011 001 100 by C. Hint: The first 3 bits of the dividend are p = 101, so from the table the corresponding first 3 bits of the quotient are q 110.Write the 110 above the second 3 bits of the dividend, and subtract C Xq 101 110, again from the table, from the first 6 bits of the dividend. Keep going in groups of 3 bits. There should be no remainder Hints/Help a) by adding 000 or 111 to the 3 bits making up p, it is shown that both bit additions are valid for the procedure. The same value for q is obtained (remainders are different, but those are ignored for this method) b) For the table, calculate the two missing q values by taking the corresponding value for p appending 3 O's to p and then dividing that by C to get q for that p. For the missing Cxq values multiply C by the q given or calculated. When multiplying C and q, the results will be a 1 from 1x1 or 0 from 0x1 or 0x0. The addition is performed modulo two with no carry: 1+10 no carry 1+1+1 - 1 no carry. Arithmetic is done at the bit level c) Division is performed 3 bits at a time. Take the first three bits of the number that is being divided that corresponds to a p in the table. For that value of p there is a q and a Cxq value. o is the quotient and goes over bits 4,5 and 6 of the number being divided. The Cxq value goes beneath the first 6 bits. The first 3 bits of both match and result in 0. The last three bits have to be added as explained in part b. The resulting 3 bits from this addition make up the next p which is used to access the table. Bring down the next 3 bits of the number being divided and put them next to the 3 bits just determined. q for the value of p just found is put next to the first q, and Cxq is placed below the current 6 bits. This process continues until all numbers are divided. The resulting quotient is at the top and the remainder should be 0 for this problem. This is a faster method for verifying the CRC at the receiver (see if there is an error) Example, divide 100010101 by 1101 using the table in the problem Red represents p100 and 001 Blue represents g111 and o01 Purple represent Cxq - 100011 and 001101 1101 100010101 100011 001101 001101