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

    Which Mobile Payment Option is Best for You?

    So, you’re ready to go mobile. Whether you’re interested in replacing an old-school cash register with a sleek iPad, want to be able to take your business to farmer’s markets and trade shows, or are just finally getting that food truck up and running, there are plenty of options to choose from when it comes to mobile payment solutions. Smartphone Card Readers   This is the most well-known mobile payment option, and probably the most widespread. Business Insider reports that […]

    Read more →
  • Top News

    New features of Iphone 6 and Iphone 6 plus

    Apple launched iphone 6 in two new models iphone 6 and iphone 6 plus. The release dates for these smartphone are different in different regions. You’ll be able to get your hands on the iPhone 6 on September 19th in the UK. That’s the same date as the US, so there’s no waiting around for a delayed UK release. You’ll be able to get iOS 8 for any existing devices, on 17th September. You’ll be able to pre-order the iPhone 6 […]

    Read more →
  • Top News

    Rackspace is rumored to be available for purchase

    In May news surfaced that Rackspace had employed a venture saving money firm to assess alternatives for the organization, including a conceivable deal. Presently, reports demonstrate that Centurylink may be intrigued. Bloomberg reported today that Centurylink is “looking to gain” Rackspace, refering to “individuals acquainted with the circumstances.” There has been no official word from Rackspace or Centurylink about the reports – representatives for each one organization declined to remark, yet normally organizations don’t examine merger and securing bits of […]

    Read more →
  • Top News

    Facebook passed daily one billion videos views mark

    For quite a while the thought of auto-play in-food feature ads on Facebook appeared to be a shocking thought. What preferred approach to bother clients over to have irregular features playing everywhere that they have no enthusiasm toward? All things considered, Facebook thought of a virtuoso answer for that issue: quiet them, and afterward permit clients to unmute the features they needed to see. The arrangement has worked like gangbusters and now the organization has been seeing some exceptionally noteworthy […]

    Read more →
  • Technology Top News

    Charge your IPHONE through solar panel glasses:

    A solar panel is a set of solar photovoltaic units electrically connected and fixed on a subsidiary structure. A photovoltaic unit further is a packaged and associated with solar cells. All of us are well aware with the usage of solar panels, it uses to run cars, generate electricity, heat up pool’s water, use in calculators and watches and in lot of other things. Now Sayalee Kaluskar from Mumbai, India introduces a remarkable usage of solar panel with the collaboration […]

    Read more →
  • Top News

    NSA installed spies in virtual Games

    Games “are built and operated by companies looking to make money, so the players’ identity and activity is tracked,” said Peter W. Singer of the Brookings Institution, an author of “Cybersecurity and Cyberwar: What Everyone Needs to Know.” “For terror groups looking to keep their communications secret, there are far more effective and easier ways to do so than putting on a troll avatar.” The surveillance, which also included Microsoft’s Xbox Live, could raise privacy concerns. It is not clear […]

    Read more →
  • Top News

    Discovery of DNA From Ancient Site in Spain Reshapes Human Family Tree

    The term Denisovan, distinct to both modern humans and Neanderthals, was coined just three years ago based on some limited tooth morphology, but predominantly on the distinct DNA sequenced from a 41,000 year-old toe bone found in central Asia. Since then, anthropologists have theorized that Denisovans were contemporary Asian “cousins” to Neanderthals found in Europe and the Middle East, and to modern humans who were already living throughout Africa and were venturing out of the continent for the first time […]

    Read more →