Cyclic Redundancy Codes summary
By Jamil Khatib
All communication systems try to make sure that the transmitted messages reach the destination without any problem. So they intend to implement different algorithms in order to satisfy this requirement. One of the options is to encode the message in a way that enables the receiver to check the corrupted messages, example of such coding is the CRC.
Data storage devices must also prevent any corruption of its data. The best choice for this problem is to use data redundancy, which costs a lot. So instead of that, data can be encoded using redundant codes in order to detect the corrupted data and the CRC is the one of the most common codes that is used in such cases.
CRC stands for Cyclic Redundancy Check. Which means that is based on cyclic algorithm that generates redundant information.
The CRC performs a mathematical calculation on a block of data and returns information (number) about the contents and organization of that data. So the resultant number uniquely identifies that block of data. This unique number can be used to check the validity of data or to compare two blocks. So this approach is used in many communication and computer systems to ensure the validity of the transmitted or stored data.
In general CRC codes are able to detect:
One approach in of error checking is to append the sum value of all message bytes to the end of the message. This sum can identify the message and changes in its contents. On the other hand, if there is more than one change one that adds up a value and one subtracts one in a way that the sum remains the same, so it can not be used to detect errors. The same can happen if the check sum is changed with the same value as the message.
4. CRC idea
The main idea of CRC is to treat the message as binary numbers, and divide it by fixed binary number. The remainder from this division is considered the checksum. The recipient of the message performs the same division and compare the remainder with the "checksum" (transmitted remainder).
5. Theory of operation:
As stated in the previous section, the CRC is a simple binary division and subtraction. The only difference is that these operations are done on modulo arithmetic based on mod 2. For example the addition and subtraction are replaced with XOR operation that do the sum and subtraction without carry.
Polynomial concept
The CRC algorithm uses the term polynomial to perform all of its calculations. This polynomial is the same concept as the traditional arithmetic polynomials. The divisor, dividend, quotient, and remainder that are represented by numbers are represented as polynomials with binary coefficients.
For example the number 23 (10111b) can be represented in the polynomial form as:
1*x4 + 0*x3 + 1*x2 + 1*x1 + 1*x0
or
x4 + x2 + x1 + x0
Note the binary representation of the number (10111).
This representation simplifies the traditional arithmetic operations (addition, multiplication, etc…) that are all done on normal algebraic polynomials.
If we can assume that X is 2, then the operations are simplified more and some because some terms can be canceled. For example the term 3*x3 is represented as 24 in normal number representation and 24 = 16+8 which is x4+x3 in polynomial representation.
Generator polynomial:
In order to do the CRC calculation; a divisor must be selected which can be any one. This divisor is called the generator polynomial. Even though, some polynomials became standard for many applications. Polynomial selection is behind the scope of this summary.
One of the most used terms in CRC is the width of the polynomial. This width is represented by the order of the highest power in the polynomial. The width of the polynomial in the previous example is 4, which has 5 bits in its binary representation.
Since CRC is used to detect errors, a suitable generator polynomial must be selected for each application. This is because each polynomial has different error detection capabilities.
CRC algorithms are commonly called after the generator polynomial width, for example CRC-16 uses a generator polynomial of width 15 and 16-bit register and CRC-32 uses polynomial width of 31 and 32-bit register.
Common used polynomials:
|
No. of bits |
Polynomial |
Name |
|
16 bits: |
(16,12,5,0) |
X25 standard |
|
(16,15,2,0) |
CRC-16/ CCITT |
|
|
32 bits: |
(32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) |
Ethernet, ATM, CRC-32 |
To Summarize:
The data D is multiplied by Xn and divided by the generator polynomial G, the quotient Q is discarded and the Remainder R is considered the check sum. On the other side, the data stream D is multiplied again by Xn and the check sum (CRC) R is added to it (normally it come with the stream) and the whole result is divided by G again. The result now should be zero for valid data.
This operation can be described by the following equation:
(Xn*D)+R = (Q*G)+0
6. How Do CRC works
Transmitter calculation
The transmitter can append zeros to the end of the message (LSB), perform the division and find the remainder and appended it to the original message.
Receiver calculation
The message receiver can do one of the followings:
Separate the message and checksum. Calculate the checksum for the message (after appending zeros) and compare the two checksums.
Checksum the whole message including the CRC (without appending zeros) and check if the new CRC comes out as Zero.
7. Implementation:
CRC has two main implementation techniques:
Straightforward:
This approach is a direct mapping for the CRC algorithm.
In fact this approach does not use standard microprocessor divide instruction because 1. We need xor based division (no carry in addition or subtraction) 2. The dividend (the message) can be very large and behind the processor support.
This approach is relatively low speed and consumes very small resources
This implementation is described in PAINLESS GUIDE TO CRC as:
Note: The register holds the remainder only after the last bit of the message gets out of it.
This algorithm is done by the long division
|
Dout |
Register Bit |
Å |
Comment |
|
0 |
0 |
0 |
Pass Register bit |
|
0 |
1 |
1 |
|
|
1 |
0 |
1 |
Xor with Poly |
|
1 |
1 |
0 |
This approach can be implemented directly using Linear-feedback shift registers (LFSR) where the division is performed by left shifting and subtraction by XOR.
Parallel Implementation:
In real world the serial approach (bit-by-bit) calculation is not acceptable for many applications that requires high performance or the smallest processing word size is more than a bit For that reason parallel implementation is needed.
Parallel implementation can be done by entering the data word to the CRC and perform the serial shift and xoring the bits in parallel. Simply it calculates all xor combinations as if a single bit shifting is done on the data and CRC register.
This implementation is best described in the cypress CRC document
Look-up table based:
This approach is based on pre-calculating the CRC for all input combinations.
This approach is best described in "A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS"
References:
http://www.ee.uwa.edu.au/~roberto/teach/itc314/http://www.lucent.ca/fpga/Downloads/crc.pdf