Paridad, código Hamming, distancia de Hamming, sumas de comprobación y CRC
Escribe los bits de datos y se calculan los de paridad. Después pulsa cualquier bit de la palabra para cambiarlo como si fuera un error de transmisión, y verás qué hace el receptor: el síndrome indica la posición del bit erróneo. Prueba con uno y con dos errores, con y sin el bit de paridad global.
paridad · datos · paridad global · bit cambiado.
Escribe la trama en bytes hexadecimales (con o sin espacios) o como texto. La columna «en la trama» da los bytes en el orden en que se envían.
Ningún canal es perfecto: una trama RS-485 que pasa junto a un variador, un bit de memoria alcanzado por una partícula o un rayado en un disco pueden cambiar un 0 por un 1. Para darse cuenta, el emisor añade a los datos unos bits de redundancia calculados a partir de ellos, y el receptor repite el cálculo. Si no coincide, hay dos estrategias:
La distancia de Hamming entre dos palabras del mismo tamaño es el número de bits en que se diferencian: entre 1011101 y 1001001 hay 2. La distancia mínima \(d\) de un código es la menor entre dos palabras válidas cualesquiera, y fija lo que puede hacer:
| Código | Distancia mínima | Detecta | Corrige |
|---|---|---|---|
| Datos sin redundancia | 1 | nada | nada |
| Bit de paridad, 2 entre 5 | 2 | 1 error | nada |
| Hamming | 3 | 2 errores | 1 error |
| Hamming con paridad global (SECDED) | 4 | 3 errores | 1 error y detecta 2 |
| Repetir cada bit 3 veces | 3 | 2 errores | 1 error (por mayoría) |
La idea es geométrica: si las palabras válidas están al menos a distancia 3, una palabra con un error sigue estando más cerca de la original que de cualquier otra.
Es el código más sencillo: se añade un bit para que el número total de unos sea par (paridad par) o impar (paridad impar). Detecta cualquier número impar de errores, pero no dos bits cambiados a la vez. Es la paridad de los puertos serie (8E1 es 8 bits de datos, paridad par y 1 bit de parada; Modbus RTU usa paridad par por defecto) y de algunas memorias antiguas. En un circuito se calcula con una cadena de puertas XOR.
Con la paridad bidimensional, los datos se colocan en una tabla y se añade la paridad de cada fila y de cada columna. Un error cambia la paridad de una fila y de una columna, y su cruce indica el bit que hay que corregir.
Richard Hamming lo ideó en 1950, harto de que los fallos de las máquinas de relés le arruinasen los cálculos del fin de semana. Las posiciones de la palabra se numeran desde 1; las que son potencia de 2 (1, 2, 4, 8…) llevan bits de paridad y el resto, los datos. Cada bit de paridad \(p_k\) cubre las posiciones cuyo número en binario tiene a 1 el bit de peso \(k\): \(p_1\) cubre 1, 3, 5, 7…; \(p_2\) cubre 2, 3, 6, 7…; \(p_4\) cubre 4–7, 12–15… Con \(r\) bits de paridad se protegen \(m\) bits de datos si:
Los datos van en las posiciones 3, 5, 6 y 7. \(p_1 = d_1 \oplus d_2 \oplus d_4 = 1 \oplus 0 \oplus 1 = 0\), \(p_2 = d_1 \oplus d_3 \oplus d_4 = 1\) y \(p_4 = d_2 \oplus d_3 \oplus d_4 = 0\). La palabra enviada es \(0110011\). Si llega \(0110111\) (falla la posición 5), el receptor recalcula las tres paridades sobre lo recibido: \(s_1 = 1\), \(s_2 = 0\), \(s_4 = 1\). El síndrome \(s_4 s_2 s_1 = 101_2 = 5\) es justo la posición del error, y basta con invertir ese bit.
| Código | Bits de datos | Bits de paridad | Rendimiento |
|---|---|---|---|
| Hamming (7, 4) | 4 | 3 | 57 % |
| Hamming (15, 11) | 11 | 4 | 73 % |
| Hamming (31, 26) | 26 | 5 | 84 % |
| Hamming (63, 57) | 57 | 6 | 90 % |
| SECDED (72, 64), memoria ECC | 64 | 8 | 89 % |
Con dos errores, el Hamming simple da un síndrome distinto de cero y «corrige» un bit que estaba bien, empeorando la palabra. Para evitarlo se añade un bit de paridad global P sobre toda la palabra (single error correction, double error detection):
Es el esquema de la memoria ECC de los servidores y de muchos microcontroladores para automoción y seguridad: 8 bits de control por cada 64 de datos.
Son rápidas y fáciles de programar, pero detectan bastante peor que un CRC del mismo tamaño.
El CRC trata el mensaje como un polinomio con coeficientes 0 y 1 (\(1011 = x^3 + x + 1\)) y lo divide entre un polinomio generador de grado \(r\). En esta aritmética (módulo 2) sumar y restar son lo mismo que la O exclusiva y no hay acarreos. El emisor añade \(r\) ceros al mensaje, divide y envía el resto en su lugar; el receptor divide la trama entera y, si no hay errores, el resto es 0.
Se añaden 3 ceros y se divide restando (XOR) el generador bajo cada 1 que queda a la izquierda. El resto es 100, así que se envía 11010011101100100. Es el ejemplo que viene cargado en la calculadora de arriba.
Con un buen polinomio de grado \(r\), el CRC detecta:
Además del polinomio, cada CRC define el valor inicial del registro, si los bits de cada byte entran reflejados (empezando por el de menos peso, como salen por una UART), si el resultado se refleja y con qué valor se hace la O exclusiva final. Por eso CRC-16/MODBUS, CRC-16/ARC y CRC-16/CCITT dan resultados distintos con los mismos datos. Para saber cuál usa un equipo se calcula el de la cadena de texto 123456789 y se compara con su valor de comprobación: 4B37 para Modbus, 29B1 para CCITT-FALSE, CBF43926 para CRC-32.
Relacionado: conversor binario y hexadecimal, código 2 entre 5 y simulador de puertas lógicas (la XOR).