Problem $1.$

Suppose we want to transmit the message $1011001001001011$ and protect it from errors using the CRC$-8$ generator $100000111.$

$1\mathrm{.}1.$ Determine the message that is transmitted.

$1\mathrm{.}2.$ Suppose the leftmost bit of the message is inverted due to noise on the transmission link. What is the result of the receiver's CRC calculation? How does the receiver know that an error has occurred?

Problem $2.$

The CRC algorithm as presented in this chapter, requires lots of bit manipulations. It is$,$ however, possible to do them by taking multiple bits at a time, via a table$-$driven method, that enables efficient software implementations of CRC$.$ I outline the strategy here for long division $3$ bits at a time $($See table below$)$; in practice, we would divide $8$ bits at a time, and the table would have $256$ entries.

Let the generator $\backslash ($ G$=1101\backslash ).$ To build the table for $\backslash ($ G $\backslash ),$ we take each $3-$bit sequence $\backslash ($ p $\backslash ),$ append three trailing $0$ s $,$ and then find the quotient $\backslash ($ q$=$p $000\backslash$div G $\backslash ),$ ignoring the remainder. The third column is the product of $\backslash ($ G $\backslash$times q $\backslash )($note: do exclusive$-$or when adding bits up$),$ and the first $3$ bits should be equal $\backslash ($ p $\backslash ).2\mathrm{.}1.$ Fill in the missing entries in the following table $($I did two rows for you already.$)$

$2\mathrm{.}2$ Use the table you developed above to divide $101001011001100$ by $\backslash ($ G$=1101\backslash ).$

Hint: The first $3$ bits of the dividend are $\backslash ($ p$=101\backslash ),$ so from the table, the corresponding first $3$ bits of the quotient are $\backslash ($ q$=110\backslash ).$ Write $110$ above the second $3$ bits of the dividend, and subtract $\backslash ($ G $\backslash$times q$=101110\backslash )($again$,$ from table$)$ from the first $6$ bits of the dividend. Keep going in groups of $3$ bits.