Referat ANALIZA SI SINTEZA DISPOZITIVELOR NUMERICE

Mai jos puteti citi fragmente din Referat ANALIZA SI SINTEZA DISPOZITIVELOR NUMERICE si de asemenea puteti face Download Referat ANALIZA SI SINTEZA DISPOZITIVELOR NUMERICE

Citeste fragmente din Referat ANALIZA SI SINTEZA DISPOZITIVELOR NUMERICE

ANALIZA ŞI SINTEZA DISPOZITIVELOR NUMERICE cursBibliografie Circuite de comutare aplicate în calculatoarele electronice, V. Pop, Volker Popovici, ed. Facla, 1976 Circuite integrate digitale, Gh. Ştefan, I. Drăghici, T. Mureşan, E. Barbu, EDP, 1983 De la poarta TTL la microprocesor, I. Sztojanov ş.a., ET, 1987 Proiectarea cu circuite logice MSI şi LSI standard, T.R. Blakeslee, ET, 1988 Circuite integrate digitale, Gh. Stefan, V. Bistriceanu, Probleme, proiectare, EDP, 1992 Circuite integrate digitale, Gh. Stefan, V. Bistriceanu, Probleme, proiectare, Ed. Albastră, 2000 Automatizări discrete în industrie, Culegere de probleme, N. Sprânceană, R. Dobrescu, Th. Borangiu, ET, 1978 Sisteme numerice cu circuite integrate, Culegere de probleme, Sanda Maican, ET, 1980 Analiza şi sinteza dispozitivelor numerice, I.A. Leţia, Îndrumător de laborator, I.P. Cluj-Napoca, 1985 Analiza şi sinteza dispozitivelor numerice, A. Neţin, O. Creţ, Îndrumător de laborator, UT Press. Cluj-Napoca, 1998 Curs 1 CAPITOLUL I ELEMENTE DE ALGEBRĂ BOOLEANĂ 1.1. Generalităţi Transferul, prelucrarea şi păstrarea datelor numerice sau nenumerice în interiorul unui calculator se realizează prin intermediul circuitelor de comutare. Aceste circuite se caracterizează prin faptul că prezintă două stări stabile care se deosebesc calitativ între ele. Stările sunt puse în corespondenţă cu valorile binare “0” şi “1” sau cu valorile logice “adevărat” şi “fals” (din acest motiv se mai numesc şi circuite logice). Pornind de la aceste considerente, un domeniul al logicii matematice, (ştiinţa care utilizează metode matematice în soluţionarea problemelor de logică) numit “algebra logicii” şi-a găsit o largă aplicare în analiza şi sinteza circuitelor logice. Algebra logicii operează cu propoziţii care pot fi adevărate sau false. Unei propoziţii adevărate i se atribuie valoarea “1”, iar unei propoziţii false i se atribuie valoarea “0”. O propoziţie nu poate fi simultan adevărată sau falsă, iar două propoziţii sunt echivalente d.p.d.v. al algebrei logice, dacă simultan ele sunt adevărate sau false. Propoziţiile pot fi simple sau compuse, cele compuse obţinându-se din cele simple prin legături logice de tipul conjuncţiei (, disjuncţiei ( sau negaţiei (. Bazele algebrei logice au fost puse de matematicianul englez George Boole (1815-1864) şi ca urmare ea se mai numeşte şi algebră booleană. Ea a fost concepută ca o metodă simbolică pentru tratarea funcţiilor 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 comutaţie. 1.2. Definirea axiomatică a algebrei booleene Algebra booleană este o algebră formată din: elementele (0,1(; 2 operaţii binare numite SAU şi SI, notate simbolic + sau ( şi ( sau (; 1 operaţie unară numită NU negaţie, notată simbolic sau (. Operaţiile 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 = 1 Axiomele algebrei booleene sunt următoarele: Fie o mulţime M compusă din elementele x1, x2,…xn, împreună cu operaţiile ( şi +. Această mulţime formează o algebră dacă: Mulţimea M conţine cel puţin 2 elemente distincte x1 ( x2 (x1,x2( M); Pentru ( x1 ( M, x2 ( M avem: x1 + x2 ( M şi x1 ( x2 ( M Operaţiile ( şi + au următoarele proprietăţi: sunt comutative x1 ( x2 = x2 ( x1 x1 + x2 = x2 + x1 sunt asociative x1 ( (x2 ( x3) = (x1 ( x2) ( x3 x1 + (x2 + x3) = (x1 + x2) + x3 sunt distributive una faţă de cealaltă x1 ( (x2 + x3) = x1 ( x2 + x1 ( x3 x1 + (x2 ( x3) = (x1 + x2) ( (x1 + x3) Ambele operaţii admit câte un element neutru cu proprietatea: x1 + 0 = 0 + x1 = x1 x1 ( 1 = 1 ( x1 = x1 unde 0 este elementul nul al mulţimii, iar 1 este elementul unitate al mulţimii. Dacă mulţimea M nu conţine decât 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 proprietăţile: x ( x = 0 principiul contradicţiei x + x = 1 principiul terţului exclus x este inversul elementului x. În definirea axiomatică a algebrei s-au folosit diferite notaţii. În tabelul următor se dau denumirile şi notaţiile specifice folosite pentru diverse domenii: Matematică Logică Tehnică Prima lege de compoziţie x1 + x2 Disjuncţie x1 ( x2 SAU x1 + x2 A doua lege de compoziţie x1 ( x2 Conjuncţie x1 ( x2 SI Elementul invers x Negare (x NU x 1.3. Proprietăţile algebrei booleene Plecând de la axiome se deduc o serie de proprietăţi care vor forma reguli de calcul în cadrul algebrei booleene. Aceste proprietăţi sunt: Principiul dublei negaţii x = x dubla negaţie duce la o afirmaţie Idempotenţa x ( x = x x + x = x Absorbţia x1 ( (x1 + x2) = x1 x1 + (x1( x2) = x1 Proprietăţile elementelor neutre x ( 0 = 0 x ( 1 = x x + 0 = x x + 1 = 1 Formulele lui De Morgan x1 ( x2 = x1 + x2 x1 + x2 = x1 ( x2 Aceste formule sunt foarte utile datorită posibilităţii de a transforma produsul logic în sumă logică şi invers. Formulele pot fi generalizate la un număr arbitrar de termeni: x1 ( x2 ( … ( xn = x1 + x2 + … + xn x1 + x2 + … + xn = x1 ( x2 ( … ( xn Principiul dualităţii – dacă în axiomele şi proprietăţile algebrei booleene se interschimbă 0 cu 1 şi + cu (, sistemul de axiome rămâne acelaşi, în afara unor permutări. Verificarea proprietăţilor se poate face cu ajutorul tabelelor de adevăr şi cu observaţia că două funcţii sunt egale dacă iau aceleaşi valori în toate punctele domeniului de definiţie. Prin tabelul de adevăr se stabileşte o corespondenţă între valorile de adevăr ale variabilelor şi valoarea de adevăr a funcţiei. Obs. Comutativitatea şi asociativitatea pot fi extinse la un număr arbitrar, dar finit, de termeni, indiferent de ordinea lor. 1.4. Funcţii booleene O funcţie f: Bn ( B, unde B = (0,1( se numeşte funcţie booleană. Această funcţie booleană y = f(x1, x2,…,xn) are drept caracteristică faptul că atât variabilele cât şi funcţia nu pot lua decât două valori distincte, 0 sau 1. Funcţia va pune în corespondenţă fiecărui element al produsului cartezian n dimensional, valorile 0 sau 1. Astfel de funcţii sunt utilizate pentru caracterizarea funcţionării unor dispozitive (circuite) construite cu elemente de circuit având două stări (ex.: un întrerupător închis sau deschis, un tranzistor blocat sau în conducţie; funcţionarea unui astfel de circuit va fi descrisă de o variabilă booleană xi). 1.4.1. Funcţii booleene elementare Revenim la forma generală a unei funcţii booleene de n variabile: y = f(x1, x2,…,xn) Domeniul de definiţie este format din m = 2n puncte. Deoarece în fiecare din aceste puncte funcţia poate lua doar valorile 0 şi 1 rezultă că numărul total al funcţiilor booleene de n variabile este N = 2m. Vom considera în continuare funcţiile elementare de 1 variabilă. Pentru n = 1 avem m = 2 şi N = 4. Funcţia are forma y = f(x) şi cele 4 forme ale ei se găsesc în tabelul următor: f2 1 0 x Negaţia lui x f3 1 1 1 Constanta 1 La fel se pot realiza toate funcţiile cu ajutorul unor funcţii de bază. Acestora le vor corespunde şi nişte circuite logice elementare, cu ajutorul cărora se poate realiza practic orice tip de circuit. Ţinând cont de faptul că circuitele logice de comutaţie au 2 stări stabile LOW (L) şi HIGH (H), asignând lui L ( 0 şi lui H ( 1 se poate întocmi un tabel al funcţiilor elementare. Inversor – NOT f = x x f = x x f 0 1 1 0 x f L H Poartă SI – AND f = x1 ( x2 x1 x2 f=x1(x2 x1 x2 f 0 0 0 0 1 0 1 0 0 1 1 1 x1 x2 f L L L L H L H L L Poartă SAU – OR f = x1 + x2 x1 x2 f=x1+x2 x1 x2 f 0 0 0 0 1 1 1 0 1 1 1 1 x1 x2 f L L L L H H H L H Poartă SI-NU – NAND f = x1 ( x2 x1 x2 f=x1(x2 x1 x2 f 0 0 1 0 1 1 1 0 1 1 1 0 x1 x2 f L L H L H H H L H Poartă SAU-NU – NOR f = x1 + x2 x1 x2 f=x1+x2 x1 x2 f 0 0 1 0 1 0 1 0 0 1 1 0 x1 x2 f L L H L H L H L L SAU EXCLUSIV – XOR f = x1 + x2 x1 x2 f=x1 + x2 x1 x2 f 0 0 0 0 1 1 1 0 1 1 1 0 x1 x2 f L L L L H H H L H COINCIDENŢĂ f = x1 ( x2 x1 x2 f=x1 ( x2 =x1 + x2 x1 x2 f 0 0 1 0 1 0 1 0 0 1 1 1 x1 x2 f L L H L H L H L L H H H 1.4.2. Reprezentarea funcţiilor booleene Există două moduri de reprezentare a funcţiilor booleene: grafică şi analitică. Modalităţi grafice - se caracterizează printr-o reprezentare intuitivă, uşor de reţinut, dar sunt inadecvate pentru funcţii booleene cu un număr de variabile mai mare decât 4; 2. Modalităţi analitice - sunt mai greoaie, dar permit metode automate, deci algoritmi de simplificare a funcţiei; se folosesc în general pentru funcţii booleene cu numărul variabilelor mai mare decât 5. Modalităţi de reprezentare grafică Modalităţile de reprezentare grafică sunt: tabel de adevăr, diagramă Karnaugh, schemă logică, diagramă de timp. Tabel de adevăr – se marchează într-un tabel corespondenţa dintre valorile de adevăr ale variabilelor de intrare şi valoarea de adevăr a funcţiei, în fiecare punct al domeniului de definiţie. Pentru o funcţie cu n variabile de intrare vom avea 2n combinaţii. Există situaţii în care, pentru anumite combinaţii ale variabilelor de intrare, valoarea funcţiei nu este specificată. Aceste funcţii se numesc incomplet definite. În tabel, în locul în care funcţia nu este specificată, se notează cu “X”. Dacă o funcţie booleană este incomplet definită pentru “m” combinaţii ale variabilelor de intrare se pot defini 2m funcţii noi prin alegerea arbitrară a valorilor incomplet definite. Diagramă Karnaugh O diagramă Karnaugh pentru o funcţie booleană de n variabile se desenează sub forma unui pătrat sau dreptunghi împărţit în 2n compartimente. Fiecare compartiment este rezervat unui termen canonic al funcţiei, respectiv unuia dintre vârfurile cubului n dimensional din reprezentarea geometrică a funcţiei (2n n-uple ale funcţiei). Diagrama Karnaugh este organizată astfel încât 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 adevărată, iar în celălalt 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 indicând domeniul fiecărei variabile, fie indicând pe linie şi coloană n-uple de zerouri şi unităţi corespondente unui compartiment din diagramă şi ordinea variabilelor. Prima notaţie se foloseşte în cazul în care se reprezintă funcţia prin forma ei canonică sau normală. A doua notaţie se foloseşte în cazul în care funcţia se reprezintă prin tabel de adevăr. Pentru a putea reprezenta uşor funcţii exprimate în mod convenţional prin indicii termenilor canonici se poate nota fiecare compartiment cu indicele termenului corespondent, ţinând cont de o anumită ordine a variabilelor. Exemple: Diagrama Karnaugh pentru funcţia de 2 variabile: f(x1, x2) = x1(x2 + x1(x2 x1 sau x1 x2 Obs. Numerotarea liniilor şi coloanelor se face în cod Gray (cod binar reflectat) 10 1100 1010 1101 1011 1110 1001 1111 1000 Diagrama Karnaugh pentru funcţia de 3 variabile: y = f(x1,x2,x3) Domeniul de definiţie este format din 23 = 8 puncte şi reprezintă vârfurile unui cub cu latura 1: x1 001 101 011 111 000 100 x3 010 110 x2 Diagramele Karnaugh corespunzătoare pot fi reprezentate astfel: x2 x3 sau Diagrama Karnaugh pentru funcţia de 4 variabile: y = f(x1,x2,x3,x4) x3 Prin săgeţi am marcat vecinătăţile punctului de coordonate 0010. 4) Diagramele Karnaugh pentru funcţii de mai mult de 4 variabile se construiesc din diagrame de 4 variabile considerate ca diagrame elementare. Schemă logică – reprezentare cu ajutorul simbolurilor circuitelor logice. Diagramă de timp – reprezentare utilă pentru studiul unor forme tranzitorii de hazard în circuitele logice. Se reprezintă funcţii logice în a căror evoluţie intervine timpul. Exemplu: f = x1(x2 x2 f Curs 2 1.4.2.2. Modalităţi de reprezentare analitică 1) Formele canonice Fie o funcţie booleană f(x), unde x = (x1,x2,…,xn). Se defineşte numărul i = x1(20 + x2(21 + … + xn(2n-1 ca număr de combinaţii. Exemplu: x1 x2 x3 f 0 0 0 0 0 1 0 1 0 ( i = 0(22 + 1(21 + 0(20 = 2 0 1 1 Fie funcţia Pi definită pe Bn ( B, deci Pi : Bn ( B Pi(x1,x2,…,xn) = 1 dacă numărul de combinaţii este i 0 în caz contrar Această funcţie se numeşte constituent al unităţii. Se poate arăta că orice funcţie booleană dată prin tabelul de adevăr se poate scrie ca o sumă de constituenţi ai unităţii. f(x1, x2,…,xn) = Pi1 + Pi2 + … + Pip = ( Pij i,j(M1 unde M1 = mulţimea tuturor combinaţiilor argumentelor pentru care funcţia ia valoarea 1. Această formă de scriere se numeşte forma canonică disjunctivă FCD, iar termenii constituenţi se numesc termeni canonici conjunctivi sau mintermi (se mai numeşte şi forma sumă de produse). Funcţia booleană se mai poate scrie şi sub forma Si : Bn ( B unde B = {0,1}. Si(x1,x2,…,xn) = 0 dacă numărul de combinaţii este i 1 în caz contrar Se poate demonstra că orice funcţie booleană poate fi adusă la forma: f(x1, x2,…,xn) = Si1 ( Si2 ( … ( Siq = ( Sij i,j(M0 unde M0 = mulţimea tuturor combinaţiilor argumentelor pentru care funcţia ia valoarea 0. Această formă de scriere se numeşte forma canonică conjunctivă FCC, iar factorii constituenţi se numesc termeni canonici conjunctivi sau maxtermi (se mai numeşte şi forma produs de sume). Se poate demonstra că Si = Pi. Algoritmi de obţinere a formelor canonice pe baza tabelului de adevăr sau a diagramei Karnaugh: FCD se determină toate combinaţiile variabilelor pentru care valoarea funcţiei este 1; se scriu mintermii corespunzători (o variabilă apare nenegată dacă are valoarea 1 şi negată dacă are valoarea 0); se însumează mintermii obţinuţi anterior. FCC se determină toate combinaţiile variabilelor pentru care valoarea funcţiei este 0; se scriu maxtermii corespunzători prin însumarea variabilelor (o variabilă apare nenegată dacă are valoarea 0 şi negată dacă are valoarea 1); se înmulţesc maxtermii obţinuţi 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 adevăr; prin aplicarea dublei negaţii şi a teoremelor lui De Morgan. Teorema lui Shannon Complementul unei funcţii booleene se obţine prin complementarea fiecărei variabile şi interschimbarea operatorilor ŞI cu SAU şi reciproc. f(x1,x2,…,xn)+,( = f(x1,x2,…,xn)(,+ Teorema de expansiune Fie funcţia 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) Funcţia 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 funcţiilor booleene termenii conţin toate variabilele independente de intrare, negate sau nenegate. Termenii formei elementare nu conţin toate variabilele de intrare. Această formă se obţine din formele canonice prin minimizare. 3) Forma neelementară Forma neelementară conţine variabile sau grupuri de variabile comune mai multor termeni. Se obţine din celelalte forme prin aplicarea algebrei booleene. Este folosită la implementarea funcţiilor logice deoarece permite reducerea numărului de intrări în circuitele logice. Are dezavantajul măririi numărului de nivele logice. 1.4.3. Minimizarea funcţiilor booleene Algebra booleană se foloseşte la analiza şi sinteza dispozitivelor numerice (circuite de comutaţie). Între gradul de complexitate al circuitului şi cel al funcţiei care îl descrie există o legătură directă. Aceasta este motivaţia pentru care, în etapa de sinteză a circuitelor de comutaţie, după definirea acestora, urmează în mod obligatoriu etapa de minimizare a funcţiei, având drept scop obţinerea unor forme echivalente mai simple (forma minimă). Soluţia minimă obţinută în urma minimizării ar trebui să fie cea mai avantajoasă (economie de porţi logice, obţinerea unei scheme mai fiabile, mai ieftine). În realitate nu este întotdeauna aşa. De exemplu, dorinţa de a obţine un sistem uşor depanabil poate duce la obţinerea unei soluţii neminimale, dar care prezintă proprietăţi 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 (intersecţie minimală). Criteriile utilizate în vederea minimizării sunt: reducerea numărului de variabile; reducerea numărului 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 parţial simplificate în forme elementare minimale. Metodele de minimizare pot fi grupate în metode algebrice şi metode grafice. 1.4.3.1. Minimizarea grafică Diagrama Karnaugh Minimizarea se bazează pe proprietatea de adiacenţă a codului binar reflectat (Gray) cu ajutorul căruia se numerotează liniile şi coloanele diagramei Karnaugh. În vederea minimizării se aleg suprafeţele maxime (subcuburi) formate din constituenţi ai unităţii, respectiv din constituenţi ai lui 0, suprafeţe (subcuburi) având ca dimensiune un număr de pătrate (compartimente) egal întotdeauna cu puteri ale lui 2. Aceste suprafeţe vor corespunde termenilor canonici, termenii vecini fiind adiacenţi (diferă printr-un singur bit). Ca urmare, în urma grupării lor se vor reduce variabilele pe baza relaţiei: x1(x2 + x1(x2 = x1. Metoda de minimizare: se realizează grupări de compartimente (subcuburi) care sunt puteri ale lui 2. Un compartiment poate fi membru al mai multor suprafeţe. O suprafaţă cu 2m celule vecine va elimina 2m variabile de intrare. se scriu ecuaţiile corespunzătoare fiecărei suprafeţe, obţinându-se astfel termenii elementari. se realizează forma disjunctivă minimă (FDM) prin însumarea termenilor elementari obţinuţi prin gruparea constituenţilor lui 1 sau forma conjunctivă minimă (FCM) prin înmulţirea termenilor elementari obţinuţi prin gruparea de constituenţi ai lui 0; funcţiile minimale obţinute sunt identice, ele diferind numai prin forma de prezentare. Pentru a se obţine forma minimală a unei funcţii booleene este util să se minimizeze ambele forme canonice, FCC şi FCD. Apoi, în funcţie de disponibilitatea componentelor şi de numărul de conexiuni care rezultă, se poate alege forma minimală a funcţiei booleene care va fi implementată. Exemplu: f(x1,x2,x3,x4) = ( (3, 7, 8, 9, 12, 13, 15) x3 Pentru FDM a funcţiei se obţin două variante, după cum se aleg suprafeţele pentru minimizare: fFDM1 = x1(x3 + x1(x3(x4 + x1(x2(x4 sau fFDM2 = x1(x3 + x1(x3(x4 + x2(x3(x4 Implementarea cu porţi de tip SI-NU arată astfel: fFDM1 = x1(x3 + x1(x3(x4 + x1(x2(x4 = = x1(x3 ( x1(x3(x4 ( x1(x2(x4 Minimizarea funcţiei negate va fi: fFDM = x1(x3 + x3(x4 + x1(x2(x3 La fel se procedează şi la minimizarea funcţiei prin folosirea constituenţilor de 0: x3 Forma minimizată conjunctivă a funcţiei FCM este: fFCM = (x1+x3)((x3+x4)((x1+x2+x3) Diagrame Karnaugh pentru funcţii incomplet definite Funcţiile incomplet definite sunt cele care în anumite puncte ale domeniului de definiţie pot lua valoarea 0 sau valoarea 1. Avem două posibilităţi: combinaţii de intrare pentru care funcţia are valori indiferente (nedefinite); combinaţii ale variabilelor care nu pot să apară din punct de vedere fizic; în aceste situaţii trebuie studiat dacă combinaţiile sunt susceptibile să se producă în urma unei manevre false sau în urma unui defect de funcţionare; pentru a evita funcţionarea greşită, în locaţiile corespunzătoare se impun valori pentru funcţie, astfel încât să nu se perturbe funcţionarea normală. Valorile nespecificate precum şi locaţiile corespunzătoare din diagrama Karnaugh se numesc “indiferente” sau “arbitrare” sau “redundante”. Ele se notează cu “x” şi vor fi considerate în timpul minimizării ca având valoarea 1 sau 0, în funcţie de situaţie, pentru a se obţine o minimizare cât mai bună. x3 Ca să minimizăm funcţia în FDM considerăm că x au valoarea 1 şi grupăm aceşti x numai cu valorile de 1, nu şi între ei (o grupare între ei nu are nici o semnificaţie). Se obţine: fFDM = x1(x2 + x2(x3 + x1(x4 + x2(x4 Obs. În cazul funcţiilor incomplet definite, funcţia complementară simplificată prin grupări de 0 nu coincide întotdeauna cu complementul funcţiei. Diagrame Karnaugh cu expresii Superpoziţia funcţiilor booleene Fie o funcţie booleană f(X) cu X = (x1,x2,…, xi, xi+1,…,xn). Dacă considerăm X1 = (x1,x2,…, xi) şi X2 = (xi+1,…,xn) şi dacă funcţia f(X) poate fi scrisă ca o funcţie f(X) = f3[f1(X1), f2(X2)] atunci spunem că f(X) a fost obţinută prin superpoziţia funcţiilor f1(X1) şi f2(X2). Dacă X1(X2 = ( atunci avem o superpoziţie disjunctă, iar dacă X1(X2 ( ( avem o superpoziţie nedisjunctă. x1 f xn După superpoziţie avem: x1 f1 xi f3 f xi+1 f2 xn Decompoziţia funcţiilor booleene Dacă se dă o funcţie booleană şi un set de funcţii se cere să se realizeze o “spargere” a funcţiei booleene. S-a reuşit decompoziţia funcţiei 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] decompoziţia este simplă. m-1 Decompoziţia este nedisjunctă dacă: (Xi = ( i=j m-1 Decompoziţia este disjunctă dacă: (Xi ( ( i=j Exemplu: f(x1,x2,x3,x4) = ((0, 2, 3, 7, 9, 10, 11, 14) 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] 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 corespunzătoare este: x3 În general o diagramă Karnaugh cu “n” expresii (sau variabile) are 2n locaţii. Prin înglobarea în diagramă a “m” expresii (variabile) dimensiunea diagramei se reduce, numărul de locaţii devenind 2n-m. Pentru a minimiza o funcţie prin diagrame Karnaugh cu expresii se fac următorii paşi: se consideră toate variabilele din diagramă ca şi cum ar fi 0 şi se formează suprafeţe (subcuburi) cu constituenţii lui 1; se consideră toate locaţiile cu 1 indiferente şi se formează suprafeţe (subcuburi) cu variabilele înglobate; se consideră intersecţia variabilelor înglobate cu grupările obţinute în pasul 2; se face reuniunea termenilor din paşii 1 şi 3; pentru mai mult de o variabilă înglobată se tratează pe rând conform paşilor 1 - 4 numai câte o variabilă, celelalte fiind considerate 0, iar apoi se scrie reuniunea tuturor termenilor obţinuţi. Exemplu: Să se minimizeze funcţia cu variabile înglobate: x1 x2x3 00 01 11 10 0 a+b 1 c 1 1 1 x Pasul 1. Se obţine x2(x3 + x1(x3 Pasul 2 şi 3. Se obţine c(x2 + (a+b)(x1(x3 Pasul 4. f = x2(x3 + x1(x3 + c(x2 + (a+b)(x1(x3 Curs 3 1.4.3.2. Minimizarea algebrică Minimizarea algebrică a funcţiilor booleene se face cu ajutorul teoremelor algebrei booleene. În cazul în care numărul de variabile este mai mare decât 6 se utilizează metoda de minimizare Quine-Mc Cluskey. Această metodă are avantajul că algoritmul este uşor de implementat pe calculator. Pentru prezentarea metodei vom lua ca exemplu funcţia: f = ( (0, 2, 3, 5, 7, 8, 10, 11, 13, 15) Etapele de minimizare sunt: Se grupează termenii canonici astfel încât termenii din fiecare grupă să conţină acelaşi număr 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 Se compară fiecare termen dintr-o grupă cu toţi cei din grupa următoare, aplicând relaţia de reducere: x1(x2 + x1(x2 = x1. Se grupează termenii care diferă printr-o singură variabilă (o singură poziţie binară). Termenul obţinut prin combinare va conţine pe poziţia respectivă semnul -. Comparare Rezultatul comparării între x1 x2 x3 x4 0, 2 0 0 - 0 0, 8 - 0 0 0 2, 3 0 0 1 - 2, 10 - 0 1 0 8, 10 1 0 - 0 3, 7 0 - 1 1 3, 11 - 0 1 1 5, 7 0 1 - 1 5, 13 - 1 0 1 10, 11 1 0 1 - 7, 15 - 1 1 1 11, 15 1 - 1 1 13, 15 1 1 - 1 În continuare se repetă procedeul de comparare până când nu mai este posibilă nici o reducere. Comparare Rezultatul comparării î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 rezultanţi, (0, 2, 8, 10), (2, 3, 10, 11), (3, 7, 11, 15) şi (5, 7, 13, 15) se numesc implicanţi primi IP. Se aleg acei implicanţi primi IP care asigură acoperirea minimală a termenilor canonici TC. Pentru aceasta se construieşte un tabel de acoperire, în care pe coloane se notează termenii canonici TC, iar pe linii implicanţii primi IP. În intersecţii se notează acei termeni canonici TC acoperiţi de fiecare implicant prim IP. Unii dintre implicanţii primi sunt implicanţi primi esenţiali pentru că acoperă cel puţin un termen canonic al funcţiei, care nu este acoperit de alt implicant prim. Implicanţii primi esenţiali vor face parte în mod obligatoriu din expresia minimizată a funcţiei. În cazul nostru implicanţi primi esenţiali sunt (0, 2, 8, 10) şi (5, 7, 13, 15). Pentru termenii canonici care au rămas neacoperiţi, 3 şi 11, se observă că pot fi aleşi 2 implicanţi primi, (2, 3, 10, 11) şi (3, 7, 11, 15), deci există 2 soluţii de minimizare. f = (0, 2, 8, 10) + (5, 7, 13, 15) + (2, 3, 10, 11) = x2x4 + x2x4 + x2x3 şi f = (0, 2, 8, 10) + (5, 7, 13, 15) + (3, 7, 11, 15) = x2x4 + x2x4 + x3x4 1.4.4. Minimizarea sistemelor de funcţii booleene Sistemele de funcţii booleene sunt exprimate prin f: Bn ( Bm unde B =(0, 1(. Argumentele pot fi de n variabile şi sunt mai multe funcţii de acest tip: f1, f2,…, fm. Pentru a minimiza sistemele de funcţii se caută implicanţi primi pentru f1, f2,…, fm şi pentru produsele f1(f2, f1(f3…, f1(fm, … f1(f2(f3,…, f1(f2(f3(f4,…, … f1(f2(…(fm. Soluţia aleasă pentru implementarea sistemului de funcţii booleene va fi cea care va fi cea mai avantajoasă din punct de vedere al circuitelor disponibile şi al preţului. 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. Calculăm funcţiile 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. Determinăm implicanţii primi din funcţiile simple şi din produsele determinate la punctul 1. Pentru determinarea implicanţilor primi se folosesc diagrame Karnaugh în care se iau toate acoperirile posibile. Pentru f1: 1 1 1 1 Pentru f2: 1 1 1 1 Pentru f3: 1 1 1 1 Pentru f1(f2: 1 1 1 Pentru f1(f3: 1 1 1 1 Pentru f2(f3 şi f1(f2(f3: 1 1 1 3. Construim un tabel în care capetele de linii vor reprezenta funcţiile, iar coloanele vor fi implicanţii primi. f1 1,5 6,7 5,7 x2x3 x1x2 x1x3 - - f2 1,5 4,5 4,6 x2x3 x1x2 x1x3 - i f3 0,2 2,6 6,7 5,7 x1x3 x2x3 x1x2 x1x3 g f - f1(f2 1,5 6 x2x3 x1x2x3 e - f1(f3 5,7 6,7 x1x3 x1x2 d f2(f3 = f1(f2(f3 5 6 x1x2x3 x1x2x3 b a 4. Se notează IP pe coloana a patra din tabel începând cu ultimul, iar cei care apar dublaţi nu se mai notează. 5. Se construieşte un tabel al acoperirilor funcţiilor f1, f2, f3. Notaţii Indicii Funcţia de unde au rezultat f1 f2 f3 1 5 6 7 1 4 5 6 0 2 5 6 7 a 6 f1(f2(f3 x x x 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. Determinăm acoperirile optime ale funcţiilor f1, f2, f3. A(f1) = e,c + e,d,a = A1 + A2 cu e implicant prim esenţial A(f2) = e,h + e,i,a = B1 + B2 cu e implicant prim esenţial A(f3) = g,c,b + g,c,d, + g,f,d + g,a,d = C1 + C2 + C3 + C4 cu g implicant prim esenţial 7. Se scriu toate acoperirile posibile pentru sistemul de funcţii şi se alege acea acoperire care realizează condiţiile de preţ minim şi disponibilitate de piese. Se face tabelul pentru acoperiri: unei acoperiri se face suma costurilor implicanţilor 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 legătură. n-1 C = ( gr ((n-r) r=0 unde gr este numărul subcuburilor din care lipsesc r variabile. Pentru acoperirea A1B1C2, care are elementele e,c,h,g,d, avem costul: 2 C = ( gr ((3-r) = g0(3 + g1(2 + g2(1 = 0(3 + 5(2 + 0(1 = 10 r=0 e = x2x3 c = x1x2 h = x1x3 g = x1x3 d = x1x3 Minimizarea sistemului de funcţii va fi: f1 = x2x3 + x1x2 f2 = x2x3 + x1x3 f3 = x1x3 + x1x3 + x1x2 = x1x2 + x1 + x3 Datorită reducerii corelate a sistemului de funcţii apar porţi comune mai multor funcţii. Curs 4 CAPITOLUL II CIRCUITE LOGICE COMBINAŢIONALE 2.1. Definiţii Circuitele logice combinaţionale, CLC, sunt un caz particular al sistemelor secvenţiale finite sau al automatelor finite, numite automate de grad 0. Circuitele logice combinaţionale se caracterizează prin faptul că variabilele de ieşire sunt independente de timp şi de starea internă, fiind determinate numai de variabilele de intrare (starea variabilelor de intrare la momentul considerat). Legătura dintre starea ieşirii şi starea intrării unui CLC este realizată de funcţia de transfer. x1 y1 x2 y2 CLC xn ym Oricare funcţie de ieşire y (y1, y2,…, ym) este funcţie 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) Funcţiile se vor exprima în forma canonică disjunctivă FCD sau în forma canonică conjunctivă FCC. Independenţa faţă de timp presupune că o dată cu modificarea variabilelor de intrare se modifică simultan şi variabilele de ieşire. Din punct de vedere practic, datorită întârzierilor produse de circuitele logice şi de conexiuni, modificarea simultană nu este posibilă. Ca urmare, pe durata procesului tranzitoriu de stabilire a variabilelor de ieşire, vectorul ieşirilor poate lua valori intermediare diferite de valoarea finală, ceea ce conduce la fenomenul de hazard combinaţional, de care trebuie să se ţină cont la proiectarea unui sistem numeric. În general, la circuitele logice combinaţionale, vom face abstracţie de proprietăţile fizice ale porţilor logice, de faptul că un impuls teoretic diferă de unul real. Vom analiza aceste fenomene doar în cazul hazardului combinaţional. 2.2. Analiza circuitelor logice combinaţionale În cadrul analizei CLC se pleacă de la cunoaşterea schemei logice a circuitului şi se urmăreşte stabilirea funcţionării acestuia. Stabilirea expresiei variabilei de ieşire se face de la intrare la ieşire, urmărind transformările variabilelor de intrare. Definim ca număr de nivele al unui CLC numărul maxim de porţi dintre intrări şi ieşiri. Numerotarea nivelelor se face de la ieşire înspre intrare. x5 x1 x2 y1 x3 x4 y2 x6 x7 4 3 2 1 Circuitul logic combinaţional din exemplu are 4 nivele. Există şi următoarea situaţie de legături între porţi: x1 y x2 x3 Acest circuit are şi legături inverse. Ultimele porţi nu pot fi numerotate, deci circuitul nu este un CLC. În CLC sunt admise legăturile inverse (ieşirea unei porţi dintr-un nivel inferior să fie dusă la intrarea unei porţi dintr-un nivel superior) cu condiţia ca definiţia CLC să fie respectată. Algoritm de determinare a legăturilor inverse în CLC a. Se numerotează toate porţile logice care au ca intrări un subset din mulţimea variabilelor de intrare ale circuitului logic (de la 1 la k); b. Se numerotează de la k+1 porţile care au ca intrări fie intrări ale circuitului, fie ieşiri ale porţilor numerotate la punctul a. Dacă am reuşit să numerotăm toate porţile circuitului logic, acesta este fără legături inverse şi este circuit combinaţional. Dacă nu am reuşit numerotarea tuturor porţilor logice, circuitul este de tip secvenţial. 2.3. Sinteza circuitelor logice combinaţionale În cadrul sintezei circuitelor logice combinaţionale se cunoaşte funcţia pe care trebuie să o îndeplinească circuitul şi se caută să se găsească structura acestuia. Etapele sintezei circuitelor logice combinaţionale sunt: Enunţul problemei; Alcătuirea tabelului de adevăr, definirea funcţiei sau funcţiilor; Minimizarea funcţiei sau funcţiilor; Desenarea schemei circuitului Există mai multe metode de implementare a CLC, diferenţiate 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 până la 50 de tranzistoare integrate pe capsulă. Dintre aceste circuite fac parte porţile 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 funcţiei sau funcţiilor logice cu ajutorul circuitelor integrate existente. CLC de tip SSI se folosesc mai mult pentru adaptarea la aplicaţie a circuitelor de tip MSI şi LSI standardizate, care nu satisfac cu exactitate cerinţele 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 până la 500 de tranzistoare integrate. Ele oferă structuri mai complexe, disponibile ca şi structuri standard. Forma funcţiilor logice pe care dorim să le implementăm cu circuite de tip MSI trebuie să fie corelată cu circuitele disponibile. De obicei nu mai este necesară minimizarea funcţiilor. Circuite combinaţionale uzuale (specializate) 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 ieşire se obţine alt cod. Convertoarele de cod fac compatibilă funcţionarea a 2 sisteme în care informaţia 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 e construiesc diagrame Karnaugh pentru determinarea funcţiilor minimizate pentru b3, b2, b1, b0. Diagrama Karnaugh pentru b3: 11 1 1 1 1 10 1 1 1 1 Obţinem: b3 = g3 Diagrama Karnaugh pentru b2: Obţinem b2 = g2g3 + g2g3 = g2 + g3 Diagrama Karnaugh pentru b1: Obţinem b1 = g1g2g3 + g1g2g3 + g1g2g3 + g1g2g3 = g1(g2 + g3) + g1(g2 + g3) = g1 + g2 + g3 Diagrama Karnaugh pentru b0: Obţinem b0 = g0g1g2g3 + g0g1g2g3 + g0g1g2g3 + g0g1g2g3 + g0g1g2g3 + g0g1g2g3 + g0g1g2g3 + g0g1g2g3 = g2g3(g0 + g1) + … = g0 + g1 + g2 + g3 În general: bn = gn i bi = 1 dacă + ( gj = 1 j=n-1 0 dacă nu 2) Conversia din BCD în Gray: gn = bn gi = bi + bi+1 Codificatoare Codificatoarele sunt CLC la care activarea unei intrări conduce la apariţia unui cuvânt de cod la ieşire. Exemplu: Codificator din zecimal în BCD (binar codificat zecimal) Intrările sunt active pe 0 logic. De exemplu, dacă este activă (adică 0) intrarea 5, pe ieşire se va obţine codul în BCD pentru 5, adică 0101. Funcţiile pentru ieşiri 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 intrări active simultan şi la ieşire se obţine cuvântul de cod care corespunde intrării care este cea mai prioritară. Prioritatea creşte de la cifra 0 înspre cifra 9. Decodificatoare Decodificatoarele sunt CLC la care se activează doar una dintre ieşiri, pentru combinaţia (codul) corespunzătoare a variabilelor de intrare. Ele au funcţie inversă codificatoarelor. Ieşirile decodificatoarelor sunt active pe 0 logic (funcţionează în logică negativă). I1 y1 Circuite SI-NU In ym Numărul ieşirilor distincte este m ( 2n. Exemplu: Decodificator pentru 3 cifre binare. Funcţiile pentru ieşiri sunt: O7 = I2I1I0; O6 = I2I1I0; O5 = I2I1I0; O4 = I2I1I0; O3 = I2I1I0; O2 = I2I1I0; O1 = I2I1I0; O0 = I2I1I0. Multiplexoare Multiplexoarele sunt CLC care permit trecerea datelor de pe una din intrări la o ieşire unică. Selecţia intrării se face printr-un cuvânt de cod de selecţie numit şi adresă. I0 MUX y In-1 sm-1 s0 Cu m linii de selecţie se pot selecta 2m intrări. Funcţia realizată de ieşire este: y = Ik unde k este numărul de combinaţii k = sm-1 ( 2m-1 + … + s0 ( 20 Aplicaţiile cele mai importante ale MUX sunt la selecţia secvenţială a datelor, conversia paralel-serie a datelor, sisteme de transmisie a datelor pe un singur canal, implementarea circuitelor logice combinaţionale cu o singură ieşire. 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 selecţie s şi o ieşire y. În funcţie de semnalul de selecţie avem pentru ieşire: y = I0 ( s + I1 ( s. s = 0 ( y = I0 s = 1 ( y = I1 Deci multiplexorul lasă să treacă spre ieşire semnalul de pe acea linie de intrare corespunzătoare lui s. 2) I0 I1 MUX I2 4 : 1 y I3 s0 s1 Multiplexorul de tip 4:1 are 4 semnale de intrare, 2 semnale de selecţie şi un semnal de ieşire. Ieşirea 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 atât ieşirea adevărată cât şi cea negată. Ele au şi o intrare de “Enable” pentru validare, care permite o funcţie SI suplimentară. Demultiplexoare Demultiplexoarele sunt CLC care permit transmiterea datelor de pe o intrare de date comună pe una din ieşirile selectate. Selectarea ieşirii se face cu ajutorul unui cuvânt de cod de selecţie numit şi adresă. y0 I DEMUX yn-1 sm-1 s0 Cu m linii de selecţie se pot selecta 2m ieşiri. Funcţiile de ieşire sunt: y0 = sm-1 ( … ( s0 ( I y1 = sm-1 ( … ( s0 ( I y2m = sm-1 ( … ( s0 ( I Comparatoare numerice Comparatoarele numerice sunt CLC care permit determinarea valorii relative a două numere binare. Comparatoarele pot fi de 1 bit sau de mai mulţi biţi. Exemplu: Comparator pe 1 bit Ai y1 y2 Bi y3 Funcţiile de ieşire sunt: y1 = Ai ( Bi pentru Ai < Bi, y2 = Ai + Bi pentru Ai = Bi y3 = Ai ( Bi pentru Ai > Bi Acest circuit constituie celula de bază pentru compararea numerelor cu mai mulţi biţi. Detectoare-generatoare de paritate Detectoarele-generatoare de paritate sunt CLC cu rol de a determina şi genera paritatea sau imparitatea numărului de variabile de intrare egale cu 1. Bitul de paritate este utilizat ca metodă de verificare a transferului de date. Sunt posibile 2 situaţii: numărul biţilor de 1 + bitul de paritate = număr par numărul biţilor de 1 + bitul de paritate = număr impar Realizarea detectoarelor de paritate se bazează pe funcţia logică SAU-EXCLUSIV (0 pentru par şi 1 pentru impar). Sumatoare-scăzătoare Sumatoarele şi scăzătoarele sunt CLC care realizează adunarea, respectiv scăderea cifrelor binare. Semisumatorul este un CLC care efectuează suma a 2 numere binare de câte 1 bit, fără a ţine cont de transportul de la bitul de semnificaţie 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 mulţi biţi se realizează prin interconectarea sumatoarelor pentru 1 bit. Adunarea se efectuează în paralel, iar propagarea transportului în serie. Semiscăzătorul de 1 bit are ieşirile: D0 = A0 ( B0 + A0 ( B0 = A0 + B0 I0 = A0 ( B0 Scăzătorul complet de rangul n are ieşirile: 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 Scăzătoarele pentru cuvinte binare cu mai mulţi biţi se realizează prin interconectarea scăzătoarelor pentru 1 bit. Unităţi aritmetico-logice Unităţile aritmetico-logice sunt CLC care realizează operaţii de tip aritmetic şi operaţii de tip logic. Curs 5 2.3.2.1. Implementarea funcţiilor 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 toţi termenii canonici. Implementarea cu DCD a unei funcţii booleene nu necesită operaţii de minimizare. La ieşirea DCD se obţin toţi termenii canonici negaţi ai formei canonice disjunctive FCD ai funcţiei. Realizarea funcţiei se face cu o poartă logică de tip SI-NU, cu un număr de intrări egal cu numărul de termeni ai funcţiei. Implementarea cu MUX a unei funcţii booleene se bazează pe relaţia care defineşte funcţionarea sa. De exemplu, pentru un MUX de tip 4:1 avem ecuaţia ieşirii: y = I0 ( x1 ( x2 + I1 ( x1 ( x2 + I2 ( x1 ( x2 + I3 ( x1 ( x2 în care se observă că există intrări separate pentru fiecare din cele 4 combinaţii ale variabilelor de selecţie x1, x2. Dacă avem o funcţie booleană de n variabile de intrare se pot da factor variabilele x1 şi x2 şi se obţin 4 funcţii de n-2 variabile de intrare, care se vor conecta la intrările 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 funcţie de 4 variabile se pot elimina 3 variabile prin aplicarea lor pe intrările de selecţie ale unui MUX 8:1. La cele 8 intrări ale MUX se vor conecta cele 8 funcţii de o variabilă. Singurele funcţii posibile de o variabilă sunt: xi, xi, 0, 1. Deci putem implementa orice funcţie cu 4 variabile de intrare folosind un singur MUX de 8 căi şi fără porţi adiţionale. Exemplu Considerăm funcţia: f = (0, 1, 3, 5, 9, 10, 13, 15) = x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0 Folosim un MUX 8:1 şi aplicăm variabilele x2x1x0 pe intrările de selecţie. Pentru a determina intrările multiplexorului, I0 – I7, vom face un tabel: I0 x3 x2x1x0 I1 1 (x3 + x3) ( x2x1x0 I2 x3 x2x1x0 I3 x3 x2x1x0 I4 0 x2x1x0 I5 1 (x3 + x3) ( x2x1x0 I6 0 x2x1x0 I7 x3 x2x1x0 Implementarea funcţiei cu MUX este: En x3 1 x3 x3 f 0 f 1 0 x3 s2 s1 s0 x2 x1 x0 Avantajele implementării cu MUX: se poate implementa funcţia cu un sigur circuit de tip MUX; intrarea de Enable poate fi folosită ca un SI final cu întreaga funcţie; doar o singură variabilă trebuie să fie disponibilă şi adevărată şi negată. Dezavantajele implementării cu MUX: nu se pot folosi termeni în comun în cazul minimizării sistemelor de funcţii (sisteme cu mai multe ieşiri); nu se poate face implementarea funcţiilor la care numărul de termeni este mai mare decât numărul intrărilor MUX; există multe funcţii care pot fi implementate comod prin utilizarea de porţi logice ( MUX utilizat doar pentru funcţii dificile. Procedura de implementare cu MUX se poate face plecând de la diagrama Karnaugh. Se construieşte o diagramă Karnaugh în care se defineşte domeniul intrărilor I. x3x2 x1x0 00 01 11 10 00 I0 I1 I3 I2 01 I4 I5 I7 I6 11 I4 I5 I7 I6 10 I0 I1 I3 I2 x3x2 x1x0 00 01 11 10 00 1 1 1 01 1 11 1 1 10 1 1 Variabila care variază este x3. Configuraţiile de 1 din diagrama Karnaugh indică modul de conectare a intrărilor 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ă, conţinutul ei nu se modifică în timpul funcţionării. Structura ei este stabilită în procesul de fabricaţie sau este stabilită de utilizator prin programare. I0 O0 DCD Matrice In-1 Om-1 Memoria ROM este formată din două niveluri de porţi logice: SI (un decodificator) şi SAU-NU (matricea de memorie). DCD din primul nivel primeşte codurile de intrare în binar (n este numărul intrărilor) şi activează pentru fiecare cod o ieşire din cele 2n. Ieşirile 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 fiecărui cuvânt de memorie. Ieşirile sunt de obicei “three-state” sau “open colector” pentru a permite legarea în paralel cu ieşirile altor memorii. Avem notaţiile: n = numărul de biţi ai vectorului de intrare (adresa) c = numărul de cuvinte memorate în ROM ( c = 2n b = numărul de biţi din fiecare cuvânt Numărul de cuvinte trebuie să fie putere a lui 2. Modul de organizare a ROM este specificat prin produsul c x b. Capacitatea memoriei se exprimă prin numărul total de biţi memoraţi: C = 2n x b. Unitatea de măsură pentru capacitatea memoriei este kilobitul (1 Kb = 1024 biţi). Memoriile au o intrare de “Enable” care permite (E = 0) sau inhibă (E = 1) funcţionarea ROM. Dacă memoria este dezactivată, indiferent de adresare, ieşirile sunt pe semnal logic 1. Aplicaţiile mai importante ale memoriilor de tip ROM sunt: memorarea instrucţiunilor şi datelor în sisteme de calcul şi automate secvenţiale; transformări de adresă şi înmagazinarea instrucţiunilor în microprogramare; conversii de cod; generatoare de caractere; generare de secvenţe de impulsuri; implementarea CLC cu un număr mare de variabile de intrare şi ieşire. Implementarea CLC cu un număr mare de variabile de intrare şi ieşire se bazează pe structura internă a memoriei ROM. Pe nivelul de DCD se decodifică toţi termenii canonici. Fiecare cuvânt de la intrarea matricei reprezintă de fapt un termen canonic format din variabilele de intrare. La nivelul următor se adună toţi termenii din expresia oricărei funcţii şi rezultă funcţia de ieşire. Lista de cuvinte din ROM este chiar tabelul de adevăr al CLC. La implementarea cu ROM nu este necesară minimizarea, deoarece sunt memoraţi toţi termenii canonici şi sunt incluse toate posibilităţile de apariţie a acestora în funcţia de ieşire. Pentru folosirea eficientă a memoriei ROM în sinteza funcţiilor booleene, variabilele de intrare şi ieşire trebuie codate, astfel încât să conţină cât mai multă informaţie. 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 numărului de intrări în ROM se utilizează des şi multiplexoarele. Exemplu: Să se implementeze cu ROM funcţiile: 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 A3 x2 A2 16 x 4 biţi x1 A1 x0 A0 CS D3D2D1D0 f2 f1 f0 Cu A s-au notat intrările de adrese, cu D datele şi cu CS (chip select), intrarea de Enable a circuitului. Conţinutul înscris în memorie este dat în tabelul următor: 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 1 0 1 0 0 Scopurile urmărite la implementarea cu ROM sunt: utilizarea unui număr minim de circuite integrate; folosirea integrală a capacităţii memoriei. Pentru implementarea CLC cu memorii ROM trebuie urmărite următoarele etape: stabilirea dimensiunii memoriei necesare pentru aplicaţia respectivă; alegerea tipur