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.6k
- Engineering Mathematics 7.3k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.4k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 570
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 70
- Projects 18

48,691 questions

52,776 answers

183,436 comments

68,390 users