¿Cuál es la distancia de Hamming y cómo la determino para un esquema de CRC?

Question

Mientras estudiaba para una clase en redes de computadoras, el profesor habló sobre la distancia de Hamming entre 2 palabras de código válidas en un código de muestra. He leído sobre la distancia de Hamming, y tiene sentido desde la perspectiva de diferenciar la distancia entre 2 cuerdas. Por ejemplo:

Code Word 1 = 10110 

El remitente envía palabra de código 1, y hay un error introducido, y el receptor recibe 10100. Así que ya ves que el cuarto bit se corrompió. Esto daría lugar a la distancia de Hamming de un 1 porque:

Valid Code Word: 10110 
Error Code Word: 10100 
       ----- 
XOR    00010 

El XOR de las cadenas de resultados 2 en un 1, por lo que la distancia de Hamming es 1. Tengo entendido que hasta ese momento. Pero entonces el prof pregunta:

• ¿Cuál es la distancia de martillado del protocolo de bit CRC-16 estándar?
• ¿Cuál es la distancia de corte del protocolo de bit CRC-32 estándar?

Estoy un poco confundido, y me preguntaba si alguien podría ayudar. Gracias.

Answer 1

Probablemente ya se haya dado cuenta, pero lo que ha pedido es probablemente la cantidad mínima de errores de bit que un código CRC no detectaría. La respuesta depende del ancho, el polinomio y la longitud del mensaje. Por ejemplo, el polinomio CRC-32 mejor conocido (0x1EDC6F41) tiene una distancia de Hamming de 6 o superior para mensajes de hasta 5.275 bits (Castaglioni, Bräuer, Herrmann: Optimización de códigos de comprobación de redundancia cíclica con 24 y 32 bits de paridad, IEEE Transactions on Communications, vol 41 no 6, junio de 1993), lo que significa que garantiza la detección de hasta 5 bits invertidos en un solo mensaje de 5.275 bits o menos.

Por cierto, la palabra de código incluye la suma de comprobación, por lo que su ejemplo es incorrecto.