Technology News as it Happens.

What is Cyclic Redundancy Check (CRC)

November 2, 2012 10:11 am

CRC has been an integral part of the computer industry for quite some time. The actual implementation of CRC is quite simple, especially from within 4th Dimension. However, the concept behind CRC is less straightforward.

 

What is CRC?

 

A CRC performs a mathematical calculation on a block of data and returns a number that represents the content and organization of that data. The idea is to have the CRC return a number that uniquely identifies the data. We can think of CRC as being the operation that generates a “fingerprint” for a block of data. The actual number, or fingerprint, that is used to identify the data is called a checksum. The following picture, shows the flow of a CRC.

 

By comparing the checksum of a block of data to another block of data’s checksum, we can determine if the data is an exact match or not. CRCs are mostly performed when transferring files from one location to another. Depending on the medium by which files are transferred, errors to data may occur during the transmission. In mission critical applications, it may be especially important to know that files are valid and reliable. Most networking protocols use CRCs to verify data received is the same as the data that was sent.

Verifying transmitted information, sending and receiving records, modifying files and records, and verifying emails between 4D databases, are a few of the reasons for which a 4D Developer would want to use CRC. Knowing how a CRC is implemented will also pave the way to understanding how to incorporate encryption into our databases.

Polynomials

CRC arithmetic is referred to in the mathematical world as “polynomial arithmetic module two”. CRC arithmetic addresses basic mathematical operations on binary numbers. CRC arithmetic does not have any carry or borrow operations, which makes calculations on large amount of data very efficient. Fortunately, adding, subtracting, multiplying, and dividing binary numbers is very straightforward.

Addition and subtraction in CRC arithmetic are identical. The bitwise operator XOR is equivalent to adding or subtracting. We know how to XOR values, which means you know how to add and subtract in CRC arithmetic. The following example is nothing more than two binary numbers being XORed.

Multiplication in CRC arithmetic is straightforward as well. The steps for CRC multiplication are the same as in regular long multiplication, with two specific rules: calculations are OR (not XOR) and there are no carries. We will not be using multiplication in CRCs, however, here is an example.

 

CRC division is more difficult to grasp because you must know when one binary number goes into another. A number is only as significant as the position of the leftmost 1 bit. For example, 0110 is less than 1001. The following example is actually a simple representation of a CRC. The remainder would be the actual checksum for the data.

 

 

Role of Divisor

we can choose a divisor that is to be used in the CRC calculation. The divisor in a CRC calculation is called the polynomial, or poly. In the case of CRCs, the poly is nothing more than a binary number. It gets its name because the number represents a polynomial with binary coefficients. For example:

1*(x7)+0*(x6)+0*(x5)+1*(x4)+1*(x3)+0*(x2)+1*(x1)+1*(x0) = 10011011

Polys come in various sizes. The more popular polys use 16 or 32 bit lengths. The length of a poly is determined by the position of the leftmost 1 bit.

There are many popular polys in use, or you can create your own. However, some polys are better at identifying errors or differences in data than others. With this in mind, it’s a good idea to use one of the more time-tested polys than one you create.

Role of Remainder

Our CRC word is simply the remainder, i.e., the result of the last 6-bit exclusive OR operation.  Of course, the leading bit of this result is always 0, so we really only need the last five bits.  This is why a 6-bit key word leads to a 5-bit CRC.  In this case, the

CRC word for this message string is 00010, so when I transmit the message word M I will also send this corresponding CRC word.When you receive them you can repeat the above calculation on M with our agreed generator polynomial k and verify that the resulting remainder agrees with the CRC word  

A popular 32 bit polynomial is (0x04C11DB7), which is used in PKZip, Ethernet and FDDI. By searching on the Internet, you can find more polys that you can use in your CRCs.

CRC16

Example:

Initial CRC value: 1111 1111 1111 1111
Byte to process: 0101 1010

 

The Most used CRC polynomials

The 16-bit polynomial is known as the "X25 standard", and the 32-bit polynomial is the "Ethernet standard", and both are widely used in all sorts of applications.  (Another common 16-bit key polynomial familiar to many modem operators is 11000000000000101, which is the basis of the "CRC-16" protocol.)  These polynomials
are certainly not unique in being suitable for CRC calculations, but it's probably a good idea to use one of the established standards, to take advantage of all the experience accumulated over many years of use.

Following is a list of the most used CRC polynomials

  • CRC-12: X^12+X^11+X^3+X^2+X+1
  • CRC-16: X^16+X^15+X^2+1
  • CRC-CCITT: X^16+X^12+X^5+1
  • CRC-32: X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X+1

The CRC-12 is used for transmission of streams of 6-bit characters and generates 12-bit FCS. Both CRC-16 and CCRC-CCITT are used for 8 bit transmission streams and both result in 16 bit FCS. The last two are widely used in the USA and Europe respectively and give adequate protection for most applications. Applications that need extra protection can make use of the CRC-32 which generates 32 bit FCS. The CRC-32 is used by the local network standards committee (IEEE-802) and in some DOD applications.

32-bit CRC

The ITU-TSS has defined a 32-bit CRC too. Its formula is: G(x)=x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1=0

Related Technology News:


Be Sociable, Share!

yasir

Syed Yasir Hashmi is a tech guru working in the industry for the last 15 years.

Leave a Reply


Latest Technology News

  • Technology Top News

    Most Stylish Phone Ever!!

    Samsung is continually improving upon the quality of its smartphone displays, and the screens on the Galaxy S6 and Galaxy S6 take things to new heights. In fact, according to extensive testing from DisplayMate, one of them has the best smartphone display yet. The key element for a great smartphone has always been a truly innovative and top performing display, and the best leading edge smartphones have always flaunted their super high tech displays. It’s the display performance that determines […]

    Read more →
  • Technology Top News Out of the Blue!!

    Out of the Blue!!

    NASA has been working on a plan for months to create an air traffic control system for drones to make sure the flying machines don’t crash into things like people and planes. Now that plan includes trying to develop a reliable system so people can fly drones remotely. It’s a response to the massive wet blanket the Federal Aviation Administration’s rules threw on the country’s budding aerial industry: that drone operators need to have a line of sight to their […]

    Read more →
  • Technology Top News

    Team Work makes it a dream work.

    Japan’s big three automakers will team up with electronics giants and the government in a bid to propel the country into the front ranks of self-driving car technology, officials and local media said Thursday. “We will set up a so-called self-navigation business conference so that we can discuss what measures we need to take,” a land and transport ministry official said, adding that they have yet to set the agenda. The Nikkei business daily said the government will invite Toyota, […]

    Read more →
  • Technology Top News Technology at its Best

    Technology at its Best

    The new Whatsapp voice feature might bring them into competition with Skype and Viber, both of which offer online voice calling services.Some of its millions of users report their account is allowing them to make regular voice calls.Voice calling the killer Whatsapp feature that’s making Indian telecom service providers shake in their boots has been ’round the corner’ for a long time now. But it looks like it’s finally about to land on our phones.The voice calling feature in Whatsapp […]

    Read more →
  • Technology Top News Motorola E series launching

    Motorola E series launching

    Motorola today launched the 3G and 4G variants of the second-generation Moto E smartphone in India. The Lenovo-owned manufacturer priced the 3G model, which will be up for sale from March 11, at Rs 6,999. The company, however, did not reveal the price of the 4G version, but said that it will bring the smartphone to the market in the next couple of months. The 3G version of second-generation Moto E is powered by a 1.2GHz Qualcomm 200 quad-core processor, […]

    Read more →
  • Technology Top News Whats APP calling feature propelling in Saudi Arabia

    Whats APP calling feature propelling in Saudi Arabia

    Meanwhile, the Communication and Information Technology Commission had decided to lower call rates for mobiles and landlines by 40 per cent in anticipation of this change. This move was presumed to encourage mobile phone users to talk for longer durations. But this step will also establish strong competition between the traditional call system and free calls as part of social networking apps on smart phones. WhatsApp’s one of the most popular messaging website, which has recently started rolling out calling […]

    Read more →
  • Technology Top News

    Smart Phone at very much affordable rates.

    Xolo is expanding its smartphone portfolio with new budget phones to attract Indian consumers. The latest in the company’s lineup is the Xolo A1010, duly fitting into the entry-level smartphone category. The latest Androidpowered smartphone is low on specs but Xolo justifies the minimalism with its affordable price tag. Xolo Launches New Good-Looking Budget Phone With 5-Inch Display For Just Rs. 5,499Xolo A1010 Is The New Budget Android Phone For Rs. 5,499 HomeShop18 Product Listing Xolo A1010 is a dual-SIM, […]

    Read more →