I principali metodi di rilevazioni di errori sono 3: CRC, CHECKSUM ed HAMMINGma ci siamo mai chiesti in che modo nascono questi errori?
DOVE NASCONO GLI ERRORI?
Quando avviene uno scambio di informazioni tra l’elaboratore e la memoria attraverso i fili paralleli (BUS), il segnale trasmesso può essere soggetto a rumori e quindi si può sovrapporre creando un bit errato. In caso vi sia la presenza di ERRORE questo può esser trattato in 4 modi diversi:
Il messaggio viene scartato.
Viene richiesta la trasmissione del messaggio.
Viene migliorata la qualità del canale.
L’errore viene cercato di correggerlo
HAMMING
Nel 1950 Hamming propone il sistema di codifica a correzione d’errore che porta oggi il suo nome: il codice di Hamming.
L’idea di base del codice di Hamming è quella di codificare la posizione dell’eventuale errore
Si aggiungono alcuni bit di controllo, tanti quanti sono necessari per codificare la posizione del bit errato
Poiché anche i bit di controllo sono soggetti a errore, occorre includere anche le posizioni di questi bit nel conteggio totale.
Data una stringa di 8 bit, si aggiungono 4 bit di controllo, per un totale di 12 bit di codework
4 bit di posizione bastano per codificare le 12 posizioni, dato che 24 = 16 ci permette di codificare 16 posizioni (4 configurazioni non utilizzate).
Codework è il risultato della somma dei bit di dati + i bit di controllo
Esempio
BIT DI CONTROLLO
Costruiamo il singolo codework “mischiando” bit di informazione e bit di controllo. Innanzitutto numeriamo i bit della parola da trasmettere a partire da sinistra verso destra, inserendo a ogni posizione avente per indice una potenza del 2 il posto per un bit di controllo.
Ogni bit di controllo è un bit di parità che esprime la parità di un sottoinsieme opportuno dei bit della stringa
il bit di controllo in posizione 2j controlla la parità di tutti i bit la cui posizione, in binario, ha il j-esimo bit a 1
Il primo bit di controllo si ottiene come parità di tutti i bit che sono in posizione tale per cui la loro codifica binaria ha 1 nel bit meno significativo (sono tutte le posizioni dispari).
primo bit di controllo
Il secondo bit è di parità per tutti i bit in cui la codifica binaria della posizione ha il 2° bit = 1, e cioè 2 3 6 7 10 11..
secondo bit è di parità
Il terzo bit è di parità per tutti i bit in cui la codifica binaria della posizione ha il 3° bit=1, cioè 4 5 6 7 12 …
Il quarto bit è di parità per tutti i bit in cui la codifica binaria della posizione ha il 4° bit = 1 cioè 8 9 10 11 12 …
terzo e quarto bit di parità
Per approfondire ti consigliamo la lettura di questi articoli:
I principali metodi di rilevazioni di errori sono 3: CRC, CHECKSUM ed HAMMING ma ci siamo mai chiesti in che modo nascono questi errori?
DOVE NASCONO GLI ERRORI?
Quando avviene uno scambio di informazioni tra l’elaboratore e la memoria attraverso i fili paralleli (BUS), il segnale trasmesso può essere soggetto a rumori e quindi si può sovrapporre creando un bit errato. In caso vi sia la presenza di ERRORE questo può esser trattato in 4 modi diversi:
Il messaggio viene scartato.
Viene richiesta la trasmissione del messaggio.
Viene migliorata la qualità del canale.
L’errore viene cercato di correggerlo
CHECKSUM
Come funziona CHECKSUM?
Per riuscire a correggere l’errore mediante un codice di parità è necessario utilizzare il sistema di controllo della parità incrociata. Si introduce in coda alla trasmissione di un blocco di n dati un byte, chiamato byte di checksum, che viene calcolato eseguendo l’operazione di XOR su tutti i byte costituenti il blocco-dati da trasmettere.
Questo metodo prende anche il nome di controllo di parità longitudinale LRC(Longitudinal Redundancy Check)
il bit di parità descritto precedentemente è detto anche controllo di parità trasversale o VRL
parità longitudinale e parità trasversale
ESEMPIO
Supponiamo che durante la trasmissione un bit del Dato3 si sporchi
Alla ricezione il controllo di parità trasversale ci segnala la presenza dell’errore sul Dato3 senza però indicarne la posizione.
Rilevamento posizione errore
Alla fine della trasmissione dei dati il controllo “verticale” ci segnala la presenza di un errore nel bit b5, dato che il numero di 1 è dispari
Dall’ intersezione tra la riga e la colonna individuiamo il bit che si è sporcato => siamo quindi in grado di correggere un errore
DIFETTI CHECKSUM
Se gli errori crescono non sono più rilevabili ed è necessario aumentare la distanza minima di Hamming introducendo ulteriori bit di ridondanza.
Per esempio, in presenza di due errori ci troviamo in questa situazione:
situazione
In questo caso però non siamo in grado di correggere perché entrambe le correzioni portano a configurazioni legittime e quindi generano un’ambiguità nella correzione.
I principali metodi di rilevazioni di errori sono 3: CRC, CHECKSUM ed HAMMING ma ci siamo mai chiesti in che modo nascono questi errori?
DOVE NASCONO GLI ERRORI?
Quando avviene uno scambio di informazioni tra l’elaboratore e la memoria attraverso i fili paralleli (BUS), il segnale trasmesso può essere soggetto a rumori e quindi si può sovrapporre creando un bit errato. In caso vi sia la presenza di ERRORE questo può esser trattato in 4 modi diversi:
Il messaggio viene scartato.
Viene richiesta la trasmissione del messaggio.
Viene migliorata la qualità del canale.
L’errore viene cercato di corregerlo
CRC
Esempio esercizio
ll metodo di rilevazione degli errori usato più comunemente nei sistemi di comunicazione è il codice CRC o codice a ridondanza ciclica.
Si utilizza un polinomio G(x), chiamato generatore polinomiale, in cui i bit di ordine più alto e più basso devono essere a 1, noto al mittente e al ricevente. Sia M(x) la stringa di bit da inviare (di m bit) e G(X) il polinomio generatore (di r bit). M(X) deve essere più lungo di G(X) cioè m>r. ll metodo si basa sul calcolo di una checksum che dipende da M(X) e G(x) da aggiungere in fondo a M(x) in modo che la stringa ottenuta sia divisibile per G(X). ll mittente invia un frame composto dai bit di dati (M(x)) e dalla checksum. Per verificare la corretta ricezione basta che il ricevente divida il frame per G(x); se la divisione dà un resto vuol dire che si è verificato un errore.
Parte 1
Per calcolare il CRC di un pacchetto M(X) di m bit si procede così:
Le operazioni sui polinomi sono eseguite in aritmetica modulo 2: non ci sono riporti per l”addizione o prestiti perla sottrazione; addizione e sottrazione sono identiche all’ or esclusivo. La divisione è eseguita come se fosse binaria ma la sottrazione è eseguita in modulo 2 (in pratica un divisore è contenuto nel dividendo se il dividendo ha tanti bit quanti il divisore contando le cifre dal primo 1 a sinistra).
Parte 2
Questo metodo del CRC non è infallibile; possono verificarsi degli errori nel frame inviato che danno comunque O come risultato della divisione del frame per G(X) e che quindi non sono rilevati. La scelta del polinomio G(X) `e importante perla bontà del metodo.
l polinomi che sono diventati standard internazionali sono:
