Como você calcular o restante XOR usado na CRC?
-
19-08-2019 - |
Pergunta
Eu estou tentando lembrar como a matemática é trabalhada para calcular o restante de um algoritmo XOR em cheques de redundância cíclica para verificar os bits restante de uma mensagem de rede.
Eu não deveria ter lançado o livro de texto.
Isso é facilmente feito em código, mas como é que funcionou à mão?
Eu sei que é algo como um algoritmo de divisão padrão, mas não me lembro onde ir de lá para obter o restante.
___________
1010 | 101101000
Nota:. eu fiz google-lo, mas não foi capaz de encontrar um lugar onde eles mapearam os passos em descobrir o restante
Solução
É longa divisão por binário 11. Há um exemplo na Wikipedia .
Outras dicas
1010 | 101101000
1010
0001 this result is 1011 XOR 1010 = 0001
1010
1010
0000 thus no remainder.
Assim 101101000 é perfeito e não ocorreu nenhum erro na transmissão / recepção
Na minha experiência, é mais fácil de convertê-lo para um polinômio ao calcular à mão, especialmente quando há um monte de zeros.
1010 = 1*x^3 + 0*x^2 + 1*x^1 + 0*x^0 = x^3 + x = x3 + x
101101000 = x8 + x6 + x5 + x3
-------------------
x3 + x ) x8 + x6 + x5 + x3
Em seguida, você dividir o maior prazo do dividendo (x^8
) com o primeiro mandato no divisor (x^3
), resultando em x^5
. Você colocar esse número em cima e, em seguida, multiplicam com cada termo no divisor . Isso resulta o seguinte para a primeira iteração:
x5
-------------------
x3 + x ) x8 + x6 + x5 + x3
x8 + x6
Fazendo XOR para cada termo, em seguida, produz o novo dividendo: x5 + x3
:
x5
-------------------
x3 + x ) x8 + x6 + x5 + x3
x8 + x6
-------------------
x5 + x3
Siga o mesmo padrão até maior prazo do dividendo é menor, então maior prazo do divisor. Após o cálculo estiver concluído será parecido com isto:
x5 + x2
-------------------
x3 + x ) x8 + x6 + x5 + x3
x8 + x6
-------------------
x5 + x3
x5 + x3
-------------------
0
O lembrete neste caso é 0, o que indicaria que provavelmente nenhum erro ocorreu durante a transmissão.
Nota: Eu encurtado x^y
como xy
no exemplo acima para reduzir a desordem na resposta, uma vez que não suporta matemática equação formatação.
Nota 2:. Adicionando / subtraindo um múltiplo do divisor a partir do dividendo também dará o lembrete 0, já que (P(x) + a*C(x)) / C(x) = P(x)/C(x) + a*C(x)/C(x)
dá o mesmo lembrete de como P(x)/C(x)
desde o lembrete de a*C(x)/C(x)
é 0