Come viene scelto il polinomio generatore G(x)?
Nel simulatore puoi scrivere qualsiasi generatore binario valido per fare esercizio. Nelle reti reali, però, G(x) non viene scelto dallo studente, dal programmatore o dalla scheda di rete: è fissato da uno standard tecnico.
- Il primo bit deve essere
1, perché indica il termine di grado massimo. - Il grado di
G(x)determina il numero di bit del CRC: grado 3 → CRC di 3 bit; grado 32 → CRC di 32 bit. - Un buon generatore è progettato per rilevare molti tipi di errore: errori su un singolo bit, su due bit, errori con numero dispari di bit alterati e raffiche di errore.
- Per questo Ethernet usa un polinomio standard CRC-32, molto più robusto dei piccoli generatori didattici.
G(x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1
Bit del generatore usati dal simulatore:
100000100110000010001110110110111Nota didattica: il simulatore mostra la divisione modulo 2 nella forma scolastica. Le implementazioni reali possono usare registri a scorrimento, bit riflessi, valore iniziale e XOR finale. Il principio rimane: il FCS contiene un CRC di 32 bit.
Matematica dell’algoritmo CRC
Il CRC interpreta le sequenze binarie come polinomi con coefficienti 0 e 1. Tutte le somme avvengono in modulo 2: in pratica, si usa lo XOR.
1. Oggetti matematici
| Simbolo | Significato |
|---|---|
M(x) | Polinomio del messaggio originale. |
G(x) | Polinomio generatore, noto sia al trasmettitore sia al ricevitore. |
n | Grado di G(x). È anche il numero di bit del CRC. |
M'(x)=M(x)·xⁿ | Messaggio con n zeri aggiunti in coda, usato solo per il calcolo. |
CRC(x) | Resto della divisione modulo 2 di M'(x) per G(x). |
T(x) | Frame finale trasmesso. |
2. Formula del CRC
CRC(x) = [M(x) · xⁿ] mod G(x)
Il CRC è quindi il resto della divisione binaria modulo 2.
3. Formula del frame trasmesso
T(x) = M(x) · xⁿ ⊕ CRC(x)
Il simbolo ⊕ indica XOR. Operativamente il risultato appare come M seguito dal CRC, perché gli zeri finali di M(x)·xⁿ vengono sostituiti dal resto.
4. Controllo in ricezione
T(x) mod G(x) = 0
Se il resto è tutto zero, il frame viene accettato. Se il resto è diverso da zero, il frame viene scartato.
5. Vincolo didattico adottato nel simulatore
Il simulatore accetta qualsiasi messaggio binario valido. Quando grado M(x) < grado G(x) oppure M è tutto zero, il calcolo procede comunque ma viene mostrato un avviso didattico: questi casi sono matematicamente legittimi ma spesso risultano meno istruttivi in un esercizio introduttivo.
6. Collisione CRC
È possibile, anche se raro, che un frame alterato produca comunque resto zero. In quel caso si parla di errore non rilevato o collisione CRC. Con un CRC-32 reale, per errori casuali, l’ordine di grandezza della probabilità è circa 1 su 2³².
I seguenti casi di test sono stati verificati indipendentemente e devono produrre i risultati indicati. Servono come prova di correttezza dell'algoritmo per chiunque voglia replicare o validare il simulatore. Puoi caricarli rapidamente cliccando "Carica".
| Messaggio M | Generatore G | CRC atteso | Frame trasmesso | Fonte | |
|---|---|---|---|---|---|
1101 |
1011 |
001 |
1101001 |
Lezione standard (CRC-3 didattico) | |
1010 |
1101 |
001 |
1010001 |
Esercizio guidato (CRC-3 didattico) | |
11010011101100 |
1011 |
100 |
11010011101100100 |
Wikipedia — Cyclic redundancy check | |
10110010 |
100000111 |
00010111 |
1011001000010111 |
CRC-8 ATM (1 byte) | |
1111111111111111 |
10011 |
0011 |
11111111111111110011 |
CRC-4 ITU su pattern di soli "1" |
100000100110000010001110110110111 (33 bit),
corrispondente a x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1.
Verificato bit per bit contro lo standard IEEE 802.3.