Suma de verificación

El algoritmo de suma de verificación más simple es la llamada verificación de paridad longitudinal , que divide los datos en "palabras" con un número fijo n de bits y luego calcula la operación OR exclusiva (XOR) bit a bit de todas esas palabras. El resultado se agrega al mensaje como una palabra adicional. En términos más sencillos, para n = 1, esto significa agregar un bit al final de los bits de datos para garantizar que haya un número par de '1'. Para verificar la integridad de un mensaje, el receptor calcula la operación OR exclusiva bit a bit de todas sus palabras, incluida la suma de verificación; si el resultado no es una palabra compuesta por n ceros, el receptor sabe que se produjo un error de transmisión. ^{[ 3 ]}

Con esta suma de verificación, cualquier error de transmisión que altere un solo bit del mensaje, o un número impar de bits, se detectará como una suma de verificación incorrecta. Sin embargo, un error que afecte a dos bits no se detectará si estos se encuentran en la misma posición en dos palabras distintas. Tampoco se detectará el intercambio de dos o más palabras. Si los bits afectados se eligen de forma independiente y aleatoria, la probabilidad de que un error de dos bits no se detecte es 1/ n .

Una variante del algoritmo anterior consiste en sumar todas las "palabras" como números binarios sin signo, descartando los bits de desbordamiento, y añadir el complemento a dos del total como suma de verificación. Para validar un mensaje, el receptor suma todas las palabras de la misma manera, incluyendo la suma de verificación; si el resultado no es una palabra llena de ceros, debe haber ocurrido un error. Esta variante también detecta cualquier error de un solo bit, pero en SAE J1708 se utiliza la suma modular pro . ^{[ 4 ]}

Las sumas de verificación simples descritas anteriormente no detectan algunos errores comunes que afectan a muchos bits a la vez, como cambiar el orden de las palabras de datos o insertar o eliminar palabras con todos los bits a cero. Los algoritmos de suma de verificación más utilizados en la práctica, como la suma de verificación de Fletcher , Adler-32 y las comprobaciones de redundancia cíclica (CRC), solucionan estas deficiencias al considerar no solo el valor de cada palabra, sino también su posición en la secuencia. Esta característica generalmente aumenta el costo de calcular la suma de verificación.

La idea de la suma de verificación difusa se desarrolló para la detección de correo no deseado mediante la creación de bases de datos cooperativas de múltiples proveedores de servicios de Internet (ISP) con correos electrónicos sospechosos de ser spam. El contenido de dicho spam a menudo puede variar en sus detalles, lo que haría que la suma de verificación normal sea ineficaz. Por el contrario, una "suma de verificación difusa" reduce el texto del cuerpo a su mínimo característico y luego genera una suma de verificación de la manera habitual. Esto aumenta considerablemente las posibilidades de que correos electrónicos de spam ligeramente diferentes produzcan la misma suma de verificación. El software de detección de spam de los ISP, como SpamAssassin , de los ISP cooperativos, envía las sumas de verificación de todos los correos electrónicos al servicio centralizado como DCC . Si el recuento de una suma de verificación difusa enviada supera un cierto umbral, la base de datos indica que probablemente se trata de spam. Los usuarios del servicio ISP generan de manera similar una suma de verificación difusa para cada uno de sus correos electrónicos y solicitan al servicio una probabilidad de spam. ^{[ 5 ]}

Un mensaje de m bits puede considerarse como un vértice del hipercubo m -dimensional . El efecto de un algoritmo de suma de verificación que produce una suma de verificación de n bits es asignar cada mensaje de m bits a un vértice de un hipercubo mayor, de dimensión m + n . Los 2 ^{m + n} vértices de este hipercubo representan todos los mensajes recibidos posibles. Los mensajes recibidos válidos (aquellos que tienen la suma de verificación correcta) comprenden un conjunto más pequeño, con solo 2 ^m vértices.

Un error de transmisión de un solo bit corresponde a un desplazamiento desde una esquina válida (el mensaje y la suma de verificación correctos) a una de las m esquinas adyacentes. Un error que afecta a k bits mueve el mensaje a una esquina que se encuentra a k pasos de su esquina correcta. El objetivo de un buen algoritmo de suma de verificación es dispersar las esquinas válidas lo máximo posible, para aumentar la probabilidad de que los errores de transmisión "típicos" terminen en una esquina inválida.