¿Cuál es la distancia de Hamming, y cómo se determinan por un esquema CRC?

Question

Si bien el estudio de una clase en redes de computadoras, el prof habló sobre la distancia de Hamming entre 2 palabras de código válidas en un código de ejemplo. He leído acerca de la distancia Hamming, y tiene sentido desde la perspectiva de contar la distancia diferencia entre 2 cadenas. 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í se ve que el cuarto bit se corrompió. Esto resultaría en la distancia una de Hamming de 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 Hamming del protocolo de bits estándar CRC-16?
• ¿Cuál es la distancia de Hamming del protocolo de bits estándar CRC-32?

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

Answer 1

Es probable que lo descubrió por ahora, pero lo que él pidió fue muy probablemente el mínimo número de errores de bit que un código CRC no detectaría. La respuesta depende de la anchura, el polinomio y la longitud del mensaje. Por ejemplo, el más conocido CRC-32 polinomio (0x1EDC6F41) tiene una distancia de Hamming de 6 o mejor para los mensajes de hasta 5.275 bits (Castaglioni, Bräuer, Herrmann: Optimización de redundancia cíclica-Check Codes con 24 y 32 bits de paridad, IEEE Transacciones sobre Comunicaciones, vol 41 no 6, junio de 1993) lo que significa que se garantiza para detectar hasta 5 bits volteadas en un único mensaje de 5.275 bits o menos.

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