Electronica-Digitala-de-Gheorghe-TOACSE-613-Pag.pdf

Electronic a digital a - Curs Gheorghe TOACS E April 3, 20051

TRANSILVANIA University Bra sov, Electronics and Computers Email: [email protected]

1

Cuprins1 PORT I LOGICE 1.1 SUPORTUL LOGIC PENTRU SISTEMELE DIGITALE . . . . . 1.1.1 Axiomele si teoremele algebrei Booleene . . . . . . . . . . . 1.1.2 Algebre polivalente . . . . . . . . . . . . . . . . . . . . . . . 1.1.3 Funct ii Booleene . . . . . . . . . . . . . . . . . . . . . . . . 1.1.4 Forme canonice . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.5 Forme disjunctive si conjunctive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 POARTA LOGICA 1.3 PARAMETRII PORT ILOR LOGICE . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 PORT I LOGICE IN TEHNOLOGIA BIPOLARA 1.4.1 Inversorul bipolar . . . . . . . . . . . . . . . . . . . . . . . . 1.4.2 Port i logice TTL . . . . . . . . . . . . . . . . . . . . . . . . 1.4.3 Port i pentru magistrale . . . . . . . . . . . . . . . . . . . . 1.5 PORT I IN TEHNOLOGIA CMOS . . . . . . . . . . . . . . . . . . 1.5.1 Tranzistorul MOSFET . . . . . . . . . . . . . . . . . . . . . 1.5.1.1 Tehnologia de fabricat ie a tranzistorului MOS . . 1.5.1.2 Ecuat iile tranzistorului MOS . . . . . . . . . . . . 1.5.2 Inversorul CMOS . . . . . . . . . . . . . . . . . . . . . . . . 1.5.2.1 Caracteristica static a de transfer VO = f (VI ) . . . 1.5.2.2 Proiectarea inversorului CMOS . . . . . . . . . . . 1.5.2.3 Tehnologia de fabricat ie a inversorului CMOS . . 1.5.2.4 Regimul dinamic al inversorului . . . . . . . . . . 1.5.3 Familia de port i logice CMOS . . . . . . . . . . . . . . . . . 1.5.3.1 Poarta NOR si NAND cu dou a intr ari . . . . . . . 1.5.3.2 Port i logice complexe . . . . . . . . . . . . . . . . 1.5.3.3 Seriile de port i ale familiei CMOS . . . . . . . . . 1.5.3.4 Interfat area TTL-CMOS si CMOS-TTL . . . . . . 1.5.4 Poarta de transmisie CMOS . . . . . . . . . . . . . . . . . . 1.5.5 Circuite logice dinamice . . . . . . . . . . . . . . . . . . . . 1.5.6 Metoda efortului logic . . . . . . . . . . . . . . . . . . . . . 1.5.6.1 Determinarea nt arzierii pe o poart a logic a . . . . 1.5.6.2 Calculul nt arzierii n ret elele de port i logice . . . 1.5.6.3 Alegerea num arului optim de niveluri pe un traseu 1.6 REJECT IA ZGOMOTELOR . . . . . . . . . . . . . . . . . . . . . 1.6.1 Reject ia zgomotelor externe . . . . . . . . . . . . . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 7 7 11 14 19 26 31 39 52 52 56 59 66 66 66 72 79 80 83 87 90 94 95 98 105 107 111 115 123 124 131 136 142 148

4 1.6.2 Reject ia 1.6.2.1 1.6.2.2 1.6.2.3 1.6.2.4

CUPRINS zgomotelor interne . . . . . . . . . . . . . . . . . . . . 150 Zgomotul de mas a. . . . . . . . . . . . . . . . . . . . . 150 Zgomotul datorit a neadapt arii liniilor. . . . . . . . . . 151 Zgomotul datorat cuplajului electromagnetic (diafonia) 158 Zgomotul datorit a curent ilor de alimentare . . . . . . 160 173 173 176 177 182 186 191 193 196 199 203 209 213 218 218 220 224 232 233 237 247 250 255 261 263 263 269 272 273 273 275 275 280 287 288 291 293 295 301 301

2 CIRCUITE LOGICE COMBINAT IONALE 2.1 CIRCUITUL LOGIC COMBINAT IONAL . . . . . . . . . . . . . . . . 2.2 REPREZENTAREA CLC . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Tabelul de adev ar . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Reprezentarea analitic a . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Diagrama Veitch - Karnaugh . . . . . . . . . . . . . . . . . . . 2.2.3.1 Minimizarea funct iilor incomplet denite . . . . . . . 2.2.3.2 Minimizare pe diagrame V-K cu variabile reziduu . . 2.2.3.3 Minimizarea prin diagrame V-K a circuitelor cu ie siri multiple . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.4 Diagrama de decizie binar a, BDD . . . . . . . . . . . . . . . . 2.2.5 Modalit a ti neformale de reprezentare . . . . . . . . . . . . . . . 2.3 REALIZAREA CIRCUITELOR COMBINAT IONALE . . . . . . . . . 2.3.1 Hazardul static . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 CLC PENTRU FUNCT II LOGICE . . . . . . . . . . . . . . . . . . . 2.4.1 Codicatorul . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2 Codicatorul prioritar, CDCP . . . . . . . . . . . . . . . . . . . 2.4.3 Decodicatorul, DCD . . . . . . . . . . . . . . . . . . . . . . . 2.4.3.1 Convertorul de cod . . . . . . . . . . . . . . . . . . . 2.4.4 Multiplexorul . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.4.1 Aplicat ii cu circuite multiplexoare . . . . . . . . . . . 2.4.5 Demultiplexorul . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.6 Memoria numai cu citire, ROM . . . . . . . . . . . . . . . . . . 2.4.6.1 Realizarea circuitelor si modulelor ROM . . . . . . . 2.4.6.2 Module de memorie ROM . . . . . . . . . . . . . . . . 2.4.7 Dispozitivele logice programabile, PLD . . . . . . . . . . . . . . 2.4.7.1 Matricea Logic a Programabil a, PLA . . . . . . . . . . 2.4.7.2 Matricea logic a programabil a cu nivel OR x, PAL . 2.4.7.3 Circuitul de tip GAL . . . . . . . . . . . . . . . . . . 2.5 CLC PENTRU FUNCT II NUMERICE . . . . . . . . . . . . . . . . . 2.5.1 Comparatorul . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2 Sumatorul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2.1 Sumatorul cu Transport Progresiv, STP . . . . . . . . 2.5.2.2 Sumatoare de performant a ridicat a . . . . . . . . . . 2.5.3 Multiplicatorul . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.3.1 Multiplicatorul matriceal . . . . . . . . . . . . . . . . 2.5.3.2 Multiplicatorul tip arbore Wallace . . . . . . . . . . . 2.5.3.3 Multiplicatorul tabelar . . . . . . . . . . . . . . . . . 2.5.4 Circuite de deplasare . . . . . . . . . . . . . . . . . . . . . . . . 2.5.5 Unitatea Aritmetic a si Logic a, ALU . . . . . . . . . . . . . . . 2.5.5.1 Calea de date . . . . . . . . . . . . . . . . . . . . . . .

CUPRINS Organizarea si implementarea unei si logic a . . . . . . . . . . . . . . . 2.5.5.3 Structurarea unei ALU elementare PROBLEME . . . . . . . . . . . . . . . . . . . . . 2.5.5.2

5 unit a ti aritmetic a . . . . . . . . . . . 305 . . . . . . . . . . . 306 . . . . . . . . . . . 311 321 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 330 330 332 340 341 344 345 345 354 357 361 372 376 382 383 386 391 395 395 398 402 405 409 418 423 425 428 431 435 439 450 452 452 455 458 460 468 473

2.6

3 CIRCUITE LOGICE SECVENT IALE, CLS 3.1 CIRCUITE LOGICE SECVENT IALE ASINCRONE . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 CIRCUITE LOGICE SECVENT IALE SINCRONE . . . . . . 3.2.1 Sincronizarea semnalelor asincrone . . . . . . . . . . . 3.2.2 Automate nite: structur a, denit ii, clasic ari . . . . 3.2.3 Modalit a ti de reprezentare ale automatelor . . . . . . 3.2.3.1 Graful de tranzit ie al st arilor . . . . . . . . . 3.2.3.2 Tabelul de tranzit ie al st arilor . . . . . . . . 3.2.3.3 Diagrame de variat ie n timp ale semnalelor . 3.2.3.4 Organigrama ASM . . . . . . . . . . . . . . . 3.2.3.5 Limbaje de transfer ntre registre, RTL . . . 3.2.4 Reducerea num arului de st ari . . . . . . . . . . . . . . 3.2.5 Asignarea st arilor . . . . . . . . . . . . . . . . . . . . . 3.2.5.1 Intr ari si ie siri asincrone . . . . . . . . . . . . 3.2.6 Proiectarea automatelor sincrone . . . . . . . . . . . . 3.3 CIRCUITE BASCULANTE . . . . . . . . . . . . . . . . . . . 3.3.1 Circuitul latch . . . . . . . . . . . . . . . . . . . . . . 3.3.1.1 Latch-ul SR . . . . . . . . . . . . . . . . . . 3.3.1.2 Latch-ul D . . . . . . . . . . . . . . . . . . . 3.3.2 Circuite Basculante Bistabile (Triggere) . . . . . . . . 3.3.2.1 Principiul master-slave . . . . . . . . . . . . 3.3.2.2 Bistabilul D . . . . . . . . . . . . . . . . . . 3.3.2.3 Bistabilul JK . . . . . . . . . . . . . . . . . . 3.3.2.4 Bistabilul T . . . . . . . . . . . . . . . . . . 3.3.3 Aplicat ii la automate . . . . . . . . . . . . . . . . . . . 3.3.4 Circuitul basculant bistabil asimetric (Triggerul Schmitt) . . . . . . . . . . . . . . . . . . . . 3.3.5 Circuitul basculant monostabil . . . . . . . . . . . . . 3.3.6 Circuitul basculant astabil . . . . . . . . . . . . . . . . ATOR 3.4 CIRCUITE NUMAR . . . . . . . . . . . . . . . . . . . 3.4.1 Num ar atoare asincrone . . . . . . . . . . . . . . . . . 3.4.2 Num ar atoare sincrone . . . . . . . . . . . . . . . . . . 3.4.2.1 Num ar atoare presetabile . . . . . . . . . . . 3.4.2.2 Num ar atoare n cod arbitrar . . . . . . . . . 3.5 CIRCUITE REGISTRU . . . . . . . . . . . . . . . . . . . . . 3.5.1 Registru paralel . . . . . . . . . . . . . . . . . . . . . . 3.5.2 Circuitul acumulator . . . . . . . . . . . . . . . . . . . 3.5.3 Structura pipeline . . . . . . . . . . . . . . . . . . . . 3.5.4 Registrul de deplasare . . . . . . . . . . . . . . . . . . 3.5.5 Registrul serie-paralel . . . . . . . . . . . . . . . . . . 3.5.6 Circuite liniare cu registre de deplasare . . . . . . . .

6 3.5.7 Distribut ia si aplicarea semnalului de ceas . . MEMORIA CU ACCES ALEATORIU . . . . . . . . 3.6.1 Memoria RAM static a . . . . . . . . . . . . . 3.6.2 Memoria RAM dinamic a. . . . . . . . . . . . 3.6.2.1 Memoria DRAM sincron a, SDRAM 3.6.3 Circuite actuale pentru memoriile de date . . 3.6.4 Memoria adresabil a prin cont inut, CAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

CUPRINS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484 495 499 505 513 526 533 551 551 555 556 557 562 570 572 578 594 599

3.6

4 SUPORTUL CIRCUISTIC PENTRU APLICAT II 4.1 CONEXIUNI PROGRAMABILE . . . . . . . . . . . 4.2 PROIECTAREA DE TIP FULL-CUSTOM . . . . . 4.3 PROIECTAREA CU ARII DE PORT I LOGICE . . 4.4 PROIECTAREA CU CELULE STANDARD . . . . 4.5 PROIECTAREA CU CPLD . . . . . . . . . . . . . . 4.6 PROIECTAREA CU FPGA . . . . . . . . . . . . . . 4.6.1 Blocul Logic Congurabil . . . . . . . . . . . 4.6.2 Resursele de interconectare . . . . . . . . . . 4.7 PROIECTAREA PENTRU TESTABILITATE . . . 4.8 COMBINAT IONAL SAU SECVENT IAL? . . . . . . 4.9 COMPARAT IE INTRE DIFERITELE I DE PROGRAMARE . . . . . . . . . MODALITAT 5 Bibliograe

. . . . . . . . . . 608 611

Capitolul 1

PORT I LOGICE1.1 SUPORTUL LOGIC PENTRU SISTEMELE DIGITALE

Practica sistemelor digitale simple se poate face pe baz a de rat ionamente logice elementare. Dar, deoarece sistemele digitale au devenit foarte complexe, si aceast a tendint a continu a, pentru analiza, proiectarea/sinteza si realizarea acestora este necesar un suport formal abstract si un suport circuistic. Suportul formal abstract se construie ste, prin extensie, pe baza algebrei logice bivalente iar suportul circuistic se construie ste pornind de la poarta logic a. Abordarea ntrep atruns a a acestor dou a componente constituie subiectul acestui capitol.

1.1.1

Axiomele si teoremele algebrei Booleene

In logica aristotelian a, care trebuie nt eleas a ca o stiint a a demonstrat iei, al c arui obiect l constituie stabilirea condit iilor corectitudinii g andirii, se opereaz a pe baz a de rat ionament cu propozit ii (logica propozit iilor), care pot : e adev arate, e false. De exemplu, dac a presupunem c a pentru statura unei persoane sunt admise numai dou a atribute - nalt si scund - iar pentru vreme numai dou a atribute - rece si cald - atunci sunt naturale urm atoarele patru propozit ii simple: vremea este cald a, vremea este rece, Radu este nalt si Radu este scund. Consider and c a din ecare pereche de atribute unul este adev arat si cel alalt fals rezult a c a propozit iile formate cu aceste atribute pot e adev arate e false; o propozit ie nu poate simultan si fals a si adev arat a ( n cazul nostru consider am c a prima si a treia propozit ie simpl a sunt adev arate, iar celelalte dou a sunt false). Dar, cu aceste propozit ii simple pot realizate propozit ii compuse, de exemplu: vremea este cald a si Radu este nalt, vremea este rece sau Radu este scund. Propozit iile compuse pot , la fel, adev arate sau false in funct ie de valoarea de adev ar/fals a propozit iilor componente si de modul de compunere a acestora n propozit ia compus a. Modul de compunere, n acest caz corespunde conectorului AND/S I pentru prima propozit ie compus a, respectiv conectorului OR/SAU pentru a doua propozit ie compus a. Dac a prima propozit ie are valoarea de adev ar, c and vremea este cald a si Radu este nalt, evident c a a doua propozit ie compus a are valoare de fals. Dar dac a prima propozit ie compus a o transform am n nu 7

8

1.1. SUPORTUL LOGIC PENTRU SISTEMELE DIGITALE

este adev arat: c a Radu este nalt si vremea este cald a atunci aceast a nou a propozit ie are o valoare de fals ca si a doua propozit ie compus a? Evident c a da. Dar dac a mai introducem si o a treia pereche de propozit ii simple z apada este alb a, z apada este neagr a si form am propozit ii compuse, dup a diferite moduri de compunere, din c ate una din ecare pereche anterioar a atunci mai putem arma cu u surint a care dintre propozit iile compuse sunt echivalente? Destul de greu. In general, la nivelul normal de dotare intelectual a, un individ cu greu poate realiza un rat ionament corect, f ar a un suport mecanic, c and opereaz a simultan cu mai mult de trei variabile. Pentru ,, a nvinge aceast a incapacitate avem nevoie de un instrument care s a mecanizeze rat ionamentele stufoase. Matematicianul englez George Boole (1815-1854) a elaborat o algebr a (algebra Boolean a) ale c arei axiome si teoreme pot utilizate pentru a transforma (transfera) logica aristotelian a a propozit iilor din domeniul rat ionamentului oral ntr-un limbaj formal, operant cu simboluri (logica formal a). Aceast a logic a formal a poate aplicat a ca un instrument operant si pentru descrierea conect arii, n sisteme, a elementelor zice (mecanice, electrice, hidropneumatice) care prezint a in funct ionarea lor doar dou a st ari distincte. Algebra Boolean a (algebr a logic a binar a, algebr a logic a bivalent a) opereaz a pe o mult ime binar a B: B = 0 = 1 = {x|x = 0, 1} elementul nul elementul unitate (universal).

(1.1)

Tabelul 1.1 Operatorii booleeni; denit ie si simboluri graceOPERATORUL LOGIC SIMBOL TABELUL DE ADEVAR x 0 1 x 0 0 1 1 x 0 0 1 1 x x 1 0 y 0 1 0 1 y 0 1 0 1x y x y x.y

Reprezentarea grafica conform standardului IEC/ANSI911984 varianta veche varianta noua 1 1

Complementarea logica(negatia) NOT / NON Conjunctia, Produsul logic AND / SI Disjunctia, Suma logica OR / SAU

0 0 0 1x y xy x +y

x y

x.y

x y

&

x.y

+

0 1 1 1

x y

x+y

x y

> 1 x+y

ANSI (American National Standard Institute)

CAPITOLUL 1. PORT I LOGICE

9

In aceast a carte elementele mult imii binare reprezint a valorile logice de adev ar sau de fals sau cifrele sistemului de numerat ie n baza doi - bit ( binary digit - cifr a binar a). Exist a concepute si algebre denite pe mult imi care cont in mai mult de dou a elemente, algebre polivalente logic a polivalent a, logic a cu n-valori; cazuri n care mult imea de denit ie este format a din n numere ntregi. O generalizare pentru logica cu n-valori este logica fuzzy, ns a n logica fuzzy variabilele iau valori n mod continuu pe intervalul [0,1]. [Matei 93], [Cocan 01]. Denit ia 1.1 n M Fie M o mult ime nevid a. O aplicat ie f denit a pe M cu valori f :M M se nume ste lege de compozit ie intern a. Algebra Boolean a dene ste pe mult imea B urm atoarele trei legi de compozit ie intern a (la care, obi snuit, ne vom referi si prin termenul de operator logic): 1. Complementarea sau negat ia (NOT/NON); 2. Conjunct ia sau produsul logic (AND/S I); 3. Disjunct ia sau suma logic a (OR/SAU). Tabelul 1.2 Axiomele si teoremele algebrei Booleene DenumireaAxioma 1: Mult imea B = {0, 1} este nchis a n raport cu operatorii + si (Inchiderea) Axioma 2: Asociativitatea Axioma 3: Comutativitatea Axioma 4: Existent a elementului neutru Axioma 5: Distributivitatea Axioma 6: Existent a complementului Teorema 1: Idempotent a sau tautologia Teorema 2: Legea lui 0 si a lui 1 Teorema 3: Dubla negat ie (Involut ia) Teorema 4: Absorbt ia Absorbt ia invers a Teorema 5: Teorema lui De Morgan

Forma cu operatorul produs ()

Forma cu operatorul sum a (+)

x B, y B x y B x B, y B x + y B x (y z ) = (x y ) z xy =yx x1=1x=x xx=0 xx=x x0=0 x=x x + (y + z ) = (x + y ) + z x+y =y+x x+0=0+x=x

x (y + z ) = x y + x z x + y z = (x + y ) (x + z ) x+x=1 x+x=x x+1=1 x=x

x (x + y ) = x x (x + y ) = x y x (x + y ) = x yxy =x+y

x+xy =x x+xy =x+y x+xy =x+yx+y =xy

10


In Tabelul 1.1 sunt prezentate pentru ecare lege de compozit ie boolean a aplicat ia denit a sub forma unui tabel de adev ar precum si simbolurile grace de reprezentare. De si exist a recomandarea pentru utilizarea noilor reprezent ari grace s-a ncet a tenit si continu a folosirea vechilor reprezent ari grace (americane). Denit ia 1.2 O expresie Boolean a f (x1 , x2 , . . . , xn , 0, 1, , +), compus a prin intermediul celor trei operatori AND, OR, NOT prezint a o expresie dual a f D care se obt ine din expresia lui f prin substitut iile urm atoare: AN D OR, OR AN D, 0 1, 1 0 f D (x1 , x2 , . . . , xn , 0, 1, , +) = f (x1 , x2 , . . . , xn , 1, 0, +, ) (1.2)

Dac a o axiom a, teorem a sau expresie boolean a este adev arat a atunci si forma sa dual a este adev arat a. Axiomele si teoremele algebrei Booleene sunt prezentate, sistematic, n Tabelul 1.2. Pentru ecare dintre acestea sunt expuse cele dou a forme, cea n form a produs si cea n form a sum a, ecare ind duala celeilalte. In acest tabel sunt sase axiome si cinci teoreme. Corectitudinea unei expresii booleene se poate verica analitic (prin utilizarea axiomelor si teoremelor din Tabelul 1.2) sau prin calcularea valorilor logice ale expresiilor din cele dou a p art i ale semnului egalit a tii. Folosind aceste dou a modalit a ti n continuare se va verica corectitudinea expresiei teoremei absorbt iei (Teorema 4).

x ( x +y) Axioma 5 x x + x y Teorema 1 x + x y Axioma 4 x 1+ x y Axioma 5 x (1+y) Teorema 2 x 1 Axioma 4 x x ( x+y) =x

x + x y Axioma 4 x 1+ x y Axioma 5 x (1+ y) Teorema 2 x 1 Axioma 4 x x + x y =x

x 0 0 1 1

y 0 1 0 1

x y 0 0 0 1 =

x +y 0 1 1 1

x+ x y 0 0 1 1

x (x + y) 0 0 1 1

=

Continu am demonstrat ia analitic a pentru variantele teoremei de absorbt ie invers a (Teorema 4), dar acum nu se mai indic a succesiune num arul axiomelor si teoremelor aplicate.


11

x + y = x + y 1 = x + y (x + x) = x 1 + y x + y x = x (1 + y ) + y x = x + x y x + y = x + y 1 = x + y (x + x) = x 1 + y x + y x = x (1 + y ) + x y = x + x y

1.1.2

Algebre polivalente

Algebra Boolean a a devenit un suport formal pentru sistemele zice care utilizeaz a elemente cu dou a st ari distincte. Algebra Boolean a, care am introdus-o anterior si la care ne vom referi prin B(2), este cel mai simplu membru al unei familii de algebre Booleene B(q ) bazate pe not iunea abstract a de latice (o latice este o mult ime nevid a ,, ,, L nzestrat a cu dou a operat ii , care satisfac propriet a tile de idempotent a , comutativitate, asociativitate si absorbt ie). Astfel, se poate construi o algebr a Boolean a B (q ) pentru orice num ar q care este o putere a lui doi, q = 2 k . Deci exist a familia de algebre Booleene B (2), B (4), B (8),. . ., B (2 k ). Pentru k = 1, q = 21 rezult a B (2) denit a pe {0, 1} care este chiar algebra Boolean a prezentat a anterior. Pentru k = 2, q = 22 = 4 rezult a B (4) denit a pe mult imea {0, a, b, 1} cu urm atoarele tabele de denit ie ale operatorilor: conjunct ie, disjunct ie si deplasarea ciclic a. 0 a b 1 0 0 0 0 0 a 0 a 0 a b 0 0 b b 1 0 a b 1 + 0 a b 1 0 0 a b 1 a a a 1 1 b b 1 b 1 1 1 1 1 1 x 0 a b 1 x a b 1 0

Conjunct ia

Disjunct ia

Deplasarea ciclic a

Dintre toate algebrele B (q ) numai B (2) este funct ional complet a, deci poate suport pentru implementarea sistemelor logice. O algebr a este funct ional complet a dac a pentru o funct ie de un num ar de variabile se genereaz a doar o singur a reprezentare/expresie. Dezvoltarea tehnologiei electronice a dus la realizarea unor elemente care pot realiza mai multe st ari distincte. Era normal, ca pentru elementele cu mai multe st ari, s a se g aseasc a un suport formal cu valori multiple adic a algebre polivalente, sau q valente, mult imea de denit ie pentru aceste algebre ind format a dintr-un num ar de q elemente distincte. Construct ia algebrelor polivalente a urmat dou a c ai. Prima, a fost o generalizare a operatorilor/(conectivi) booleeni AND, OR si NOT spre operatori corespunz atori conjunct ia, disjunct ia si deplasarea ciclic a obt in andu-se algebrele Postiene (introduse de E.L. Post, 1921). A doua cale, dezvoltat a de B.A. Bernstein (1928), a fost o abordare prin algebra claselor de resturi, operatorii ind adunarea si nmult irea modulo q . O algebr a Postian a q -valent a, P (q ), este denit a pe mult imea {0, 1, 2, . . . , q 1}, adic a pe intervalul de numere ntregi [0, q 1], iar operatorii sunt denit i n felul urm ator: - conjunct ia: x y = min(x, y ); - disjunct ia: x + y = max(x, y ); - deplasarea ciclic a: x = x 1 modulo q .

12


Pentru algebrele Postiene P (2) si P (4) rezult a urm atoarele tabele de adev ar ale celor trei operatori: - P(2) 0 1 0 0 0 1 0 1 Conjunct ia binar a - P(4) 0 1 2 3 0 1 2 0 0 0 0 1 1 0 1 2 0 1 2 Conjunct ia cuaternar a 3 0 1 2 3 + 0 1 2 3 0 1 2 0 1 2 1 1 2 2 2 2 3 3 3 Disjunct ia cuaternar a 3 3 3 3 3 x 0 1 2 3 x x x 1 2 3 2 3 0 3 0 1 0 1 2 Deplasarea ciclic a cuaternar a x 0 1 2 3 + 0 1 0 0 1 1 1 1 Disjunct ia binar a x 0 1 x x 1 0 0 1 Deplasarea ciclic a binar a

Rezult a o identitate ntre B (2) si P (2), (B (2) P (2)). Algebrele Postiene pot o replic a pentru algebrele Booleene, dar operarea n aceste algebre, ca aplicat ii pentru funct iile de comutat ie, devine dicil a pe m asur a ce q are valori mai mari. Cea de a doua cale de generalizare, dezvoltat a de B.A. Bernstein, a generat o alt a clas a de algebre q -valente care pot denite pentru oricare num ar ntreg prin q sau pentru un num ar ntreg putere a lui q . Mult imea de denit ie pentru o astfel de algebr a este {0, 1, 2, . . . , q 1}, iar operatorii sunt operat iile aritmetice de adunare si de nmult ire modulo q . Structurile algebrice denite pe clasele de resturi modulo q (q num ar prim) sunt referite prin c ampuri Galois si sunt notate cu GF (q ) . Pentru GF (3) tabelele de adev ar prin aplicarea operatorilor produs, , si sum a, , modulo 3 sunt: 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1

Dintre structurile GF (q ) cea pentru q = 2, GF (2) algebra modulo 2, denumit a algebr a Reed-Muller, prezint a interes ca suport formal n implement arile unor algoritmi sau circuite de calcul sau de codicare. Operatorii algebrei Reed-Muller au urm atoarele tabele de adev ar: 0 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 x 0 1 x 1 0

Se observ a c a at at pentru algebra Boolean a B (2) c at si pentru algebra ReedMuller, GF (2), operatorii de nmult ire logic a sunt identici ( = ), la fel si operatorii de complementare. In schimb, difer a operatorii disjunct ie, ace stia ind SAU INCLUSIV (sum a logic a, +) n B (2) si respectiv SAU EXCLUSIV (sum a aritmetic a modulo


13

2, ) n GF (2). Aceast a, aparent ne nsemnat a diferent a , determin a semnicative diferent e ntre cele dou a formalisme, ceea ce apare si n metodele de proiectare si implementare. Axiomele pe GF (2) sunt:1. Inchiderea. GF (2) este nchis a n raport cu operatorii si . 2. Asociativitatea. 3. Comutativitatea. 4. Distributivitatea. 5. Elementul neutru. A GF (2), B GF (2) A B GF (2), A B GF (2) A (B C ) = (A B ) C = A B C A (B C ) = (A B ) C = A B C A B = B A, A B = B A A (B C ) = A B A C A 0 = A, A 1 = A

Din prezentarea acestor propriet a ti apare similaritatea dintre GF (2) cu algebra numerelor reale (care este denit a pe un c amp innit). Dar urm atoarea axiom a relev a o proprietate diferit a ntre aceste dou a algebre care rezult a din natura aritmeticii modulo 2. 6. Existent a inversului. A A = 0, A A=A

Din ultima axiom a a algebrei GF (2) rezult a c a A = A, adic a ecare element este egal cu inversul s au; aceasta nseamn a c a adunarea si sc aderea sunt identice n GF (2), ceea ce este diferit fat a de adunarea aritmetic a din algebra numerelor reale. Folosind aceast a axiom a se deduce: dac a A B = C atunci A = C B , B = A C si A B C = 0. Se pot duce relat ii pentru exprimarea operatorilor din B (2) prin cei din GF (2) AB = A B A+B = A BAB A = A1

(1.3-a)

care se pot demonstra n felul urm ator. Se consider a expresia pentru sum a modulo doi A B = A B + A B (a se vedea funct ia f6 (x1 , x0 ) n 1.1.3) A+B A1 = A1+A1=A0+A=A = A + B = A B = ((A 1) (B 1)) 1 = (A B 1 B A 1 1 1) 1 = (A = A BBA11=A BBA

B B A 1) 1

Iar pentru exprimarea operatorilor din GF (2) prin cei din B (2) exist a relat iile A B AB = AB = AB+AB

(1.3-b)

A1

= A

Relat iile 1.3 indic a modalit a ti de utilizare at at a formalismului din GF (2) c at si a celui din B (2) pentru implementarea sistemelor n funct ie de suportul zic (circuistica) disponibil a.

14


1.1.3

Funct ii Booleene

Fie B (2) = ({0, 1}, , +, ) algebra Boolean a binar a. Un cuv ant binar este o succesiune de bit i; un cuv ant este caracterizat prin lungimea sa, adic a de num arul de bit i din succesiune. Denit ia 1.3 Vom numi o congurat ie binar a de n bit i, sau cuv ant binar cu lungimea de n bit i, un element al mult imii {0, 1} n . Cu doi bit i se pot forma patru cuvinte distincte cu lungimea de doi bit i (00, 01, 10, 11), cu trei bit i se pot forma opt cuvinte distincte cu lungimea de trei bit i (000, 001, 010, 011, 100, 101, 110, 111), iar cu n bit i se pot forma 2 n cuvinte distincte ecare cu lungimea de n bit i; deci mult imea {0, 1} n este constituit a din 2n cuvinte distincte cu lungimea de n bit i. Denit ia 1.4 O funct ie Boolean a 1 , f , cu n intr ari si m ie siri este o aplicat ie f : {0, 1}n {0, 1}m (1.4)

cu domeniul de denit ie n X = {0, 1}n si cu domeniul de valori n Y {0, 1}m . Relat ia 1.4, n cazul c and funct ia logic a are o singur a ie sire, m = 1, cuv antul de ie sire are lungimea de un bit, se retranscrie sub forma: f : {0, 1}n {0, 1}1 (1.5)

Teoretic, funct ia logic a cu m ie siri se poate construi din m aplicat ii de forma 1.5 conectate n paralel. O funct ie logic a cu num arul de ordine i dintr-o familie de funct ii logice de n variabile, denit a conform relat iei 1.4, va notat a sub forma fi (xn1 , xn2 , . . . , x1 , x0 ) sau sub forma fin . In acest capitol se vor studia doar funct iile cu o singur a ie sire. Funct ia logic a de zero variabile. Domeniul de denit ie pentru funct ia de zero variabile este mult imea vid a, {0, 1}0 , iar domeniul de valori este {0, 1}. Rezult a c a 0 0 pot exista dou a funct ii notate cu f0 si f1 care genereaz a pe ie sire cele dou a valori din mult imea {0, 1}0 f0 0 f1

= =

0 1

(1.6)

De fapt, putem spune c a aceste funct ii sunt identice cu dou a constante. Intr-un sistem digital cele dou a constante pot reprezentate zic prin dou a tensiuni xe: tensiunea de alimentare (VDD , VCC ) si tensiunea de mas a VSS sau 0V (liniile/barele de alimentare ale circuitului). Funct ii logice de o singur a variabil a. Congurat iile distincte de un singur bit pe mult imea de denit ie {0, 1}1 sunt cei doi bit i 1 si 0. Deci funct ia y = f (x), pentru ecare valoare binar a atribuit a variabilei x, poate lua una din cele dou a valori binare y = 1 sau y = 0. Cu cele dou a valori posibile pentru y se pot forma patru cuvinte 1 1 diferite, deci pentru o singur a variabil a exist a patru funct ii logice distincte: f 0 , f1 , 1 1 f2 si f3 reprezentate n tabelul din Figura 1.1.1 Termenul

de funct ie Boolean a, n aceast a carte, este sinonim cu funct ie logic a.


15

x 0 1

f01 0 0 a)

f11 0 1

f21 1 0

f31 1 1 x

x "0" b) x d)

x c)

x

VCC x e)

"1"

Figura 1.1 Funct iile de o singur a variabil a: a) tabelul funct iilor de o variabil a; 1 1 b) f0 , funct ia zero (conectarea la mas a); c) f2 , funct ia inversor (circuitul inversor); 1 1 d) f1 , funct ia identitate (driver, buer); e) f3 , funct ia tautologie (conectarea la tensiunea de alimentare). 1. Funct ia zero f0 (x) = 0. Aceasta genereaz a valoarea 0 indiferent de valoarea alocat a variabilei x. Intr-un sistem nu se va calcula niciodat a funct ia zero deoarece valoarea acestei funct ii exist a, zic punctul respectiv se leag a la tensiunea de mas a; 1 0 evident f0 si f0 au acela si efect adic a valoarea constant a 0. 2. Funct ia identitate, f1 (x) = x. Logic, aceast a funct ie pare a f ar a utilitate; dar, practic, aceast a funct ie este foarte utilizat a sub denumirea de driver sau buer si ntr-un sistem zic are o act iune de a aduce/ nt ari la anumite valori normale semnalul electric care este suport pentru variabila x. Aceste circuite care nu realizeaz a o funct ie ,, logic a ci doar au rol de nt arire a semnalului electric sunt referite prin circuit buer sau circuit driver respectiv buer sau driver. 3. Funct ia negat ie (NOT), f2 (x) = x. De fapt, acesta este operatorul de complementare din Tabelul 1.1. Putem interpreta aspectul logic sau aritmetic al act iunii acestei funct ii. Logic, funct ia negat ie aplicat a va substitui adev arul cu fals si falsul cu adev ar. Aritmetic, este un incrementor sau decrementor pentru num ararea n baza doi (at at la num arare n sens cresc ator (direct) c at si n sens descresc ator (invers), trecerea ntre dou a numere consecutive se face prin modicarea bitului cel mai put in semnicativ, LSB (Least Signicant Bit), din unu n zero sau din zero n unu, vezi Figura 2.17-a si 2.17-b). Suportul zic pentru implementarea acestei funct ii este elementul inversor. 4. Funct ia tautologie, f3 (x) = 1. Acest a funct ie genereaz a valoarea 1 indiferent de valoarea alocat a variabilei x. Intr-un sistem nu se va calcula niciodat a aceast a funct ie deoarece valoarea sa exist a, zic punctul respectiv se leag a la tensiunea de alimentare 1 0 VDD /VCC ; evident f3 si f1 au acela si efect. Funct ii de dou a variabile. La o funct ie de dou a variabile f (x 1 , x0 ) mult imea de denit ie, {0, 1}2 , este compus a din cele patru cuvinte de intrare de doi bit i. Pentru cele patru cuvinte de intrare se obt in pentru funct ie patru valori binare, dar cu cele patru valori binare se pot obt ine 42 = 16 cuvinte, deci, n total exist a 16 funct ii diferite de dou a variabile care sunt prezentate n tabelul din Figura 1.2-a. Aceste funct ii au anumite denumiri care exprim a act iunea realizat a: 1. f0 (x1 , x0 ) = 0, funct ia zero. Act iunea sa este identic a cu a celor dou a funct ii 0 1 f0 ,f0 .

16


x1 x2 f02 f12 f22 f32 f42 f52 f62 f72 f82 f92 f102 f112 f122 f132 f142 f152 0 0 1 1 0 1 0 1 0 0 0 0 x1 x0 x1 x0 b) f9 = x1 x0 d) 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 1 1 0 a) f6 = x1 x0 x1 x0 x1 x0 e) f7 = x1. x0 c) f1 = x1+x0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1

Figura 1.2 Funct ii de dou a variabile: a) tabelul funct iilor de dou a variabile; 2 b) simbolul grac pentru funct ia XOR, f6 ; c) simbolul grac pentru funct ia NAND, 2 2 f7 ; d) simbolul grac pentru funct ia NXOR, f9 ; e) simbolul grac pentru funct ia 2 NOR, f1 . 2. f1 (x1 , x0 ) = x1 + x0 , funct ia SAU-NEGAT/NOT-OR/NOR cu reprezentarea grac a din Figura 1.2-e. Se observ a c a valorile funct iei rezult a prin negarea valorilor obt inute cu operatorul OR (Tabelul 1.1). ia negarea implicat iei inverse; circuitul interdict ie 3. f2 (x1 , x0 ) = x1 x0 , funct (inhibare). 4. f3 (x1 , x0 ) = x1 , negarea lui x1 . 5. f4 (x1 , x0 ) = x1 x0 , funct ia negarea implicat iei directe; circuitul interdict ie (inhibare). 6. f5 (x1 , x0 ) = x0 , negarea lui x0 . 7. f6 (x1 , x0 ) = x1 x0 + x1 x0 , funct ia negarea coincident ei, SAU-EXCLUSIV/ XOR cu simbolul grac de reprezentare n Figura 1.2-b si cu structura de implementare n Figura 1.3-a. Act iunea acestei funct ii poate interpretat a n trei modalit a ti. Prima, se observ a c a asupra celor dou a valori binare ale variabilelor x 1 si x0 funct ia opereaz a ca un sumator modulo 2 (0 0 = 0, 0 1 = 1, 1 0 = 1, 1 1 = 0) de unde si notat ia consacrat a f6 (x1 , x0 ) = x1 x0 . O alt a variant a echivalent a de exprimare se obt ine n felul urm ator: x1 x0 = x1 x0 + x1 x0 = x1 x0 + x0 x0 + x1 x0 + x1 x1 = x0 (x1 + x0 ) + x1 (x1 + x0 ) = (x1 + x0 )(x1 + x0 ) = (x1 + x0 ) (x1 x0 ). A doua interpretare este cea de inversor comandat, relat iile 1.3. Dac a una din variabile este 1 atunci valoarea funct iei va egal a cu negata celeilalte variabile de intrare; f6 (x1 , 1) = x1 1 = x1 . A treia interpretare este cea de negarea coincident ei, adic a anticoincident a


17

( si invers, negarea anticoincident ei este coincident a, adic a x 1 x0 ). Rezult a c a se poate realiza foarte u sor un circuit pentru coincident a a dou a cuvinte de doi bit i x1 x0 , y1 y0 rat ion and n felul urm ator: cuvintele coincid c and nu este adev arat a anticoincident a pentru bit ii de rangul unu x 1 , y1 SI nu este adev arat a anticoincident a pentru bit ii de rangul zero x0 , y0 ; deci relat ia de coincident a este (x1 y1 ) (x0 y0 ) = (x1 y1 ) + (x0 y0 ). Reprezentarea acestui mod de implementare a relat iei de coincident a este dat a n Figura 1.3-c. ia SI-NEGAT/NOT-AND/NAND, cu simbolul grac 8. f7 (x1 , x0 ) = x1 x0 , funct de reprezentare din Figura 1.2-c. Se observ a c a valorile funct iei rezult a prin negarea valorilor obt inute cu operatorul AND (Tabelul 1.1). 9. f8 (x1 , x0 ) = x1 x0 , funct ia conjunct ie, produsul logic AND, SI. 10. f9 (x1 , x0 ) = x1 x0 + x1 x0 , f9 (x1 , x0 ) = x1 x0 , funct ia coincident a , SAU-EXCLUSIV NEGAT/NXOR cu simbolul grac de reprezentare n Figura 1.2-d si cu structurarea ca n Figura 1.3-b. Implementarea circuitului de coincident a a dou a cuvinte de doi bit i x1 x0 si y1 y0 este prezentat a n Figura 1.3-d; (x1 y1 ) (x0 y0 ). 11. f10 (x1 , x0 ) = x0 , funct ia ce nu depinde de x1 . 12. f11 (x1 , x0 ) = x1 + x0 , funct ia implicat ie direct a. 13. f12 (x1 , x0 ) = x1 , funct ia ce nu depinde de x0 . ia implicat ie invers a. 14. f13 (x1 , x0 ) = x1 + x0 , funct 15. f14 (x1 , x0 ) = x1 + x0 , funct ia conjunct ie, sum a logic a OR, SAU. 16. f15 (x1 , x0 ) = 1, funct ia tautologie, act iunea sa este identic a cu ale funct iilor 0 1 f1 , f3 . Funct ii de trei variabile. Pentru funct iile de trei variabile f (x 2 , x1 , x0 ) mul timea de dent ie, {0, 1}3 , este compus a din opt (23 = 8) cuvinte binare de 3 bit i, pentru ecare din aceste cuvinte funct ia poate avea o valoare binar a 0 sau 1. Cu opt valori binare pot denite 28 funct ii diferite. Modul de formare al funct iilor de trei variabile fi3 , i = 0, 1, . . . , 255 rezult a din Tabelul 1.3. Indicele i, care identic ax1 x1 x 1x 0 x1 x0 x1 x0 x0 x1 x 1x 0 x 1x 0 x1 x0

x0 x1 y1 x0 y0

x0

x 1x 0

a)x 1 = y1 x 1x 0 = y1y0 x 0 = y0 x1 y1 x0 y0

b)x 1=y 1 x 1x 0 = y1y0 x 0=y 0

c)

d)

Figura 1.3 Funct iile XOR si NXOR: a,b) structura circuitelor XOR, respectiv NXOR; c,d) circuite de coincident a cu XOR si NXOR.

18


funct ia fi3 , este corespondentul zecimal al num arului binar de 8 bit i format cu valorile binare ale funct iei. De exemplu funct ia f187 are urm atoarele valori binare 1101 1101, deoarece 187|10 = 1101 1101|2 . Bitul cel mai semnicativ, MSB (Most Signicant Bit), din cuv antul valorilor funct iei, corespunde congurat iei de intrare x 2 x1 x0 = 111, iar LSB corespunde congurat iei de intrare x2 x1 x0 = 000. Utilitatea tuturor funct iilor fi3 pentru implementarea sistemelor logice este discutabil a deoarece , 16 dintre aceste funct ii sunt echivalentul funct iilor f i2 iar unele din cele r amase pot compuse prin intermediul altor funct ii de dou a variabile. In general, pentru implementarea sistemelor logice sunt utilizate doar c ateva din funct iile expuse pentru cazul n = 2. n Pentru n variabile num arul funct iilor logice distincte este 2(2 ) ; ceea ce determin a pentru n = 4 216 = 65536 funct ii, iar pentru n = 5 232 = 4294967296 funct ii(!). Denit ia 1.5 Un sistem complet de funct ii Booleene este un set minimal de funct ii Booleene cu ajutorul c arora se poate exprima orice funct ie Boolean a. In paragraful 1.1.1 s-au denit cele trei legi de compozit ie pe mult imea B . Cu ajutorul celor trei operatori NOT, AND si OR poate exprimat a oricare funct ie logic a, deci ace sti operatori formeaz a un sistem complet. Al doilea set de operatori care pot constitui un sistem complet este perechea NOT si AND. Acest set poate substituit numai cu o singur a funct ie, funct ia f7 (x1 , x0 ) = (x1 x0 ), adic a operatorul NAND, deoarece operatorul NOT apare ca un NAND de aceea si variabil a (x x) = x, iar operatorul AND rezult a ca un NAND negat, (x1 x0 ) = x1 x0 . Al treilea set de operatori OR si NOT formeaz a de asemenea un sistem complet. S i aceast a pereche de operatori poate substituit a numai cu o singur a funct ie, funct ia f2 (x1 , x0 ) = x1 + x0 , care este operatorul NOR. Deoarece NOR este un OR negat se poate obt ine u sor OR prin negarea NOR-ului, (x 1 + x0 ) = x1 + x0 , iar NOT-ul este Tabelul 1.3 Funct ii logice de trei variabile

x2 x1 x0 f03 f13 f23 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0

f173 1 0 0 0 1 0 0 017 10 = 0001001 2

f1873 1 0 1 1 1 0 1 1187 10 = 10111011 2

f2553 1 1 1 1 1 1 1 1


19

identic cu NOR-ul aplicat aceleia si variabile (x + x) = x. In Tabelul 1.4 sunt modelat i operatorii NOT, AND, OR, NAND si NOR e numai cu NAND, e numai cu NOR. Apare, deci, posibilitatea ca un sistem logic s a poat a realizat doar cu un singur operator. Consecint a practic a a acestei observat ii este enorm a prin faptul c a implementarea unui sistem se poate obt ine prin replicarea aceluia si operator (acela si tip de circuit), n consecint a pret ul de cost scade foarte mult si sigurant a n funct ionare cre ste. Exist a circuite integrate, produse de turn atoria de siliciu, dar nc a neterminate, care cont in un singur (sau dou a) circuite logice elementare ntr-un num ar foarte mare, referite ca arie de port i logice (gate-array, vezi sect iunea 4.3). Pe o astfel de arie de port i logice utilizatorul si poate realiza sistemul pentru aplicat ia sa prin proiectarea doar a conexiunilor ntre un num ar de circuite logice elementare. Apoi, turn atoria de siliciu termin a circuitul integrat, prin realizarea conexiunilor proiectate de utilizator, rezult and astfel un circuit cu multe avantaje, la a c arui construct ie a participat at at utilizatorul (custom) c at si turn atoria de siliciu; sistem referit ca ind o proiectare de tip semi-custom.

1.1.4

Forme canonice

Denit ia 1.4 exprim a not iunea de funct ie logic a de n variabile. Cu cele n variabile se pot compune, prin intermediul operatorilor AND, OR si NOT, termenii funct iei si la fel tot cu ace sti operatori pot inclu si termenii n cadrul funct iei. In consecint a , un termen al unei funct ii logice poate avea variabile negate sau nenegate (NOT), care pot nsumate logic (OR) sau nmult ite logic (AND). Denit ia 1.6 Termenul canonic produs este produsul logic a tuturor celor n variabile ale funct iei, negate sau nenegate. Termenul canonic produs este referit ca minterm. Exemplu de termen canonic produs pentru n = 3 poate x 2 x1 x0 . Un termen canonic produs nu poate format din mai mult de n factori (variabile). Dac a ar avea mai mult de n factori atunci ar nsemna c a una sau mai multe variabile ar intra n produsul logic at at negate c at si nenegate ceea ce, conform axiomei de existent a a nsemna c a termenul se reduce la constanta complementului x x = 0, Tabelul 1.2, ar Tabelul 1.4 Modelarea operatorilor logici pe baz a de NAND sau NOROperatorul logic modelat cu poarta: A NOT A A B A = A .A A.B A A A B A = A+A A+B A A A B A.B = A+B A B A+B A B A.B = A+B A.B A+B A B AND A+B A B A+B = A.B A B A+B = A+B A+B A+B A B A.B OR A+B A B A+B = A+B A B A.B = A+B A B A.B A NAND A.B A B A+B = A.B A B A+B = A+B A+B A+B A B A+B NOR A+B

NAND A B

A.B

A.B

B

NOR A B

20


Tabelul 1.5 Codicarea termenilor canonici produs si sum a (n=3)Valoarea variabilelor x2 x1 x0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 Mintermul si codul P i x 2x 1x 0 = P 0 x 2x 1x 0 = P 1 x 2x 1x 0 = P 2 x 2x 1x 0 = P 3 x 2x 1x 0 = P 4 x 2x 1x 0 = P 5 x 2x 1x 0 = P 6 x 2x 1x 0 = P 7 Maxtermul si codul Si x 2 +x 1 + x 0 = S0 x 2 + x 1 +x 0 = S1 x 2 + x 1 + x 0 = S2 x 2 + x 1 + x 0 = S3 x 2 + x 1 + x 0 = S4 x 2 + x 1 +x 0 = S5 x 2 + x 1 +x 0 = S6 x 2 + x 1 + x 0 = S7

i 0 1 2 3 4 5 6 7

0. Un termen produs se noteaz a prin Pi . Num arul tuturor termenilor produs Pi este 2n , deci i = 0, 1, 2, . . . , 2n 1. Dar cum se codic a un minterm prin simbolul Pi ? Se va exemplica pentru cazul n = 3. Un termen canonic produs are valoarea logic a 1 numai atunci c and tot i factorii s ai au valoarea logic a 1. Pentru exemplul anterior de termen produs x 2 x1 x0 , cu valoarea logic a 1, rezult a o unic a congurat ie de valori: x 2 = 1, x1 = 0, x0 = 1. Cuv antul binar format din valorile variabilelor este 101, care este num arul cinci n zecimal, reprezentat n codul de numerat ie binar natural. Deci, iat a c a mintermul x2 x1 x0 poate codicat prin litera P cu indicele 5, adic a P 5 ; dar aceast a codicare trebuie s a e o aplicat ie bijectiv a deci si trecerea invers a de la codul P i la exprimarea ca produs logic canonic a mintermului trebuie s a e unic a. De exemplu, trecerea de la termenul canonic produs P6 la mintermul corespunz ator se face n felul urm ator: 6|10 = 110|2 x2 x1 x0 . Rezult a urm atoarea regul a de codicare a termenilor canonici produs: pentru reprezentarea unui minterm prin simbolul Pi variabilelor negate li se atribuie valoarea zero, iar variabilelor nenegate li se atribuie valoarea unu. Este corect a si reciproca, n cuv antul de cod Pi pentru un bit cu valoarea unu corespunde n produsul logic canonic o variabil a nenegat a iar pentru un bit cu valoarea zero corespunde o variabil a negat a. Aplic and aceast a regul a pentru funct ia de trei variabile se pot scrie relat iile din Tabelul 1.5. Denit ia 1.7 Termenul canonic sum a este suma logic a a tuturor celor n variabile ale funct iei, negate sau nenegate. Termenul canonic sum a este referit ca maxterm. Pentru o funct ie de trei variabile (n = 3) ca un exemplu de termen canonic sum a poate acesta x2 + x1 + x0 . La fel, ca si la termenul canonic produs, un termen canonic sum a nu poate compus din mai mult de n variabile, n caz contrar n termen ar a cu constanta 1. Num arul exista suma x + x = 1, deci valoarea termenului ar egal total de termeni canonici sum a este 2n iar codicarea se face prin simbolul Si . a zero numai atunci c and Termenul canonic sum a x2 + x1 + x0 are valoarea logic


21

ecare termen al sumei are valoarea zero, adic a x 2 = 1, x1 = 0, x0 = 1. Rezult a indicele i al simbolului Si ca ind egal cu num arul zecimal ce este reprezentat n binar de cuv antul format din valorile celor trei variabile adic a 101| 2 = 5|10 , deci S5 . Trecerea invers a, de exemplu de la S6 la maxtermul corespunz ator, se face n felul urm ator 6|10 = 110|2 x2 + x1 + x0 . Rezult a urm atoarea regul a de codicare a termenilor canonici sum a pentru reprezentarea unui maxterm prin simbolul Si : variabilelor negate li se atribuie valoarea unu, iar variabilelor nenegate li se atribuie valoarea zero. Este corect a si reciproca, n cuv antul de cod pentru un bit cu valoarea unu corespunde n sum a logic a canonic ao variabil a negat a iar pentru valoarea zero corespunde o variabil a nenegat a. Conform acestei reguli de codicare pentru n = 3 se pot scrie relat iile din Tabelul 1.5. Se observ a c a, pentru codicare, la aceea si variabil a nenegat a se atribuie valoarea 1 n minterm si 0 n maxterm si pentru aceea si variabil a negat a se atribuie valoarea 0 n minterm si 1 n maxterm. Iar pentru trecerea invers a, de la cod la expresia logic a, unui bit 1 n cuv antul de cod i corespunde o variabil a nenegat a n minterm si o variabil a negat a n maxterm si invers pentru bitul 0. Ca o consecint a , din aceste reguli de codicare, se pot demonstra urm atoarele relat ii: Si = P i ; Pi = S i (1.7)

adic a termenul canonic sum a se obt ine prin negarea termenului canonic produs si invers. La fel, pentru i = j , i, j = 0, 1, 2, . . . , 2n 1, se pot demonstra relat iile: Pi Pj = 0; S i + Sj = 1 (1.8)

(pe baza x + x = 1, x x = 0, Axioma 6). Valoarea unui termen Pi , respectiv Si se poate modica prin intermediul unui coecient binar di {0, 1} n felul urm ator: a) d i Pi = Pi 0 Si 0 dac a di = 1 dac a di = 0 dac a di = 0 dac a di = 1 (1.9-a) (1.9-b)

b) di + Si =

Denit ia 1.8 Forma canonic a normal a disjunctiv a, FCND, a unei funct ii de n variabile este suma logic a a tuturor termenilor de forma 1.9-a.2n 1 i=0

f (xn1 , xn2 , . . . , x1 , x0 ) =

di Pi

(1.10)

Denit ia 1.9 Forma canonic a normal a conjunctiv a, FCNC, a unei funct ii de n variabile este produsul logic a tuturor termenilor de forma 1.9-b.2n 1 i=0

f (xn1 , xn2 , . . . , x1 , x0 ) =

(di + Si )

(1.11)

22


Denit ia 1.10 Forma normal a disjunctiv a, FND, a unei funct ii de n variabile este o sum a numai de mintermi ai c aror coecient i d i = 1 Forma FND se obt ine din FCND prin eliminarea mintermilor ai c aror coecient i au valoarea di = 0. Pentru exprimarea FND se introduce o reprezentare simbolic a, sub forma unei liste f (xn1 , xn2 , . . . , x1 , x0 ) =2n 1 i=0

(d0 , d1 , . . . , d2n 2 , d2n 1 )

(1.12)

care cont ine doar indicii acelor coecient i ai funct iei care au valoare d i = 1. De exemplu, pentru o funct ie de patru variabile:15

f (x3 , x2 , x1 , x0 ) =i=0

(0, 3, 4, 5, 8, 9, 12, 14, 15)

aceast a list a enumer a doar indicii coecient ilor binari d 0 = 1, d3 = 1, d4 = 1, d5 = 1, d8 = 1, d9 = 1, d12 = 1, d14 = 1 si d15 = 1. Denit ia 1.11 Forma normal a conjunctiv a, FNC, a unei funct ii de n variabile este un produs numai de maxtermi ai c aror coecient i d i = 0. Forma FNC se obt ine din FCNC prin eliminarea maxtermilor ai c aror coecient i a sub forma unei di = 1. Pentru exprimarea FNC se introduce o reprezentare simbolic liste f (xn1 , xn2 , . . . , x1 , x0 ) =2n 1 i=0

(d0 , d1 , . . . , d2n 2 , d2n 1 )

(1.13)

care cont ine doar indicii acelor coecient i ai funct iei care au valoarea d i = 0. Lu and ca exemplicare funct ia dat a la relat ia 1.12 de data aceasta lista va 15

f (x3 , x2 , x1 , x0 ) =i=0

(1, 2, 6, 7, 10, 11, 13),

adic a sunt enumerat i doar indicii coecient ilor binari care au valoarea zero. Uneori este avantajos s a se lucreze cu negata formei normale conjunctive sau cu negata formei normale disjunctive ale funct iei care pot exprimate respectiv sub formele a) f (xn1 , xn2 , . . . , x1 , x0 ) =2n 1 i=0 2n 1 i=0

(di + Si ) (d i P i )

(1.14-a)

b)

f (xn1 , xn2 , . . . , x1 , x0 ) =

(1.14-b)

Aceste forme de scriere se pot obt ine pornind de la relat iile 1.10 si 1.11, prin negarea ambelor p art i, apoi aplicarea teoremei lui DeMorgan si tin and cont de relat iile 1.7, n felul urm ator:


23

f (xn1 , xn2 , . . . , x1 , x0 ) =

2n 1 i=0

(di Pi ) =

2n 1 i=0

(d i + P i ) =

2n 1 i=0

(di + Si )

f (xn1 , xn2 , . . . , x1 , x0 ) =

2n 1 i=0

(di + Si ) =

2n 1 i=0

(di S i ) =

2n 1 i=0

(di Pi )

Aceste exprim ari se pot deduce si prin rat ionament din relat iile 1.10 si 1.11. Din FCND se obt ine FND dac a se consider a numai termenii canonici produs care au valoarea 1, relat ia 1.12, respectiv din FCNC se obt ine FNC, relat ia 1.13, dac a se consider a numai termenii canonici sum a care au valoarea 0. Sub forma FND funct ia are valoarea 1 pentru suma tuturor termenilor canonici care au coecient ii d i = 1 si are valoarea 0 pentru suma tuturor termenilor canonici care au coecient ii d i = 0. Evident c a funct ia negat a f va avea valoarea 1 pentru suma tuturor acelor termeni canonici care produc valoarea 0 pentru f , adic a pentru acei coecient i d i care sunt 0; respectiv funct ia negat a f va avea valoarea 0 pentru suma tuturor acelor termeni canonici care produc valoarea 1 pentru f , adic a pentru acei coecient i d i = 1. Deci a ca o form a FND, relat ia 1.14-b, de acei termeni produs funct ia negat a f poate scris pentru care di = 1, adic a pentru acei coecient i di care au valoarea 0 la scrierea funct iei f sub form a FND. Acela si rat ionament se poate face si pentru forma FNC, adic a se scrie funct ia f pentru coecient ii d i care au valoarea 0 iar funct ia f , relat ia 1.14-a, pentru coecient ii care au valoarea 1, adic a d i = 0. O modalitate uzual a de denire a unei funct ii logice este cea prin tabelul de adev ar. Denit ia 1.12 Tabelul de adev ar este un tabel care n prima coloan a din st anga, coloana de intrare, listeaz a toate congurat iile de valori ale variabilelor de intrare X = {0, 1}n , iar n urm atoarele coloane, coloane de ie sire, sunt listate valorile, din Y {0, 1}, corespunz atoare ie sirilor. Astfel de tabele de adev ar au fost prezentate init ial n Tabelul 1.1 pentru introducerea operatorilor booleeni NOT, AND, OR iar apoi n Figurile 1.1, 1.2 si Tabelul 1.2, respectiv pentru funct ile logice de una, dou a si trei variabile. Exemplul 1.1 Pentru o celul a sumator complet s a se deduc a funct ia logic a sum a, s i si funct ia logic a pentru transferul urm ator, Ci . Solut ie. In sect iunea 2.5.2 se va analiza sumarea a dou a cuvinte binare cu lungimea de n bit i A = An1 An2 . . . Ai . . . A1 A0 si B = Bn1 Bn2 . . . Bi . . . B1 B0 . Operat ia de sumare a celor dou a cuvinte se realizeaz a pentru ecare pereche de bit i (Ai , Bi ) ncep and cu perechea i = 0, de rangul cel mai put in semnicativ, (20 ), p an a la perechea i = n 1, de rangul cel mai n1 semnicativ, (2 ). Pentru ecare rang aceast a sumare este efectuat a cu o celul a sumator complet. O celul a sumator complet pentru rangul i are trei intr ari Ai , Bi , Ci1 care sunt respectiv bit ii celor dou a cuvinte A si B si transportul anterior Ci1 ce a fost generat de celula din rangul 2(i1) . Semnalele generate la ie sire de c atre celula sumator complet sunt doi bit i: si sum a (= Ai + Bi + Ci1 ) si Ci transportul urm ator care se aplic a la celula de rang 2(i+1) ca transport anterior. Celula sumator complet este notat a uneori cu simbolul (3, 2), indic and faptul c a are trei intr ari si dou a ie siri. Exist a si celula (2, 2) care are numai dou a intr ari Ai si Bi (nu se consider a transportul anterior Ci1 ) care este referit a ca celul a semisumator. Pentru o celul a sumator complet tabelul de adev ar este prezentat n Tabelul 1.6.

24


Tabelul 1.6 Tabelul de adev ar pentru o celul a sumator/sc az ator completIntrari Adunare Bi C i1 / Ii1 si C i gi pi 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 1 Scadere di I i 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 Numarator de 1 Ci si 0 0 0 1 0 1 1 1 0 1 1 0 1 0 0 1 (0) (1) (1) (2) (1) (2) (2) (3)

Ai 0 0 0 0 1 1 1 1

Pentru ie sirea sum a si forma normal a canonic a disjunctiv a, FNCD conform relat iei 1.10, este :7

si (Ai , Bi , Ci1 ) =

i=0

di P i = d 0 P 0 + d 1 P 1 + d 2 P 2 + d 3 P 3 + d 4 P 4 + d 5 P 5 + d 6 P 6 + d 7 P 7

unde di , i = 0, 1, 2, . . . , 7 sunt coecient ii funct iei din coloana si din Tabelul 1.6. Evident c a produsele pentru care di = 0 pot eliminate deoarece au valoarea 0 si se obt ine forma normal a disjunctiv a, FND. si (Ai , Bi , Ci1 ) = = 1 P1 + 1 P2 + 1 P4 + 1 P7 =

Ai B i Ci1 + Ai Bi C i1 + Ai B i C i1 + Ai Bi Ci1

Se observ a c a FND se poate scrie direct lu and numai acei mintermi pentru care funct ia are valoarea 1 n tabelul de adev ar,7

si (Ai , Bi , Ci1 ) =

(1, 2, 4, 7)0

,, de unde si expresia de sintez a pe baz a de 1 . Aplic and axiomele si teoremele din Tabelul 1.2, si expresiile pentru XOR si NXOR, forma normal a disjunctiv a pentru s i se transform a n felul urm ator: si (Ai , Bi , Ci1 ) = = Ai (B i Ci1 + Bi C i1 ) + Ai (B i C i1 + Bi Ci1 ) = Ai (Bi Ci1 ) + Ai (Bi Ci1 ) = Ai Bi Ci1

(1.15)

Dar din Tabelul 1.6 se poate face si sinteza funct iei negate si , aceasta va avea valori 1 ia 1.14-b, deci forma normal a disjunctiv aa (di = 1) acolo unde si are valori 0 (di = 0), relat funct iei negate se scrie direct examin and tabelul de adev ar:7

si (Ai , Bi , Ci1 )

=i=0

(0, 3, 5, 6) = Ai B i C i1 + Ai Bi Ci1 + Ai B i Ci1 + Ai Bi C i1 = Ai (B i C i1 + Bi Ci1 ) + Ai (B i Ci1 + Bi C i1 ) = Ai Bi C i1

= = =


25

Se pune ntrebarea care cale se alege pentru sinteza funct iei, cea prin FND pentru funct ia negat a sau cea prin FND pentru funct ia nenegat a? R aspunsul este evident: prin calea care solicit a mai put in efort, adic a cea care duce la o form a FND cu mai put ini mintermi. Pentru funct ia Ci sinteza se face din tabelul de adev ar, de data aceasta pe baz a de zerouri, adic a prin formele conjunctive. Forma canonic a normal a conjunctiv a, FCNC, conform exprim arii din relat ia 1.11, se va scrie:7

Ci (Ai , Bi , Ci1 )

=i=0

(di + Si ) = (d0 + S0 ) (d1 + S1 ) (d2 + S2 ) (d3 + S3 ) (d4 + S4 ) (d5 + S5 ) (d6 + S6 ) (d7 + S7 )

=

unde di , i = 0, 1, . . . , 7 sunt coecient ii funct iei din coloana Ci . Se pot elimina factorii pentru care di = 1 deci se ajunge la forma normal a conjunctiv a FNC,7

Ci (Ai , Bi , Ci1 ) =

(0, 1, 2, 4)0

,, care se putea scrie direct prin inspectarea valorilor de zero (sintez a pe baz a de 0 ) si scrierea produsului de maxtermi n felul urm ator: Ci = = S 0 S1 S2 S4 =

(Ai + Bi + Ci1 ) (Ai + Bi + C i1 ) (Ai + B i + Ci1 ) (Ai + Bi + Ci1 )

Aplicarea propriet a tii de distributivitate la aceast a expresie duce la 3 3 3 3 = 81 termeni produs care apoi sunt redu si prin aplicarea axiomelor si teoremelor algebrei Booleene. A doua cale de sintez a pe baz a de zerouri se poate face pentru funct ia negat a C i prin inspectarea tabelului de adev ar se aleg maxtermii pentru care funct ia are valoarea 1, relat ia 1.14-a. Rezult a forma normal a conjunctiv a, FNC, pentru funct ia negat a7

C i (Ai , Bi , Ci1 )

=0

(3, 5, 6, 7) = (Ai + B i C i1 ) (Ai + B i + Ci1 ) (Ai + B i + Ci1 ) (Ai + B i + C i1 )

=

si de data aceasta se pot obt ine 81 de termeni produs care pot redu si. Uzual, se alege ntre sinteza prin FNC pentru funct ia negat a sau sinteza prin FNC pentru funct ia nenegat a prin observarea n tabelul de adev ar care cale duce la mai put ini maxtermi. Din aceste dou a tentative de sintez a pe baz a de zero se constat a dicultatea aplic arii formelor conjunctive, acesta este unul din argumentele pentru care n practic a se aplic a aproape n exclusivitate sinteza pe baz a de 1, adic a FND, e pentru funct ia negat a f , e pentru funct ia nenegat a f. In consecint a , revenind la sinteza pe baz a de 1 rezult a pentru Ci7

a) Ci (Ai , Bi , Ci1 ) = =

(3, 5, 6, 7) =i=1

Ai Bi Ci1 + Ai B i Ci1 + Ai Bi C i1 + Ai Bi Ci1

(1.16)

o form a rezonabil a, fat a de sintezele anterioare prin FNC si care prin procedee analitice este adus a la urm atoarele forme disjunctive FD: b) Ci (Ai , Bi , Ci1 ) c) Ci (Ai , Bi , Ci1 ) = = Ai (Bi Ci1 ) + Bi Ci1 Ci1 (Ai Bi ) (Ai Bi )

26


1.1.5

Forme disjunctive si conjunctive

Forma disjunctiv a FD a funct iei este o sum a de termeni necanonici de unde si denumirea de sum a de produse, iar forma conjunctiv a FC a funct iei este un produs de termeni sum a necanonici, denumit a si produs de sume. Reducerea formelor normale disjunctive (FND) sau normale conjunctive (FNC), respectiv la FD sau FC este referit a ca un procedeu de minimizare a funct iei, de si uneori nu se obt ine forma minim a sau se obt in mai multe expresii (neminime). Exist a trei modalit a ti de minimizare: 1 - analitic a, utiliz and axiomele si teoremele algebrei Booleene. Aceast a cale este ecient a doar pentru funct ii cu num ar mic de variabile si de termeni. 2 - prin metode grace (de exemplu diagrama Veitch - Karnaugh), de asemenea utilizabile pentru funct ii care nu au mai mult de 5-6 variabile. 3 - pe baza unor algoritmi sau abord ari euristice . Exist a algoritmi (de exemplu Quine - McQlusky) care pot aplicat i unor funct ii cu zeci de variabile si ie siri multiple. Ace sti algoritmi stau la baza programelor de minimizare (de exemplu Espresso - MV) incluse n medii de Programare Automat a n Electronic a, referite prin termenul tehnici EDA (Electronic Design Automation). Minimizarea pe cale analitic a implic a put in a practic a n utilizarea axiomelor si teoremelor algebrei booleene. Aceast a practic a nu se bazeaz a pe un algoritm anume ci mai mult pe intuit ie. Astfel se pot ad auga termeni (tautologia) care apoi se grupeaz a cu alt ii nc at s a se aplice (cel mai frecvent ) axioma de existent a a complementului iei sau absorbt ia invers a. (x + x = 1), teorema absorbt Exemplul 1.2 Pentru urm atoarea form a normal a disjunctiv aF (A, B, C, D) = AB C D + AB C D + AB C D + AB C D + AB C D + +A B C D + A B C D + A B C D + A B C D + A B C D s a se deduc a forma minim a. Solut ie. Se grupeaz a c ate doi termeni canonici pentru a se aplica axioma de existent a a complementului (dar pentru aceasta unii termeni A B C D, A B C D se dubleaz a) n felul urm ator: F (A, B, C, D) = = = = = A B D (C + C ) + ( A B C D + A B C D ) + ( A B C D + A B C D ) + +(A B C D + A B C D) + (A B C D + A B C D) + A B D (C + C ) = A B D + A B C (D + D) + B C D(A + A) + B C D(A + A) + +A B C (D + D) + A B D = B D(A + A) + A B C + B C D + B C D + A B C = B D + B D (C + C ) + B ( A C + A C ) = B D + B D + B (A C + A C )

pentru care aplic and expresia funct iei SAU EXCLUSIV NEGAT se obt ine F (A, B, C, D) = B D + B (A C )


27

Uneori se pune problema de a se parcurge traseul invers adic a pentru o form a minim a s a se deduc a forma normal a disjunctiv a din care a provenit. In general, pentru o astfel de extindere de la un termen produs la un termen canonic produs se introduc n termenul produs variabilele care lipsesc sub forma x + x. De asemenea, pentru ca o form a disjunctiv a s a e extins a la forma normal a conjunctiv a (produse de sume) suma de termeni produs trebuie transformat a ntr-un produs de sume utiliz and axioma distributivit a tii A + B C = (A + B ) (A + C ), iar n termenii sum a variabilele care lipseau se introduc prin axioma de existent a a complemntului x x = 0. Exemplul 1.3 Urm atoarea form a disjunctiv a F (A, B, C ) = A B + A C s a e extins a la forma normal a conjunctiv a. Solut ie. In primul r and termenii produs sunt convertit i n termeni sum a utiliz and axioma de distributivitate.F (A, B, C ) = = (A B + A) (A B + C ) = (A + A) (B + A) (A + C ) (B + C ) = (A + B ) (A + C ) (B + C )

Fiec arui termen sum a i lipse ste o variabil a care se introduce n felul urm ator: A+B A+C B+C In nal se obt ine:7

= = =

A + B + C C = (A + B + C ) (A + B + C ) A + C + B B = (A + B + C ) (A + B + C ) B + C + A A = (A + B + C ) (A + B + C )

F (A, B, C )

=

(A + B + C ) (A + B + C ) (A + B + C ) (A + B + C ) =0

(0, 2, 4, 5)

Expresiile sub form a de sume de produse sau produse de sume se pot modela pe dou a niveluri de operatori respectiv pe AND-OR sau OR-AND. De exemplu urm atoarele forme FD si FC: F1 = A B + C D si F2 = (A + B )(C + D)

pot modelate ca n Figura 1.4-a si 1.4-b. Uneori se impune ca modelarea s a se fac a e numai cu operatorul NAND sau e numai cu operatorul NOR. Pentru forme FD modelarea se face u sor pe baza operatorului NAND (not am simbolic prin AB (A, B )) deoarece aplic and sumei de produse teorema dublei negat ii si apoi teorema lui DeMorgan se obt ine tocmai un NAND de NAND-uri. In schimb pentru forme FC modelarea se face mai u sor pe baza operatorului NOR (not am simbolic prin A + B (A, B )) deoarece aplic and produsului de sume teorema dublei negat ii si apoi teorema lui DeMorgan se obt ine tocmai un NOR de NOR-uri. Astfel F1 si F2 devin: F1 F2 = = AB + C D = AB C D ( (A, B ), (C, D)) ( (A, B ), (C, D))

(A + B ) (C + D) = (A + B ) + (C + D)

28A B C D a) A B C D b)

1.1. SUPORTUL LOGIC PENTRU SISTEMELE DIGITALEA B C D A.B

F 1 = A. B + C. D

F 1 = (A. B) .(C. D)

C .D c)

F 2 = (A+B).(C+D)

A B C D

A+B F 2 = (A+B)+(C+D) C+D

d)

Figura 1.4 Implementarea formelor FD si FC: a,b) pe dou a niveluri AND-OR, respectiv OR-AND; c,d) pe dou a niveluri NAND-NAND, respectiv NOR-NOR.

Num ar and simbolurile si rezult a c a pentru ecare funct ie sunt necesari trei operatori NAND respectiv NOR cu c ate dou a intr ari cum se poate vedea si n Figura 1.4-c si 1.4-d. Variabilele negate pot obt inute prin x (x, x) sau (x, x). Uneori pentru conversia model arii de tip AND-OR sau OR-AND, respectiv ntr-o modelare de tip NAND-NAND sau NOR-NOR se pot utiliza anumite reguli grace de transformare, care rezult a din axiomele si teoremele algebrei Booleene. Aceste reguli sunt:

Regula 1. La ie sirea unui operator se poate introduce un cerculet de negat ie dar atunci trebuie introdus un cerculet de negat ie si la intrarea operatorului imediat ,, urm ator (Dubla negat ie este adev ar ), deci pe conexiunea ntre cei doi operatori variabila nu sufer a modic ari;

Regula 2. Introducerea unui cerculet de negat ie pe ie sirea unei funct ii trebuie urmat a, tot pe ie sire, de ad augarea nc a a unui cerculet de negat ie (buer inversor). Respectiv, introducerea la o variabil a de intrare, ntr-un operator, a unui cerculet de negat ie trebuie precedat a de negarea aceleia si variabile de intrare (aplicarea pe intrare a variabilei negate);

Regula 3. C and se face conversia unui simbol grac init ial ntr-unul nal, AND/NAND OR/NOR, se pot introduce la simbolul nal cerculet e de negat ie e la intrare, e pe ie sire, e at at la intrare c at si la ie sire dar numai dac a la terminalele corespunz atoare ale simbolului init ial nu a existat un cerculet de negat ie n felul urm ator (de fapt aceast a regul a nu este dec at o aplicare grac a a teoremei lui DeMorgan):


29

AND

OR

NAND

NOR

Exemplul 1.4 Pentru conversiile din Figura 1.4 s a se aplice regulile grace de transformare. Solut ie. Aplic and regulile de conversie grac a se obt in succesiunile de circuite ca n Figura 1.5.A B C D F = A. B + C. D F = (A.B). (C.D) A F B C regula 1 D A B F C regula 3 D F

a) Maparea AND OR in NAND NAND este o conversie naturala F = A. B + C. D F = (A+B)+(C+D) A F B C regula 3 D F

A B C D

A F B C regula 2 D

b) Maparea AND OR in NOR NOR este o conversie nepotrivita A B C D F = (A+B)(C+D) F = (A+B)+(C+D) A F B C regula 3 D F A F B C regula 1 D

c) Maparea OR AND in NOR NOR este o conversie naturala F = (A+B)(C+D) A B C D F = (A B)(C D) A F B C regula 3 D F

A F B C regula 1 D

d) Maparea OR AND in NAND NAND este o conversie nepotrivita

Figura 1.5 Exemple de conversii grace de tipul AND-OR/OR-AND n NAND-NAND sau NOR-NOR. Uneori apare si problema invers a a model arii, pentru o modelare dat a s a se determine expresia FD sau FC care l descrie, de fapt aceast a abordare pentru un sistem deja implementat este referit a ca analiza sistemului. Se poate obt ine funct ia logic aa modelului prin urm atoarele trei modalit a ti: 1 - pentru ecare congurat ie de valori logice ale variabilelor de intrare se deduc

30


valori logice n punctele intermediare ale modelului si respectiv se calculeaz a valoarea logic a de ie sire si n felul acesta se construie ste tabelul de adev ar. Apoi, din tabelul de adev ar rezultat se deduce funct ia logic a. 2 - se scriu expresiile logice dup a ecare simbol de operator logic, pornind de la ecare intrare nspre ie sire, rezult and dup a ultimul operator expresia logic aa funct iei. Aceast a modalitate este asem an atoare cu prima: se merge de la intrare schemei spre ie sire din punct n punct, dar la prima modalitate cu valorile funct iei pe c and la aceast a modalitate cu expresiile funct iei. 3 - utiliz and convent iile prin cerculet e de negat ie. A treia modalitate este recomandat a doar atunci c and operatorii au ie sirile negate (NAND, NOR) sau au intr ari negate, deci parcurgerea de la intrare spre ie sire ridic a anumite dicult a ti. De ce? pentru c a suntem mai obi snuit i s a oper am cu operatorii AND si OR cu intr ari nenegate. De fapt, aceasta se reduce tot la a doua modalitate dar prin conversia operatorilor care cont in cerculet e de negat ie n operatori f ar a aceste cerculet e, se ajunge la o reprezentare numai cu operatori AND si OR. Exemplul 1.5 Pentru modelele de circuite din Figura 1.6-a, 1.6-c s a se deduc a expresia funct iilor (aplic and cerculet ele de negat ie).A B C A B C F D

F

c)regula 3 A B C D

a)regula 3

F

A B C

d)F F = A. (B+C) A B C D regula 3

b)

F

e)

F = (A+B). C+D

Figura 1.6 Exemple de conversie a modelelor logice spre structuri cu operatori AND si OR pentru determinarea funct iilor logice.Solut ie. Pentru modelul din Figura 1.6-a se aplic a regula 3 si se obt in numai operatori AND si OR, F = A (B + C ). Pentru modelul din Figura 1.6-c se aplic a de dou a ori regula 3 si structura poate considerat a ca ind compus a doar din operatori AND si OR pentru care se scrie foarte simplu expresia logic a, F = D + C (A + B ).


31

Acest mod de transformare a modelelor logice este foarte indicat n depanarea circuitelor deoarece pornind de la intrare spre ie sire, dup a ecare nivel logic de OR sau AND se poate verica simplu corectitudinea semnalelor. In ncheierea prezent arii acestor not iuni de suport formal pentru sistemele digitale accentu am faptul c a formele normale disjunctive, FND, sau formele disjunctive, FD, (sum a de produse) pot modelate pe dou a nivele logice AND-OR. De asemenea, formele normale conjunctive, FNC, sau formele conjunctive, FC, (produse de sume) pot modelate pe dou a nivele logice OR-AND. Aceste armat ii sunt adev arate n mod teoretic c and operatorii AND, OR se aplic a pentru orice num ar de intr ari si exist a disponibile si variabilele negate. In practic a, unde un operator este o poart a logic a, trebuie luate cu precaut ie aceste armat ii n funct ie de port ile disponibile si de num arul de intr ari ale acestora (adic a de restrict iile electrice de conectivitate ale acestor port i).

1.2

POARTA LOGICA

C and se trece de la formele FND, FNC la FD, FC si de la modelele acestora pe baz a de operatori NOT, AND, OR, NOR, NAND, la implement ari reale pe baz a de circuite electronice pentru operatorii logici se folose ste, n exprimare, termenul de poart a logic a. Prin termenul de poart a logic a se face referire la orice circuit electronic care implementeaz a un operator logic, deci exist a poarta inversor (NOT), poarta AND, poarta OR, poart a XOR, poarta NAND etc. Prin referirea tuturor circuitelor logice cu termenul de poart a logic a apare un abuz de limbaj care, totu si, are o justicare din punct de vedere al transferului semnalului (variabile logice binare) prin circuit. Consider and operatorii logici prezentat i n Tabelul 1.7, cu cele dou a intr ari A,C si ie sirea f , se poate analiza cum pentru transferul semnalului logic A spre ie sirea f , prin condit ionarea de c atre semnalul C (de control), circuitul electronic care implementeaz a un astfel de operator are un comportament similar cu ,, utilizarea/funct ionarea unei port i. Astfel, c and circuitul poart a este deschis las a semnalul A s a treac a modicat sau nemodicat spre ie sirea f , iar c and poarta este ,, nchis a semnalul A nu se transfer a la ie sirea f . Intuitiv, n aceast a analogie, poarta este nchis a sau deschis a de c atre cineva, adic a n cazul unui circuit de un semnal de control, variabila C . De exemplu, pentru poarta AND c and este deschis a, C = 1, semnalul de intrare A se transfer a la ie sire f = A, iar c and este nchis a, C = 0, semnalul de intrare A nu se transfer a la ie sire, f este ncontinuu la valoarea logic a 0. Poarta XOR, este put in mai special a, este permanent deschis a, transfer a la ie sire semnalul de intrare nemodicat pentru C = 0, f = A (A 0 = A), iar pentru C = 1 transfer a spre ie sire intrarea A negat a, f = A (A 1 = A); poarta XOR are o funct ionare de circuit inversor comandat. O astfel de interpretare, de circuit poart a, se poate g asi pentru oricare din operatorii prezentat i n Tabelul 1.7. Analiz and n paralel poarta AND si poarta OR se poate observa c a poarta AND este deschis a pentru C = 1 iar poarta OR este deschis a pentru C = 0, astfel spunem c a una este deschis a c and semnalul C este activat n 1 logic iar cealalt a c and semnalul C este activat n 0 logic. P an a acum ata sam valorii de adev ar, pentru o variabil a,

32

1.2. POARTA LOGICA

Tabelul 1.7 Interpretarea operatorilor logici ca circuite poart aINTRARI C 0 0 1 1 Iesirea este : A 0 1 0 1 AND OR NAND NOR XOR NXOR

A C

f A C

f A

f A C

f A C

f A C

f

C 0 1 1 1 1 1 1 0

0 0 0 1

1 0 0 0

0 1 1 0

1 0 0 1

f=0 f=A f=1 f=A f=1 f=A f=0 f=Af=A f=A f=Af=A

Pentru variabila C = 0 C = 1 C = 1 C = 0 C = 0 C = 1 C = 1 C = 0 C = 0 C = 1 C = 0 C = 1 de control :

valoarea binar a 1 si pentru valoarea de fals valoarea binar a 0. Dar, n practic a, se poate ata sa pentru starea de adev ar a unei variabile acea valoare binar a pe care variabila o are n starea activ a (adic a starea care produce act iunea pentru care se justic a acea variabil a), care poate : e bitul 1, e bitul 0. Iar valoarea de fals variabila o are n starea de neactivare, care poate : e pentru valoarea binar a 1, e pentru valoarea binar a 0. In aceast a interpretare, variabila A c and este n stare activ a pentru valoarea bisi c and este n starea activ a nar a 1 (activ High) se noteaz a n felul urm ator A H pentru valoarea binar a 0 (activ Low) se noteaz a A L . La fel, si o ie sire OU T a unei port i poate considerat a n stare activ a (adev arat a) e c and are valoarea binar a 0 si se noteaz a OU T L, e c and are valoarea binar a 1 si se noteaz a OU T H . Cu aceste notat ii tabelele de adev ar pentru port ile logice se realizeaz a nu pentru valorile binare 1 si 0 ci pentru st arile de activare (adev arat) si neactivare (fals) ale intr arilor si, respectiv, pentru starea de activare (adev arat) si neactivare (fals) a ie sirii. Pe simbolurile grace ale port ilor pentru semnalele de intrare si de ie sire active n L se introduc cerculet e de negat ie. In practic a, dac a un semnal este activ n starea High, de a suxul H si se reprezint a numai A sau exemplu A H sau OU T H , nu se mai adaug

INTR1 INTR2_L INTR3_L INTR4_L INTR5 a)

OUT_L

INTR1 INTR2_L INTR3_L INTR4_L INTR5 b)

OUT_L

Figura 1.7 Reprezentarea mixat a a semnalelor (pentru valoarea binar a asignat a st arii de adev ar: a) pentru o poart a AND; b) pentru o poart a OR.


33

OU T nt eleg andu-se c a au valoarea de adev ar (starea activ a) n 1 logic iar valoarea de fals n 0 logic. In schimb, pentru semnalele active n starea Low se ment ine suxul L. Deci, poate s a apar a aceast a notare mixat a, adic a semnalele active n starea High nu mai au suxul H dar cele active n starea Low au suxul L. De exemplu, pentru poarta AND din Figura 1.7-a ie sirea este activ a (valoare de adev ar), OU T L = 0, se obt ine c and toate intr arile sunt activate (au valoare de adev ar), adic a: IN T R1 = 1, si IN T R5 = 1; iar pentru poarta IN T R2 L = 0, IN T R3 L = 0, IN T R4 L = 0 OR din Figura 1.7-b ie sirea nu este activ a (nu are valoare de adev ar, OU T L = 1) numai c and nici una din intr ari nu este activat a (este fals a), adic a: IN T R1 = 0, si IN T R5 = 0. IN T R2 L = 1, IN T R3 L = 1, IN T R4 L = 1 In practica circuitelor digitale pentru o variabil a V AR, care este activ a n starea n aceast a carte se va utiliza Low, se utilizeaz a dou a notat ii: V AR sau V AR L; at at notat ia de variabil a negat a, V AR, c at si notat ia de nivel Low, V AR L, ambele av and aceea si semnicat ie. Exemplul 1.6 S a se reprezinte tabelele de adev ar si simbolurile grace uniforme (vezi Tabelul 1.1) pentru toate variantele de activare ale variabilelor de intrare si ie sirii la o poart a AND cu dou a intr ari. Solut ie. Ie sirea unei port i AND cu dou a intr ari este activ a (are valoare de adev ar) numai c and sunt active (au valori de adev ar) ambele intr ari; deci o aplicat ie pe mult imeaA B AB A+B

Fals Fals Fals Fals Fals Adevarat Fals Adevarat Adevarat Fals Fals Adevarat Adevarat Adevarat Adevarat Adevarat A B A 0 0 1 1 A B A 0 0 1 1

&B 0 1 0 1 O 0 0 0 1

O

A B_L A 0 0 1 1

&B_L O 0 1 0 1 0 0 1 0

O

A_L B A_L 0 0 1 1

&B 0 1 0 1 O 0 1 0 0

O

A_L B_L

&

O

A_L B_L O 0 0 1 1 O_L A_L B_L 0 1 0 1 1 0 0 0 O_L

&B 0 1 0 1

O_L O_L 1 1 1 0

A B_L

&

O_L

A_L B A_L 0 0 1 1

&B 0 1 0 1

&

A B_L O_L 0 0 1 1 0 1 0 1 1 1 0 1

O_L 1 0 1 1

A_L B_L O_L 0 0 1 1 0 1 0 1 0 1 1 1

Figura 1.8 Variante de asignare a valorilor binare pentru semnalele active la o poart a AND

34

1.2. POARTA LOGICA

{adev ar,fals} cu valori tot n aceast a mult ime. Ata sa nd ec arei valori de adev ar (activare), pentru variabilele de intrare si pentru ie sire, e nivelul Low e nivelul High rezult a 8 variante pentru tabelul de adev ar, Figura 1.8. Realizat i variantele pentru tabelul de adev ar si pentru poarta OR.

In tehnic a, de foarte mult timp, este utilizat un element ce prezint a dou a st ari: contactul unui releu. Un contact nchis prin lamela sa stabile ste, ntre dou a puncte de circuit, un traseu de rezistent a electric a de valoare foarte mic a, teoretic zero, iar un contact deschis ntrerupe un circuit ntre dou a puncte, deci realizeaz a ntre cele dou a puncte o rezistent a innit a. Celor dou a st ari ale contactului ( nchis, deschis) li se pot asocia elementele mult imii binare {0, 1}. Rezult a c a pentru circuitele cu contacte, denumite ret ele de comutat ie, se poate aplica formalismul algebrei Booleene, B (2); apare astfel posibilitatea de a formaliza proiectarea si analiza ret elelor de comutat ie. Acest formalism a fost prima dat a folosit de Claude Shannon n 1938 care, a scos din arhiva matematicilor algebra conceput a de George Boole (1852) si a aplicat-o n acest scop. In Figura 1.9 este schit at a o structur a de circuit cu releu care, prin cele dou a contacte ale sale, unul normal deschis cel alalt normal nchis, realizeaz a traseul circuitelorx y x y f f = x+y d) x y z z x f

~

x x x a)

f1 f2

~ x

x x f=x b)

f

~ x

x x f= x c)

f

~

f

x~ x y

y y

z z z

f

f

~

x xx y z x y z x z

~

x y zx y z x y z x z

x y f = x. y e)

f

f

f

f =x y z +xy z + x z f)

f =(x + y +z )(x + y +z )( x+z) g)

Figura 1.9 Ret ele de comutat ie: a) structur a de circuit releu; b,c,d,e) ret ele de comutat ie pentru modelarea operatorilor de: identitate, negat ie, sum a logic a si produs logic; f,g) ret ele de comutat ie pentru modelarea unei forme de sume-de-produse si produse-de-sume.


35

de alimentare a dou a becuri notate cu f1 si f2 . Un contact normal deschis este n stare deschis a c and releul nu este comandat si trece n stare nchis a c and releul este comandat. Invers, un contact normal nchis este n starea nchis a c and releul nu este comandat si se deschide c and releul este comandat. In aceast a schit a , c and releul este necomandat tensiunea de alimentare a bobinei este 0, x = 0, arm atura nu este atras a, contactul normal nchis este nchis, cel normal deschis este deschis, iar becul f1 este stins si becul f2 este aprins. C and se comand a releul, tensiunea de alimentare are o anumit a valoare, pe care o putem nota cu 1, x = 1, contactul normal deschis se nchde, cel normal nchis se deschide deci becul f 1 se aprinde si f2 se stinge. Ata sa nd st arii becurilor valoarea logic a 1 (activ) c and este aprins si valoarea logic a 0 (inactiv) c and este stins rezult a c a aplicat ia {0, 1} {0, 1}, conform Figurii 1.1, este funct ia 1 1 f1 , adic a identitate pentru becul f1 , f1 = x si este funct ia f2 , adic a negat ie pentru becul f2 , f2 = x. Evident, contactul normal deschis prin care se realizeaz a funct ia de identitate se va nota cu variabila x, Figura 1.9-b, iar contactul normal nchis prin care se realizeaz a funct ia de negat ie se va nota cu variabila negat a, x, Figura 1.9-c. Rezult a, intuitiv, c a dou a contacte nseriate realizeaz a, pentru ret eaua de comutat ie respectiv a, modelarea produsului logic de dou a variabile, Figura 1.9-e, iar dou a contacte n paralel realizeaz a modelarea sumei logice a dou a variabile, Figura 1.9-d. OAUD

ID

+

A

G

S

D

A UD +

K

K UDG

K

S

D

A a) V CCRC

K b) V CCRC pMOS VO VO Vin Vin nMOS VO Vin VO

V DD

V DD

Vin

c)

d)

Figura 1.10 Elemente zice componente de baz a pentru structurarea port ilor logice: a,b) elemente componente pentru modelarea funct iei de identitate. c,d) elementele componente pentru modelarea funct iei de inversor n tehnologie bipolar a si n tehnologie CMOS.

36

1.2. POARTA LOGICA

ret ea de comutat ie serie-paralel, Figura 1.9-f, modeleaz a o funct ie disjunctiv a (sum a de produse, FD) iar o ret ea de comutat ie paralel-serie, Figura 1.9-g, modeleaz a o funct ie conjunctiv a (produse de sume, FC). 1 Elementele logice de baz a n structura unei port i sunt cele dou a funct ii f 1 (identi1 tate) si f2 (negat ie) cu care se pot realiza diferite organiz ari prin intermediul celor patru tipuri de conectare: serie, paralel, serie-paralel si paralel-serie. In circuitele poart a componentele zice care pot modela funct ia identitate pot dioda sau tranzistorul de trecere. O diod a polarizat a n sens direct este echivalent a unui contact nchis iar polarizat a n sens invers poate modela un contact deschis, Figura 1.10-a (s-a considerat caracteristica de diod a ideal a). La fel, un tranzistor de trecere (vezi Figura 1.51) poate echivalentul unui contact nchis/deschis dup a cum tranzistorul este comandat n conduct ie/blocare, Figura 1.10-b. Pentru funct ia de inversor exist a circuite simple n ecare tehnologie. Structura unui circuit inversor n tehnologie bipolar a este reprezentat a n Figura 1.10-c (vezi sect iunea 1.5.2) iar pentru inversorul CMOS n Figura 1.10-d (vezi sectiunea 1.4.1). Circuitul cu diode care produce la ie sire tensiunea de valoare minim a aplicat a la intrare, M IN (V1 , V2 , V3 ), Figura 1.11-a si circuitul cu diode care produce la ie sire tensiunea maxim a aplicat a la intrare, M AX (V1 , V2 , V3 ), Figura 1.11-b pot utilizate ca structuri de poart a AND sau OR n funct ie de convent ia de logic a folosit a.Vref =+5V

V1 V2 V3

D1 D2 D3

R VO

V1 V2 VO VL VL VL VL VH VL VH VL VL VH VH VH

V1 V2 0 0 0 1 1 1 0 1

VO 0 0 0 1

V1 V2 1 1 1 0 0 0 1 0

VO 1 1 1 0

V High = +5V V Low = 0V V O = Min(V 1,V 2,V 3)

a)

Logica pozitiva "1" VH "0" VL Poarta AND V1 V2 VO VL VL VL VL VH VH VH VL VH VH VH VH V1 V2 0 0 0 1 1 1 0 1 VO 0 1 1 1

Logica negativa "0" VH "1" VL Poarta OR V1 V2 1 1 1 0 0 0 1 0 VO 1 0 0 0

V1 V2 V3

D1 D2 D3

VO

RVref = 0V

b)

V High = +5V V Low = 0V V O = Max(V 1,V 2,V 3)

Logica pozitiva "1" VH "0" VL Poarta OR

Logica negativa "0" VH "1" VL Poarta AND

Figura 1.11 Echivalarea circuitelor MIN (a) si MAX(b) ca port i logice AND si OR n funct ie de convent ia de logic a pozitiv a sau negativ a


37

Prin convent ia de logic a pozitiv a ntr-un circuit nivelului de tensiune ridicat VH (High), n general tensiunea de alimentare V H = VCC , VH = VDD , i se atribuie ,, valoarea logic a 1 iar nivelului de tensiune cobor at VL (Low), n general tensiunea ,, de mas a VL = VSS = 0V , i se atribuie valoarea logic a 0 . Invers, prin convent ia de ,, ,, logic a negativ a se fac urm atoarele atribuiri VH 0 , VL 1 . Exist a circuite logice care sunt alimentate cu tensiuni negative (V EE ) fat a de mas a, circuitele de tip ECLEmitter Coupled Logic, si la acestea se p astreaz a atribuirile din convent iile de logic a pozitiv a sau negativ a; diferent a fat a de circuitele care se alimenteaz a la tensiune pozitiv a este faptul c a VH = 0V (tensiunea masei) si VL = VEE , Figura 1.13. Circuitul MIN, Figura 1.11-a, va genera pentru ie sire V O = M IN (V1 , V2 , V3 ) deoarece va conduce numai dioda care are aplicat pe catod tensiunea cu valoarea cea mai cobor at a, celelalte diode, cu catozii mai pozitivi, vor blocate. Consider and circuitul MIN realizat numai cu dou a diode D1 si D2 , la catozii c arora se aplic a numai tensiunile de valori VH sau VL , se poate construi tabelul pentru tensiunea de ie sire VO . Aplic and acestui tabel convent ia de logic a pozitiv a rezult a c a circuitul MIN are o funct ionare de poart a AND, iar n convent ia de logic a negativ a are o funct ionare de poart a OR. Circuitul MAX, Figura 1.11-b, va genera pentru ie sire tensiunea maxim a aplicat a pe intrare VO = M AX (V1 , V2 , V3 ) deoarece va conduce doar dioda care are aplicat pe anod tensiunea cea mai ridicat a, celelalte diode, cu potent ial mai cobor at pe anod, vor blocate. Aplic and tabelului, care arat a corespondent a dintre tensiunea de ie sire VO si tensiunile de intrare V1 , V2 (sunt considerate doar dou a intr ari), convent ia de logic a pozitiv a rezult a c a circuitul MAX are funct ionare de poart a OR iar n convent ia de logic a negativ a are o funct ionare de poart a AND. Teorema 1.1 Duala unei funct ii de variabile negate este egal a cu negata funct iei de variabile nenegate. f (x0 , x1 , . . . , xn1 ) = f D (x0 , x1 , . . . , xn1 ) (1.17)

Relat ia 1.17 se poate verica pe tabelele de adev ar din Figura 1.11-a si 1.11-b deoarece o convent ie de logic a se obt ine din cealalt a convent ie prin negarea variabilelor si V1 + V2 = iar operatorii AND si OR sunt unul dualul celuilalt: V 1 V2 = V1 + V2 V1 V2 . De fapt, relat ia 1.17 este o generalizare a teoremei lui DeMorgan. Exemplul 1.7 S a se conceap a o organizare de circuit, folosind circuitele MIN si MAX, care s a produc a tot i maxtermii si mintermii de dou a variabile. Se poate extinde aceasta pentru generarea de sume de produse de dou a variabile? si de patru Solut ie. Mintermii de dou a variabile x1 x0 , x1 x0 , x1 x0 , x1 x0 pot produ circuite MIN, ca n Figura 1.11-a, dar cu patru diode pe catozii c arora se aplic a variabilele x1 , x1 , x0 , x0 . Cele patru circuite MIN se pun n paralel ca n Figura 1.12-a realiz and o i matrice AND. Maxtermii de dou a variabile x1 + x0 , x1 + x0 , x1 + x0 , x1 + x0 pot generat de patru circuite MAX ca n Figura 1.11-b, cu variabilele de intrare x1 , x1 , x0 , x0 , iar cele patru circuite sunt conectate n paralel realiz and matricea OR din Figura 1.12-b. (Atent ie care catozi sunt conectat i la linii pentru circuitele MIN si la coloane pentru circuitul MAX). Evident c a se pot obt ine sume de produse de dou a variabile dac a cele patru ie siri de la matricea AND sunt conectate, ecare, la c ate o intrare la matricea OR realiz and o congurat ie

38

1.2. POARTA LOGICA

de circuit pe dou a niveluri logice, AND-OR. C and se realizeaz a aceast a nseriere de niveluri logice apar dou a probleme: prima, este c aderea de tensiune pe jonct iunile n conduct ie, ceea ce duce ca semnalul de ie sire n stare logic a 1 s a e sub valoarea VH , iar a doua, este lipsa unei decupl ari (izolare) ntre intrare si ie sire. Pentru valorile urm atoare VH = 5V , VL = 0V , VDon = 0, 7V , R1 = 1K , R2 = 10K rezult a tensiunea de ie sire n starea H egal a cu VH (VH VDon ) R1 = 3, 9V VH = 5V (R1 + R2 )

Structura obt inut a prin nserierea unei matrice AND cu o matrice OR poate suport pentru implementarea oric arei funct ii sum a de produse dac a matricile respective sunt programabile, adic a pe nivelul AND se poate genera oricare termen produs iar pe nivelul OR se poate selecta oricare produs n obt inerea unei sume (vezi sectiunea 2.4.7). Fizic, generarea acestor termeni cu structura similar a celei din Figura 1.12 se face, ntr-un nod al celor dou a matrice, prin neconectarea sau conectarea diodei la linie respectiv la coloan a, ceea ce se reduce la arderea sau ment inerea unui fuzibil nseriat cu dioda dintr-un nod. Prin fabricat ie, realiz and n ecare nod o diod a nseriat a cu un fuzibil, i se ofer a utilizatorului ca ulterior s a aib a posibilitatea de a programa ecare nod din matricea AND si matricea OR n funct ie de expresia particular a a funct iei exprimat a ca sum a de produse. In procesul de programare, cu ajutorul unui aparat programator, utilizatorul poate selecta oricare nod din cele dou a matrice si prin aplicarea unei tensiuni de valoare 10 30V s a ard a fuzibilul. Dispozitivele programabile de c atre utilizator sunt foarte eciente si exibile n etapa de dezvoltare a unui produs c and se ncearc a diferite variante p an a la obt inerea variantei nale. Produc atorii de dispozitive programabile produc aceste dispozitive cu toate nodurile matricei nzestrate e cu fuzibil e cu un antifuzibil. La dispozitivele cu fuzibil, prin programare, rezistent a conexiunii dintr-un nod este modicat a de la valoarea zero la valoara innit a (arderea fuzibilului). Un fuzibil din tungsten-titan sau nichel-crom cu l a timea de 0.15m necesit a pentru ardere un curent de 10 60mA timp de 1 10ms (Texas Instruments), iar un fuzibil din polisiliciu cu+V (+5V) x +y x x y y xy xy xy xy pentru realizarea AND OR R2 R2 Matricea OR b) R2 R2 x +y x +y x +y

R1

R1

R1

R1

x x y y

Matricea AND a)

Figura 1.12 Organizarea unei matrice programabile n logica pozitiv a: a)pentru termeni produs; b)pentru termeni sum a.


39

,, l a timea de 25m se poate arde cu un curent de 20 80mA timp de 15s (AMD). Dar, exist a pericolul ca n timp, datorit a efectelor termice din circuitul integrat, unele fuzibile arse s a duc a la refacerea conexiunii. La dispozitivele cu antifuzibil, prin programare, rezistent a conexiunii dintr-un nod este modicat a de la o valoare init ial a foarte mare de ordinul 100M la o valoare sub 1K . Trasei de antifuzibil realizat a e dintr-un dielectric (de exemplu ONO, Oxigen-Nitrura-Oxigen), e din siliciu amorf, n procesul de programare, i se aplic a un curent de ordinul zeci de mA cu durata sub 1s, prin aceasta produc and modicarea rezistent ei. Conexiunile pe baz a de antifuzibil, spre deosebire de cele pe baz a de fuzibil, nu se pot reface nt ampl ator (adic a s a revin a la rezistent e de 100M ). Dispozitivele programabile at at cele cu fuzibil c at si cele cu antifuzi

Electronica-Digitala-de-Gheorghe-TOACSE-613-Pag.pdf

Documents

Transcript of Electronica-Digitala-de-Gheorghe-TOACSE-613-Pag.pdf