Qual é a distância de Hamming e como faço para determinar isso para um esquema de CRC?

Question

Enquanto estudava para uma aula em redes de computadores, o professor falou sobre a distância de hamming entre duas palavras de código válidas em um código de amostra. Eu li sobre a distância de Hamming e faz sentido da perspectiva de dizer a distância da diferença entre 2 cordas. Por exemplo:

Code Word 1 = 10110 

O remetente envia o código da palavra 1 e há um erro introduzido e o receptor recebe 10100. Então você vê que o quarto bit foi corrompido. Isso resultaria na distância de Hamming de 1 porque:

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

O XOR das 2 cordas resulta em um 1, então a distância de hamming é 1. Eu entendo até esse ponto. Mas então o professor pergunta:

• Qual é a distância de hamming do protocolo padrão do CRC-16 de bits?
• Qual é a distância de hamming do protocolo padrão do CRC-32 BIT?

Estou um pouco confuso e queria saber se alguém poderia ajudar. Obrigado.

Answer 1

Você provavelmente já descobriu agora, mas o que ele pediu foi provavelmente o número mínimo de erros de bits que um código CRC não detectaria. A resposta depende da largura, do polinômio e do comprimento da mensagem. Por exemplo, o polinômio CRC-32 mais conhecido (0x1edc6f41) tem uma distância de hamming de 6 ou melhor para mensagens de até 5.275 bits (Castaglioni, Bräuer, Herrmann: otimização de códigos de redundância cíclica com 24 e 32 bits de paridade, IEEE. Transações sobre Comunicações, vol 41 n.

BTW, a palavra do código inclui a soma de verificação, então seu exemplo está incorreto.