Parità, codice di Hamming, distanza di Hamming, somme di controllo e CRC
Scrivi i bit di dati e vengono calcolati quelli di parità. Poi clicca su un bit qualsiasi della parola per invertirlo come se fosse un errore di trasmissione, e guarda cosa fa il ricevitore: la sindrome indica la posizione del bit errato. Prova con uno e con due errori, con e senza il bit di parità globale.
parità · dati · parità globale · bit cambiato.
Scrivi la trama in byte esadecimali (con o senza spazi) o come testo. La colonna «nella trama» dà i byte nell’ordine in cui vengono inviati.
Nessun canale è perfetto: una trama RS-485 che passa vicino a un inverter, un bit di memoria colpito da una particella o un graffio su un disco possono trasformare uno 0 in un 1. Per accorgersene, il trasmettitore aggiunge ai dati alcuni bit di ridondanza calcolati a partire da essi, e il ricevitore ripete il calcolo. Se non coincide, ci sono due strategie:
La distanza di Hamming tra due parole della stessa lunghezza è il numero di bit in cui differiscono: tra 1011101 e 1001001 è 2. La distanza minima \(d\) di un codice è la più piccola tra due parole valide qualsiasi, e stabilisce ciò che può fare:
| Codice | Distanza minima | Rileva | Corregge |
|---|---|---|---|
| Dati senza ridondanza | 1 | niente | niente |
| Bit di parità, 2 su 5 | 2 | 1 errore | niente |
| Hamming | 3 | 2 errori | 1 errore |
| Hamming con parità globale (SECDED) | 4 | 3 errori | 1 errore e ne rileva 2 |
| Ripetere ogni bit 3 volte | 3 | 2 errori | 1 errore (a maggioranza) |
L’idea è geometrica: se le parole valide distano almeno 3, una parola con un errore resta più vicina all’originale che a qualsiasi altra.
È il codice più semplice: si aggiunge un bit perché il numero totale di uno sia pari (parità pari) o dispari (parità dispari). Rileva qualsiasi numero dispari di errori, ma non due bit cambiati insieme. È la parità delle porte seriali (8E1 significa 8 bit di dati, parità pari e 1 bit di stop; Modbus RTU usa la parità pari per impostazione predefinita) e di alcune vecchie memorie. In un circuito si calcola con una catena di porte XOR.
Con la parità bidimensionale, i dati si dispongono in una tabella e si aggiunge la parità di ogni riga e di ogni colonna. Un errore cambia la parità di una riga e di una colonna, e il loro incrocio indica il bit da correggere.
Richard Hamming lo ideò nel 1950, stufo che i guasti delle macchine a relè gli rovinassero i calcoli del fine settimana. Le posizioni della parola si numerano da 1; quelle che sono potenze di 2 (1, 2, 4, 8…) contengono bit di parità e le altre i dati. Ogni bit di parità \(p_k\) copre le posizioni il cui numero in binario ha a 1 il bit di peso \(k\): \(p_1\) copre 1, 3, 5, 7…; \(p_2\) copre 2, 3, 6, 7…; \(p_4\) copre 4–7, 12–15… Con \(r\) bit di parità si proteggono \(m\) bit di dati se:
I dati vanno nelle posizioni 3, 5, 6 e 7. \(p_1 = d_1 \oplus d_2 \oplus d_4 = 1 \oplus 0 \oplus 1 = 0\), \(p_2 = d_1 \oplus d_3 \oplus d_4 = 1\) e \(p_4 = d_2 \oplus d_3 \oplus d_4 = 0\). La parola inviata è \(0110011\). Se arriva \(0110111\) (è sbagliata la posizione 5), il ricevitore ricalcola le tre parità su ciò che ha ricevuto: \(s_1 = 1\), \(s_2 = 0\), \(s_4 = 1\). La sindrome \(s_4 s_2 s_1 = 101_2 = 5\) è proprio la posizione dell’errore, e basta invertire quel bit.
| Codice | Bit di dati | Bit di parità | Rendimento |
|---|---|---|---|
| Hamming (7, 4) | 4 | 3 | 57 % |
| Hamming (15, 11) | 11 | 4 | 73 % |
| Hamming (31, 26) | 26 | 5 | 84 % |
| Hamming (63, 57) | 57 | 6 | 90 % |
| SECDED (72, 64), memoria ECC | 64 | 8 | 89 % |
Con due errori, l’Hamming semplice dà una sindrome diversa da zero e «corregge» un bit che era giusto, peggiorando la parola. Per evitarlo si aggiunge un bit di parità globale P su tutta la parola (single error correction, double error detection):
È lo schema della memoria ECC dei server e di molti microcontrollori per l’automotive e la sicurezza: 8 bit di controllo ogni 64 di dati.
Sono veloci e facili da programmare, ma rilevano molto peggio di un CRC della stessa dimensione.
Il CRC tratta il messaggio come un polinomio a coefficienti 0 e 1 (\(1011 = x^3 + x + 1\)) e lo divide per un polinomio generatore di grado \(r\). In questa aritmetica (modulo 2), sommare e sottrarre equivalgono all’OR esclusivo e non ci sono riporti. Il trasmettitore aggiunge \(r\) zeri al messaggio, divide e invia il resto al loro posto; il ricevitore divide l’intera trama e, se non ci sono errori, il resto è 0.
Si aggiungono 3 zeri e si divide sottraendo (XOR) il generatore sotto ogni 1 che resta a sinistra. Il resto è 100, quindi si invia 11010011101100100. È l’esempio caricato nel calcolatore qui sopra.
Con un buon polinomio di grado \(r\), il CRC rileva:
Oltre al polinomio, ogni CRC definisce il valore iniziale del registro, se i bit di ogni byte entrano riflessi (a partire dal meno significativo, come escono da una UART), se il risultato viene riflesso e con quale valore si fa l’OR esclusivo finale. Per questo CRC-16/MODBUS, CRC-16/ARC e CRC-16/CCITT danno risultati diversi con gli stessi dati. Per sapere quale usa un dispositivo si calcola quello della stringa di testo 123456789 e lo si confronta con il suo valore di controllo: 4B37 per Modbus, 29B1 per CCITT-FALSE, CBF43926 per CRC-32.
Vedi anche: convertitore binario ed esadecimale, codice 2 su 5 e simulatore di porte logiche (lo XOR).