CRC: Locate Erroneous Byte

Question

Assume a multi-byte block of data is processed twice by some CRC, once unchanged and once with a single faulty byte. Can the faulty byte be located solely based on the two codes? Note that does not imply that the exact nature of the error has to be identified only its location, neither is the byte error restricted to a single bit-flip which can be corrected by any CRC.

Answer 1

Given: the CRC for good data and the CRC for data with one bad byte. The two given CRCs are assumed to be good, so there is no error within the CRCs themselves. Xor the good data CRC with the bad data CRC. Consider this as xoring the good data + good CRC with the bad data + bad CRC, the result is data that is all zeroes except for the one bad byte, and a corresponding CRC. The xor also cancels out any initial CRC value or post complementing of the CRC value.

In order to be able detect the location of the bad byte, the CRC needs to be unique for every possible combination of byte location and byte value.

I found that CRC32C polynomial 0x1edc6f41 produces unique CRCs for 1 to 190235 bytes of data. It fails at 190236 bytes of data, as an all zero buffer except for bfr[0] = 0xfb or bfr[190235] = 0x32 both produce the same (non-unique) CRC = 0x364b1c30 .

Example code to determine location given a good crc and a bad crc (one bad byte):

static uint32_t crcrtbl[256];

void genrtbl(void)
{
uint32_t crc;
uint32_t b;
uint32_t c;
uint32_t i;
    for(c = 0; c < 0x100; c++){
        crc = c;
        for(i = 0; i < 8; i++){
            b = crc&1;
            crc >>= 1;
            crc ^= (0 - b) & (0x11edc6f41>>1);
        }
        crcrtbl[c] = crc;
    }
}

size_t crc32r(uint32_t crc, size_t size)
{
    while(size--){
        crc = (crc >> 8) ^ crcrtbl[crc & 0xff];
        if(0 == (crc & 0xffffff))
            break;
    }
    return(size);
}
// ...
genrtbl();  // generate table
// given good_crc and bad_crc, return location
location = crc32r(good_crc ^ bad_crc, size);

code to generate crc

uint32_t crctbl[256];

void gentbl(void)
{
uint32_t crc;
uint32_t b;
uint32_t c;
uint32_t i;
    for(c = 0; c < 0x100; c++){
        crc = c<<24;
        for(i = 0; i < 8; i++){
            b = crc>>31;
            crc <<= 1;
            crc ^= (0 - b) & 0x1edc6f41;   // 32 bit crc
        }
        crctbl[c] = crc;
    }
}

uint32_t crc32(uint32_t crc32, uint8_t * bfr, size_t size)
{
uint32_t crc = crc32;
    while(size--)
        crc = (crc << 8) ^ crctbl[(crc >> 24)^*bfr++];
    return(crc);
}