¿Es posible hacer una corrección de errores rudimentaria con CRC?

Question

Sé que la intención total del uso de CRC es la detección de errores, pero escuché a alguien decir que se puede usar para corregir errores básicos además de la detección de errores. Tenía curiosidad si este era el caso, y si es así, ¿qué tan poderoso es? Quiero decir, generalmente nos referimos a CRC como capaz de realizar la detección de x bits, pero tengo curiosidad si es capaz de realizar la corrección de x bits. Si es así, ¿cómo funciona esto? Gracias.

Answer 1

Es posible hacer la corrección de errores de un solo bit con un CRC. Supongamos una tiene un CRC "registro" y tiene funciones para ejecutar el algoritmo CRC hacia adelante y hacia atrás un poco a la vez, haciendo caso omiso de datos entrantes

 
int crc_forward(int old_value, int data_bit) 
{ 
    if (old_value & 0x8000) 
    return ((old_value^0x8000) SHL 1)^0x1021^data_bit; 
    else 
    return (old_value SHL 1)^data_bit; 
} 

int crc_reverse(int old_value) 
{ 
    if (old_value & 1) 
    return (old_value SHR 1)^0x8810; 
    else 
    return old_value SHR 1; 
} 

supongamos que tiene un paquete que se calcula de manera que la inicialización de la CRC en cierta el valor y ejecutando crc_forward para cada bit (MSB primero) debería dar como resultado cero. Si se obtiene un valor de CRC distinto de cero, se puede ejecutar el algoritmo en reversa (ignorando los bits de datos) hasta que el valor de CRC calculado sea 1. Esa es la ubicación del bit incorrecto.

Tenga en cuenta que este enfoque puede ser adecuado para la corrección de errores de software en cosas como flash NAND. Para usarlo de forma útil para la corrección de errores de hardware, uno debería poder retrasar las operaciones de lectura hasta que se pueda procesar el ECC, o de lo contrario se necesitaría una tabla de valores de 'síndrome' y posiciones de bit.

Answer 2

Recientemente trabajé en la detección de errores CRC16 y la corrección de errores de un solo bit.

Aquí es la idea básica:

1. Suponga que tiene un solo bit de error.
2. Si los datos + crc no incluyen ningún error, el CRC será 0, de lo contrario no lo es.
3. Definimos el CRC enviado como CRC y CRC recibido como CRCr.
4. Luego los bits de error están dados por CRCox = CRCs^CRCr.
5. El resultado abarca errores CRC y errores de datos.
6. Tenga en cuenta qué relación existe entre CRCox y el error de bit.

¿Esto es claro? Tengo un trabajo sobre esto. Si quieres saber más, házmelo saber.

Answer 3

PUEDE hacer la corrección de errores de múltiples bits con CRC. Al mirar wikipedia, con referencias al trabajo de koopmans, un CRC puede detectar sus errores hamming_distance-1. La distancia de Hamming depende de la longitud de la carga útil y del polinomio de CRC en uso. Entonces, por ejemplo, el polinomio de Koopman de 0xBA0DC66B puede detectar hasta 5 bits de error en mensajes de hasta 16360 bits de longitud. El algoritmo descrito en los dos mensajes anteriores puede extenderse hasta tantos bits como sea necesario, pero el tiempo aumenta exponencialmente con la cantidad de bits que se deben corregir.

1. Calcular error CRC = CRC_gotten^CRC_expected.
2. Mire todos los mensajes de 1 bit posibles (es decir, todos 0, a 1 y todos 0) (hay casos de longitud de mensaje a evaluar. Observe que BITS no BYTES) y el error es el mensaje que genera el error CRC.
3. Invierte el bit detectado para corregir el error.

Si no puede encontrar 1 bit que coincida con el error CRC, mire todo 2 bit, 3 bits hasta su hamming_distance-1.Tenga en cuenta que esto se vuelve lento rápidamente, message_length squared para 2 bits, en cubos para 3 bits hasta la quinta potencia para cinco bits.