Lair Of The Multimedia Guru

2005-12-07

Correcting byte and burst errors with CRCs

Can CRCs be used to fix a whole messed up byte? Yes as long as the codeword (data bits + crc bits) is less then whats in this table under 8≤b:

generator polynom b≤2 b≤3 b≤4 b≤5 b≤6 b≤7 b≤8 b≤9 b≤10 b≤11 b≤12 b≤13 b≤14
CRC-4 0xF0000000 8 6 6 6 6 6 6 6 6 6 6 6 6
CRC-5 0x28000000 16 9 7 7 7 7 7 7 7 7 7 7 7
CRC-7 0xA2000000 18 18 9 9 9 9 9 9 9 9 9 9 9
CRC-7 0x12000000 34 28 12 9 9 9 9 9 9 9 9 9 9
CRC-7 0x6E000000 66 12 9 9 9 9 9 9 9 9 9 9 9
CRC-8 0x07000000 130 12 12 10 10 10 10 10 10 10 10 10 10
CRC-8 0x39000000 20 20 11 10 10 10 10 10 10 10 10 10 10
CRC-8 0xD5000000 96 24 12 10 10 10 10 10 10 10 10 10 10
CRC-12 0x80F00000 2050 555 16 16 16 14 14 14 14 14 14 14 14
CRC-12 0x80B00000 513 259 16 16 16 14 14 14 14 14 14 14 14
CRC-12 0x1F100000 68 68 21 15 15 14 14 14 14 14 14 14 14
CRC-15 0x8B320000 130 130 130 130 58 27 17 17 17 17 17 17 17
CRC-16 0x10210000 32770 7144 4181 175 19 19 19 18 18 18 18 18 18
CRC-16 0x80050000 32770 19 19 19 19 19 19 18 18 18 18 18 18
CRC-16 0xA0970000 16386 931 862 76 76 65 22 18 18 18 18 18 18
CRC-16 0xC5030000 7164 7164 188 188 164 145 28 18 18 18 18 18 18
CRC-16 0x90D90000 154 154 154 154 154 77 21 18 18 18 18 18 18
CRC-24 0x80510100 7164 7164 1028 1028 1028 1028 1028 1028 348 30 30 26 26
CRC-32 0x04C11DB7 376820511 376820511 30435040 14373578 14373578 3932619 1077949 49616 11995 5682 1731 732 40
CRC-32 0x404098E2 1026 1026 1026 1026 1026 1026 1026 1026 1026 1026 241 229 114
CRC-32 0x1EDC6F41 2147483650 258958121 193439312 62023781 3040389 1847228 603132 98658 4913 3356 1104 86 86
CRC-32 0x741B8CD7 114698 114698 16390 16390 6361 3955 1601 120 120 120 120 77 49
CRC-32 0xF4ACFB13 32770 32770 32770 32770 32770 32770 32770 32770 6508 3052 1696 152 152
CRC-32 0x32583499 32772 32772 11340 11340 6230 5348 324 324 324 324 156 44 34
CRC-32 0x20044009 32772 32772 3792 3792 3792 3792 620 360 302 302 52 52 52
CRC-32 0xA833982B 65540 65540 1928 1928 1928 1928 1928 1593 203 203 203 66 66
CRC-32 0x00210801 65540 65540 15207 15207 3211 3211 959 83 83 83 39 39 39

table was created with crc_test_v2.c

To actually correct byte errors the code below could be used, a complete example (crc_test_byte.c) is available too.

static int get_error(unsigned int crc, unsigned int len, int *error){
    int i;

    for(i=0; i<len; i++){
        if(!(crc & ~255)){
            *error= crc;
            return i;
        }
        crc= (crc>>1) ^ (((G>>1)|0x80000000) & (-(crc&1)));
    }
    return -1;
}
Filed under: Error Correcting Codes — Michael @ 23:08

Powered by WordPress