Calcolatrice di divisione in colonna CRC / XOR / modulo 2

Come usare la Calcolatrice CRC / XOR / modulo 2

Per calcolare un CRC con divisione modulo 2, segui questi 4 passaggi:

• Inserisci il messaggio binario (bit dati) nel primo campo.
• Inserisci il polinomio generatore come bit binari nel secondo campo.
• La calcolatrice aggiunge (n − 1) bit zero, dove n è la lunghezza del generatore.
• Clicca su Calcola per eseguire XOR sul messaggio e leggi il resto come CRC.

Il quoziente di solito viene scartato nel lavoro CRC — il resto è il checksum che si aggiunge al messaggio prima della trasmissione.

CRC e aritmetica modulo 2

Un controllo di ridondanza ciclica rileva errori di trasmissione trattando un messaggio come un grande polinomio binario e dividendolo per un polinomio generatore concordato. La divisione avviene in aritmetica modulo 2 (GF(2)), dove addizione e sottrazione sono identiche e uguali a XOR — non ci sono riporti né prestiti. Il resto di questa divisione è il CRC. Quando il ricevente divide messaggio più CRC per lo stesso generatore, un resto 0 significa nessun errore rilevato. Questa calcolatrice riproduce esattamente quel processo bit a bit.

Come funziona la divisione CRC modulo 2

La calcolatrice calcola il CRC attraverso cinque azioni interne:

• Aggiunge (n − 1) bit zero al messaggio, dove n è il numero di bit del generatore.
• Allinea il generatore sotto il bit 1 più a sinistra del resto corrente.
• Esegue XOR del generatore su quei bit (sottrazione modulo 2 senza prestito).
• Sposta al bit 1 successivo e ripete l'allineamento XOR.
• Si ferma quando i bit rimanenti sono meno del generatore; quei bit sono il CRC.

Ogni bit del quoziente è 1 dove il generatore viene XORato e 0 altrove, ma per il CRC conta solo il resto finale.

Formula per la divisione CRC

La Calcolatrice CRC / XOR / modulo 2 calcola CRC = (M(x) · xⁿ⁻¹) mod G(x) in GF(2), dove M(x) è il messaggio, G(x) è il generatore di n bit e tutte le addizioni sono XOR. Il frame trasmesso è M(x)·xⁿ⁻¹ + CRC, che G(x) divide esattamente. Lato ricevente, un resto zero conferma l'integrità.

Problemi di esempio CRC / XOR

Questi esempi mostrano divisione modulo 2 con XOR a ogni passaggio.

Esempio 1 — Messaggio 1101, generatore 101

1. Lunghezza generatore 3, quindi aggiungi 2 zeri: 1101 diventa 110100.
2. XOR 101 sui bit iniziali ripetutamente: 110100 → 011100 → 001000 → 000010.
3. Gli ultimi 2 bit, 10, sono il resto CRC.

Esempio 2 — Perché la sottrazione è XOR

1. In modulo 2, 1 + 1 = 0 e 1 − 1 = 0, quindi addizione e sottrazione sono la stessa operazione.
2. Quell'operazione è esattamente XOR bit a bit, senza riporto né prestito.
3. Quindi ogni passaggio di divisione è un XOR del generatore sui bit correnti.

Esempio 3 — Controllo lato ricevente

1. Aggiungi il CRC al messaggio e dividi per lo stesso generatore.
2. Esegui XOR esattamente come prima.
3. Un resto 0 significa nessun errore rilevato.

Lunghezza generatore 3, quindi aggiungi 2 zeri: 1101 diventa 110100.
XOR 101 sui bit iniziali ripetutamente: 110100 → 011100 → 001000 → 000010.
Gli ultimi 2 bit, 10, sono il resto CRC.

In modulo 2, 1 + 1 = 0 e 1 − 1 = 0, quindi addizione e sottrazione sono la stessa operazione.
Quell'operazione è esattamente XOR bit a bit, senza riporto né prestito.
Quindi ogni passaggio di divisione è un XOR del generatore sui bit correnti.

Aggiungi il CRC al messaggio e dividi per lo stesso generatore.
Esegui XOR esattamente come prima.
Un resto 0 significa nessun errore rilevato.

Problemi CRC svolti

Come calcoli il CRC di 10110 con generatore 1011?

Aggiungi 3 zeri (lunghezza generatore 4) per ottenere 10110000, poi esegui XOR verso il basso. Allinea 1011 sotto ogni 1 iniziale e fai XOR: 10110000 → 00100000 → dopo XOR successivi gli ultimi 3 bit formano il resto CRC. Il resto viene poi aggiunto a 10110 così l'intero frame è divisibile per 1011 senza resto.

Perché un resto zero significa che i dati sono intatti?

Il mittente ha scelto il CRC così il frame trasmesso è un multiplo esatto del generatore. Ogni multiplo di G(x) diviso per G(x) lascia resto 0. Se i bit cambiano in transito, il frame di solito non è più un multiplo, quindi la divisione del ricevente lascia un resto non zero, segnalando un errore.

Errori comuni CRC / modulo 2

La divisione CRC modulo 2 produce 5 errori frequenti:

• Usare sottrazione binaria ordinaria con prestiti invece di XOR.
• Aggiungere il numero sbagliato di bit zero (deve essere lunghezza generatore meno uno).
• Allineare il generatore sotto un bit 0 invece del 1 iniziale.
• Trattare i riporti come se esistessero in aritmetica GF(2).
• Riportare il quoziente come CRC invece del resto.

La Calcolatrice CRC / XOR / modulo 2 esegue XOR a ogni passaggio, aggiunge gli zeri corretti e restituisce il resto come checksum.

Domande frequenti