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.4); 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.

Table 2.4

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 does not 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.

Transcribed Image Text:

Table 2.4 Table-driven CRC calculation. 000 001 010 011 100 101 110 111 q=p 000C 000 001 011 0 111 110 100 Cxq 000 000 001 101 010 011 100 011 101 110 110 111