Why should we append zeros during CRC calculation?

Question

Say we have M as message bits , why do we need to append r-zeros to M message bits before performing the division to obtain r-bit checksum. Why don't we directly perform the division on the M message bits only (no zeros appended) and append the r-bit checksum at the end before transmission.

Answer 1

Rewriting your question the way I understood it. Just to make sure that we are talking about the same thing. It is possible that I misunderstood, in which case this is rubbish.

Let $m(x)$ be the message polynomial, and $p(x)$ a CRC-polynomial of degree $r$. Normally the CRC-tagged message is generated as follows. We calculate the remainder $r_1(x)$ of $x^rm(x)$ when divided by $p(x)$. The transmitted/stored version of the message is then $f(x)=x^rm(x)+r_1(x)$. Because $\deg r_1(x)\le r$, and the message polynomial was multiplied by $x^r$ (=padded with $r$ zeros) the CRC-tag $r_1(x)$ does not overwrite any message bits.

The receiver can then perform the CRC-check simply by checking whether their version of $f(x)$ is divisible by $p(x)$.

I understood that your suggestion is to just calculate the remainder $r_2(x)$ of $m(x)$ when divided by $p(x)$, without padding the zeros, and then transmit the pair $(m(x), r_2(x))$. The receiver can then check whether the polynomial formed by the last $r$ bits matches with the remainder of the message polynomial.

The reason why the standard way is better is the following. The CRC-polynomial $p(x)$ can be designed in such a way that no binomial $x^{k_1}+x^{k_2}$ is divisible by it unless the exponents are very large (larger than the maximum allowed message length this CRC-polynomial comes with). For example, it is possible to select a degree 16 polynomial $p(x)$ in such a way that this never happens, when $k_1,k_2<2^{16}-1=65535$ - a relatively long block.

A consequence of this design is that ALL error patterns of two bits are caught. Consider the following. If instead of $f(x)=x^rm(x)+r_1(x)$ the receiver makes two mistakes, he will see $$f'(x)=f(x)+x^{k_1}+x^{k_2}$$ instead of $f(x)$. But because $f(x)$ is divisible by $p(x)$ and the extra binomial is not, he will notice that an error has happened, because $f'(x)$ is not divisible by $p(x)$.

But if we did it your way, the following bad thing might happen. What if instead of a legal $(m(x),r_2(x))$ pair, the receiver makes, again, two errors, placed in a nasty way such that he sees instead of the above pair the pair $$ (m(x)+x^j,r_2(x)+x^j), $$ where $j<\deg p(x)$? Unfortunately they will not catch errors of this type. That's because as $$m(x)\equiv r_2(x)\pmod{p(x)},$$ we also have $$ m(x)+x^j\equiv r_2(x)+x^j\pmod{p(x)}, $$ and hence this erroneous message passes this check even though only two bit errors occurred. Notice that we cannot improve this situation by redesigning the polynomial $p(x)$.

Algebraically the difference is that your method fails, when the same monomial error $x^j$ occurs in both the message and the check parts, as $x^j+x^j=0$. With zero padding in place that type of error will be caught because $p(x)$ does not divide any binomials. Zero padding means that divisibility by $p(x)$ will be tested with the error polynomial $x^{j+r}+x^j$ instead of the pair $(x^j,x^j)$.

Answer 2

To simplify @Jyrki's answer even further, suppose that $M(x)=1$, that is, the $k-1 = \text{degree-}M$ high-order data bits are $0$. Then, in the absence of zero-padding, the division process that divides by $g(x)$ to give the remainder $t(x)$ of degree smaller than $r$ simply returns $t(x) = 1$. Transmitting $M(x)$ followed by $t(x)$ results in a codeword of $$\underbrace{00\cdots01}_{k ~\text{data bits}}\,\underbrace{00\cdots 01}_{r~\text{parity bits}}$$ and so two errors could change the received sequence into the all-zeroes sequence which will be happily accepted as a transmission with no errors in it.