error_detection2

Nella sua forma piu’ generica, un qualsiasi sistema di comunicazione si puo’ schematizzare con tre semplici blocchi:

teoriasegnali1Dove il trasmettitore è l’apparato che invia l’informazione e il ricevitore è il suo speculare.

Per canale intenderemo, se non meglio specificato, “tutto ciò che li separa” …

Questa schematizzazione è volutamente molto generica.

Nulla impedisce, infatti, che il trasmettitore siamo… noi stessi che parliamo a voce alta ad un nostro amico (il ricevitore dell’informazione) e il canale sia l’autobus affollato su cui siamo saliti.

E’ una esperienza comune che tra il trasmettitore e il ricevitore qualcosa possa andare “storto” e la comunicazione risulti compromessa; contenga quindi i proverbiali “fischi per fiaschi”.

Omettendo difetti o problemi da entrambi i lati (non stiamo mangiando mentre parliamo e il nostro amico ci sente benissimo) rimane soltanto un possibile colpevole: il canale.

Come vedremo il canale è, per sua definizione, fonte di incertezza e quindi di rumore. Il rumore può essere appena percepibile o, nei casi peggiori, può superare e di molto gli sforzi del trasmettitore, rendendoli vani (mai provato a sussurrare qualcosa vedendo un film al cinema …?)

Con il termine generico di rumore si intende qualsiasi perturbazione (disturbo) impredicibile che altera apprezzabilmente la qualita’ dell’informazione ricevuta.

Le caratteristiche del rumore non sono per definizione prevedibili, al più si può arrivare ad una rappresentazione statistica.

Il rumore è specifico per ogni tipo di canale. Osservando il cielo stellato il principale rumore è la luce di un lampione. Parlando al cellulare, il rumore può essere una sirena della polizia. O l’orribile palazzone di vetro e acciaio da cui stiamo telefonando. O la pioggia. [Nota, le onde elettromagnetiche dei cellulari sono riflesse e dissipate dai fabbricati e sono attenuate dall’atmosfera e dalle particelle d’acqua].
Per essere un po’ piu’ realistici il nostro sistema di comunicazione, per quanto minimalista, andrebbe rappresentato in questo modo :

error_detection_schema_generale

Puo’ essere interessante notare che questo schema è così generico da avere due importanti caratteristiche:

* Si applica alla maggioranza dei sistemi di comunicazione reali (e con un po’ di approssimazione, alla quasi totalità), semplici o complessi che siano ;

* Può essere applicato in modo ricorsivo a tutte le sotto-componenti del sistema. Diciamo che è una rappresentazione… “frattale” !

Facciamo un esempio:

Il trasmettitore potrebbe essere il sito di Netflix e il ricevitore la nostra TV in salotto. Il canale rappresenta, quindi, tutta la rete Internet che interconnette i dispositivi.

Se andiamo piu’ in dettaglio, la TV del salotto è connessa al nostro router wifi. Quindi il router fa da trasmettitore rispetto al televisore. A sua volta, il router è connesso tramite il doppino telefonico alla centralina (armadio) della Telecom, posto sotto casa. In questo caso, il router fa da ricevitore e l’armadio da trasmettitore.

A sua volta, la centralina è connessa alla centrale provinciale che e’ connessa alla rete nazionale e cosi’ via.

Si ricava che ogni macro-blocco puo’ essere scomposto nella terna: Trasmettitore/Canale/Ricevitore. Generalmente questa espansione ricorsiva termina quando il canale smette di essere un blocco logico di interconnessione e diviene un mezzo fisico.

I mezzi fisici nei sistemi di comunicazione sono moltissimi, ma i piu’ comuni sono sicuramente l’atmosfera in cui si propagano le onde radio, il doppino di rame un po’ ossidato della linea telefonica e le fibre ottiche che uniscono in grandi fasci l’Europa con l’America.

I mezzi possono essere anche i più esotici, ma vale la stessa regola: il canale introduce sempre un certo rumore. Sia esso il vuoto cosmico attraversato dalla luce delle stelle più lontane per raggiungere un telescopio, sia il cavetto delle cuffie mentre vediamo un film sul tablet, sia la sala dell’auditorium dove ascoltiamo un concerto.

Inoltre l’accezione del sistema di comunicazione può essere sorprendentemente vasta. Anche un hard disk che memorizza un file ha un trasmettitore (il computer) un ricevitore (la superficie magnetica) e un canale (il vuoto all’interno e i circuiti di interconnessione).

Persino quando leggiamo un libro possiamo identificare un trasmettitore (la carta stampata) un ricevitore (i nostri occhi) e un canale (l’aria, ma anche il vetro dei nostri occhiali). E i disturbi non mancano, da un fastidioso riflesso agli occhiali graffiati e non tanto puliti.

Come abbiamo detto, il rumore è specifico per ogni canale, ovvero per ogni mezzo fisico (espandendo i vari blocchi logici, prima o poi si arriva sempre alla fisica…)

Limitandoci alle comunicazioni tra dispositivi elettronici connessi tramite cavi in rame o via wireless, le fonti di rumore possono essere interne (rumore provocato dal movimento caotiche delle cariche elettriche nel mezzo e nei trasduttori che lo accoppiano a trasmettitore e ricevitore) ed esterne. Queste ultime sono le piu’ insidiose. Tipicamente si tratta di radio-onde, spesso generate da altri dispositivi nelle vicinanze.

Entrando nello specifico dei sistemi di trasmissione digitali, è noto a tutti che le informazioni sono inviate attraverso una sequenza di zero e di uno (i bit, tipicamente raggruppati 8 alla volta, i bytes).

L’effetto del rumore su tali trasmissioni è che, con una certa probabilità, uno o più bit arrivano al ricevitore alterati (un uno e’ divenuto uno zero, o viceversa).

Se il sistema di comunicazioni funziona correttamente, la probabilita’ che il singolo bit venga alterato dovrebbe essere relativamente bassa; ipotizziamo per pura semplicita’ che sia minore o uguale dell’ 1%, ovvero mediamente ogni 100 bit un bit subisce un’alterazione.

error_detection3

Figura 4: Esempio di errore con inversione di 1 con 0

L’osservazione che la probabilità di errore sia relativamente bassa ci suggerisce un modo efficiente di contrastare il rumore, ovvero dividere la trasmissione in opportuni “pacchetti” ed aggiungere alla fine di ogni pacchetto dei “simboli di controllo” (un “simbolo” può essere un bit, o magari un byte, o anche molti byte). Un accordo preliminare tra il trasmettitore e il ricevitore permette a quest’ultimo di analizzare i simboli di controllo e verificare se l’ultima informazione ricevuta è corretta o è affetta da errore. In questo caso il ricevitore puo’ richiedere la ri-trasmissione del pacchetto.

Occorre osservare che se il messaggio da inviare è molto lungo, la suddivisione in pacchetti è fondamentale per ottenere una certa efficienza. Infatti è molto più rapido chiedere il ri-invio dei soli pacchetti errati (la minoranza, in teoria) piuttosto che dell’intero messaggio.

I simboli di controllo opportunamente aggiunti, detti anche “ridondanza”, permettono di ottenere due risultati:

* La Rilevazione degli Errori (Error Detection), per cui è possibile verificare la correttezza (o meno) del contenuto informativo ricevuto ;

* La Correzione automatica degli errori mediante codifiche E.C.C. (Error Correcting Codes) per cui il sistema è automaticamente in grado di apportare tutte le correzioni, ovvero di chiedere la ri-trasmissione se il numero di errori è eccessivo.

La tecnica più semplice per la rilevazione degli errori è l’aggiunta di un parity bit.

In pratica, una sequenza di N bit informativi viene seguita da un singolo bit di controllo: il parity bit, appunto. Questo bit vale “0” o “1” a seconda della somma modulo 2 dei bit della sequenza informativa che lo precede. Ad esempio, se la somma (modulo 2) fosse 0, il bit aggiunto vale “1”. Viceversa, se la somma fosse 1 il bit aggiunto vale “0”.

E’ semplice verificare che se uno dei bit della trasmissione venisse alterato il parity bit permetterebbe immediatamente (e con semplicità) di rilevare l’errore sul pacchetto.

Notare che questa tecnica funziona solo se la probabilita’ di errore è abbastanza bassa (non piu’ di un bit per pacchetto), in quanto se i bit alterati fossero due (o un multiplo di 2, ad es. 4) la parity risulterebbe comunque corretta e la detection fallirebbe!

Una variazione interessante della bit-parity appena descritta (detta monodimensionale) è la bit-parity bidimensionale.

In questo caso la sequenza di dati viene scritta in una matrice (ad es. i 64 bit di un pacchetto sono scritti all’interno di una matrice di dimensione 8×8) e per ciascuna riga e ciascuna colonna e’ calcolato il parity-bit. Questo permette di ottenere una maggiore robustezza ai disturbi.

Un’evoluzione della tecnica del parity bit è il Checksum. Dalle due parole inglesi Verifica e Somma, il checksum è “un codice di verifica basato su una somma” o comunque su una operazione aritmetica.

Come esempio di checksum si potrebbe decidere di aggiungere ad una sequenza di quattro numeri interi da trasmettere (5, 7, 11, 12) un quinto numero, che sia semplicemente la somma algebrica dei precedenti; in questo caso: 35 (5+7+11+12=35).

In caso di errore nella trasmissione di uno dei cinque numeri (es. si riceve: 5, 7, 10, 12, 35) il ricevitore sarebbe facilmente in grado di rilevare un errore (infatti 5+7+10+12 è uguale a 34 e non a 35).

Il checksum per la sua semplicita ed efficacia è presente in molte codifiche di uso comune.

Qui di seguito vedremo il funzionamento del codice ISBN mentre nel successivo post, parleremo di  codice fiscale,  carte di credito e faremo un esempio di correzione automatica degli errori.

I codici ISBN e EAN

Il primo sistema universale per la catalogazione di articoli fu ideato per le librerie nel 1965 (SBN, Standard Book Numbering, specifico per libri e giornali), in breve trasformato nel codice numerico internazionale per le pubblicazioni, ISBN, in uso ancor’oggi.

Sin da subito fu posto il problema della lettura di tale codice con lo scanner, generalmente una grossa fonte di errori. Un primo esperimento fu fatto con l’apposito font “OCR-A”, che facilita la lettura di testo da parte delle macchine (e’ usato tuttora dalle banche, ad esempio per i numeri delle carte di credito o degli assegni); la scarsa qualita’ e gli alti costi degli scanner dell’epoca lo fecero ritenere non sufficientemente affidabile.

Si passo’ quindi ad un sistema di codifica dei numeri con codice a barre, che semplifica di moltissimo il lavoro che deve svolgere lo scanner, riducendo gli errori. Fu anche aggiunta una cifra di checksum, funzione di tutte le cifre presenti nel codice, per evidenziare eventuali errori dovuti alla trascrizione, dettatura telefonica o cattiva scansione.

Un codice ISBN e’ costituito complessivamente da 10 numeri, raggruppati secondo una regola. Questa e’ una possibile regola di codifica per le 10 cifre:

  • 2 cifre: Codice paese (o gruppo linguistico)
  • 4 cifre: Editore (un editore puo’ possedere piu’ di un codice)
  • 3 cifre: Titolo
  • 1 cifra: Checksum

In effetti questa regola puo’ variare leggermente. Ad esempio, editori con un vasto numero di titoli possono richiedere un codice editore piu’ breve (a 2 o 3 cifre) in modo da poter spendere 4 o 5 cifre per il titolo. Paesi con minor numero di case editrici hanno un codice paese a 3 cifre, e cosi’ via. I paesi angolossasoni hanno solo una cifra per il codice paese (“0” oppure “1”).

Per fare un esempio, quando la Sig.ra Rowling porto’ al suo editore il primo libro di Harry Potter, nel 1997, le venne assegnato questo codice ISBN: 0747532745.

Infatti:

  • Gruppo linguistico: “0“, Inglese
  • Editore: “7475“, Bloomsbury Publishing
  • Titolo: “3274“, Harry Potter and the Philosopher’s Stone
  • Checksum: “5” (spiegato in seguito)

Riconoscendo l’efficacia del codice ISBN in ambito librario, una estensione alla catalogazione di qualsiasi articolo ebbe come risultato la codifica UPC, divenuta poi EAN.

In questo caso le cifre utilizzate sono 13. Questa e’ una possibile regola di raggruppamento:

  • 3 cifre: Codice paese (chiamato anche codice GS1)
  • 5 cifre: Codice produttore
  • 4 cifre: Numero articolo
  • 1 cifra: Checksum

Curiosamente, si e’ scelto di non abbandonare la codifica ISBN dei libri facendola convergere nella codifica (piu’ generale) EAN.

Come effetto, dunque, ogni libro dispone di due codifiche differenti (secondo il registro ISBN e secondo il registro EAN).

Fortunatamente, pero’, i libri non vengono ricodificati da zero nei due registri, bensi’ vengono dotati all’origine di un codice ISBN e il codice EAN si puo’ ricavare facendo precedere il suo codice ISBN dal numero “978“.

Ricordando che le prime tre cifre del codice EAN sono il paese di provenienza, risulta che tutti i libri provengono da un paese fittizio, chiamato convenzionalmente “Bookland” (indipendentemente dal reale gruppo linguistico della pubblicazione, che e’ comunque ricavabile dalla prima cifra del codice ISBN).

Resta pero’ un piccolo problema. Il checksum, presente in entrambe le codifiche, e’ funzione di tutte le cifre presenti nel codice !

Per cui, il checksum di un codice EAN e’ funzione delle prime 12 cifre mentre il checksum di un codice ISBN e’ funzione delle prime 9.

Come risultato, quando si costruisce il codice EAN di un libro occorre ri-calcolare il checksum, ignorando l’ultima cifra del codice ISBN.

La formula di verifica del checksum e’:

(wN·dN + wN-1·dN-1 + ... + w1·d1) mod M = 0
Dove i termini di sono le N cifre del codice da verificare, i coefficienti wi sono noti e sono detti pesi del codice e M e’ il modulo scelto per la somma.

Generalmente d1, l’ultimo termine della somma, e’ l’incognita da calcolare affinche’ la somma in modulo restituisca il risultato corretto, cioe’ zero.

Nell’ipotesi in cui w1 = 1, applicando le regole dell’aritmetica modulare, si ottiene:

(wN·dN + wN-1·dN-1 + ... + 1·d1) mod M = M mod M
1·d1 mod M = (M - (wN·dN + wN-1·dN-1 + ... + w2·d2 mod M) mod M)
d1 = (M - wN·dN - wN-1·dN-1 - ... - w2·d2) mod M
Nel caso della codifica ISBN-10 i parametri risultano:

  • N = 10
  • wj = j
  • M = 11

Mentre nel caso del EAN (anche chiamato ISBN-13):

  • N = 13
  • wj = 3 se j e' pari
  • wj = 1 se j e' dispari
  • M = 10

Come esercizio calcoliamo il checksum delle codifiche ISBN-10 e EAN del primo libro di Harry Potter, di cui conosciamo le prime 9 cifre del ISBN: 074753274

Nel caso del ISBN-10,

d1 = (11 - 10·0 - 9·7 - 8·4 - 7·7 - 6·5 - 5·3 - 4·2 - 3·7 - 2·4) mod 11 = (11 - 226) mod 11 = -215 mod 11 = -215 + (11·k) mod 11 = -215 + 220 = 5

Nel caso di EAN, in cui le prime cifre del codice sono: 978-074753274, il checksum risulta:

d1 = (10 - 1·9 - 3·7 - 1·8 - 3·0 - 1·7 - 3·4 - 1·7 - 3·5 - 1·3 - 3·2 - 1·7 - 3·4) mod 10 = (10 - 107) mod 10 = -97 mod 10 = -97 + (10·k) mod 10 = 97 + 100 = 3

Una semplice verifica sul sito di Amazon ci conferma che il libro in oggetto ha in effetti codice ISBN: 074753274-5 e codice EAN: 978-074753274-3

Per ora ci fermiamo qui con gli esempi di error detection….ma ovviamente non finisce qui…

Continueremo a parlare di questo argomento nella seconda parte che sarà pubblicata a breve ovviamente qui su “Math is in the Air”.

 

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