Calculadora de divisão longa CRC / XOR / módulo 2

CRC / XOR calculator: enter message bits and generator poly for modulo-2 division.

Output: CRC remainder after XOR long division.

A Calculadora de Divisão Longa CRC / XOR / Módulo 2 executa divisão binária sem carries nem empréstimos, usando XOR bit a bit a cada passo. Esta é a aritmética por trás das verificações de redundância cíclica (CRC): a mensagem recebe bits zero anexados e é dividida por um polinômio gerador, e o resto vira o checksum CRC. Como em módulo 2 adição e subtração são ambas XOR, cada passo é uma comparação simples de bits. Digite uma palavra de dados e um gerador (divisor) para ver cada alinhamento, cada XOR e o resto final usado como CRC.

Como usar a Calculadora CRC / XOR / Módulo 2

Para calcular um CRC por divisão módulo 2, siga estes 4 passos:

Digite a mensagem binária (bits de dados) no primeiro campo.
Digite o polinômio gerador como bits binários no segundo campo.
A calculadora anexa (n − 1) bits zero, onde n é o comprimento do gerador.
Clique em Calcular para fazer XOR na mensagem e leia o resto como CRC.

O quociente costuma ser descartado no trabalho com CRC — o resto é o checksum que se anexa à mensagem antes da transmissão.

CRC e aritmética módulo 2

Uma verificação de redundância cíclica detecta erros de transmissão tratando uma mensagem como um grande polinômio binário e dividindo-o por um polinômio gerador acordado. A divisão é feita em aritmética módulo 2 (GF(2)), onde adição e subtração são idênticas e iguais a XOR — não há carries nem empréstimos. O resto dessa divisão é o CRC. Quando o receptor divide mensagem mais CRC pelo mesmo gerador, um resto 0 significa nenhum erro detectado. Esta calculadora reproduz exatamente esse processo bit a bit.

A divisão reparte um total em grupos iguais. A divisão longa faz isso dígito por dígito.

Divisor (32) — o número pelo qual você divide. Coloque-o à esquerda da chave.

Como funciona a divisão CRC módulo 2

A calculadora calcula o CRC por meio de cinco ações internas:

Anexa (n − 1) bits zero à mensagem, onde n é o número de bits do gerador.
Alinha o gerador sob o bit 1 mais à esquerda do resto atual.
Faz XOR do gerador nesses bits (subtração módulo 2 sem empréstimo).
Desloca para o próximo bit 1 e repete o alinhamento XOR.
Para quando os bits restantes são menos que o gerador; esses bits são o CRC.

Cada bit do quociente é 1 onde o gerador é XORado e 0 no resto, mas para CRC só importa o resto final.

Anexa (n − 1) bits zero à mensagem, onde n é o número de bits do gerador.

Fórmula para divisão CRC

A Calculadora CRC / XOR / Módulo 2 calcula CRC = (M(x) · xⁿ⁻¹) mod G(x) em GF(2), onde M(x) é a mensagem, G(x) é o gerador de n bits e todas as adições são XOR. O frame transmitido é M(x)·xⁿ⁻¹ + CRC, que G(x) divide exatamente. No receptor, um resto zero confirma a integridade.

Dividendo

Divisor

Quociente

Resto

110100111 = 1011 × 108902 + 189 → A identidade é válida

Problemas de exemplo CRC / XOR

Estes exemplos mostram divisão módulo 2 com XOR a cada passo.

Exemplo 1 — Mensagem 1101, gerador 101

Comprimento do gerador 3, então anexe 2 zeros: 1101 vira 110100.
XOR 101 nos bits iniciais repetidamente: 110100 → 011100 → 001000 → 000010.
Os últimos 2 bits, 10, são o resto CRC.

Exemplo 2 — Por que a subtração é XOR

Em módulo 2, 1 + 1 = 0 e 1 − 1 = 0, então somar e subtrair são a mesma operação.
Essa operação é exatamente XOR bit a bit, sem carry nem empréstimo.
Então cada passo de divisão é um XOR do gerador nos bits atuais.

Exemplo 3 — Conferência no receptor

Anexe o CRC à mensagem e divida pelo mesmo gerador.
Faça XOR exatamente como antes.
Um resto 0 significa nenhum erro detectado.

Comprimento do gerador 3, então anexe 2 zeros: 1101 vira 110100.
XOR 101 nos bits iniciais repetidamente: 110100 → 011100 → 001000 → 000010.
Os últimos 2 bits, 10, são o resto CRC.

Problemas CRC resolvidos

Como você calcula o CRC de 10110 com gerador 1011?

Anexe 3 zeros (comprimento do gerador 4) para obter 10110000, depois faça XOR para baixo. Alinhe 1011 sob cada 1 inicial e faça XOR: 10110000 → 00100000 → após XORs sucessivos os últimos 3 bits formam o resto CRC. O resto é então anexado a 10110 para que o frame completo seja divisível por 1011 sem resto.

1101001111011

Por que um resto zero significa que os dados estão intactos?

O remetente escolheu o CRC para que o frame transmitido seja múltiplo exato do gerador. Qualquer múltiplo de G(x) dividido por G(x) deixa resto 0. Se bits mudarem em trânsito, o frame geralmente deixa de ser múltiplo, então a divisão do receptor deixa um resto não zero, sinalizando erro.

1010111

Erros comuns CRC / módulo 2

A divisão CRC módulo 2 produz 5 erros frequentes:

Usar subtração binária comum com empréstimos em vez de XOR.
Anexar o número errado de bits zero (deve ser comprimento do gerador menos um).
Alinhar o gerador sob um bit 0 em vez do 1 inicial.
Tratar carries como se existissem em aritmética GF(2).
Informar o quociente como CRC em vez do resto.

A Calculadora CRC / XOR / Módulo 2 faz XOR a cada passo, anexa os zeros corretos e retorna o resto como checksum.

Usar subtração binária comum com empréstimos em vez de XOR.

Anexar o número errado de bits zero (deve ser comprimento do gerador menos um).

Alinhar o gerador sob um bit 0 em vez do 1 inicial.

Tratar carries como se existissem em aritmética GF(2).

Informar o quociente como CRC em vez do resto.

Perguntas frequentes

O que é divisão módulo 2?

É divisão binária em GF(2), onde adição e subtração são ambas XOR e não há carries nem empréstimos. Cada passo faz XOR do gerador nos bits atuais onde o bit inicial é 1.

Como se calcula um CRC?

Anexe (comprimento do gerador − 1) bits zero à mensagem, depois divida pelo gerador usando divisão longa módulo 2 (XOR). O resto é o checksum CRC.

Por que se usa XOR em vez da subtração normal?

Em aritmética módulo 2, 1 + 1 = 0 sem carry, então adição e subtração são idênticas e iguais a XOR. Isso torna cada passo de divisão um único XOR bit a bit.

Quantos bits zero anexo à mensagem?

Anexe um a menos que o número de bits do gerador. Um gerador de 4 bits significa 3 zeros anexados, reservando espaço para o resto CRC.

Como o receptor confere o CRC?

O receptor divide mensagem mais CRC pelo mesmo gerador usando divisão módulo 2. Um resto 0 significa nenhum erro detectado; um resto não zero sinaliza corrupção.

O quociente importa no CRC?

Não. Para CRC só o resto é usado como checksum. O quociente normalmente é descartado.

O que é o polinômio gerador?

É o divisor binário acordado, escrito como polinômio como x³ + x + 1 (1011). Remetente e receptor devem usar o mesmo gerador para a verificação funcionar.

A identidade CRC

A Calculadora CRC / XOR / Módulo 2 usa CRC = (M(x)·xⁿ⁻¹) mod G(x) em GF(2), então o frame transmitido M(x)·xⁿ⁻¹ + CRC é exatamente divisível por G(x). Como um múltiplo do gerador deixa resto 0, a divisão módulo 2 do receptor retorna 0 quando os dados estão intactos.