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*(x⁷)+0*(x⁶)+0*(x⁵)+1*(x⁴)+1*(x³)+0*(x²)+1*(x¹)+1*(x⁰) = 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:

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)=x²⁶+x²³+x²²+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x¹+1=0

Related Technology News:

• What is Commercial off the Shelf (COTS)?
• Alternate mark inversion (AMI)
• Encoding Schemes
• Differential Manchester encoding
• Component Based Software Engineering (CBSE)

Be Sociable, Share!

•