Codici a controllo dell`errore per le memorie

Elettronica dei Sistemi Digitali
Corso di Laurea in Informatica
Crema, 23 Maggio 2001
Codici a controllo dell’errore
per le memorie
Stefano Gregori
Laboratorio di Microsistemi Integrati
Dipartimento di Elettronica
Università di Pavia
Via Ferrata, 1
27100 Pavia
E-mail: [email protected]
Stefano Gregori
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
1
Argomenti
introduzione
rivelazione e correzione degli errori
la probabilità d’errore
i codici a controllo dell’errore per le memorie a
semiconduttore
i codici a controllo dell’errore per le memorie ML
Stefano Gregori
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
2
Sistemi di comunicazione elettrica
sorgente
canale
utilizzatore
trasmettitore
linea
ricevitore
trasmissione
C
C
ingresso
calcolo
uscita
scrittura
conservazione
lettura
elaborazione
memorizzazione
Stefano Gregori
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
3
Errori nel funzionamento delle reti
TEMPORANEI
ALTERAZIONE
DELLE CONDIZIONI
DI FUNZIONAMENTO
cadute o oscillazioni della
tensione di alimentazione
disturbi elettromagnetici
vibrazioni
radiazioni (particelle α,
raggi cosmici)
rumore elettromagnetico
Stefano Gregori
PERMANENTI
GUASTI
difetti di isolamento tra
conduttori
interruzioni di
collegamenti
alterazione delle variabili
di stato di reti sequenziali
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
4
Rivelazione degli errori
DUPLICAZIONE DI UNA UNITÀ
x1
xn
z1
zm
U
U'
z'1
confronto
E
z'm
E=
Stefano Gregori
m
zi ⊕ z' i
Σ
i =1
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
5
Rivelazione degli errori
CODICE A CONTROLLO DI PARITÀ IN RETI COMBINATORIE
x1
xn
z1
zm
C
controllo di parità
generatore
di parità
Stefano Gregori
controllo
di parità
p
E
u1
u2
u3
u4
u5
u6
u7
u8
E
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
6
Rivelazione degli errori
CODICE A CONTROLLO DI PARITÀ IN RETI SEQUENZIALI
x1
xn
y1
yk
C
generatore
di parità
z1
zm
y'1
y'k
pz
controllo
di parità
Ez
controllo
di parità
Ey
py
Stefano Gregori
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
7
Correzione degli errori
TRIPLICAZIONE DELLA RETE
x1
xn
R1
blocco maggioritario
R2
M
z
u1
M
um
R3
M(u1, ...,um ) =
k=
Stefano Gregori
m +1
2
M(u1, …, um)
Σ
i j =1, ...,m
ui1 ... uik
i1 ≠...≠ i k
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
8
Correzione degli errori
CONTROLLI DI PARITÀ
z1
x1
xn
C
zm
z1
zm
correzione
dell'errore
uscite
corrette
generatore
di bit di
controllo
c1
controlli
di parità
posizione
dell'errore
ck
Stefano Gregori
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
9
Correzione del singolo errore
CONTROLLO DI
PARITÀ A MATRICE
c3
i
bit di informazione k = h ⋅ i
bit di controllo
m=h+i
bit totali
n=k+m
h
CODICI DI
HAMMING
c2 c1
c3
c2
c1
(n,k) = (7,4)
n = 2m − 1
k = 2m − 1 − m
il numero di bit di controllo richiesti è il
minimo intero m tale che
il minimo numero di bit di controllo si
ha quando h = i, in questo caso si ha
m = 2h = 2 k
questo metodo corregge 1 errore
e rivela 1 o 2 errori
Stefano Gregori
m = log2 (k + m + 1)
questo metodo rivela e corregge
1 errore
il metodo può essere esteso per
rivelare anche 2 errori, in questo caso
m = 1 + log2 (k + m )
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
10
Probabilità d'errore
funzioni cumulative dell'errore
unità singola
 1 − exp( −εt ) se t ≥ 0
P1(t ) = 
altrimenti
0
unità triplicata e blocco maggioritario
 1 − 3 exp( −2εt ) + 2 exp( −3εt ) se t ≥ 0
P2 (t ) = 
altrimenti
0
unità quintuplicata e blocco maggioritario
 1 − 10 exp( −3εt ) + 15 exp( −4εt ) − 6 exp( −5εt )
P3 (t ) = 
 0 se t < 0
t = tempo
ε = tasso d'errore del circuito
ln 2
P1 > Pi (i = 2, 3, …) se t <
ε
Stefano Gregori
[× 1/ε]
caso generale con k > n / 2
P (t ) =
n
n
n −i
i
 (P1(t )) (1 − P1(t ))
i =k  i 
Σ
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
11
Probabilità d'errore
La probabilità di errore di i bit su n (compresi i bit di parità) sul periodo t, si può approssimare con una
legge di Poisson (ε è il tasso di guasto sul singolo bit)
 (εnt )i exp( −εnt )

se t ≥ 0
Pi (t ) = 
i!
 0
altrimenti
La funzione cumulativa dell'errore al
tempo t è data da
E1(t ) = 1 − P0 (t )
e corrisponde alla probabilità di errore
sulla parola quando non è effettuata la
correzione.
Con la correzione di 1 e di 2 errori
questa probabilità si riduce
rispettivamente a
E2 (t ) = 1 − P0 (t ) − P1(t )
E3 (t ) = 1 − P0 (t ) − P1(t ) − P2 (t )
Stefano Gregori
[× 1/ε]
i valori usati per n nel grafico sono n1 = 64, n2 = 71, n3 = 78;
per la triplicazione la probabilità di lettura errata è data dalla
seguente espressione in cui il numero di celle è n4 = 64,
mentre per P0 e P1 è n = 3
E4 (t ) = 1 − (P0 (t ) − P1(t ))n4
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
12
Probabilità d'errore
posta la probabilità d'errore della
singola cella pari a p, il grafico
mostra la come varia la probabilità
di lettura errata al variare di p e
della tecnica di correzione scelta
1 con parole da k cifre, la
probabilità di lettura errata PLE è
PLE = 1 − (1 − p)k = O(kp)
2 con un codice che corregge 1 errore
per parola
 n(n − 1) 2 
PLE = 1 − (1 − p)n − n p (1 − p)n −1 = O
p 

 2
3 con un codice che corregge 2 errori
per parola
PLE
 n(n 2 − 3n + 1) 3 
= O
p 


6


Stefano Gregori
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
13
Errori nelle memorie
SOFT
HARD
è un cambiamento dello stato
della cella che sia
casuale
non ripetitivo
di un numero ridotto di celle
per volta
non permanente o almeno
recuperabile nel successivo
ciclo di scrittura
è associato a un difetto
permanente esistente nel
dispositivo o creatosi durante
il suo funzionamento per
incapacità dei materiali di
sopportare gli stress applicati
le tecniche di controllo dell'errore permettono di ridurre efficacemente gli effetti
degli errori soft e risultano utili anche per il recupero di alcuni errori hard
Stefano Gregori
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
14
ECC per le memorie
CARATTERISTICHE
velocità nelle operazioni di codifica e di
decodifica per peggiorare il meno possibile il
tempo d'accesso
strutture di codifica e
decodifica parallele (a
matrice)
ridotta area aggiuntiva dovuta alle celle di buona progettazione del
controllo e ai circuiti di codifica e di decodifica codice e dei circuiti
capacità di correggere qualsiasi errore sulla
singola cella e su celle adiacenti
utilizzo di codici Q-ari
per celle multilivello e
spaziatura delle celle
esempi di
distribuzioni
di errori soft
dmax
Stefano Gregori
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
15
ECC per le memorie
METODI PIÙ
UTILIZZATI
SEC (single-error-correcting) codici di Hamming
SEC-DED (single-error-correcting double-errordetecting) codici odd-weight-column di Hsiao
SEC-DED-SBD (single-error-correcting doubleerror-detecting single-byte-error-detecting) codici
di Reddy
SBC-DBD (single-byte-error-correcting doublebyte-error-detecting) codici basati sulla teoria dei
campi finiti
DEC-TED (double-error-correcting triple-errordetecting) codici di Bose-ChaudhuriHocquenghem
Stefano Gregori
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
16
ECC per le memorie
PERMETTONO DI RIDURRE LA
PROBABILITÀ D'ERRORE CON
L’AGGIUNTA DI RIDONDANZA
informazione
ridondanza
k
n–k
codifica: ogni k cifre di
informazione, sono aggiunte n – k
cifre di controllo
decodifica: grazie alle cifre di
controllo, sono individuati e corretti
gli errori intervenuti su tutte le n cifre
il numero massimo di errori
correggibili dipende dalla ridondanza
del codice
CODICI BINARI
CODICI NON BINARI
sono i codici più diffusi
operano su cifre binarie
la loro descrizione matematica si
basa sull'algebra del campo finito a
due elementi GF(2)
possono essere utilizzati quando
l’unità "base" di informazione non è
una cifra binaria, ma una cifra in
base Q
la descrizione matematica si basa
sull’algebra dei campi finito a Q
elementi GF(Q)
Stefano Gregori
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
17
Errori di una cella multilivello
righe
SCRITTURA
11 = 3
colonne
ogni cella di memoria a Q = 2b livelli può memorizzare
un simbolo Q-ario equivalente a b bit di informazione
simboli quaternari
0 = 00
1 = 01
2 = 10
3 = 11
LETTURA
0 = 00
cella guasta
l'errore di una cella corrisponde all'errore dei b bit a essa associati
Stefano Gregori
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
18
Circuiti per le operazioni non binarie
corrispondenza tra
simboli quaternari
e simboli binari
simbolo
quaternario
addizione tra due
simboli quaternari
Stefano Gregori
0 = 00
1 = 01
2 = 10
3 = 11
bit alto
bit basso
tabelle di addizione e moltiplicazione
nel campo finito di 4 elementi
+
0
1
2
3
·
0
1
2
3
0
0
1
2
3
0
0
0
0
0
1
1
0
3
2
1
0
1
2
3
2
2
3
0
1
2
0
2
3
1
3
3
2
1
0
3
0
3
1
2
moltiplicazione per 2
moltiplicazione per 3
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
19
Descrizione algebrica dei codici lineari
Codifica
il processo di codifica può essere descritto in forma vettoriale dall'equazione
c = i·G
la matrice G di k righe e n colonne definisce il codice ed è chiamata matrice generatrice
Decodifica e correzione dell’errore
si definisce la matrice di controllo di parità H in modo che per ogni parola di codice c
c·Ht = 0
si definisce sindrome della parola r il vettore s di lunghezza (n – k) tale che
s = r·Ht = c·Ht + e·Ht = e·Ht
dalla sindrome è possibile risalire al valore del vettore d’errore e* più probabile
la correzione può allora essere effettuata con la seguente operazione
c* = r – e*
la matrice H e la matrice G sono legate dalla seguente espressione
G·Ht = 0
le operazioni di addizione e moltiplicazione vanno effettuate nel campo degli elementi
finiti a Q elementi
Stefano Gregori
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
20
Percorso dell’informazione
ERRORI
parola di informazione
k
codificatore
k bit o k cifre
k
parola stimata
Stefano Gregori
scrittura di n celle
parola di codice
n
circuiti di
scrittura
matrice di
memoria
n bit o n cifre
decodificatore
n
parola letta
circuiti di
lettura
lettura di n celle
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
21
Blocco per il controllo dell’errore
DW
DW
CW
generatore
dei simboli
di controllo
DR
ai circuiti di
scrittura
CW
CR
DW
DR
CW
CR
S
E
DE
S
valutazione
della
sindrome
E
DE
ai buffer
d’uscita
= parola di informazione da scrivere
DR
= parola di informazione letta dalla memoria
= simboli di controllo calcolati per essere scritti in memoria
= simboli di controllo letti dalla memoria
= sindrome
= vettore d’errore
= parola di informazione stimata fornita in uscita
Stefano Gregori
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
22
Generatore dei simboli di controllo
parola di informazione
ik−1
i1
i0
Stefano Gregori
simboli di controllo
cn−k−1
c0
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
23
Valutazione della sindrome
sindrome
sn−k−1
s1
s0
vettore d’errore
e0
Stefano Gregori
en
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
24
Esempio di ECC per memorie ML
Codice quaternario (36,32)
100000011100000001111111110000111111 
H = 010001100100111110000011231111000011
001010101011001230012301001123112300

(matrice del
000111010023231002310010002311231123
controllo di parità) 
Il codice è stato ottenuto abbreviando il codice di Hamming quaternario (85,81).
Allo scopo di minimizzare le dimensioni dei circuiti di codifica e decodifica è
stata determinata la matrice H con il minor numero di simboli 2 e 3 ed il
massimo numero di simboli 0.
Alcune caratteristiche:
overhead di area 12.5 %
stimata una probabilità d'errore per la singola cella di 10−7, la probabilità di
lettura errata (PLE) passa da 3.2·10−6 a 6.3·10−12
porte logiche dei circuiti di codifica e decodifica 1200 gate equivalenti
tempo di generazione dei simboli di controllo 5 ns
tempo di valutazione della sindrome 10 ns
Stefano Gregori
Codici a controllo dell’errore per le memorie
Crema, 23-5-2001
25