SCIENZE & TECNOLOGIE INFORMATICHE
PROF. COSTA PAOLO
Teoria correzione dell’errore (error detection) nelle trasmissioni di dati
Quando due sistemi in comunicazione si trasferiscono informazioni mantenere l’integrità
dell’informazione è uno dei problemi fondamentali da risolvere. Ci sono diverse tecniche che rilevano
e correggono gli errori causati da interferenze varie nella trasmissione.
Nella trasmissione dei dati e informazioni tra sistemi c’è sempre un canale di trasmissione che li
separa e che può contenere altri segnali che viaggiano e che vanno ad interferire con tutti gli altri,
queste interferenze sono indicate come disturbi/rumori del canale. Un esempio molto comune e che ci
può capitare è quello di dovere comunicare con un nostro amico mentre stiamo viaggiando nel
pullman affollato, notiamo subito che, tra il vociare degli altri passeggeri ed il rumore del traffico, se
vogliamo tenere la nostra comunicazione con efficacia dobbiamo alzare la voce o ripetere le parole
più spesso, questo è l’effetto causato dal “rumore” che è presente sul pullman.
Con il termine rumore (disturbo) si indica una qualsiasi perturbazione impredicibile che altera
apprezzabilmente la qualità della trasmissione dell’informazione tra un sistema trasmittente ed un
sistema ricevente. Il rumore è specifico di ogni canale.
Esempi: la luce di un lampione mentre si osserva il cielo stellato; parlando al cellulare in strada
sentire la sirena della polizia; il rumore nelle cuffie perchè il cavetto è logorato; il fastidio oculare
mentre leggiamo un libro o guardiamo il monitor del computer; il riflesso degli occhiali che non sono
abbastanza puliti; etc.
Di questi tipi di rumore si possono distinguere quelli interni al canale (le cariche elettriche che
scorrono nel cavetto) e quelli esterni al canale (il rumore della sirena).
Nelle trasmissioni di informazioni digitali costituite da sequenze di bit (0 e 1) il rumore può alterare la
sequenza cambiando un bit da zero ad uno o un uno a zero. Questa alterazione può avvenire con
bassa o alta frequenza di probabilità dipende dalla qualità di isolamento del canale dai segnali
esterni. Nel caso di bassa probabilità (esempio 1%, un bit ogni 100) la tecnica di correzione più
efficiente è quella di far ritrasmettere il segnale al sistema trasmittente mentre, nel caso di alta
probabilità la correzione deve essere fatta con altre tecniche che fanno uso di metodi di calcolo
matematico aggiungendo ulteriori bit di informazione all’informazione originaria. Le tecniche di
correzione si dividono in due categorie:
● Rilevazione dell’errore (error detection), per cui è possibile rilevare la correttezza del
messaggio ricevuto; ossia la capacità di scoprire l’errore causato dal rumore o da altri
fenomeni deterioramenti durante la trasmissione delle informazioni.
● Correzione automatica dell’errore (error correction codes), il sistema è in grado di apportare
tutte le correzioni, o richiede la ritrasmissione se il numero di errori è eccessivo. Ossia la
tecnica di ricostruire l’informazione originaria, eliminando gli errori occorsi durante la
trasmissione.
La correzione dell’errore può avvenire secondo due modalità:
● Automatic repeat request (ARQ), in questo caso il mittente insieme ai dati invia un codice per
individuare l’errore che sarà utilizzato in ricezione e quindi richiedere la ritrasmissione dei soli
dati corrotti. Questa richiesta in molti casi è automatica in quanto il ricevente invia un segnale
ACK acknowledgment di risposta per i soli dati corretti, quindi il sistema trasmittente rinvierà
solo quei dati per i quali non riceve questo segnale entro un tempo limite (timeout) prefissato.
● Forward Error Correction (FEC), in questo caso il mittente codifica i dati con un codice a
correzione di errore (ECC) e li invia. Il ricevente non invia nessun messaggio di richiesta di
rinvio in quanto codifica il messaggio servendosi, anche, di un insieme di parole che risultano
accettabili per l’interpretazione e che solo in caso di un rilevante numero di errori presenti nel
pag 1.8
SCIENZE & TECNOLOGIE INFORMATICHE
PROF. COSTA PAOLO
messaggio ricevuto fa ottenere una interpretazione errata del messaggio effettivamente
inviato.
Entrambi gli schemi implicano l'introduzione di ridondanza (overhead) nel flusso di dati tra mittente e
destinatario diminuendo così la portata utile (throughtput) informativa ovvero diminuendo l'efficienza
di trasmissione e aumentando così la banda necessaria. Essi possono essere anche combinati tra
loro, in modo tale che gli errori più lievi siano corretti senza necessità di ritrasmissione, e quelli più
pesanti siano invece solamente individuati per poi richiedere la ritrasmissione.
La tecnica più semplice è quella dell’aggiunta del bit di parità: alla sequenza degli N bit
dell’informazione viene aggiunto il parity bit che deve avere il valore 0 (zero) se la somma degli uno
presenti nella sequenza è un numero pari (even), mentre deve avere il valore 1 (uno) sel la somma
degli uno presenti nella sequenza è un numero dispari (odd). Questa tecnica per la sua semplicità è
applicabile solo nel caso di alterazione di un solo bit o di un numero dispari di bit ma non è applicabile
per alterazioni elevate di bit o di un numero pari di bit.
Una tecnica più sofisticata è quella del Checksum, questa consiste nello scrivere la sequenza di bit
in una matrice e per ciascuna riga e colonna viene eseguita la somma dei bit per ottenere il parity bit,
questo metodo rende la trasmissione meno alterabile (risulta più robusto) dai disturbi. Un esempio
pratico del Checksum può essere la verifica della trasmissione di quattro numeri: 4; 7; 11; 12; al cui
somma (4+7+11+12) è 34 numero che viene aggiunto alla sequenza come controllo. Se si verifica
un’alterazione dei numeri nella trasmissione esempio l’undici 11 si muta in 17 la somma (4+7+17+12)
è 40 e l’errore sarebbe subito rilevato.
Il controllo di parità definisce un codice che si ottiene mediante l'aggiunta di un bit di parità (in
grassetto nella tabella), calcolato in modo tale che il numero totale di bit uguali ad 1 sia pari (in questo
caso si parla di even parity). Questo codice è in grado di rilevare errori in numero dispari (1, 3, 5, …,
ecc.); se ci fossero un numero pari di bit modificati l’errore non verrebbe rilevato.
Dato pos1 pos2 pos3 pos4 pos5 pos6 pos7 pos8 ctr
bit 0 1 0 0 0 0 1 0 0
peso 27 26 25 24 23 22 21 20 parity
B b1 b2 b3 b4 b5 b6 b7 b8 p
Nella tabella è rappresentato il codice del carattere “B” con il bit di controllo (ctr) posto ad zero (0)
perchè il numero totale di bit ad 1 è pari.
Questa tecnica viene comunemente usata nell'ambito della trasmissione asincrona e sincrona
orientata al carattere, per rivelare errori sul bit, è il codice di controllo utilizzato nei calcolatori per
prevenire errori nella ricezione dei dati o nella lettura su memorie di massa, aggiungendo
informazione ridondante. Per la sua semplicità, la parità è usata in molti dispositivi hardware dove le
operazioni possono essere ripetute in caso di difficoltà, o se è solo utile sapere che è avvenuto un
errore. Per esempio i bus SCSI e PCI usano la parità per trovare errori di trasmissione, inoltre molte
cache di microprocessori includono tale sistema di protezione. Dato che le cache dati sono solo una
copia della RAM, se vi si trova un errore, può essere cancellata e ricaricata.
Nelle trasmissioni seriali dei dati, viene usato comunemente un formato di 7 bit, con un bit di parità
pari e uno o due bit di stop. Questo formato può essere utilizzato per i 7 bit del codice ASCII.
pag 2.8
SCIENZE & TECNOLOGIE INFORMATICHE
PROF. COSTA PAOLO
Durante la scrittura dei dati (sequenza di bit), si aggiunge un bit di controllo posto a 0 o 1 dopo ogni
byte. Nel caso in cui, all'interno di un byte,
i bit a 1 siano in numero pari, il bit
aggiuntivo verrà posto a 0. Nel caso
invece che i bit a 1 siano in numero
dispari, verrà aggiunto un bit posto a 1;
viene utilizzato anche in molte
applicazioni per la prevenzione degli
errori come la lettura dei dati memorizzati
su nastri magnetici, e per la memorizzazione dei byte nella memoria principale.
Quindi, il bit di parità è un codice di controllo, ma non è un codice di correzione d'errore, poiché non
c'è modo di determinare quale particolare bit è sbagliato. Usando un canale molto disturbato, può
essere necessario un lungo tempo per effettuare una trasmissione corretta, o può non accadere mai.
pag 3.8
SCIENZE & TECNOLOGIE INFORMATICHE
PROF. COSTA PAOLO
Problema 4: Archivi pag 57 vol 4
La codifica ASCII del carattere “B” è: <0100 0010>; supponiamo che la parità adottata sia pari (even).
Dopo il trasferimento di un carattere da un dispositivo periferico alla memoria centrale si rileva la
sequenza di bit <0100 0010 1>.
> Il trasferimento è stato eseguito in modo corretto?
> Quale è il bit che si trova nella posizione indicata dalla lettera X se la sequenza di bit rilevata è
<0100 X010 0>?
Svolgimento problema
Consideriamo l’informazione che deve essere trasferita il carattere “B” con codice binario <0100
0010> e secondo il protocollo adottato ai bit dell’informazione viene aggiunto un bit di controllo che è
detto “bit di parità” che, secondo, sempre il protocollo, viene posto a destra del bit meno significativo
(dopo il primo bit più a destra).
Secondo quanto stabilito dal problema il protocollo adotta come parità “even” (pari).
Quindi il bit di parità che può assumere due valori:1 e 0; in questo problema viene posto uguale a
zero perché il numero di bit uno presenti nella sequenza del carattere “B” è pari e per cui la somma
totale degli uno (compreso il bit di parità) deve rimanere invariata.
Dopo il trasferimento la sequenza dei bit presenta che la somma degli uno totali (compreso quello del
bit di parità) è dispari, la sequenza trasferita è <0100 0010 1>;
quindi la risposta alla domanda: “il trasferimento è stato eseguito in modo corretto?” è negativa,
ossia NO nel trasferimento si è verificato un errore che ha modificato il numero dei bit a uno rendendo
la somma dispari. In questo caso, particolare, proprio il bit di parità è stato modificato.
In questa modalità, per le regole dettate dal protocollo, l’errore viene subito individuato in quanto è
nota la posizione del bit di parità e quindi è possibile eliminare l’errore.
Nel caso che nel trasferimento si sia verificato la modifica di un bit e che questa riguardi uno dei bit
dell’informazione, l’evidenza dell’errore non comporta la possibilità di eliminare l'errore perchè nella
realtà non è possibile individuare quale bit è stato modificato; questo errore può essere eliminato solo
con delle ripetizioni di rinvio dell’informazione, la sequenza binaria del carattere “B” e del bit di
controllo. Questa descrizione riguarda il secondo quesito del problema: “Determinare che valore
pag 4.8
SCIENZE & TECNOLOGIE INFORMATICHE
PROF. COSTA PAOLO
assume il bit indicato dalla lettera “X” nella sequenza <0100 X010 0>?”. La risposta a questo quesito
non è semplice perché il protocollo non specifica altre informazioni per permettere di determinare il
valore della X. Quindi anche in questo caso si deve rinviare la sequenza di bit fino ad eliminare
l’errore.
Il codice di Hamming
Ci sono procedimenti che permettono, una volta individuato la presenza di un errore tramite il bit di
controllo, di eliminare questo errore ed uno di questi è il <codice di Hamming>.
Il codice di Hamming si basa sul metodo di aggiungere maggiore informazione (più bit)
all’informazione da trasferire prima che essa sia effettivamente trasferita. In genere il codice di
Hamming aggiunge quattro bit (h1, h2, h3, h4) di controllo per ogni 8 bit (1 byte) di informazione nelle
posizioni 1, 2, 4, 8 della sequenza dei dodici bit.
Applicazione codice Hamming
Per fare un esempio di applicazione del codice di Hamming prendiamo in considerazione il carattere
“B” ed il suo codice binario: <0100 0010> (8 bit = 1 byte) a questa sequenza devono essere aggiunti
quattro bit ottenendo un totale di dodici bit. Per operare con semplicità ci creiamo questo schema
pos 1 pos 2 pos 3 pos 4 pos 5 pos 6 pos 7 pos 8 pos 9 pos 10 pos 11 pos 12
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100
h1 h2 m1 h3 m2 m3 m4 h4 m5 m6 m7 m8
20 = 1 21 = 2 22 = 4 23 = 8
Nel codice di Hamming la stringa da trasmettere è: <h1 h2 m1 h3 m2 m3 m4 h4 m5 m6 m7 m8>,
per il nostro esempio il messaggio da trasmettere è: M = <m1 m2 m3 m4 m5 m6 m7 m8>. Così come
composto il codice di Hamming fa in modo di controllare due volte ogni bit del messaggio. I valori dei
bit di controllo, infatti, sono ottenuti con una operazione di XOR (^) bit a bit sui bit del messaggio e
sono così formati:
> h1 = 20 = 0001 presenta 1 alla 4a posizione e quindi controlla nella stringa quelle posizioni che
hanno un 1 in 4a posizione, ossia h1 = m1 ^ m2 ^ m4 ^ m5 ^ m7
> h2 = 21 = 0010 presenta 1 alla 3a posizione e quindi controlla nella stringa quelle posizioni che
hanno un 1 in 3a posizione, ossia h2 = m1 ^ m3 ^ m4 ^ m6 ^ m8
> h3 = 22 = 0100 presenta 1 alla 2a posizione e quindi controlla nella stringa quelle posizioni che
hanno un 1 in 2a posizione, ossia h3 = m2 ^ m3 ^ m4 ^ m8
pag 5.8
SCIENZE & TECNOLOGIE INFORMATICHE
PROF. COSTA PAOLO
> h4 = 23 = 1000 presenta 1 alla 1a posizione e quindi controlla nella stringa quelle posizioni che
hanno un 1 in 1a posizione, ossia h4 = m5 ^ m6 ^ m7 ^ m8
Essendo il messaggio M = “B” = 0100 0010 andiamo a calcolare i valori dei bit di controllo
h1 = m1 ^ m2 ^ m4 ^ m5 ^ m7 = 0 ^ 1 ^ 0 ^ 0 ^ 1 = 0
h2 = m1 ^ m3 ^ m4 ^ m6 ^ m7 = 0 ^ 0 ^ 0 ^ 0 ^ 1 = 1
h3 = m2 ^ m3 ^ m4 ^ m8 =1^0^0^0 = 1
h4 = m5 ^ m6 ^ m7 ^ m8 =0^0^1^0 = 1
ottenuti i quattro bit <h1 h2 h3 h4> = <0 1 1 1> li andiamo ad aggiungere a quelli di “B” per formare la
stringa di Hamming, ossia:
H = <0 1 0 1 1 0 0 1 0 0 1 0>
Dato pos1 pos2 pos3 pos4 pos5 pos6 pos7 pos8 pos9 pos10 pos11 pos12
bit 0 1 0 1 1 0 0 1 0 0 1 0
011
cod 0001 0010 0011 0100 0101 0110 1000 1001 1010 1011 1100
1
H h1 h2 m1 h3 m3 m3 m4 h4 m5 m6 m7 m8
A questo punto per verificare che nel trasferimento non ci siano stati errori è necessario che l’unità
ricevente esegua delle operazioni di XOR sulla stringa ricevuta e, queste operazioni sono così
formate:
S1 = h1 ^ m1 ^ m2 ^ m4 ^ m5 ^ m7 = 0 ^ 0 ^ 1 ^ 0 ^ 0 ^ 1 = 0
S2 = h2 ^ m1 ^ m3 ^ m4 ^ m6 ^ m7 = 1 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 0
S3 = h3 ^ m2 ^ m3 ^ m4 ^ m8 =1^1^0^0^0 = 0
S4 = h4 ^ m5 ^ m6 ^ m7 ^ m8 =1^0^0^1^0 = 0
avendo ottenuto che tutte le somme Si e quindi la sequenza <S4 S3 S2 S1> = <0 0 0 0> sono zero
si può affermare che non c’è stato errore nel trasferimento dell’informazione.
Ora facciamo il caso, del problema, che nel trasferire “B” = <0100 0010> si sia verificato un errore che
ha modificato un bit e la stringa ricevuta sia quella contenente “X” ossia: M = <0100 X010> e si vuole
determinare la posizione del bit modificato ed anche il suo il valore. Quindi andiamo a formare la
stringa di Hamming, H = <h1 h2 m1 h3 m2 m3 m4 h4 m5 m6 m7 m8> nella quale il bit modificato è
m5; per semplicità e chiarezza di scrittura rappresentiamo la stringa in tabella
pos 1 pos 2 pos 3 pos 4 pos 5 pos 6 pos 7 pos 8 pos 9 pos 10 pos pos 12
11
h1 h2 m1 h3 m2 m3 m4 h4 m5 m6 m7 m8
0 1 0 1 1 0 0 1 1 0 1 0
Ora calcoliamo le somme con l’operazione di XOR bit a bit sulla stringa ricevuta secondo la regola di
Hamming prima vista
S1 = h1 ^ m1 ^ m2 ^ m4 ^ m5 ^ m7 = 0 ^ 0 ^ 1 ^ 0 ^ 1 ^ 1 = 1
S2 = h2 ^ m1 ^ m3 ^ m4 ^ m6 ^ m7 = 1 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 0
pag 6.8
SCIENZE & TECNOLOGIE INFORMATICHE
PROF. COSTA PAOLO
S3 = h3 ^ m2 ^ m3 ^ m4 ^ m8 =1^1^0^0^0 =0
S4 = h4 ^ m5 ^ m6 ^ m7 ^ m8 = 1 ^ 1 ^ 0 ^ 1 ^ 0 =1
otteniamo la sequenza (S4 S3 S2 S1)2 = (1 0 0 1)2 = (9)10 che ci indica posizione che occupa il bit
che nel trasferimento è stato modificato, ossia il nono bit essendo il suo valore uno (1) si modifica nel
valore zero (0), cvd.
Un’altra applicazione della tecnica del Checksum
I codici ISBN e EAN
Nel 1965 fu creato il codice per la catalogazione dei libri l’SBN (Standard Book Numbering) che in
breve tempo fu internazionalizzato come ISBN. Questo codice è stato associato alla versione codice
OCR-A con lettura mediante sistema ottico scanner. Ma il sistema di lettura dei caratteri risultava
poco affidabile e costoso quindi si passò al codice a barre. I sistemi di lettura possono causare errori
e quindi il codice a barre ha un suo sistema di rilevazione dell’errore un Checksum, questa cifra è
correlata alle cifre che compongono il numero.
Il codice ISBN è formato da 10 cifre raggruppate con una certa regola:
● 2 cifre per il paese (o gruppo linguistico)
● 4 cifre per l’editore (un editore può avere più di un codice)
● 3 cifre per Titolo
● 1 cifre Checksum
A questa regola possono esserci delle variazioni: una cifra per il paese (come l’Inghilterra 0), due o
tre cifre per l’editore e quindi cinque o tre per il titolo. Per fare un esempio, quando la [Link] Rowling
porto' al suo editore il primo libro di Harry Potter, nel 1997, le venne assegnato questo codice ISBN:
0-7475-3274-5.
Infatti:
Gruppo linguistico: "0", Inglese
Editore: "7475", Bloomsbury Publishing
Titolo: "3274", Harry Potter and the Philosopher's Stone
Checksum: "5" (spiegato in seguito)
Questo codice è così efficace che è stato esteso a tutti gli articoli e viene indicato con EAN ed in
questo caso le cifre sono 13, così distribuite:
● 3 cifre: Codice paese (chiamato anche codice GS1)
● 5 cifre: Codice produttore
● 4 cifre: Numero articolo
● 1 cifra: Checksum
Il codice EAN non ha sostituito del tutto il codice ISBN in quanto i libri riportano entrambi e nel caso
sia presente il solo ISBN aggiungendo 978 si ottiene l’EAN.
Deve tenersi presente che le prime tre cifre dell’EAN son del paese e quindi il 978 indica un paese
fittizio chiamato “Bookland”. Un’altra particolarità è sulla cifra Checksum che per l’EAN è dipendente
dalle prime 12 cifre mentre per l’ISBN è dipendente dalle prime 9 cifre.
Quando si costruisce l’EAN non bisogna considerare l’ultima cifra dell’ISBN, la formula per la verifica
del checksum è
pag 7.8
SCIENZE & TECNOLOGIE INFORMATICHE
PROF. COSTA PAOLO
(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, cioè' 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
Riferimenti sitografici:
> Bit di parità
> Modbus RTU - Guida Completa
> Controllo parità
> Operazione bit a bit
> L'error detection nelle trasmissioni digitali
>
pag 8.8