Cyclic Redundancy Check

There are multiple ways to complete a data transmission. The most popular involves the use of twisted copper pairs and the Internet. This uses analog data transmission. and problems can occur, caused by magnetic interfaces, connection errors and many other things.

The newest technology involves the use of optics, with interoffice fiber trunks that transmit digital codes. This assures a really low error rate; however, considering that this technology is still quite expensive, it will probably be a long time before we switch to this all over the world.

Then again, there is the wireless data connection so popular today with the rise of notebooks. This relies solely on analog data transmission, and many other frequencies can occur at the same time we transmit our data. This will lead, of course, to corrupted data.

Due to this, we need to come up with some error correction and detection methods. The error correction part calls for a whole lot of effort and resources. Therefore, it is only recommended for use in places where transmitting another package of the initial data implies heavy penalties or (just as easily) could be corrupted. This is the case with a wireless connection. I will deal with this in a future article.

Nevertheless, the error detection part is more straightforward and can be implemented in hardware effortlessly with the help of some linear feedback shift registers. As a result, most of the protocols used today implement this at a hardware level. I will present this too; however, before we reach that point, you need to learn the idea behind the classic algorithm.

Error detecting codes

Use error detecting codes whenever occasional errors are present and retransmitting the data is easier than dealing with the error and trying to correct it. Error detecting usually implies the addition of few extra bits after the data you want to transmit anyway. This transmits at some level the “traits” of your data to the receiver's side. There we can recalculate this “trait.” If the transmitted and the calculated “traits” are the same, we can conclude with a high probability that our data went through without an error.

We use the hamming code for error correction. To correct a bit corruption of d length we need a distance between errors of 2*d+1. Therefore, to correct one bit of error inside a 1000-bit long piece of data we need 10 check bits, summing to 10,000 bits to send. To detect the same error, a single bit will suffice, and we come up with 2,002 bits sent with the retransmission included.

For simple error detection, a few bytes will suffice in any case. For example, the simple Ethernet uses just four bytes for transmitting up to 1500 bytes. We call this appended data (or “trait” of the sent data) the checksum. Of course, there is a small probability that the sent checksum will be corrupted. However, as the checksum is just a few bits, the chances are slim. If for some reason this happens often, you just need to make the checksum smaller in size and send smaller packages.

The acronym for this type of correction is CRC (or Cyclic Redundancy Check) and has the structure:

<Original intact message><Checksum calculated>

Now the question is, how can we sum up, in just a few bytes, the structure of a data package? An initial approach is to use the parity bit method and append this at the end. Every piece of data inside our computers is coded into a binary system with ones and zeros. The parity bit signals whether, within the records we send, the number of ones present is odd or even. According to our network protocol use, we know the length of the data we send/receive. Once we have this data, we can signal the change of any odd bits in our sent package.

Nevertheless, most of the time errors in real life occur with burst rates. This means that multiple bits (one after another) change. For instance, on a wireless connection, if noise intervenes due to a nearby mobile telephone being activated, this noise is present for a longer time than it takes for a single bit to make its way through our network. As a result, multiple bits will change against our will. To detect changes like this, we need stronger algorithms.

A more evolved approach is to add our package content byte by byte and make a module division with 256. This way, we will get a byte-long checksum. While calculating this, we will get the impression that we use every bit of every byte to affect the result. Nevertheless, the chance that an error will pass by without us noticing it is still one out of 256. We can strengthen this by sending a two-bytes-long checksum, as this will lead to a 16-bit register that concludes with a modulo 65536.

The golden path: division

The real drawback to the sum method is that one incoming bit affects only a single bit of the checksum, and not the entire registry. A strong checksum has two characteristics: width and chaos. The width refers to the fact that with the increase of the bits used for the width of the checksum, the chances for unobserved errors are slimmer and slimmer. The chaos part says that any input bit/character we want to send should affect as many bits in the checksum as possible.

This brings us to a solution used widely wherever data transmission and error checking is done. The theory is simple. Treat every package you want to send as an enormous binary number. If your package consists of multiple bytes, append one after another. Now divide this number with another binary number (using module two division) and make the remainder the checksum.

To find out why this works, we need to look at its mathematical roots. We can treat the ones and zeros inside the bit sequence as the coefficients of a polynomial. The k-th bit is the coefficient of the x on the k-th power. A polynomial with x on the n-th power has a degree of n+1.

Let there be f, the function assigned this way for our data package, and g, the function assigned to the binary number with which we divide. This second polynomial is the generator polynomial.

There exists a modulo two arithmetic under this algebraic field. This arithmetic implies that we do every operation (addition, subtraction, division) just as usual (using the binary number operations), however there are no borrows and carries. This simplifies operations a lot, as we can transform the operation to an XOR of the corresponding bits in the case of addition and subtraction. As for the division, we use the same method we learned in the first class, with the modification that we use modulo two subtractions.

The following image makes the subtraction and addition clear:

(Image courtesy of Andrew S. Tanenbaum - Computer Networks)

In the transmitted package, the checksum is included. Moreover, if you divide by a given generator polynomial of power k-th, we can agree that the highest coefficient will be one. Otherwise, the polynomial would be just k-1-th power. Therefore, with a generator polynomial of k-th power, a k width checksum is generated.

Concluding to the result

We can also observe that, given the nature of modulo two division, appending any number of zeros to the end will not change the remainder.

A+0=0+A=A

Therefore, we may freely add k zeros to our data and at the end, replace these zeros with the checksum. This way our data package will have a consistent length. Both the sender and the receiver will use the same generator polynomial.

At the other end we may save the checksum, replace it with zeros, and see if, executed once again, the checksum calculation operation raises the same checksum. Alternatively, choose the simpler method: just call the operation for the data itself and see if the resulting checksum is zero. To understand this, look at the basic division rule:

Dividend = quotient * divisor + remainder

Now we transform this to the following form:

Dividend - remainder = quotient * divisor

We make the subtraction with the appending (addition) of the checksum at the end. Nevertheless, as the addition in modulo two arithmetic is the same as subtraction, in fact, we resolve this step once we add the checksum. Therefore, what we send, in fact, is the quotient multiplied by the divisor. This is obviously divisible with the divisor (that is the generator polynomial).

Calculating a checksum and creating the final package is illustrated in the following image:

(Image courtesy of Andrew S. Tanenbaum - Computer Networks)

There are better and worse generator polynomials. Finding this is the goal of an entire field of science, and I will not go into it. Generally, the polynomials we use will detect all odd numbers of bit errors and burst errors of length n (where n is the width of the checksum). Instead of writing up the polynomial from scratch as a mathematical function, I will simplify it by pointing out at what power the coefficient is one.

One way to note the generator polynomial in the upper division is (4, 1, 0). Using this notation system, the table below presents a few good polynomials:

This will be all for today. Join me next time when we will get practical and implement all this in C code, so you can use it inside microcontrollers or programs where you want to generate a checksum for some long binary sequence. Meantime, if you have any questions on what I've presented so far, feel free to ask them here on the blog.

If you have other specific questions, something that does not fit here, you can join our friendly ever-growing forum at the DevHardware and ask our experts there. Thank you for reading up to this point and remember to rate this article as you consider fit. Until next time: Live With Passion!