1

ANALIZA I SINTEZA DISPOZITIVELOR NUMERICEcurs

1

2

Bibliografie1. Circuite de comutare aplicate n calculatoarele electronice, V. Pop, Volker Popovici, ed. Facla, 1976 2. Circuite integrate digitale, Gh. tefan, I. Drghici, T. Murean, E. Barbu, EDP, 1983 3. De la poarta TTL la microprocesor, I. Sztojanov .a., ET, 1987 4. Proiectarea cu circuite logice MSI i LSI standard, T.R. Blakeslee, ET, 1988 5. Circuite integrate digitale, Gh. Stefan, V. Bistriceanu, Probleme, proiectare, EDP, 1992 6. Circuite integrate digitale, Gh. Stefan, V. Bistriceanu, Probleme, proiectare, Ed. Albastr, 2000 7. Automatizri discrete n industrie, Culegere de probleme, N. Sprncean, R. Dobrescu, Th. Borangiu, ET, 1978 8. Sisteme numerice cu circuite integrate, Culegere de probleme, Sanda Maican, ET, 1980 9. Analiza i sinteza dispozitivelor numerice, I.A. Leia, ndrumtor de laborator, I.P. Cluj-Napoca, 1985 10.Analiza i sinteza dispozitivelor numerice, A. Nein, O. Cre, ndrumtor de laborator, UT Press. Cluj-Napoca, 1998

2

3

Curs 1 CAPITOLUL I ELEMENTE DE ALGEBR BOOLEAN1.1. GeneralitiTransferul, prelucrarea i pstrarea datelor numerice sau nenumerice n interiorul unui calculator se realizeaz prin intermediul circuitelor de comutare. Aceste circuite se caracterizeaz prin faptul c prezint dou stri stabile care se deosebesc calitativ ntre ele. Strile sunt puse n coresponden cu valorile binare 0 i 1 sau cu valorile logice adevrat i fals (din acest motiv se mai numesc i circuite logice). Pornind de la aceste considerente, un domeniul al logicii matematice, (tiina care utilizeaz metode matematice n soluionarea problemelor de logic) numit algebra logicii i-a gsit o larg aplicare n analiza i sinteza circuitelor logice. Algebra logicii opereaz cu propoziii care pot fi adevrate sau false. Unei propoziii adevrate i se atribuie valoarea 1, iar unei propoziii false i se atribuie valoarea 0. O propoziie nu poate fi simultan adevrat sau fals, iar dou propoziii sunt echivalente d.p.d.v. al algebrei logice, dac simultan ele sunt adevrate sau false. Propoziiile pot fi simple sau compuse, cele compuse obinndu-se din cele simple prin legturi logice de tipul conjunciei disjunciei sau negaiei . , Bazele algebrei logice au fost puse de matematicianul englez George Boole (1815-1864) i ca urmare ea se mai numete i algebr boolean. Ea a fost conceput ca o metod simbolic pentru tratarea funciilor logicii formale, dar a fost apoi dezvoltat i aplicat i n alte domenii ale matematicii. n 1938 Claude Shannon a folosit-o pentru prima dat n analiza circuitelor de comutaie.

1.2. Definirea axiomatic a algebrei booleeneAlgebra boolean este o algebr format din: - elementele {0,1}; - 2 operaii binare numite SAU i SI, notate simbolic + sau i sau ; - 1 operaie unar numit NU negaie, notat simbolic sau . Operaiile se definesc astfel: SI SAU NU 0 0=0 0+0=0 0=1 0 1=0 0+1=1 1=0 1 0=0 1+0=1 1 1=1 1+1=13

4

Axiomele algebrei booleene sunt urmtoarele: Fie o mulime M compus din elementele x1, x2,xn, mpreun cu operaiile i +. Aceast mulime formeaz o algebr dac: 1) Mulimea M conine cel puin 2 elemente distincte x1 x2 (x1,x2 M); 2) Pentru x1 M, x2 M avem: x1 + x2 M i x1 x2 M 3) Operaiile i + au urmtoarele proprieti: a. sunt comutative x1 x2 = x2 x1 x1 + x2 = x2 + x1 b. sunt asociative x1 (x2 x3) = (x1 x2) x3 x1 + (x2 + x3) = (x1 + x2) + x3 c. sunt distributive una fa de cealalt x1 (x2 + x3) = x1 x2 + x1 x3 x1 + (x2 x3) = (x1 + x2) (x1 + x3) 4) Ambele operaii admit cte un element neutru cu proprietatea: x1 + 0 = 0 + x1 = x1 x1 1 = 1 x1 = x1 unde 0 este elementul nul al mulimii, iar 1 este elementul unitate al mulimii. 5) Dac mulimea M nu conine dect dou elemente, acestea trebuie s fie obligatoriu elementul nul 0 i elementul unitate 1; atunci pentru x M exist un element unic notat cu x cu proprietile: x x=0 principiul contradiciei x+x=1 principiul terului exclus x este inversul elementului x. n definirea axiomatic a algebrei s-au folosit diferite notaii. n tabelul urmtor se dau denumirile i notaiile specifice folosite pentru diverse domenii: Matematic Prima lege de compoziie x1 + x2 A doua lege de compoziie x1 x2 Elementul invers x Logic Disjuncie x1 x2 Conjuncie x1 x2 Negare x Tehnic SAU x1 + x2 SI x1 x2 NU x

4

5

1.3. Proprietile algebrei booleenePlecnd de la axiome se deduc o serie de proprieti care vor forma reguli de calcul n cadrul algebrei booleene. Aceste proprieti sunt: 1) Principiul dublei negaii x=x dubla negaie duce la o afirmaie 2) Idempotena x x=x x+x=x 3) Absorbia x1 (x1 + x2) = x1 x1 + (x1 x2) = x1 4) Proprietile elementelor neutre x 0=0 x 1=x x+0=x x+1=1 5) Formulele lui De Morgan x1 x2 = x1 + x2 x1 + x2 = x1 x2 Aceste formule sunt foarte utile datorit posibilitii de a transforma produsul logic n sum logic i invers. Formulele pot fi generalizate la un numr arbitrar de termeni: x1 x2 xn = x1 + x2 + + xn x1 + x2 + + xn = x1 x2 xn 6) Principiul dualitii dac n axiomele i proprietile algebrei booleene se interschimb 0 cu 1 i + cu , sistemul de axiome rmne acelai, n afara unor permutri. Verificarea proprietilor se poate face cu ajutorul tabelelor de adevr i cu observaia c dou funcii sunt egale dac iau aceleai valori n toate punctele domeniului de definiie. Prin tabelul de adevr se stabilete o coresponden ntre valorile de adevr ale variabilelor i valoarea de adevr a funciei. Obs. Comutativitatea i asociativitatea pot fi extinse la un numr arbitrar, dar finit, de termeni, indiferent de ordinea lor.

1.4. Funcii booleeneO funcie f: Bn B, unde B = {0,1} se numete funcie boolean. Aceast funcie boolean y = f(x1, x2,,xn) are drept caracteristic faptul c att variabilele ct i funcia nu pot lua dect dou valori distincte, 0 sau 1. Funcia va pune n coresponden fiecrui element al produsului cartezian n dimensional, valorile 0 sau 1. Astfel de funcii sunt utilizate pentru caracterizarea funcionrii unor dispozitive (circuite) construite cu elemente de circuit avnd dou stri (ex.: un ntreruptor nchis sau5

6

deschis, un tranzistor blocat sau n conducie; funcionarea unui astfel de circuit va fi descris de o variabil boolean xi). 1.4.1. Funcii booleene elementare Revenim la forma general a unei funcii booleene de n variabile: y = f(x1, x2,,xn) Domeniul de definiie este format din m = 2n puncte. Deoarece n fiecare din aceste puncte funcia poate lua doar valorile 0 i 1 rezult c numrul total al funciilor booleene de n variabile este N = 2m. Vom considera n continuare funciile elementare de 1 variabil. Pentru n = 1 avem m = 2 i N = 4. Funcia are forma y = f(x) i cele 4 forme ale ei se gsesc n tabelul urmtor: fi f0 f1 f2 f3 x 0 0 0 1 1 1 0 1 0 1 Reprezentare 0 x x 1 Denumire Constanta 0 Variabila x Negaia lui x Constanta 1

La fel se pot realiza toate funciile cu ajutorul unor funcii de baz. Acestora le vor corespunde i nite circuite logice elementare, cu ajutorul crora se poate realiza practic orice tip de circuit. innd cont de faptul c circuitele logice de comutaie au 2 stri stabile LOW (L) i HIGH (H), asignnd lui L 0 i lui H 1 se poate ntocmi un tabel al funciilor elementare. Denumire Inversor NOT Poart SI AND Funcie f=x x f=x f = x1 x2 x1 x2 f=x1 x2 Poart SAU OR f = x1 + x2 x1 x2 f=x1+x2 Simbol Tabel de adevr x f 0 1 1 0 x1 x2 f 0 0 0 0 1 0 1 0 0 1 1 1 x1 x2 f 0 0 0 0 1 1 1 0 1 1 1 1 Tabel de definiie x f L H H L x1 x2 f L L L L H L H L L H H H x1 x2 f L L L L H H H L H H H H

6

7

Poart SI-NU NAND

f = x1 x2 x1 x2 f=x1 x2

Poart SAU-NU NOR

f = x1 + x2 x1 x2 f=x1+x2

SAU EXCLUSIV XOR f = x1 + x2 x1 x2 f=x1 + x2 COINCIDEN f = x1 x2 x1 x2 f=x1 x2 =x1 + x2

x1 0 0 1 1 x1 0 0 1 1 x1 0 0 1 1 x1 0 0 1 1

x2 0 1 0 1 x2 0 1 0 1 x2 0 1 0 1 x2 0 1 0 1

f 1 1 1 0 f 1 0 0 0 f 0 1 1 0 f 1 0 0 1

x1 L L H H x1 L L H H x1 L L H H x1 L L H H

x2 L H L H x2 L H L H x2 L H L H x2 L H L H

f H H H L f H L L L f L H H L f H L L H

1.4.2. Reprezentarea funciilor booleene Exist dou moduri de reprezentare a funciilor booleene: grafic i analitic. 1. Modaliti grafice - se caracterizeaz printr-o reprezentare intuitiv, uor de reinut, dar sunt inadecvate pentru funcii booleene cu un numr de variabile mai mare dect 4; 2. Modaliti analitice - sunt mai greoaie, dar permit metode automate, deci algoritmi de simplificare a funciei; se folosesc n general pentru funcii booleene cu numrul variabilelor mai mare dect 5. 1.4.2.1. Modaliti de reprezentare grafic Modalitile de reprezentare grafic sunt: tabel de adevr, diagram Karnaugh, schem logic, diagram de timp. 1. Tabel de adevr se marcheaz ntr-un tabel corespondena dintre valorile de adevr ale variabilelor de intrare i valoarea de adevr a funciei, n fiecare punct al domeniului de definiie. Pentru o funcie cu n variabile de intrare vom avea 2n combinaii. Exist situaii n care, pentru anumite combinaii ale variabilelor de intrare, valoarea funciei nu este specificat. Aceste funcii se numesc incomplet definite. n tabel, n locul n care funcia nu este specificat, se noteaz cu X. Dac o funcie boolean este incomplet definit pentru

7

8

m combinaii ale variabilelor de intrare se pot defini 2m funcii noi prin alegerea arbitrar a valorilor incomplet definite. 2. Diagram Karnaugh O diagram Karnaugh pentru o funcie boolean de n variabile se deseneaz sub forma unui ptrat sau dreptunghi mprit n 2n compartimente. Fiecare compartiment este rezervat unui termen canonic al funciei, respectiv unuia dintre vrfurile cubului n dimensional din reprezentarea geometric a funciei (2n n-uple ale funciei). Diagrama Karnaugh este organizat astfel nct dou compartimente vecine pe o linie sau pe o coloan corespund la doi termeni canonici care difer numai printr-o singur variabil, care apare n unul adevrat, iar n cellalt negat (la dou n-pluri adiacente). Se consider vecine i compartimentele aflate la capetele opuse ale unei linii, respectiv coloane. Diagrama Karnaugh se noteaz fie indicnd domeniul fiecrei variabile, fie indicnd pe linie i coloan n-uple de zerouri i uniti corespondente unui compartiment din diagram i ordinea variabilelor. Prima notaie se folosete n cazul n care se reprezint funcia prin forma ei canonic sau normal. A doua notaie se folosete n cazul n care funcia se reprezint prin tabel de adevr. Pentru a putea reprezenta uor funcii exprimate n mod convenional prin indicii termenilor canonici se poate nota fiecare compartiment cu indicele termenului corespondent, innd cont de o anumit ordine a variabilelor. Exemple: 1) Diagrama Karnaugh pentru funcia de 2 variabile: f(x1, x2) = x1 x2 + x1 x2 x2 x2 sau x1 00 01 11 10 x2 Obs. Numerotarea liniilor i coloanelor se face n cod Gray (cod binar reflectat) 0 1 x1 0 1 x1x2 x1x2 x1x2 x1x2 x1 x2 0 1 x1 0 0 1 1 1 0

8

9

Cod binar direct Cod Gray 0000 0000 0001 0001 0010 0011 0011 0010 0100 0110 0101 0111 0110 0101 0111 0100 1000 1100 1001 1101 1010 1111 1011 1110 1100 1010 1101 1011 1110 1001 1111 1000 2) Diagrama Karnaugh pentru funcia de 3 variabile: y = f(x1,x2,x3) Domeniul de definiie este format din 23 = 8 puncte i reprezint vrfurile unui cub cu latura 1: x1 001 011 010 x2 Diagramele Karnaugh corespunztoare pot fi reprezentate astfel: x2 x1 x2x3 0 1 000 4 1 5

101 111 000 110 100 x3

013 7

112 6

10

x1 sau

x3

9

10

x1x2 x3 0 0 1 00 3 01 2 x2 6 7 x1 11 5 10 4 3) Diagrama Karnaugh pentru funcia de 4 variabile: y = f(x1,x2,x3,x4) x4 x1x2 x3x4 00 01 11 10 0 1 3 2 00 5 7 6 01 4 x2 12 13 15 14 x1 11 9 11 10 10 8 x3 Prin sgei am marcat vecintile punctului de coordonate 0010. 4) Diagramele Karnaugh pentru funcii de mai mult de 4 variabile se construiesc din diagrame de 4 variabile considerate ca diagrame elementare. 3. Schem logic reprezentare cu ajutorul simbolurilor circuitelor logice. 4. Diagram de timp reprezentare util pentru studiul unor forme tranzitorii de hazard n circuitele logice. Se reprezint funcii logice n a cror evoluie intervine timpul. Exemplu: f = x1 x2 x1 x2 f

x3 1

Curs 21.4.2.2. Modaliti de reprezentare analitic 1) Formele canonice Fie o funcie boolean f(x), unde x = (x1,x2,,xn). Se definete numrul i = x1 20 + x2 21 + + xn 2n-1 ca numr de combinaii. Exemplu: x1 x2 x3 f 0 0 0 0 0 110

11

0 1 0 i = 0 22 + 1 21 + 0 20 = 2 0 1 1 Fie funcia Pi definit pe Bn B, deci Pi : Bn B Pi(x1,x2,,xn) = 1 dac numrul de combinaii este i 0 n caz contrar Aceast funcie se numete constituent al unitii. Se poate arta c orice funcie boolean dat prin tabelul de adevr se poate scrie ca o sum de constitueni ai unitii. f(x1, x2,,xn) = Pi1 + Pi2 + + Pip = Pij i,jM1 unde M1 = mulimea tuturor combinaiilor argumentelor pentru care funcia ia valoarea 1. Aceast form de scriere se numete forma canonic disjunctiv FCD, iar termenii constitueni se numesc termeni canonici conjunctivi sau mintermi (se mai numete i forma sum de produse). Funcia boolean se mai poate scrie i sub forma Si : Bn B unde B = {0,1}. Si(x1,x2,,xn) = 0 dac numrul de combinaii este i 1 n caz contrar Se poate demonstra c orice funcie boolean poate fi adus la forma: f(x1, x2,,xn) = Si1 Si2 Siq = Sij i,jM0 unde M0 = mulimea tuturor combinaiilor argumentelor pentru care funcia ia valoarea 0. Aceast form de scriere se numete forma canonic conjunctiv FCC, iar factorii constitueni se numesc termeni canonici conjunctivi sau maxtermi (se mai numete i forma produs de sume). Se poate demonstra c Si = Pi. Algoritmi de obinere a formelor canonice pe baza tabelului de adevr sau a diagramei Karnaugh: FCD - se determin toate combinaiile variabilelor pentru care valoarea funciei este 1; - se scriu mintermii corespunztori (o variabil apare nenegat dac are valoarea 1 i negat dac are valoarea 0); - se nsumeaz mintermii obinui anterior. FCC - se determin toate combinaiile variabilelor pentru care valoarea funciei este 0;

11

12

- se scriu maxtermii corespunztori prin nsumarea variabilelor (o variabil apare nenegat dac are valoarea 0 i negat dac are valoarea 1); - se nmulesc maxtermii obinui anterior. Exemplu: x1 x2 x3 f 0 0 0 0 0 0 1 1 mintermul este x1 x2 x3 0 1 0 0 maxtermi sunt (x1+x2+x3) (x1+x2+x3) Trecerea dintr-o form canonic n alta se poate face n dou moduri: - cu ajutorul tabelului de adevr; - prin aplicarea dublei negaii i a teoremelor lui De Morgan. Teorema lui Shannon Complementul unei funcii booleene se obine prin complementarea fiecrei variabile i interschimbarea operatorilor I cu SAU i reciproc. f(x1,x2,,xn)+, = f(x1,x2,,xn) ,+ Teorema de expansiune Fie funcia boolean f(x1,x2,, xi-1, xi, xi+1,,xn) care se expandeaz dup variabila xi. Avem atunci: f(x1,x2,, xi-1, xi, xi+1,,xn) = xi f(x1,x2,, xi-1, 1, xi+1,,xn) + xi f(x1,x2,, xi-1, 0, xi+1,,xn) Funcia dual este: f = [xi + f(x1,x2,, xi-1, 0, xi+1,,xn)] [xi + f(x1,x2,, xi-1, 1, xi+1,,xn)] 2) Forma elementar La formele canonice ale funciilor booleene termenii conin toate variabilele independente de intrare, negate sau nenegate. Termenii formei elementare nu conin toate variabilele de intrare. Aceast form se obine din formele canonice prin minimizare. 3) Forma neelementar Forma neelementar conine variabile sau grupuri de variabile comune mai multor termeni. Se obine din celelalte forme prin aplicarea algebrei booleene. Este folosit la implementarea funciilor logice deoarece permite reducerea numrului de intrri n circuitele logice. Are dezavantajul mririi numrului de nivele logice. 1.4.3. Minimizarea funciilor booleene Algebra boolean se folosete la analiza i sinteza dispozitivelor numerice (circuite de comutaie). ntre gradul de complexitate al circuitului i cel al funciei care l descrie exist o legtur direct. Aceasta este motivaia pentru care, n etapa de sintez a circuitelor de12

13

comutaie, dup definirea acestora, urmeaz n mod obligatoriu etapa de minimizare a funciei, avnd drept scop obinerea unor forme echivalente mai simple (forma minim). Soluia minim obinut n urma minimizrii ar trebui s fie cea mai avantajoas (economie de pori logice, obinerea unei scheme mai fiabile, mai ieftine). n realitate nu este ntotdeauna aa. De exemplu, dorina de a obine un sistem uor depanabil poate duce la obinerea unei soluii neminimale, dar care prezint proprieti interesante de simetrie i regularitate. Prin aplicarea metodelor de minimizare (de simplificare) se ajunge la expresii minimale sub forma unor SAU-uri de SI-uri (reuniune minimal) ori a unor SI-uri de SAU-uri (intersecie minimal). Criteriile utilizate n vederea minimizrii sunt: - reducerea numrului de variabile; - reducerea numrului de termeni; - reducerea pe ansamblu a variabilelor i termenilor, astfel ca suma lor s devin minim. Minimizarea const n principal n transformarea formelor canonice i a formelor elementare parial simplificate n forme elementare minimale. Metodele de minimizare pot fi grupate n metode algebrice i metode grafice. 1.4.3.1. Minimizarea grafic 1. Diagrama Karnaugh Minimizarea se bazeaz pe proprietatea de adiacen a codului binar reflectat (Gray) cu ajutorul cruia se numeroteaz liniile i coloanele diagramei Karnaugh. n vederea minimizrii se aleg suprafeele maxime (subcuburi) formate din constitueni ai unitii, respectiv din constitueni ai lui 0, suprafee (subcuburi) avnd ca dimensiune un numr de ptrate (compartimente) egal ntotdeauna cu puteri ale lui 2. Aceste suprafee vor corespunde termenilor canonici, termenii vecini fiind adiaceni (difer printr-un singur bit). Ca urmare, n urma gruprii lor se vor reduce variabilele pe baza relaiei: x1 x2 + x1 x2 = x1. Metoda de minimizare: - se realizeaz grupri de compartimente (subcuburi) care sunt puteri ale lui 2. Un compartiment poate fi membru al mai multor suprafee. O suprafa cu 2m celule vecine va elimina 2m variabile de intrare. - se scriu ecuaiile corespunztoare fiecrei suprafee, obinnduse astfel termenii elementari.

13

14

- se realizeaz forma disjunctiv minim (FDM) prin nsumarea termenilor elementari obinui prin gruparea constituenilor lui 1 sau forma conjunctiv minim (FCM) prin nmulirea termenilor elementari obinui prin gruparea de constitueni ai lui 0; funciile minimale obinute sunt identice, ele diferind numai prin forma de prezentare. Pentru a se obine forma minimal a unei funcii booleene este util s se minimizeze ambele forme canonice, FCC i FCD. Apoi, n funcie de disponibilitatea componentelor i de numrul de conexiuni care rezult, se poate alege forma minimal a funciei booleene care va fi implementat. Exemplu: f(x1,x2,x3,x4) = (3, 7, 8, 9, 12, 13, 15) x4 x1x2 x3x4 00 01 x1 11 10 00 0 0 1 1 01 0 0 1 1 11 1 1 1 0 10 0 0 0 0 x2

x3 Pentru FDM a funciei se obin dou variante, dup cum se aleg suprafeele pentru minimizare: fFDM1 = x1 x3 + x1 x3 x4 + x1 x2 x4 sau fFDM2 = x1 x3 + x1 x3 x4 + x2 x3 x4 Implementarea cu pori de tip SI-NU arat astfel: fFDM1 = x1 x3 + x1 x3 x4 + x1 x2 x4 = = x1 x3 x1 x3 x4 x1 x2 x4

Minimizarea funciei negate va fi:fFDM = x1 x3 + x3 x4 + x1 x2 x3 La fel se procedeaz i la minimizarea funciei prin folosirea constituenilor de 0: x4 x1x2 x3x4 00 01 11 10 00 0 0 1 0 01 0 0 1 0 x2 x1 11 1 1 1 014

15

10

1

1

0

0

x3 Forma minimizat conjunctiv a funciei FCM este: fFCM = (x1+x3) (x3+x4) (x1+x2+x3)2. Diagrame Karnaugh pentru funcii incomplet definite

Funciile incomplet definite sunt cele care n anumite puncte ale domeniului de definiie pot lua valoarea 0 sau valoarea 1. Avem dou posibiliti: - combinaii de intrare pentru care funcia are valori indiferente (nedefinite); - combinaii ale variabilelor care nu pot s apar din punct de vedere fizic; n aceste situaii trebuie studiat dac combinaiile sunt susceptibile s se produc n urma unei manevre false sau n urma unui defect de funcionare; pentru a evita funcionarea greit, n locaiile corespunztoare se impun valori pentru funcie, astfel nct s nu se perturbe funcionarea normal. Valorile nespecificate precum i locaiile corespunztoare din diagrama Karnaugh se numesc indiferente sau arbitrare sau redundante. Ele se noteaz cu x i vor fi considerate n timpul minimizrii ca avnd valoarea 1 sau 0, n funcie de situaie, pentru a se obine o minimizare ct mai bun. x4 x1x2 x3x4 00 01 x1 11 10 00 x 1 1 01 x 1 1 x 11 1 1 1 10 x x x2

x3 Ca s minimizm funcia n FDM considerm c x au valoarea 1 i grupm aceti x numai cu valorile de 1, nu i ntre ei (o grupare ntre ei nu are nici o semnificaie). Se obine: fFDM = x1 x2 + x2 x3 + x1 x4 + x2 x4

Obs. n cazul funciilor incomplet definite, funcia complementar simplificat prin grupri de 0 nu coincide ntotdeauna cu complementul funciei.3. Diagrame Karnaugh cu expresii a. Superpoziia funciilor booleene

15

16

Fie o funcie boolean f(X) cu X = (x1,x2,, xi, xi+1,,xn). Dac considerm X1 = (x1,x2,, xi) i X2 = (xi+1,,xn) i dac funcia f(X) poate fi scris ca o funcie f(X) = f3[f1(X1), f2(X2)] atunci spunem c f(X) a fost obinut prin superpoziia funciilor f1(X1) i f2(X2). Dac X1X2 = atunci avem o superpoziie disjunct, iar dac X1X2 avem o superpoziie nedisjunct. x1 f xn Dup superpoziie avem: x1 f1 xi f3 f xi+1 f2 xn b. Decompoziia funciilor booleene Dac se d o funcie boolean i un set de funcii se cere s se realizeze o spargere a funciei booleene. S-a reuit decompoziia funciei booleene dac: f = fm [fm-1(Xm-1), fm-2(Xm-2),,f1(X1),X0] unde Xi X Dac f poate fi scris ca f = f2[f1(X1),X0] decompoziia este simpl.m-1

Decompoziia este nedisjunct dac: Xi = i=j m-1

Decompoziia este disjunct dac: Xi i=j

Exemplu: f(x1,x2,x3,x4) = (0, 2, 3, 7, 9, 10, 11, 14) x4 x1x2 x3x4 00 01 11 10 00 1 1 1 01 1 x2 x1 11 1 10 1 1 1 x3 fFDM = x1 x2 x4 + x1 x3 x4 + x1 x3 x4 + x1 x2 x4 = x2(x1 x4) + x3(x1 + x4) = = x2 G + x3 G unde G = x1 + x4 i deci f se poate scrie: f = f2[G(x1,x4), x2,x3]16

17

Pornind de la aceast form pentru f, facem o minimizare.f = x2 G + x3 G = x2 G (x3 + x3) + x3 G (x2 + x2) = = x2x3G + x2x3G + x2x3G + x2x3G = x2x3 + x2x3G + x2x3G Diagrama Karnaugh corespunztoare este: x2 x3 0 1 0G 1 x2 1 0 G x3 n general o diagram Karnaugh cu n expresii (sau variabile) are n 2 locaii. Prin nglobarea n diagram a m expresii (variabile) dimensiunea diagramei se reduce, numrul de locaii devenind 2n-m. Pentru a minimiza o funcie prin diagrame Karnaugh cu expresii se fac urmtorii pai: 1) se consider toate variabilele din diagram ca i cum ar fi 0 i se formeaz suprafee (subcuburi) cu constituenii lui 1; 2) se consider toate locaiile cu 1 indiferente i se formeaz suprafee (subcuburi) cu variabilele nglobate; 3) se consider intersecia variabilelor nglobate cu gruprile obinute n pasul 2; 4) se face reuniunea termenilor din paii 1 i 3; 5) pentru mai mult de o variabil nglobat se trateaz pe rnd conform pailor 1 - 4 numai cte o variabil, celelalte fiind considerate 0, iar apoi se scrie reuniunea tuturor termenilor obinui. Exemplu: S se minimizeze funcia cu variabile nglobate: x1 x2x3 00 01 11 10 0 a+b 1 c 1 1 1 x Pasul 1. x1 x2x3 00 01 11 10 0 1 1 1 1 x Se obine x2 x3 + x1 x3

Pasul 2 i 3.11 x x 10 c x

x1 x2x3 0 1

00 x

01 a+b

Se obine

c x2 + (a+b) x1 x317

18

Pasul 4. f = x2 x3 + x1 x3 + c x2 + (a+b) x1 x3

Curs 31.4.3.2. Minimizarea algebric

Minimizarea algebric a funciilor booleene se face cu ajutorul teoremelor algebrei booleene. n cazul n care numrul de variabile este mai mare dect 6 se utilizeaz metoda de minimizare Quine-Mc Cluskey. Aceast metod are avantajul c algoritmul este uor de implementat pe calculator. Pentru prezentarea metodei vom lua ca exemplu funcia: f = (0, 2, 3, 5, 7, 8, 10, 11, 13, 15) Etapele de minimizare sunt: 1. Se grupeaz termenii canonici astfel nct termenii din fiecare grup s conin acelai numr de 1, respectiv 0. TC x1 x2 x3 x4 0 0 0 0 0 2 0 0 1 0 8 1 0 0 0 3 0 0 1 1 5 0 1 0 1 10 1 0 1 0 7 0 1 1 1 11 1 0 1 1 13 1 1 0 1 15 1 1 1 1 2. Se compar fiecare termen dintr-o grup cu toi cei din grupa urmtoare, aplicnd18

19

relaia de reducere: x1 x2 + x1 x2 = x1. Se grupeaz termenii care difer printr-o singur variabil (o singur poziie binar). Termenul obinut prin combinare va conine pe poziia respectiv semnul -. Comparare Rezultatul comparrii ntre x1 x2 x3 x40, 2 0, 8 2, 3 2, 10 8, 10 3, 7 3, 11 5, 7 5, 13 10, 11 7, 15 11, 15 13, 15 0 0 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 1 0 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1

n continuare se repet procedeul de comparare pn cnd nu mai este posibil nici o reducere. Comparare Rezultatul comparrii ntre x1 x2 x3 x4 0, 2, 8, 10 - 0 - 0 2, 3, 10, 11 - 0 1 3, 7, 11, 15 - - 1 1 5, 7, 13, 15 - 1 - 1 Termenii rezultani, (0, 2, 8, 10), (2, 3, 10, 11), (3, 7, 11, 15) i (5, 7, 13, 15) se numesc implicani primi IP. 3. Se aleg acei implicani primi IP care asigur acoperirea minimal a termenilor19

20

canonici TC. Pentru aceasta se construiete un tabel de acoperire, n care pe coloane se noteaz termenii canonici TC, iar pe linii implicanii primi IP. n intersecii se noteaz acei termeni canonici TC acoperii de fiecare implicant prim IP. IP 0 2 3 5 7 8 10 TC 11 13 15 0, 2, 8, x x x x 10 2, 3, 10, x x x 11 x 3, 7, 11, x x 15 x x 5, 7, 13, x x 15 x x Unii dintre implicanii primi sunt implicani primi eseniali pentru c acoper cel puin un termen canonic al funciei, care nu este acoperit de alt implicant prim. Implicanii primi eseniali vor face parte n mod obligatoriu din expresia minimizat a funciei. n cazul nostru implicani primi eseniali sunt (0, 2, 8, 10) i (5, 7, 13, 15). Pentru termenii canonici care au rmas neacoperii, 3 i 11, se observ c pot fi alei 2 implicani primi, (2, 3, 10, 11) i (3, 7, 11, 15), deci exist 2 soluii de minimizare. f = (0, 2, 8, 10) + (5, 7, 13, 15) + (2, 3, 10, 11) = x2x4 + x2x4 + x2x3 i20

21

f = (0, 2, 8, 10) + (5, 7, 13, 15) + (3, 7, 11, 15) = x2x4 + x2x4 + x3x41.4.4. Minimizarea sistemelor de funcii booleene

Sistemele de funcii booleene sunt exprimate prin f: Bn Bm unde B ={0, 1}. Argumentele pot fi de n variabile i sunt mai multe funcii de acest tip: f1, f2,, fm. Pentru a minimiza sistemele de funcii se caut implicani primi pentru f1, f2,, fm i pentru produsele f1 f2, f1 f3, f1 fm, f1 f2 f3, , f1 f2 f3 f4,, f1 f2 fm. Soluia aleas pentru implementarea sistemului de funcii booleene va fi cea care va fi cea mai avantajoas din punct de vedere al circuitelor disponibile i al preului. Exemplu: f1(x1,x2,x3) = (1, 5, 6, 7) f2(x1,x2,x3) = (1, 4, 5, 6) f3(x1,x2,x3) = (0, 2, 5, 6, 7) 1. Calculm funciile produs: f1 f2 = (1, 5, 6) f1 f3 = (5, 6, 7) f2 f3 = (5, 6) f1 f2 f3 = (5, 6), identic cu f2 f3 2. Determinm implicanii primi din funciile simple i din produsele determinate la punctul 1.21

22

Pentru determinarea implicanilor primi se folosesc diagrame Karnaugh n care se iau toate acoperirile posibile. Pentru f1:x1 x2x3 0 1 x1 x2x3 0 1 x1 x2x3 0 1 x1 x2x3 0 1 x1 x2x3 0 1 x1 x2x3 0 1 00 01 1 1 01 1 1 01 1 00 01 1 1 01 1 00 01 1 11 1 11 10 1 10 1

Pentru f2:00 1 00 1

Pentru f3:11 1 11 10 1 1 10 1 11 1 11 10 1 10 1

Pentru f1 f2: Pentru f1 f3:

00

Pentru f2 f3 i f1 f2 f3:

3. Construim un tabel n care capetele de linii vor reprezenta funciile, iar coloanele vor fi implicanii primi.

Funcia

Implicani primi22

23

Indici Expresii Notaii f1 1,5 x2x3 6,7 x1x2 5,7 x1x3 f2 1,5 x2x3 4,5 x1x2 i 4,6 x1x3 h f3 0,2 x1x3 g 2,6 x2x3 f 6,7 x1x2 5,7 x1x3 1,5 x2x3 e f1 f2 6 x1x2x3 5,7 x1x3 d f1 f3 6,7 x1x2 c 5 x1x2x3 b f2 f3 = 6 x1x2x3 a f1 f2 f3 4. Se noteaz IP pe coloana a patra din tabel ncepnd cu ultimul, iar cei care apar dublai nu se mai noteaz. 5. Se construiete un tabel al acoperirilor funciilor f1, f2, f3. Nota Indi Funci f1 f2 f3 ii cii a de 1 5 6 7 1 4 5 6 0 2 5 6 7 unde au rezulta t a 6 f1 f2 f x x x23

24

3

b

5 f1 f2 f3

x

x

x

c 6, 7 f1 f3 x x x x d 5, 7 f1 f3 x x x x e 1, 5 f1 f2 x x x x f 2, 6 f3 x x g 0, 2 f3 x x h 4, 6 f2 x x i 4, 5 f2 x x 6. Determinm acoperirile optime ale funciilor f1, f2, f3. A(f1) = e,c + e,d,a = A1 + A2 cu e implicant prim esenial A(f2) = e,h + e,i,a = B1 + B2 cu e implicant prim esenial A(f3) = g,c,b + g,c,d, + g,f,d + g,a,d = C1 + C2 + C3 + C4 cu g implicant prim esenial 7. Se scriu toate acoperirile posibile pentru sistemul de funcii i se alege acea acoperire care realizeaz condiiile de pre minim i disponibilitate de piese. Se face tabelul pentru acoperiri: Acoperiri A1B1C1 A1B1C2 A1B1C3 Elementele acoperirii e,c,h,g,b e,c,h,g,d e,c,h,g,f,d24

Numr de termeni 5 5 6

Co st 11 10

25

A1B1C4 e,c,h,g,a,d 6 A1B2C1 e,c,i,a,g,b 6 A1B2C2 e,c,i,a,g,d 6 A1B2C3 e,c,i,a,g,f,d 7 A1B2C4 e,c,i,a,g,d 6 A2B1C1 e,d,a,h,g,c,b 7 A2B1C2 e,d,a,h,g,c 6 A2B1C3 e,d,a,h,g,f 6 A2B1C4 e,d,a,h,g 5 11 A2B2C1 e,d,a,i,g,c,b 7 A2B2C2 e,d,a,i,g,c 6 A2B2C3 e,d,a,i,g,f 6 A2B2C4 e,d,a,i,g 5 11 Avem acoperiri minimale cu 5 termeni. Pentru a calcula costul unei acoperiri se face suma costurilor implicanilor primi din acoperirea considerat. Costul unui implicant prim de n variabile din care lipsesc r variabile este n-r, pentru c fiecare variabil prezent necesit un contact, o legtur.n-1

C = gr (n-r)r=0

unde gr este numrul subcuburilor din care lipsesc r variabile. Pentru acoperirea A1B1C2, care are elementele e,c,h,g,d, avem costul:2

25

26

C = gr (3-r) = g0 3 + g1 2 + g2 1 = 0 3 + 5 2 + 0 1 = 10r=0

e = x2x3 c = x1x2 h = x1x3 g = x1x3 d = x1x3 Minimizarea sistemului de funcii va fi: f1 = x2x3 + x1x2 f2 = x2x3 + x1x3 f3 = x1x3 + x1x3 + x1x2 = x1x2 + x1 + x3 Datorit reducerii corelate a sistemului de funcii apar pori comune mai multor funcii.Curs 4 CAPITOLUL II CIRCUITE LOGICE COMBINAIONALE2.1. DefiniiiCircuitele logice combinaionale, CLC, sunt un caz particular al sistemelor secveniale finite sau al automatelor finite, numite automate de grad 0. Circuitele logice combinaionale se caracterizeaz prin faptul c variabilele de ieire sunt independente de timp i de starea intern, fiind determinate numai de variabilele de intrare (starea variabilelor de intrare la momentul considerat). Legtura dintre starea ieirii i starea intrrii unui CLC este realizat de funcia de transfer. x1 y1 x2 y2 CLC xn ym

26

27

Oricare funcie de ieire y (y1, y2,, ym) este funcie de toate variabilele de intrare (x1, x2,, xn). Un CLC se poate descrie astfel: y1 = f1(x1, x2,, xn) y2 = f2(x1, x2,, xn) ym = fm(x1, x2,, xn) Funciile se vor exprima n forma canonic disjunctiv FCD sau n forma canonic conjunctiv FCC. Independena fa de timp presupune c o dat cu modificarea variabilelor de intrare se modific simultan i variabilele de ieire. Din punct de vedere practic, datorit ntrzierilor produse de circuitele logice i de conexiuni, modificarea simultan nu este posibil. Ca urmare, pe durata procesului tranzitoriu de stabilire a variabilelor de ieire, vectorul ieirilor poate lua valori intermediare diferite de valoarea final, ceea ce conduce la fenomenul de hazard combinaional, de care trebuie s se in cont la proiectarea unui sistem numeric. n general, la circuitele logice combinaionale, vom face abstracie de proprietile fizice ale porilor logice, de faptul c un impuls teoretic difer de unul real. Vom analiza aceste fenomene doar n cazul hazardului combinaional.

2.2. Analiza circuitelor logice combinaionalen cadrul analizei CLC se pleac de la cunoaterea schemei logice a circuitului i se urmrete stabilirea funcionrii acestuia. Stabilirea expresiei variabilei de ieire se face de la intrare la ieire, urmrind transformrile variabilelor de intrare. Definim ca numr de nivele al unui CLC numrul maxim de pori dintre intrri i ieiri. Numerotarea nivelelor se face de la ieire nspre intrare. x5 x1 x2 y1 x3 x4 y2 x6 x7 4 3 2 1

x1

Circuitul logic combinaional din exemplu are 4 nivele. Exist i urmtoarea situaie de legturi ntre pori: y27

28

x2 x3

Acest circuit are i legturi inverse. Ultimele pori nu pot fi numerotate, deci circuitul nu este un CLC. n CLC sunt admise legturile inverse (ieirea unei pori dintr-un nivel inferior s fie dus la intrarea unei pori dintr-un nivel superior) cu condiia ca definiia CLC s fie respectat.

Algoritm de determinare a legturilor inverse n CLCa. Se numeroteaz toate porile logice care au ca intrri un subset din mulimea variabilelor de intrare ale circuitului logic (de la 1 la k); b. Se numeroteaz de la k+1 porile care au ca intrri fie intrri ale circuitului, fie ieiri ale porilor numerotate la punctul a. Dac am reuit s numerotm toate porile circuitului logic, acesta este fr legturi inverse i este circuit combinaional. Dac nu am reuit numerotarea tuturor porilor logice, circuitul este de tip secvenial.

2.3. Sinteza circuitelor logice combinaionalen cadrul sintezei circuitelor logice combinaionale se cunoate funcia pe care trebuie s o ndeplineasc circuitul i se caut s se gseasc structura acestuia. Etapele sintezei circuitelor logice combinaionale sunt: 1. Enunul problemei; 2. Alctuirea tabelului de adevr, definirea funciei sau funciilor; 3. Minimizarea funciei sau funciilor; 4. Desenarea schemei circuitului Exist mai multe metode de implementare a CLC, difereniate dup nivelul de complexitate al circuitelor integrate folosite. 2.3.1. Sinteza CLC cu circuite integrate SSI Circuitele integrate de tip SSI small scale integration au pn la 50 de tranzistoare integrate pe capsul. Dintre aceste circuite fac parte porile logice fundamentale: SI-NU (NAND), SAU-NU (NOR), NU (NOT), SI (AND), SAU (OR), SAU-EXCLUSIV (XOR). Dup parcurgerea etapelor de sintez se face implementarea funciei sau funciilor logice cu ajutorul circuitelor integrate existente. CLC de tip SSI se folosesc mai mult pentru adaptarea la aplicaie a

28

29

circuitelor de tip MSI i LSI standardizate, care nu satisfac cu exactitate cerinele de proiectare. Ele vor fi utilizate acolo unde circuitele cu grad nalt de integrare nu pot fi folosite. 2.3.2. Sinteza CLC cu circuite integrate MSI Circuitele integrate de tip MSI medium scale integration au pn la 500 de tranzistoare integrate. Ele ofer structuri mai complexe, disponibile ca i structuri standard. Forma funciilor logice pe care dorim s le implementm cu circuite de tip MSI trebuie s fie corelat cu circuitele disponibile. De obicei nu mai este necesar minimizarea funciilor. Circuite combinaionale uzuale (specializate) 1. Convertoare de cod Convertoarele de cod sunt CLC care permit trecerea dintr-un cod binar n altul. La intrarea circuitului se aplic cuvintele unui cod i la ieire se obine alt cod. Convertoarele de cod fac compatibil funcionarea a 2 sisteme n care informaia este codificat n mod diferit. Exemplu: Conversiile din cod Gray n cod binar-zecimal (BCD) i invers 1) Cod Gray BCD Cuvintele de cod n cele dou coduri sunt: Gray: gn, gn-1,, g0 BCD: bn, bn-1,, b0 Reguli: bn = gn g3 g2 g1 g0 b3 b2 b1 b0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 1 0 0 1 1 1 1 0 1 0 0 0 1 1 1 1 Se construiesc diagrame Karnaugh pentru determinarea funciilor minimizate pentru b3, b2, b1, b0.29

30

Diagrama Karnaugh pentru b3: g3g2 g1g0 00 01 11 10 00 01 11 1 1 1 1 10 1 1 1 1 Obinem: b3 = g3 Diagrama Karnaugh pentru b2: g3g2 g1g0 00 01 11 10 00 01 1 1 1 1 11 10 1 1 1 1 Obinem b2 = g2g3 + g2g3 = g2 + g3 Diagrama Karnaugh pentru b1: g3g2 g1g0 00 01 11 10 00 1 1 01 1 1 11 1 1 10 1 1 Obinem b1 = g1g2g3 + g1g2g3 + g1g2g3 + g1g2g3 = g1(g2 + g3) + g1(g2 + g3) = g1 + g2 + g3 Diagrama Karnaugh pentru b0: g3g2 g1g0 00 01 11 10 00 1 1 01 1 1 11 1 1 10 1 1 Obinem b0 = g0g1g2g3 + g0g1g2g3 + g0g1g2g3 + g0g1g2g3 + g0g1g2g3 + g0g1g2g3 + g0g1g2g3 + g0g1g2g3 = g2g3(g0 + g1) + = g0 + g1 + g2 + g3 n general: bn = gni

bi =

1 0

dac + gj = 1j=n-1

dac nu

2) Conversia din BCD n Gray: gn = bn gi = bi + bi+1 2. Codificatoare30

31

Codificatoarele sunt CLC la care activarea unei intrri conduce la apariia unui cuvnt de cod la ieire. Exemplu: Codificator din zecimal n BCD (binar codificat zecimal) Zecimal BCD 3 0 1 2 3 4 5 6 7 8 9 2 22 21 20 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 Intrrile sunt active pe 0 logic. De exemplu, dac este activ (adic 0) intrarea 5, pe ieire se va obine codul n BCD pentru 5, adic 0101. Funciile pentru ieiri sunt: 23 = 8 9 22 = 4 5 6 7 21 = 2 3 6 7 20 = 1 3 5 7 9 Codificatorul prioritar este un codificator care are mai multe intrri active simultan i la ieire se obine cuvntul de cod care corespunde intrrii care este cea mai prioritar. Prioritatea crete de la cifra 0 nspre cifra 9. 3. Decodificatoare Decodificatoarele sunt CLC la care se activeaz doar una dintre ieiri, pentru combinaia (codul) corespunztoare a variabilelor de intrare. Ele au funcie invers codificatoarelor. Ieirile decodificatoarelor sunt active pe 0 logic (funcioneaz n logic negativ). I1 y1

Circuite SI-NUIn ym Numrul ieirilor distincte este m 2n. Exemplu: Decodificator pentru 3 cifre binare. I2 I1 I0 O7 O6 O5 O4 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 131

O3 1 1 1 0

O2 1 1 0 1

O1 1 0 1 1

O0 0 1 1 1

32

1 1 1 1

0 0 1 1

0 1 0 1

1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1

Funciile pentru ieiri sunt: O7 = I2I1I0; O6 = I2I1I0; O5 = I2I1I0; O4 = I2I1I0; O3 = I2I1I0; O2 = I2I1I0; O1 = I2I1I0; O0 = I2I1I0. 4. Multiplexoare Multiplexoarele sunt CLC care permit trecerea datelor de pe una din intrri la o ieire unic. Selecia intrrii se face printr-un cuvnt de cod de selecie numit i adres. I0

MUX In-1

y

sm-1 s0 Cu m linii de selecie se pot selecta 2m intrri. Funcia realizat de ieire este: y = Ik unde k este numrul de combinaii m-1 k = sm-1 2 + + s0 20 Aplicaiile cele mai importante ale MUX sunt la selecia secvenial a datelor, conversia paralel-serie a datelor, sisteme de transmisie a datelor pe un singur canal, implementarea circuitelor logice combinaionale cu o singur ieire. Exemple 1) I0 MUX y I1 2:1 s Multiplexorul de tip 2:1 are 2 semnale de intrare, I0 i I1, un semnal de selecie s i o ieire y. n funcie de semnalul de selecie avem pentru ieire: y = I0 s + I1 s. s=0 y = I0 s=1 y = I1

Deci multiplexorul las s treac spre ieire semnalul de pe acea linie de intrare corespunztoare lui s.I0

2)

32

33

I1I2 I3

MUX4:1 y

s0 s1 Multiplexorul de tip 4:1 are 4 semnale de intrare, 2 semnale de selecie i un semnal de ieire. Ieirea va fi: y = I0 s0 s1 + I1 s0 s1 + I2 s0 s1 + I3 s0 s1 Exist multiplexoare de tip 8 : 1, 16: 1, 32 : 1. Multiplexoarele integrate au disponibile att ieirea adevrat ct i cea negat. Ele au i o intrare de Enable pentru validare, care permite o funcie SI suplimentar. 5. Demultiplexoare Demultiplexoarele sunt CLC care permit transmiterea datelor de pe o intrare de date comun pe una din ieirile selectate. Selectarea ieirii se face cu ajutorul unui cuvnt de cod de selecie numit i adres. y0

I

DEMUX yn-1sm-1 s0

Cu m linii de selecie se pot selecta 2m ieiri. Funciile de ieire sunt: y0 = sm-1 s0 I y1 = sm-1 s0 I y2m = sm-1 s0 I 6. Comparatoare numerice Comparatoarele numerice sunt CLC care permit determinarea valorii relative a dou numere binare. Comparatoarele pot fi de 1 bit sau de mai muli bii. Exemplu: Comparator pe 1 bit Ai y1 y2 Bi y3 Funciile de ieire sunt: y1 = Ai Bi pentru Ai < Bi, y2 = Ai + Bi pentru Ai = Bi y3 = Ai Bi pentru Ai > Bi33

34

Acest circuit constituie celula de baz pentru compararea numerelor cu mai muli bii. 7. Detectoare-generatoare de paritate Detectoarele-generatoare de paritate sunt CLC cu rol de a determina i genera paritatea sau imparitatea numrului de variabile de intrare egale cu 1. Bitul de paritate este utilizat ca metod de verificare a transferului de date. Sunt posibile 2 situaii: a. numrul biilor de 1 + bitul de paritate = numr par b. numrul biilor de 1 + bitul de paritate = numr impar Realizarea detectoarelor de paritate se bazeaz pe funcia logic SAUEXCLUSIV (0 pentru par i 1 pentru impar). 8. Sumatoare-scztoare Sumatoarele i scztoarele sunt CLC care realizeaz adunarea, respectiv scderea cifrelor binare. Semisumatorul este un CLC care efectueaz suma a 2 numere binare de cte 1 bit, fr a ine cont de transportul de la bitul de semnificaie imediat inferioar. Semisumatorul este: A0 S0 1/2 B0 C0 Valorile pentru suma S0 i transportul spre rangul superior C0 sunt: S0 = A0 B0 + A0 B0 = A0 + B0 C0 = A0 B0 Sumatorul pentru bitul de rang n este: An Sn Cn-1 Bn Cn Valorile pentru suma Sn i transportul Cn pentru rangul superior sunt: Sn = An Bn Cn-1 + An Bn Cn-1 + An Bn Cn-1 + An Bn Cn-1 = = (An + Bn) Cn-1 + (An + Bn) Cn-1 = An + Bn + Cn-1 Cn = An Cn-1 + Bn Cn-1 + An Bn Sumatoarele pentru cuvinte binare cu mai muli bii se realizeaz prin interconectarea sumatoarelor pentru 1 bit. Adunarea se efectueaz n paralel, iar propagarea transportului n serie. Semiscztorul de 1 bit are ieirile: D0 = A0 B0 + A0 B0 = A0 + B0 I0 = A0 B0 Scztorul complet de rangul n are ieirile:

34

35

Dn = An Bn In-1 + An Bn In-1 + An Bn In-1 + An Bn In-1 = =(An + Bn) In-1 + (An + Bn) In-1 = An + Bn + In-1 In = An In-1 + Bn In-1 + An Bn Scztoarele pentru cuvinte binare cu mai muli bii se realizeaz prin interconectarea scztoarelor pentru 1 bit. 9. Uniti aritmetico-logice Unitile aritmetico-logice sunt CLC care realizeaz operaii de tip aritmetic i operaii de tip logic.

Curs 52.3.2.1. Implementarea funciilor booleene cu circuite MSI Circuitele integrate de tip MSI cum sunt decodificatorul DCD, demultiplexorul DEMUX i multiplexorul MUX pot fi considerate circuite universale deoarece genereaz n interior toi termenii canonici. Implementarea cu DCD a unei funcii booleene nu necesit operaii de minimizare. La ieirea DCD se obin toi termenii canonici negai ai formei canonice disjunctive FCD ai funciei. Realizarea funciei se face cu o poart logic de tip SI-NU, cu un numr de intrri egal cu numrul de termeni ai funciei. Implementarea cu MUX a unei funcii booleene se bazeaz pe relaia care definete funcionarea sa. De exemplu, pentru un MUX de tip 4:1 avem ecuaia ieirii: y = I0 x1 x2 + I1 x1 x2 + I2 x1 x2 + I3 x1 x2 n care se observ c exist intrri separate pentru fiecare din cele 4 combinaii ale variabilelor de selecie x1, x2. Dac avem o funcie boolean de n variabile de intrare se pot da factor variabilele x1 i x2 i se obin 4 funcii de n-2 variabile de intrare, care se vor conecta la intrrile I0 I3 ale unui MUX de tip 4:1. Similar, cu un MUX 8:1 se pot elimina 3 variabile de intrare, iar cu un MUX 16:1 se pot elimina 4 variabile de intrare. Dac avem o funcie de 4 variabile se pot elimina 3 variabile prin aplicarea lor pe intrrile de selecie ale unui MUX 8:1. La cele 8 intrri ale MUX se vor conecta cele 8 funcii de o variabil. Singurele funcii posibile de o variabil sunt: xi, xi, 0, 1. Deci putem implementa orice funcie cu 4 variabile de intrare folosind un singur MUX de 8 ci i fr pori adiionale. Exemplu Considerm funcia: f = (0, 1, 3, 5, 9, 10, 13, 15) = x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0 Folosim un MUX 8:1 i aplicm variabilele x2x1x0 pe intrrile de selecie. Pentru a determina intrrile multiplexorului, I0 I7, vom face un tabel:35

36

I0 I1 I2 I3 I4 I5 I6 I7

x3 1 x3 x3 0 1 0 x3

x2x1x0 (x3 + x3) x2x1x0 x2x1x0 x2x1x0 x2x1x0 (x3 + x3) x2x1x0 x2x1x0 x2x1x0

Implementarea funciei cu MUX este: En x3 1 x3 x3 f 0 f 1 0 x3 s2 s1 s0 x2 x1 x0 Avantajele implementrii cu MUX: - se poate implementa funcia cu un sigur circuit de tip MUX; - intrarea de Enable poate fi folosit ca un SI final cu ntreaga funcie; - doar o singur variabil trebuie s fie disponibil i adevrat i negat. Dezavantajele implementrii cu MUX: - nu se pot folosi termeni n comun n cazul minimizrii sistemelor de funcii (sisteme cu mai multe ieiri); - nu se poate face implementarea funciilor la care numrul de termeni este mai mare dect numrul intrrilor MUX; - exist multe funcii care pot fi implementate comod prin utilizarea de pori logice MUX utilizat doar pentru funcii dificile. Procedura de implementare cu MUX se poate face plecnd de la diagrama Karnaugh. Se construiete o diagram Karnaugh n care se definete domeniul intrrilor I. x1x0 00 01 11 10 00 I0 I1 I3 I2 01 I4 I5 I7 I6 11 I4 I5 I7 I636

x3x2

37

10 x3x2 x1x0 00 01 11 10

I0 00 1

I1 01 1 1 1 1

I3 11 1 1

I2 10

1

Variabila care variaz este x3. Configuraiile de 1 din diagrama Karnaugh indic modul de conectare a intrrilor MUX, la x3, x3, 1 sau 0. I0 = x3; I1 = 1; I2 = x3; I3 = x3; I4 = 0; I5 = 1; I6 = 0; I7 = x3 2.3.3. Sinteza CLC cu circuite integrate LSI Circuitele integrate de tip LSI Large Scale Integration au peste 500 de tranzistoare integrate pe capsul. Pentru exemplificarea sintezei CLC se descriu dou tipuri de circuite din aceast categorie: ROM (Read Only Memory) i PLA (Programmable Logic Array), cu varianta FPLA. 2.3.3.1. Sinteza CLC cu memorii de tip ROM Memoria de tip ROM este numit i memorie fix sau permanent. Ea este nevolatil, coninutul ei nu se modific n timpul funcionrii. Structura ei este stabilit n procesul de fabricaie sau este stabilit de utilizator prin programare. I0 O0 DCD In-1 Matrice Om-1

Memoria ROM este format din dou niveluri de pori logice: SI (un decodificator) i SAU-NU (matricea de memorie). DCD din primul nivel primete codurile de intrare n binar (n este numrul intrrilor) i activeaz pentru fiecare cod o ieire din cele 2n. Ieirile DCD se conecteaz sau nu se conecteaz la circuitele de tip SAU-NU i astfel se memoreaz un 0 sau un 1 logic. Vectorii de intrare n ROM se numesc adrese i reprezint codurile n binar ale numerelor asociate fiecrui cuvnt de memorie. Ieirile sunt de obicei three-state sau open colector pentru a permite legarea n paralel cu ieirile altor memorii. Avem notaiile: n = numrul de bii ai vectorului de intrare (adresa) c = numrul de cuvinte memorate n ROM c = 2n b = numrul de bii din fiecare cuvnt Numrul de cuvinte trebuie s fie putere a lui 2. Modul de organizare a ROM este specificat prin produsul c x b. Capacitatea37

38

memoriei se exprim prin numrul total de bii memorai: C = 2n x b. Unitatea de msur pentru capacitatea memoriei este kilobitul (1 Kb = 1024 bii). Memoriile au o intrare de Enable care permite (E = 0) sau inhib (E = 1) funcionarea ROM. Dac memoria este dezactivat, indiferent de adresare, ieirile sunt pe semnal logic 1. Aplicaiile mai importante ale memoriilor de tip ROM sunt: - memorarea instruciunilor i datelor n sisteme de calcul i automate secveniale; - transformri de adres i nmagazinarea instruciunilor n microprogramare; - conversii de cod; - generatoare de caractere; - generare de secvene de impulsuri; - implementarea CLC cu un numr mare de variabile de intrare i ieire. Implementarea CLC cu un numr mare de variabile de intrare i ieire se bazeaz pe structura intern a memoriei ROM. Pe nivelul de DCD se decodific toi termenii canonici. Fiecare cuvnt de la intrarea matricei reprezint de fapt un termen canonic format din variabilele de intrare. La nivelul urmtor se adun toi termenii din expresia oricrei funcii i rezult funcia de ieire. Lista de cuvinte din ROM este chiar tabelul de adevr al CLC. La implementarea cu ROM nu este necesar minimizarea, deoarece sunt memorai toi termenii canonici i sunt incluse toate posibilitile de apariie a acestora n funcia de ieire. Pentru folosirea eficient a memoriei ROM n sinteza funciilor booleene, variabilele de intrare i ieire trebuie codate, astfel nct s conin ct mai mult informaie. Se poate codifica orice grup de variabile care sunt mutual exclusive, adic doar una dintre ele poate fi activ la un moment dat. Pentru reducerea numrului de intrri n ROM se utilizeaz des i multiplexoarele. Exemplu: S se implementeze cu ROM funciile: f0(x3,x2,x1,x0) = x3 x2 x1 x0 f1(x3,x2,x1,x0) = x2 x1 f2(x3,x2,x1,x0) = x3 x2 x1 x0 + x3 x2 x0 + x3 x2 x0 + x2 x1 Memoria folosit este de tipul: x3 A338

39

x2 x1 x0

A2 A1 A0

16 x 4 bii CS D3D2D1D0

f2 f1 f0 Cu A s-au notat intrrile de adrese, cu D datele i cu CS (chip select), intrarea de Enable a circuitului. Coninutul nscris n memorie este dat n tabelul urmtor: A2 A1 A0 D3 f1 f0 A3 f2 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0

Scopurile urmrite la implementarea cu ROM sunt: - utilizarea unui numr minim de circuite integrate; - folosirea integral a capacitii memoriei. Pentru implementarea CLC cu memorii ROM trebuie urmrite urmtoarele etape: - stabilirea dimensiunii memoriei necesare pentru aplicaia respectiv; - alegerea tipurilor de circuite de tip ROM cu dimensiuni identice sau ct mai apropiate de cele stabilite anterior; - dac nu exist memorii cu dimensiuni identice sau apropiate de cele dorite se fac transformri de dimensiuni (modificarea numrului de cuvinte sau numrului de bii pe cuvnt); - stabilirea tabelului de adevr al ROM;

39

40

- reducerea dimensiunii ROM atunci cnd este posibil prin utilizarea codificrii intrrilor sau ieirilor i a multiplexrii intrrilor. 2.3.3.2. Sinteza CLC cu PLA PLA (Programmable Logic Array) este un CLC cu dou nivele de logic programabil, o matrice de pori SI i o matrice de pori SAU. PLA este de fapt o structur universal, extins, de implementare cu 2 nivele de pori logice. Ambele matrici sunt programabile, n procesul de fabricaie sau de ctre utilizator, conform aplicaiei concrete. PLA este o structur mobil i se utilizeaz eficient pentru sisteme cu mai mult de 8 variabile de intrare. Deoarece la PLA sunt programabile ambele nivele, implementarea se face pornind de la termenii elementari ai funciei, obinui prin minimizarea ei. Reprezentarea schematic a PLA cu n intrri, m ieiri i p termeni elementari realizabili este: x1 conexiune programabil x2

xn Matrice SI 1 conexiune programabil p 1 Matrice SAU fm m conexiune programabil CS Avantajele implementrii cu PLA fa de implementarea cu ROM se refer la posibilitatea programrii matricei SI i a complementrii variabilelor de ieire (variabilele de ieire pot fi programate individual ca active pe 0 sau pe 1). Aplicaii ale PLA sunt la:40

f1

41

- microprogramare; - conversii de cod; - generare de caractere; - realizare de tabele de funcii; - implementarea automatelor secveniale. Observaie. Exist circuite integrate cu grad i mai mare de integrare (VLSI) utilizate n implementare. Amintim dintre acestea FPGA (Field Programmable Gate Array).

2.4. Hazardul combinaionalDatorit ntrzierilor produse de circuitele logice i de firele de legtur ale unui CLC se poate ca starea ieirii circuitului n momentul modificrii strii variabilelor s nu coincid cu valoarea funciei corespunztoare valorii intrrilor n momentul considerat. Pentru timp scurt circuitul are o comportare greit, numit hazard. Exemplu f(x1,x2,x3) = x1 x3 + x2 x3 x1 1 f x3 g 3 f x2 2 x3 h Diagrama Karnaugh pentru funcie este: x1 x2x3 00 01 11 10 0 1 1 1 1 1 n practic ntrzierile 1, 2, 3 ale porilor SI-NU nu sunt egale, de aceea poate s apar hazardul combinaional i cnd se pune condiia ca doar o singur variabil de intrare s se modifice la un moment dat. Hazardul apare atunci cnd starea intrrilor x1x2x3 se modific de la 010 la 011 sau invers. x1 x2 x31

41

42

g h f f tr3

2

dei starea ar trebui s fie nemodificat. Dup timpul de reacie tr = 1 + 2 va apare la ieire un impuls negativ de durat t = 2 1 i n aceast durat ieirea ia o valoare incorect. Eliminarea hazardului static se poate face n cazul n care se impune ca la un moment dat s se modifice starea unei singure variabile de intrare. Pentru realizarea funciei se consider i unii termeni redundani din diagrama Karnaugh, astfel nct oricare doi de 1 aflai n csue adiacente n diagram s fie inclui cel puin ntr-un contur luat n considerare la sinteza schemei.2 1

>

Pentru exemplul dat se va introduce n expresia funciei termenul x1x2. f = x2 x1 + x3 x1 + x3 x2 x1 x3 x2 x3 x1 g h 1

f2

3

f

i t42

43

x2 x1 x2 x3 g h i f f Observaii 1. Hazardul static poate s apar i cnd 1 > 2, la schimbarea 011 n 000. 2. Proiectarea unui CLC cnd se schimb mai mult dect o singur variabil de intrare la un moment dat, fr s apar hazard, este mai dificil sau chiar imposibil de realizat (hazard de funcie). 3. Eliminarea sigur a hazardului se poate face lund n considerare ieirea circuitului dup un interval de timp mai mare dect ntrzierea maxim din circuit.1

2

Curs 6 CAPITOLUL III CIRCUITE LOGICE SECVENIALE

Circuitele logice secveniale, CLS, sunt automate de ordinul 1. Se obin din automatele de ordinul 0 (CLC) prin introducerea unor reacii (legturi inverse). Sunt alctuite din circuite logice combinaionale i elemente de memorare binar.43

44

Semnalele de ieire ale CLS depind att de combinaia semnalelor aplicate pe intrri ct i de starea circuitului. Un CLS este caracterizat printr-o secven a semnalelor de ieire i o secven a strilor elementelor de memorie, pentru fiecare secven a semnalelor aplicate pe intrrile circuitului.Dup modul de funcionare (modul de transmitere a semnalelor) exist 2 categorii principale de CLS: 1. asincrone comportarea este determinat de aplicarea pe intrri a semnalelor n momente oarecare; starea circuitului depinde de ordinea n care se schimb semnalele; 2. sincrone comportarea este determinat de aplicarea pe intrri a semnalelor n momente discrete, bine determinate n timp; sincronizarea se realizeaz cu ajutorul unor impulsuri date de un generator de tact (ceas). Exemple de CLS: bistabili, numrtoare, registre, memorii RAM.

3.1. Circuite basculante bistabileDefiniie. Circuitele basculante bistabile (CBB sau bistabil) sunt circuite logice secveniale care au dou stri stabile distincte. Trecerea dintr-o stare n alta se face la aplicarea unei comenzi din exterior. Caracteristica principal a CBB este c sunt sisteme cu memorie (elemente de memorie binar). Un bistabil poate pstra un timp nedefinit informaia binar i n acelai timp starea sa poate fi citit n orice moment. Se asociaz uneia dintre cele 2 stri ale bistabilului funcia de memorare a cifrei binare 1 i celei de a doua stri funcia de memorare a cifrei binare 0. Bistabilul are 2 ieiri, una care pune n eviden cifra binar memorat, numit ieire adevrat i a doua, care pune n eviden valoarea negat a cifrei binare memorate, denumit ieire negat. 3.1.1. Bistabilul RS asincron (latch) Bistabilul RS asincron are 2 intrri de comand (de date): S (Set) i R (Reset) i dou ieiri Q i Q (complementare). Simbolul bistabilului RS asincron este: S Q R Q

44

45

Tabelul de adevr al bistabilului RS asincron este: tn tn+1 Sn Rn Qt+1 0 0 Qt 1 0 1 0 1 0 1 1 Din punct de vedere logic nu are sens s se fac simultan nscrierea i tergerea informaiei, ca urmare Sn = 1 i Rn = 1 va fi o situaie interzis (de nedeterminare, pentru c nu se poate prevedea starea final). Condiia de bun funcionare care se pune este Sn Rn = 0. Pentru a face sinteza circuitului vom considera semnalul de ieire Qt+1 la momentul tn+1, semnal care depinde de starea intrrilor Sn i Rn i de starea Qt, la momentul tn. Vom scrie Qt+1 ca o funcie de 3 variabile: Qt 0 0 0 0 1 1 1 1 Sn 0 0 1 1 0 0 1 1 Rn 0 1 0 1 0 1 0 1 Qt+1 0 0 1 1 0 1

Diagramele Karnaugh pentru Qt+1 i Qt+1 sunt urmtoarele: Qt+1: Qt SnRn 00 01 11 10 0 0 0 x 1 1 1 0 x 1 Qt+1: Qt SnRn 0 1 00 1 0 01 1 1 11 x x 10 0 0

Dac minimizm funciile n FCC obinem: Qt+1 = Rn (Sn + Qt) Qt+1 = Sn (Rn + Qt)45

46

Deducem funciile pentru schema cu pori de tip SAU-NU: Qt+1 = Qt+1 = Rn (Sn + Qt) = Rn + (Sn + Qt) Qt+1 = Qt+1 = Sn (Rn + Qt) = Sn + (Rn + Qt) R Q

S

Q

Schema bistabilului RS asincron realizat cu pori de tip SI-NU se bazeaz pe funciile n forma FCD obinute din diagramele Karnaugh: Qt+1 = Sn + (Qt Rn) Qt+1 = Rn + (Qt Sn) Qt+1 = Sn + (Qt Rn) = Sn (Qt Rn) Qt+1 = Rn + (Qt Sn) = Rn (Qt Sn) S Q

R46

Q

47

Pentru Sn = Rn = 1 rezult Q = 0 i Q = 0, cele dou ieiri nefiind complementare. Circuitul i pierde n acest caz caracterul de circuit bistabil, cu dou stri distincte stabile. Bistabilul RS asincron este cel mai simplu element de memorare care poate fi realizat cu circuite logice elementare. Observaie. O aplicaie tipic a bistabilului RS asincron este utilizarea acestuia la eliminarea oscilaiilor ce apar la contactele mecanice.

3.1.2. Bistabilul RS sincron (latch cu ceas) Bistabilul RS sincron se obine din bistabilul RS asincron prin adugarea unor pori logice suplimentare cu scopul de a rspunde la semnalele de intrare R i S numai sub aciunea unui semnal de comand numit impuls de tact (ceas). Sa S Q CLK R Ra47

Q

48

Ieirile bistabilului RS sincron se modific doar cnd semnalul de tact (ceas) CLK este activ. Simbolul bistabilului RS sincron este: S Q CLK R Q Diagrama de timp pentru bistabilul RS sincron este: CLK R S Q Funcionarea este descris de funciile: Qt+1 = S + R Qt Qt+1 = R + S Qt S R=0 i la acest bistabil situaia intrrilor n care S = R = 1 introduce o nedeterminare, de aceea ea trebuie evitat. Ct timp CLK este 0, intrrile de date nu influeneaz bistabilul. Cnd CLK = 1 bistabilul urmrete modificrile intrrilor de date. Cnd CLK redevine 0 bistabilul se zvorte (de aceea48

49

se numete latch), pstreaz informaia avut anterior pe ieire. Introducem noiunea de funcie de excitaie, caracteristic pentru fiecare bistabil. Ea pune n eviden cum trebuie s fie intrrile bistabilului (ce stare trebuie s aib) pentru a se realiza o tranziie specific. Tabelul de excitaie pentru bistabilul RS sincron este: Qt Qt+1 R S 0 0 x 0 0 1 0 1 1 0 1 0 1 1 0 x Observaie. n afara intrrilor sincrone, la bistabilul RS sincron se introduc i intrri asincrone, Ra i Sa, la nivelul bistabilului RS asincron (porile SI-NU). Aceste intrri sunt utilizate cu scopul forrii la 0, prin Ra, sau la 1, prin Sa, a ieirii bistabilului. Apariia unor comenzi pe aceste intrri se execut independent de prezena sau absena tactului. Din acest motiv intrrile asincrone ale unui bistabil sunt prioritare n raport cu intrrile sincrone. 3.1.3. Bistabilul D sincron (delay) Bistabilul D sincron are o singur intrare, D i cele 2 ieiri complementare, Q i Q. Starea urmtoare a bistabilului D este determinat de49

50

modificarea intrrii D. El ntrzie cu un tact informaia pe care o primete pe intrare (circuit elementar de ntrziere). Sunt cele mai rspndite bistabile n registrele de date. Simbolul bistabilului D sincron: S D Q CLK Q R Bistabilul D se obine din bistabilul RS sincron: D Q CLK Q Funciile bistabilului D sunt: Qt+1 = D Qt+1 = D Tabelul de adevr al bistabilului D este: D Q 0 0 1 1 Tabelul de excitaie al bistabilului D este: Qt Qt+1 D50

51

0 0 0 0 1 1 1 0 0 1 1 1 Starea urmtoare a bistabilului de tip D sincron este dependent doar de semnalul aplicat pe intrare, ea fiind independent de starea actual a bistabilului. Exist dou tipuri de bistabile de tip D sincron, unele care comut pe front (atunci cnd se schimb tactul) i altele care comut pe nivel (atunci cnd tactul este pe nivel). 3.1.4. Bistabilul JK sincron Bistabilul JK sincron elimin situaia de nedeterminare pe ieiri, prezent la bistabilul RS sincron, la combinaia S = R = 1 pe intrri. Se folosesc reacii (legturi inverse) suplimentare. Tabelul de adevr al bistabilului JK sincron este: J K Qt+1 0 0 Qt 0 1 0 1 0 1 1 1 Qt Tabelul de excitaie al bistabilului JK sincron este: Qt Qt+1 J K51

52

0 0 1 1

0 1 0 1

0 1 x x

x x 1 0

Funciile pentru bistabilul de tip JK se determin din diagrama Karnaugh, pe baza tabelului de adevr n forma detaliat: Qt J K Qt+1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0Qt+1: Qt JK 0 1 00 1 01 11 1 10 1 1

Qt+1 = J Qt + K Qt Qt+1 = J Qt + K Qt Un bistabil de tip JK sincron se obine din bistabilul RS sincron prin efectuarea legturilor care permit eliminarea condiiei R S = 0. R = K Qt S = J Qt52

53

Q J CLK sau K Q

S J CLK K R Intrrile S i R sunt intrrile asincrone, care acioneaz la ultimul nivel de pori logice, nu depind de semnalul de tact i sunt prioritare fa de intrrile sincrone J i K (adic n momentul n care una dintre ele se activeaz, bistabilul va funciona n regim asincron). Simbolul utilizat pentru bistabilul JK sincron este: J53

Q

Q

S Q

54

CLK K Q R O analiz mai atent a bistabilului JK sincron arat c att timp ct intrarea de tact (CLK) rmne pe 1 logic dup stabilirea noii stri, bistabilul intr n oscilaie (i tot schimb starea). Pentru a exista o singur comutare, durata impulsului pe CLK trebuie s fie mai mare dect timpul de propagare a semnalului printr-o poart logic i mai mic dect timpul de propagare a semnalului prin dou pori logice. 3.1.5. Bistabilul T sincron (Toggle) Bistabilul T sincron se obine din bistabilul JK sincron prin legarea intrrilor J i K mpreun. Bistabilul schimb starea (comut) cnd pe intrare are semnal logic 1. S T CLK Q R Q

54

55

Tabelul de adevr al bistabilului T sincron este: T Qt+1 0 Qt 1 Qt Tabelul de excitaie al bistabilului T sincron este: Qt Qt+1 T 0 0 0 0 1 1 1 0 1 1 1 0 Pentru determinarea funciilor bistabilului T sincron utilizm diagrama Karnaugh de 2 variabile:Qt T 0 1 0 1 1 1

Qt+1 = T Qt + T Qt = T + Qt Qt+1 = T Qt + T Qt = T + Qt = T Qt Bistabilul T sincron are aceleai deficiene ca i bistabilul JK sincron, legate de durata impus a semnalului de tact. Bistabilul T sincron este util n aplicaiile de numrtoare binare. Concluzie. Deficiena principal a structurilor de bistabile studiate este c nu se poate face o distincie net ntre intrrile care condiioneaz55

56

momentul comutrii i cele care determin modul comutrii (nu se face distincie net ntre cnd i cum). 3.1.6. Bistabile master-slave MS Bistabilele de tip master-slave introduc un tip de structur care permite rezolvarea comutrii bistabilelor. Acest principiul masterslave poate fi aplicat oricrui circuit bistabil. Structura master-slave este compus din 2 celule de memorie, una master i cealalt slave. Master S R SM QM CLK RM QM CLK Impulsul de tact are dou fronturi, unul pozitiv (de urcare de la 0 la 1, n logica pozitiv) i unul negativ (de coborre de la 1 la 0, n logica pozitiv). La bistabilele master-slave pe frontul cresctor al semnalului de tact se face nscrierea informaiei n master, slave fiind practic deconectat. Pe frontul descresctor urmtor se56

Slave SS QS Q CLK RS QS Q

57

face transferul informaiei din master n slave i informaia va apare la ieiri dup frontul descresctor al impulsului de tact. Se asigur astfel o bun separare ntre intrrile de date i ieirile bistabilelor. S 1 3 Q

2 R CLK M 2 1 Q

4

Q

S 3 4

CLK

5

tS tH tS este timpul de set-up = perioada n care datele trebuie s fie pregtite nainte de impulsul de tact. tH este timpul de holding. Pe perioada 1 2 a impulsului de ceas, porile de la intrare nu sunt nc deschise, iar

57

58

porile 3,4 se blocheaz i astfel izoleaz slave de master. Pe zona 2 3 porile de intrare 1,2 se deschid i informaia trece n master. Porile 3,4 sunt nchise i slave i pstreaz vechea informaie. Pe zona 3 4 porile 1,2 se nchid i porile 3,4 nu se deschid nc: master este izolat de intrare i de slave. Pe perioada 4 5 porile 3,4 se deschid, n timp ce porile 1,2 sunt blocate i informaia apare pe ieire. Perioada critic este cea de meninere a datelor la intrare, tH, pe perioada 4 5. Memorarea se face pe frontul descresctor al impulsului de tact.Curs 73.2. Aplicaii ale circuitelor basculante bistabile3.2.1. Numrtoare Numrtoarele sunt circuite logice secveniale care nregistreaz numrul de impulsuri aplicate la intrare. Ele se realizeaz prin asocierea circuitelor basculante bistabile, avnd rol de celule de memorie binar, cu circuite logice combinaionale, care determin modul corect n care urmeaz ca numrtorul s-i schimbe starea la fiecare nou impuls aplicat la intrare. Clasificare Clasificarea numrtoarelor se face dup anumite criterii: 1. modul de funcionare (comutare a bistabililor): - asincrone celulele de memorie din care este construit numrtorul nu comut simultan ci aleator;

58

59

- sincrone celulele de memorie din care este construit numrtorul comut simultan sub aciunea unui impuls de tact aplicat simultan tuturor celulelor. 2. modul de modificare a strilor (coninutului): - directe i cresc coninutul cu o unitate la fiecare impuls aplicat la intrare; - inverse coninutul scade cu o unitate la fiecare impuls aplicat la intrare; - reversibile numr direct sau invers, n funcie de o comand aplicat din exterior. 3. modul de codificare a informaiei: - binare - binar-zecimale - modulo p etc. Numrtoarele se pot realiza cu celule de memorie de tip T care realizeaz o divizare cu 2. Prin interconectarea a n celule de memorie se obine un numrtor cu un numr de stri distincte. Fiecrei stri i vom asocia cte un cuvnt de cod binar de lungime n, reprezentnd coninutul celor n celule binare pentru starea dat a numrtorului. Codul n care numr un numrtor va fi dat de succesiunea cuvintelor de cod binar asociate strilor numrtorului. Numrul strilor stabile distincte posibile ale unui numrtor format din n celule binare este 2n. Dac din aceste stri se elimin k stri rezult un numrtor cu p = 2n k stri distincte. Matematic, operaia realizat de numrtor este o operaie modulo p. Definiii: Capacitatea numrtorului = numrul strilor sale distincte. Factorul de divizare = raportul dintre numrul de impulsuri de la intrare i numrul impulsurilor de la ieire. Observaie. Un numrtor funcioneaz de fapt i ca un divizor de frecven. Tipuri de numrtoare 1. Numrtor binar asincron direct Schema logic a numrtorului este realizat prin conectarea n cascad a bistabililor de tip JK n configuraie de bistabili de tip T: Q0 Q1 Q2 J0 Q0 CLK0 K0 Q0 J1 Q1 CLK1 K1 Q1 J2 Q2 CLK2 K2 Q2

59

60

1

1

1

R

Q0, Q1, Q2, ieirile numrtorului, ne dau starea lui la un moment dat. R este semnalul de Reset, folosit pentru aducerea numrtorului n starea iniial, la 000. Intrrile bistabililor JK sunt toate legate la 1 logic, deci bistabilii vor comuta la fiecare impuls de tact. Tact exterior se aplic doar pe intrarea primului bistabil. Formele de und pentru numrtorul binar asincron direct sunt: CLK Q0 Q1 Q2 Q2 Q1 Q0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Numrtorul este modulo 8, numrnd direct n binar, de la 000 la 111. El basculeaz pe fronturile descresctoare ale impulsurilor de tact.Dac dorim s obinem valorile numrului n zecimal putem utiliza ieirile numrtorului, Q0, Q1, Q2, ca i intrri ntr-un decodificator binar zecimal. Dezavantajul numrtorului asincron este c timpul de comutare, n cel mai defavorabil caz, este egal cu suma timpilor de comutare a tuturor bistabililor care l compun. Avantajul lui const n simplitatea schemei, realizat doar cu bistabile, prin interconectri directe. 2. Numrtor binar asincron invers Schema logic a numrtorului este: Q0 Q1 Q2 J0 Q0 CLK0 K0 Q0 1 160

J1 Q1 CLK1 K1 Q1 1

J2 Q2 CLK2 K2 Q2 R

61

Formele de und pentru numrtorul binar asincron invers sunt: CLK Q0 Q1 Q2 Q2 Q1 Q0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0

Numrtorul este modulo 8, numrnd invers n binar, de la 111 la 000. El basculeaz pe fronturile descresctoare ale impulsurilor de tact.3. Numrtor binar asincron reversibil Numrtorul binar asincron reversibil are celula de memorie de baz ca i numrtoarele asincrone anterioare, dar ntre celulele de memorie se intercaleaz multiplexoare de tip 2:1 prin care se comand sensul de numrare. Q0 Q1 Q2 J0 Q0 CLK0 K0 Q0 1 S A Mux 2:1 Y B 1 J1 Q1 CLK1 K1 Q1 A Mux 2:1 Y B 1 J2 Q2 CLK2 K2 Q2 R

Pentru S = 0 numrtorul numr direct, iar pentru S = 1 numrtorul numr invers. 4. Numrtor binar sincron serie i paralel Realizarea numrtoarelor de tip sincron are ca scop creterea vitezei de comutare a numrtorului n ansamblu. Funcionarea acestor numrtoare este sincron, bistabilii, de tip JK, avnd intrrile de CLK legate mpreun. Pe baza tabelului de adevr se obine logica combinaional suplimentar, care asigur funcionarea corect a numrtorului.61

62

Nr. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Q0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Q1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

Q2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

Q3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

Schema logic pentru numrtorul binar sincron serie este: Q0 1 S J Q CLK K Q R Reset Intrrile J i K ale primului bistabil sunt legate la 1 logic i vor comuta bistabilul la fiecare tact (conform tabelului de adevr). Al doilea bistabil comut doar din 2 n 2 impulsuri de tact, adic atunci cnd Q0 trece din 1 n 0, deci pot fi legate la ieirea primului bistabil. Al treilea bistabil basculeaz din 4 n 4 impulsuri i va fi comandat de funcia SI ntre ieirile Q1 Q0, iar al patrulea bistabil comut din 8 n 8 impulsuri i va fi comandat de funcia SI ntre ieirile Q2 Q1 Q0. n cazul numrtorului binar sincron de tip serie porile logice de tip SI utilizate vor fi toate cu 2 intrri, ca n schema logic anterioar.62

Q1

Q2

Q3

S J Q CLK K Q R

S J Q CLK K Q R

S J Q CLK K Q R

63

Pentru mrirea vitezei de rspuns a numrtorului se vor folosi pori logice de tip SI cu numrul de intrri necesar funciei SI implementate, ca n schema de mai jos, corespunztoare unui numrtor binar sincron paralel. Q0 1 S J Q CLK K Q R CLK Reset Timpul de comutare al numrtorului binar sincron paralel este mai mic dect la cel serie, dar exist pori de tip SI cu un numr mai mare de intrri. 5. Numrtor binar sincron reversibil Pentru realizarea reversibilitii numrtorului binar sincron se folosesc 2 intrri suplimentare, Count-Up (numr direct) i Count-Down (numr invers). Aceste numrtoare vor avea i ieiri pentru transport (Carry) i mprumut (Borrow), care vor permite legarea n cascad a numrtoarelor. Sinteza numrtoarelor modulo p Pentru a face sinteza unui numrtor cu p 2n trebuie determinat numrul minim de celule de memorie binar necesare. Relaia folosit este: 2n p. Celulele de memorie se interconecteaz apoi astfel nct s se omit (2n p) stri. Din acest motiv exist mai multe variante posibile pentru interconectare, deci i pentru sinteza numrtorului. Exemplu: Sinteza unui numrtor modulo 5. Pentru 2n 5 obinem n = 3, deci vom avea 3 celule de memorie pentru numrtor. Numrul strilor omise va fi 23 5 = 8 5 = 3. Presupunem c avem urmtoarea succesiune a strilor de numrare (ciclu de numrare): 000 001 010 011 100 S J Q CLK K Q R S J Q CLK K Q R S J Q CLK K Q R Q1 Q2 Q3

63

64

Evident c se putea alege i alt succesiune a strilor numrtorului. Folosim pentru realizarea numrtorului bistabili de tip JK. Se construiete un tabel cu strile actuale ale numrtorului, cu strile urmtoare i cu condiionrile intrrilor JK ale celor 3 bistabili folosii pentru sintez. Completarea tabelului se face pe baza tabelului de excitaie al bistabilului JK sincron.

Qt 0 0 1 1Q2t 0 0 0 0 1 Q1t 0 0 1 1 0 Q0t 0 1 0 1 0

Qt+1 J 0 0 1 1 0 x 1 xJ2 0 0 0 1 x K2 x x x x 1

K x x 1 0J1 0 1 x x 0 K1 x x 0 1 x J0 1 x 1 x 0 K0 x 1 x 1 x

Q2t+1 Q1t+1 Q0t+1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0

Diagramele Karnaugh pentru cele 6 intrri ale bistabilelor ne permit determinarea funciilor pentru intrri. Strile omise se consider indiferente. J2: Q2 Q1Q0 00 01 11 10 0 1 1 x x x x J2 = Q1 Q0 K2: Q2 Q1Q0 00 01 11 10 0 x x x x 1 1 x x x K2 = 1 J1: Q2 Q1Q0 00 01 11 10 0 1 x x 1 x x x J1 = Q0 K1: Q2 Q1Q0 00 01 11 1064

65

0 1

x x

x x

1 x

x

K1 = Q0 J0: Q2 Q1Q0 00 01 11 10 0 1 x x 1 1 x x x J0 = Q2 K0: Q2 Q1Q0 00 01 11 10 0 x 1 1 x 1 x x x x K0 = 1 Schema logic pentru numrtorul modulo 5 va fi urmtoarea: Q2 Q1 Q0

1

J2 Q2 CLK K2 Q2 R2

J1 Q1 CLK K1 Q1 R1

J0 Q0 CLK 1 K0 Q0 R0

CLK Reset Pentru rezolvarea complet a sintezei numrtorului modulo 5 trebuie discutat i problema strilor omise. Ce se ntmpl cu numrtorul dac nu are secven de iniializare sau dac ajunge cumva n una dintre strile care nu face parte din ciclul de numrare? Care va fi evoluia numrtorului? Trebuie verificate tranziiile numrtorului n cazul n care este ntr-o stare din afara ciclului de numrare. Putem avea 2 situaii: fie numrtorul revine singur n ciclul de numrare, fie trebuie reproiectat astfel nct s revin n ciclul de numrare. Strile omise n exemplul dat sunt: 101 010 110 010 i din starea aceasta se revine n ciclu 111 010 Observaie. Un numrtor modulo p se poate obine folosind un numrtor binar sincron. Se las numrtorul binar s evolueze pn la

65

66

starea p-1. La atingerea strii p se aplic numrtorului, printr-o logic combinaional, un impuls de tergere (pe intrarea de Reset). Numrtoare Moebius Numrtoarele Moebius sunt numrtoare n inel cu coad ntoars (twisted tail ring counter). Dei exist numrtoare de tip MSI pentru numrarea binar sau a altor tipuri de secvene, exist unele cazuri n care se prefer proiectarea unor numrtoare speciale cu bistabili i pori logice. Exemplu: un numrtor cu 8 stri la care la fiecare tranziie se modific numai un singur bit, se poate construi utiliznd urmtoarea secven: 0000 0 1000 8 1100 12 1110 14 1111 15 0111 7 0011 3 0001 1 Proiectarea se face i cu bistabili de tip D i cu bistabili de tip JK. Tabelul folosit pentru sinteza numrtorului este: t t t t t t t Q Q2 Q1 Q0 Q3 Q2 Q1 Q0 D3 D2 D1 D0 J3 K3 J2 K2 J1 K1 J0 K0+1 +1 +1 +1

0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 1 0 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 Diagramele Karnaugh ne permit intrrile bistabilelor D3 D0 i J3 K0. D3: Q3Q2 Q1Q0 00 01 11 10 D3 = Q0 D2: 00 1 x 1 1 01 x x x 11 10 x x 1 x

0 1 1 1 1 0 0 0

0 0 1 1 1 1 0 0

0 0 0 1 1 1 1 0 s

1 x 0 x 0 x 0 x x 0 1 x 0 x 0 x x 0 x 0 1 x 0 x x 0 x 0 x 0 1 x x 1 x 0 x 0 x 0 0 x x 1 x 0 x 0 0 x 0 x x 1 x 0 0 x 0 x 0 x x 1 determinm valorile pentru

x

66

67

Q3Q2 Q1Q0 00 01 11 10 D2 = Q3 Q3Q2 Q1Q0 00 01 11 10 D1 = Q2 D0: Q3Q2 Q1Q0 00 01 11 10 D0 = Q1 Q3Q2 Q1Q0 00 01 11 10 J3 = Q0 K3: Q3Q2 Q1Q0 00 01 11 10 K3 = Q0 J2: Q3Q2 Q1Q0 00 01 11 10 J2 = Q3

00 x 1 1

01 x x x

11 1 x

10 x x 1 x

D1:00 x 1 01 x x x 01 x x x 11 1 1 x 11 1 1 1 x 10 x x 1 x 10 x x 1 x

00 x

J3:00 1 x x x 00 x x 01 x x x 01 x x x x 01 x x x 11 x x 11 x x 1 x 11 x x x 10 x x x x 10 x x x 10 x x x x

00 x x 1

67

68

K2: Q3Q2 Q1Q0 00 01 11 10 K2 =Q3 J1: Q3Q2 Q1Q0 00 01 11 10 J1 = Q2 K1: Q3Q2 Q1Q0 00 01 11 10 K1 = Q2

00 x x x 00 x 1

01 x x x x 01 x x x 01 x x x x

11 x 1 x 11 x x x x 11 1 x

10 x x x 10 x x x x 10 x x x

00 x x x x

J0:Q3Q2 Q1Q0 00 01 11 10 00 x x x 01 x x x x 11 x x 1 10 x x x J0 = Q1 K0: Q3Q2 Q1Q0 00 01 11 10 00 x 1 x 01 x x x 11 x x x 10 x x x x K0 = Q1 Cele 2 scheme logice pentru numrtor sunt: D3 Q3 D2 Q2 D1 Q1 D0 Q0

CLK Q3

CLK Q2

CLK Q1

CLK Q0

68

69

CLK

J3 Q3 CLK K3 Q3 CLK

J2 Q2 CLK K2 Q2

J1 Q1 CLK K1 Q1

J0 Q0 CLK K0 Q0

Observaie. Starea fiecrui bistabil este determinat de starea anterioar a bistabilului plasat n stnga sa, iar starea primului bistabil este determinat de ieirea complementar a ultimului bistabil. Se pot construi numrtoare Moebius de orice dimensiune (ordin). Aplicaii ale numrtoarelor Moebius a. Se pot folosi ca i numrtoare de stare. Dac numrtorul este implementat cu bistabile JK, fiecare comutare a strii este controlat de cte o intrare diferit. Din acest motiv, modificarea oricrei stri va putea fi controlat independent, adugnd o poart SI sau SI-NU pe intrarea respectiv (de exemplu tranziia 0 8 este controlat de J3, tranziia 8 12 de J2 .a.m.d.).

b. Generatoare de ceas cu mai multe faze. Cele 8 ieiri ale numrtorului genereaz de fapt 8 semnale de ceas defazate n mod egal, cu factor de umplere de 50%. n general un numrtor Moebius de n bii genereaz 2n faze de ceas.c. Decodificarea oricrei stri se poate face printr-o poart cu 2 intrri. Pt. a face decodificarea strii se vor urmri cei 2 bii adiaceni distinci, 1 i 0. d. Decodificarea strilor succesive se realizeaz prin pori care au ca intrri ultimul 1 al primei stri i primul 0 al ultimei stri.

Curs 83.2.2. Registre Registrele sunt circuite logice secveniale care permit stocarea i/sau deplasarea informaiei codificate binar. Ele se realizeaz din celule de memorie binar (CBB) i din circuite logice combinaionale (CLC),

69

70

care permit nscrierea, citirea i transferul informaiei. Capacitatea unui registru este dat de numrul celulelor de memorie. Orice informaie binar, care nu depete capacitatea registrului, poate fi nscris prin acionarea corespunztoare a intrrilor (care depinde i ea de natura bistabilelor). Registrele pot s fie de mai multe tipuri: de memorie; de deplasare; combinate; universale. Registrele de memorie memoreaz informaia binar n celule de memorie binar. n fiecare celul de memorie se memoreaz un bit de informaie. ncrcarea se poate face paralel, prin intrrile asincrone, de Set i Reset. Registrele de deplasare sunt cele care realizeaz transferul informaiei. Transferul se poate face: stnga-dreapta; dreapta-stnga; n ambele sensuri. La fiecare impuls de tact coninutul registrului se deplaseaz cu cte o celul (n sensul stabilit). Semnalul de ieire este identic cu cel de intrare, dar ntrziat cu un numr de impulsuri de tact egal cu numrul de celule de memorie din care este format registrul. Exceptnd primul bistabil, ecuaia de stare a unui registru de deplasare stnga-dreapta este dat de relaia: Qi(t+1) = Qi-1(t) c (unde c = impulsul de tact). Exemplu: Registru de deplasare stnga-dreapta cu bistabile JK MS. Q0 Q1 Q2 Q3 SIN J0 Q0 J1 Q1 J2 Q2 J3 Q3

CLK CLKK0 R Reset CLK Q0

CLKK1 R Q1 K2 R

CLKQ2 K3 R Q3

La fiecare impuls de tact coninutul bistabilului Qi se transfer n bistabilul Qi+1. n bistabilul Q0 se introduce informaia din exterior, iar coninutul ultimului bistabil se pierde. ncrcarea registrului se realizeaz deci n mod serie. Iniializarea registrului se face prin semnalul de Reset, care foreaz toate ieirile registrului n 0 logic. Registrele de deplasare dreapta-stnga i reversibile se realizeaz folosind circuite logice combinaionale suplimentare. Registrele combinate sunt cele care au i funcia de memorare i cea de deplasare.

70

71

Registrele universale cumuleaz toate funciile: deplasare stngadreapta, deplasare dreapta-stnga, ncrcare serie sau paralel a informaiei, citire serie sau paralel a informaiei. RI A B C D LI S0 S1

CLK CLR

D Q CLK CLR

D Q CLK CLR

D Q CLK CLR

D Q CLK CLR

Q0 Q1 Q2 Q3 Intrrile de selecie S1S0 condiioneaz modul de funcionare a registrului. Avem: S1S0 = 00 pstreaz coninutul nemodificat; S1S0 = 01 deplasare stnga-dreapta; S1S0 = 10 deplasare dreapta-stnga; S1S0 = 11 ncrcare paralel. tergerea registrului se face asincron, prin semnalul CLR. Aplicaii ale registrelor Registrele sunt utilizate n mai multe tipuri de aplicaii, dup funciile pe care pot s le ndeplineasc. 1. Registre de deplasare cu reacie Au ieirile conectate la intrri i pot fi: - registre de deplasare n inel coninutul ultimei celule de memorie se nscrie n prima celul de memorie; Q0 Q1 Q2 Q3 1 0 0 0 SIN 0 1 0 0 0 0 1 0

Q0 Q1 Q2 Q3

0

0

0

1

1 0 0 0 - registre (numrtoare) Johnson n prima celul se introduce coninutul negat al ultimei celule. Q0 Q1 Q2 Q3

71

72

SIN

0 1 1

0 0 1

0 0 0

0 0 0

Q0 Q1 Q2 Q3

1

1

1

0

1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 2. Memorie de tip FIFO (First In, First Out), primul nscris primul citit (memorie coad) Se realizeaz cu registre de deplasare stnga-dreapta. Numrul registrelor depinde de lungimea cuvintelor ce urmeaz a fi memorate. Capacitatea memoriei depinde de lungimea registrelor. De exemplu, dac registrele sunt de 4 bii, capacitatea memoriei este de 4 cuvinte. La fiecare impuls de tact se introduc datele pe intrarea serial. y1 SIN x1 y2 SIN x2 y3 SIN x3 y4 SIN x4 CLK Ts Ts Ts Ts

3. Memorie de tip LIFO (Least In, First Out), ultimul introdus primul citit (memorie stiv)

72

73

Realizarea se face cu registre combinate. Numrul registrelor este dat de lungimea cuvntului de memorie, iar lungimea registrelor determin capacitatea de memorie. xiA0 A1 A1 SIN A0 Q0 Q1 Q2 Q3 CLK yi

R

A1 A0 0 1 deplasare stnga-dreapta nscriere 1 0 citire Memoria stiv poate fi organizat i soft, n memoria de tip RAM, dar dei capacitatea acesteia poate fi mare, timpul de acces va fi i el mare. 4. Conversia serie-paralel i paralel serie a informaiei Pentru conversia serie-paralel se face ncrcarea registrului pe intrarea serial i cu comand de tact serie Ts i se citete informaia pe ieiri, paralel. Pentru conversia paralel-serie se face ncrcarea paralel a informaiei, cu comand de tact paralel Tp i apoi se deplaseaz informaia stnga-dreapta, cu comand de tact serie Ts i se citete serie la ultima ieire. 5. Generatoare de secvene Generatoarele de secvene genereaz o succesiune de secvene binare (1 i 0) de lungime dat (prestabilite). Lungimea secvenei reprezint numrul de bii dup care se repet ntreaga secven. Secvenele binare pot fi: - aleatoare, de lungime infinit; - deterministe, de lungime finit. Secvenele binare deterministe de lungime maxim se numesc secvene pseudoaleatoare. Realizarea generatoarelor de secvene se face cu registre n reacie cu circuite logice combinaionale adecvate.

73

74

Q0 y = Q0 + Q2 S0 Q0 CLK R0 Q0 CLK

Q1

Q2

S1 Q1 CLK R1 Q1

S2 Q2 CLK R2 Q2

Secvena pseudoaleatoare generat la ieirile Q0Q1Q2 este: 100 110 111 011 101 010 001 3.2.3. Memorii RAM Memoriile de tip RAM (random access memory) sunt memorii de tip citete-scrie, cu acces aleator. Ele nu-i pstreaz informaia dup ntreruperea tensiunii de alimentare. Memoria este format din nivelul de decodificare, matricea de memorie realizat cu celule de memorie binar de tip latch i nivelul de multiplexare. Dimensiunea memoriei este specificat prin numrul de cuvinte i numrul de bii pe cuvnt. Capacitatea memoriei este dat de numrul de bii memorai n matricea de memorie. Schema funcional de principiu a unei memorii RAM este urmtoarea: Adres n n CE sau CS (chip select) Decodificator 2n Matrice de memorie 2n WE (write enable) Multiplexor

DateDecodificatorul acioneaz pentru selectarea fiecrei celule de memorie, iar multiplexorul permite selectarea oricrei celule de memorie la intrare ieire.

74

75

Validarea memoriei se face prin intrarea CS. Citirea memoriei se face dac WE = 1, iar scrierea memoriei se face dac WE = 0. Datele de intrare i ieire pot s foloseasc linii diferite sau aceeai linie bidirecional. Memoriile pot avea un numr diferit de ci de date (de obicei cuvinte de 1 bit sau de un numr de bii multiplu de 2). Memoriile de tip RAM pot s fie din punct de vedere constructiv de tip static sau dinamic. Cele dinamice sunt realizate cu condensatoare i au nevoie de remprosptarea la diferite intervale de timp a informaiei memorate, pentru a se evita pierderea ei. Extinderea capacitii memoriilor se face att prin extinderea dimensiunii cuvntului de memorie (numrul de bii din cuvnt), ct i prin extinderea numrului de cuvinte ale memoriei (adresa de memorie).

Curs 93.3. Sinteza circuitelor logice secveniale sincroneCircuitele secveniale sincrone trec dintr-o stare n alta la momente distincte de timp, determinate de impulsurile de tact. ntre dou impulsuri de tact starea circuitului nu se modific. Variabile de intrare Generare stare nou Calculul excitaiilor secundare CLC Excitaii secundare Tact Registru de stri Stri interne CL Variabile secundare Calculul variabilelor de ieire CLC CL = circuit logic general pstreaz starea intern registru de stri (bistabili RS, D, JK, registre, memorii); poate fi circuit logic secvenial cu bucl de reacie.

75

76

CLC = determin funciile de excitaie secundare care n prezena tactului determin trecerea circuitului n alt stare se poate numi generatorul strii noi; se pot realiza cu pori logice sau cu circuite specializate (multiplexoare, decodificatoare). Variabilele de intrare sunt n general sincrone cu impulsul de tact, dar pot fi i de tip asincron. 3.3.1. Etapele de sintez 1. Expunerea condiiilor de funcionare (descrierea comportrii circuitului). Stabilirea modalitii de definire a circuitului care trebuie sintetizat prin: - tabel de tranziii; - graf de tranziii; - organigram; - forme de und. Trebuie evideniate: - strile prin care trece circuitul; - valorile variabilelor de intrare pentru care se schimb strile; - valorile rezultate ale variabilelor de ieire. Evoluia circuitului ncepe ntr-o stare iniial i de obicei se revine la aceast stare, dup ultima stare a ciclului. 2. Se codific strile circuitului. 3. Se ncearc reducerea (simplificarea) numrului de stri a circuitului, dac este posibil, nct s se pstreze funcionarea lui corect.

4. Se decide asupra modului de implementare (registrul de stri interne). 5. Se determin funciile de excitaie i cele de ieire, dac este posibil.6. Se studiaz problemele legate de eventualele ieiri false (hazard) sau tranziii false. 7. Se deseneaz circuitul. Etapa cea mai dificil este cea de codificare a strilor. n general funcionrile defectuoase se datoreaz unor tranziii greite ntre stri sau unor semnale greite care apar la circuitul de generare a variabilelor de ieire. Tranziiile greite ntre stri apar datorit prezenei variabilelor de intrare asincrone (se elimin cel mai uor dac se sincronizeaz variabilele de intrare cu semnalul de tact).

76

77

Codificarea strilor se stabilete astfel nct, n orice stare, pentru toate combinaiile posibile de intrri asincrone, s nu fie mai mult dect o singur variabil de stare dependent de o variabil de intrare asincron. n aceste condiii, dou stri rezultate din calea de ieire a unei intrri asincrone vor avea codificare adiacent. Ieirile false pot s apar din cauz c la trecerea dintr-o stare n alta, variabilele de stare practic nu se modific simultan. Pentru evitarea tranziiilor false ale ieirilor se pot folosi metodele: - se realizeaz o codificare adiacent a strilor; - se foreaz trecerea circuitului prin stri suplimentare; - se sincronizeaz variabilele de ieire. Observaie: Hazardul static al CLC se elimin prin proiectare (se introduc termeni redundani, indifereni).

3.3.2. Utilizarea organigramei n sinteza circuitelor logice secveniale sincrone Elementele componente ale organigramei de funcionare a oricrui circuit secvenial sincron sunt: - elementul de intrare (control sau decizie): Variabile de intrare - sincrone var. 0 - asincrone var. 0 - elementul de stare: Q2Q1Q0 000 - elementul de ieire: transfer 1 1

77

78

Configuraii elementare care unesc cele 3 elemente de baz: A B 001 011 tranziie simpl: - contor de timp - soluionarea problemei de codificare a strilor

A Adun B

stare cu ieire

A 1 B I1

stare cu decizie 0 C

A Scade 1 B I1

stare cu ieire i decizie

0 C

A I1

stare cu ieire condiionat 1

78

79

0 B

Ieire

A 0 1 I2 0 B 1 I3 0 I1 1

stri cu decizii multiple i ieire

C Ieire

Observaii1. Orice tranziie ntre 2 stri ale circuitului se face ntr-un singur impuls de tact. 2. La un moment dat circuitul se poate gsi ntr-o singur stare. 3. Un circuit care se gsete la un moment dat ntr-o stare dat, cu un set de intrri dat, poate avea o singur stare urmtoare. 3.3.3. Sinteza circuitelor secveniale sincrone cu diferite elemente de memorie n sinteza circuitelor secveniale sincrone se vor folosi ca elemente de memorie bistabili de tip D i JK. Implementarea registrului de stri se va realiza cu aceste tipuri de bistabile. Exemplu: S se recunoasc secvena 101 n irul de cifre binare 10101. Graful de tranziii are n noduri strile circuitului. Pe arce avem tranziia dintr-o stare n alta pentru o anumit intrare, cu o anumit ieire. 0/0 1/0 Init A B 1/1 0/0 Avem 2 variabile B=01, C=11). Cu x am este: St Q1Q0 de stare pentru a putea codifica 2 stri (A=00, notat intrarea, cu z ieirea. Tabelul de tranziii St+1,z x=0 x=179

1/0 0/0 C

80

00 01 11

A B C

A,0 C,0 A,0

B,0 B,0 B,1

a. Implementm registrul de stri cu bistabile de tip D. Funciile de excitaie se deduc explicitnd diagrama strilor pentru momentul t i momentul t+1. Strile se vor nlocui cu codurile lor (A=00, B=01, C=11). St St+1 (Q1Q0)t+1 z Q1Q0 D1D0 D1D0 x=0 x=1 x=0 x=1 00 (A) 00 (A) 01 (B) 0 0 01 (B) 11 (C) 01 (B) 0 0 11 (C) 00 (A) 01 (B) 0 1 Di = Qit D1: Q1Q0 x 00 01 11 10 D1 = Q1 Q0 x D0: Q1Q0 x 00 01 11 10 D0 = x + Q1 Q0 z: Q1Q0 x 00 01 11 10 z = Q1 x 0 0 1 0 x 0 0 1 0 x 1 0 0 0 x 1 1 1 1 x ecuaia strii urmtoare

0 0 0 0 x

1 0 0 1 x

80

81

La trecerea din starea C n starea A se poate trece prin starea B, ceea ce nu corespunde funcionrii. n mod normal se introduce o stare suplimentar pentru a rezolva situaia. Schema pentru circuitul secvenial sincron este: D1 Q1 CLK Q1 Init CLK D0 Q0 CLK Q0 R Q1 Q0 x R Q1 x Q1 x D1 Q0 D0 z

b. Implementm registrul de stri cu bistabile de tip JK. Diagrama strilor se completeaz innd cont de