IT

Codici di rilevazione e correzione degli errori

Parità, codice di Hamming, distanza di Hamming, somme di controllo e CRC

Sistemi di numerazione: Binario ed esadecimale Codice Gray Codici BCD Virgola mobile e fissa Parità, Hamming e CRC

Bit di parità

Dati

Codice di Hamming

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.

Dati

parità · dati · parità globale · bit cambiato.

Distanza di Hamming tra due parole

Parole

Calcolatore di CRC e somme di controllo

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.

Trama

CRC passo per passo: la divisione polinomiale

Divisione

Perché servono

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:

Distanza di Hamming

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:

\[ \text{rileva fino a } d - 1 \text{ errori} \qquad \text{corregge fino a } \left\lfloor \frac{d-1}{2} \right\rfloor \text{ errori} \]
CodiceDistanza minimaRilevaCorregge
Dati senza ridondanza1nienteniente
Bit di parità, 2 su 521 erroreniente
Hamming32 errori1 errore
Hamming con parità globale (SECDED)43 errori1 errore e ne rileva 2
Ripetere ogni bit 3 volte32 errori1 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.

Parità

È 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.

Il codice di Hamming

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:

\[ 2^{r} \ge m + r + 1 \]
Esempio: Hamming (7, 4) con i dati 1011

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.

CodiceBit di datiBit di paritàRendimento
Hamming (7, 4)4357 %
Hamming (15, 11)11473 %
Hamming (31, 26)26584 %
Hamming (63, 57)57690 %
SECDED (72, 64), memoria ECC64889 %

SECDED: correggerne uno e rilevarne due

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.

Somme di controllo

Sono veloci e facili da programmare, ma rilevano molto peggio di un CRC della stessa dimensione.

CRC (controllo di ridondanza ciclico)

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.

Esempio: messaggio 11010011101100 con il generatore 1011 (\(x^3 + x + 1\))

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:

Perché lo stesso «CRC-16» dà numeri diversi

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.

Il CRC nell’industria

Altri codici correttori

Vedi anche: convertitore binario ed esadecimale, codice 2 su 5 e simulatore di porte logiche (lo XOR).