Como você calcular o restante XOR usado na CRC?

Question

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

Answer 1

É longa divisão por binário 11. Há um exemplo na Wikipedia .

Answer 2

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

Answer 3

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