ZElectronica Digitala de Gheorghe TOACSE 613 Pag (CEL)

8/20/2019 ZElectronica Digitala de Gheorghe TOACSE 613 Pag (CEL)

1/612

Electronică digitală

- Curs -

Gheorghe TOACŞE 1

April 3, 2005

1TRANSILVANIA University Braşov, Electronics and ComputersEmail: [email protected]


2/612


3/612

Cuprins

1 PORŢI LOGICE 71.1 SUPORTUL LOGIC PENTRU SISTEMELE DIGITALE . . . . . . . 7

1.1.1 Axiomele şi teoremele algebrei Booleene . . . . . . . . . . . . . 71.1.2 Algebre polivalente . . . . . . . . . . . . . . . . . . . . . . . . . 111.1.3 Funcţii Booleene . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.1.4 Forme canonice . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.1.5 Forme disjunctive şi conjunctive . . . . . . . . . . . . . . . . . 261.2 POARTA LOGICĂ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311.3 PARAMETRII PORŢILOR LOGICE . . . . . . . . . . . . . . . . . . 391.4 PORŢI LOGICE ÎN TEHNOLOGIA BIPOLARĂ . . . . . . . . . . . 52

1.4.1 Inversorul bipolar . . . . . . . . . . . . . . . . . . . . . . . . . . 521.4.2 Porţi logice TTL . . . . . . . . . . . . . . . . . . . . . . . . . . 561.4.3 Porţi pentru magistrale . . . . . . . . . . . . . . . . . . . . . . 59

1.5 PORŢI ÎN TEHNOLOGIA CMOS . . . . . . . . . . . . . . . . . . . . 661.5.1 Tranzistorul MOSFET . . . . . . . . . . . . . . . . . . . . . . . 66

1.5.1.1 Tehnologia de fabricaţie a tranzistorului MOS . . . . 661.5.1.2 Ecuaţiile tranzistorului MOS . . . . . . . . . . . . . . 72

1.5.2 Inversorul CMOS . . . . . . . . . . . . . . . . . . . . . . . . . . 79

1.5.2.1 Caracteristica statică de transfer V O = f (V I ) . . . . . 801.5.2.2 Proiectarea inversorului CMOS . . . . . . . . . . . . . 831.5.2.3 Tehnologia de fabricaţie a inversorului CMOS . . . . 871.5.2.4 Regimul dinamic al inversorului . . . . . . . . . . . . 90

1.5.3 Familia de porţi logice CMOS . . . . . . . . . . . . . . . . . . . 941.5.3.1 Poarta NOR şi NAND cu două intrări . . . . . . . . . 951.5.3.2 Porţi logice complexe . . . . . . . . . . . . . . . . . . 981.5.3.3 Seriile de porţi ale familiei CMOS . . . . . . . . . . . 1051.5.3.4 Interfaţarea TTL-CMOS şi CMOS-TTL . . . . . . . . 107

1.5.4 Poarta de transmisie CMOS . . . . . . . . . . . . . . . . . . . . 1111.5.5 Circuite logice dinamice . . . . . . . . . . . . . . . . . . . . . . 1151.5.6 Metoda efortului logic . . . . . . . . . . . . . . . . . . . . . . . 123

1.5.6.1 Determinarea ̂ıntârzierii pe o poartă logică . . . . . . 1241.5.6.2 Calculul ̂ ıntârzierii ı̂n reţelele de porţi logice . . . . . 1311.5.6.3 Alegerea numărului optim de niveluri pe un traseu . . 136

1.6 REJECŢIA ZGOMOTELOR . . . . . . . . . . . . . . . . . . . . . . . 1421.6.1 Rejecţia zgomotelor externe . . . . . . . . . . . . . . . . . . . . 148

3


4/612

4 CUPRINS

1.6.2 Rejecţia zgomotelor interne . . . . . . . . . . . . . . . . . . . . 1501.6.2.1 Zgomotul de mas̆a. . . . . . . . . . . . . . . . . . . . . 1501.6.2.2 Zgomotul datorită neadaptării liniilor. . . . . . . . . . 1511.6.2.3 Zgomotul datorat cuplajului electromagnetic (diafonia) 1581.6.2.4 Zgomotul datorită curenţilor de alimentare . . . . . . 160

2 CIRCUITE LOGICE COMBINAŢIONALE 1732.1 CIRCUITUL LOGIC COMBINAŢIONAL . . . . . . . . . . . . . . . . 1732.2 REPREZENTAREA CLC . . . . . . . . . . . . . . . . . . . . . . . . . 176

2.2.1 Tabelul de adevăr . . . . . . . . . . . . . . . . . . . . . . . . . 1772.2.2 Reprezentarea analitică . . . . . . . . . . . . . . . . . . . . . . 1822.2.3 Diagrama Veitch - Karnaugh . . . . . . . . . . . . . . . . . . . 186

2.2.3.1 Minimizarea funcţiilor incomplet definite . . . . . . . 1912.2.3.2 Minimizare pe diagrame V-K cu variabile reziduu . . 1932.2.3.3 Minimizarea prin diagrame V-K a circuitelor cu ieşiri

multiple . . . . . . . . . . . . . . . . . . . . . . . . . . 1962.2.4 Diagrama de decizie binară, BDD . . . . . . . . . . . . . . . . 199

2.2.5 Modalit̆aţi neformale de reprezentare . . . . . . . . . . . . . . . 2032.3 REALIZAREA CIRCUITELOR COMBINAŢIONALE . . . . . . . . . 2092.3.1 Hazardul static . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

2.4 CLC PENTRU FUNCŢII LOGICE . . . . . . . . . . . . . . . . . . . 2182.4.1 Codificatorul . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2182.4.2 Codificatorul prioritar, CDCP . . . . . . . . . . . . . . . . . . . 2202.4.3 Decodificatorul, DCD . . . . . . . . . . . . . . . . . . . . . . . 224

2.4.3.1 Convertorul de cod . . . . . . . . . . . . . . . . . . . 2322.4.4 Multiplexorul . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

2.4.4.1 Aplicaţii cu circuite multiplexoare . . . . . . . . . . . 2372.4.5 Demultiplexorul . . . . . . . . . . . . . . . . . . . . . . . . . . 2472.4.6 Memoria numai cu citire, ROM . . . . . . . . . . . . . . . . . . 250

2.4.6.1 Realizarea circuitelor şi modulelor ROM . . . . . . . 255

2.4.6.2 Module de memorie ROM . . . . . . . . . . . . . . . . 2612.4.7 Dispozitivele logice programabile, PLD . . . . . . . . . . . . . . 263

2.4.7.1 Matricea Logică Programabilă, PLA . . . . . . . . . . 2632.4.7.2 Matricea logică programabilă cu nivel OR fix, PAL . 2692.4.7.3 Circuitul de tip GAL . . . . . . . . . . . . . . . . . . 272

2.5 CLC PENTRU FUNCŢII NUMERICE . . . . . . . . . . . . . . . . . 2732.5.1 Comparatorul . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2732.5.2 Sumatorul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275

2.5.2.1 Sumatorul cu Transport Progresiv, STP . . . . . . . . 2752.5.2.2 Sumatoare de performanţă ridicată . . . . . . . . . . 280

2.5.3 Multiplicatorul . . . . . . . . . . . . . . . . . . . . . . . . . . . 2872.5.3.1 Multiplicatorul matriceal . . . . . . . . . . . . . . . . 2882.5.3.2 Multiplicatorul tip arbore Wallace . . . . . . . . . . . 2912.5.3.3 Multiplicatorul tabelar . . . . . . . . . . . . . . . . . 293

2.5.4 Circuite de deplasare . . . . . . . . . . . . . . . . . . . . . . . . 2952.5.5 Unitatea Aritmetică şi Logică, ALU . . . . . . . . . . . . . . . 301

2.5.5.1 Calea de date . . . . . . . . . . . . . . . . . . . . . . . 301


5/612

CUPRINS 5

2.5.5.2 Organizarea şi implementarea unei unit̆aţi aritmeticăşi logică . . . . . . . . . . . . . . . . . . . . . . . . . . 305

2.5.5.3 Structurarea unei ALU elementare . . . . . . . . . . . 3062.6 PROBLEME . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311

3 CIRCUITE LOGICE SECVENŢIALE, CLS 3213.1 CIRCUITE LOGICE SECVENŢIALE

ASINCRONE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3213.2 CIRCUITE LOGICE SECVENŢIALE SINCRONE . . . . . . . . . . . 330

3.2.1 Sincronizarea semnalelor asincrone . . . . . . . . . . . . . . . . 3303.2.2 Automate finite: structură, definiţii, clasificări . . . . . . . . . 3323.2.3 Modalit̆aţi de reprezentare ale automatelor . . . . . . . . . . . 340

3.2.3.1 Graful de tranziţie al stărilor . . . . . . . . . . . . . . 3413.2.3.2 Tabelul de tranziţie al stărilor . . . . . . . . . . . . . 3443.2.3.3 Diagrame de variaţie ı̂n timp ale semnalelor . . . . . . 3453.2.3.4 Organigrama ASM . . . . . . . . . . . . . . . . . . . . 3453.2.3.5 Limbaje de transfer ̂ıntre registre, RTL . . . . . . . . 354

3.2.4 Reducerea numărului de stări . . . . . . . . . . . . . . . . . . . 3573.2.5 Asignarea stărilor . . . . . . . . . . . . . . . . . . . . . . . . . . 3613.2.5.1 Intrări şi iȩsiri asincrone . . . . . . . . . . . . . . . . . 372

3.2.6 Proiectarea automatelor sincrone . . . . . . . . . . . . . . . . . 3763.3 CIRCUITE BASCULANTE . . . . . . . . . . . . . . . . . . . . . . . . 382

3.3.1 Circuitul latch . . . . . . . . . . . . . . . . . . . . . . . . . . . 3833.3.1.1 Latch-ul SR . . . . . . . . . . . . . . . . . . . . . . . 3863.3.1.2 Latch-ul D . . . . . . . . . . . . . . . . . . . . . . . . 391

3.3.2 Circuite Basculante Bistabile (Triggere) . . . . . . . . . . . . . 3953.3.2.1 Principiul master-slave . . . . . . . . . . . . . . . . . 3953.3.2.2 Bistabilul D . . . . . . . . . . . . . . . . . . . . . . . 3983.3.2.3 Bistabilul JK . . . . . . . . . . . . . . . . . . . . . . . 4023.3.2.4 Bistabilul T . . . . . . . . . . . . . . . . . . . . . . . 405

3.3.3 Aplicaţii la automate . . . . . . . . . . . . . . . . . . . . . . . . 4093.3.4 Circuitul basculant bistabil asimetric

(Triggerul Schmitt) . . . . . . . . . . . . . . . . . . . . . . . . . 4183.3.5 Circuitul basculant monostabil . . . . . . . . . . . . . . . . . . 4233.3.6 Circuitul basculant astabil . . . . . . . . . . . . . . . . . . . . . 425

3.4 CIRCUITE NUMĂRĂTOR . . . . . . . . . . . . . . . . . . . . . . . . 4283.4.1 Numărătoare asincrone . . . . . . . . . . . . . . . . . . . . . . 4313.4.2 Numărătoare sincrone . . . . . . . . . . . . . . . . . . . . . . . 435

3.4.2.1 Numărătoare presetabile . . . . . . . . . . . . . . . . 4393.4.2.2 Numărătoare ̂ın cod arbitrar . . . . . . . . . . . . . . 450

3.5 CIRCUITE REGISTRU . . . . . . . . . . . . . . . . . . . . . . . . . . 4523.5.1 Registru paralel . . . . . . . . . . . . . . . . . . . . . . . . . . . 4523.5.2 Circuitul acumulator . . . . . . . . . . . . . . . . . . . . . . . . 4553.5.3 Structura pipeline . . . . . . . . . . . . . . . . . . . . . . . . . 4583.5.4 Registrul de deplasare . . . . . . . . . . . . . . . . . . . . . . . 4603.5.5 Registrul serie-paralel . . . . . . . . . . . . . . . . . . . . . . . 4683.5.6 Circuite liniare cu registre de deplasare . . . . . . . . . . . . . 473


6/612

6 CUPRINS

3.5.7 Distribuţia şi aplicarea semnalului de ceas . . . . . . . . . . . . 4843.6 MEMORIA CU ACCES ALEATORIU . . . . . . . . . . . . . . . . . . 495

3.6.1 Memoria RAM static̆a . . . . . . . . . . . . . . . . . . . . . . . 4993.6.2 Memoria RAM dinamică . . . . . . . . . . . . . . . . . . . . . . 505

3.6.2.1 Memoria DRAM sincronă, SDRAM . . . . . . . . . . 5133.6.3 Circuite actuale pentru memoriile de date . . . . . . . . . . . . 5263.6.4 Memoria adresabil̆a prin conţinut, CAM . . . . . . . . . . . . . 533

4 SUPORTUL CIRCUISTIC PENTRU APLICAŢI I 5514.1 CONEXIUNI PROGRAMABILE . . . . . . . . . . . . . . . . . . . . . 5514.2 PROIECTAREA DE TIP FULL-CUSTOM . . . . . . . . . . . . . . . 5554.3 PROIECTAREA CU ARII DE PORŢI LOGICE . . . . . . . . . . . . 5564.4 PROIECTAREA CU CELULE STANDARD . . . . . . . . . . . . . . 5574.5 PROIECTAREA CU CPLD . . . . . . . . . . . . . . . . . . . . . . . . 5624.6 PROIECTAREA CU FPGA . . . . . . . . . . . . . . . . . . . . . . . . 570

4.6.1 Blocul Logic Configurabil . . . . . . . . . . . . . . . . . . . . . 5724.6.2 Resursele de interconectare . . . . . . . . . . . . . . . . . . . . 578

4.7 PROIECTAREA PENTRU TESTABILITATE . . . . . . . . . . . . . 5944.8 COMBINAŢIONAL SAU SECVENŢIAL? . . . . . . . . . . . . . . . . 5994.9 COMPARAŢIE ÎNTRE DIFERITELE

MODALITĂŢI DE PROGRAMARE . . . . . . . . . . . . . . . . . . . 608

5 Bibliografie 611


7/612

Capitolul 1

PORŢI LOGICE

1.1 SUPORTUL LOGIC PENTRU SISTEMELE

DIGITALE

Practica sistemelor digitale simple se poate face pe baz ă de raţionamente logiceelementare. Dar, deoarece sistemele digitale au devenit foarte complexe, şi aceastătendinţă continuă, pentru analiza, proiectarea/sinteza şi realizarea acestora este nece-sar un suport formal abstract şi un suport circuistic. Suportul formal abstract seconstruieşte, prin extensie, pe baza algebrei logice bivalente iar suportul circuisticse construieşte pornind de la poarta logică. Abordarea ı̂ntrepătrunsă a acestor douăcomponente constituie subiectul acestui capitol.

1.1.1 Axiomele şi teoremele algebrei Booleene

În logica aristoteliană, care trebuie ı̂nţeleasă ca o ştiinţă a demonstraţiei, alcărui obiect ı̂l constituie stabilirea condiţiilor corectitudinii gândirii, se operează pebază de raţionament cu propoziţii (logica propoziţiilor), care pot fi: fie adevărate,fie false. De exemplu, dacă presupunem că pentru statura unei persoane sunt admisenumai două atribute - ı̂nalt şi scund - iar pentru vreme numai două atribute - receşi cald - atunci sunt naturale următoarele patru propoziţii simple: vremea este cald˘ a ,vremea este rece , Radu este ı̂nalt şi Radu este scund . Considerând că din fiecarepereche de atribute unul este adevărat şi celălalt fals rezultă că propoziţiile formatecu aceste atribute pot fi fie adevărate fie false; o propoziţie nu poate fi simultan şifalsă şi adevărată (̂ın cazul nostru considerăm că prima şi a treia propoziţie simplăsunt adevărate, iar celelalte două sunt false). Dar, cu aceste propoziţii simple pot firealizate propoziţii compuse, de exemplu: vremea este cald˘ a şi Radu este ı̂nalt , vre-mea este rece sau Radu este scund . Propoziţiile compuse pot fi, la fel, adevărate saufalse in funcţie de valoarea de adevăr/fals a propoziţiilor componente şi de modul de

compunere a acestora ı̂n propoziţia compusă. Modul de compunere, ı̂n acest caz core-spunde conectorului AND/ŞI pentru prima propoziţie compusă, respectiv conectoru-lui OR/SAU pentru a doua propoziţie compusă. Dacă prima propoziţie are valoareade adevăr, când vremea este caldă şi Radu este ı̂nalt, evident că a doua propoziţiecompusă are valoare de fals. Dar dacă prima propoziţie compusă o transformăm ı̂n nu

7


8/612

8 1.1. SUPORTUL LOGIC PENTRU SISTEMELE DIGITALE

este adev˘ arat: c˘ a Radu este ı̂nalt şi vremea este cald˘ a atunci această nouă propoziţieare o valoare de fals ca şi a doua propoziţie compusă? Evident că da. Dar dacămai introducem şi o a treia pereche de propoziţii simple z˘ apada este alb˘ a , z˘ apada este neagr˘ a şi formăm propoziţii compuse, după diferite moduri de compunere, din câteuna din fiecare pereche anterioară atunci mai putem afirma cu uşurinţă care dintrepropoziţiile compuse sunt echivalente? Destul de greu. În general, la nivelul normalde dotare intelectuală, un individ cu greu poate realiza un raţ ionament corect, fărăun suport mecanic, când operează simultan cu mai mult de trei variabile. Pentrua ı̂nvinge această incapacitate avem nevoie de un instrument care să “mecanizeze

,,

raţionamentele stufoase.Matematicianul englez George Boole (1815-1854) a elaborat o algebră (algebra

Booleană) ale cărei axiome şi teoreme pot fi utilizate pentru a transforma (transfera)logica aristoteliană a propoziţiilor din domeniul raţionamentului oral ı̂ntr-un limbajformal, operant cu simboluri (logica formală). Această logică formală poate fi aplicatăca un instrument operant şi pentru descrierea conectării, ı̂n sisteme, a elementelorfizice (mecanice, electrice, hidropneumatice) care prezintă in funcţionarea lor doardouă stări distincte.

Algebra Booleană (algebră logică binară, algebră logică bivalentă) operează peo mulţime binară B:

B = {x|x = 0, 1}0 = elementul nul (1.1)

1 = elementul unitate (universal).

Tabelul 1.1 Operatorii booleeni; definiţie şi simboluri grafice

TABELUL DEADEVAR

Reprezentarea grafica conform

varianta noua

logica(negatia)

Complementarea

Conjunctia,

Produsul logic

Disjunctia,

Suma logica

01 0

1

’ 1

+

1

standardului IEC/ANSI−91−1984varianta veche

11

0

000

10

1

0

01

1

000

10

1

0

01

1

0

10

1

0

0

1

1

11

0

yx

yx

y

x .x y

y

x x+y

&

x .x y

y

> 1 x+y

x

y

x xx’

x y∨x y+

x∪y

∧x yx y.

x∩y

OPERATORUL LOGIC SIMBOL

ANSI (American National Standard Institute)

0

1

NOT / NON

AND / SI

OR / SAU


9/612

CAPITOLUL 1. PORŢI LOGICE 9

În această carte elementele mulţimii binare reprezint̆a valorile logice de adevăr sau defals sau cifrele sistemului de numeraţie ı̂n baza doi - bit ( binary digit - cifră binară).

Există concepute şi algebre definite pe mulţimi care conţin mai mult de douăelemente, algebre polivalente – logică polivalentă, logică cu n-valori; cazuri ı̂ncare mulţimea de definiţie este formată din n numere ı̂ntregi. O generalizare pentrulogica cu n-valori este logica fuzzy, ı̂nsă ı̂n logica fuzzy variabilele iau valori ı̂n modcontinuu pe intervalul [0,1]. [Matei 93], [Cocan 01].

Definiţia 1.1 Fie M o mulţime nevidă. O aplicaţie f definită pe M cu valoriı̂n M

f : M → M se numeşte lege de compoziţie internă.

Algebra Booleană defineşte pe mulţimea B următoarele trei legi de compoziţieinternă (la care, obişnuit, ne vom referi şi 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 logică (OR/SAU).

Tabelul 1.2 Axiomele şi teoremele algebrei Booleene

Denumirea Forma cu operatorul

produs (·)Forma cu operatorul

sumă (+)

Axioma 1: Mulţimea B = {0, 1}este ı̂nchisă ı̂n raportcu operatorii + şi ·(Inchiderea)

x ∈ B, y ∈ B ⇒ x · y ∈ B x ∈ B, y ∈ B ⇒ x + y ∈ B

Axioma 2: Asociativitatea x

·(y

·z ) = (x

·y)

·z x + (y + z ) = (x + y) + z

Axioma 3: Comutativitatea x · y = y · x x + y = y + xAxioma 4: Existenţa

elementului neutru x · 1 = 1 · x = x x + 0 = 0 + x = x

Axioma 5: Distributivitatea x · (y + z ) = x · y + x · z x + y · z = (x + y) · (x + z )Axioma 6: Existenţa

complementului x · x = 0 x + x = 1

Teorema 1: Idempotenţa sautautologia

x · x = x x + x = xTeorema 2: Legea lui 0 şi a lui 1 x · 0 = 0 x + 1 = 1Teorema 3: Dubla negaţie

(Involuţia) x = x x = x

Teorema 4: Absorbţia

Absorbţia inversă

x · (x + y) = xx

·(x + y) = x

·y

x · (x + y) = x · y

x + x · y = xx + x

·y = x + y

x + x · y = x + yTeorema 5: Teorema lui De

Morgan x · y = x + y x + y = x · y


10/612


În Tabelul 1.1 sunt prezentate pentru fiecare lege de compoziţ ie booleană aplicaţiadefinită sub forma unui tabel de adevăr precum şi simbolurile grafice de reprezentare.Deşi există recomandarea pentru utilizarea noilor reprezentări grafice s-a ı̂ncetăţenitşi continuă folosirea vechilor reprezentări grafice (americane).

Definiţia 1.2 O expresie Booleană f (x1, x2, . . . , xn, 0, 1, ·, +), compusă prinintermediul celor trei operatori AND, OR, NOT prezintă o expresie duală f D carese obţine din expresia lui f prin substituţiile următoare: AND → OR, OR → AND,0 → 1, 1 → 0

f D(x1, x2, . . . , xn, 0, 1, ·, +) = f (x1, x2, . . . , xn, 1, 0, +, ·) (1.2)

Dacă o axiomă, teoremă sau expresie booleană este adevărată atunci şi forma sa

duală este adevărată.Axiomele şi teoremele algebrei Booleene sunt prezentate, sistematic, ı̂n Tabelul

1.2 . Pentru fiecare dintre acestea sunt expuse cele două forme, cea ı̂n formă produsşi cea ı̂n formă sumă, fiecare fiind duala celeilalte. În acest tabel sunt şase axiome şi

cinci teoreme.Corectitudinea unei expresii booleene se poate verifica analitic (prin utilizarea

axiomelor şi teoremelor din Tabelul 1.2 ) sau prin calcularea valorilor logice ale expre-siilor din cele două părţi ale semnului egalităţii. Folosind aceste două modalităţi ı̂ncontinuare se va verifica corectitudinea expresiei teoremei absorbţ iei (Teorema 4).

0

0

1

1

0

0

1

1

0

0

0

1

0

1

1

1

x+ x= y· x

Teorema 1

Axioma 4

Teorema 2

Teorema 2

Axioma 4

Axioma 5

Axioma 4Axioma 5

Axioma 5

Axioma 4

( )· +

0

1

0

1

0

0

1

1

x y x

· · x x x y

·

+1· · x x y

( )· x y

x y x +

+

1· x

1+

x

+ x ·(

x)

x y

· x

x = y

+ · x

+ y1 x ·

( )· x y+1

1· x

x

=

=

y x x· y x + y x y ( )· + y+ · x x x

Continuăm demonstraţia analitică pentru variantele teoremei de absorbţie inversă(Teorema 4), dar acum nu se mai indică succesiune numărul axiomelor şi teoremeloraplicate.


11/612


x + y = x + y · 1 = x + y(x + x) = x · 1 + y · x + y · x = x · (1 + y) + y · x = x + x · yx + 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 Booleană a devenit un suport formal pentru sistemele fizice care utilizeazăelemente cu două stări distincte. Algebra Booleană, care am introdus-o anterior şi lacare ne vom referi prin B(2), este cel mai simplu membru al unei familii de algebreBooleene B(q ) bazate pe noţiunea abstractă de latice (o latice este o mulţ ime nevidăL ı̂nzestrată cu două operaţii “∨,,, “∧,, care satisfac proprietăţile de idempotenţă, co-mutativitate, asociativitate şi absorbţie). Astfel, se poate construi o algebră BooleanăB(q ) pentru orice număr q care este o putere a lui doi, q = 2k. Deci există familiade algebre Booleene B (2), B (4), B (8),. . ., B (2k). Pentru k = 1, q = 21 rezultă B (2)definită pe {0, 1} care este chiar algebra Booleană prezentată anterior. Pentru k = 2,q = 22 = 4 rezultă B(4) definită pe mulţimea {0,a,b, 1} cu următoarele tabele dedefiniţie ale operatorilor: conjuncţie, disjuncţie şi deplasarea ciclică.

· 0 a b 1 + 0 a b 1 x x

0 0 0 0 0 0 0 a b 1 0 aa 0 a 0 a a a a 1 1 a bb 0 0 b b b b 1 b 1 b 11 0 a b 1 1 1 1 1 1 1 0

Conjuncţia Disjuncţia Deplasarea

ciclică

Dintre toate algebrele B(q ) numai B(2) este funcţional completă, deci poatefi suport pentru implementarea sistemelor logice. O algebră este funcţional com-pletă dacă pentru o funcţie de un număr de variabile se generează doar o singurăreprezentare/expresie.

Dezvoltarea tehnologiei electronice a dus la realizarea unor elemente care pot re-aliza mai multe stări distincte. Era normal, ca pentru elementele cu mai multe stări,să se găsească un suport formal cu valori multiple adică algebre polivalente, sau q -valente, mulţimea de definiţie pentru aceste algebre fiind formată dintr-un număr de q elemente distincte. Construcţia algebrelor polivalente a urmat două căi. Prima, a fosto generalizare a operatorilor/(conectivi) booleeni AND, OR şi NOT spre oper-atori corespunzători – conjuncţia, disjuncţia şi deplasarea ciclică – obţinându-sealgebrele Postiene (introduse de E.L. Post, 1921). A doua cale, dezvoltată de B.A.Bernstein (1928), a fost o abordare prin algebra claselor de resturi, operatoriifiind adunarea şi ı̂nmulţirea modulo q .

O algebră Postiană q -valentă, P (q ), este definită pe mulţimea {0, 1, 2, . . . ,q − 1}, adică pe intervalul de numere ı̂ntregi [0, q − 1], iar operatorii sunt definiţi ı̂nfelul următor:

- conjuncţia: x · y = min(x, y);- disjuncţia: x + y = max(x, y);

- deplasarea ciclică: x = x ⊕ 1 modulo q .


12/612


Pentru algebrele Postiene P (2) şi P (4) rezultă următoarele tabele de adevăr alecelor trei operatori:

- P(2)

· 0 1 + 0 1 x x x0 0 0 0 0 1 0 1 01 0 1 1 1 1 1 0 1Conjuncţia Disjuncţia Deplasarea

binară binară ciclicăbinară

- P(4)

· 0 1 2 3 + 0 1 2 3 x x x x x0 0 0 0 0 0 0 1 2 3 0 1 2 3 01 0 1 1 1 1 1 1 2 3 1 2 3 0 12 0 1 2 2 2 2 2 2 3 2 3 0 1 23 0 1 2 3 3 3 3 3 3 3 0 1 2 3

Conjuncţia Disjuncţia Deplasarea ciclică

cuaternară cuaternară cuaternară

Rezultă o identitate ı̂ntre B(2) şi P (2), (B(2) ≡ P (2)). Algebrele Postiene pot fio replică pentru algebrele Booleene, dar operarea ı̂n aceste algebre, ca aplicaţii pentrufuncţiile de comutaţie, devine dificilă pe măsură ce q are valori mai mari.

Cea de a doua cale de generalizare, dezvoltată de B.A. Bernstein, a generat oaltă clasă de algebre q -valente care pot fi definite pentru oricare număr ı̂ntreg prin q sau pentru un număr ı̂ntreg putere a lui q . Mulţimea de definiţie pentru o astfel dealgebră este {0, 1, 2, . . . , q − 1}, iar operatorii sunt operaţiile aritmetice de adunareşi de ı̂nmulţire modulo q . Structurile algebrice definite pe clasele de resturimodulo q (q număr prim) sunt referite prin câmpuri Galois şi sunt notatecu GF (q) . Pentru GF (3) tabelele de adevăr prin aplicarea operatorilor produs, ,şi sumă,

⊕, modulo 3 sunt:

0 1 2 ⊕ 0 1 20 0 0 0 0 0 1 21 0 1 2 1 1 2 02 0 2 1 2 2 0 1

Dintre structurile GF (q ) cea pentru q = 2, GF (2) algebra modulo 2, denumităalgebră Reed-Muller, prezintă interes ca suport formal ı̂n implementările unoralgoritmi sau circuite de calcul sau de codificare. Operatorii algebrei Reed-Muller auurmătoarele tabele de adevăr:

0 1 ⊕ 0 1 x x0 0 0 0 0 1 0 11 0 1 1 1 0 1 0

Se observă că atât pentru algebra Booleană B(2) cât şi pentru algebra Reed-Muller, GF (2), operatorii de ı̂nmulţire logică sunt identici ( = ·), la fel şi operatoriide complementare. În schimb, diferă operatorii disjuncţie, aceştia fiind SAU INCLU-SIV (sumă logică, +) ı̂n B(2) şi respectiv SAU EXCLUSIV (sumă aritmetică modulo


13/612


2, ⊕) ı̂n GF (2). Aceast̆a, aparent nêınsemnată diferenţă, determină semnificativediferenţe ı̂ntre cele două formalisme, ceea ce apare şi ı̂n metodele de proiectare şiimplementare. Axiomele pe GF (2) sunt:

1. Închiderea. GF (2) este ı̂nchisă ı̂n A∈

GF (2), B ∈

GF (2)⇒

A

B ∈

GF (2),raport cu operatorii şi ⊕. A⊕B ∈ GF (2)

A⊕ (B ⊕C ) = (A⊕B) ⊕ C = A ⊕B ⊕ C 2. Asociativitatea.

A (B C ) = (AB) C = A B C 3. Comutativitatea. A⊕B = B ⊕A, A B = B A4. Distributivitatea. A (B ⊕ C ) = A B ⊕A C 5. Elementul neutru. A⊕ 0 = A, A 1 = A

Din prezentarea acestor proprietăţi apare similaritatea dintre GF (2) cu algebranumerelor reale (care este definită pe un câmp infinit). Dar următoarea axiomă relevăo proprietate diferită ı̂ntre aceste două algebre care rezultă din natura aritmeticiimodulo 2.

6. Existenţa inversului. A⊕

A = 0, A

A = A

Din ultima axiomă a algebrei GF (2) rezultă că A = −A, adică fiecare element esteegal cu inversul său; aceasta ı̂nseamnă că adunarea şi scăderea sunt identice ı̂nGF (2), ceea ce este diferit faţă de adunarea aritmetică din algebra numerelor reale.Folosind această axiomă se deduce: dacă A ⊕ B = C atunci A = C ⊕ B, B = A ⊕ C şi A ⊕ B ⊕ C = 0.

Se pot duce relaţii pentru exprimarea operatorilor din B (2) prin cei din GF (2)

A · B = A BA + B = A B ⊕ A ⊕ B (1.3-a)

A = A ⊕ 1

care se pot demonstra ı̂n felul următor. Se consideră expresia pentru sumă modulodoi A ⊕ B = A · B + A · B (a se vedea funcţia f 6(x1, x0) ı̂n 1.1.3)

A ⊕ 1 = A · 1 + A · 1 = A · 0 + A = AA + B = A + B = A · B = ((A ⊕ 1) (B ⊕ 1)) ⊕ 1

= (A B ⊕ 1 B ⊕ A 1 ⊕ 1 1) ⊕ 1 = (A B ⊕ B ⊕ A ⊕ 1) ⊕ 1= A B ⊕ B ⊕ A ⊕ 1 ⊕ 1 = A B ⊕ B ⊕ A

Iar pentru exprimarea operatorilor din GF (2) prin cei din B (2) există relaţiile

A B = A · BA

⊕B = A

·B + A

·B (1.3-b)

A ⊕ 1 = A

Relaţiile 1.3 indică modalităţi de utilizare atât a formalismului din GF (2) cât şi acelui din B(2) pentru implementarea sistemelor ı̂n funcţie de suportul fizic (circuistica)disponibilă.


14/612


1.1.3 Funcţii Booleene

Fie B(2) = ({0, 1}, ·, +, −) algebra Booleană binară. Un cuvânt binar este osuccesiune de biţi; un cuvânt este caracterizat prin lungimea sa, adică de numărul debiţi din succesiune.

Definiţia 1.3 Vom numi o configuraţie binară de n biţi, sau cuvânt binarcu 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 2n cuvinte distinctefiecare cu lungimea de n biţi; deci mulţimea {0, 1}n este constituită din 2n cuvintedistincte cu lungimea de n biţi.

Definiţia 1.4 O funcţie Booleană 1, f , cu n intrări şi m ieşiri este o aplicaţie

f : {0, 1}n → {0, 1}m (1.4)cu domeniul de definiţie ı̂n X = {0, 1}n şi cu domeniul de valori ı̂n Y ⊆ {0, 1}m.

Relaţia 1.4, ı̂n cazul când funcţia logică are o singură ieşire, m = 1, cuvântul deieşire are lungimea de un bit, se retranscrie sub forma:

f : {0, 1}n → {0, 1}1 (1.5)Teoretic, funcţia logică cu m ieşiri se poate construi din m aplicaţii de forma

1.5 conectate ı̂n paralel. O funcţie logică cu numărul de ordine i dintr-o familiede funcţii logice de n variabile, definită conform relaţiei 1.4, va fi notată sub formaf i(xn−1, xn−2, . . . , x1, x0) sau sub forma f

ni .

În acest capitol se vor studia doarfuncţiile cu o singură ieşire.

Funcţia logică de zero variabile. Domeniul de definiţie pentru funcţia de zerovariabile este mulţimea vidă, {0, 1}0, iar domeniul de valori este {0, 1}. Rezult̆a căpot exista două funcţii notate cu f 0

0

şi f 0

1

care generează pe ieşire cele două valori dinmulţimea {0, 1}

f 00 = 0

f 01 = 1 (1.6)

De fapt, putem spune că aceste funcţii sunt identice cu două constante. Într-unsistem digital cele două constante pot fi reprezentate fizic prin două tensiuni fixe:tensiunea de alimentare (V DD, V CC ) şi tensiunea de masă V SS sau 0V (liniile/barelede alimentare ale circuitului).

Funcţii logice de o singură variabilă. Configuraţiile distincte de un singur bitpe mulţimea de definiţie {0, 1}1 sunt cei doi biţi 1 şi 0. Deci funcţia y = f (x), pentrufiecare valoare binară atribuită variabilei x, poate lua una din cele două valori binare

y = 1 sau y = 0. Cu cele două valori posibile pentru y se pot forma patru cuvintediferite, deci pentru o singură variabilă există patru funcţii logice distincte: f 10 , f

11 ,

f 12 şi f 13 reprezentate ı̂n tabelul din Figura 1.1.

1Termenul de funcţie Booleană, ı̂n această carte, este sinonim cu funcţie logică.


15/612


f 01 f 1

1 f 21 f 3

1

00 0

0 011

1

1

1

a)

"0"

b) c)

xx

d)

x

x

e)

VCCx

x

x "1"

Figura 1.1 Funcţiile de o singură variabilă: a) tabelul funcţiilor de o variabilă;b) f 10 , funcţia zero (conectarea la masă); c) f

12 , funcţia inversor (circuitul inversor);

d) f 11 , funcţia identitate (driver, buffer); e) f 13 , funcţia tautologie (conectarea la ten-

siunea de alimentare).

1. Funcţia zero f 0(x) = 0. Aceasta genereaz̆a valoarea 0 indiferent de valoareaalocată variabilei x. Într-un sistem nu se va calcula niciodată funcţia zero deoarecevaloarea acestei funcţii există, fizic punctul respectiv se leagă la tensiunea de masă;evident f 10 şi f

00 au acelaşi efect adică valoarea constantă 0.

2. Funcţia identitate, f 1(x) = x. Logic, această funcţie pare a fi fără utilitate; dar,practic, această funcţie este foarte utilizată sub denumirea de driver sau buffer şiı̂ntr-un sistem fizic are o acţiune de a aduce/̂ıntări la anumite valori normale semnalulelectric care este suport pentru variabila x. Aceste circuite care nu realizează o funcţielogică ci doar au rol de “̂ıntărire

,,a semnalului electric sunt referite prin circuit buffer

sau circuit driver respectiv buffer sau driver.3. Funcţia negaţie (NOT), f 2(x) = x. De fapt, acesta este operatorul de com-

plementare din Tabelul 1.1. Putem interpreta aspectul logic sau aritmetic al acţiuniiacestei funcţii. Logic, funcţia negaţie aplicată va substitui adevărul cu fals şi fal-sul cu adevăr. Aritmetic, este un incrementor sau decrementor pentru numărarea

ı̂n baza doi (atât la numărare ı̂n sens crescător (direct) cât şi ı̂n sens descrescător(invers), trecerea ı̂ntre două numere consecutive se face prin modificarea bitului celmai puţin semnificativ, LSB (Least Significant Bit), din unu ı̂n zero sau din zero ı̂nunu, vezi Figura 2.17-a şi 2.17-b). Suportul fizic pentru implementarea acestei funcţiieste elementul inversor.

4. Funcţia tautologie, f 3(x) = 1. Acestă funcţie generează valoarea 1 indiferent devaloarea alocată variabilei x. Într-un sistem nu se va calcula niciodată această funcţiedeoarece valoarea sa există, fizic punctul respectiv se leagă la tensiunea de alimentareV DD/V CC ; evident f

13 şi f

01 au acelaşi efect.

Funcţii de două variabile. La o funcţie de două variabile f (x1, x0) mulţimeade definiţie, {0, 1}2, este compusă din cele patru cuvinte de intrare de doi biţi. Pentrucele patru cuvinte de intrare se obţin pentru funcţie patru valori binare, dar cu cele

patru valori binare se pot obţine 4

2

= 16 cuvinte, deci, ı̂n total există 16 funcţiidiferite de două variabile care sunt prezentate ı̂n tabelul din Figura 1.2-a.Aceste funcţii au anumite denumiri care exprimă acţiunea realizată:1. f 0(x1, x0) = 0, funcţia zero. Acţiunea sa este identică cu a celor două funcţii

f 00 ,f 10 .


16/612


f 02 f 1

2 f 22 f 3

2 f 42 f 5

2 f 62 f 7

2 f 82 f 9

2 f 102 f 11

2 f 122 f 13

2 f 142 f 15

2

0

0

0

01

1

1

1

0

0

0

0

0

0

0

0

0

0

1

1

1

1

0

0

1

0

0

0

0

0

1

1

1

1

0

0

1

1

1

0 1

0

0

0 1

1

0

0 1

1

0

0 1

1

1

0 1

1

0

0 1

1

1

0 1

1

1

0 1

1

1

1

a)

c)b)

d) e)

x1 x2

x1

x1 x0f 9 =

f 6 = x1 x0 x0.f 7 = x1

f 1 = x1+x0

x0

x1

x0

x0

x1

x1

x0

Figura 1.2 Funcţii de două variabile: a) tabelul funcţiilor de două variabile;b) simbolul grafic pentru funcţia XOR, f 26 ; c) simbolul grafic pentru funcţia NAND,f 27 ; d) simbolul grafic pentru funcţia NXOR, f

29 ; e) simbolul grafic pentru funcţia

NOR, f 21 .

2. f 1(x1, x0) = x1 + x0, funcţia SAU-NEGAT/NOT-OR/NOR cu reprezentareagrafică din Figura 1.2-e. Se observă că valorile funcţiei rezultă prin negarea valorilorobţinute cu operatorul OR (Tabelul 1.1).

3. f 2(x1, x0) = x1 · x0 , funcţia negarea implicaţiei inverse; circuitul interdicţie(inhibare).

4. f 3(x1, x0) = x1, negarea lui x1.5. f 4(x1, x0) = x1 · x0, funcţia negarea implicaţiei directe; circuitul interdicţie

(inhibare).

6. f 5(x1, x0) = x0, negarea lui x0.

7. f 6(x1, x0) = x1 · x0 + x1 · x0, funcţia negarea coincidenţei, SAU-EXCLUSIV/XOR cu simbolul grafic de reprezentare ı̂n Figura 1.2-b şi cu structura de imple-mentare ı̂n Figura 1.3-a. Acţiunea acestei funcţii poate fi interpretată ı̂n trei modali-tăţi.

Prima, se observă că asupra celor două valori binare ale variabilelor x1 şi x0 funcţiaoperează ca un sumator modulo 2 (0⊕0 = 0, 0⊕1 = 1, 1⊕0 = 1, 1⊕1 = 0) de undeşi notaţia consacrată f 6(x1, x0) = x1 ⊕ x0. O altă variantă echivalentă de exprimarese obţine ı̂n felul următor: 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. Dacă una dinvariabile este 1 atunci valoarea funcţiei va fi egală cu negata celeilalte variabile deintrare; f 6(x1, 1) = x1 ⊕ 1 = x1.

A treia interpretare este cea de negarea coincidenţei, adică anticoincidenţă


17/612


(şi invers, negarea anticoincidenţ ei este coincidenţa, adică x1 ⊕ x0). Rezult̆a că sepoate realiza foarte uşor un circuit pentru coincidenţa a două cuvinte de doi biţix1x0, y1y0 raţionând ı̂n felul următor: cuvintele coincid când nu este adevăratăanticoincidenţa pentru biţii de rangul unu x1, y1 SI nu este adevărată anticoincidenţapentru 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 coin-cidenţă este dată ı̂n Figura 1.3-c.

8. f 7(x1, x0) = x1 · x0, funcţia SI-NEGAT/NOT-AND/NAND, cu simbolul graficde reprezentare din Figura 1.2-c. Se observă că valorile funcţiei rezultă prin negareavalorilor obţinute cu operatorul AND (Tabelul 1.1).

9. f 8(x1, x0) = x1 · x0, funcţia conjuncţie, produsul logic AND, SI.10. f 9(x1, x0) = x1 · x0 + x1 · x0 , f 9(x1, x0) = x1 ⊕ x0, funcţia coincidenţă,

SAU-EXCLUSIV NEGAT/NXOR cu simbolul grafic de reprezentare ı̂n Figura 1.2-dşi cu structurarea ca ı̂n Figura 1.3-b. Implementarea circuitului de coincidenţă a douăcuvinte de doi biţi x1x0 şi y1y0 este prezentată ı̂n Figura 1.3-d; (x1 ⊕ y1) · (x0 ⊕ y0).

11. f 10(x1, x0) = x0, funcţia ce nu depinde de x1.12. f 11(x1, x0) = x1 + x0, funcţia implicaţie directă.

13. f 12(x1, x0) = x1, funcţia ce nu depinde de x0.14. f 13(x1, x0) = x1 + x0, funcţia implicaţie inversă.15. f 14(x1, x0) = x1 + x0, funcţia conjuncţie, sumă logică OR, SAU.16. f 15(x1, x0) = 1, funcţia tautologie, acţiunea sa este identică cu ale funcţiilor

f 01 , f 13 .

Funcţii de trei variabile. Pentru funcţiile de trei variabile f (x2, x1, x0) mul-ţimea de definţie, {0, 1}3, este compusă din opt (23 = 8) cuvinte binare de 3 biţi,pentru fiecare din aceste cuvinte funcţia poate avea o valoare binară 0 sau 1. Cuopt valori binare pot fi definite 28 funcţii diferite. Modul de formare al funcţiilor detrei variabile f 3i , i = 0, 1, . . . , 255 rezultă din Tabelul 1.3 . Indicele i, care identifică

d)

a)

x1 x1 x1x0

x1x0

b)

x1 x0

x1

x0

x0x0

x0 x1

x1x0

x1x0

x1 x0

c)

x1y1

x0y0

x1 = y1

x0 = y0

x1x0 y1y0=

x1y1

x0y0

x1=y1

x0=y0

x1x0 y1y0=

Figura 1.3 Funcţiile XOR şi NXOR: a,b) structura circuitelor XOR, respectivNXOR; c,d) circuite de coincidenţă cu XOR şi NXOR.


18/612


funcţia f 3i , este corespondentul zecimal al numărului binar de 8 biţi format cu valorilebinare ale funcţiei. De exemplu funcţia f 187 are următoarele valori binare 1101 1101,deoarece 187|10 = 1101 1101|2. Bitul cel mai semnificativ, MSB (Most SignificantBit), din cuvântul valorilor funcţiei, corespunde configuraţiei de intrare x2x1x0 = 111,iar LSB corespunde configuraţiei de intrare x 2x1x0 = 000.

Utilitatea tuturor funcţiilor f 3i pentru implementarea sistemelor logice este dis-cutabilă deoarece , 16 dintre aceste funcţ ii sunt echivalentul funcţiilor f 2i iar unele

din cele rămase pot fi compuse prin intermediul altor funcţ ii de două variabile. Îngeneral, pentru implementarea sistemelor logice sunt utilizate doar câteva din funcţiileexpuse pentru cazul n = 2.

Pentru n variabile numărul funcţiilor logice distincte este 2(2n); ceea ce

determină pentru n = 4 → 216 = 65536 funcţii, iar pentru n = 5 → 232 = 4294967296funcţii(!).

Definiţia 1.5 Un sistem complet de funcţii Booleene este un set minimalde funcţii Booleene cu ajutorul cărora se poate exprima orice funcţie Booleană.

În paragraful 1.1.1 s-au definit cele trei legi de compoziţ ie pe mulţimea B. Cu

ajutorul celor trei operatori NOT, AND şi OR poate fi exprimată oricare funcţielogică, deci aceşti operatori formează un sistem complet.Al doilea set de operatori care pot constitui un sistem complet este perechea

NOT şi AND. Acest set poate fi substituit numai cu o singur̆a funcţie, funcţiaf 7(x1, x0) = (x1 · x0), adică operatorul NAND, deoarece operatorul NOT apare caun NAND de aceeaşi variabilă (x · x) = x, iar operatorul AND rezultă ca un NANDnegat, (x1 · x0) = x1 · x0.

Al treilea set de operatori OR şi NOT formează de asemenea un sistem complet.Şi această pereche de operatori poate fi substituită numai cu o singură funcţie, funcţiaf 2(x1, x0) = x1 + x0, care este operatorul NOR. Deoarece NOR este un OR negat se

poate obţine uşor OR prin negarea NOR-ului, (x1 + x0) = x1 + x0, iar NOT-ul este

Tabelul 1.3 Funcţii logice de trei variabile

f 03 f 1

3 f 23 f 17

3 f 1873 f 255

3

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1 1

1

1

1

1

1

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

0

0

0

1

0

0

0

1

1

1

1

1

1

0

0 1

1

1

1

1

1

1

1

17 10 = 0001001 2 187 10 = 10111011 2

x2 x1 x0


19/612


identic cu NOR-ul aplicat aceleiaşi variabile (x + x) = x.

În Tabelul 1.4 sunt modelaţi operatorii NOT, AND, OR, NAND şi NOR fie numaicu NAND, fie numai cu NOR. Apare, deci, posibilitatea ca un sistem logic s ă poatăfi realizat doar cu un singur operator. Consecinţa practică a acestei observaţii esteenormă prin faptul că implementarea unui sistem se poate obţine prin replicareaaceluiaşi operator (acelaşi tip de circuit), ı̂n consecinţă preţul de cost scade foartemult şi siguranţa ı̂n funcţionare creşte.

Există circuite integrate, produse de turnătoria de siliciu, dar ı̂ncă neterminate,care conţin un singur (sau două) circuite logice elementare ı̂ntr-un număr foarte mare,referite ca arie de porţi logice (gate-array, vezi secţiunea 4.3). Pe o astfel de arie deporţi logice utilizatorul ı̂şi poate realiza sistemul pentru aplicaţia sa prin proiectareadoar a conexiunilor ı̂ntre un număr de circuite logice elementare. Apoi, turnătoria desiliciu termină circuitul integrat, prin realizarea conexiunilor proiectate de utilizator,rezultând astfel un circuit cu multe avantaje, la a cărui construcţie a participat atâtutilizatorul (custom) cât şi turnătoria de siliciu; sistem referit ca fiind o proiectare detip semi-custom.

1.1.4 Forme canonice

Definiţia 1.4 exprimă noţiunea de funcţie logică de n variabile. Cu cele n variabilese pot compune, prin intermediul operatorilor AND, OR şi NOT, termenii funcţiei şila fel tot cu aceşti operatori pot fi incluşi termenii ı̂n cadrul funcţiei. În consecinţă,un termen al unei funcţii logice poate avea variabile negate sau nenegate (NOT), carepot fi ı̂nsumate logic (OR) sau ı̂nmulţ ite logic (AND).

Definiţia 1.6 Termenul canonic produs este produsul logic a tuturor celorn variabile ale funcţiei, negate sau nenegate. Termenul canonic produs este referit caminterm.

Exemplu de termen canonic produs pentru n = 3 poate fi x 2 · x1 · x0. Un termencanonic produs nu poate fi format din mai mult de n factori (variabile). Dacă ar avea

mai mult de n factori atunci ar ı̂nsemna că una sau mai multe variabile ar intra ı̂nprodusul logic atât negate cât şi nenegate ceea ce, conform axiomei de existenţă acomplementului x · x = 0, Tabelul 1.2 , ar ı̂nsemna că termenul se reduce la constanta

Tabelul 1.4 Modelarea operatorilor logici pe bază de NAND sau NOR

AA A+B

B

A

B

AA

B

A.B = A+B

A.B = A+BA = A .A

AA A+BA.BA

B

A = A+A

A+B

A.BA+B =

B

A.BA

B

A

A+B A+B

A+BA+B =

AA

A+BA+B =

A.B

B

ANAND

A.B A+B=

B

AA+B

A B.

A+B

B

A

A+BA

B

NOR

A+B A+B=

A.BA+B =

A.BA.B

B

A

A B.A

B

NAND

A+BA

B

NORA+B

Operatorul

logicmodelatcu poarta:

NOT AND OR

B

A A+B

A

B

A

B

A

BB

A


20/612


Tabelul 1.5 Codificarea termenilor canonici produs şi sumă (n=3)

Valoareavariabilelor

0

1

2

3

4

5

6

7

i

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1 1

1

1

1

1

1

1

1

x2 x1 x0

x0x2x1 = P0

x1x2 x0 = P1

x0x2x1 = P2

x0x2x1 = P3

x1x2 x0 = P4

x1x2 x0 = P5

x1x0x2 = P6

x2 x0x1 = P7

si codul Pi

Mintermul

x2 +x1 x0+ = S0

x2 x1 x0+ + = S1

x2 x1 x0+ + = S2

+ +x2 x1 x0 = S3

x1x2 x0 = S4+ +

x1x2 + +x0 = S6

x0+ +x2 x1 = S7

x1x2 = S5+ +x0

si codul Si

Maxtermul

0. Un termen produs se notează prin P i. Numărul tuturor termenilor produs P i este2n, deci i = 0, 1, 2, . . . , 2n − 1.

Dar cum se codifică un minterm prin simbolul P i ? Se va exemplifica pentru cazuln = 3. Un termen canonic produs are valoarea logică 1 numai atunci când toţi factoriisăi au valoarea logică 1. Pentru exemplul anterior de termen produs x2 · x1 · x0, cuvaloarea logică 1, rezultă o unică configuraţie de valori: x2 = 1, x1 = 0, x0 = 1.Cuvântul binar format din valorile variabilelor este 101, care este num ărul cinci ı̂nzecimal, reprezentat ı̂n codul de numeraţie binar natural. Deci, iată că mintermulx2 ·x1 ·x0 poate fi codificat prin litera P cu indicele 5, adică P 5; dar această codificaretrebuie să fie o aplicaţie bijectivă deci şi trecerea inversă de la codul P i la exprimareaca produs logic canonic a mintermului trebuie s ă fie unică. De exemplu, trecerea dela termenul canonic produs P 6 la mintermul corespunzător se face ı̂n felul următor:

6|10 = 110|2 → x2 · x1 · x0.Rezultă următoarea regulă de codificare a termenilor canonici produs: pentru re-prezentarea unui minterm prin simbolul P i variabilelor negate li se atribuie valoareazero, iar variabilelor nenegate li se atribuie valoarea unu. Este corect̆a şi reciproca,ı̂n cuvântul de cod P i pentru un bit cu valoarea unu corespunde ı̂n produsul logiccanonic o variabilă nenegată iar pentru un bit cu valoarea zero corespunde o variabilănegată. Apliĉand această regulă pentru funcţia de trei variabile se pot scrie relaţiiledin Tabelul 1.5 .

Definiţia 1.7 Termenul canonic sumă este suma logică a tuturor celor nvariabile ale funcţiei, negate sau nenegate. Termenul canonic sumă este referit camaxterm.

Pentru o funcţie de trei variabile (n = 3) ca un exemplu de termen canonic sumă

poate fi acesta x2 +x1 +x0. La fel, ca şi la termenul canonic produs, un termen canonicsumă nu poate fi compus din mai mult de n variabile, ı̂n caz contrar ı̂n termen arexista suma x + x = 1, deci valoarea termenului ar fi egală cu constanta 1. Numărultotal de termeni canonici sumă este 2n iar codificarea se face prin simbolul S i.

Termenul canonic sumă x2 + x1 + x0 are valoarea logică zero numai atunci când


21/612


fiecare termen al sumei are valoarea zero, adică x2 = 1, x1 = 0, x0 = 1. Rezultăindicele i al simbolului S i ca fiind egal cu numărul zecimal ce este reprezentat ı̂nbinar de cuvântul format din valorile celor trei variabile adică 101|2 = 5|10, deci S 5.Trecerea inversă, de exemplu de la S 6 la maxtermul corespunzător, se face ı̂n felulurmător 6

|10 = 110

|2

→x2 + x1 + x0.

Rezultă următoarea regulă de codificare a termenilor canonici sumă pentru repre-zentarea unui maxterm prin simbolul S i: variabilelor negate li se atribuie valoareaunu, iar variabilelor nenegate li se atribuie valoarea zero. Este corectă şi reciproca, ı̂ncuvântul de cod pentru un bit cu valoarea unu corespunde ̂ın sumă logică canonică ovariabilă negată iar pentru valoarea zero corespunde o variabilă nenegată. Conformacestei reguli de codificare pentru n = 3 se pot scrie relaţiile din Tabelul 1.5 .

Se observă că, pentru codificare, la aceeaşi variabilă nenegată se atribuie valoarea1 ı̂n minterm şi 0 ı̂n maxterm şi pentru aceeaşi variabilă negată se atribuie valoarea0 ı̂n minterm şi 1 ı̂n maxterm. Iar pentru trecerea inversă, de la cod la expresialogică, unui bit 1 ı̂n cuvântul de cod ı̂i corespunde o variabilă nenegată ı̂n mintermşi o variabilă negată ı̂n maxterm şi invers pentru bitul 0. Ca o consecinţă, din acestereguli de codificare, se pot demonstra următoarele relaţii:

S i = P i; P i = S i (1.7)

adică termenul canonic sumă se obţine prin negarea termenului canonic produs şiinvers.

La fel, pentru i = j , i, j = 0, 1, 2, . . . , 2n − 1, se pot demonstra relaţiile:

P i · P j = 0; S i + S j = 1 (1.8)(pe baza x + x = 1, x · x = 0, Axioma 6).

Valoarea unui termen P i, respectiv S i se poate modifica prin intermediul unuicoeficient binar di ∈ {0, 1} ı̂n felul următor:

a) di · P i = P i dacă di = 1

0 dacă di = 0 (1.9-a)

b) di + S i =

S i dacă di = 00 dacă di = 1

(1.9-b)

Definiţia 1.8 Forma canonică normală disjunctivă, FCND, a unei funcţiide n variabile este suma logică a tuturor termenilor de forma 1.9-a.

f (xn−1, xn−2, . . . , x1, x0) =

2n−1i=0

di · P i (1.10)

Definiţia 1.9 Forma canonică normală conjunctivă, FCNC, a unei funcţii

de n variabile este produsul logic a tuturor termenilor de forma 1.9-b.

f (xn−1, xn−2, . . . , x1, x0) =

2n−1i=0

(di + S i) (1.11)


22/612


Definiţia 1.10 Forma normală disjunctiv̆a, FND, a unei funcţii de nvariabile este o sumă numai de mintermi ai căror coeficienţi d i = 1

Forma FND se obţine din FCND prin eliminarea mintermilor ai căror coeficienţiau valoarea di = 0. Pentru exprimarea FND se introduce o reprezentare simbolică,

sub forma unei liste

f (xn−1, xn−2, . . . , x1, x0) =2n−1

i=0

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

care conţine doar indicii acelor coeficienţ i ai funcţiei care au valoare di = 1. Deexemplu, pentru o funcţie de patru variabile:

f (x3, x2, x1, x0) =

15i=0

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

această listă enumeră doar indicii coeficienţilor binari d 0 = 1, d3 = 1, d4 = 1, d5 = 1,d8 = 1, d9 = 1, d12 = 1, d14 = 1 şi d15 = 1.

Definiţia 1.11 Forma normală conjunctivă, FNC, a unei funcţii de nvariabile este un produs numai de maxtermi ai căror coeficienţi d i = 0.

Forma FNC se obţine din FCNC prin eliminarea maxtermilor ai căror coeficienţidi = 1. Pentru exprimarea FNC se introduce o reprezentare simbolică sub forma uneiliste

f (xn−1, xn−2, . . . , x1, x0) =

2n−1i=0

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

care conţine doar indicii acelor coeficienţi ai funcţiei care au valoarea d i = 0. Luândca exemplificare funcţia dată la relaţia 1.12 de data aceasta lista va fi

f (x3, x2, x1, x0) =15

i=0

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

adică sunt enumeraţi doar indicii coeficienţilor binari care au valoarea zero.Uneori este avantajos să se lucreze cu negata formei normale conjunctive sau cu

negata formei normale disjunctive ale funcţiei care pot fi exprimate respectiv subformele

a) f (xn−1, xn−2, . . . , x1, x0) =

2n−1i=0

(di + S i) (1.14-a)

b) f (xn−1, xn−2, . . . , x1, x0) =2n−1

i=0(di

·P i) (1.14-b)

Aceste forme de scriere se pot obţine pornind de la relaţiile 1.10 şi 1.11, prinnegarea ambelor părţi, apoi aplicarea teoremei lui DeMorgan şi ţinând cont de relaţiile1.7, ı̂n felul următor:


23/612


f (xn−1, xn−2, . . . , x1, x0) =2n−1

i=0

(di · P i) =2n−1

i=0

(di + P i) =2n−1

i=0

(di + S i)

f (xn−1, xn−2, . . . , x1, x0) =

2n−1i=0

(di + S i) =

2n−1i=0

(di · S i) =2n−1

i=0

(di · P i)

Aceste exprimări se pot deduce şi prin raţionament din relaţiile 1.10 şi 1.11. DinFCND se obţine FND dacă se consideră numai termenii canonici produs care auvaloarea 1, relaţia 1.12, respectiv din FCNC se obţ ine FNC, relaţia 1.13, dacă seconsideră numai termenii canonici sumă care au valoarea 0. Sub forma FND funcţiaare valoarea 1 pentru suma tuturor termenilor canonici care au coeficienţii d i = 1 şiare valoarea 0 pentru suma tuturor termenilor canonici care au coeficienţii di = 0.Evident că funcţia negată f va avea valoarea 1 pentru suma tuturor acelor termenicanonici care produc valoarea 0 pentru f , adică pentru acei coeficienţi di care sunt0; respectiv funcţia negată f va avea valoarea 0 pentru suma tuturor acelor termeni

canonici care produc valoarea 1 pentru f , adică pentru acei coeficienţi di = 1. Decifuncţia negată f poate fi scrisă ca o formă FND, relaţia 1.14-b, de acei termeni produspentru care di = 1, adică pentru acei coeficienţi di care au valoarea 0 la scriereafuncţiei f sub formă FND. Acelaşi raţionament se poate face şi pentru forma FNC,adică se scrie funcţia f pentru coeficienţii d i care au valoarea 0 iar funcţ ia f , relaţia1.14-a, pentru coeficienţii care au valoarea 1, adică d i = 0.

O modalitate uzuală de definire a unei funcţii logice este cea prin tabelul de adevăr.

Definiţia 1.12 Tabelul de adevăr este un tabel care ı̂n prima coloană dinstânga, coloana de intrare, listează toate configuraţiile de valori ale variabilelor deintrare X = {0, 1}n, iar ı̂n următoarele coloane, coloane de ieşire, sunt listate valorile,din Y ⊆ {0, 1}, corespunzătoare ieşirilor.

Astfel de tabele de adevăr au fost prezentate iniţial ı̂n Tabelul 1.1 pentru intro-

ducerea operatorilor booleeni NOT, AND, OR iar apoi ı̂n Figurile 1.1, 1.2 şi Tabelul 1.2 , respectiv pentru funcţile logice de una, două şi trei variabile.

Exemplul 1.1 Pentru o celulă sumator complet să se deducă funcţia logică sumă, s işi funcţia logică pentru transferul următor, C i.

Soluţie. În secţiunea 2.5.2 se va analiza sumarea a două cuvinte binare cu lungimea de nbiţi A = An−1An−2 . . . Ai . . . A1A0 şi B = Bn−1Bn−2 . . . Bi . . . B1B0. Operaţia de sumare acelor două cuvinte se realizează pentru fiecare pereche de biţi (Ai, Bi) ı̂ncepând cu perecheai = 0, de rangul cel mai puţin semnificativ, (20), până la perechea i = n−1, de rangul cel maisemnificativ, (2n−1). Pentru fiecare rang această sumare este efectuată cu o celulă sumatorcomplet. O celulă sumator complet pentru rangul i are trei intrări Ai, Bi, C i−1 care suntrespectiv biţii celor două cuvinte A şi B şi transportul anterior C i−1 ce a fost generat decelula din rangul 2(i−1). Semnalele generate la ieşire de către celula sumator complet suntdoi biţi: si –sumă (= Ai + Bi + C i−1) şi C i –transportul următor care se aplică la celula

de rang 2(i+1)

ca transport anterior. Celula sumator complet este notată uneori cusimbolul

(3, 2), indiĉand faptul că are trei intrări şi două ieşiri. Există şi celula

(2, 2)

care are numai două intrări Ai şi Bi (nu se consideră transportul anterior C i−1) care estereferită ca celulă semisumator. Pentru o celul̆a sumator complet tabelul de adevăr esteprezentat ı̂n Tabelul 1.6 .


24/612


Tabelul 1.6 Tabelul de adevăr pentru o celulă sumator/scăzător complet

Ai Bi Ci−1 / Ii−1 si gi pi di I i siCi Ci

Intrari Numarator de 1ScadereAdunare

00

0

0

1

1

1

1

00

1

1

0

0

1

1

01

0

1

0

1

0

1

01

1

0

1

0

0

1

00

0

1

0

1

1

1

00

0

0

1

1

00

1

1

1

1

1

01

1

0

1

0

0

1

01

1

1

0

0

0

1

00

0

1

0

1

1

1

01

1

0

1

0

0

1

(0)(1)

(1)

(2)

(1)

(2)

(2)

(3)

0

0

0

Pentru ieşirea sumă si forma normală canonică disjunctivă, FNCD conform relaţiei 1.10,este :

si(Ai, Bi, C i−1) =

7

i=0

di ·P i = d0 ·P 0+d1 ·P 1+d2 ·P 2+d3 ·P 3+d4 ·P 4+d5 ·P 5+d6 ·P 6+d7 ·P 7

unde di, i = 0, 1, 2, . . . , 7 sunt coeficienţii funcţiei din coloana si din Tabelul 1.6 . Evidentcă produsele pentru care di = 0 pot fi eliminate deoarece au valoarea 0 şi se obţine formanormală disjunctivă, FND.

si(Ai, Bi, C i−1) = 1 · P 1 + 1 · P 2 + 1 · P 4 + 1 · P 7 == Ai · Bi · C i−1 + Ai · Bi · C i−1 + Ai ·Bi ·C i−1 + Ai · Bi ·C i−1

Se observă că FND se poate scrie direct luând numai acei mintermi pentru care funcţiaare valoarea 1 ı̂n tabelul de adevăr,

si(Ai, Bi, C i−1) =7

0

(1, 2, 4, 7)

de unde şi expresia de “sinteză pe bază de 1,,

. Aplicând axiomele şi teoremele din Tabelul 1.2 , şi expresiile pentru XOR şi NXOR, forma normală disjunctivă pentru s i se transformăı̂n felul următor:

si(Ai, Bi, C i−1) = Ai · (Bi · C i−1 + Bi · C i−1) + Ai · (Bi · C i−1 + Bi · C i−1) == Ai · (Bi ⊕ C i−1) + Ai(Bi ⊕C i−1) = Ai ⊕Bi ⊕C i−1 (1.15)

Dar din Tabelul 1.6 se poate face şi sinteza funcţiei negate si, aceasta va avea valori 1(di = 1) acolo unde si are valori 0 (di = 0), relaţia 1.14-b, deci forma normală disjunctivă afuncţiei negate se scrie direct examinând tabelul de adevăr:

si(Ai, Bi, C i−1) =7

i=0

(0, 3, 5, 6) =

= Ai · Bi · C i−1 + Ai · Bi · C i−1 + Ai · Bi · C i−1 + Ai · Bi · C i−1 == Ai · (Bi ·C i−1 + Bi · C i−1) + Ai · (Bi · C i−1 + Bi · C i−1) == Ai ⊕Bi ⊕ C i−1


25/612


Se pune ı̂ntrebarea care cale se alege pentru sinteza funcţiei, cea prin FND pentru funcţianegată sau cea prin FND pentru funcţia nenegată? Răspunsul este evident: prin calea caresolicită mai puţin efort, adică cea care duce la o formă FND cu mai puţini mintermi.

Pentru funcţia C i sinteza se face din tabelul de adevăr, de data aceasta pe bază de zer-ouri, adică prin formele conjunctive. Forma canonică normală conjunctivă, FCNC, conform

exprimării din relaţia 1.11, se va scrie:

C i(Ai, Bi, C i−1) =7

i=0

(di + S i) =

= (d0 + S 0) · (d1 + S 1) · (d2 + S 2) · (d3 + S 3) · (d4 + S 4) · (d5 + S 5) ··(d6 + S 6) · (d7 + S 7)

unde di, i = 0, 1, . . . , 7 sunt coeficienţii funcţiei din coloana C i. Se pot elimina factorii pentrucare di = 1 deci se ajunge la forma normală conjunctivă FNC,

C i(Ai, Bi, C i−1) =70

(0, 1, 2, 4)

care se putea scrie direct prin inspectarea valorilor de zero (“sinteză pe bază de 0,,

) şiscrierea produsului de maxtermi ı̂n felul următor:

C i = S 0 · S 1 · S 2 · S 4 == (Ai + Bi + C i−1) · (Ai + Bi + C i−1) · (Ai + Bi + C i−1) · (Ai + Bi + C i−1)

Aplicarea proprietăţii de distributivitate la această expresie duce la 3 × 3 × 3 × 3 = 81termeni produs care ap oi sunt reduşi prin aplicarea axiomelor şi teoremelor algebrei Bo oleene.

A doua cale de sinteză pe bază de zerouri se poate face pentru funcţia negată C i prininspectarea tabelului de adevăr se aleg maxtermii pentru care funcţia are valoarea 1, relaţia1.14-a. Rezult̆a forma normală conjunctivă, FNC, pentru funcţia negată

C i(Ai, Bi, C i−1) =70

(3, 5, 6, 7) =

= (Ai + Bi

·C i−1)

·(Ai + Bi + C i−1)

·(Ai + Bi + C i−1)

··(Ai + Bi + C i−1)şi de data aceasta se pot obţine 81 de termeni produs care pot fi reduşi. Uzual, se alegeı̂ntre sinteza prin FNC pentru funcţia negată sau sinteza prin FNC pentru funcţia nenegatăprin observarea ı̂n tabelul de adevăr care cale duce la mai puţini maxtermi. Din aceste douătentative de sinteză pe bază de zero se constată dificultatea aplicării formelor conjunctive,acesta este unul din argumentele pentru care ı̂n practică se aplică aproape ı̂n exclusivitatesinteza pe bază de 1, adică FND, fie pentru funcţia negată f , fie pentru funcţia nenegată f .

În consecinţă, revenind la sinteza pe bază de 1 rezultă pentru C i

a) C i(Ai, Bi, C i−1) =7

i=1

(3, 5, 6, 7) =

= Ai · Bi · C i−1 + Ai · Bi · C i−1 + Ai · Bi · C i−1 + Ai · Bi · C i−1 (1.16)

o formă rezonabilă, faţă de sintezele anterioare prin FNC şi care prin procedee analitice esteadusă la următoarele forme disjunctive FD:

b) C i(Ai, Bi, C i−1) = Ai · (Bi ⊕ C i−1) + Bi · C i−1c) C i(Ai, Bi, C i−1) = C i−1 · (Ai ⊕Bi) · (Ai · Bi)


26/612


1.1.5 Forme disjunctive şi conjunctive

Forma disjunctivă FD a funcţiei este o sumă de termeni necanonici de undeşi denumirea de sumă de produse, iar forma conjunctivă FC a funcţiei este unprodus de termeni sumă necanonici, denumită şi produs de sume. Reducerea formelor

normale disjunctive (FND) sau normale conjunctive (FNC), respectiv la FD sau FCeste referită ca un procedeu de minimizare a funcţiei, deşi uneori nu se obţine formaminimă sau se obţin mai multe expresii (neminime).

Există trei modalit̆aţi de minimizare:

1 - analitică, utilizând axiomele şi teoremele algebrei Booleene. Această cale esteeficientă doar pentru funcţii cu număr mic de variabile şi de termeni.

2 - prin metode grafice (de exemplu diagrama Veitch - Karnaugh), de asemeneautilizabile pentru funcţii care nu au mai mult de 5-6 variabile.

3 - pe baza unor algoritmi sau abordări euristice . Există algoritmi (de exem-plu Quine - McQlusky) care pot fi aplicaţ i unor funcţii cu zeci de variabile şiieşiri multiple. Aceşti algoritmi stau la baza programelor de minimizare (de ex-

emplu Espresso - MV) incluse ı̂n medii de Programare Automată ı̂n Electronică,referite prin termenul tehnici EDA (Electronic Design Automation).

Minimizarea pe cale analitică implică puţină practică ı̂n utilizarea axiomelor şiteoremelor algebrei booleene. Această practică nu se bazează pe un algoritm anume cimai mult pe intuiţie. Astfel se pot adăuga termeni (tautologia) care apoi se grupeazăcu alţii ı̂ncât să se aplice (cel mai frecvent ) axioma de existenţă a complementului(x + x = 1), teorema absorbţiei sau absorbţia inversă.

Exemplul 1.2 Pentru următoarea formă normală disjunctivă

F (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 C D + A B C D + A B C D

să se deducă forma minimă.Soluţie. Se grupează câte 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 dublează) ı̂n felulurmător:

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 aplicând expresia funcţiei SAU EXCLUSIV NEGAT se obţine

F (A,B,C,D) = B ⊕D + B (A⊕ C )


27/612


Uneori se pune problema de a se parcurge traseul invers adică pentru o formăminimă să se deducă forma normală disjunctivă din care a provenit. În general,pentru o astfel de extindere de la un termen produs la un termen canonic produs seintroduc ı̂n termenul produs variabilele care lipsesc sub forma x + x. De asemenea,pentru ca o formă disjunctivă să fie extinsă la forma normală conjunctivă (produse desume) suma de termeni produs trebuie transformată ı̂ntr-un produs de sume utilizândaxioma distributivităţii A + B C = (A + B) (A + C ), iar ı̂n termenii sumă variabilelecare lipseau se introduc prin axioma de existenţă a complemntului x · x = 0.

Exemplul 1.3 Următoarea formă disjunctivă F (A,B,C ) = A B + A C să fie extinsăla forma normală conjunctivă.

Soluţie. În primul rând termenii produs sunt convertiţi ı̂n termeni sumă utilizândaxioma 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 )

Fiecărui termen sumă ı̂i lipseşte o variabilă care se introduce ı̂n felul următor:

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

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

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

În final se obţine:

F (A,B,C ) = (A + B + C ) (A + B + C ) (A + B + C ) (A + B + C ) =70

(0, 2, 4, 5)

Expresiile sub formă de sume de produse sau produse de sume se pot modela

pe două niveluri de operatori respectiv pe AND-OR sau OR-AND. De exempluurmătoarele forme FD şi FC:

F 1 = A B + C D şi F 2 = (A + B)(C + D)

pot fi modelate ca ı̂n Figura 1.4-a şi 1.4-b. Uneori se impune ca modelarea săse facă fie numai cu operatorul NAND sau fie numai cu operatorul NOR. Pentruforme FD modelarea se face uşor pe baza operatorului NAND (notăm simbolic prinA · B → (A, B)) deoarece aplicând sumei de produse teorema dublei negaţii şiapoi teorema lui DeMorgan se obţine tocmai un NAND de NAND-uri. În schimbpentru forme FC modelarea se face mai uşor pe baza operatorului NOR (notăm sim-bolic prin A + B → (A, B)) deoarece aplicând produsului de sume teorema dubleinegaţii şi apoi teorema lui DeMorgan se obţine tocmai un NOR de NOR-uri.

Astfel F 1 şi F 2 devin:

F 1 = A B + C D = A B · C D −→ ( (A, B), (C, D))F 2 = (A + B) (C + D) = (A + B) + (C + D) −→ ( (A, B), (C, D))


28/612


F1 = A B + C D. .

A

B

C

D

A

B

C

A B.

C D.D

F1 = (A B) (C D). ..

A

B

C

D

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

C

D

B

A

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

A+B

C+D

c)

b)

a)

d)

Figura 1.4 Implementarea formelor FD şi FC: a,b) pe două niveluri AND-OR,respectiv OR-AND; c,d) pe două niveluri NAND-NAND, respectiv NOR-NOR.

Numărând simbolurile şi rezultă că pentru fiecare funcţie sunt necesari treioperatori NAND respectiv NOR cu câte două intrări cum se poate vedea şi ı̂n Figura1.4-c şi 1.4-d. Variabilele negate pot fi obţinute prin x → (x, x) sau (x, x).Uneori pentru conversia modelării de tip AND-OR sau OR-AND, respectiv ı̂ntr-omodelare de tip NAND-NAND sau NOR-NOR se pot utiliza anumite reguli graficede transformare, care rezultă din axiomele şi teoremele algebrei Booleene. Acestereguli sunt:

Regula 1. La ieşirea unui operator se poate introduce un cerculeţ de negaţie daratunci trebuie introdus un cerculeţ de negaţie şi la intrarea operatorului imediaturmător (“Dubla negaţie este adevăr

,,), deci pe conexiunea ı̂ntre cei doi operatori

variabila nu suferă modificări;

Regula 2. Introducerea unui cerculeţ de negaţie pe ieşirea unei funcţii trebuie ur-mată, tot pe ieşire, de adăugarea ı̂ncă a unui cerculeţ de negaţie (buffer inver-sor). Respectiv, introducerea la o variabilă de intrare, ı̂ntr-un operator, a unuicerculeţ de negaţie trebuie precedată de negarea aceleiaşi variabile de intrare(aplicarea pe intrare a variabilei negate);

Regula 3. Când se face conversia unui simbol grafic iniţial ı̂ntr-unul final,

AND/NAND ↔ OR/NOR, se pot introduce la simbolul final cerculeţ e de ne-gaţie fie la intrare, fie pe ieşire, fie atât la intrare cât şi la ieşire dar numai dacăla terminalele corespunzătoare ale simbolului iniţial nu a existat un cerculeţ denegaţie ı̂n felul următor (de fapt această regulă nu este decât o aplicare graficăa teoremei lui DeMorgan):


29/612


AND

NAND NOR

OR

Exemplul 1.4 Pentru conversiile din Figura 1.4 să se aplice regulile grafice de trans-formare.

Soluţie. Aplicând regulile de conversie grafică se obţin succesiunile de circuite ca ı̂n

Figura 1.5.

A

B

C

D

A

B

C

D

AB

C

D

regula 3

B

C

D

A

FB

C

D

A

regula 1

A

B

D

C

F

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

F

a) Maparea AND − OR in NAND − NAND este o conversie naturala

regula 3regula 2

b) Maparea AND − OR in NOR − NOR este o conversie nepotrivita

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

A

C

B

D D

A

B

C

A

B

D

Cregula 1 regula 3

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

c) Maparea OR − AND in NOR − NOR este o conversie naturala

A

C

D

B

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

AB

D

C

AB

C

D

F

F F

FF

F

F FF

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

regula 3regula 1

Figura 1.5 Exemple de conversii grafice de tipul AND-OR/OR-AND ı̂nNAND-NAND sau NOR-NOR.

Uneori apare şi problema inversă a modelării, pentru o modelare dată să se deter-

mine expresia FD sau FC care ı̂l descrie, de fapt această abordare pentru un sistemdeja implementat este referită ca analiza sistemului. Se poate obţine funcţia logică amodelului prin următoarele trei modalităţi:

1 - pentru fiecare configuraţie de valori logice ale variabilelor de intrare se deduc


30/612


valori logice ı̂n punctele intermediare ale modelului şi respectiv se calculeazăvaloarea logică de ieşire şi ı̂n felul acesta se construieşte tabelul de adevăr.Apoi, din tabelul de adevăr rezultat se deduce funcţia logică.

2 - se scriu expresiile logice după fiecare simbol de operator logic, pornind de la

fiecare intrare ı̂nspre ieşire, rezultând după ultimul operator expresia logică afuncţiei. Această modalitate este asemănătoare cu prima: se merge de la intrareschemei spre ieşire din punct ı̂n punct, dar la prima modalitate cu valorilefuncţiei pe când la această modalitate cu expresiile funcţiei.

3 - utilizând convenţiile prin cerculeţe de negaţie.

A treia modalitate este recomandată doar atunci când operatorii au ieşirile negate(NAND, NOR) sau au intrări negate, deci parcurgerea de la intrare spre ieşire ridicăanumite dificultăţi. De ce? pentru că suntem mai obişnuiţi să operăm cu operatoriiAND şi OR cu intrări nenegate. De fapt, aceasta se reduce tot la a doua modalitatedar prin conversia operatorilor care conţin cerculeţe de negaţie ı̂n operatori fără acestecerculeţe, se ajunge la o reprezentare numai cu operatori AND şi OR.

Exemplul 1.5 Pentru modelele de circuite din Figura 1.6-a, 1.6-c să se deducă expresiafuncţiilor (aplicând cerculeţele de negaţie).

regula 3

b)

A

B

C

F

a)

A

B

C

F

F = A (B+C).

regula 3

regula 3

c)

D

B

CF

d)

D

A

B

CF

.F = (A+B) C+D

F

e)

D

A

B

C

Figura 1.6 Exemple de conversie a modelelor logice spre structuri cu op-eratori AND şi OR pentru determinarea funcţiilor logice.

Soluţie. Pentru modelul din Figura 1.6-a se aplică regula 3 şi se obţin numai operatoriAND şi OR, F = A · (B + C ). Pentru modelul din Figura 1.6-c se aplică de două ori regula3 şi structura poate fi considerată ca fiind compusă doar din operatori AND şi OR pentru

care se scrie foarte simplu expresia logică, F = D + C · (A + B).


31/612


Acest mod de transformare a modelelor logice este foarte indicat ı̂n depanareacircuitelor deoarece pornind de la intrare spre ieşire, după fiecare nivel logic de ORsau AND se poate verifica simplu corectitudinea semnalelor.

În ı̂ncheierea prezentării acestor noţiuni de suport formal pentru sistemele digitaleaccentuăm faptul că formele normale disjunctive, FND, sau formele disjunctive, FD,(sumă de produse) pot fi modelate pe dou ă nivele logice AND-OR. De asemenea,formele normale conjunctive, FNC, sau formele conjunctive, FC, (produse de sume)pot fi modelate pe două nivele logice OR-AND. Aceste afirmaţii sunt adevărate ı̂nmod teoretic când operatorii AND, OR se aplică pentru orice număr de intrări şiexistă disponibile şi variabilele negate. În practică, unde un operator este o poartălogică, trebuie luate cu precauţie aceste afirmaţii ı̂n funcţie de porţile disponibile şide numărul de intrări ale acestora (adică de restricţiile electrice de conectivitate aleacestor porţi).

1.2 POARTA LOGICĂ

Când se trece de la formele FND, FNC la FD, FC şi de la modelele acestorape bază de operatori NOT, AND, OR, NOR, NAND, la implement ări reale pe bazăde circuite electronice pentru operatorii logici se foloseşte, ı̂n exprimare, termenulde poartă logică. Prin termenul de poartă logică se face referire la orice circuitelectronic care implementează un operator logic, deci există poarta inversor (NOT),poarta AND, poarta OR, poartă XOR, poarta NAND etc. Prin referirea tuturor cir-cuitelor logice cu termenul de poartă logică apare un abuz de limbaj care, totuşi, areo justificare din punct de vedere al transferului semnalului (variabile logice binare)prin circuit. Considerând operatorii logici prezentaţi ı̂n Tabelul 1.7 , cu cele douăintrări A,C şi ieşirea f , se poate analiza cum pentru transferul semnalului logic Aspre ieşirea f , prin condiţionarea de către semnalul C (de control), circuitul elec-tronic care implementează un astfel de operator are un comportament similar cuutilizarea/funcţionarea unei porţi. Astfel, când circuitul poartă este “deschis,, lasăsemnalul A să treacă modificat sau nemodificat spre ieşirea f , iar când poarta este“ı̂nchisă

,,semnalul A nu se transferă la ieşirea f . Intuitiv, ı̂n această analogie, poarta

este ı̂nchisă sau deschisă de către cineva, adică ı̂n cazul unui circuit de un semnal decontrol, variabila C .

De exemplu, pentru poarta AND când este deschisă, C = 1, semnalul de intrare Ase transferă la ieşire f = A, iar când este ı̂nchisă, C = 0, semnalul de intrare A nu setransferă la ieşire, f este ı̂ncontinuu la valoarea logică 0. Poarta XOR, este puţin maispecială, este permanent deschisă, transferă la ieşire semnalul de intrare nemodificatpentru C = 0, f = A (A ⊕ 0 = A), iar pentru C = 1 transferă spre ieşire intrarea Anegată, f = A (A ⊕ 1 = A); poarta XOR are o funcţionare de circuit inversorcomandat. O astfel de interpretare, de circuit poartă, se poate găsi pentru oricare

din operatorii prezentaţi ı̂n Tabelul 1.7 .Analizând ı̂n paralel poarta AND şi poarta OR se poate observa că poarta ANDeste deschisă pentru C = 1 iar poarta OR este deschisă pentru C = 0, astfel spunemcă una este deschisă când semnalul C este activat ı̂n 1 logic iar cealaltă când semnalulC este activat ı̂n 0 logic. Până acum ataşam valorii de adevăr, pentru o variabilă,


32/612

32 1.2. POARTA LOGIC ˘ A

Tabelul 1.7 Interpretarea operatorilor logici ca circuite poartă

AND

C

f A f A

C

OR

A

C

f

XOR

A

C

f

NOR

f A

C

NANDf

NXOR

A

C

INTRARI

C A

Pentruvariabilade control :

0

10

0

01

1 1

0

0

0

1

0

1

1

1

1

1

1

0

1

0

0

0

0

0

1

1

1

1

0

0

este :Iesirea f = 0 f = A f = 1 f = A f = 1 f = A f = A f = A f = A f = A f = Af = 0

C = 0 C = 1 C = 0C = 1C = 0 C = 1C = 1C = 0 C = 0 C = 1 C = 0 C = 1

valoarea binară 1 şi pentru valoarea de fals valoarea binară 0. Dar, ı̂n practică, sepoate ataşa pentru starea de adevăr a unei variabile acea valoare binară pe carevariabila o are ı̂n starea activă (adică starea care produce acţiunea pentru care se

justifică acea variabilă), care poate fi: fie bitul 1, fie bitul 0. Iar valoarea de falsvariabila o are ı̂n starea de neactivare, care poate fi: fie pentru valoarea binară 1,fie pentru valoarea binară 0.

În această interpretare, variabila A când este ı̂n stare activă pentru valoarea bi-nară 1 (activ High) se notează ı̂n felul următor A H şi ĉand este ı̂n starea activăpentru valoarea binară 0

ZElectronica Digitala de Gheorghe TOACSE 613 Pag (CEL)

Documents

Transcript of ZElectronica Digitala de Gheorghe TOACSE 613 Pag (CEL)