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

Comments (0)

2005-12-07

Correcting byte and burst errors with CRCs

Links