Codici binari nel progetto dei sistemi affidabili.

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 lunguezza 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 Hammig 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 azzuro.

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 proprieta della separabilita. Per questo motivo il recupero dell’informazione originale deve essere eseguito mediante una decodifica piu complicata.

3.ridondanza

La ridondanza si puo definire come il costo aggiuntivo richiesto rispetto ad una codifica minima.

La ridondanza puo 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 puo 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 puo essere anche limitato dalla semplicita 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 cioe quale componente e guasto. In generale, per avere capacita diagnostica occorre maggiore ridondanza, e quindi costo maggiore. Inoltre, la capacita diagnostica puo 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 – cioe 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 piu semplice consiste nel controllo della parita. 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 pairta: parita pari e parita dispari:

La codifica di parita viene eseguita aggiungendo al word-code un bit con valore dipendente dal tipo di parita scelta in modo da avere un numero di bit “1” pari o dispari a seconda della parita in uso:

- in una codifica con parita pari, il numero di tutti i bit “1” compreso il bit di parita è pari.Esempio:

- in una codifica a parita dispari, il numero di tutti i bit “1” compreso il bit di parita è dispari.Esempio:

Si noti che, poiche 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 parita  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 parita con singolo bit puo non rilevare alcuni errori su piu 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 parita 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 puo essere rilevato da una parita dispari solo se il numero di bit e pari, lo stesso fallimento viene rilevato da una parita pari solo se il numero di bit della parola, compreso il bit di parita,
e dispari. D’altra parte il fallimento che porta tutti i bit a 0 non puo essere mai rilevato dalla parita pari in quanto una parola che vale zero viene considerata con un numero pari di 1. Viceversa questo fallimento viene sempre rilevato dalla parita 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 parita pari e l’altro con parita 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 purche 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 identficiato.

Bit-per-multiple-chip

Per risolvere il problema precedente viene utilizzato un numero di bit di parita 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 parita controlla un solo bit di ogni chip. Come si puo facilmente notare questa tecnica di parita 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 parita 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 parita viene assegnato ad un singolo chip. In questo modo non solo viene rilevato il fallimento di singolo chip, ma dato che ogni bit di parita 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 pairta su una parola non `

e in grado di rilevare errori su piu 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 parita interlacciata. E’ simile, in concetto, alla parita bit-per-multiple-chip. La differenza sostanziale consiste nel fatto che questo tipo di parita 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 parita vengono organizzati in modo tale che non sia possibile che due bit adiacenti del code-word appartengono allo stesso gruppo. La parita interlacciata e utile, come si puo immaginare, per il
rilevamento degli errori sui bit adiacenti, tipici dei collegamenti a bus.

Overlapped parity

L’ultimo tipo di parita che esaminiamo ha come idea di base che un bit appartenga a piu di un gruppo di parita. Questo permette, oltre ad una rivelazione degli errori, anche la loro localizzazione in questo
modo, mediante un’operazione di complemento, l’errore puo essere corretto.

Il concetto di base di questa tecnica consiste nel porre ciascun bit di parita 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 parita. Questo tipo di parita puo essere implementata mediante una serie di comparatori e un decoder con una circuiteria di controllo di parita. L’operazione di correzione dell’errore puo 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 parita vengono nuovamente generati e confrontati con quelli memroizzati. 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 parita coinvolti quando si verificano errori sui bit 3, 2,1 ecc.

Ora, si supponga di memorizzare la parola 1101. I bit di parita per questa parola sono i seguenti 100 (parita dispari),per cui la parola complessiva `e 1101100. Si supponga invece di leggere la parola 1001100. Come si puo notare
si e verifcato un errore sul bit 2. Vediamo come puo essere corretto. Come abbiamo detto quando si recupera una parola dalla memoria i bit di parita devono essere nuovamente generati. Stando alla parola letta i nuovi bit
di parita sono i seguenti 010. Il confronto tra i vecchi bit di parita e i nuovi appena calcolati mostra due bit in disaccordo , piu 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 parita per 4−bit di informazione cioe il 75% di ridondanza in più. Comunque, all’aumentare dei bit di informazione, la percentuale
di ridondnaza diminuisce. In particolare e possibile stabilire il legame tra i bit di informazione da proteggere e i bit di parita. 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 cioe dobbiamo proteggere d−bit di informazione e r−bit di parita. 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 proprieta: 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 proprieta: 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 cdifica 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 puo 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 adder per eseguire la somma N + 2N dove la quantita 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 verra 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 adder 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 piu 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 gia 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). Poiche 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, cioe 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 Proffessore Alessandoro Fantechi

Soluzione

Grazie per l’attenzione