Can the following code be used for detecting an error in a data packet of 256 bytes?
/* * Function: Do_CRC8 * * Description: * Computes the CRC value given the byte and the old CRC value as a static value * * Return Value: CRC value * Parameters: Input data byte to be CRC'ed * Remarks: * uses a table driven method to speed things up. * * */ unsigned char Do_CRC8(unsigned char xx) { // this procedure calculates const unsigned char code Table[256]={ 0x00,0x07,0x0E,0x09,0x1C,0x1B,0x12,0x15,0x38,0x3F,0x36,0x31,0x24,0x23,0x2A,0x2D, 0x70,0x77,0x7E,0x79,0x6C,0x6B,0x62,0x65,0x48,0x4F,0x46,0x41,0x54,0x53,0x5A,0x5D, 0xE0,0xE7,0xEE,0xE9,0xFC,0xFB,0xF2,0xF5,0xD8,0xDF,0xD6,0xD1,0xC4,0xC3,0xCA,0xCD, 0x90,0x97,0x9E,0x99,0x8C,0x8B,0x82,0x85,0xA8,0xAF,0xA6,0xA1,0xB4,0xB3,0xBA,0xBD, 0xC7,0xC0,0xC9,0xCE,0xDB,0xDC,0xD5,0xD2,0xFF,0xF8,0xF1,0xF6,0xE3,0xE4,0xED,0xEA, 0xB7,0xB0,0xB9,0xBE,0xAB,0xAC,0xA5,0xA2,0x8F,0x88,0x81,0x86,0x93,0x94,0x9D,0x9A, 0x27,0x20,0x29,0x2E,0x3B,0x3C,0x35,0x32,0x1F,0x18,0x11,0x16,0x03,0x04,0x0D,0x0A, 0x57,0x50,0x59,0x5E,0x4B,0x4C,0x45,0x42,0x6F,0x68,0x61,0x66,0x73,0x74,0x7D,0x7A, 0x89,0x8E,0x87,0x80,0x95,0x92,0x9B,0x9C,0xB1,0xB6,0xBF,0xB8,0xAD,0xAA,0xA3,0xA4, 0xF9,0xFE,0xF7,0xF0,0xE5,0xE2,0xEB,0xEC,0xC1,0xC6,0xCF,0xC8,0xDD,0xDA,0xD3,0xD4, 0x69,0x6E,0x67,0x60,0x75,0x72,0x7B,0x7C,0x51,0x56,0x5F,0x58,0x4D,0x4A,0x43,0x44, 0x19,0x1E,0x17,0x10,0x05,0x02,0x0B,0x0C,0x21,0x26,0x2F,0x28,0x3D,0x3A,0x33,0x34, 0x4E,0x49,0x40,0x47,0x52,0x55,0x5C,0x5B,0x76,0x71,0x78,0x7F,0x6A,0x6D,0x64,0x63, 0x3E,0x39,0x30,0x37,0x22,0x25,0x2C,0x2B,0x06,0x01,0x08,0x0F,0x1A,0x1D,0x14,0x13, 0xAE,0xA9,0xA0,0xA7,0xB2,0xB5,0xBC,0xBB,0x96,0x91,0x98,0x9F,0x8A,0x8D,0x84,0x83, 0xDE,0xD9,0xD0,0xD7,0xC2,0xC5,0xCC,0xCB,0xE6,0xE1,0xE8,0xEF,0xFA,0xFD,0xF4,0xF3 }; ucCRC=Table[ucCRC ^ xx]; return (ucCRC); }
"Can the following code be used for detecting an error in a data packet of 256 bytes?" Sure, but if you were listening at all to what I said here, http://www.keil.com/forum/docs/thread4290.asp , you will recall that: That is too much data to cover with only an 8-bit CRC. Generally speaking, an n-bit CRC's error detection properties degrade after 2**(n-1)-1 data bits. Thus, an 8-bit CRC should be avoided for data blocks over 15 bytes in length. For 256 byte data, you really should be using a 16-bit CRC. Is there any particular reason that you think that using the same 8-bit CRC and polynomial, but calculating it using a 256-byte feedback table instead of a 16-byte feedback table removes the > 2**(n-1)-1 data bit degradation?
Dan's rule of thumb may be a good one but it is not strictly speaking true that a CRC degrades as the CRC is used to detect errors in larger packets. In fact the characteristics of well-chosen CRC polynomials are well know. A CRC of n-bits is able to detect all 1 and 2 bit errors, all odd numbers of errors and all errors with burst less than n bits in length, and will only fail to detect 1 in 2^n other patterns of errors. Obviously, the larger the packet to be protected, the greater the probability of getting more than 3 incorrect bits. Just how likely this is depends upon the bit error rate of the transmission/storage medium. Burst errors are of puticular interest because these are particularly common in practice. Further reading: http://www.repairfaq.org/filipg/LINK/F_crc_v3.html
"Obviously, the larger the packet to be protected, the greater the probability of getting more than 3 incorrect bits." To illustrate the "degradation point", consider the CRC-16 polynomial [X^16 + X^15 + X^2 + 1 = (X + 1) * (X^15 + X + 1)] which, among its error detection properties that are independent of block length:
Using CRC-16 as an example, I said "I think that it's fair to say that when using too large of blocks, some error detection properties of a CRC are compromised...". I should also say that it is my inference that the same thing goes for the 8-bit CRC that the OP is using (and that I have used on occasion), although I have not yet seen it written anywhere for that particular 8-bit CRC polynomial. I think it's only fair to say that too. ;-)
A CRC is much like division. You can think of the data to be protected as one long binary number, divided by the CRC polynomial, to get the CRC, which is like the remainder of the division. It's just that the definition of "divison" is a little different. Consider the more familiar mod operator '%'. Let's say we're calculating a value mod 8. 1 % 8 == 1 2 % 8 == 2 ... 9 % 8 == 1 For a particular mod value, there is some range of inputs that will have the same result. The output repeats cyclically. You know, in fact, that any input larger than the mod value might have the same output as some smaller value, and there are many possible large values that all map to the same result. CRCs have a similar problem. If the length of the data to be protected is longer than 2^N for your CRC-N, then the CRC protection is weakened. The nice error detection properties of CRCs cited above (which are a property of the polynomial used, which is why you always see the same polynomials over and over) apply to blocks of data less than 2^N bytes long. A CRC-8 will not do well at detecting (for example), simultaneous errors in bytes 128 and 384 of a 512-byte block. As far as the division is concerned, the second set of 256 bytes aliases with the first in a way analogous to the way 1 % 8 aliases with 9 % 8. If you want to detect a change from 1 to 9 with the mod operator as your checksum function, you must pick a mod value larger than 8. If you want to detect errors in a block longer than 256 bytes with a CRC as your checksum function, you need a CRC-16 (or better).