CRC: найти ошибочный байт - PullRequest
Новая
       84

CRC: найти ошибочный байт

0 голосов
/ 30 апреля 2019

Предположим, что многобайтовый блок данных обрабатывается дважды с помощью CRC, один раз без изменений и один раз с одним ошибочным байтом.Может ли неисправный байт быть расположен исключительно на основе двух кодов?Обратите внимание, что это не означает, что точная природа ошибки должна быть идентифицирована только ее местонахождением, и при этом ошибка байта не ограничена единственным переключением битов, которое может быть исправлено любым CRC.

1 Ответ

1 голос
/ 30 апреля 2019

Дано: CRC для хороших данных и CRC для данных с одним плохим байтом. Предполагается, что два заданных CRC являются хорошими, поэтому в самих CRC нет ошибок. Xor хороших данных CRC с плохими данными CRC. Рассматривайте это как ксерокопирование хороших данных + хороший CRC с плохими данными + плохой CRC, в результате получаются данные со всеми нулями, кроме одного плохого байта, и соответствующий CRC. Xor также отменяет любое начальное значение CRC или последующее дополнение значения CRC.

Для того, чтобы иметь возможность определять местоположение плохого байта, CRC должен быть уникальным для каждой возможной комбинации местоположения байта и значения байта.

Я обнаружил, что полином CRC32C 0x1edc6f41 создает уникальные CRC для данных от 1 до 190235 байт. Он завершается с ошибкой в ​​190236 байт данных, так как все нулевые буферы за исключением того, что bfr [0] = 0xfb или bfr [190235] = 0x32 оба выдают одинаковый (неуникальный) CRC = 0x364b1c30.

Пример кода для определения местоположения с хорошим CRC и плохим CRC (один плохой байт): 

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);

код для генерации 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);
}
...