Please enable JavaScript.
Coggle requires JavaScript to display documents.
codici per rilevazione d'errore - Coggle Diagram
codici per rilevazione d'errore
Identificazione e correzione degli errori
obbiettivo
stabilire numero massimo di errori che un codice è in grado di individuare
errore
cambiamento di un bit in una posizione della parola
identificazione della presenza di errori
codice rivelatore di ordine n
Se un codice deve rilevare n errori, la sua distanza di hamming deve essere almeno pari a "d=n+1"
PE
numero pari di 1
PO
numero dispari di 1
viene aggiunto un bit tra 0 e 1
Ridondanza del codice
La codifica necessaria affinchè si possa riconoscere un errore
Distanza o Distanza di Hamming
numero di bit per cui due configurazioni differiscono
per calcolare la distanza tra due codifiche si esegue lo
XOR
tra i due codici e si conta quanti 1 ha il risultato
Codice di Hamming
se la distanza di Hamming tra codici legittimi è pari almeno a d=2^n+1, allora è corregibile l'errore sino all'ordine n di errori
inventato nel 1950
è un codice che consente di correggere un singolo errore e funziona con qualunque dimensione del messaggio da tramettere
aggiunge bit di controllo
codice corretto ottimo:
bit_dati +bit_controllo +1<=2^bit_controllo
Distanza minima
un codice per la rilevazine di modifice su k bit deve avere almeno DMIN = k + 1
è la minima distanza minima di un codice
Correzione degli errori con LRC o byte di checksum
per correggere l'errore mediante un codice di parità è necessario utilizzare il sistema di controllo della
parità incrociata
byte di checksum
calcolato eseguendo lo
XOR
chiamato anche controllo di parità longitudinale(LRC)
dall'intersezione tra la riga e la colonna individuiamo il bit che si è sporcato
Codici ridondanti
per la rilevazione di errori è necessario l'utilizzo di
codici ridondanti
Codici rilevatori di errori
permette di scoprire se c'è un errore e correggerlo
Controllo di parità
codice di Hamming
Codici correttori di errori
permette di scoprire solo la presenza di un errore
bit di parità (o dispari)
CRC (Controllo a Ridondanza Ciclica)
m
= bit di dati contenenti informazione da trasmettere
r
= bit di controllo o bit ridondanti
Ciascuna parola in codice uilizza
n = m + r
bit, quindi ha lunghezza pari a
n
bit
BCD
aggiunge un bit in più alla codifica, chiamato
bit di parità
, in modo da rendere pari il numero di 1
chiamato anche
VRC
(VERTICAL REDUNDANCY CHECK
CODEWORK
risultato della somma dei bit dati + bit di controllo
SEDC
Single Error Detecion Code
CODICE LEGITTIMO
Parola in codice che soddisfa algoritmo di parità
CRC(Codice a Ridondanza Ciclica)
sfrutta la divisione tra polinomi
mittente
Divide polinomio M(x) per polinomio G(x) e aggiunge il resto ottenuto dalla divisione al codice da trasmettere
destinatario
Esegue la divisione e se il resto è 0 il codice è esatto altrimenti si è sporcato uno o più bit