Talk:Cyclic redundancy check/Archive 1

This page is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Abstract Algebra

I removed "polynomial" remarks as they are derisive and I am very familiar with abstract algebra including ring theory.

Errors caused by noise

I am taking a class on networking, and they use noise as the background noise such as white noise. They keep this separate from things such as spikes and cross-talk which they credit more with error causing conditions. Errors commonly come in bursts, so white noise wouldn't cause these predominant errors. I would suggest that the noise link at the least point to Noise_(disambiguation) and at best point to a stub of electronic noise such as Impulse noise(spikes), Cross-Talk, Echoes, Attenuation, Intermodulation noise, Jittre, and Harmonic distortion. My two cents...—Preceding unsigned comment added by 140.158.132.252 (talk) 17:30, 24 February 2009 (UTC)

This page should be renamed to Cyclic Redundancy Codes

CRC does not mean Cyclic Redundancy Check BUT Cyclic Redundancy Codes. According to this anyway http://www.reversing.be/article.php?story=20061209172953555 at around the top.

"A lot of people think CRC is short for Cyclic Redundancy Check. If indeed CRC is short for Cyclic Redundancy Check then a lot of people use the term incorrect. If it was you could not say 'the CRC of the program is 12345678'. People are also always saying a certain program has a CRC check, not a Cyclic Redundancy Check check. Conclusion: CRC stands for Cyclic Redundancy Code and NOT for Cyclic Redundancy Check."

This is what I also thinking

194.237.142.7 (talk) 16:40, 12 December 2007 (UTC)

~~(reply, I have no clue which codes I can use to fix the layout for that.)~~

Nevermind, I found it.

"People are also always saying a certain program has a CRC check, not a Cyclic Redundancy Check check."

Though strictly correct, this does not mean it is always true. For example, most people talk about their PIN-code, their Personal Identification Number Code, which is kind of silly aswell. Nevertheless, I have yet to hear someone talk about his (or her) PIN.

// Ilyushin

Reference table needs some additional data

Please provide reverse representation for the crc-24 I added to the table, I didn't trust my abilities with hex enough to do it myself. It would look good if someone who knows how to do it also adds the Normal of reciprocal representation.

Table is missing ANSI X3.66 CRC -- anonymous coward

CRC for CAN bus

This should be 0x62CC according to the Koopman paper

-> As you can see in another section of this page, Koopman uses a different representation not given in the table. I've calculated both kinds of hex, Koopman and normal, for some polynoms given here inclusive CAN, and my results verified that the information in this table is correct.

Misc stuff added at the start

Please add a subject heading when starting a new subject - thanks!

I appreciate whomever italicized "intentionally" when referring to how CRC cannot be relied on for data integrity. It helped me clarify that, for personal file checks (for backups) a CRC will suit my needs just fine. --John 00:25, 1 Feb 2005 (UTC)John

Thanks to the authors of this page. You explained this concept when google failed me!

Where are the off-the-shelf crc calculators? downloadable?

I need more info on the polynomials. I don't completely understand, why 0x04C11DB7, how do you get this number? What numbers needs actually to be stored in the lookup table and how to calculate them?? How long is a lookup table for CRC32 and how do you know that?

This article is rather moderate in comparison to its german counterpart: http://de.wikipedia.org/wiki/Cyclic_Redundancy_Check

Speed of a lookup table

It's not actually 8 times as fast (would an "eight-fold increase" mean nine times faster?) if you use very fast CRC code. This seems to be the fastest on a PowerPC without resorting to tables, presumably because it has few branches. The fastest code using tables is only a little over 4 times faster (though it IS eight times faster than looping through every bit, but that's really stupid code).

uint32_t crc32_2(unsigned char const * data, size_t length) {
 uint32_t poly = 0xEDB88320, crc = -1; 
 do {
  crc = crc ^ *data++;
  crc = (crc >> 1) ^ (poly *(crc & 1));
  crc = (crc >> 1) ^ (poly *(crc & 1));
  crc = (crc >> 1) ^ (poly *(crc & 1));
  crc = (crc >> 1) ^ (poly *(crc & 1));
  crc = (crc >> 1) ^ (poly *(crc & 1));
  crc = (crc >> 1) ^ (poly *(crc & 1));
  crc = (crc >> 1) ^ (poly *(crc & 1));
  crc = (crc >> 1) ^ (poly *(crc & 1));
 } while (--length);
 
 return ~crc;
}

--Elektron 19:51, 2004 Jun 16 (UTC)

Just for comparison, here's the standard table code:

uint32_t crc32_3(unsigned char const * data, size_t length) {
 uint32_t crc = -1; 
 do {
  crc = crc ^ *data++;
  crc = (crc >> 8) ^ crc32_table[crc & 255];
 } while (--length);
 return ~crc;
}

It can also be done not quite as fast using a much smaller table:

uint32_t crc32_4(unsigned char const * data, size_t length) {
 uint32_t crc = -1; 
 do {
  crc = crc ^ *data++;
  crc = (crc >> 4) ^ crc32_table[crc & 15];
  crc = (crc >> 4) ^ crc32_table[crc & 15];
 } while (--length);
 
 return ~crc;
}

For speedier lookup table implementations for CRC-32 look at the current zlib version, which is faster than the Algorithm 4 in the references. Both process 32-bits at a time with an algorithmic loop unrolling.

Note that the CRC-16-IBM 256 entry table can be replaced by a closed form expression. The original assembler MS-DOS kermit used this (I think) and the HP150 ROM CRCs also use it.

CRC-16-IBM         8005                     Reversed          C0C1
                        **           *  *  ***      **     *
                         111111           | 111111
                         5432109876543210 | 5432109876543210
                                         -+-
crc_table[1 << 7]  8303  7     77      77 | 7 7            7  A001
crc_table[1 << 6]  8183  6      66     66 | 6666           6  F001
crc_table[1 << 5]  80C3  5       55    55 | 55 55          5  D801
crc_table[1 << 4]  8063  4        44   44 | 44  44         4  CC01
crc_table[1 << 3]  8033  3         33  33 | 33   33        3  C601
crc_table[1 << 2]  801B  2          22 22 | 22    22       2  C301
crc_table[1 << 1]  800F  1           1111 | 11     11      1  C181
crc_table[1 << 0]  8005  0            0 0 | 00      00     0  C0C1
                                          +
uint16_t crc_table(uint16_t tab_x)        | uint16_t crc_table(uint16_t tab_x)
{                                         | {
   uint16_t tmp =                         |   uint16_t tmp =
      (tab_x ^ (tab_x << 1)) << 1;        |      (tab_x ^ (tab_x << 1)) << 6;
                                          |
   return                                 |   return
      (odd_parity(tab_x)                  |      (odd_parity(tab_x)
      ? tmp ^ 0x8003                      |      ? tmp ^ 0xC001
      : tmp);                             |      : tmp);
}                                         | }

Don't know if anyone used the CCIT version. Reversed wrong, probably.

CRC-16-CCIT        1021                     Reversed          1189
                        *   *      *    * |*   *   **   *  *
                         111111           | 111111
                         5432109876543210 | 5432109876543210
                                         -+-
crc_table[1 << 7]  9188  7  7   77   7    | 7    7      7     8408
crc_table[1 << 6]  48C4   6  6   66   6   |  6    6      6    4204
crc_table[1 << 5]  2462    5  5   55   5  |   5    5      5   2102
crc_table[1 << 4]  1231     4  4   44   4 |    4    4      4  1081
crc_table[1 << 3]  8108  3      3    3    | 3   33   3  3     8C48
crc_table[1 << 2]  4084   2      2    2   |  2   22   2  2    4624
crc_table[1 << 1]  2042    1      1    1  |   1   11   1  1   2312
crc_table[1 << 0]  1021     0      0    0 |    0   00   0  0  1189
                                          +
uint16_t crc_table(uint16_t tab_x)        | uint16_t crc_table(uint16_t tab_x)
{                                         | {
   uint16_t tmp =                         |   uint16_t tmp =
      tab_x ^ (tab_x >> 4);               |      tab_x ^ ((tab_x & 0xF) << 4);
                                          |
   return                                 |   return
      (tmp                                |      ((tmp >> 4)
      ^ (tmp << 5)                        |      ^ (tmp << 3)  
      ^ ((tmp & 0xF) << 12));             |      ^ (tmp << 8));
}                                         | }

RDBrown 22:34, 14 February 2006 (UTC)

Stuff to do

This page needs improvements:

More discussion of the information theory of CRCs and what polynomials have to do with anything.
A code example for the version with the lookup table.
A general description of the characteristics of CRCs, such as how many erroneous bits they can reliably detect and within what length.
The effects of the factors of the CRC polynomial, and the difference between irreducible and primitive.
The equivalence of parity and the CRC polynomial x+1
Flesh out the section on the application of CRCs compared to cryptographic hashes and why one would choose one over the other.
Explain how hardware CRC calculators are implemented using shift registers.
Why certain polynomials work better than others.
How a CRC (which implements error detection) compares with error correction.

I agree that all of these should be, if not explained in detail, at least briefly explained and linked to an article that does explain them in more detail. Deco 02:32, 24 Feb 2005 (UTC)

Need to add stuff about collisions. Many duplicate file finders use CRC32 + file size, what is the probability of two files having the same CRC32 result, and same file size, but actually be different files would be interesting to add. --ShaunMacPherson 11:01, 15 May 2005 (UTC)

p=2^-32, for two files of the same size more than 32 bits long. -- The Anome 11:09, May 15, 2005 (UTC)

Wrong algorithm?

Recently an anon stated that the algorithm shown is wrong. While I doubt that, are we really sure? Acedemic sources? Shinobu 18:24, 26 October 2005 (UTC)

I believe it is, indeed, the wrong algorithm. The Pseudocode states that

   if most significant bit of shiftRegister xor bitString[i] = 1 {
       shiftRegister := (shiftRegister left shift 1) xor polynomial
       least significant bit of shiftRegister = 1
   } else
       shiftRegister := (shiftRegister left shift 1)

I believe this should say

   if most significant bit of shiftRegister = 1
       shiftRegister := ((shiftRegister left shift 1) xor polynomial) or (the bit of bitString at position i)
   else
       shiftRegister := (shiftRegister left shift 1) or (the bit of bitString at position i)

My references? The "SIMPLE" algorithm at http://www.ross.net/crc/download/crc_v3.txt. Also, http://wwwdsa.uqac.ca/~daudet/Cours/Reseaux/DOCUMENTS/repertoire43/crc16-ccitt.htm talks about "good" and "bad" implementations of CRC, and the algorithm (currently) presented on Wikipedia seems to be the "bad" implementation. User:Chrisobyrne 2005 Dec 15 15:22 UTC.

In that case, please edit away. Shinobu 16:25, 15 December 2005 (UTC)

I suspect the published algorithm works only for irreducible polynomials, whereas the algorithm in crc_v3.txt also works for composite polynomials. a_caspis@yahoo.com, 26 May 2006

I did tests with CRC 32 with a dull implementation (with mathcad) and the first algorithm is really working, could it be that CRC-32 is different from standard ?!?

Anyway, if you want to verify it, here is a pdf of the matchad document that i made to test everything: http://en.wikipedia.org/wiki/Image:CRC32-Algorithm-mathcad.pdf of course you can also ask for the mathcad document if you have mathcad 11 JimKi 13:55, 5 January 2006 (UTC) e-mail: jimki-removethis-@hotmail.com

The 2 examples below show that the actual algorithm shown on the main page is wrong i'm editing this

The algorithm on the main page is correct. I found a reference ITU-2066, section A.2.7.

It's written in standardese, but it makes it clear that the initial value of the shift register is added (XORed) with the message (as the algorithm on the main page does), not prepended to it (as the alternate algorithm does).

I've since found a copy of ITU recommendation I.363 (ATM Adaption Layer), which is a lot less obscure than ITU-2066. The language is identical. Nybbler 22:43, 16 February 2006 (UTC)

This algorithm on the main page current is incorrect:

 function crc(bit array bitString[1..len], int polynomial) {
     shiftRegister := initial value // commonly all 0 bits or all 1 bits
     for i from 1 to len {
         if most significant bit of shiftRegister xor bitString[i] = 1 {
             shiftRegister := (shiftRegister left shift 1) xor polynomial
         } else {
             shiftRegister := (shiftRegister left shift 1)
         }
     }
     return shiftRegister
 }

The whole purpose of this algorithm is to replicate the polynomial division that defines CRC. This algorithm does not do that. For one thing, it never shifts the current data bit onto the right side of the shift register as is necessary in long division. For another, the condition that causes a divide on long division is iff the MSB of the shift register is 1 (regardless of the current data bit). Remember, the polynomial has an implied MSB of 1 (so a 16-th order CRC is using 16 bits to represent the actual 17-bit polynomial). Because of this, if a one is detected in the MSB of the shift register, the current bit is shifted on ("dropped down" if computing by hand) and the one on the left is discarded. That one is canceled by the implied 17th bit.

If you don't believe me, get out some paper and a pencil and do it by hand. For sources, I used "Computer Networks: A Systems Approach", 3rd edition, by Peterson and Davie; the ITU-T V.41 specification, and the definition of CRC given in this article.

As for the initial value being xor'd onto the message, I don't see where it says that. It's just what the shift register is set to when the routine starts. Mathematically, it's equivilant to prepending the initial value to the messsage and then using an initial shift register value of zero.

The "SIMPLE" algorithm specified above is correct. Again, if you don't believe me, run the math by hand. I've gone ahead and put the correct one back onto the main page so other people don't waste time (like I ended up doing) implementing something that won't work. Jdoty 29 June 2006

Again the algorythm was corrected to a wrong one, i don't want to revert it back because i already lost enough time, the current algorythm shows that you need to make an "OR" with the current data. look at the FF example computation below, and explain me how you can come to FF00000h as a result with this algorythm. You say to take paper and pencil, but you don't show your way of computing it, so my method below give the right result, prove that it is wrong by showing YOUR method and then we will be able to discuss.

Ok, here's an example worked out by hand using the mathematical definition of CRC:
Polynomial: x8+x7+x3+x2+1 = 0x8D = 10001101 (the CCIT-8bit polynomial)
Data: 'A' = 0x41 = 01000001
Step one: multiply data by x^8, so Data = 0100000100000000
Step two: divide data by polynomial (remember that there is an implied 1 at the MSb):

         ________________
10001101|0100000100000000
           10001101 <- 100000100 is larger than 10001101, so divide (xor) 
           --------
           100010010 <- 10001001 is NOT larger than 10001101, so bring down a zero and divide
            10001101
            --------
             100111110
              10001101
              --------
              101100110
               10001101
               --------
               111010110
                10001101
                --------
                0101101100 <- It takes two zeros to make 01011011 larger than 10001101
                  10001101
                  --------
                  11100001 <- Remainder = 0xE1

So, the 8-bit CRC is E1. The shift register is just implementing the long division. Two things happen per iteration through the division. It either divides or carrys down a zero. The divide condition happens if the the MSB of the shift register is one, and is completed by carrying down the next data bit and XOR-ing. If it isn't able to divide yet, another bit needs to be carried down. This result can be verified from several online CRC calculators and the method is taken from the SIMPLE CRC source above and is verified from the textbook above (and follows from the mathematical definition of CRC). CRC32 typically does some funky extra steps such as inverting the data before calculation, inverting the CRC result, reversing byte order, etc. Your algorithm works given the specific pre- and post-generation steps as defined by most CRC32 definitions, but it doesn't work on all cases (the ITTU CRC16 definition doesn't work with your algorithm for instance). All this algorithm does is the division step and is applicable in all cases. The user must be aware of the other requirements of the CRC definition that they are implementing.

Also, your 'I' character binary is incorrect. It should be 0x01001001. This is true for both big and little endian. Endian refers to BYTE order, you switched the nibbles (half-bytes) around. Jdoty

Update: I found another external source, this time published by IEEE, worth citing. A Tutorial On CRC Computations (Ramabadran, IEEE Micro 1998) Jdoty

Please note that the above illustration of a long-division-style CRC computation is misleading. The assertion that "100000100 is larger than 10001101" applies to binary integers, but these bit patterns are not binary integers: they are elements of a finite field, where notions of "larger" and "smaller" are not particularly useful. A simpler view of the process comes from restoring the sometimes-omitted high-order bit to the divisor, making it 110001101, and subtracting (or adding; they're the same with elements of GF(2)) whenever the high-order bit of the divisor is aligned with a "1" bit in what's left of the dividend. Peter 00:49, 7 May 2007 (UTC)

My 'I' character is correct, the problem is that you compute CRC32 without checking how the rest of the world is doing it. and excuse me, but i didn't switch the nibble, but the whole 8 bits 01001001 reverse is 10010010 correct or no ?!?

Take any crc32 programm, like quicksfv, winsfv, azza-sfv, dbcrc etc... and make a i.txt file whith only a single character "I", then use these programs to compute the CRC32 and miracle, the crc is DD0216B9.

I put this "I" example especially to make people remark that it's special by using all bit in reverse order.

I don't mind the crc 16 or any different kind of CRC since there is no way of checking if they are right or not; but CRC32 is widely used by many people, and there are plenty of commercial software that use it to check integrity, and all are getting the same results. Use winrar to pack the i.txt of 1 byte and you get DD0216B9 as CRC.

I don't care about all the references you can find in any books, as long as you don't compute a CRC32 with your algorithm, you can't prove that i'm wrong since i'm getting the same CRC32 value as all the softwares.

I even did the "123456789" test that gives the right CRC32 i didn't post it here because it's way long but it works and the CRC32 is correct.

I was wrong about your bit-reversed 'I'. My mistake. I was confused by where you referred to it as "big-endian" and "little-endian".

I looked up the IEEE 802.3 (Ethernet) standard which first defined the specific CRC32 implementation used by so many programs. It is defined as:

 Step 1 - Take the data to be M(x)
 Step 2 - Compliment the first 32 bits of M(x) <- this is what you meant when you said to XOR the initial value into the message
 Step 3 - Multiply M(x) by x^32  <- this means add 32 zeros to the end of the message
 Step 4 - Divide the augmented M(x) by the polynomial G(x)
 Step 5 - The compliment of the result is the CRC checksum
 It is also defined that the bit-order for each message byte (and the final CRC value) is reversed.

The algorithm on the main page implements step 4 which is the basis for CRC and the common denominator between ALL CRC definitions. Your algorithm takes several shortcuts to make it more effecient for the IEEE 802.3 specification, but it doesn't apply to any others. For one thing it skips step 3 by not augmenting the message with the extra zeros. To get the same results from the standard, generic CRC algorithm, the message must be augmented with the zeros (as stated in the CRC definition for 802.3, CCITT-16, and even on the wikipedia CRC article). Then, the first four bytes of the message must be inverted (step 2). Then the CRC algorithm is run with an initial shift register value of zero.

Since the CRC32 specification is so common with modern software, it would probably be good to make specific note of the extra steps required to calculate it (maybe give it it's own page?), but I feel the more generic CRC algorithm should be the one shown here. Otherwise, people looking to understand CRC in general, or people looking to implement another non-CRC32 checksum (like CRC16-CCITT, which is used with XMODEM, Bluetooth, and PPP among other places), would have troubles.

What are your thoughts on that? Jdoty 1 Sept 2006

Well, if it matters, I have a public-domain implementation of CRC-32 that performs all these steps here. Check out the file "crc32.c" for how to correctly do per-byte, per-short, and per-int updates. The file "file_crc32.c" shows how to perform a CRC-32 checksum on an entire file. The "pad with zeros at the end" aspect only matters if you're really doing long division the long, slow way. The final table lookup is doing the same thing. --Mr z 23:39, 17 May 2007 (UTC)

Oh, and my CRC-16 implementation (in the same directory) is also public-domain. --Mr z 23:40, 17 May 2007 (UTC)

They're the same algorithm

Folks, addition modulo two (a.k.a. XOR) is, like all addition, a commutative and associative operator. That means that the sum is the same regardless of the order in which the inputs are added.

Further, the only time a bit of the shift register is actually tested is when it is shifted off the end and used to control the polynomial XOR.

You need to XOR in the input bit sometime before that test, but it can be right at the beginning or right at the end. You get the same result either way. The various alternatives being discussed here are just different ways of doing the same thing.

Right at the end is popular in hardware. In particular, as you're trying find the CRC of a message polynomial m(x) into a CRC by computing x¹⁶m(x) mod p(x), delaying needing a bit of x¹⁶m(x) by 16 bit times avoids the need to actually do the multiplication by x¹⁶ (i.e. add 16 trailing 0 bits).

On the other hand, a popular way to do it in software is to XOR in 8 bits at a time into the shift register.

But it all produces the same result in the end.

The algorithm from before made several other assumptions about the data that only apply to that specific CRC32 definition. It would not produce results that were valid for various other CRC definitions. Yes, the one I provided does need the added zeros padded on the end. And yes, it can be done without the zeros by modifying the algorithm as you stated. While the one I provided isn't the most efficient, it does best reflect the mathematical definition (and how one would go about doing it by hand). I'm not against a better algorithm for general use being included, or even ones that apply to only specific CRC calculations, on the condition that they're well documented as to their use. I strongly feel that the one that mirrors the math be included since 1) it's more generic, and 2) it provides a better foundation for someone trying to learn what CRC is and how it works. When I was first trying to get it to work, I followed the definition exactly: multiplied (padded) the data, divided by the polynomial, and then stuck the result into the extra padded zeros. The only problem was that the division step wasn't producing the correct result. It took a long time to figure out that the problem was that the wikipedia algorithm didn't do what it said (or at least implied) it did. (Posted 4 Oct 2006, forgot to sign) Jdoty 11:35, 5 October 2006 (UTC)

3 examples of full CRC32 computation

Well with these, you can see a step by step explanation of how it works.

The "I" letter example is to show that you must use the BIG Endian convention, MSB on the right, LSB on the left

These examples use this algorythm:

 function crc(bit array bitString[1..len], int polynomial) {
     shiftRegister := initial value // commonly all 0 bits or all 1 bits
     for i from 1 to len {
         if most significant bit of shiftRegister xor bitString[i] = 1 {
             shiftRegister := (shiftRegister left shift 1) xor polynomial
         } else {
             shiftRegister := (shiftRegister left shift 1)
         }
     }
     return shiftRegister
 }

JimKi

Demonstration of CRC32 computation with 00h

The base data is 00h (00000000b)

The polynomial is 04C11DB7h (00000100110000010001110110110111b) 

The initial shift register value is FFFFFFFFh (11111111111111111111111111111111b) 

Starting 8 iterations
-------------------------------------------------------------------------------------------
Iteration 1, data remaining '0'0000000
     Shifting left, new shift register is '1'11111111111111111111111111111110
     (Data BIT out) XOR (SR BIT out) : 0 XOR 1 = 1, must XOR with poly
     SR       : 11111111111111111111111111111110 (FFFFFFFE)
     Poly     : 00000100110000010001110110110111 (04C11DB7)
     XOR        ===========================================
     Result   : 11111011001111101110001001001001 (FB3EE249)
-------------------------------------------------------------------------------------------
Iteration 2, data remaining '0'000000
     Shifting left, new shift register is '1'11110110011111011100010010010010
     (Data BIT out) XOR (SR BIT out) : 0 XOR 1 = 1, must XOR with poly
     SR       : 11110110011111011100010010010010 (F67DC492)
     Poly     : 00000100110000010001110110110111 (04C11DB7)
     XOR        ===========================================
     Result   : 11110010101111001101100100100101 (F2BCD925)
-------------------------------------------------------------------------------------------
Iteration 3, data remaining '0'00000
     Shifting left, new shift register is '1'11100101011110011011001001001010
     (Data BIT out) XOR (SR BIT out) : 0 XOR 1 = 1, must XOR with poly
     SR       : 11100101011110011011001001001010 (E579B24A)
     Poly     : 00000100110000010001110110110111 (04C11DB7)
     XOR        ===========================================
     Result   : 11100001101110001010111111111101 (E1B8AFFD)
-------------------------------------------------------------------------------------------
Iteration 4, data remaining '0'0000
     Shifting left, new shift register is '1'11000011011100010101111111111010
     (Data BIT out) XOR (SR BIT out) : 0 XOR 1 = 1, must XOR with poly
     SR       : 11000011011100010101111111111010 (C3715FFA)
     Poly     : 00000100110000010001110110110111 (04C11DB7)
     XOR        ===========================================
     Result   : 11000111101100000100001001001101 (C7B0424D)
-------------------------------------------------------------------------------------------
Iteration 5, data remaining '0'000
     Shifting left, new shift register is '1'10001111011000001000010010011010
     (Data BIT out) XOR (SR BIT out) : 0 XOR 1 = 1, must XOR with poly
     SR       : 10001111011000001000010010011010 (8F60849A)
     Poly     : 00000100110000010001110110110111 (04C11DB7)
     XOR        ===========================================
     Result   : 10001011101000011001100100101101 (8BA1992D)
-------------------------------------------------------------------------------------------
Iteration 6, data remaining '0'00
     Shifting left, new shift register is '1'00010111010000110011001001011010
     (Data BIT out) XOR (SR BIT out) : 0 XOR 1 = 1, must XOR with poly
     SR       : 00010111010000110011001001011010 (1743325A)
     Poly     : 00000100110000010001110110110111 (04C11DB7)
     XOR        ===========================================
     Result   : 00010011100000100010111111101101 (13822FED)
-------------------------------------------------------------------------------------------
Iteration 7, data remaining '0'0
     Shifting left, new shift register is '0'00100111000001000101111111011010
     (Data BIT out) XOR (SR BIT out) : 0 XOR 0 = 0, keep current SR
     Result   : 00100111000001000101111111011010 (27045FDA)
-------------------------------------------------------------------------------------------
Iteration 8, data remaining '0'
     Shifting left, new shift register is '0'01001110000010001011111110110100
     (Data BIT out) XOR (SR BIT out) : 0 XOR 0 = 0, keep current SR
     Result   : 01001110000010001011111110110100 (4E08BFB4)
-------------------------------------------------------------------------------------------
Finally, we must XOR the SR with FFFFFFFFh and reverse all the bits
     SR  : 01001110000010001011111110110100 (4E08BFB4)
     XOR : 11111111111111111111111111111111 (FFFFFFFF)
           ===========================================
     Res : 10110001111101110100000001001011 (B1F7404B)
           =================REVERSE===================
     CRC32 11010010000000101110111110001101 (D202EF8D)

Demonstration of CRC32 computation with FFh

The base data is FFh (11111111b)

The polynomial is 04C11DB7h (00000100110000010001110110110111b) 

The initial shift register value is FFFFFFFFh (11111111111111111111111111111111b) 

Starting 8 iterations
-------------------------------------------------------------------------------------------
Iteration 1, data remaining '1'1111111
     Shifting left, new shift register is '1'11111111111111111111111111111110
     (Data BIT out) XOR (SR BIT out) : 1 XOR 1 = 0, keep current SR
     Result   : 11111111111111111111111111111110 (FFFFFFFE)
-------------------------------------------------------------------------------------------
Iteration 2, data remaining '1'111111
     Shifting left, new shift register is '1'11111111111111111111111111111100
     (Data BIT out) XOR (SR BIT out) : 1 XOR 1 = 0, keep current SR
     Result   : 11111111111111111111111111111100 (FFFFFFFC)
-------------------------------------------------------------------------------------------
Iteration 3, data remaining '1'11111
     Shifting left, new shift register is '1'11111111111111111111111111111000
     (Data BIT out) XOR (SR BIT out) : 1 XOR 1 = 0, keep current SR
     Result   : 11111111111111111111111111111000 (FFFFFFF8)
-------------------------------------------------------------------------------------------
Iteration 4, data remaining '1'1111
     Shifting left, new shift register is '1'11111111111111111111111111110000
     (Data BIT out) XOR (SR BIT out) : 1 XOR 1 = 0, keep current SR
     Result   : 11111111111111111111111111110000 (FFFFFFF0)
-------------------------------------------------------------------------------------------
Iteration 5, data remaining '1'111
     Shifting left, new shift register is '1'11111111111111111111111111100000
     (Data BIT out) XOR (SR BIT out) : 1 XOR 1 = 0, keep current SR
     Result   : 11111111111111111111111111100000 (FFFFFFE0)
-------------------------------------------------------------------------------------------
Iteration 6, data remaining '1'11
     Shifting left, new shift register is '1'11111111111111111111111111000000
     (Data BIT out) XOR (SR BIT out) : 1 XOR 1 = 0, keep current SR
     Result   : 11111111111111111111111111000000 (FFFFFFC0)
-------------------------------------------------------------------------------------------
Iteration 7, data remaining '1'1
     Shifting left, new shift register is '1'11111111111111111111111110000000
     (Data BIT out) XOR (SR BIT out) : 1 XOR 1 = 0, keep current SR
     Result   : 11111111111111111111111110000000 (FFFFFF80)
-------------------------------------------------------------------------------------------
Iteration 8, data remaining '1'
     Shifting left, new shift register is '1'11111111111111111111111100000000
     (Data BIT out) XOR (SR BIT out) : 1 XOR 1 = 0, keep current SR
     Result   : 11111111111111111111111100000000 (FFFFFF00)
-------------------------------------------------------------------------------------------
Finally, we must XOR the SR with FFFFFFFFh and reverse all the bits
     SR  : 11111111111111111111111100000000 (FFFFFF00)
     XOR : 11111111111111111111111111111111 (FFFFFFFF)
           ===========================================
     Res : 00000000000000000000000011111111 (000000FF)
           =================REVERSE===================
     CRC32 11111111000000000000000000000000 (FF000000)

Demonstration of CRC32 computation with 'I' 49h

The base data is 49h (10010010b)

The polynomial is 04C11DB7h (00000100110000010001110110110111b) 

The initial shift register value is FFFFFFFFh (11111111111111111111111111111111b) 

Starting 8 iterations
-------------------------------------------------------------------------------------------
Iteration 1, data remaining '1'0010010
     Shifting left, new shift register is '1'11111111111111111111111111111110
     (Data BIT out) XOR (SR BIT out) : 1 XOR 1 = 0, keep current SR
     Result   : 11111111111111111111111111111110 (FFFFFFFE)
-------------------------------------------------------------------------------------------
Iteration 2, data remaining '0'010010
     Shifting left, new shift register is '1'11111111111111111111111111111100
     (Data BIT out) XOR (SR BIT out) : 0 XOR 1 = 1, must XOR with poly
     SR       : 11111111111111111111111111111100 (FFFFFFFC)
     Poly     : 00000100110000010001110110110111 (04C11DB7)
     XOR        ===========================================
     Result   : 11111011001111101110001001001011 (FB3EE24B)
-------------------------------------------------------------------------------------------
Iteration 3, data remaining '0'10010
     Shifting left, new shift register is '1'11110110011111011100010010010110
     (Data BIT out) XOR (SR BIT out) : 0 XOR 1 = 1, must XOR with poly
     SR       : 11110110011111011100010010010110 (F67DC496)
     Poly     : 00000100110000010001110110110111 (04C11DB7)
     XOR        ===========================================
     Result   : 11110010101111001101100100100001 (F2BCD921)
-------------------------------------------------------------------------------------------
Iteration 4, data remaining '1'0010
     Shifting left, new shift register is '1'11100101011110011011001001000010
     (Data BIT out) XOR (SR BIT out) : 1 XOR 1 = 0, keep current SR
     Result   : 11100101011110011011001001000010 (E579B242)
-------------------------------------------------------------------------------------------
Iteration 5, data remaining '0'010
     Shifting left, new shift register is '1'11001010111100110110010010000100
     (Data BIT out) XOR (SR BIT out) : 0 XOR 1 = 1, must XOR with poly
     SR       : 11001010111100110110010010000100 (CAF36484)
     Poly     : 00000100110000010001110110110111 (04C11DB7)
     XOR        ===========================================
     Result   : 11001110001100100111100100110011 (CE327933)
-------------------------------------------------------------------------------------------
Iteration 6, data remaining '0'10
     Shifting left, new shift register is '1'10011100011001001111001001100110
     (Data BIT out) XOR (SR BIT out) : 0 XOR 1 = 1, must XOR with poly
     SR       : 10011100011001001111001001100110 (9C64F266)
     Poly     : 00000100110000010001110110110111 (04C11DB7)
     XOR        ===========================================
     Result   : 10011000101001011110111111010001 (98A5EFD1)
-------------------------------------------------------------------------------------------
Iteration 7, data remaining '1'0
     Shifting left, new shift register is '1'00110001010010111101111110100010
     (Data BIT out) XOR (SR BIT out) : 1 XOR 1 = 0, keep current SR
     Result   : 00110001010010111101111110100010 (314BDFA2)
-------------------------------------------------------------------------------------------
Iteration 8, data remaining '0'
     Shifting left, new shift register is '0'01100010100101111011111101000100
     (Data BIT out) XOR (SR BIT out) : 0 XOR 0 = 0, keep current SR
     Result   : 01100010100101111011111101000100 (6297BF44)
-------------------------------------------------------------------------------------------
Finally, we must XOR the SR with FFFFFFFFh and reverse all the bits
     SR  : 01100010100101111011111101000100 (6297BF44)
     XOR : 11111111111111111111111111111111 (FFFFFFFF)
           ===========================================
     Res : 10011101011010000100000010111011 (9D6840BB)
           =================REVERSE===================
     CRC32 11011101000000100001011010111001 (DD0216B9)

Polynomial reversion?

I keep editing the page so that the reverse of 0x8005 is listed as 0x4003, and the reverse of 0x04C11DB7 is listed as 0xDB710641. But others keep editing the page so that the reverse of 0x8005 is listed as 0xa001, and the reverse of 0x04C11DB7 is listed as 0xEDB88320. If I'm not mistaken, THESE ARE JUST PLAIN WRONG! It simply doesn't make sense not to re-instate the full polynomial before reversing.

Can anyone come up with a good reference that says it is OK to reverse an incomplete polynomial? If not, then I think the article needs to have a good edit so that this incorrect information is never re-instated into it.

Chrisobyrne 17:11, 10 January 2006 (UTC)

First of all, you won't find numerical representations of polys in very many authoritative texts since that's an implementation detail. Confusion arises because the numerical rep of the poly depends on the code you're going to drop it into. For a 16 bit case (and typical implementations): if you are processing LSB-first, your poly rep. will have bit 15 set, since that's x^0. For an MSB-first case, the LSB corresponds to x^0 so that must be set. So, ONE definition of 'reversing the poly' is actually keeping the same CRC poly and converting it for use in a different algo. The other definition (yours) is for when you want to keep the same algo and use a different poly which is mathematically similar to the first (the factors of a reversed CRC poly are the factors of the original CRC poly, reversed).

So in the context of the table, as it appears today (Apr 9 2007): It appears to have been fixed and clarified a bit. Personally, I think the 'reciprocal' concept should be discussed before the concept of mapping a poly into an integer, since they are different things, and discussing them together invites confusion.

FOLKS: There are two completely different reasons to reverse the numeric representation of a CRC polynomial, and they are done differently. Also, if you put a number up to represent a CRC polynomial without referring to a piece of code which uses that number, you are inviting confusion. There's a lot of nonsense on the web because of this (so a high google count doesn't make anything right!!)

I don't understand the comment below ('about right and wrong'), it seems it is not applicable to CRCs; unless

x^{0}

and

x^{n}

are present in the polynomial, then it's not an n-bit CRC polynomial, end of discussion; please see the definition of the CRC and the remainder theorem.

There is a couple issues:

About right and wrong. First, there is nothing wrong in reversing truncated polynomial as you can always restore the original polynomial (applying the same reversion). But the other way of reversion (which you like) is wrong because it is not invertible in general. For example, let's consider polynomials $p(x)=x^{16}+x^{15}+x^{2}+1$ and $q(x)=x^{16}+x^{15}+x^{2}$ that differ only by the coefficient of $x^{0}$ . In standard notation they correspond to hexadecimal values 0x8005 and 0x8004 respectively. Now what is reversed form these polynomials? It may be a surprise, but if we follow your way of reversion we will get the same value 0x4003 for BOTH polynomials. This brings an important point that omitting the trailing coefficient is valid only if the value of this coefficient is fixed (that is usually but not necessary the case). In opposite, omiting the leading coefficient is always valid as its value is always 1.
About popularity. Try to search "DB710641" and "EDB88320" in google and compare the number of hits. Even if 0xEDB88320 were wrong theoretically, it deserves to be mentioned because of its popularity.

So I vote for keeping both ways of reversion.

Maxal 00:25, 11 January 2006 (UTC)

I think the solution is to have a line across the page, above which there is to be no mention of polys in numeric form; the reciprocal concept should be introduced above that line. Just below the line should be a note about how numerical polys are only meaningful in connection with an algorithm.

The article states "... a polynomial with its bits reversed ... produces a bit-reversed result". I question if this statement is still true when the reversion isn't done using the full polynomial - unless, of course, you make significant changes to the algorithm. And, if 0xEDB88320 is wrong theoretically (as I strongly suspect it is), the surely it is the one that should be placed in parenthesis, and not 0xDB710641.

Chrisobyrne 16:01, 11 January 2006 (UTC)

Yes, the algorithm dealing with reversed polynomials is different. But it can be obtained from the presented one with replacing "most" to "least" and "left" to "right". Inside the loop it should have something like

         if least significant bit of shiftRegister = 1 {
             shiftRegister := ((shiftRegister right shift 1)
                               or (the bit of bitString at position i left shift d-1)) xor (polynomial)
         } else {
             shiftRegister := (shiftRegister right shift 1)
                               or (the bit of bitString at position i left shift d-1)
         }

where d is the degree of the polynomial. Maxal 09:00, 13 January 2006 (UTC)

The major confusion here seems to be that reversing the representation of a polynomial and reversing the polynomial itself are two entirely different operations. When you reverse the bottom bits of the hex representation and use the reversed algorithm, you haven't changed anything mathematically; it's still the same polynomial and gives the same results (only reversed). If you reverse including the implied 1 bit, you get the normal representation of the reciprocal polynomial. This is still a valid polynomial but not the same one. I've attempted to explain this on the page.

By the way, there's no need to worry about polynomials with a 0 x^0 coefficient. Useful CRC polynomials always have a 1 x^0 coefficient. This is because the trailing zeros cancel in the division, so a e.g. 4-bit poly with normal representation 0xE is exactly the same as the 3 bit poly 0x7. This should probably appear on the page somewhere but I'm not quite sure where it fits in.

Nybbler 18:53, 10 February 2006 (UTC)

The Adler check sum doesn't belong in this article

The Adler check sum is not a CRC, and therefore the mentions of it in this article are off topic. They are potentially confusing, since the reader could be left with the impression that Adler is a CRC. They are redundant because Alder-32 has its own Wikipedia entry.

I think "32-bit Adler" in the comparison table is fine (but should be linked). However, I think the references to "CRC-16-Adler_A", "CRC-16-Adler_B", and "CRC-32-Adler" in the section "Polynomial CRC Specifications" are quite misleading and should be removed. I want a third opinion here first though. Deco 04:30, 4 November 2005 (UTC)

Perhaps they are the "official" designations or perhaps the "ITU-IEEE Syntax" has something to do with it. Shinobu 09:26, 6 November 2005 (UTC)

I think the Adlers should not be called CRCs. CRCs are shortened *cyclic* codes and so the codewords are multiples of an underlying generator polynomial. The Adlers are not like this. gazzaa 13:08, 16 February 2006 (UTC)

CRC error repair?

I backup data 5gb at a time or so. I have two DVD's that have CRC errors on them. Does anybody know if there is a way to recover the data off of the DVDs? When I browse the DVD in Windows explorer the files are visible but I can not access them. Any ideas?

I'd suggest ripping the DVD's entirely with a program that blindly copies an image of the entire disk. Chances are however that the CRC errors are on the image as well (if the "retry 24 times"-strategy of the copy program doesn't help). Perhaps there exist utilities that can recalculate the CRCs, but remember that some data has been irretrievably lost. A first step might be (carefully!) cleaning the disks. To prevent things like this happenig in the future you could use parity archives. Shinobu 01:44, 11 November 2005 (UTC)

Perhaps useful: http://sourceforge.net/projects/dvdisaster Additional error correction for CD and DVD media --Wikinaut 23:07, 10 April 2007 (UTC)

Use examples

It said: used by (among others) Ethernet, FDDI, PKZIP, WinZip, and PNG. I think mentioning PKZIP an WinZIP is redundant (pun intended) here, since both programs handle the same file format - ZIP. Many programs work with ZIP archives, so it doesn't make sense to list them all (or any.) Since the use of CRC is standardized by format, not a program, I will change that; since I can see that another file format is listed (PNG) it seems appropriate. --Arny 05:21, 14 February 2006 (UTC)

CRC-64

In "Polynomials and types" CRC-64 is listed both in 'common use' and 'not in common use'. Where does it belong? --Arny 05:29, 14 February 2006 (UTC)

It's in common use -- the ECMA standard listed in the table prescribes their use for DLT drives, which are common enough in themselves. Also it appears DVD IDs used by Microsoft are 64-bit CRCs (I do not know which polynomial).

Instead of fixing that I think perhaps the entire "Polynomials and types" section should be removed as both redundant with the table and somewhat confusing. There are no CRC "types" (AFAIK), there's only polynomials with different lengths. Also names like "CRC-16" unfortunately don't refer to a size of a CRC, but are ambiguous names which when used in context refer a specific CRC polynomial.

-- Nybbler 16:08, 14 February 2006 (UTC)

Error Detection Strength

UPDATE - Tabris.DarkPeace: The above point is partially incorrect. As the data only exists in 2 base states, if ANY OF THE LEADING ZERO's become corrupt, what do they therefore become in binary ?. In reality only the quantity of leading zero's needs to be known. Once changed to 1 (from 0) due to corruption, the leading zero arguement is invalidated, to some degree, as the CRC will obviously be totally different and thus not match / pass checks. This ensures reliability when used forwards or backwards so to speak, it may also save some latency / implementation costs of hardware varients of CRC. (darkpeace@internode.on.net).

I've reverted the above notice. What Darkpeace is pointing out is that corruption in leading zeros can be detected, which is true. What the comment it is referring to is that corruption consisting in a a change in the number of leading zeros cannot be detected, which is also true. 10000, 00000010000 and 00010000 have the same CRC.

Nybbler 23:24, 24 February 2006 (UTC)

Timings?

Where did the relative timings come from? It needs to state a source and an example architecture. Wei Dai's Crypto++ timings could be used. Note that Pentium 4 processers are very slow at certain kinds of rotate operations, so AMD timings are probably more representative of timings across a variety of architectures while still representing a very popular processor.

Comparing to MD4 is a bit of a waste; MD4 is overkill for an error check and too weak for cryptographic purposes. Compare to SHA-1 instead. You should also compare to the fastest MACs, like UMAC and Poly1305-AES. — ciphergoth 08:13, 15 April 2006 (UTC)

These benchmarks completely contradict that section - they show Adler-32 as being not slightly faster than CRC-32, but several times faster - 4.7 cycles/byte for CRC-32 but 1.3 cycles/byte for Adler-32. I've removed that section for now - we need a source to re-introduce it. Poly1305 is around 4.4 cycles/byte in bulk. — ciphergoth 08:03, 16 April 2006 (UTC)

Error correction?

Why does the article say, that CRC can correct errors? (In the very first paragraph I think.) Later on there's nothing about correction and none of the other sources I found, suggested that. —Preceding unsigned comment added by 84.63.44.154 (talk • contribs)

CRCs can't correct errors, though there are closely related codes that can. If the article suggests that it should be corrected. — ciphergoth 18:49, 25 April 2006 (UTC)

I have corrected this error, which was introduced in this edit. — ciphergoth 19:02, 25 April 2006 (UTC)

Technically, if you assume a priori that there is only a single-bit error, then an n-bit CRC is strong enough to correct a single bit error in a message of length (2^n)-1 or less if the checksum is known to be good. A program trying to correct such an error can determine if the error is likely to be a single bit error by looking at the XOR of the computed and expected CRCs (the "syndrome"), and performing a logarithm in GF(2^n). Not for the faint of heart, but entirely possible. This happens to be the case because CRC codes are linear codes and the final checksum is the sum of the checksums associated with each of the '1' bits in the input with an appropriate number of 0s after them. For the degenerate case, consider a message of length 1 with a CRC-1 (aka. parity bit) after it. If the parity bit doesn't match the data bit, and the parity bit is known to be good, the data bit is trivially corrected. For longer CRCs, blindly assuming the CRC is correct and the message is in error becomes more profitable, as the # of bits in the potentially-correctable message grows exponentially wrt. to the length of the CRC. --Mr z 00:59, 19 May 2007 (UTC)

The same process used to generate a CRC can also generate an error correcting code, but it's not usually called a CRC when you do that, and doing the correction requires techniques beyond those used in the CRC. Nybbler 15:52, 30 May 2006 (UTC)

The Ethernet CRC-32 is the generator polynomial of a single error correcting Hamming Code. If it were implemented in an error correction mode it could correct 1 error per code word. As a CRC generator it is not implemented to correct errors. It will only detect errors in this mode. Kenneth Brayer —Preceding unsigned comment added by 129.83.31.2 (talk) 21:18, 14 August 2008 (UTC)

CCITT CRC-8

I've added the $x^{8}+x^{7}+x^{3}+x^{2}+1$ polynom to the CRC table as CRC-8-CCITT because it seems generally refered to as "CCITT-8 CRC" or similar. I just feel a little unsure about the name since the only user of this polynom I know of is the Dallas / Maxim 1-Wire bus which is a proprietary system. Maybe somebode know more such as which CCITT / ITU-T standard specifies this polynom?

-- Ralf.Baechle 2006-06-27

xmodem CRC - more information?

Can anyone confirm the existance of CRC-16-BBS?? The only reference I can find to it is [1] and from what google tells me, XMODEM-CRC used CRC-CCITT's polynomial....

XMODEM-CRC and YMODEM use CRC-CCITT. I´ve been using for two decades the algorithm in http://www.ciphersbyritter.com/ARTS/CRCMYST.HTM. This article also has a good explanation of CRCs. Dquadros 13:49, 12 December 2006 (UTC)

XMODEM CRC is exactly analagous to CRC-CCITT. XMODEM CRC is not CRC-16-IBM. Will fix if no-one else does.. —Preceding unsigned comment added by Red660 (talk • contribs) 21:40, 17 April 2008 (UTC)

Confusing

The explanation is confusing. There is no example provided, all is just mathematics.

I agree. This article is among the worst, most useless I've ever encountered. Just a bunch of geeks masturbating in a language nobody understands. —The preceding unsigned comment was added by 66.108.117.83 (talk) 23:24, 29 December 2006 (UTC).

^ Hm, I wouldn't go that far..

I would. 74.137.111.179 (talk) 22:50, 22 July 2008 (UTC)

The problem is that this article is aimed at people who ALREADY understand it, who want to get a little more depth. It should be for people who WANT to understand it at all, primarily. Aimed at people who have only a vague understanding of what CRC is, if any.

This is far too confusing and doesn't explain things in a way a n00b could possibly understand - it just leaps from here to there with no real connection or explanation. Fine if you are revising something you already know, sucky if you want it explained from scratch.

If I understood it I might be able to offer a better way to explain it, but I came here to help me understand and it hasn't helped at all, so I can't.

ALSO: The opening sentence refers to packets - I was under the impression bit streams were known as "frames" rather than "packets" at this level. (?)

--Elín 17:08, 6 January 2007 (UTC)

Alternative Explanation.

Now that I understand it better, perhaps this could be an outline for a simpler explanation. I hope that I understood it correctly.

Example:

A sender wishes to send a message to a receiver.

The bit stream sent, for example 010011010 can be represented as a polynomial where each number represents a coefficient. For example:

M(x) = 0x⁸ + x⁷ + 0x⁶ + 0x⁵ + x⁴ + x³ + 0x² + x¹ + 0x⁰

To simplify:

M(x) = x⁷ + x⁴ + x³ + x

According to the CRC algorithm, the sender and receiver must agree on a divisor - for example:

C(x) = x³ + x² + 1

in C(x), the highest index is 3, so K=3.

The next step is to multiply M(x) by x^k, which we will call T(x), so in this case:

T(x) = (x⁷ + x⁴ + x³ + x) * x^k = x¹⁰ + x⁷ + x⁶ + x⁴

Now T(x) is divided by C(x).

T(x) / C(x) = x⁷ + x⁶ + x⁵ + x⁴ + x³ + 1 + (x² + 1)/ C(x)

The last part is the remainder. The remainder is what we are interested in so we multiply throughout to attain T(x) - remainder = 0.

Instead of subtracting, we use an operation called XOR.

The equation is turned into binary (a 1 where there is a coefficient of 1 and a 0 where there is (effectively) a coefficient of 0, as with the first stage but reversed), and K+1 number of zeroes are added to the end of T(x) (such that there is no overlap):

1001101 and K+1 zeroes: 0000

10011010000 <- T(x) plus zeroes
00000000101 <- The remainder

The XOR function lines them up thus, and then simply applies two basic rules. In the downward columns, if the numbers are different, put a 1, if they are the same, put a 0. Hence:

10011010000
00000000101
___________
10011010101

This is basically the remainder added to T(x).

Converting this back into a polynomial gives us the frame which is sent to the receiver:

P(x) = x¹⁰ + x⁷ + x⁶ + x⁴ + x² + 1

The receiver checks to see if an error has occurred during transmission by dividing P(x) by C(x).

P(x) / C(x) = x⁷ + x⁶ + x⁵ + x⁴ + x³ + 1

Remainder = 0. Because the remainder is 0, the receiver knows the message was sent correctly.

--Elín 14:43, 7 January 2007 (UTC)

Still a bit confused

Elin, first of all, your notes helped me make a lot more sense of CRC :) but could you explain this bit in your work: "The last part is the remainder. The remainder is what we are interested in so we multiply throughout to attain T(x) - remainder = 0."

How do you multiply throughout? Doesnt that just make you end up where you started? Maybe im just acting dumb but its too early for me to think clearly.

Cheers, Russ

Redfox04 10:31, 19 January 2007 (UTC)

Secure enough for authentication?

Is CRC secure enough to be used in authentication?--Bernard François 15:52, 27 January 2007 (UTC)

No it's linear, so the contribution of any bit in the CRC is independent and can be precalculated it useful - so an attacker could change data to match a given CRC for example. See the "Reversing CRC" link in external links in the article. Isn't authentication what the cryptographic hash functions like SHA are for? RDBrown 01:22, 28 January 2007 (UTC)

Endianess Confusion

This article uses the term endianess to refer to both byte-order and bit-order. I won't get into an argument over whether or not this is technically correct, but it does make the article more confusing. I would recommend that the term endianess be reserved for byte-order, which is the more common usage. Alternately, I would not be opposed to simply using the more descriptive terms (byte-order, bit-order, MS-bit-first LS-bit-first, etc) in every case, in place of the more generic endianess terms. I would definately refrain from using the terms big-endian and little-endian to refer to most-significant and least-significant bit first.

134.253.26.6 15:53, 29 January 2007 (UTC)

It doesn't seem the least bit confusing to me (big-endian means most-significant-thing first; little-endian means least-significant-thing first), but article edited per your suggestion anyway. I left the synonyms in, however, but as parenthesized synonyms. 71.41.210.146 06:22, 17 March 2007 (UTC)

All of this page is terribly confusing!

Having practiced and implemented CRC's since the begining of the 80' I can tell you this is NOT a synthetic page. It confused terribly the matter! The whole discussion on endianess is irrelevant and should not be part of a basic CRC explanation. No editing of the page can possibly be done. It just should be rewritten! RJG13 11:27, 30 January 2007 (UTC)

I agree perhaps two versions sould be attached a basic version stating how it works and then the detailed information below it or something Antbelcastro 03:12, 25 March 2007 (UTC)

The Example section already does as much. However, it does warrant pointing out that article is far from accessible to the non-technical. If my wife or my father were to attempt to read this, they would find almost nothing of value to them before giving up halfway down the page full of mathematics. Personally, I find that part more interesting than a lay treatment of the subject, but it would be nice to have more of an introduction/to flesh out further what a CRC is/why it matters before the really in depth parts. MrZaius^talk 19:46, 22 April 2007 (UTC)

I think the article will improve if we can reach a consensus on a couple of pivotal points. First, do we want the article to be useful to the non-mathematically inclined? If so, the word "polynomial" should be relegated to the "mathematics of CRCs" page, and the early discussion should revolve around CRCs' interesting error-detection capabilities (e.g., guarantee of detecting error bursts shorter than n, and 1-2^-n probability of detecting longer errors).

Second, do we want to pretend that all CRCs are binary, and maybe mention at the end that there are non-binary CRCs? Or should we hit the user right off with the full generality, and thereby risk damaging people's wives and fathers? (I see problems either way.)

Third, can we agree that practical implementation questions (including endianness) should be localized in an Implementations section? The variety of CRC implementations that one encounters is bewildering, and Wikipedia is an excellent place to sort them out, but implementation matters shouldn't be allowed to muddle the exposition of the (basically simple) concept of the CRC. Peter 01:29, 7 May 2007 (UTC)

Disagree strongly; precisely because people find endianness confusing, it must be explained clearly from the first

Um... the word "synthetic" makes no sense in context, and "it confused terribly the matter" is sufficiently ungrammatical that the identity of "the matter" referred to is unclear. Could you clarify?

Regarding the (ir)relevance of endianness in a basic explanation, I would like to disagree strongly. The article was mess of reverts as people "corrected" little-endian code and polynomial values to big-endian code and vice-versa. You can see the residue of that in the talk page above. It remains the single most confusing thing to beginning implementors, who don't understand that to generate a CRC in software, you have to specify the generator polynomial and the endianness. Thus, it's possible for two pieces of example code that compute a CRC using the same polynomial to get different results.

It isn't helped by the fact that most of the hardware documentation skips over the issue because it doesn't apply to bit-serial applications. It's only when you assemble them into bytes that it matters.

Also, there is in many applications a correct endianness to use. It's worth understanding which is appropriate. 71.41.210.146 06:19, 17 March 2007 (UTC)

Strange mathematics

Can CRC be calculated for a stream of odd number of bits? If so, the stated fact that it can detect all errors in an odd number of bits seems contradictory to me. Though of course I strongly suspect it's a flaw in my thinking, I'd appreciate if someone pointed it out.

~~The thinking goes as follows:~~

1. Take the original message. Let n be its length in bits. Compute and store its CRC.
2. Add a single bit, say always a 0, to the end of the message. Compute and store the CRC of this n+1-bit bitstream.

~~Now, in verification:~~

3. Verify the CRC of the original n-bit message against the CRC computed in step 1. This ensures that if there are any undetected errors, an even number of bits in the original n-bit message must have flipped.
4. Intentionally flip the bit added in step 2. Verify the CRC of the message with this flipped bit added (together n+1 bits) against the CRC computed in step 2. This ensures that if there are any undetected errors, an even number of bits must have flipped in the whole n+1-bit bitstream, and one of them is the one we intentionally flipped, hence an odd number of bits must have flipped in the original n-bit message.

Now, since it is impossible that both even and odd number of bits have flipped in the original n-bit message, if the CRCs are both correct, we have ensured that the original message is intact. This means we have compressed the original bitstream of whatever length to the two CRCs, which is of course absurd. --SLi 22:45, 5 March 2007 (UTC)

Argh. Forget. Too late to do maths like this :D --SLi 23:21, 5 March 2007 (UTC)

Changes to introductory sections, 2007-05-08

I changed the lead paragraph to improve precision, to focus more on the essential attributes, and to avoid calling a CRC a "checksum". The description of a CRC as a "hash function", although perhaps defensible in general terms, seemed likely to mislead the newcomer: the primary purpose of a hash function is to scatter wildly, while that of a CRC is to detect errors, and while those goals may be somewhat aligned, they are very different.

I expanded the Introduction to include a mention of the fact that some CRCs are not binary and to include a description of the sort of error-detection guarantees that one gets with CRCs.

I changed the "CRCs and Data Integrity" section to include a more detailed description of CRCs' weakness, and to remove text that gave the (erroneous) impression that the CRC's unsuitability is related to its length. Despite misgivings that this article is about CRCs, not cryptography, I carried forward the advice to use a message authentication code instead.

Peter 22:19, 8 May 2007 (UTC)

However, it's worth noting that technically, a CRC is a checksum. It's weighted checksum—the polynomial defines the value each bit is multiplied by before adding it to the checksum—and addition is done in GF(2ⁿ) and not Z_2ⁿ, but it's a linear sum. The CRC of the sum of two messages is the sum of the CRCs of the individual messages.

71.41.210.146 21:36, 30 May 2007 (UTC)

That's certainly a reasonable position, which is why I refrained (I hope) from asserting that a CRC is not a checksum. One could argue (and I guess you do) that any linear code is a checksum, but for someone arriving at this article without a pretty sophisticated mathematical mindset, the term probably sheds more darkness than light: Imagine looking at a CRC algorithm and trying to find the "sum". So . . . you're right, but can we leave it like this?

Peter 02:06, 31 May 2007 (UTC)

Removing "When CRCs collide"

I removed the section "When CRCs collide" because its motivations, terminology, and conclusions were unclear. Of course there are collisions: an n-bit CRC, given all possible inputs of n+m bits, will produce 2^m-1 collisions at each of its 2ⁿ possible values; that's a simple consequence of its linearity. Furthermore, if the population of input values is considered to be random, the number of inputs that one must expect to try before finding one collision is approximately 2^n/2, the same as for any good hash function. If the population of input values is not considered to be random -- the only case in which collisions rates can differ between two good hash functions of the same length -- then one must specify what that population is before proceeding with the disucssion.

The notion of a polynomial's intrinsic repeat rate lacked a clear definition. The notion of using a CRC as a random-number generator has been extensively studied under the heading of Linear Feedback Shift Registers, and periods less than 2ⁿ-1 bits are unnecessarily short.

The assertion that a particular 64-bit CRC has one collision every 2⁶⁴ CRCs ignores the Birthday Phenomenon, by which one predicts that the first colliding pair will be found after about 2³² CRCs. And the assertion that one 64-bit CRC function has fewer collisions than another is a remarkable proposition that certainly requires explanation and supporting evidence. Peter 00:56, 9 May 2007 (UTC)

Divisor

Why is it called a divisor when it doesn't actually divide? If you calculate the remainder of the example using division, you get 0111 (converted to decimal the division is 13548 / 11, and that has a remainder of 7), not 0101. —Preceding unsigned comment added by MysticMetal (talk • contribs)

(Presumably this question applies to the Mathematics of CRCs section.) As explained in the Introduction, the division is not the familiar division of integers, but rather the division of a finite field where "subtraction" is done by exclusive-ORing. Perhaps it's not reasonable to assume that the reader of this section has read (or understood, or remembered) that part of the Introduction. Maybe a pointer back to it would be appropriate, or maybe a restatement. What do you think? Peter 01:04, 15 May 2007 (UTC)

Moved to Talk

The following comments was in italics...comments on articles belong on its talk page, not in the article. Or, gee, just make the change yourself - that's the whole point. Afabbro 17:39, 10 July 2007 (UTC)

"The following table below omits "Initial value", "Reflected value" and "Final XOR value". This table does not indicate whether the CRC is reducible or irreducible. Irreducibility is an important CRC property."

Step-by-step examples

I see that somebody has just contributed (and somebody has removed) another step-by step example. I think it's difficult to know just how much detail to put in- it might be justifiable to have the first and final couple of stages of one of the CRC algorithms as an example but the problem then arises of which algorithm to use.

I think what would be really useful would be (a link somewhere to) usage examples and extracts from definitive coefficient tables for each of the algorithms and variants so that if somebody was implementing something obscure like CRC-8-CCITT they could see that they'd got things right. Perhaps a monograph in WikiBooks? MarkMLl 09:49, 14 September 2007 (UTC)

Doesn't cite sources

This page doesn't cite any sources at all as far as I can see. —Preceding unsigned comment added by 194.129.249.111 (talk) 11:48, 30 November 2007 (UTC)

GF(2) or GF(2^n)

If I remember correctly from school, this arithmetic is all done in GF(2^n), not GF(2), as stated in the article. 192.91.173.42 (talk) 02:22, 6 March 2008 (UTC)

No. In general, the arithmetics here is done in a polynomial ring over GF(2) modulo some polynomial p(x) (i.e., in GF(2)[x]/< p(x) >). Only if p(x) is irreducible over GF(2) this ring is a finite field and is isomorphic to GF(2^n). But in general, p(x) is not required to be irreducible. Maxal (talk) 09:56, 6 March 2008 (UTC)

Controversial opinions

I have heard that both PGP and CRC can not protect data from intentional changes.

http://crc32-checksum.waraxe.us/

However, there is a paper which nod it

http://cat.inist.fr/?aModele=afficheN&cpsidt=14826384

Now whom I listen to?

Would people please make more comment on this? Thanks

talk pages are here to discuss the article not for general discussions of the topic. This article already discusses why CRC's can not protect data from intentional changes. Wrs1864 (talk) 14:57, 24 March 2008 (UTC)

The paper (available here) is nonsense and should never have been published. The author has no clue what a digital signature is. -- BenRG (talk) 15:45, 24 March 2008 (UTC)

If you want, you may go to Wikipedia:Reference_desk/Computing for your CRC question. Here is the portal of Reference desk Wikipedia:Reference_desk if you have questions other than computing. - Justin545 (talk) 05:35, 25 March 2008 (UTC)

All bits in representation?

Regarding the recent good faith edits by 208.102.175.210 and 192.118.76.130, what is the consensus on including all bits in the binary representation, e.g.

Normal: 0x04C11DB7 → 0x104C11DB7 (adding MSB)
Normal of reciprocal: 0x31CE8603 → 0x71CE8603 (adding LSB)
Reverse: 0xEDB88320 → 0xEDB88320.8 (the MSB is below bit 0, making the value a fraction)

Would it be helpful to change/revert the table to these forms? -- Regregex (talk) 13:42, 11 April 2008 (UTC)

I don't think so, the most and least significant bits of a CRC polynomial are always 1 so they are implied, and the real polynomials are explicitly listed in the table. The forms 0xEDB88320 and 0x04C11DB7 are constants that actually appear in implementations. They're for implementation purposes, not illustration purposes, and if you add the extra bit, it will just confuse the issue more. The point is that a given CRC polynomial can be mapped to a hex constant for use in code to calculate the CRC polynomial. I think a short example illustrating the relationship between the polynomial and the constants (and/or a reference to an external page that already does this) would be much more helpful. Arghman (talk) 15:04, 17 February 2009 (UTC)

Test vectors

It would be useful to include and/or cite a webpage which has test vectors for each of the CRC variants listed in the table. I'm implementing one of the more obscure variants and I need to test it to make sure it works. Arghman (talk) 14:58, 17 February 2009 (UTC)

This page is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.