The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

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.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,753 questions

46,767 answers

140,670 comments

58,544 users