checksum - suma - metodos para la deteccion y correccion de errores pdf
¿Cómo es útil una suma de comprobación de complemento 1s para la detección de errores? (5)
Se puede generar una suma de comprobación simplemente agregando bits. ¿Cómo es útil el paso adicional de tomar el complemento 1s?
Entiendo la teoría. Sé cómo calcular el complemento de 1s y sé cómo agregar los complementos hace que el resultado sea todo 1s.
Me gustaría ver un ejemplo simple de cómo se detecta un error.
Al "agregar bits" supongo que te refieres a calcular los bits de paridad. Según esta entrada de Wikipedia sobre sumas de comprobación , para una suma de comprobación de paridad "la probabilidad de que un error de dos bits no se detecte es de 1 / n", mientras que con una suma modular (como 1s complemento) "la probabilidad de que se produzca un error de dos bits no detectado es un poco menos de 1 / n ".
Esta columna "Preguntar al Dr. Matemáticas" explica cómo calcular el complemento 1s (más comúnmente para TCP / IP).
Creo que el ejemplo que estás buscando se puede encontrar here .
La razón por la que hacemos el complemento de 1 es que cuando el complemento de 1 se agrega a la suma de todos los valores y el resultado se recorta a la longitud de bits de la máquina (16 bits en el ejemplo anterior), es todo de 1. Las CPU tienen una función para tomar el complemento de números de 1, y tomar el complemento de 1 de all-1 es all-0.
La razón: las CPU odian trabajar con bits, excepto en trozos de los que normalmente utilizan. Por lo tanto, agregar dos números de 64 bits puede tomar 1 ciclo, pero la verificación individual de todos los bits de ese número llevará muchos más (en un ciclo ingenuo, tal vez tan alto como 8x64 ciclos). Las CPU también tienen la capacidad de tomar de forma trivial los complementos de 1, y detectar que el resultado del último cálculo fue cero sin inspeccionar los bits individuales y la rama en función de eso. Básicamente, es una optimización que nos permite verificar sumas de comprobación muy rápido. Como la mayoría de los paquetes están bien, esto nos permite verificar la suma de comprobación sobre la marcha y llevar los datos al destino mucho más rápido.
Ejemplo, tiene tres palabras en el paquete UDP que necesita enviar.
0110011001100000
0101010101010101
1000111100001100
UDP en el lado del remitente realiza el complemento 1s de la suma de todas las palabras de 16 bits. La suma de las dos primeras palabras de 16 bits es
0110011001100000
+
0101010101010101
--> 1011101110110101
Al agregar la tercera palabra a la suma anterior, tenga en cuenta que esta última adición tuvo un desbordamiento, que se envolvió alrededor
--> 0100101011000010
El complemento a 1s se obtiene al convertir todos los 0s a 1s y al convertir todos los 1s a 0s.
Así, el complemento 1s de la suma 0100101011000010 es 1011010100111101 , que se convierte en la suma de comprobación. En el receptor, se agregan las cuatro palabras de 16 bits, incluida la suma de comprobación. Si no se introducen errores en el paquete, entonces claramente la suma en el receptor será 1111111111111111 . Si uno de los bits es un 0, entonces sabemos que se han introducido errores en el paquete.
El complemento (inversión de bit) de una suma de comprobación es útil en al menos dos formas.
- Simplifica el proceso de verificación de la suma de comprobación.
Si, por ejemplo, hay una suma de control final 56, el complemento será 199. Súmalos y el resultado es 255. El razonamiento: complementando la suma de control final, el resultado final siempre será 255 cuando se incluya el dígito de suma de comprobación en la suma calculo Realizar el complemento por segunda vez con 255 producirá 0, lo que para las CPU en ese momento era una forma más eficiente de confirmar que la suma de comprobación es válida sin tener que comparar dos números.
- Permite detectar un error indetectable.
Calcular un mensaje de n ceros produce una suma de comprobación de cero. Esto significa que un mensaje legítimo que consta de ceros es indistinguible de una situación de pérdida o borrado de memoria que debe detectarse como un error. Al complementar la suma de comprobación final de 0 en este caso, el resultado es 255 en su lugar, lo que evita que el resultado de cero siga siendo válido.
La suma de comprobación es muy importante para la creación de redes, como se mencionó partickmdnet. Básicamente, para cada datagrama transmitido en el protocolo IP, hay una suma de comprobación que se calculó antes de tiempo y se transmitió. Si incluso un bit está dañado y se envía incorrectamente en la parte de datos del datagrama, entonces la suma de comprobación calculada en el enrutador receptor será diferente de la que se proporciona con el datagrama. Esto le indica al enrutador que el datagrama está dañado (ya sea los datos o la parte de la suma de comprobación) y el enrutador descartará el datagrama.