Eficiencia de detección de errores (CRC, suma de verificación, etc.)

Question

Tengo una situación hipotética de enviar unidades de datos, cada una de las miles de bytes. La tasa de falla es rara, pero cuando ocurre un error, es menos probable que sea un error de bit y más probable que sea un error en algunos bits seguidos.

Al principio pensé en usar una suma de verificación, pero aparentemente eso puede perder errores de bit más que un solo bit. Una verificación de paridad tampoco funcionará, por lo que CRC podría ser la mejor opción.

¿El uso de una verificación de redundancia cíclica es eficiente en miles de bytes? ¿O hay otros métodos que funcionarían mejor?

Answer 1

Las verificaciones de redundancia cíclica (CRC) son populares específicamente Debido a su eficiencia en la detección de errores de bits con una precisión garantizada.

Existen diferentes diseños para generar polinomios CRC donde la compensación es la precisión frente a la complejidad computacional. En su caso, puede elegir el "más rápido" que cumpla con sus requisitos de precisión.

Es posible que desee comenzar con este artículo de Wikipedia sobre el Verificación de redundancia cíclica.

Answer 2

CRC está cubierto en otra pregunta aquí
¿Cuándo es más apropiado CRC que MD5/SHA1?
Es adecuado para detectar errores aleatorios y fáciles de implementar.

Answer 3

Es normal usar un CRC. No estoy seguro de lo que quieres decir con 'eficiencia', pero creo que a veces el CRC se implementa en hardware (por ejemplo, en la tarjeta Ethernet). De lo contrario, puede encontrar implementaciones 'optimizadas' (usando una tabla de búsqueda).

Answer 4

¿Qué tan grandes son sus sectores de disco? Probablemente al menos 512 bytes. Y CRC es un esquema tradicional para el disco de nivel de hardware ECC.

Los algoritmos polinomiales CRC Stock son bastante efectivos para un pequeño número de errores de bits. La precisión exacta es matemáticamente computable. El CRC también es altamente eficiente en el hardware, donde un número relativamente pequeño de puertas y registros de turnos puede administrar el trabajo sobre la marcha.