Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
You can't be completely ignorant if you know enough to implement the computation in a program. Please tell us more about what it is you feel is unclear. Just unspecified "useful hints" are difficult to provide when we don't know which state of knowledge they have to be useful in. –  Henning Makholm Sep 20 '11 at 15:58
    
Well, implementation was pretty easy I would say. There was an algoirthm on the compututation of CRC in the technical spec of 802.11b But I tried to compute by actually dividing the Message polynomial by the Gen.Polynomial $x^16+x^12+x^5+1$ but the reminder was not what I had expected. –  www.sapnaedu.in Sep 20 '11 at 17:43
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
Thanks Dilip, I think I missed multiplying $x^{16}$ to d(n). Thanks taking time in explaining to me. –  www.sapnaedu.in Sep 20 '11 at 17:48
    
I missed it again, I tried multiplying d(x) is multiplied by $x^{16}$ before beginning the long division, but p(x) was not what I had expected. In the shift register implementation, I initially set the contents to all 1's, will dividing the $x^{16}$ *d(x)/t(x), do we need to handle this ? How does this change the calculations. I am trying to understand the CRC computation in IEEE 802.11 Standard Thanks –  www.sapnaedu.in Sep 20 '11 at 18:37
    
I don't have access to the IEEE 802.11 standard and so don't know how it does things. But initial loading with all $1$s is one of the bells or whistles I mentioned as likely to be uninteresting to readers of this forum. –  Dilip Sarwate Sep 20 '11 at 18:50
    
thanks a lot, would it be possible to direct me to a reference where they talk of this exception and how the polynomial changes, how it changes in the computation of CRC ? –  www.sapnaedu.in Sep 20 '11 at 22:51
1  
ross.net/crc/crcpaper.html –  Dilip Sarwate Sep 21 '11 at 0:47
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.