¿Es posible hacer la corrección del error rudimentaria con el CRC?

Question

Yo sé toda la intención de utilizar el CRC es hacer la detección de errores, pero he oído estado alguien que puede ser utilizado para hacer la corrección del error básico, además de la detección de errores. Estaba ansioso por ver si este era el caso, y si es así, lo poderoso que es? Es decir, nos referimos generalmente al 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 del error de un bit con un CRC. Supongamos una tiene un CRC "registro" y tiene funciones para ejecutar el algoritmo CRC adelante y hacia atrás un poco a la vez, haciendo caso omiso de los datos de entrada

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

uno Supongamos que tiene un paquete que se calcula de modo que la inicialización del crc a algún valor y funcionando crc_forward para cada bit (MSB primero) debe dar cero. Si se obtiene un valor de CRC que no sea cero, uno puede ejecutar el algoritmo de bits de datos (ignorando) inversa hasta que el valor CRC calculado es 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 útilmente emplear para la corrección de errores de hardware, habría que sea capaz de retrasar las operaciones de lectura hasta que la ECC se pudo procesar, o de lo que uno puede necesitar una tabla de valores 'síndrome' y las posiciones de bit.

Answer 2

Se puede hacer la corrección del error de varios bits con CRC. En cuanto a la wikipedia, con referencias a Koopmans trabajo, un CRC puede detectar hasta sus errores hamming_distance-1. La distancia de Hamming depende de la longitud de carga útil, y el polinomio CRC en uso. Así, por ejemplo Koopmans polinómica de 0xBA0DC66B puede detectar hasta 5 bits de error en los mensajes hasta 16360 bits de longitud. El algoritmo descrito en los dos mensajes anteriores se puede extender hasta tantos bits como sea necesario, pero el tiempo aumenta exponencialmente con el número de bits de arreglar.

1. Calcular error CRC = CRC_gotten ^ CRC_expected.
2. Mire a través de todos los posibles mensajes de 1 bit (es decir, todos 0, un 1, y todos 0) (hay casos message_length a evaluar. Tenga en cuenta que esto es BITS no bytes) y el bit de error es el mensaje que genera el error CRC.
3. Invertir el bit detectado para corregir el error.

Si usted no puede encontrar 1 bit que coincide con el error de CRC, mirada a través de los 2 bits, 3 bits hasta su hamming_distance-1. Tenga en cuenta que esto se pone lento rápido, message_length cuadrado de 2 bits, en cubos de 3 bits a la quinta potencia de cinco bits.

Answer 3

Hace poco trabajó en la detección de errores CRC 16 y corrección de errores de un solo bit.

Aquí está la idea básica:

1. Suponga que tiene un solo bit de error.
2. Si los datos + CRC incluye ningún error, el CRC será 0, de lo contrario no lo es.
3. Se define el CRC enviado como CRC y CRC recibidos como crcr.
4. A continuación, los bits de error están dadas por CRCox = CRCs ^ CRCr.
5. El resultado abarca tanto errores y datos CRC errores.
6. Tienes vistazo a lo que la relación entre CRCox y el error es poco.

¿Está claro? Tengo un papel en esto. Si quieres saber más, házmelo saber.