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!

Leave a Reply


 

Latest Technology News

  • Top News new android virus proving to be deadly hijacks your phone when it is off

    new android virus proving to be deadly hijacks your phone when it is off

    New android malware has been found now which can bitterly destroy tour mobile device when it is off and can bitterly perplex you.Now, new android virus has been scene on the go and is going to rattle your mobile phone in every possible way it wants But because of the new way it works, it is really tricky. You might shut off your device in a very relaxed manner, and the hackers who have laid the foundation oh this deadly […]

    Read more →
  • Top News

    Japan companies to jointly work on self-driving car technology

    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 Unverified sims to be blocked by PTA on Friday

    Unverified sims to be blocked by PTA on Friday

    PTA is telling cellphone users they must register their identities by entering fingerprints in a national database, a move the government sees as a way to combat terrorism but one that has privacy experts wary.Mobile phone users have a deadline this week to match their SIM cards with their fingerprints that will be collected and stored by PTA otherwise their unverified sims are going to be blocked. Pakistan Telecommunication Authority had firstly given the dead line of 26th February but […]

    Read more →
  • Top News you tube introduces app for kids much to the delight of parents.

    you tube introduces app for kids much to the delight of parents.

    Youtube has launched a service called YouTube Kids, a new version of the internet’s leading destination for video aimed squarely at children.this app is blessing in disguise for parents who had the fear that their children have been exposed to objectionable content. Reviews regarding the app have generally been positive but the only cause of concern for parents is that password is required to unlock the app because once children read the password it would be easy for them to […]

    Read more →
  • Mobile Phones Top News

    Galaxy core prime to be released on February 26

    Verizon will launch the Samsung Galaxy Core Prime online on February 26 . Starting March 5, the handset will also be available in stores. Originally announced in October, Samsung’s Galaxy Core premium features are a 4.5-inch display with only 480 x 800 pixels, and is powered by a quad-core Snapdragon 410 processor. Other features include a 5 MP rear camera, 2 MP front-facing camera, 1 GB of RAM, and 8 GB of expandable storage space. A 2000 mh battery with […]

    Read more →
  • Top News Mercedes-Benz new model C 450 AMG 2016

    Mercedes-Benz new model C 450 AMG 2016

    The C450 AMG is billed as a more affordable alternative to the C63. It gets a look of its own that is characterized by a single-slat radiator grille with small chrome inserts, a less aggressive front bumper, a gray air diffuser out back and model-specific 18-inch alloy wheels. The C450 power has been tossed up and makes it a car of high worth. Its an amazing stylish and luxurious car.Inside, the C450 comprises of elegant the seats, the dashboard, the […]

    Read more →
  • Top News

    AVG unveils new virus only affects devices running Android 5.0

      Hackers are starting to target our mobile smartphones and tablets more and more these days. And that’s really no surprise. Because we do so much on our gadgets, from banking to email, smartphones and tablets are a goldmine for hackers intent on ripping you off. Now, security researcher AVG has just spotted a new mobile gadget virus. But because of the new way it works, it is really tricky. You might shut off your devive in a very relaxed […]

    Read more →