rilevazione e correzione di errori

possibili errori quando si trasmette un dato

anche quando si memorizza

errori: tipi di soluzioni

rilevazione: c'è stato un errore in trasmissione? on in memorizzazione?
correzione: correggere l'errore, se c'è

rilevazione: modo ovvio

si trasmette due volte

si vede se arriva la stessa cosa due volte

svantaggo del modo ovvio

raddoppio il numero dei bit

esiste un modo con un solo bit in più: parità

parità

a⊕b = 1 se a e b sono diversi
definito come (a∧¬b) ∨ (¬a∧b)

a⊕b⊕c⊕d⊕e⊕f⊕…
vale 1 se il numero di variabili uguali a 1 è dispari
(es. solo a vale uno, oppure solo b, c, f)

verifica errori

vanno trasmessi o memorizzati 7 bit
se ne aggiunge un ottavo che è il loro ⊕

originari 1100111, numero dispari di uni, si aggiunge 1
originari 0011110, numero pari di uni, si aggiunge 0

risultato: numero pari di uni complessivi

in caso di errore…

parità ed errori

si inviano gli otto bit
fra questi il numero di uni è pari
parità su tutti gli otto bit è 0

11001111 → 11000111

si verifica un errore: un bit arriva diverso
arriva zero invece di uno, o viceversa

nel complesso, gli uni aumentano o diminuiscono di uno
da pari diventano dispari
parità su tutti gli otto bit è 1 invece di 0

parità di tutti gli otto:

no errore: 0
errore: 1

schema

no errore:

errore:

il bit aggiuntivo permette di rilevare un errore singolo

valutazione formula

formula ⊕ usata due volte:

prima di trasmettere: il valore dice quale bit aggiungere
in ricezione: verifica se c'è stato errore

stesso sistema per rilevare errori di memorizzazione

correzione di errori

basato su distanza di Hamming

esempio su numeri in base 4 invece di 2

multiplo di tre

invece di 0,1,2,3
si trasmette 0,3,6,9
numero in base dieci

un errore = cambiamento di +1 o -1

esempio di errore: invece di 3 arriva 4

valori corretti ed errati

corretti: 0,3,6,9
errati: tutti gli altri

arriva 4 ⇒ errore (rilevato)

in più…

correzione di errori

è arrivato 4
cosa era stato inviato?

inviato 3: un errore +1
inviato 6: due errori -1

più probabile un errore di due
era stato inviato 3
il singolo errore si può correggere

caso binario

i valori sono solo 0 e 1
non si possono moltiplicare

altro modo per distanziare quello che viene inviato:
aggiungere due bit invece di uno

hamming

parita' aggiunge 1 se dispari e 0 se pari; quindi il totale e' sempre pari un errore cambia in dispari totali, per questo funziona con ogni possibile errore ma con due bit cambia pari->dispari->pari, per questo non funziona con due errori ma c'e' un modo di modificare la parita' in modo tale che invece di coretto->errore->corretto e' corretto->errore->errore->corretto esempio correlato: si trasmette un valore intero n; ogni errore e' una modifica di +1 o -1 codifico n con 3*n, che e' un multiplo di 3 se arriva 3 e' ok, 4 o 5 no, 6 ok di nuovo se arriva 4 non solo so che e' sbagliato, ma che e' piu' probabile che sia un 3 con un errore +1 invece che un 6 con errore -2 se *assumo* che l'errore se c'e' e' singolo, allora riesco a correggere l'errore, non solo a rilevarlo nel caso binario non e' cosi' perche' i valori sono solo 0 e 1, per cui la massima distanza e' sempre 1; ma si riesce ugualmente a dare un concetto di distanza che puo' servire per la correzione di errori: un frammento da 7 bit viene trasmesso con due di parita' in un certo modo per cui due frammenti validi sono a distanza tre invece che due come nel caso di parita' e quindi si riesce a correggere un singolo errore

crc

modo di calcolare la parita'

 message   1     0     0     1     0     1     1     1
     
           |     |
           |     |
           |     |
           +-----%
                 |
                 V
     
 result          1     0     1     0     1     1     1

proseguo fino alla fine l'ultimo bit e' il codice

potrei farlo con secondo e terzo invece del secondo soltanto

 message   1     0     0     1     0     1     1     1
     
           |     |     |
           +-----------%
           |     |     |
           +-----%     |
                 |     |
                 V     V
     
 result          1     1     1     0     1     1     1

ma potrei farlo con secondo, terzo e quarto:

 message   1     0     0     1     0     1     1     1
     
           |     |     |     |
           +-----------------%
           |     |     |     |
           +-----------%     |
           |     |     |     |
           +-----%     |     |
                 |     |     |
                 V     V     V
     
 result          1     1     0     0     1     1     1

ma anche con secondo e quarto soltanto:

 message   1     0     0     1     0     1     1     1
     
           |     |           |
           +-----------------%
           |     |           |
           +-----%           |
                 |           |
                 V           V
     
 result          1     0     0     0     1     1     1

codice 1101 per dire: primo, secondo e quarto

vari modi di vedere la stessa operazione:

se il primo bit vale uno, si fa xor del codice con il messaggio
se il primo bot vale uno, si invertono i bit del messaggio nei punti in cui il codice vale 1
si fa xor del primo con i bit del messaggio nei punti in cui il codice vale 1
primo in and ogni bit del codice, poi xor con il messaggio

la prima variante si puo' vedere anche in questo modo: si calcola il polinomio x³ + x² + x⁰ dove x e' il primo bit del frammento di codice; viene 1101 se il primo bit vale 1, altrimenti 0; di questo valore si fa lo xor con il frammento di messaggio

questo formalizza CRC come un polinomio, cosa che permette la sua trattazione matematica; invece di dire "codice" si trova si dice "polinomio", perche' sono la stessa cosa: 1101 e' il polinomio x³ + x² + x⁰ dove x

esempio di come rileva gli errori in sequenza perche' e' adatto a errori in sequenza
ogni errore influenza più immediati successori insieme, diffusione dell'errore sui vicini

i due sistemi piu' usati in pratica, i relativi codici e usi http://en.wikipedia.org/wiki/Cyclic_redundancy_check, tabella

crc32: 0x04C11DB7
bzip2, Ethernet (IEEE 802.3), gzip, mpeg-2, png, sata, pkzip, posix cksum
crc32c: 0x1EDC6F41
btrfs, ext4, iSCSI, SCTP

nota che questi codici sono 32 bit, non includono l'uno iniziale

esempio: dove si trova il crc32 in un file png: a parte l'header (8 byte), e' una sequenza di sezioni; in cui ogni sezione e' fatta di: lunghezza (4), tipo di sezione (4), dati (variabile), CRC-32 (4); la lunghezza e' della sola parte dati; il CRC-32 e' calcolato su tipo e dati