Detección de errores

01 · Objetivo

Saber que algo falló

Los temas anteriores dejaron esta cola sin explicar: SUMA en el paquete del tema 41 y del 42, CRC en Modbus (tema 25), el octavo byte de un código ROM de 1-Wire (tema 21), los cuatro bytes finales de una trama Ethernet (tema 29). Todas hacen lo mismo: agregan redundancia, información que no aporta nada nuevo pero permite comprobar el resto. El receptor repite el cálculo sobre lo que recibió y compara con lo que acompañaba al mensaje. Si no coinciden, algo del mensaje o de la verificación cambió en el camino, y el mensaje se descarta o se pide de nuevo.

Lo que hace falta saber para elegir bien es de qué depende la calidad de esa función f: cuántos bits tiene la verificación (a más bits, menos errores se le escapan), qué tipos de daño garantiza detectar (un bit, dos bits, una ráfaga, un cambio de orden), cuánto cuesta calcularla en tiempo y memoria, y qué cubre dentro del paquete. Ningún método detecta el cien por ciento: toda verificación de n bits deja pasar alguna fracción de los daños, que para un daño al azar es 1/2n. La diferencia entre los métodos está en qué daños garantizan atrapar y cuáles dejan para el azar.

02 · La idea

Redundancia y distancia

Si un mensaje de 4 bits puede ser cualquiera de las 16 combinaciones, todas son válidas: toda alteración produce otro mensaje válido, y no hay forma de saberlo. Para detectar, hace falta que no todas las combinaciones sean válidas. Se agregan bits que dependen de los datos, y solo algunas combinaciones del conjunto, las palabras de código, son legales. Un error que transforma una palabra de código en otra combinación que no lo es, se detecta. Uno que la transforma justo en otra palabra de código, no.

La medida de qué tan bien lo hace un código es la distancia de Hamming d: la cantidad mínima de bits que hay que cambiar para pasar de una palabra de código a otra. Si d = 2, cambiar un bit nunca lleva a otra palabra válida: se detecta cualquier error de un bit. En general, un código de distancia d detecta cualquier daño de hasta d − 1 bits (y, como se verá en el tema 45, puede corregir hasta (d − 1)/2 bits). Los daños de más de d − 1 bits pueden llevar a otra palabra válida o no, y de ahí sale la fracción residual de 1 en 2ⁿ.

Ese equilibrio se ve en los tres grandes métodos: la paridad (1 bit, distancia 2), las sumas (8 o 16 bits, baratas, con puntos ciegos) y el CRC (8, 16 o 32 bits, con garantías sobre ráfagas y un costo algo mayor). Para un dato que cuesta poco perder (una temperatura que se repite cada segundo) alcanza lo barato; para uno que cuesta mucho aceptar mal (una orden de actuación, una actualización de firmware) hace falta más.

03 · Un bit de más

El bit de paridad

Es el método más simple. A un grupo de bits se le agrega uno más, elegido para que la cantidad total de unos sea par (paridad par) o impar (paridad impar). El receptor cuenta los unos: si la cantidad tiene la paridad esperada, acepta; si no, hubo un error. El byte 0x2E (00101110) tiene cuatro unos, por lo que su bit de paridad par es 0; el 0x7C (01111100) tiene cinco, y el bit de paridad par es 1. Con paridad impar, los bits serían los complementarios. Es la paridad que activa la UART con el formato 8E1 u 8O1 (tema 7): cada byte lleva su propio bit.

Su garantía es exacta: detecta todo daño que cambie un número impar de bits (uno, tres, cinco…) y ninguno que cambie un número par, porque dos inversiones se compensan y la cuenta de unos queda con la misma paridad. Cuesta un bit por bloque, pero eso es mucho si el bloque es chico: un bit por byte es el 12,5 % de más. Y le va mal frente a las ráfagas: una de dos bits pasa siempre. Con una tasa de error de bit pequeña, la mayoría de los daños son de un solo bit y la paridad los atrapa (tema 43); por eso se usa en enlaces simples y en memorias, y por eso es insuficiente en uno ruidoso.

Paridad longitudinal y bidimensional

Se puede aplicar la paridad por columnas también. La paridad longitudinal (LRC, longitudinal redundancy check) es el XOR de todos los bytes del mensaje: cada bit del resultado es la paridad par de una columna. Con un LRC de un byte al final, más la paridad de cada byte, se obtiene una paridad bidimensional:

Con las dos paridades, un error de un bit hace fallar una fila y una columna, y su cruce localiza el bit, que se puede corregir invirtiéndolo: es la idea que se retoma en el tema 45. Dos errores que caen en el mismo par de filas y columnas (cuatro bits en las esquinas de un rectángulo) siguen sin verse. Con dos bits alterados en filas y columnas distintas, la detección es segura pero la ubicación es ambigua. Costo: un bit por byte más un byte por mensaje.

04 · Sumar para comprobar

Sumas de verificación

Una suma de verificación (checksum) trata los bytes como números y los combina con operaciones aritméticas simples. Es muy barata en un microcontrolador: una suma por byte. Las variantes más comunes:

Para el mensaje 2E 09 7C 15, el XOR da 4E; la suma de los cuatro bytes es 0xC8, y su complemento a dos, 0x38, que es lo que se transmite (así el receptor suma todo, verificación incluida, y espera 0). Fletcher-16 de la cadena «abcde» da 0xC8F0, y la suma de Internet de los bytes 00 01 F2 03 F4 F5 F6 F7, 0x220D. La herramienta 1 las calcula para cualquier mensaje.

Su problema son los puntos ciegos, porque la suma y el XOR son operaciones conmutativas y no distinguen cómo se llegó al resultado:

• El orden de los bytes no importa. 12 34 y 34 12 tienen la misma suma y el mismo XOR. Un intercambio de dos bytes pasa inadvertido.
• Los daños se compensan. Si un byte sube en 1 (2E → 2F) y otro baja en 1 (09 → 08), la suma queda igual. Con el XOR pasa algo análogo: dos bits invertidos en la misma columna se anulan. En la simulación de la herramienta 4, con dos bits invertidos en un mensaje de 8 bytes, la suma de un byte deja pasar el 6 % de los daños y la paridad total, todos.
• Los ceros no cuentan. Insertar o quitar bytes 00 no cambia la suma: un byte nulo de más o de menos pasa inadvertido (Fletcher lo nota por la segunda suma, la de Internet no).
• No garantizan nada sobre las ráfagas de más de unos bits, y una suma de n bits deja pasar alrededor de 1/2ⁿ de los daños aleatorios, pero con una distribución peor que la de un CRC.

Fletcher-16 mejora la sensibilidad al orden, y la suma de Internet es un compromiso pensado para calcularse rápido en cualquier procesador y actualizarse de forma incremental cuando un router cambia unos campos. Para un paquete de sensores sobre un cable corto, una suma de un byte puede ser suficiente. Para un bus industrial o una radio, no: ahí hace falta algo con garantías.

05 · El estándar

El CRC: la división por un polinomio

El CRC (cyclic redundancy check) parte de una idea sencilla: tratar el mensaje como un número muy grande y calcular el resto de dividirlo por otro número fijo, el generador. El resto es la verificación. Para que sea eficiente en un circuito, la división no usa aritmética común sino aritmética sin acarreo, en la que sumar y restar son la misma operación, el XOR. Así, cada bit del mensaje es un coeficiente 0 o 1 de un polinomio (el mensaje 1101 es x³ + x² + 1), el generador es otro polinomio (1011 es x³ + x + 1), y la división es la de polinomios con coeficientes módulo 2. El resultado, de grado menor que el del generador, tiene tantos bits como el grado: n bits de CRC con un generador de grado n.

El cálculo se hace así, como muestra la figura: se agregan n ceros al mensaje, y se recorre de izquierda a derecha; cada vez que aparece un 1 al frente, se resta (XOR) el generador alineado con ese 1. Al final quedan n bits: el CRC. Para el mensaje 1101 y el generador 1011, el CRC es 001, y se transmite 1101 001. El receptor divide los 7 bits recibidos por el mismo generador: 1101001 ÷ 1011 deja resto 000. Si algún bit cambió, el resto es distinto de cero, salvo que el daño sea justo un múltiplo del generador. Con 1100001 (un bit cambiado) el resto es 011, y con 1101011, 010: detectados.

Qué garantiza

Lo importante es que, a diferencia de la suma, el CRC tiene propiedades demostrables, que dependen del generador pero valen para cualquier mensaje:

• Detecta toda ráfaga de hasta n bits, es decir, cualquier daño contenido en n bits consecutivos, sin importar los valores. Un CRC-16 detecta con seguridad cualquier interferencia que dañe hasta 16 bits seguidos. Es la propiedad más valiosa frente a las interferencias del tema 43.
• Detecta todos los daños de 1, 2 y 3 bits (con un buen generador) si el mensaje no es demasiado largo; por ejemplo, el CRC-8 de polinomio 0x07 hasta unos 119 bits (14 bytes), y el CRC-16 de Modbus hasta miles de bits.
• Con un generador que tenga el factor (x + 1) (como el de Modbus, 0x8005), detecta todos los daños de un número impar de bits, como la paridad.
• Para cualquier otro daño, más largo o más complejo, deja pasar la fracción 1/2ⁿ (1/256 con n = 8, 1/65 536 con n = 16, una en 4300 millones con n = 32), la mejor que puede lograr una verificación de n bits.
• Es sensible al orden y a la posición: cada bit contribuye según el lugar que ocupa. Intercambiar bytes, o insertar un cero, cambia el CRC.

Y conserva una propiedad práctica que se aprovecha en el receptor: si se calcula el CRC sobre el mensaje con su CRC al final, el resultado es siempre el mismo valor fijo (cero, en la mayoría de los algoritmos): no hace falta separar el mensaje de su verificación para comparar. La herramienta 2 muestra ese resultado.

Como el CRC es lineal (el CRC del XOR de dos mensajes es el XOR de sus CRC), un daño se detecta o no según su forma, no según el mensaje: la pregunta es siempre si el patrón de bits alterados es un múltiplo del generador. Esa es la razón de que la herramienta 4 pueda probar con mensajes al azar y obtenga resultados estables. También implica una advertencia de seguridad: un CRC protege contra el azar, pero no contra alguien que modifica el mensaje y recalcula el CRC (tema 49).

06 · Un catálogo

Los CRC de uso común

Existen decenas de CRC, y dos que se llaman igual («CRC-16») pueden ser distintos. Un CRC se define con cinco parámetros además del ancho: el polinomio, el valor inicial del registro, si se procesan los bits reflejados (el menos significativo primero, como el UART y Ethernet) y el XOR final. Cada uno cambia el resultado. La prueba de que una implementación es la correcta es el valor de verificación: el CRC del texto ASCII 123456789, que todos los catálogos publican.

Otros que aparecen en el curso, con distinto ancho: el CRC-15 de CAN (tema 27), el CRC-7 y el CRC-16 de las tarjetas SD en modo SPI (tema 14), y los CRC-5 y CRC-16 de USB. La enseñanza de la tabla es doble. Primero, «CRC-16» no alcanza como especificación: Modbus, CCITT-FALSE y XMODEM dan resultados distintos con los mismos datos, y dos equipos que los eligen sin acordar no se entienden. Al documentar un protocolo propio hay que escribir los cinco parámetros o nombrar el catálogo (como «CRC-16/MODBUS»), y publicar un vector de prueba. Segundo, el XOR final y el valor inicial no son decoración: un valor inicial distinto de cero hace que el CRC de un mensaje que empieza con ceros no sea siempre cero; el XOR final, que un mensaje vacío no tenga siempre el mismo CRC que otro.

07 · Cómo se programa

Cómo se calcula un CRC

Hay tres formas de calcular un CRC, que difieren en velocidad y memoria:

La implementación bit a bit se escribe directamente de la definición. Para un CRC no reflejado, se coloca el byte en la parte alta del registro y se desplaza a la izquierda; para uno reflejado, se hace al revés, desplazando a la derecha con el polinomio con sus bits invertidos (el de Modbus, 0x8005, queda 0xA001). La versión por tabla aprovecha que el efecto de un byte entero sobre el registro depende solo de ese byte combinado con el registro: se calcula 256 veces, una por valor, y después cada byte del mensaje es una consulta y un XOR. La tabla se arma con el mismo código bit a bit aplicado a cada valor de 0 a 255 (la sección 9 lo hace), y se verifica con el valor de prueba. Qué se elige es una decisión de memoria contra velocidad, y para un enlace a 9600 baudios (un byte cada 1 ms) el método bit a bit sobra: un ESP32 calcula un CRC-16 de una trama de 10 bytes en una fracción de microsegundo por bit.

Tres errores de implementación son clásicos:

• Equivocarse en los parámetros: valor inicial, reflejo o XOR final. Es el error más común y no avisa: el CRC es un número cualquiera, solo que distinto del que calcula el otro extremo. Se previene con el vector de prueba 123456789 y, si es posible, con una trama real de otra implementación (como la de Modbus de los ejercicios).
• Enviar los bytes del CRC en el orden equivocado. Los CRC reflejados (Modbus, CRC-32) se envían con el byte bajo primero; los no reflejados, con el alto primero. Si el receptor espera el otro orden, ninguna trama valida, aunque el cálculo sea correcto. La herramienta 2 muestra el orden de transmisión de cada uno.
• Calcular sobre un rango distinto del que calcula el otro extremo: incluir o no el delimitador de inicio, el largo, las direcciones. Se resuelve definiendo con claridad qué cubre (sección 8).

Verificar en el receptor se puede hacer de dos maneras equivalentes: recalcular el CRC sobre los datos y compararlo con el recibido, o recalcular sobre datos y CRC juntos y esperar el residuo fijo (cero en los CRC sin XOR final, 0x2144DF1C en el CRC-32). La segunda evita separar el CRC de la trama y tiene un detalle: se necesita el orden de bytes correcto del CRC al final.

08 · Tamaño y lugar

Elegir y colocar la verificación

Qué tamaño

La verificación se elige según el costo de aceptar un mensaje dañado, comparado con el costo de agregar bytes a cada trama. El cálculo conservador es sencillo: se supone que cada trama dañada tiene un daño tan grande que la verificación de n bits lo deja pasar con probabilidad 2⁻ⁿ, y se multiplica por las tramas dañadas por unidad de tiempo (tema 43). La herramienta 5 lo hace. Con el ejemplo del tema 43 (tasa de error de bit de 10⁻⁵, tramas de 10 bytes a 9600 baudios, unas 345 tramas dañadas por hora), una verificación de 8 bits aceptaría una trama dañada cada 44 minutos en el peor caso, una de 16 bits cada 7,9 días, y una de 32 bits, una cada 1400 años. Es una cota muy pesimista (los daños de uno a tres bits los detectan todos los CRC), pero muestra el orden de magnitud: para datos que se repiten y se filtran, 8 bits pueden alcanzar; para órdenes o configuraciones, 16 es el mínimo razonable, y 32 para firmware, archivos o tramas largas.

Un CRC de n bits protege mejor a mensajes cortos: sus garantías sobre 1, 2 y 3 bits valen hasta cierto largo, y pasado ese largo hay daños de pocos bits que se escapan. Por eso las tramas largas llevan CRC más largos (32 bits en Ethernet con 1500 bytes) y las cortas pueden usar menos.

Qué cubre y dónde va

La verificación va en la cola del paquete (tema 42), y cubre todo lo que sigue al delimitador de inicio: el largo, las direcciones, el tipo y los datos. Que cubra las direcciones es esencial: un destino alterado enviaría el paquete al nodo equivocado. Que cubra el largo, también: es lo que permite al receptor saber dónde termina. El delimitador SOF queda afuera porque es una constante que el receptor ya conoce. Si se pasa del paquete de los temas anteriores al CRC-16, el único cambio es la cola, que pasa de 1 a 2 bytes, y la cuenta de cuántos bytes se esperan tras el largo (de LEN + 1 a LEN + 2):

A5 07 02 01 01 2E 09 7C 15 26 19: 11 bytes, con el CRC-16/Modbus 0x1926 de los ocho bytes 07 02 01 01 2E 09 7C 15, transmitido con el byte bajo primero (26 19). Al validar, el receptor calcula el CRC sobre los bytes que van del LEN al final y espera cero. Es un cambio de formato: conviene que el protocolo tenga un campo de versión (tema 41) para que un nodo con suma de un byte no entienda mal a uno con CRC-16 sin avisar.

Qué no hace un CRC

• No corrige: detecta que algo cambió, pero no dice qué ni dónde. Para reparar hace falta reenviar (tema 45) o un código corrector.
• No detecta lo que no daña los bits: una trama perdida, duplicada o recibida fuera de orden tiene un CRC perfecto. Eso lo cubren los números de secuencia (tema 45).
• No detecta un mensaje bien formado pero equivocado: un sensor que entrega un valor absurdo, con CRC correcto. Eso es validación de la aplicación.
• No protege contra un atacante: cualquiera puede modificar el mensaje y recalcular el CRC. Para la autenticidad, se usa un código criptográfico (tema 49).

09 · Con el microcontrolador

CRC-8 y CRC-16 en el programa

El programa siguiente implementa las dos formas (bit a bit y por tabla), las verifica con los valores de referencia, valida una trama real de Modbus, arma el paquete del tema 42 con un CRC-16 en lugar de la suma, y hace un experimento: invierte K_BITS bits al azar en 100 000 mensajes de 8 bytes y cuenta cuántos daños se le escapan a la suma de un byte, al CRC-8 y al CRC-16. Al final mide cuánto tarda cada método. Se carga en un ESP32 o un Arduino y se mira por el monitor serie.

// ---------- Configuración ----------
const uint8_t  K_BITS = 2;                                     // bits que se invierten en cada prueba del experimento
const uint32_t PRUEBAS = 100000;

// ---------- Sumas ----------
uint8_t suma8(const uint8_t *d, size_t n) {                    // la suma de los temas 41 y 42
    uint8_t s = 0;
    while (n--) s += *d++;
    return (uint8_t)(0x100 - s);
}

// ---------- CRC-8 (polinomio 0x07, sin reflejo, inicio 0), bit a bit ----------
uint8_t crc8(const uint8_t *d, size_t n) {
    uint8_t crc = 0x00;
    while (n--) {
        crc ^= *d++;                                           // el byte entra por la parte alta del registro
        for (uint8_t i = 0; i < 8; i++) crc = (crc & 0x80) ? (crc << 1) ^ 0x07 : crc << 1;
    }
    return crc;
}

// ---------- CRC-16/Modbus (polinomio 0xA001 reflejado, inicio 0xFFFF), bit a bit ----------
uint16_t crc16Bits(const uint8_t *d, size_t n) {
    uint16_t crc = 0xFFFF;
    while (n--) {
        crc ^= *d++;
        for (uint8_t i = 0; i < 8; i++) crc = (crc & 1) ? (crc >> 1) ^ 0xA001 : crc >> 1;
    }
    return crc;
}

// ---------- CRC-16/Modbus por tabla: una consulta por byte ----------
uint16_t tabla16[256];                                         // 512 bytes de RAM; también puede ir en flash
void armarTabla16() {
    for (uint16_t n = 0; n < 256; n++) {                       // el resultado de procesar el byte n con el registro en cero
        uint16_t r = n;
        for (uint8_t i = 0; i < 8; i++) r = (r & 1) ? (r >> 1) ^ 0xA001 : r >> 1;
        tabla16[n] = r;
    }
}
uint16_t crc16(const uint8_t *d, size_t n) {
    uint16_t crc = 0xFFFF;
    while (n--) crc = (crc >> 8) ^ tabla16[(crc ^ *d++) & 0xFF];
    return crc;
}

// ---------- El paquete del tema 42 con CRC-16 ----------
const uint8_t SOF = 0xA5;

uint8_t armarPaquete(uint8_t *p, uint8_t dst, uint8_t src, uint8_t tipo, const uint8_t *datos, uint8_t n) {
    p[0] = SOF;
    p[1] = n + 3;                                              // el largo cuenta destino, origen, tipo y datos
    p[2] = dst;
    p[3] = src;
    p[4] = tipo;
    memcpy(p + 5, datos, n);
    uint16_t c = crc16(p + 1, n + 4);                          // cubre desde el largo hasta el final de los datos
    p[5 + n] = c & 0xFF;                                       // el byte bajo primero, como Modbus
    p[6 + n] = c >> 8;
    return n + 7;                                              // bytes totales
}

bool paqueteValido(const uint8_t *p, uint8_t total) {          // total incluye SOF y CRC
    return total >= 7 && p[0] == SOF && p[1] + 4 == total && crc16(p + 1, total - 1) == 0;   // el residuo de datos más CRC es cero
}

// ---------- Pruebas ----------
void imprimir(const char *t, const uint8_t *p, uint8_t n) {
    Serial.print(t);
    for (uint8_t i = 0; i < n; i++) Serial.printf(" %02X", p[i]);
    Serial.println();
}

void autoprueba() {
    const uint8_t v[] = { '1', '2', '3', '4', '5', '6', '7', '8', '9' };
    Serial.printf("CRC-8 de 123456789: %02X (esperado F4)\n", crc8(v, 9));
    Serial.printf("CRC-16/Modbus de 123456789: %04X por bits, %04X por tabla (esperado 4B37)\n", crc16Bits(v, 9), crc16(v, 9));
    const uint8_t modbus[] = { 0x01, 0x03, 0x00, 0x00, 0x00, 0x0A };
    Serial.printf("trama Modbus 01 03 00 00 00 0A: CRC %04X (esperado CDC5: se envía C5 CD)\n", crc16(modbus, 6));
    const uint8_t datos[] = { 0x2E, 0x09, 0x7C, 0x15 };
    uint8_t p[16];
    uint8_t total = armarPaquete(p, 0x02, 0x01, 0x01, datos, 4);
    imprimir("paquete con CRC-16:", p, total);
    Serial.printf("válido: %s\n", paqueteValido(p, total) ? "sí" : "no");
    p[5] ^= 0x01; p[6] ^= 0x01;                                // dos bits en la misma columna: la suma no los vería
    Serial.printf("con dos bits invertidos: %s (la suma de un byte: %s)\n", paqueteValido(p, total) ? "válido" : "inválido",
                  suma8(p + 1, 8) == 0x2D ? "no los ve" : "los ve");
}

void experimento() {
    uint8_t m[8], d[8];
    uint32_t pasoSuma = 0, pasoC8 = 0, pasoC16 = 0;
    for (uint32_t t = 0; t < PRUEBAS; t++) {
        for (uint8_t i = 0; i < 8; i++) m[i] = d[i] = random(256);
        uint64_t elegidos = 0;                                 // un bit por posición, para no repetir
        for (uint8_t k = 0; k < K_BITS; ) {
            uint8_t pos = random(64);
            if (elegidos & (1ULL << pos)) continue;
            elegidos |= 1ULL << pos;
            d[pos >> 3] ^= 1 << (pos & 7);
            k++;
        }
        if (suma8(m, 8) == suma8(d, 8)) pasoSuma++;
        if (crc8(m, 8) == crc8(d, 8)) pasoC8++;
        if (crc16(m, 8) == crc16(d, 8)) pasoC16++;
    }
    Serial.printf("con %u bits invertidos en %lu pruebas, sin detectar: suma %lu, CRC-8 %lu, CRC-16 %lu\n",
                  K_BITS, (unsigned long)PRUEBAS, (unsigned long)pasoSuma, (unsigned long)pasoC8, (unsigned long)pasoC16);
}

void medirTiempos() {
    uint8_t buf[64];
    for (uint8_t i = 0; i < 64; i++) buf[i] = i * 7;
    volatile uint16_t sumidero = 0;
    unsigned long t0 = micros();
    for (int i = 0; i < 1000; i++) sumidero = crc16Bits(buf, 64);
    unsigned long bits = micros() - t0;
    t0 = micros();
    for (int i = 0; i < 1000; i++) sumidero = crc16(buf, 64);
    unsigned long tabla = micros() - t0;
    Serial.printf("CRC-16 de 64 bytes: %.2f µs bit a bit, %.2f µs por tabla\n", bits / 1000.0, tabla / 1000.0);
}

void setup() {
    Serial.begin(115200);
    armarTabla16();
    autoprueba();
    experimento();
    medirTiempos();
}

void loop() {}

Qué hay que notar:

• Las funciones son cortas, y los parámetros están a la vista: el polinomio, el valor inicial y el sentido del desplazamiento. Si un CRC no coincide con el de otro equipo, son esos tres números (y el orden de los bytes de salida) los sospechosos. El autoprueba compara con los valores de referencia: es la primera verificación de cualquier implementación nueva.
• La tabla se arma con el mismo cálculo bit a bit, aplicado una vez a cada valor de byte, y después el cálculo por byte es una consulta y un XOR. Las dos versiones del CRC-16 tienen que dar el mismo resultado; crc16Bits queda como referencia para comprobarlo. En un microcontrolador con poca RAM, la tabla se declara const y va en flash (en un AVR, con PROGMEM).
• La validación del receptor es una línea: crc16(p + 1, total − 1) == 0. Se calcula sobre todo, del largo al CRC, y el residuo debe ser cero. Eso solo vale con el CRC enviado en el orden correcto (el bajo primero en este algoritmo); con el orden invertido, ninguna trama valida.
• El experimento reproduce la herramienta 4: con K_BITS = 2, la suma deja pasar alrededor del 6 % y los dos CRC, ninguno; con K_BITS = 4 aparecen unos pocos casos para los CRC (del orden de 1 en 100 para el CRC-8 y 1 en mil o menos para el CRC-16); con 8, el CRC-8 deja pasar cerca del 0,4 al 0,8 % y el CRC-16 una fracción mucho menor. Las cantidades varían con el generador de números aleatorios de la placa.
• La medición de tiempos muestra el compromiso: la versión por tabla es varias veces más rápida que la de bits, con el costo de 512 bytes. A 9600 baudios un byte tarda 1 ms en llegar, de modo que cualquiera de las dos sobra; a 1 Mbaudio o con tramas de kilobytes, la tabla (o el hardware) se vuelve necesaria.
• Para integrar el CRC al receptor del tema 42, solo cambian dos cosas: la cantidad de bytes que se esperan tras el largo (b + 2 en lugar de b + 1) y la comprobación final (crc16(buf, n) == 0 en lugar de sumar y comparar con cero).
• En un Arduino sin printf en Serial, se reemplaza por Serial.print; sin uint64_t eficiente (AVR), el experimento usa un arreglo de banderas.

10 · Analogía con programación

Verificaciones en Python

Todas las verificaciones del tema se prueban sin hardware, y el CRC genérico (con los cinco parámetros) cabe en pocas líneas. El modelo siguiente calcula los seis CRC del catálogo, arma el paquete con CRC-16, muestra los puntos ciegos de la suma y repite el experimento de daños con un generador de números aleatorios determinista, el mismo de la página, para que las cantidades coincidan con las de la herramienta 4.

MASCARA = 0xFFFFFFFF


def invertir(v, ancho):
    return int(f"{v:0{ancho}b}"[::-1], 2)


def crc(datos, ancho, poli, inicio=0, reflejado=False, xor_final=0):
    """CRC genérico bit a bit con los cinco parámetros del catálogo."""
    mascara = (1 << ancho) - 1
    reg = inicio
    if reflejado:
        poli_r = invertir(poli, ancho)
        for b in datos:
            reg ^= b
            for _ in range(8):
                reg = (reg >> 1) ^ poli_r if reg & 1 else reg >> 1
    else:
        for b in datos:
            reg ^= b << (ancho - 8)
            for _ in range(8):
                reg = ((reg << 1) ^ poli) & mascara if (reg >> (ancho - 1)) & 1 else (reg << 1) & mascara
    return reg ^ xor_final


def tabla(ancho, poli, reflejado):
    return [crc([n], ancho, poli, 0, reflejado) for n in range(256)]   # la entrada n es el CRC del byte n con registro en cero


def crc_tabla(t, datos, ancho, inicio=0, reflejado=False, xor_final=0):
    reg = inicio
    for b in datos:
        if reflejado:
            reg = (reg >> 8) ^ t[(reg ^ b) & 0xFF]
        else:
            reg = ((reg << 8) & ((1 << ancho) - 1)) ^ t[((reg >> (ancho - 8)) ^ b) & 0xFF]
    return reg ^ xor_final


ALG = {                                                       # ancho, polinomio, inicio, reflejado, XOR final
    "CRC-8":              (8, 0x07, 0x00, False, 0x00),
    "CRC-8/Maxim":        (8, 0x31, 0x00, True, 0x00),
    "CRC-16/Modbus":      (16, 0x8005, 0xFFFF, True, 0x0000),
    "CRC-16/CCITT-FALSE": (16, 0x1021, 0xFFFF, False, 0x0000),
    "CRC-16/XMODEM":      (16, 0x1021, 0x0000, False, 0x0000),
    "CRC-32":             (32, 0x04C11DB7, 0xFFFFFFFF, True, 0xFFFFFFFF),
}


def suma8(datos):
    return (0x100 - sum(datos)) & 0xFF


def paridad_total(datos):
    return sum(bin(b).count("1") for b in datos) & 1


def fletcher16(datos):
    s1 = s2 = 0
    for b in datos:
        s1 = (s1 + b) % 255
        s2 = (s2 + s1) % 255
    return (s2 << 8) | s1


def mulberry32(semilla):
    a = semilla & MASCARA
    def siguiente():
        nonlocal a
        a = (a + 0x6D2B79F5) & MASCARA
        t = ((a ^ (a >> 15)) * (a | 1)) & MASCARA
        t ^= (t + (((t ^ (t >> 7)) * (t | 61)) & MASCARA)) & MASCARA
        return ((t ^ (t >> 14)) & MASCARA) / 4294967296
    return siguiente


def experimento(k, n_bytes=8, pruebas=20000, semilla=1):
    azar = mulberry32(semilla)
    t8, t16 = tabla(8, 0x07, False), tabla(16, 0x8005, True)
    perdidos = [0, 0, 0, 0]                                   # paridad total, suma, CRC-8, CRC-16
    for _ in range(pruebas):
        msg = [int(azar() * 256) for _ in range(n_bytes)]
        malo = msg[:]
        elegidos = set()
        while len(elegidos) < k:
            elegidos.add(int(azar() * n_bytes * 8))
        for p in elegidos:
            malo[p >> 3] ^= 1 << (p & 7)
        perdidos[0] += paridad_total(msg) == paridad_total(malo)
        perdidos[1] += suma8(msg) == suma8(malo)
        perdidos[2] += crc_tabla(t8, msg, 8) == crc_tabla(t8, malo, 8)
        perdidos[3] += crc_tabla(t16, msg, 16, 0xFFFF, True) == crc_tabla(t16, malo, 16, 0xFFFF, True)
    return perdidos


v = b"123456789"
for nombre, p in ALG.items():
    print(f"{nombre:20s} {crc(v, *p):0{p[0] // 4}X}")
print("Fletcher-16 de abcde:", f"{fletcher16(b'abcde'):04X}")

modbus = ALG["CRC-16/Modbus"]
cuerpo = bytes([0x07, 0x02, 0x01, 0x01, 0x2E, 0x09, 0x7C, 0x15])
c = crc(cuerpo, *modbus)
paquete = bytes([0xA5]) + cuerpo + bytes([c & 0xFF, c >> 8])
print("paquete con CRC-16:", paquete.hex(" ").upper(), len(paquete), "bytes; residuo:", crc(paquete[1:], *modbus))
print("trama Modbus 01 03 00 00 00 0A:", f"{crc(bytes([1, 3, 0, 0, 0, 10]), *modbus):04X}")

malo = bytearray(paquete)
malo[5] ^= 0x01
malo[6] ^= 0x01                                               # 2E→2F y 09→08: la suma de los datos no cambia
print("dos bits en la misma columna: suma", f"{suma8(cuerpo):02X}", "→", f"{suma8(bytes(malo[1:9])):02X}", "| residuo del CRC-16:", f"{crc(bytes(malo[1:]), *modbus):04X}")
print("12 34 y 34 12: suma", f"{suma8(bytes([0x12, 0x34])):02X}", f"{suma8(bytes([0x34, 0x12])):02X}", "| CRC-8", f"{crc(bytes([0x12, 0x34]), *ALG['CRC-8']):02X}", f"{crc(bytes([0x34, 0x12]), *ALG['CRC-8']):02X}")

for k in (1, 2, 3, 4, 8):
    p, s, c8, c16 = experimento(k)
    print(f"{k} bits invertidos en 20000 pruebas, sin detectar: paridad {p}, suma {s}, CRC-8 {c8}, CRC-16 {c16}")

Resultado: los seis CRC de «123456789» son F4, A1, 4B37, 29B1, 31C3 y CBF43926, los valores del catálogo, y Fletcher-16 de «abcde» es C8F0. El paquete del tema 42 con CRC-16/Modbus es A5 07 02 01 01 2E 09 7C 15 26 19, de 11 bytes, y al recalcular sobre lo que sigue al A5 el residuo es 0; la trama Modbus 01 03 00 00 00 0A da CDC5 (se envía C5 CD). Con dos bits invertidos en la misma columna (2E → 2F, 09 → 08), la suma sigue en 2D, mientras que el residuo del CRC-16 pasa a 113C, distinto de cero: detectado. Los mensajes 12 34 y 34 12 (mismos datos en otro orden) tienen la misma suma (BA las dos) y distinto CRC-8: F1 contra D3. El experimento con 20 000 pruebas de 8 bytes deja sin detectar: con 1 bit, nada en ningún método; con 2 bits, paridad 20 000, suma 1233, CRC-8 0 y CRC-16 0; con 3, paridad 0, suma 249, CRC 0 y 0; con 4, paridad 20 000, suma 277, CRC-8 179 y CRC-16 15; con 8, paridad 20 000, suma 82, CRC-8 154 y CRC-16 2.

Dos lecciones del modelo. Primero, un CRC completo son cinco parámetros, y con ellos las seis variantes del catálogo salen de la misma función: no hace falta una rutina por algoritmo, sino una rutina con parámetros y un vector de prueba para cada uno. Segundo, la paridad y la suma tienen patrones de falla muy marcados (paridad ciega a los pares, suma ciega a las compensaciones), mientras que los CRC fallan solo de a poco, con daños de muchos bits, y el CRC más largo falla menos. Ese perfil es lo que hace del CRC la herramienta de uso general.

11 · Exploración interactiva

Laboratorio: sumas, CRC, daños, fugas y tiempo medio

El laboratorio tiene cinco herramientas. La primera calcula la paridad y las sumas de un mensaje. La segunda calcula su CRC con seis algoritmos. La tercera inyecta un daño a mano y muestra qué métodos lo detectan. La cuarta simula miles de daños y cuenta los que se escapan. La quinta calcula el tiempo medio hasta un error no detectado según el tamaño de la verificación.

En la herramienta 1, el byte de paridad se calcula para cada byte, la suma es la de los temas 41 y 42, y Fletcher y la suma de Internet son las de los estándares. En la 2, los CRC se calculan con los cinco parámetros del catálogo, los reflejados se envían con el byte bajo primero y el «valor de prueba» es el CRC de «123456789». En la 3, un bit se escribe como byte.bit. En la 4, el mensaje de cada prueba se sortea y se invierten bits distintos en posiciones al azar. En la 5, la fracción 2⁻ⁿ es una cota para daños grandes, y la paridad se cuenta como 1/2.

Recorrido guiado

1. En la herramienta 1, con 2E 09 7C 15 y paridad par: bits 0, 0, 1, 1, XOR 0x4E, suma 0x38, Fletcher-16 0xE1C8 y suma de Internet 0x55E1; cambiando a paridad impar, los bits se invierten (1, 1, 0, 0). Con el texto «abcde» en hexadecimal (61 62 63 64 65), Fletcher da 0xC8F0. Probá con un mensaje de un byte y con 32.
2. En la herramienta 2, con el texto 123456789: CRC-16/Modbus 0x4B37, enviado como 37 4B, residuo 0x0000. Cambiando de algoritmo: 0xF4, 0xA1, 0x29B1 (transmitido 29 B1), 0x31C3 y 0xCBF43926 (transmitido 26 39 F4 CB, residuo 0x2144DF1C). Con formato hexadecimal y 01 03 00 00 00 0A: 0xCDC5, enviado C5 CD.
3. En la herramienta 3, con el mensaje 02 01 01 2E 09 7C 15 y los bits 3.0 4.0 (dos bits de la misma columna): la paridad, el XOR y la suma no detectan (en rojo), Fletcher, el CRC-8 y el CRC-16 sí: «3 de 6 métodos dejan pasar este daño». Con 3.0 (un bit): los seis detectan. Con 3.0 3.1 (dos bits de un byte): solo la paridad falla. Vaciando los bits y escribiendo en el intercambio 3 5: la paridad, el XOR y la suma no ven el cambio de orden; los demás sí.
4. En la herramienta 4, con 8 bytes, 2 bits, 20 000 pruebas y semilla 1: paridad 20 000 (100 %), suma 1233 (6,2 %), CRC-8 0 y CRC-16 0. Con 3 bits: paridad 0, suma 249 y CRC 0. Con 4: suma 277, CRC-8 179 (0,9 %) y CRC-16 15. Con 8: suma 82, CRC-8 154 y CRC-16 2, contra 78 y 0,3 teóricos de un daño totalmente al azar. Probá otras semillas.
5. En la herramienta 5, con 1e-5, 10 bytes, 9600 baudios y 8 bits: 345 tramas dañadas por hora, una de cada 256 se escapa, 1,35 por hora y un error cada 44,5 minutos (en rojo). Con 16 bits: 7,9 días (todavía en rojo: menos de un año). Con 32: 1419 años y «seguro». Con la paridad (1 bit): una de cada dos se escapa.

12 · Comprensión

Confusiones frecuentes

13 · Práctica guiada

Predecí antes de comprobar

1. Paridad

¿Cuál es el bit de paridad par y el de paridad impar de los bytes 0x7C, 0xB3 y 0x00?

2. Qué ve la paridad

Un byte con paridad par recibe daños de 1, 2 y 3 bits. ¿Cuáles detecta?

3. XOR y suma

Calculá el XOR y la suma de verificación (complemento a dos de la suma módulo 256) del mensaje 10 20 30.

4. Un punto ciego

Los mensajes 12 34 y 34 12 tienen la misma suma y el mismo XOR. ¿Y los CRC-8 y CRC-16/Modbus? ¿Qué enseña?

5. Un CRC a mano

Calculá el CRC de 3 bits del mensaje 1101 con el generador 1011. ¿Qué trama se transmite? Si el receptor recibe 1100001, ¿qué resto obtiene?

6. Qué se escapa

Un enlace recibe 1 000 000 de tramas dañadas con daños grandes al azar. ¿Cuántas acepta, en promedio, con un CRC-8, un CRC-16 y un CRC-32? ¿Cuánta memoria ocupa la tabla de cada uno?

7. Elegir el tamaño

Con 10⁻⁵ de tasa de error, tramas de 10 bytes a 9600 baudios (345 tramas dañadas por hora), ¿cada cuánto se acepta un daño con 8, 16 y 32 bits, en el peor caso? ¿Qué conviene para una orden a un actuador?

8. El orden del CRC

El CRC-16/Modbus del paquete A5 07 02 01 01 2E 09 7C 15 es 0x1926. ¿Cómo se transmite? ¿Qué pasa si se envía 19 26?

14 · Síntesis

Ideas para recordar

¿Listo para el siguiente tema?

Antes de avanzar, calculá a mano el CRC de 3 bits de 1011 con el generador 1011 o de un mensaje de cuatro bits cualquiera; explicá por qué una suma de un byte no detecta que dos bytes se intercambiaron pero un CRC sí; y decidí qué verificación usarías para una temperatura enviada por RS-485 cada segundo y cuál para una orden de apertura de una válvula, justificando con la fracción que se escapa. Si podés justificar las tres respuestas, entendés cómo se detectan los errores.

En el próximo tema, confirmaciones, reintentos y corrección, se estudia qué hacer después de detectar: el receptor avisa con un ACK o un NACK, el emisor espera con un tiempo de espera y reenvía, los números de secuencia distinguen lo repetido de lo nuevo, y un código de Hamming permite corregir un bit sin reenviar. Con la detección de este tema, completa un enlace confiable sobre un canal que no lo es.