Circuite combinaionale Comparatoare binare de mrime, Sumatoare binare.

Comparatoare binare de mrime (Magnitude comparator).

Definiie: comparatoarele binare de mrime sunt cicuite logice combinaionale care realizeaz comparaia valorilor absolute a dou numere X si Y.

In figura urmtoare este ilustrat schema bloc a circuitului:

X (n biti)

0a A1eE

0bB

Y (n biti)

Figura 1

a,e,b - se numesc intrri de transport de informaie;A,E,B - se numesc ieiri de transport de informaie;X,Y - se numesc valori proprii ale comparatorului.

Comparaia valorilor este un proces care propag informaia de la stnga la dreapta (MSB la LSB). Cei trei bii de transport {a,e,b} au prioritate n deteminarea ieirilor {A,E,B}.

Din cele 8 combinaii numai 3 sunt permise conform tabelei de adevr :

a

e

b

A

E

B

Semnificaie

prioritate

1

0

0

1

0

0

Canal X>Y

valorile proprii decid

0

1

0

0

1

0

Egalitate dac X = Y

prioritate

0

0

1

0

0

1

Canal Y > X

0

0

0

0

0

0

0

1

1

0

1

1

Aceste combinaii sunt

funcionare eronat

1

1

0

1

1

0

interzise !

1

0

1

1

0

1

1

1

1

1

1

1

Pentru comparatorul din Figura 1 intrrile a = 0, e = 1 i b = 0, deoarece condiia logic trebuie s exprime egalitatea.

b) Conectarea n cascad a comparatoarelor

Presupunem c Xk i Yk sunt numere de 8 bii. S se proiecteze un comparator pe 32 de bii, ilustrat n Figura 2.

x31..24x23..16x15..08x07..00

a

e

b

Comp.

BYTE 3

Aa

e b

Comp.

BYTE 2

A a

e b

Comp.

BYTE 1

Aa

e b

Comp.

BYTE 0

A

E

y31..24y23..16y15..08y07..00

Figura 2

c) Proiectarea logic a comparatoarelor binare.

Pentru compararea valorilor proprii X cu Y, se vor defini urmtoarele funcii logice intermediare : = 1, dac X > YA = a + e *

= 1, dac X = YE = e * = 1, dac X < YB = b + e * Se observ c dac se compar numere de cte n bii atunci egalitatea = 1 (X = Y)

are loc pentru 2n cazuri, = 1 (X > Y), respectiv = 1 (Y >X) n cte (22n-1 - 2n-1) cazuri, din totalul de 22n combinaii binare.

Funciile A i B se prelucreaz pe 2 nivele de prelucrare ;

Funcia E se prelucreaz pe un singur nivel.

Proiectarea logic a funciilor intermediare , , pentru comparatoare de 1 bit, 2 bii i 3 bii

1) Comparatorul pe 1 bit.

y0

0

1

y00

1

y0

0

1

x0

x0

x0

0

0

0

0

1

0

0

0

1

1

1

0

1

0

1

1

0

0

= x0 *y0

= x0 *y0+x0* y0

=x0 * y0

Diagramele Karnaugh ale comparatorului pe 1 bit

2) Comparatorul pe 2 bii

y1y0

y1y0

y1y0

1 1

0 00 11 11 0

0 00 11 11 0

0 00 1

1 0x1x0

x1x0

x1x0

0 0

0 01

0 0

1110 11

0 1

1

0 1

111 111

11 1

1

1 1

1 011

1 0

11 0

1

Diagramele Karnaugh ale comparatorului pe 2 bii

= x0 * y1 * y0 + x1 * y1 + x1 * x0 * y0

= x1 * x0 * y1 * y0 + x1 * x0 * y1 * y0 + x1 * x0 * y1 * y0 + x1 * x0 * y1 * y0 = (x0 y0) + (x1 y1)= y0 * x1 * x0 + y1 * x1 + y1 * y0 * x0

= 1 n ase puncte (termeni canonici), dar n urma minimizrii rezult urmtorii trei termeni ilustrai n tabela urmtoare :

Termenulx1x0y1y0minxRelatiemaxy

x0 *

y1 * y0-10001 = 1>00 = 0

x1 *y11-0-10 = 2>01 = 1

x1 * x0 * y011-011 = 3>10 = 2

Analizm termenii funciei din tabel n modul urmtor :

Pentru numrul X s-au presupus valorile (dont care) la valoarea binar 0, rezultnd valoarea zecimal minim pe care o poate avea conform combinaiei binare a lui X;

Pentru numrul Y s-au presupus valorile (dont care) la valoarea binar 1, rezultnd valoarea zecimal maxim pe care o poate avea, conform combinaiei binare a lui Y.

In concluzie, condiia logic se poate exprima n limbaj natural , acoperind toate cazurile, ca:a = (minx 1 > maxy 0) + (minx 2 > maxy 1) + (minx 3 > maxy 2)

Note : 1. Funcia se obine prin permutarea biilor xi i yi;

2. Funcia impune egalitatea xi = yi, care se poate exprima: e = (x1 y1) + (x0 y0).

3) Comparatorul pe 3 bii

y2y1y0000001011010110111101100

x2x1x0

000

0

001

1

1

011

11

1

3

010

11

2

110

1111

116

111

11111

117

101

1111

15

100

1111

4

01326754

Diagrama Karnaugh a funciei 3 a comparatorului pe 3 bii

Se menioneaz c 3 = 1 n 28 puncte (termeni canonici), dar n urma minimizrii rezult urmtorii apte termeni din tabela urmtoare:

Termenulx2x1x0y2y1y0minxRelaiemaxy

x0 *y2* y1 * y0--1000001 = 1>000 = 0

x1 *y2* y1-1-00-010 = 2>001 = 1

x1 * x0* y2 * y0-110-0011 = 3>010 = 2

x2

1--0--100 = 4>011 = 3

*y2

x2* x0

1-1-00101 = 5>100 = 4

*y1 *y0

x2* x1

11--0-110 = 6>101 = 5

*y1

x2* x1* x1 *y0111--0111 = 7>110 = 6

4) Comparatorul pe n bii

Concluziile de mai sus se pot extrapola pentru comparatoare binare pe n bii ; 1. a = (minx 1 > maxy 0) + (minx 2 > maxy 1) + (minx 3 > maxy 2) + ... + (minx 2n-1 > maxy 2n-2)se obtine prin permutarea biilor xi i yi;

1. b = (miny 1 > maxx 0) + (miny 2 > maxx 1) + (miny 3 > maxx 2) + ... + (miny 2n-1 > maxx 2n-2) (se obine prin permutarea biilor xi i yi ) ;3. Egalitatea xi = yi, care se poate exprima: e = S (xi yi), pentru i [ 0, n-1 ].

4.2.Sumatoare binare

Sumatorul binar este un circuit logic combinaional care realizeaz suma aritmetic a dou numere ntregi X i Y reprezentate n cod binar, fiecare pe n bii. Regulile de nsumare sunt aceleai ca n cazul numerelor zecimale.

In tabela urmtoare este ilustrat un exemplu de nsumare S = X + Y a dou numere reprezentate pe 8 bii.

Binar282726252423222120hexdec

X

011010116B107

Y

11001110CE206

Carry11001110cin=0

S100111001139313

Rezultatul arat o depaire binar deoarece suma este S = 139 hex >FF, respectiv S =313dec>255.X (xn-1, ..., x0)

Schema bloc din figura 3 folosete notatiile X, Y valorile proprii de 2n bii, cin transport (carry) de intrare i cout transport (carry) de ieire care va deveni transport de intrare pentru un sumatorul de rang superior.

X (x2n-1, ..., xn)

X (xn-1, ..., x0)

n bii

n biiSsupSinf

cout15_8cin

cout7_0cin

n biin biiY (y2n-1, ..., yn)Y (yn-1, ..., y0)

Figura 3

Operaia de adunare se face modulo2 la nivel de bit deoarece numerele sunt reprezentate n binar. Blocul are 4n+1 intrri i 2n+1 ieiri. Operaia de nsumare propag bitul de transport de la celule de rang inferior la cele de rang superior. Realizarea sumei se face pe 2n bii adic aceiai lungime pe care o au numerele aplicate la intrare. In cazul blocului din figura 3, suma este de tip modulo 22n.Sumator complet pe 1 bit Diagrama Karnaugh pentru s0 i cout.

a0 b000011110ci

00101

11010

s0

a0 b000011110ci

00010

10111

cout

Observaie :Suma s0 este egal cu 1 atunci cnd numrul de bii egal cu 1 n procesul de nsumare este impar.

Transportul de ieire cout egal cu 1 atunci cnd numrul de bii egal cu 1 n vectorul de intrare este mai mare sau egal cu 2.

In diagrama Karnaugh a sumei s0 nu exist puncte adiacente, datorit distribuiei de 1, deci funcia este o funcie canonic.

s0 = ci*a0*b0 + ci*a0*b0 + ci*a0*b0 + ci*a0*b0 - forma canonic disjunctiv, respectiv:

s0 = ( (ci*a0*b0)* (ci*a0*b0)* (ci*a0*b0)* (ci*a0*b0) ) transformat cu porti nand,respectiv:

s0 = ci*(a0*b0 + a0*b0 )+ ci*(a0*b0 + a0*b0) = ci*(a0*b0 + a0*b0 )+ ci*(a0*b0 + a0*b0) =

ci*(a0 b0 ) + ci*(a0b0) = ci(a0b0) transformat cu porti xor.

In cazul transportului, biii se pot cupla conform diagramei Karnaugh i se obine expresia:

cout = ci*a0 + ci*b0 + a0*b0

2) Sumator complet pe 2 bii (n=2)

In figura 4 este reprezentat schema bloc a sumatorului complet pe 2 bii.Cei 5 bii de intrare {ci , a0 , b0 , a1, b1} determin cele 3 funcii de ieire {s0 , s1, cout}

Se observ c s0 depinde numai de {ci, a0, b0} n timp ce cout i s1 depind de toi cei 5 bii de intrare.Pentru a uura raionamentul de definire a ieirilor cout i s1 se introduce t o variabil virtual de transport intermediar, identic cu valoarea cout a sumatorului pe 1 bit.Pe baza observaiilor se pot completa rapid cele dou diagrame Karnaugh din figura 5:Suma s0 este egal cu 1 atunci cnd numrul de bii egal cu 1 n procesul de insumare este impar.

Transportul de ieire cout egal cu 1 atunci cnd numrul de bii egal cu 1 n vectorul de intrare este mai mare sau egal cu 2,

a1a0

cout

t

ci

s1

s

b1b0Figura 4

a0 b0 ci000001011010110111101100a0 b0 ci000001011010110111101100

a1b1

a1b1

00

1

111

00

0111

1

101

1

111

11

1

111

1111111111

1011

1

110

1

111

s1

cout

Figura 5s1 = a1*b1*a0*ci + a1*b1*b0*ci + a1*b1*a0*b0+cout = a1*a0*ci + a1*b0*ci + a1*a0*b0 ++ a1*b1*a0*ci + a1*b1*b0*ci + a1*b1*a0*b0++ b1*a0*ci + b1*b0*ci + b1*a0*b0 +

+ a1*b1*a0*ci + a1*b1*b0*ci + a1*b1*a0*b0++ a1*b1

+ a1*b1*a0*ci + a1*b1*b0*ci + a1*b1*a0*b0

In forma disjunctiv elementar funcia sum s1 este format din 12 termeni de cte 4 bii, iar cout este format din 6 termeni de cte 3 bii i un termen de 2 bii, ceea ce conduce la concluziile:

In general sunt necesare 3 nivele de procesare logic: negaie, conjuncie, disjuncie. Funcia cout utilizeaz numai conjuncie i disjuncie, deci 2 nivele de procesare logic

Dac se noteaz cu ntrzierea fizic de rspuns a porilor logice se vor obine ntrzieri de 3, respectiv 2 pentru stabilizarea valorilor logice ale ieirilor.

3) Sumator complet pe 4 bii cu accelerarea transportului (Carry-lookahead adder).

Sumatorul complet a dou numere de cte 4 bii poate fi implementat cu patru module de sumatoare complete pe 1 bit.

s0 = ci*a0*b0 + ci*a0*b0 + ci*a0*b0 + ci*a0*b0 - forma canonic disjunctiv, respectiv:

s0 = ( (ci*a0*b0)* (ci*a0*b0)* (ci*a0*b0)* (ci*a0*b0) ) implementat cu porti nand, respectiv: s0 = ci(a0b0) implementat cu porti xor.

cout = ci*a0 + ci*b0 + a0*b0

Admitem ca oricare poart logic de tip not, and, or, nand, nor ofer rezultatul prelucrrii dup o ntrziere de propagare egal cu , iar poarta xor va rspunde dup 3.

In figura 6 este prezentat schema bloc a unui sumator pe 4 bii. Intrzierile de prelucrare pentru fiecare ieire sunt multipli de i sunt calculai pentru implementarea cu pori (not, and, or) sau nand. Fiecare sumator din structur i va stabiliza ieirile dup stabilizarea intrrilor cu ntrzierile specifice.

a3 b3

a2 b2

a1b1a0 b0

cout8

6

4

2

ci

9

7

53

s3

s2

s1s0

Figura 6

Pentru implementarea unui sumator complet pe 4 bii cu accelerarea transportului (Carry-lookahead adder), abreviat CLA, se va restructura circuitul conform figurii 7. Ideea de baz este de a genera n mod paralel cei 4 bii de transport c1, c2, c3 i c4 prin funcii logice complexc dependente de cei nou bii de intrare.

a3 b3a2 b2a1 b1a0 b0

1 bit

1 bit

1 bit

1 bitc0

adder

adder

adder

adder

s3

s2

s1

s0

p3g3cp2g2cp1g1c1p0g0

c4

3

2

Carry lookahead generator

pGgG

Figura 7Se introduc dou funcii logice generale:gi = ai * bi denumit carry generate;

pi = ai bi denumit carry propagate.

Utiliznd notaiile de mai sus, se pot scrie funciile logice ale sumei i transportului pentru fiecare rang astfel:

si = ai bi ci = pi ci ci+1 = ai*bi + ci*ai + ci*bi = ai*bi + ci*(ai + bi) = ai*bi + ci*(ai bi) = gi + ci * pi

Nota: echivalena expresiilor ai*bi + ci*(ai + bi) i ai*bi + ci*(ai bi) se poate demonstra prin oricare dintre metodele cunoscute: tabele de adevr, diagrame Karnaugh sau raionament

sintetic.

Se vor folosi relaiile (i) i (ii) pentru a determina funciile logice ale biilor de transport ci astfel:c1 = g0 + p0*c0 c2 = g1 + p1*c1 = g1 + p1*g0 + p1*p0*c0 c3 = g2 + p2*c2 = g2 + p2*g1 + p2*p1*g0 + p2*p1*p0*c0 c4 = g3 + p3*c3 = g3 + p3*g2 + p3*p2*g1 + p3*p2*p2*c0 + p3*p2*p1*p0*c0

Procesarea celor 4 bii de transport se relizeaz pe dou nivele, and i or respectiv nand i nand, deci timpul de propagare este 2, n timp ce propagarea biilor pi = ai bi este 3.

In concluzie, ntrzierea de stabilizare a valorii celor 4 bii de transport are valoarea maxim 5, ceea ce conduce la un spor semnificativ al vitezei de calcul prin utilizarea acceleratorului

Carry lookahead generator.