Prosegue in questo post la descrizione delle tecniche di error detection iniziata nel precedente articolo (clicca qui). Questa volta ci dedicheremo ad analizzare il codice fiscale e l’algoritmo di Luhn della carta di credito.

Vedremo infine un esempio di error correction attraverso la codifica di Hamming.

Il codice fiscale

Per identificare gli errori di trascrizione (rigorosamente, a mano…) del codice nei meandri della burocrazia, l’ultimo carattere del codice fiscale e’ un checksum.La regola di calcolo è piuttosto semplice, sebbene richieda la conoscenza di due look-up tables di pubblico dominio.Dati i 15 caratteri del codice fiscale, l’ultimo carattere si calcola con la formula: ƒ((S₁ + S₂) mod 26)Dove:

• La funzione ƒ(n) associa ad ogni numero nell’intervallo 0-25 la corrispondente lettera dell’alfabeto A-Z: 0→A, 1→B, … 25→Z.
• S₁ è somma di ogni numero intero associato a ciascun carattere in posizione dispari, mappato attraverso un’apposita look-up table fornita (LUT_dispari)
• S₂ è somma di ogni numero intero associato a ciascun carattere in posizione pari, anche in questo caso mappato mediante una look-up table fornita (LUT_pari), differente dalla precedente.

Le due look-up table sono disponibili online sul sito del ministero

Esempio. Calcoliamo il checksum per il codice fiscale del sig. Mario Rossi nato a Roma: RSSMRA80A01H501

S₁=("R"+"S"+"R"+"8"+"A"+"1"+"5"+"1") = (applicando ad ogni carattere la LUT_dispari) 8+12+8+19+1+0+13+0 = 61

S₂=("S"+"M"+"A"+"0"+"0"+"H"+"0") = (applicando ad ogni carattere la LUT_pari) (18+12+0+0+0+7+0) = 37

ƒ((S₁ + S₂) mod 26) = ƒ((61+37) mod 26) = ƒ(20) = U

Pertanto, il codice fiscale completo del sig. Rossi è: RSSMRA80A01H501U

Le carte di credito

Al fine di identificare gli errori dovuti alla trascrizione disattenta o a disturbi (rumore) nella linea telefonica, dato che nelle prime forme di e-commerce si comunicava per telefono, l’ultima cifra di ogni carta di credito è un checksum calcolato con l’algoritmo di Luhn.

• In particolare, dati i 15 numeri della carta di credito, l’ultima cifra si calcola con la formula: (S₁ + S₂)·9 mod 10Dove:
  • S₁ è la somma delle cifre in posizione dispari, dopo aver moltiplicato ogni cifra per 2 e, se questo prodotto supera 9, sottraendogli 9
  • S₂ è la somma delle cifre in posizione pari

  Esempio. Calcoliamo il checksum per questa carta di credito: 123446722244477

  S₁=((2·1)+(2·3)+(2·4)+(2·7-9)+(2·2)+(2·4)+(2·4)+(2·7-9))=(2+6+8+(14-9)+4+8+8+(14-9)) = 46

  S₂=(2+4+6+2+2+4+7) = 27

  (S₁ + S₂)·9 mod 10 = (46+27)·9 mod 10 = 657 mod 10 = 7

  Pertanto, il numero di carta di credito: 1234 4672 2244 4777  è valido rispetto al test di Luhn.

Per concludere, tra le forme più raffinate di codifica per Error Detection ricordiamo il CRC (Cyclic Redundancy Check) in cui sostanzialmente il codice di verifica è resto di una divisione. In particolare, l’intero messaggio (in binario) e’ il dividendo, il divisore è una sequenza predefinita e il quoziente viene semplicemente ignorato.

Il vantaggio in questo caso è che in caso di molteplici errori di trasmissione sul messaggio (ovvero, sul dividendo) e’ abbastanza probabile che il resto della divisione differisca anche sensibilmente dall’atteso, permettendo di rilevare l’errore.

Il CRC è largamente utilizzato in informatica. Ad esempio le comunicazioni via Internet altro non sono che la trasmissione di innumerevoli pacchetti TCP ciascuno dotato di un CRC. Se il CRC in ricezione non è valido il pacchetto viene scartato e occorre ritrasmatterlo.

Error Correction Codes: la codifica di Hamming

Una evoluzione delle semplici (ma efficaci) codifiche di Error Detection è data dalle codifiche ECC, gli Error Correction Codes. Si tratta di codifiche che permettono la correzione automatica degli errori quando possibile o altrimenti la rilevazione (Nota: questo accade quando il numero di errori è all’interno della capacità di correction/detection del codice ECC).

Tra le tecniche ECC più comuni ricordiamo:

• La codifica di Hamming
• La codifica Reed-Solomon

La codifica di Hamming è in grado di correggere un singolo bit errato all’interno di un pacchetto e rilevare (ma senza poter correggere) quando i bit errati sono due.

I bit contenuti nel messaggio binario da trasmettere vengono inseriti nella prima riga di un’apposita tabella. Mediante un semplice algoritmo si calcolano le colonne della tabella, ciascuna funzione del bit del messaggio in quella posizione; infine per ciascuna riga ottenuta dall’insieme delle colonne si calcola la parità di riga (ovvero, la somma dei bit di ogni riga modulo 2), che e’ la codifica richiesta.

In dettaglio, ogni colonna è popolata con la rappresentazione binaria della posizione del bit nel messaggio se il bit è 1, mentre non viene riempita se il bit è 0. Quindi se il quarto bit del messaggio fosse "1" la quarta colonna sarebbe [1 0 0], poiche’ 4 = 100₂

L’unica lieve complicazione (che, come vedremo, aggiunge la capacita’ di rilevare quando i bit errati sono due) è che alcune colonne sono “riservate”, in quanto i bit di codifica vengono “intramezzati” al codice, in posizioni fisse e costanti.

Pertanto i bit del messaggio vengono piazzati nelle colonne libere, saltando le colonne riservate che verranno poi occupate dai bit di codice.

Le colonne riservate sono tutte e sole le potenze di 2: 2⁰ = 1, 2¹ = 2, 2² = 4, … ed in generale 2ⁿ ∀ n.

Come esempio, calcoliamo la codifica di Hamming del messaggio “47” (in binario: 01000111₂).

Prima di calcolare la matrice “intramezziamo” il messaggio originale con i bit di codifica da calcolare: c₀c₁0c₂100c₃0111 (come gia’ detto la posizione di ogni bit di codifica c_n e’ semplicemente 2ⁿ).

Calcoliamo la tabella di codifica come descritto sopra. Per comodita’ la posizione (un semplice contatore incrementale che parte da 1) viene riportata in base 10 ed in base 2.

In neretto riportiamo i soli bit del messaggio che valgono 1.

Calcolando la parita’ (somma modulo 2) di ciascuna delle ultime quattro righe, si ottiene:

c₀ = (0 + 1 + 1 + 1) modulo 2 = 1

c₁ = (1 + 0 + 0 + 1) modulo 2 = 0

c₂ = (0 + 1 + 1 + 0) modulo 2 = 0

c₃ = (1 + 0 + 1 + 0) modulo 2 = 0

Per cui la codifica di Hamming del messaggio “47” è: 100010000111.

A questo punto mostriamo la capacità di correzione del codice in caso di un singolo bit errato in ricezione.

Supponiamo di ricevere la seguente sequenza: 100010000011, dove in rosso si è riportato l’errore, sul decimo elemento della sequenza (un 1 e’ diventato uno 0).

Prima di tutto il ricevitore (poiché conosce esattamente le posizioni dei bit di codifica) separa il messaggio dalla codifica:

messaggio = 01000011

codifica = 1000

quindi ricalcola i bit di codifica per il messaggio ricevuto, esattamente come descritto sopra, ottenendo stavolta: 0010₂

Andando a confrontare le due codifiche, quella inviata dal trasmettitore e quella calcolata dal ricevitore ed evidenziandone le differenze (c’è anche un apposito operatore binario, XOR, che restituisce i bit che differiscono in due sequenze, si ottiene:

XOR(1000₂, 0010₂) = 1010₂ = 10₁₀

Da cui, l’errore è sul decimo bit, come dall’ipotesi iniziale, che quindi da 0 si puo’ correggere automaticamente ad 1.

Dopo la correzione automatica l’intera sequenza risulterà: 100010000111.

Si lascia come semplice verifica al lettore che se venissero ricevuti due bit errati (es. si ricevesse la sequenza: 10001000001) il codice ri-calcolato dal ricevitore evidenzierebbe un errore su una delle posizioni riservate alla codifica. Questo, convenzionalmente, significa che il numero di errori supera la capacità auto-correttiva del codice (che è di un bit), ed è necessario richiedere nuovamente lo stesso pacchetto.

Nell’esempio precedente l’XOR restituirebbe 0001₂ che infatti è una posizione riservata ad un bit di codifica (c₀) e non ad uno dei bit del messaggio.

La RS è una codifica molto complessa, con una base matematica (Campi di Galois) che io non conosco se non superficialmente, e comunque è dominio dei matematici puri.

Spiegare come fa RS a fare la correzione dei bit è veramente  complesso e la lasciamo alla vostra curiosità.

Vi diciamo solo che si basa sull’idea del sovracampionamento di un polinomio a partire dai dati iniziali. Il polinomio è in altri termini calcolato in più punti di quanti sarebbero sufficienti a identificarlo univocamente.

Nota, per una trattazione piu’ estensiva dell’argomento “Error Correction” si rimanda alla serie di  articoli di Daniele

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.