note di lavoro sull'argomento di Tecnologie e Progettazione di Sistemi, riferite alle pag 135-144.
rilevazione e correzione degli errori:
trasmissione di segnali digitali da sorgente a destinazione: possibile errore di trasmissione
ad ogni ricezione di un messaggio si controlla la correttezza e nel caso si sia rilevati errori:
- si scarta il messaggio
- si chiede e attende la ritrasmissione (ev. dopo aver migliorato le condizioni di comunicazione)
- meglio se si ha la possibilità di rilevare e CORREGGERE un errore.
condizione necessaria per rilevare un errore:
il codice non deve essere "efficiente", deve contenere alcune informazioni per gestire l'errore di tx e non sono i contenuti dei messaggi: si dice che il codice deve essere RIDONDANTE.
es. il codice ASCII è efficiente e non si può capire se il codice arrivato contenga errori di trasmissione oppure no.
condizione sufficiente per rilevare un errore:
DISTANZA di Hamming: numero di bit differenti tra due configurazioni binarie
Ex calcolo distanza tra due stringhe binarie
XOR tra le due stringhe produce una stringa il cui numero di 1 è proprio la distanza di hamming.
es. XOR con excel: SE bit stringa1 != bit stringa2 allora bit XOR = 1
DISTANZA MINIMA di un codice è la minima distanza che si trova tra due qualsiasi configurazioni del codice. es. codice ASCII la DMIN è 1: quanti bit differiscono tra le rappresentazioni binarie della lettera A e la lettera C?
DMIN dei codici pesati studiati?
ATT! un codice a rilevazione d'errore (SINGOLO) deve avere almeno DMIN = 2.
es.
ON 00
OFF 11
se il ricevente legge un codice 01 oppure 10 è sicuro di aver ricevuto un messaggio non valido e deve chiedere una ritrasmissione.
in generale un codice è in grado di rilevare N errori se ha almeno DMIN = N+1.
es. per rilevare 1 errore serve una DMIN almeno pari a 2. (il codice ASCII non è in grado di rilevare alcun errore di trasmissione).
codici di HAMMING: codici con bit di PARITA' per rilevazione e correzione degli errori.
es. BCD con bit di parità
si aggiunge a destra (LSB) un bit in modo che il numero di 1 sia pari per ogni stringa binaria trasmessa.
es. 01100
es. 00101
es. 00111 è un codice non legittimo (ha un numero di bit a 1 dispari, rilevato non corretto, da ritrasmettere)
ex. excel: calcolare il bit di parità di un codice BCD (si usa la funzione RESTO per decidere se il numero di bit a 1 è pari o dispari)
CORREZIONE dell'errore (singolo)
bit di parità su ogni byte o stringa binaria
+ bit di "parità" (checksum) in verticale su ogni colonna dei dati binari trasmessi
dalle coordinate orizzontali e verticali dei bit di parità e checksum si identifica il bit da correggere
vedi esempio e schema a pag. 143