Tecniche di progettazione Fault Tolerant
Per il progetto di circuiti in grado di rilevare/correggere
errori causati dai guasti si fa uso della ridondanza.
La ridondanza può essere di diversi tipi:
Ridondanza Hardware: si aggiungono dei blocchi logici in
grado di rilevare e/o correggere gli errori
Ridondanza delle informazioni: si aggiungono delle
informazioni che non sono necessarie durante il
funzionamento del sistema ma che sono utili per recuperare
a partire da informazioni errate le informazioni corrette.
Ridondanza temporale: nel caso sia stato rilevato un errore
le operazioni possono essere ripetute
1
Ridondanza Hardware: sistemi TMR
Un sistema TMR (Triple
Modular Redundancy)
consente di mascherare
l'effetto di un guasto
M
M
L'overhead di un sistema
TMR è > 200%
V
M
1
.0
N
R
(
t
)
1

[
1

R
(
t
)]

p
i

1
i
S
im
p
le
x
T
M
R
0
.8
0
.7
R
e
lia
b
ility
L'affidabilità del sistema
dipende dal Voter. Se Rv=1
0
.9
0
.6
0
.5
S
im
p
le
x
0
.4
t
0
.3
R
(t)=
e
S
im
p
le
x
0
.2
2
t
3
t
R
(t)=
3
e
-2
e
T
M
R
0
.1
T
M
R
0
.0
0
1
2
3
t
4
5
2
Ridondanza Hardware: sistemi TMR
Se non posso trascurare
l'affidabilità del voter posso
utilizzare un sistema con 3
Voter
Possono essere
utilizzati in cascata
M
V
M
V
M
V
M1
V
M2
V
M1
V
M2
V
M1
V
M2
V
la funzione logica di un voter
è: f=ab+ac+bc
3
On-line testing
Per rilevare il corretto
funzionamento di un
circuito durante il suo
funzionamento posso
utilizzare 2 moduli identici
ed un comparatore
oppure
Posso utilizzare una
struttura detta selfchecking
output
M
C
Good/Fail
M
Encoded
input
Encoded output
M
Checke
r
Error Indicator
4
Totally self-checking circuits
Un circuito è detto TSC (Totally Self-Checking) se:
È Fault secure: per ogni codeword in ingresso ogni guasto
produce in uscita una parola non di codice, o non produce
errori
È Self-testing: per ogni guasto esiste almeno una parola di
codice in ingresso che produce in uscita una parola non di
codice. (consente di l'ipotesi di guasto singolo)
Il checker:
Determina se la parola al suo ingresso è una parola di
codice
Rileva i guasti al suo interno
5
Two-rail checker
Un checker two-rail controlla se i sui ingressi X=xn..x0 e
Y=yn..y0 sono tali che xi =not(yi)
il checker two-rail è fault-secure
ed è self-testing
f
0
0
1
1
fd
0
1
0
1
errore
OK
OK
errore
6
Ridondanza delle informazioni:
codici a rilevazione/correzione di errore
Un codice binario C di lunghezza n è un insieme di n bit
che soddisfa alcune regole
Una Codeword è un elemento dell'insieme (soddisfa le
regole del codice)
Una word è una n-pla che non fa parte del codice
Le codeword sono un sottoinsieme di tutte le 2n possibili
combinazioni.
IL numero di parole appartenenti al codice C è detto size
di C
7
Codici a rilevazione di errore: il codice di parità
Il codice di parità aggiunge un bit di informazione:
Per i codici a parità odd: il numero di 1 della codeword è
dispari
Per i codici a parità even: il numero di 1 della codeword è
pari
Rileva un bit errato in qualunque posizione della codeword
Può essere utilizzato nelle memorie:
8
Generazione e controllo del codice di parità
Generazione
Controllo
9
Codici a correzione di errore: il codice di Hamming
Il codice di Hamming permette di correggere un bit errato
nella codeword
Puo essere realizzato come la sovrapposizione di diversi
codici di parità
P2
P1
P0 Errato
0
0
0
1
0
1
1
1
0
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
OK
P0
P1
P2
D0
D1
D2
D3
10