Testarea sistemelor de calcul

Universitatea Politehnica Bucuresti

Facultatea de automatica si calculatoare

Testarea sistemelor de calcul

Se considera circuitul din figura 1

Figura

Sa se calculeze un set complet de teste pentru defectul G1 b-l-1. Utilizati pentru calculul testului atat un algoritm deterministic cat si diferenta Bool-eana. Comparati rezultatele obtinute. Determinati toate celelalte defecte detectate prin testul calculat.

Folosind algoritmul determinist:

problemele initiale sunt :

Justify(G1,0) si Propagate(G1,D')

Justify(G1,0) implica a & b =0 deci (a,b)I

Propagate(G1,D') implica Justify(G2,0) si Propagate(G4,D'

Justify(G2,0) implica : e=0 si c,d sau e=1 si (c,d)I

Propagate(G4,D' 0)= Propagate(G4,D' ) implica Justify(g,1)

Justify(g,1) implica f=0

Deci setul complet de teste este:

(a,b,c,d,e,f)=

Folosind diferenta booleana

Avem ca:

Deci ecuatia circuitului este:

Avem urmatoarele notatii :

x=(a,b,c,d,e,) si y=y(x)=a*b

Deoarece blocajul se afla pe o linie interioara avem :

(1.1)

Dar :

(1.2)

Z1    Z2

Introducand relatia (1.2) in relatia (1.1) obtinem :

    (1.3)

(1.4)

(1.5)

Introducand (1.4) si (1.5) in (1.3) obtinem ca:

de unde rezulta ca

Defectul va fi sesizat daca functia de mai sus ia valoarea 1 adica

Obtinem urmatoarele valoari

si (a,b)I si )}

Se observa ca cele 2 seturi de defecte sunt identice.

Testul calculat mai detecteaza si urmatoarele defecte :

G2 b-l-0

g b-l-1

G5 b-l-0

G5 b-l-1

Sa se alcatuiasca tabela de adevar pentru functia SAU-Ex cu doua linii de intrare si 5 valori logice compozite: 0,1,x,D,D'.

Pentru calculul tabelei de adevar vom folosi urmatoarea regula:

a/b c/d = (ab)/ (cd)

Considerati o poarta logica a carei D_fr.ontiera contine atit valori D cit si valori D'. Apreciati aceasta situatie.

O poarta logica care contine ca intrari atat D cat si D' nu poate fi o D-frontiera deoarce D D' (unde este opperatia efectuata de poarta logica) va lua tot timpul o valoare de forma 0 sau 1.Deci la iesire tot timpul va exista o valoare de 0 sau de 1 indiferent de celelalte intrari

Calculati probabilitatile liniilor circuitului din figura 1.

Notam probabilitatile liniilor primare de intrare astfel:

Pentru poarta SI - G1:

Pentru poarta SAU - G5:

Pentru circuitul inversor g:

Pentru poarta SI - G2:

Pentru poarta SAU - G4:

Pentru LPE - Z:

Se considera un circuit combinational fara linii ramificate avand L nivele si compus in exclusivitate din porti SI-NU. Fiecare poarta are n linii de intrare. Toate liniile de intrare primare au probabilitatea . Din ratiuni de simetrie toate semnalele de pe nivelul l au aceeasi probabilitate . Se cere:

(a) Sa se demonstreze relatia .

(b) Sa se arate ca probabilitatea cea mai mica de detectie a unui defect

este data de relatia:

unde , iar produsul este iterat dupa nivelul k (k luand valori intre 0 si L-1).

(c) Pentru cazul particular L=2 iar n=2, determinati valoarea care

maximizeaza .

a)O poarta SI-NU :

p=p_a*p_b

p_z=1-p T p_z=1- p_a*p_b

Deci pentru o poarta SI-NU cu n intrari : a1,a2, . . an

Avem ca p=1-p_a1*p_a2 . ..*p_an

Pt problema noastra avem p_a1=p_a2= . . =p_an=p₀

Deci p₁=1-p₀ⁿ, p₂=1-p₁ⁿ , . . , p_L=1-p_L-1ⁿ

b) Este suficient sa demonstam ca probabilitatea cea mai mica de detectie a unui blocaj ce apare pe o poarta SI-NU cu n intrari fiecare avand o probabilitate p₀ este data de fornula

d_min=min(p₀,1-p₀)*p₀^n-1

Fie o poarta logica SI-NU cu iesirea Z.Daca Z b-l-1 atunci toate intrarile trebuie sa fie pe 1 pt nu detecta eroarea,deci daca o intrare nu e pe 1 se va detecta eroarea.

Daca Z b-l-0 e suficient ca o intarre sa fie pe 0 ca sa nu se detecteze eroare

Cum toate intarile au aceasi probabilitate avem formula de mai sus.

c) d=min(p₀,1-p₀)*p₀*p₁

p₁=1-p₀² deci d= min(p₀,1-p₀)*p₀*(1-p₀²)

Pt p₀=1/2 avem ca d_max=3/16

Fie Z linia de iesire a unei porti ale carei linii de intrare X si Y, au proprietatea ca sunt disjuncte. Sa se demonstreze ca .

Deoarece X si Y sunt disjuncte, nu pot avea simultan aceeassi valoare, evenimentele X=1 si Y=1 sunt independente probabilistic;

putem scrie:

sau:

Se considera un circuit combinational C implementand functia f si avand linia primara de iesire(unica) Z. Se presupune ca functia acestui circuit se poate exprima printr-o suma de k mintermi, de forma: ,

Sa se arate ca:

(a)  Daca , atunci ,

(b)  Pentru circuitul din figura 2 se cere calculul probabilitatilor

(c)   Fie . Trasati functia

Figura

a)Deoarece functia f este exprimata ca o suma de k mintermeni ,ea ar putea fi definit ca o poarta SAU cu k intrari ,unde fiecare intrare este un mintermen.Deci daca o singura intare este pe 1 atunci functia va avea valoarea 1.De aici rezulta ca probabilitatea functiei sa ia valoarea 1 este suma probabilitatilor mintermenilor ca acestia sa ia valoarea 1.

b) Z=G3+G1=

Deoarece Z este o suma de mintermeni atunci aplicand formula de la punctul a) obtinem

P_Z=p_a*( 1-p_b)*(1- p_c)+ p_b* p_c

c) p_a= p_b= p_c=q avem ca P_Z=q*(q²-q+1)

Se considera circuitul din figura 4. Se cere:

Calculul unui set minimal acoperitor de defecte;

Pentru defectul B b-l-0 determinarea unui set complet de teste utilizand algoritmul diferentei Boole-ene.

Figura 4

Z=G3+G4=G2*A+G2*C=A*(D+A*B*C)+C*(D+A*B*C)=A*D+C*D+A*B*C

Pentru a detecta defectul B b-l-0 trebuie ca

e unde obtinem A=1;B=1;C=1;D=0;