26 views

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 $x^{3}+x^{2}+1$, or $1101$. To build the table for $C$, we take each $3$-bit sequence, $p$, append three trailing $0$s, and then find the quotient $q= p \frown 000 \div C$,

Ignoring the remainder. The third column is the product $C \times q$, the first $3$ bits of which should equal $p$

(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 \times 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.