Why frame must be longer than generator polynomial?

Question

Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 213:

When the polynomial code method is employed, the sender and receiver must agree upon a generator polynomial, $G(x)$, in advance. Both the high- and low-order bits of the generator must be $1$. To compute the CRC for some frame with $m$ bits corresponding to the polynomial $M(x)$, the frame must be longer than the generator polynomial. The idea is to append a CRC to the end of the frame in such a way that the polynomial represented by the checksummed frame is divisible by $G(x)$. When the receiver gets the checksummed frame, it tries dividing it by $G(x)$. If there is a remainder, there has been a transmission error.

My question is why to compute the CRC for some frame with $m$ bit corresponding to the polynomial $M(x)$, the frame must be longer than the generator polynomial?

I tried to search for the reason but couldn't really find the exact answer, so in my opinion, if the generator polynomial is longer than the frame, it will create check bit that is more than data bit which is redundant because CRC is used in error detecting code and error detecting code is used in places where fewer error occur. But is that true?

Answer 1

The easiest way to see this is from the receiver side. As in the excerpt, "If there is a remainder, there has been a transmission error." Implicitly, if there is no remainder, there is no transmission error.

The case of no transmission error, with no remainder means that if the checksummed frame is $M'(x)$, then there is a non-zero polynomial $A(x)$ such that

$$M'(x) = G(x)A(x)$$

where

$$\hbox{d}(M'(x)) = \hbox{d}(G(x)) + \hbox{d}(A(x))$$

and $\hbox{d}()$ means the degree of the polynomial (it's "length"). Since $\hbox{d}(A(x)) \ge 1$, then

$$\hbox{d}(M'(x)) > \hbox{d}(G(x))$$

which means the frame is longer than the generator polynomial.

Answer 2

If the CRC polynomial is $m$-bit long, then in order to create $M'$ from $M$, you need to add $m$ bits (or perhaps $m-1$ bits). In particular, the final message $M'$ is at least $m$-bit long.