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.6); 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 x³ + x² +1, or 1101. To build the table for C, we take each 3-bit sequence, p, append three trailing 0s, and then find the quotient

q = p ⌢000÷C, ignoring the remainder. The third column is the product C × q, the first 3 bits of which should equal p.

 

(a) Verify, for p = 110, that the quotients p ⌢000 ÷ C and 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×q = 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.