Why high and lower bit of generator must be 1?

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 how do you determine high order bit? And why high order bit and lower order bit, both must be one? From my understanding, it is used to detect burst error but is my understanding true?

Answer 1

The low order bit, also known as the least significant bit (LSB), is the "ones" bit of the number. For example, in 001101, the LSB is the rightmost bit 001101.

The high order bit, also known as the most significant bit (MSB), is the "topmost" bit of the number. In our example 001101, it is the leftmost bit 001101.

The two terms are also used figuratively (in general discourse): a high order bit is something important, and a low order bit is something not important.

Now to your question. We represent a message $m_0,\ldots,m_n$ by a polynomial $M(x) = \sum_i m_i x^i$. Given a generator polynomial $G(x)$, the idea is to extend the message to a new message $M'(x)$ that satisfies $G(x) \mid M'(x)$.

If the low order bit of $G(x)$ is zero, then such an extension isn't always possible. Indeed, the low order bit of $G(x)$ is zero iff $x \mid G(x)$. If this is the case, then $G(x) \mid M'(x)$ implies $x \mid M'(x)$, i.e. $m_0 = 0$. So if the lower order bit of $G(x)$ is zero, we will only be able to extend $M$ to $M'$ if $m_0 = 0$ (and even this is not necessarily a sufficient condition).

If the high order bit of $G(x)$ is zero, then the problem is a different. The probability that $G(x) \mid M'(x)$ for a random $M'$ is $2^{-\deg G(x)}$ (assuming $G$ is irreducible, that is, cannot be factored nontrivially). Therefore CRC offers us $\deg G(x)$ bits of protection. We therefore want $G(x)$ to have the maximum degree possible. This corresponds to having a high order bit of one.

In practice, $G(x)$ is stored without its high order bit: an 8-bit CRC polynomial really corresponds to 9 bits 1xxxxxxxx, but there is no need to store the 1.