Definizione
Una codifica – code – e una maniera di rappresentare l’informazione o i dati, secondo un insieme di regole predefinito.
Un code-word `e un insieme di simboli, digits se il sistema `e numerico, utilizzato per rappresentare una porzione di dati secondo una codifica specificato. Un code-word viene chiamato valido se rispetta tutte le regole definite dalla codifica,altrimenti viene chiamato non valido.
Un code ha 2 parametri: n e k dove k sta per la lunghezza di un qualsiasi code-word e n sta per la sua dimensione.
Il processo di codifica consiste nel prendere il dato originale e trovare il code-word corrispondente secondo la codifica scelta, cioè rappresentare il dato originale secondo le regole della codifica utilizzata.
Il processo di decodifica consiste nel recuperare, a partire dal code-word in questione, il dato originale che esso rappresenta.
Dettaglio in immagine:
Può accadere pero che se in un code-word binario uno dei suoi bit viene alterato da vari disturbi durante il trasferimento, il code-word stesso rimanga sempre nell’insieme dei codici validi pur essendo incorretto per il dato originale che rappresenta.
Per questo ci sono
tecniche di rilevamento di errori:che si basano su una codifica particolare.
Cosi,se la codifica e stata
progettata correttamente, l’alterazione di un singolo bit comporta, come risultato, un code-word che appartiene all’insieme
dei codici illegali o non validi.
Proprietà
1.Distanza di Hamming di un codice
Definizione
Per definire questo concetto ci serve prima definire il termine
distanza di Hamming.la distanza di Hamming tra due code-word `e data dal numero delle posizioni dei bit nelle quali le due parole differiscono.In altri termini, la distanza di Hamming misura il numero di
sostituzioni necessarie per convertire un code-word nell’altro. (Grazie Wiki)
Si definisce
distanza di Hamming di una codifica come la minima distanza di Hamming calcolata tra tutte le possibili coppie di code-word della codifica.
Conseguenze sulla rilevamento e la correzione di errori
Fatto1:Si osservi che se due code-word hanno distanza di Hamming pari a 1 e sempre possibile, alterando un bit ad uno dei due, farlo coincidere con l’altro.
Fatto2:Se invece due code-word hanno distanza di Hamming pari a 2, non e
assolutamente possibile, a partire da una delle due parole, recuperare l’altra alterando solo un bit in quanto i bit nei quali differiscono sono 2.
rilevamento degli errori.
Questi fatti mostrano come la distanza di Hamming sia utile ai fini del rilevamento degli errori. Infatti,se una codifica e caratterizzata da una distanza di Hamming pari a 2, tutti gli errori su singolo bit sono rilevabili. Allo stesso modo, se una codifica e caratterizzata da una distanza di Hamming pari a 3, tutti gli errori su singolo bit e tutti gli errori su doppio bit sarebbero rilevabili. Inoltre si noti che per una codifica con distanza di Hamming pari a 3,
correzione di errori
Per una codifica caratterizzata da una distanza di Hamming pari a 3,questi fatti mostrano che sarebbe possibile anche una correzione dell’errore su singolo bit in quanto il code-word risultante da un errore su singolo bit avrebbe una distanza di Hamming pari ad 1 rispetto ad uno solo dei code-word validi – cioè quello corretto – e almeno pari a 2 rispetto a tutti gli
altri.
Vediamo un esempio per capire meglio queste due conseguenze:
Per il nostro esempio il code ha dimensione k=3 e viene rappresentato con un cubo dove ogni vertice è un code-word. I code-word validi sono colorati in azzurro.
2.La separabilità
Una codifica separabile consiste nel conservare intatta l’informazione
alla quale vengono concatenate le informazioni di controllo. Quindi, l’informazione originale concatenata con le informazioni di controllo aggiuntive forma la code-word. In questo modo, in fase di decodifica, l’unica cosa da fare e eliminare le informazioni di controllo e mantenere solo quelle di interesse. D’altra parte una codifica non separabile non possiede la proprietà della separabilità. Per questo motivo il recupero dell’informazione originale deve essere eseguito mediante una decodifica più complicata.
3.ridondanza
La ridondanza si può definire come il costo aggiuntivo richiesto rispetto ad una codifica minima.
La ridondanza può essere espressa come il rapporto tra il numero
di bit della codifica e il numero di bit strettamente necessario a rappresentare tutte le informazioni codificate. La ridondanza può essere direttamente usata per determinare il costo della codifica. Di solito, una codifica con maggiore
distanza di Hamming, e quindi migliore copertura di errori, ha ridondanza, e quindi costo maggiore.
D’altra parte, il costo della codifica può essere anche limitato dalla semplicità della codifica e decodifica (cioè dal fatto che sia separabile o no).
Formula matematica:
4.la capacità diagnostica
la sua capacita diagnostica è la capacita non solo di rilevare la presenza di un errore (e quindi di un guasto che ha provocato l’errore) ma anche di localizzare il guasto,indicare cioè quale componente e guasto. In generale, per avere capacita diagnostica occorre maggiore ridondanza, e quindi costo maggiore. Inoltre, la capacita diagnostica può essere utilizzata non soltanto per guidare la manutenzione del sistema, ma direttamente per correggere l’errore: se la capacita diagnostica e tale da fornire il vettore di errore,
sommandolo (bit a bit, in modulo 2 - cioè con una batteria di XOR) alla parola errata si ottiene la parola corretta.
Un codice con tale capacita e quindi
un codice correttore di errore.
Tipologie
1.Codici di parità
La codifica più semplice consiste nel controllo della parità. E' un codice per la rilevazione d'errore. Esistono molte variazioni rispetto all’idea che sta alla base
di questa codifica. Esistono due tipi di parità: parità pari e parità dispari:
La codifica di parità viene eseguita aggiungendo al word-code un bit con valore dipendente dal tipo di parità scelta in modo da avere un numero di bit “1” pari o dispari a seconda della parità in uso:
- in una codifica con parità pari, il numero di tutti i bit “1” compreso il bit di parità è pari.Esempio:
- in una codifica a parità dispari, il numero di tutti i bit “1” compreso il bit di parità è dispari.Esempio:
Si noti che, poiché la distanza da un code-word valido e l’altro, in entrambe le tipologie e pari ad 2, questa tecnica e in grado di rilevare gli errori su singolo bit, ma non e in grado di correggerli.
Dato il modo in cui viene costruita la code-word: aggiunta del bit di controllo, la codifica di parità e una codifica separabile.
Un’applicazione comune che utilizza questa tecnica e rappresentata dalle memorie dei computer.
La codifica/decodifica della parola, anche con questa semplice tecnica, comporta un hardware aggiuntivo, inoltre e necessario che la memoria abbia la capacita di contenere il bit aggiuntivo. L’hardware deve essere progettato quindi per la creazione e controllo dell’extra-bit. L’hardware è una batteria di XOR
Si noti pero che il controllo di parità con singolo bit può non rilevare alcuni errori su più bit.
state proposte quindi alcune varianti rispetto all’idea fondamentale, ne vedremo alcune:
Bit-per-word
questa tecnica e stata appena discussa: aggiungere un bit di parità alla parola.
Il principale svantaggio consiste nel fatto che alcuni errori possono non essere rilevabili. Ad esempio un fallimento completo, di un bus
o dei buffer, che porta tutti i bit a 1 può essere rilevato da una parità dispari solo se il numero di bit e pari, lo stesso fallimento viene rilevato da una parità pari solo se il numero di bit della parola, compreso il bit di parità,
e dispari. D’altra parte il fallimento che porta tutti i bit a 0 non può essere mai rilevato dalla parità pari in quanto una parola che vale zero viene considerata con un numero pari di 1. Viceversa questo fallimento viene sempre rilevato dalla parità dispari.
Bit-per-byte
Questa tecnica consiste nell’utilizzare due bit di controllo e suddividere quindi la parola in due byte, un bit controlla un byte, l’altro bit controlla l’altro byte. Sebbene la tecnica si chiami bit-per-byte non e necessario che i gruppi siano esattamente di 8−bit.
Per raggiungere completamente i vantaggi offerti da questa tecnica e necessario che il numero di bit di un gruppo sia pari e che un byte venga controllato con parità pari e l’altro con parità dispari. In questo modo entrambi gli errori con tutti i bit a 0 e a 1 vengono rilevati. Inoltre questa tecnica `e in grado di rilevare tutti gli errori su due bit purché un errore avvenga in un byte e l’altro errore avvenga nell’altro.
Lo svantaggio di entrambe le tecniche: bit-per-word e bit-per-byte consiste nel fatto che gli errori multipli non sono sempre rilevabili. Considerando che i bit che formano una parola sono spesso assegnati a chip separati, , il fallimento di uno dei chip non viene identificato.
Bit-per-multiple-chip
Per risolvere il problema precedente viene utilizzato un numero di bit di parità pari al numero di bit contenuti in un chip. Ciascun bit viene associato ad un solo bit di ciascun chip in questo modo un bit di parità controlla un solo bit di ogni chip. Come si può facilmente notare questa tecnica di parità e in grado di
rilevare gli errori dovuti al fallimento di un intero chip, fallimento denominato come whole-chip failure mode.
Sebbene questa variante della codifica di parità sia in grado rilevare il fallimento di un intero chip non e pero in grado di localizzare il chip danneggiato.
Bit-per-chip
questa variante e stata sviluppata per ovviare al problema appena accennato. Funziona nel modo seguente: ciascun bit di parità viene assegnato ad un singolo chip. In questo modo non solo viene rilevato il fallimento di singolo chip, ma dato che ogni bit di parità e associato ad un unico chip, il fallimento e anche
localizzabile. Lo svantaggio primario e pero lo stesso presentato dalla tecnica bit-per-word. Infatti il semplice controllo di parità su una parola non `
e in grado di rilevare errori su più bit, di conseguenza se all’interno di un
singolo chip si verificano errori multipli, tali fallimenti potrebbero non venire rilevati.
Interlaced
un altro tipo di organizzazione dei bit consiste nella parità interlacciata. E’ simile, in concetto, alla parità bit-per-multiple-chip. La differenza sostanziale consiste nel fatto che questo tipo di parità non tiene conto dell’organizzazione fisica dei bit come accade per la multiple-chip. La parola viene suddivisa in gruppi di uguale lunghezza di bit e i bit di parità vengono organizzati in modo tale che non sia possibile che due bit adiacenti del code-word appartengono allo stesso gruppo. La parità interlacciata e utile, come si può immaginare, per il
rilevamento degli errori sui bit adiacenti, tipici dei collegamenti a bus.
Overlapped parity
L’ultimo tipo di parità che esaminiamo ha come idea di base che un bit appartenga a più di un gruppo di parità. Questo permette, oltre ad una rivelazione degli errori, anche la loro localizzazione in questo
modo, mediante un’operazione di complemento, l’errore può essere corretto.
Il concetto di base di questa tecnica consiste nel porre ciascun bit di parità in modo che controlli una combinazione unica dei bit della parola. Per
comprendere meglio quanto appena detto si osservi la figura in alto. Nella figura sono anche mostrati i bit coinvolti da un fallimento sui bit di parola e di parità. Questo tipo di parità può essere implementata mediante una serie di comparatori e un decoder con una circuiteria di controllo di parità. L’operazione di correzione dell’errore può essere fatta mediante il complemento del bit errato.
Ad esempio, quando una parola viene memorizzata in una cella di memoria vengono costruiti i bit di parità aggiuntivi e memorizzati assieme alla parola. Durante l’operazione di lettura i bit di parità vengono nuovamente generati e confrontati con quelli memorizzati. Il risultato del confronto permette quindi la correzione dell’eventuale errore. Vediamo come funziona: si noti la
tabella mostrata in figura. Tale tabella mostra i bit di parità coinvolti quando si verificano errori sui bit 3, 2,1 ecc..
Ora, si supponga di memorizzare la parola 1101. I bit di parità per questa parola sono i seguenti 100 (parità dispari),per cui la parola complessiva `e 1101100. Si supponga invece di leggere la parola 1001100. Come si può notare
si e verificato un errore sul bit 2. Vediamo come può essere corretto. Come abbiamo detto quando si recupera una parola dalla memoria i bit di parità devono essere nuovamente generati. Stando alla parola letta i nuovi bit
di parità sono i seguenti 010. Il confronto tra i vecchi bit di parità e i nuovi appena calcolati mostra due bit in disaccordo , più precisamente P2 e P1. Dalla tabella in figura la configurazione dei bit affetti riferita alla riga
P2, P1 si recupera il bit che causa questa combinazione – unica – e cioè`e il bit 2, proprio il bit che e effettivamente errato. A questo punto con un’operazione di complemento e possibile recuperare la parola originale. Si noti che,in questo caso, la “spesa” per la copertura su tutti e quattro i bit e molto alta:
3−bit di parità per 4−bit di informazione cioè il 75% di ridondanza in più. Comunque, all’aumentare dei bit di informazione, la percentuale
di ridondanza diminuisce. In particolare e possibile stabilire il legame tra i bit di informazione da proteggere e i bit di parità. Sia d il numero di bit di informazione e r il numero di bit di parità`a. Le combinazioni uniche
che devono essere contemplate sono almeno d + m cioè dobbiamo proteggere d−bit di informazione e r−bit di parità. Inoltre dobbiamo contemplare anche la combinazione in cui non si sia verificato un errore. In definitiva
dobbiamo contemplare almeno d + r + 1 combinazioni uniche. Per cui la relazione tra d ed r e data dalla seguente relazione:
2.codici aritmetici
Le codifiche aritmetiche sono utili quando si rende necessario controllare le operazioni aritmetiche come addizione,moltiplicazione, divisione ecc.. L’idea di fondo e la seguente: gli operandi vengono codificati prima di eseguire su di essi
l’operazione desiderata. Il risultato viene quindi controllato per verificare se il code-word risultante dall’operazione aritmetica `e valido. Se il code-word risultante non e valido significa che si e verificata una condizione di errore. Una
codifica aritmetica deve essere invariante rispetto ad un insieme di operazioni. In particolare una codifica aritmetica
ha la seguente proprietà: A(b * c) = A(b) *A(c) dove b e c rappresenta gli operandi, * rappresenta una delle operazioni per le quali la codifica e invariante e A(x) rappresenta la codifica aritmetica per l’operando x. In altre parole possiamo dire che una codifica aritmetica ha la seguente proprietà: l’operazione aritmetica su operandi codificati produce lo stesso code-word rispetto alla codifica aritmetica del risultato della normale operazione. Per caratterizzare una codifica aritmetica è necessario specificare il metodo di codifica e l’insieme delle operazioni per le quali la codifica e invariante. Ora vediamo qualche codifica aritmetica:
Codifica AN
Questo tipo di codifica consiste nel moltiplicare ciascuna parola dei dati, N, per una costante, A. Questa codifica e invariante alle operazioni di addizione e di sottrazione, ma non alle operazioni di moltiplicazione e divisione. Quindi la verifica che il code-word sia valido viene eseguita dividendo il code-word per A e verificando che sia divisibile quindi per A. La scelta della costante A comporta il numero di extra-bit che verranno utilizzati e la capacita di rilevare gli errori. Quindi la scelta di A `e un’operazione critica. A deve essere scelta in modo tale che non sia 2 elevato alla x. Per capire le ragioni di questa limitazione dobbiamo ricordare che in base binaria la moltiplicazione per 2 elevato alla x si traduce in una operazione di shift aritmetico verso sinistra del numero per
cui il numero an−1, . . . , a0 diventerebbe an−1, . . . , a0, 0, . . . , 0 con esattamente x zero. La rappresentazione decimale
quindi e data da:
Questo numero e divisibile per 2 alla x. Si può notare inoltre che in caso di un’alterazione di uno solo dei coefficienti, il numero rimane comunque divisibile per 2 elevato alla x. Quindi se A è pari a 2 elevato alla x la codifica non e in grado di rilevare gli errori su singolo bit.
Una codifica AN corretta `e la 3N. La codifica 3N comporta, per una parola di n−bit, (n+2)−bit per rappresentare il code-word. L’implementazione della codifica 3N `e relativamente semplice: si utilizza un sommatore per eseguire la somma N + 2N dove la quantità 2N e facilmente ottenibile mediante shift binario verso sinistra di una posizione.
Codifica Residuo
E’ un tipo di codifica separabile che consiste nell’aggiungere al numero da
codificare il residuo. Supposto che il numero da codificare sia N, scelto un modulo m chiamato anche check-base, possiamo scrivere N = Im + r dove I e il quoziente intero tra N e m e r e il resto. Ad esempio supposto di dover
codificare 14 avendo scelto un modulo pari a 3 possiamo scrivere che 14 = 3 * 4 + r da cui r = 2. Il residuo quindi e pari a 2.Il numero di extra-bit necessari con questo tipo di codifica dipende dal modulo scelto, infatti il residuo non e
mai maggiore del modulo: 0 <= r < m. La verifica di correttezza su un risultato e data dal calcolo del residuo del dato da verificare e dal suo confronto con il residuo concatenato con il dato. La codifica con residuo e invariante rispetto
all’addizione. Quindi supposto di avere due numeri D1 e D2, rispettivamente con i residui r1 e r2, la somma verrà creata come S = D1 + D2 con residuo rs = r1 + r2. Durante il controllo quindi si esegue il calcolo del residuo di S e lo si controlla con rs. Se i due residui differiscono significa che si e verificato un errore. I residui vengono addizionati con un sommatore modulo−m. Il vantaggio primario di questa codifica consiste nel fatto che e separabile. Se il valore del
modulo per il calcolo del residuo viene scelto in un modo particolare la codifica prende il nome di low-cost residue.
In particolare scegliendo
il numero di extra-bit per la codifica low-cost e pari a b. Il vantaggio
primario di questa tecnica consiste nel fatto che il procedimento di codifica viene semplificato. Si ricordi infatti che per eseguire una codifica con residue dobbiamo calcolare un resto e quindi dobbiamo eseguire una divisione. La
codifica low-cost permette di sostituire l’operazione di divisione con un’operazione di addizione. I bit dell’informazione vengono prima suddivisi in gruppi di b−bit, ciascun gruppo quindi viene addizionato all’altro mediante un addizione modulo
Il risultato di questa operazione rappresenta il residue dell’informazione.
Codici ciclici
La caratteristica dei codici ciclici e data dal fatto che lo shift con riporto di un code-word genera sempre un altro code-word. Un codice ciclico e univocamente, e completamente, identificato dal suo polinomio generatore
G(X) che e un polinomio di grado (n−k) o superiore dove n rappresenta il numero di bit complessivo cioè bit di informazione più bit di controllo – e k e il numero di bit di cui e formata l’informazione originale. Un codice ciclico con polinomio generatore di grado (n−k) viene chiamato codice (n−k) e (n−k) rappresenta la sua caratteristica. Un codice di questo tipo e in
grado di rilevare errori sui singoli bit e tutti gli errori multipli e adiacenti con lunghezza non superiore a (n − k)−bit.
Supponendo che un code-word sia formato da n−bit possiamo affermare che ogni code-word e rappresentato da un polinomio V (X). Supposto di avere un code-word del tipo v = v0, . . . , vn−1, il polinomio che lo rappresenta e dato da
Quindi, ogni code-word e rappresentato da un polinomio di grado n−1 o inferiore chiamato code-polynomial. Quindi, dato il polinomio dei dati D(X), ad esempio per la parola di 4−bit 1101 il polinomio dei dati e
,il code-polynomial viene composto moltiplicando il polinomio dei dati con il polinomio generatore (che abbiamo già introdotto), per cui V (X) = D(X)G(X). Si osservi pero che ogni addizione richiesta durante la moltiplicazione
dei due polinomi deve essere eseguita in modulo 2.
Ad esempio, supposto di avere un polinomio generatore pari a
, il polinomio di codifica e quindi
,
o meglio V (X) =
In questo modo il code-word e dato dai coefficienti del code-polynomial,
e in questo caso abbiamo v = 1010001.
Vediamo come valutare se il code-word ricevuto sia valido o meno. Si supponga di aver ricevuto il code-word r = r0, . . . , rn−1, il polinomio del codice e R(X). Poiché il polinomio R(X) e stato ottenuto moltiplicando il polinomio dei dati per il polinomio generatore possiamo scrivere che R(X) = D(X)G(X) + S(X), dove
S(X), dovrebbe essere nullo se R(X) e un multiplo del polinomio generatore, cioè se R(X) `e un code-word valido. Un metodo per verificare se R(X) sia un code-word valido consiste nel dividere R(X) per G(X) e controllare che il resto della divisione sia zero. In questo caso R(X) e un codice valido. Il polinomio
S(X) viene chiamato syndrome polynomial.
Lo svantaggio primario dei codici ciclici `e rappresentato dal fatto che non sono
separabili.
Applicazione
Esercizi presi sul
sito del Professore Alessandro Fantechi
Soluzione
Grazie per l’attenzione
Benvenuto caro Lettore!
UF è un blog di ingegneria informatica pieno di articoli più o menoo tecnici. Iscriviti per rimanere aggiornato all'uscità dei prossimi articoli.