Enviás un archivo, pero ¿cómo sabés que llegó intacto? Es decir, ¿cómo sabés que no se cortó, se corrompió o cambió de alguna manera? De forma simplista, podrías simplemente sumar todos los bytes del archivo (un checksum) y enviarlo junto con el archivo. Calculás el checksum cuando sabés que el archivo está bien, y el receptor compara los checksums para ver si coinciden.

Sin embargo, una suma simple no detecta ciertas clases de errores, y por eso existen mejores algoritmos de checksum que, por ejemplo, envuelven el bit de acarreo o modifican archivos con errores comunes para que produzcan checksums distintos.

Hay dos problemas con los checksums. Primero: por más que modifiques el algoritmo, las probabilidades de que dos archivos produzcan el mismo checksum son bastante altas, especialmente con patrones de error comunes.

Por ejemplo, asumí un algoritmo muy simple que solo suma los bytes y descarta cualquier acarreo. Si un archivo contiene 0x80, 0x80, esos números esencialmente se cancelan entre sí. Si los reemplazás con 0, 0, vas a obtener el mismo checksum. En cierta medida, usar cualquier cosa que no sea una segunda copia del archivo completo va a tener este problema (alguna corrupción pasa sin ser detectada), pero querés minimizar la cantidad de veces que eso ocurre.

El otro problema es que un checksum por sí mismo no te permite corregir nada. Sabés que los datos están mal, pero no sabés por qué. Si lo pensás, el checksum más simple es un bit de paridad sobre un byte: paridad impar es simplemente sumar todos los bits. Si el bit de paridad no coincide, sabés que el byte está mal, pero no sabés por qué. Cualquier número par de errores pasa sin detección, pero estoy seguro de que errores de 1, 3, 5 o 7 bits van a quedar atrapados.

La gente inventa códigos de chequeo de errores mejores diseñando esquemas que pueden prometer detectar cierto número de cambios de bit y, al menos en algunos casos, corregirlos. Uno de estos es el chequeo de redundancia cíclica (CRC). Es fácil pensar el CRC como un "checksum fuerte", pero en realidad funciona de manera diferente. Y, lo que es más, no existe un solo algoritmo CRC. Tenés que seleccionar o diseñar un algoritmo en particular basado en tus necesidades. La mayoría de la gente elige una implementación con nombre como CCITT o Ethernet y asume que debe ser la mejor. Probablemente no lo sea.

Un CRC es un checksum en sentido amplio: le pasás un mensaje y te devuelve un valor pequeño que agregás, almacenás o comparás después. Pero a diferencia de un checksum aditivo simple, un CRC se basa en división polinomial sobre GF(2), que es una forma elegante de decir "dividir usando XOR en lugar de acarreos". Ese detalle importa. Le da a los CRC garantías muy fuertes contra clases comunes de errores, siempre que elijas el polinomio correcto para el trabajo. Esa es la clave.

La máquina polinomial

Un CRC trata tu mensaje como un polinomio binario largo. Por ejemplo, el flujo de bytes se interpreta como una secuencia de coeficientes: cada bit está presente o ausente. El algoritmo CRC divide el polinomio del mensaje, después de desplazarlo por el ancho del CRC, por un polinomio generador. El resto es el CRC.

En aritmética normal, la división involucra resta y acarreos. En aritmética CRC, la resta es XOR. Por eso el código CRC a menudo se ve así:

Código
if (crc & topbit)
    crc = (crc << 1) ^ poly;
else
    crc <<= 1;

Ese loop está implementando división polinomial larga, un bit a la vez. El polinomio generador es el número mágico. Para un CRC de 16 bits, el polinomio tiene grado 16. Para uno de 32, grado 32. Usualmente lo vas a ver escrito como una constante hexadecimal, como 0x1021 para CRC-16/CCITT o 0x04C11DB7 para el clásico CRC-32 de Ethernet, ZIP y PNG.

Qué atrapan los CRC

Un CRC bien elegido puede garantizar detección de todos los errores de un bit, muchos errores multi-bit, todos los errores en ráfaga hasta cierta longitud, y un porcentaje muy alto de errores aleatorios más largos. La métrica clave es la distancia de Hamming, a menudo abreviada HD. Si un CRC tiene HD=4 para mensajes de cierta longitud, detecta todos los errores de 1, 2 y 3 bits en mensajes de esa longitud.

Ese último calificativo es importante. La fuerza del CRC no es simplemente "CRC de 16 bits bueno, CRC de 32 bits mejor". Depende de la longitud máxima del mensaje. Un polinomio excelente para paquetes embebidos de 32 bytes puede ser mediocre para mensajes de kilobytes. Un polinomio estandarizado hace décadas puede ser familiar pero no óptimo.

El trabajo de Philip Koopman en Carnegie Mellon es la referencia obligada acá. El paper de Koopman y Chakravarty sobre selección de polinomios CRC para redes embebidas específicamente buscó buenos polinomios CRC para mensajes embebidos cortos, y las tablas "Best CRC Polynomials" de Koopman listan polinomios por ancho y rendimiento de distancia de Hamming.

Famoso no significa óptimo

Tomá CRC-16/CCITT, polinomio 0x1021. Se encuentra en todos lados: telecom, ejemplos embebidos y bootloaders. No es un polinomio terrible, pero no es automáticamente la mejor opción de 16 bits. Las tablas de Koopman incluyen otros polinomios de 16 bits con mejor comportamiento de distancia de Hamming sobre longitudes útiles de mensajes embebidos.

De manera similar, el CRC-32 clásico que usa el polinomio 0x04C11DB7 está profundamente arraigado por Ethernet, ZIP, gzip y PNG. Pero CRC-32C, el polinomio de Castagnoli, suele ser una mejor opción de propósito general. Tiene excelentes propiedades de detección de errores sobre longitudes comunes de mensajes y, además, está soportado por instrucciones de hardware en muchas CPUs modernas (incluyendo las extensiones SSE 4.2 de Intel y las equivalentes en ARMv8).

¿Qué CRC conviene en un proyecto Arduino o ESP32?

Para mensajes cortos típicos de un microcontrolador (frames de bus CAN, paquetes Zigbee, mensajes Modbus), las tablas de Koopman recomiendan polinomios distintos al CCITT por defecto que viene en muchas librerías Arduino. Antes de copiar y pegar la primera implementación que aparezca, vale la pena consultar las tablas y elegir el polinomio con la mejor distancia de Hamming para el largo máximo de tu mensaje. La diferencia puede ser detectar 3 errores en lugar de 2, lo que en un canal RF ruidoso se traduce directamente en menos paquetes corruptos pasando sin alarma.