CRC computation I would like to understand the CRC computation using CCITT CRC-16 $x^{16} + x^{12} +x^{5} +1$. I was able to successfully implement it in a program but I would like to understand the computation behind it. I was not succesful in the paper-n-pen technique. Is the CRC computation with CRC-16 different.
Any useful hints in this direction. 
P.S : I am not keen on the program or the shift register implementation but the traditional way of computing CRC with polynomials or binary sequence using binary division technique. 
Thanks for reading
 A: A CRC computation is as follows.  You have a data polynomial 
$d(x) = \sum_{i=0}^{n-1} d_ix^i$ where the $d_i \in \{0, 1\}$ are 
$n$ bits to
be transmitted (or recorded).  What is actually transmitted (or 
recorded) is 
$$t(x) = x^{16}d(x) + p(x)$$
where $p(x)$ is the ${\textit remainder~polynomial}$ 
when $x^{16}d(x)$ is divided by the CRC polynomial 
$C(x) = x^{16} + x^{12} + x^5 + 1$.  Note that polynomial division yields
$$
x^{16}d(x) = q(x)C(x) + p(x)
$$
where the quotient $q(x)$ is discarded.  But the above equation 
can be re-arranged as
$$
q(x)C(x) = x^{16}d(x) - p(x) = x^{16}d(x) + p(x) = t(x)
$$ 
(because arithmetic on the polynomial coefficients is done modulo $2$
and subtraction is thus the same as addition),
and thus $t(x)$ is a multiple of the CRC polynomial $C(x)$.
Since $p(x)$ is of degree $15$ or less, the
high-order coefficients of the polynomial $t(x)$ are the data bits
while the low-order coefficients are the so-called CRC bits or parity
bits, that is
$$
t(x) = d_{n-1}x^{n-1 + 16} + d_{n-2}x^{n-2+16}
+ \cdots d_0x^{16} + p_{15}x^{15} + p_{14}x^{14} + \cdots + p_0.
$$
In computing $p(x)$ via polynomial long division using paper and pencil,
you need to remember that
(i) $\quad \quad$ $d(x)$ is multiplied by $x^{16}$ before
beginning the long division
(ii) $\quad \quad$ the subtractions of polynomial coefficients that occur in
the long division process are all done modulo $2$ and thus are the same as additions modulo $2$ (that is, the XOR operation)
(iii) $\quad \quad$ the long division continues till $x^{16}d_0$ is processed
and the remainder is a polynomial of degree $15$ or less.
Practical CRC systems often have bells-and-whistles (such as the high-order
bits $8$ bits in $x^{16}d(x)$ are complemented before the division process
begins etc.) which I have not included above because these are likely
not  of interest in this forum.  However, ignoring such details in your 
paper-and-pencil computations will make your results differ
from the ones your machine is giving you.
At the receiving (or reading) end, what you have is a polynomial
$r(x)$ which might be $\textit slightly$ different from $t(x)$
if transmission (or read) errors changed some of the bits.  The
CRC error detection process merely divides $r(x)$ by $C(x)$; no
need to multiply $r(x)$ by $x^{16}$ first.   If
the remainder is nonzero, then $r(x)$ is $\textit not$ a multiple
of $C(x)$ and so the receiver knows that transmission (or read) errors
have occurred.  But if the remainder is $0$, then $r(x)$ is a 
multiple of $C(x)$, and
with high probability, is the same as $t(x)$.  The low-order
$16$ bits in $r(x)$ are discarded and the high-order $n$ bits
are accepted as error-free data. When the remainder is $0$, there 
is a small probability that the difference between $r(x)$ and $t(x)$ 
is a multiple of $C(x)$.  Such errors are referred to as undetected
errors.  The probability of undetected error decreases as the degree
of $C(x)$ increases.  For this reason, many modern systems use 
CRC polynomials of degree 32.
