universitatea ioan slavici de curs_proiectare... · web viewun minterm este constituit prin...

Universitatea Ioan SlaviciProiectare logica

Notite de cursPROIECTARE LOGICA

1.DESCRIEREA SEMNALELOR

În calculatoare orice entitate logică este reprezentată printr-un semnal. Există , în general semnale analogice şi semnale digitale. Semnalele analogice pot lua o infinitate de valori dintr-un interval precizat. Semnalele digitale pot lua doar doua valori dintr-un interval de tensiuni. Dacă se consideră intervalul de tensiuni cuprins între 0V şi +5V, semnalele digitale vor lua doar două valori. Prima situată undeva în apropierea valorii maxime, +5V, iar cealaltă în apropierea valorii 0V. Un semnal analogic din acelaşi interval de tensiuni poate avea orice valoare din interval

Termenul digital caracterizează, în genere, datele dintr-o mulţime. Se spune ca o mulțime de date este digitala daca ea conține un număr finit de elemente. Exemple de date digitale sunt mulțimile {0,1}, {pornit,oprit}, {rosu, albastru, verde} si {x: x este cifra zecimala}. In fiecare din aceste exemple, mulțimea de date este digitala – din moment ce numărul de elemente conținute este finit.

Mulțimea de date este analogă daca este formata dintr-un interval continuu de elemente. Astfel, mulțimea de date conține un număr infinit de elemente, având in vedere faptul ca intervalele continue cuprind o infinitate de elemente. Exemple de date analog sunt multimea numerelor reale, multimea tuturor culorilor si multimea numerelor reale intre 0 si 10.

De multe ori se aproximează datele in format analog prin conversia in digital. De exemplu, timpul este analog. Cand se comunică ora exacta, se spune ora si minutul. Un exemplu este afisajul orei pe ecranul calculatorului.

CodareaSe observa ca multimea datelor introduse în calculator de la tastatura este digitala deoarece este

compusa dintr-un numar finit de elemente.Calculatorul proceseaza date in format binar (compuse din 0 si 1), astfel ca trebuie urmati cativa pasi:

1. Datele introduse la tastatura sunt codate in secvente de biti unde literelor, cifrelor si altor simboluri li se asociaza un cod binar – cuvant cod. Codarea este o mapare care ataseaza fiecarui obiect dintr-o multime un unic element (cuvant cod) dintr-o alta multime. In acest caz, multimea de obiecte este multimea de date introduse de la tastatura. Vom vrea sa asociem o secventa de cod binar tuturor datelor introduse de la tastatura

2. Al doilea pas in acest proces este executarea de catre calculator a sarcinii dorite. Aceasta are loc in unitatea centrale de procesare (UCP), care include circuite electrice speciale ce realizeaza sarcinile.

Figura 1. Cei trei pași – codare, procesare si decodare

3. Ultimul pas este conversia rezulatului binar inapoi in format inteligibil de catre utilizator, de exemplu in cifre digitale si litere din alfabet. Aceasta etapa este numita decodare si este inversul codarii. Figura 1 ilustrează acești 3 pasi.

In continuare vom discuta detaliile celor trei pasi. Din moment ce calculatoarele proceseaza date binare, acesta va fi punctul de pornire.

Sistemul Numeric PoziționalIn sistemele numerice pozitionale, un numar N este caracterizat printr-o baza, b, numita si

radacina, si coeficienti (0, 1, ..., (b-1)), care alcatuiesc numarul. In multimea numerelor zecimale (baza

1


10), baza este implicita si poate fi omisa. Cand sunt luate in calcul alte baze, acestea trebuie specificate explicit in reprezentarea ca (N)b, sau Nb, unde b este baza.

De exemplu, in baza 10 coeficientii lui N sunt 0, 1, ...,9. Similar, in baza 5 coeficientii unui numar sunt 0, 1, 2, 3 si 4, iar pentru baza 16 avem cifrele zecimale de la 0 la 9, la care se adauga literele alfabetului A, B, C, D, E si F, reprezentant numerele zecimale 10,11, 12, 13, 14 respectiv 15. Simbolurile sunt folosite pentru ca baza numarului depaseste baza 10. Primele 6 litere ale alfabetului sunt folosite de in completarea celor 10 cifre digitale. Consideram doua formate, numerele cu punct radacina baza si numerele fara punct radacina.

Numere întregiPentru un numar dat (N)b = ni n(i-1)...n0 intr-o anumita baza b, scrierea polinomiala desfasurata

este:

(N)b=ni ×bi+n(i-1) ×b(i-1)+ n(i-2) ×b(i-2)+...+ n0 ×b0

Exemplul 1:1. Scrierea numărului zecimal 1023 in forma desfasurata, ca mai sus.2. Stabilirea valorile in baza 10 ale numerelor:

i. (1023)5ii. (10111)2

iii. (23AF)16

Solutia primei parti: Numarul este compus din 4 cifre cu b=10 si i=3. Astfel, folosind ecuatia de mai sus, avem n3 = 1, n2 = 0, n1 = 2 si n0 = 3. Numarul desfasurat este obtinut prin inlocuirea acestor valori pentru a obtine (1023)10 = 1 ×103 + 0 ×102 + 2 ×101 + 3 ×100

Solutia celei de-a doua parti:1. Aici avem i=3 si b=5. Rezulta

(1023)5 = 1 ×53 + 0 ×52 + 2 ×51 + 3 ×50

= 125 + 0 + 10 +3 = (138)10

2. (10111)2 = 1 ×24 + 0 ×23 + 1 ×22 + 1 ×20

= 16 + 0 + 4 + 2 + 1 = (23)10

3. (23AF)16 = (2 ×163)+ (3 ×162) + (A ×161) + (F ×160)= (2 ×163)+ (3 ×162) + (10 ×161) + (15 ×160)= 8192 + 768 + 160 + 15= (9135)10

Numere cu parte întreagă şi fracţionară

Un numar, (N)b, cu parte întreagă şi fracţionară este reprezentat astfel

(N)b = (ni n(i-1)... n0 . n-1 n-2... n-m)b

cu doua parti: (1) partea întreaga ni n(i-1)... n0 si (2) partea fractionara n-1 n-2... n-m. Indicii corespund localizarii unei anumite cifre in raport cu baza. Indicii părții întregi incep cu 0, intimp ce ai partii fractionare pornesc de la -1. Pentru baza 10, punctul este numit virgulă (punct) zecimal. Pentru baza 2, punctul mai este numit si punct binar.

2


Pentru un numar dat intr -o baza oarecare, b, echivalentul in zecimal este obtinut prin insumarea tuturor cifrelor numarului, inmultind pe fiecare cu bi, unde i este pozitia cifrei.

Exemplul 2:Să se gasească echivalentul zecimal pentru:

1. (1023.21)5

2. (10111.01)2

Solutie: Folosind metoda ştiută, se obține

(1023.21)5 = 1 ×53 + 0 ×52 + 2 ×51 + 3 ×50 + 2 ×5-1 + 1 ×5-2

= 125 + 0 +10 + 3 + 2/5 + 1/25= (138.44)10

Pentru partea a 2-a, se obţine

(10111.01)2 = 1 ×24 + 0 ×23 + 1 ×22 + 1 ×20 + 0 ×2-1 + 1 ×2-2

= 16 + 0 + 4 + 2 + 1 + 0 + 1/4= (23.25)10

Bazele cele mai uzuale in proiectarea digitala si in programarea in limbaj masina sunt baza 2 (numere binare), baza 8 si baza 16 (numere hexazecimale). Vom discuta in continuare procesul conversiei intre aceste trei baze.

Bazele 8 si 16Bazele 8 si 16 sunt folosite pentru a înlesni comunicarea dintre utilizator si calculator. Calculatoarele proceseaza informatia binara. Pe langa date, programele care dau comenzi calculatorului sunt de asemenea reprezentate in format binar. Atât lungimea mare, cât mai ales gradul mare de similitudine dintre două șiruri binare fac imposibila diferentierea acestora. Astfel, este dificil de distins intre două instructiuni diferite cand sunt in formatul binar. Introducerea bazelor 8 si 16 (hexazecimala) au simplificat acest proces. Conversia intre aceste trei baze este abordata in continuare.

Cifrele unui numar binar sunt numite biti. Un numar cu n biti este un numar binar care contine n biti. Cifra cea mai semnificativa este cea mai din stanga (pentru numerele binare, este numita bitul cel mai semnificativ). Similar, cifra cea mai putin semnificativa este cea mai din dreapta (in cazul numerelor binare este numita bitul cel mai putin semnificativ).

Pentru a converti un numar binar in baza 8:

1. Grupam numerele binare in seturi a cate 3 biti. Punctul de referința este punctul binar.Pentru partea intreaga, ne mutam de la punctul binar spre stanga; pentru cea fractionara pornim spre dreapta.

2. Daca este nevoie, adaugam zerouri la stanga partii intregi si la dreapta partii fractionare, pentru a forma grupuri a cate 3 biti.

3. Inlocuim fiecare grup format la punctele 1 si 2 cu echivalentul sau in baza 8.

Trebuie notat faptul ca adaugarea de zerouri la stanga partii intregi si/sau la dreapta celei fractionare nu schimba valoarea numarului initial.

Pentru a converti un numar binar in hexazecimal vom folosi procedura listata mai sus; totusi, biti sunt grupati cate 4.

Pentru a realiza punctul 3 de mai sus, vom folosi tabelul 1.4.1(a) si (b). Urmatoarele exemple ilustreaza folosirea procedurii subliniate mai sus.

3


Exemplul 3:Convertiti numarul binar 11010110.00111 in baza 8.Cand grupam cifrele binare cate 3, se observa ca avem nevoie sa adaugam un zero in partea stanga a partii intregi si unul partea drepata a partii zecimale. Numarul modificat, gruparea si echivalentul in baza 8 sunt date in figura 1.4.1.

Exemplul 4:Convertiti numarul binar 111000110.001 in hexazecimal.Similar, in gruparea cifrelor binare in grupe de cate 4, se observa ca avem nevoie sa adaugam trei zerouri la stanga partii intregi si un zero in dreapta partii fractionare.

Numarul modificat, gruparea si echivalentul hexazecimal sunt date in figura 1.4.2.

Inainte de a incheia aceasta sectiune va amintim ca procesul descris in diagramele de mai sus este reversibil, adica find dat un numar in forma octala sau hexazecimala, forma numarului in baza 2 poate fi gasita prin asocierea fiecarui grup secventa de biti necesara. Mai mult, trecerea de la baza 8 la baza 16 si invers poate fi facuta prin convertirea numarului in binar si apoi efectuand conversia din binar in celalalt format (ca in fig 1.4.1 sau 1.4.2).

4


Exemplul 5:

Dat find numarul octal (127.25)8, gasiti echivalentul sau hexazecimal.Solutie: Prima data convertim numarul in binar. Bitii numerelor binare echivalente sunt apoi regrupati in grupe de cate 4 si numarul hexazecimal corespunzator este gasit.

Tipuri de operanzi si mulțimile de definiție

Vom începe acest paragraf prin considerarea tipurilor de date folosite in limbajele de programare si matematica.

Tabelul 1.5.1

Tipuri de dateTipuri de date din calculator Echivalente matematice ExempleFara semn Numere naturale 0 , 5 , 7Cu semn Numere intregi -5 , 0 , 1 , 6Virgula fixa Numere rationale 1.2 , 1.5Virgula mobila Numere rationale -2.1x105

Caracter - ‚A’

Tipuri de date

In matematica numerele sunt grupate in functie de setul lor de valori posibile. In particular, aceasta aranjare include seturile de numere naturale, numere intregi, numere rationale, numere reale si numere complexe,multimi care sunt pastrate si in reprezentarea numerelor in calculator. Acest lucru este implementat intr-un limbaj de programare, spre exemplu: in partea de declarare a variabilelor, care este extrem de importanta. Reprezentarea numerelor in calculator e exemplificata in tabelul 1.5.1In aritmetica unui calculator, cu exceptia ultimului rand, se lucreaza cu titpurile de date din coloana 1 a tabelului 1.5.1. Numerele fara semn sunt defapt intregi nenegativi (numerele nu sunt asociate cu un semn); numerele cu semn reprezinta numere intregi cu sau far semn. Cele doua reprezentari ramase sunt folosite pentru a aproxima numerele reale. Reprezentarile in virgula fixa conti intregi cu sau fara semn cu un punct care separa 2 parti : partea intreaga si partea fractionala. Reprezentarea in virgula mobila este conpusa tot din doua parti : o parte fixa cu punct si un exponent. De exemplu, -2.1x105 contine 2 parti: -2.1 este partea fixa cu punct si 105 este exponentul. Vom vorbi mai multe despre aceste reprezentari in capitolele ce urmeaza.

Limite finiteIn matematica se folosesc multimi cu cardinalul infinit (cardinalul unei multimi este numarul de elemente a multimii). Calculatoarele contin insa, elemente de stocare finite. Ca o urmare a acestui fapt, calculatoarele proceseaza doar submultimi ale acesto multimi finite. Cand se efectueaza operatii aritmetice cu opernazi (numere), acestia sunt stocati in registrii cu un numar finit de elemente de stocare. Un registru e caracterizat de numarul de biti pe care il contine. Un registru n-bit contine n elemente de stocare, fiecare putand retine un singur bit dintr- un total de n biti. Numarul finit de biti micsoreaza limitele multimilor de numere care pot fi stocate in registrii.

5


In continuare ne vom referi in discutia noastra la kilometrajul unei masini care retine cifre zecimale. Numarul de cifre din aparatul de kilometraj este finit:

Figura 1.5.1 Numararea in baze diferite

Ca urmare, multimea de numere care poate fi stocata (inregistrata) este deasemenea finita. Pentru un aparat de kilometraj cu 5 cifre zecimale, multimea numerelor care pot fi inregistrate este de la cel mai mic 00000 pana la cel mai mare 99999=105-1. Aceasta inseamna un total de 105 numere. Numerele stocate sunt fara semn. Analog kilometrajelor, numerele in calculatoare sunt stocate in registrii de dimensiune finita.

Vom asemana limitele multimilor de numere in baze diferite cu procesul de a numara in baza 10. De aici putem deduce ecuatii pentru cel mai mic sic el mai mare numar intr-o baza data.

La numarare, intotdeauna ultima cifra cea mai nesemnificativa se schimba. Aceasta cifra este incrementata pana ajunge la valorea ei maxima (9 in cazul bazei 10). De aici rezulta ca valoarea maxima este egala cu b-1 unde b este o baza oarecare . Urmatoarea numarare face ca cea mai nesemnificativa cifra sa devina 0. Cifra urmatoare insa, se schimba si ea. In general, pentru ca o anumita cifra sa se schimbe (sa fie incrementata sau sa devina resetata la 0), toate cifrele predecesoare trebuie sa aibe valoarea maxima b-1. In baza 10, toate cifrele predecesoare trebuie sa fie de valoare 9. In baza 2, aceasta se intampla cand toate cifrele precedente au valoarea 2-1=1 ca in figura 1.5.1 b) randurile 2 si 3. In hexazecimal, acest lucru se intampla cand toate cifrele zecimale predecesoare au valoarea F, ca in figura 1.5.1 c), randurile 3 si 4.

In figura 1.5.1 a) intervalul valorilor care pot fi stocate este de la 0 la 99999 (105-1) din moment ce numarul de cifre folosite este 5. Inregistrand valori in afara acestui interval cauzeaza o eroare numita ‚overflow’ daca numarul e peste 99999 sau ‚underflow’ daca numarul e sub 0.

In caz general, cel mai mare numar fara semn pe care il putem stoca intr-un registru n-bit care stocheaza cifre in baza b este bn-1. Pentru a numara in baza 2 folosind un registru n-bit, cel mai mare intreg fara semn care poate fi stocat este 2n-1. De exemplu, pentru registrii de 3-, 4-, si 5- biti, se pot inregistra intregi binari fara semn intre (000)2 si (111)2=7, (0000)2 si (1111)2=15, respectiv (00000)2 si (11111)2=31.

Intervalul numerelor se schimba daca numarul care este stocat in format virgula mobila. Pentru acest format trebuie sa includem si locatia virgulei care este de obicei la extremitatea dreapta a registrului (pentru numere intregi) sau la extremitatea stanga a registrului (pentru numere fractionale). Daca continutul unui registru n -bit reprezinta o fractie, atunci cel mai mic numar este zero (toti bitii sunt zero) si cel mai mare numar este:

(a-1a-2a-3a-4...a-m)2=(.1111...1)2 ,unde cifra 1 apare de m ori =2-1+2-2+2-3+...+2-m

=2-m(2-m-1+2m-2+2m-3+...+20)

6


=(2m-1)/ 2m

=1-2 -m

Din acest motiv, numarul de 3 biti (111)2 poate fi interpretat ca un decimal fara semn(7) sau un fractional (7/8).

Inainte de a trece la sectiunea urmatoare, vom lista cele mai utilizate unitati de calcul binar: 1 K (kilo)=210=1024 (aproximativ 1000); 1M (mega)=220; 1G (giga)=230. Marimea unui registru poate fi data in octeti (1 octet=8 biti). De aici, un registru de 4 octeti are 32 de biti. Deasemenea, marimea unui registru este deseori numita un cuvant. Rezulta ca un registru de 32 biti are marimea unui cuvant de 32 de biti. Cel mai mare intreg fara semn care poate fi stocat in acest registru este de 232-1 care este de aproximativ 4 G.

Conversia numerelor decimale in numere echivalente din baze arbitrare

Dat fiind numarul decimal (N)10=(nin(i-1)...n0.n-1n-2...n-m)10; pentru a gasi echivalentul sau intr-o baza diferita, folosim doua metode aplicate partii intregi si fractionale ale lui N.

Conversia partii intregi

Procesul de conversie a unui numar decimal fara parte fractionara intr-un numar echivalent intr-o baza oarecare b, este dat in algoritmul 1.

Algoritmul 1: Dat fiind un numar in baza 10, N, fara parte fractionala, echivalentul sau intr-o baza oarecare b poate fi obtinut prin impartiri repetate a numarului original si a tuturor caturilor rezultate prin baza b. Resturile sunt salvate in ordinea in care sunt formate. Procesul se termina cand ultimul cat obtinut este 0. Numarul echivalent (in baza b) este obtinut prin listarea resturilor de la cea mai putin semnificativa cifra pana la cea mai semnificativa cifra in ordinea in care au fost formate resturile.

TABELUL 1.6.1

Conversia din baza 10 intr-o baza arbitrara

Resturile ri Numarul inintial (N) si caturile succesive(qi)

N=138r0=3 q0=27r1=2 q1=5r2=0 q2=1r3=1 q3=0

Exemplul de mai jos ilustreaza metoda evidentiata mai sus.

7


Exemplul 6:Convertiti numarul (138)10 in echivalentul sau in baza 5.Aplicam procedura descrisa mai devreme, la fel ca in tabelul 1.6.1 . In acest exemplu, numarul initial 138 este afisat in partea dreapta sus a tabelului. Restul diviziunii a lui 138 cu 5 este r0=3. Catul (q0) este 27 ca in tabel. Randul 3 al tabelului este obtinut prin repetarea procesului de impartire, insa de aceasta data prin folosirea catului 27 in loc de numarul initial. In final, ultimul rand se obtine prin impartirea catului 1 (q2=1) la 5, salvandu-se restul corespunzator si catul in acest rand. Cum noul cat este 0, procesul de conversie se opreste. Resturile obtinute (scrise in ordinea formarii de la dreapta la stanga) constituie numarul echivalent in baza 5, adica : (138)10=(1023)5

Exemplul 7:Convertiti numarul 23 (in baza 10) intr-un numar echivalent in baza 2. Folosind procedura evidentiata in algoritmul 1, obtinem rezultatele afisate in figura 1.6.1.

Reprezentarea binara a numarului 23 este : (23)10=(10111)2

8


Conversia părții fracționare

Procesul de conversie a partii fractionare a unui numar in baza 10 intr-un numar echivalent intr-o baza arbitrara b este dat in algoritmul 2.

Algoritmul 2: Se inmulteste in mod repetat partea fractionala si toate fractiile generate ulterior cu baza b, rezultatele intregi din fiecare multiplicare fiind salvate in ordinea formarii. Se continua pana partea fractionala este 0. Echivalentul fractional in baza b se obtine scriind cifrele intregi (in ordinea formata) de la cea mai semnificativa (in stanga) la cea mai putin semnificativa (in dreapta), apoi adaugandu-se punctul in partea stanga a numarului.

Exemplul de mai jos ilustreaza folosirea algoritmului 2.

Exemplul 8:Convertiți fracția zecimala 0.25 in fractia echivalenta in baza 2.

Aplicand algoritmul 2, obtinem rezultatele din figura 1.6.2. Fractia initiala 0.25 este scrisa in randul 1. Randul 2 contine 2 coloane, coloanele combinate sunt rezultatul operatiei 2*(2.5). Multiplicand fractia 5 din randul 2 cu numarul 2, obtinem rezultatul afisat in randul 3. Cum fractia noua este 0 algoritmul se termina aici.

Numarul fractional echivalent in baza 2 este obtinut prin scrierea partilor intregi de la stanga la dreapta in ordinea in care au fost formate si adaugand virgula la stanga numarului. Relulta ca: (0.25)2=(0.01)2

Exemplul 9:Convertiti fractia zecimala (0.44)10 intr-o fractie echivalenta in baza 5.

Urmand procedura descrisa in algoritmul 2, obtinem rezultatele din figura 1.6.3. Obtinem (0.44)10=(0.21)5

Exemplu 10:Transformam (0.7)10 intr-o fractie binara echivalenta.

Figura 1.6.4 arata procesul de conversie. Dupa cum s-a stabilit mai devreme, rezultatul din linia 3 (0.8) este obtinut prin inmultirea partii fractionare din linia precedenta (0.4) cu 2. Ultima linie are partea fractionara 0.4. Ca urmare, inmultind repetat cu 2, secventa de cifre obtinute este (0110). Aceasta secventa este repetata la infinit, deoarece criteriu de oprire al algoritmului (partea fractionara sa fie 0) nu poate fi satisfacut.

Exemplul anterior ne arata un lucru interesant despre conversia numerelor: anumite numere sunt memorata in calculator intr-o reprezentare aproximativa si nu exacta. (In matematica, ecuatia x*1/x=1 este tot timpul adevarata, cand x diferit de 0. Nu acelasi lucru se intampla cand testam conditia in limbajele de programare.)

9


Pentru a transforma un numar zecimal cu virgula fixa intr-un numar echivalent intr-o baza arbitrara, aplicam algoritmul asupra partii intregi si partii fractionare, dupa care combinam rezultatele.

Exemplu 11:Transformam (138.44)10 într-un număr echivalent în baza 5.

Din exemplele anterioare, avem ca (138)10 = (1023)5, si (0.44)10 = (0.21)5. Combinând rezultatele, avem (138.44)10 = (1023.21)5

2.FUNDAMENTELE MATEMATICE ALE PROIECTĂRII LOGICE

În anul 1854 apare la New York, în editura Dover Publication, lucrarea An Investigation of the Laws of Thought a matematicianului şi logicianului englez George Boole. Această lucrare conţine introducerea unei algebre (o structură algebrică) intenţionată să descrie relaţiile logice complexe ale limbajului natural.Focalizarea acestei lucrări asupra limbajului natural şi relaţiilor logice complexe ale acestuia este deosebit de importantă dacă se priveşte această abordare prin prisma translatării unei descrieri, în limbaj natural, a funcţionării unui circuit (bloc funcţional) oarecare, într-o descriere riguroasă, ne-ambiguă şi echivalentă funcţional acesteia.În linii mari activitatea de proiectare actuală în domeniul circuitelor digitale este compusă, între altele, dintr-o translatare de acest fel. Termenii au evoluat în complexitate dar ideea este, în principiu, aceeaşi.

Exemplul 1. Se consideră următoarea descriere verbală a unui bloc simplu de comandă al uşii unei săli:

3. uşa este deschisă atâta timp cât există în imediata sa proximitate (aproximativ 50 cm de-o parte şi de alta a uşii) o persoană şi rămâne deschisă pentru un interval, relativ scurt, de timp t chiar şi după plecarea oricărei persoane din zona de proximitate.

Se doreşte o scriere concisă exactă, în termenii algebrei comutatorilor, a acestei descrieri (făcută în termenii limbajului natural) a funcţionării uşii.Fiecare element relevant din descrierea în limbaj natural va fi notat printr-o variabilă care poate lua doar două valori 0 şi 1.Uşa este deschisă. Se notează prin variabila U. Câtă vreme uşa este deschisă, U = 1, iar când uşa este închisă U = 0. Închiderea şi deschiderea uşii are loc în urma unei acţionări, printr-un motor electric – de exemplu.Există o persoană în zona de proximitate. Determinarea unei persoane în zona de proximitate se poate realiza printr-un senzor cu traductor inductiv, fotoelectric etc. Prezenţa unei persoane în zona de proximitate se notează prin variabila P. Ori de câte ori este o persoana în apropierea uşii P = 1, altfel P = 0.Temporizatorul este activ pentru durata prestabilită t. Se notează prin T. Atunci când temporizatorul este activ T = 1, altfel T = 0. Temporizatorul este activat de îndată ce este sesizată o persoană în zona de proximitate. Activarea temporizatorului se mai numeşte şi startarea acestuia.Prezenţa unei persoane în zona de proximitate face ca uşa să se deschidă, pe de-o parte şi activează temporizatorul, pe de-altă parte. Apariţia unei persoane, în zona de proximitate, pe durata temporizării are ca efect numai reactivarea temporizării, uşa fiind deja deschisă.Se poate deduce uşor că translatarea descrierii iniţiale poate fi făcută succint astfel:

U = SAU(P,T).Sintetic funcţionarea uşii poate fi exprimată, utilizând expresia anterioar ă cu blocul funcţional SAU, astfel: uşa este deschisă dacă este sesizată, în apropiere, o persoană sau este activ temporizatorul.Limbajul natural are, spre deosebire de cel matematic, un anumit grad de ambiguitate. Enumerări de forma „Marcajul poate fi alb şi roşu sau galben”, nu au o întotdeauna precedenţă bine stabilită a operatorilor fundamentali. Operatorii fundamentali au particularităţi care pot depinde de context, în limbajul natural. Astfel, se consideră fraza „Colegul meu este îmbrăcat cu o jachetă roşie sau cu un sacou verde”, spre exemplu. Aceastǎ fraz ǎ are două dependenţe în raport cu care este adevărată. Este adevărată atunci când colegul poartă o jachetă roşie sau când poartă un sacou verde dar, ambele situaţii nu pot fi simultan satisfăcute, evident. Deosebirile dintre limbajul

10


natural şi cel matematic fac din procesul de translatare al acestora, în proiectarea sistemelor şi circuitelor digitale, o activitate solicitantă.

Modul cel mai uzitat de introducere al algebrei Booleene face apel la setul de postulate introdus de Huntington în anul 1904. Primul postulat poate fi considerat ca stabilind sistemul aflat în studiu.4. Există o mulţime K de obiecte sau elemente, satisfăcând o relaţie de echivalenţă notată prin „=”, îndeplinind principiul substituţiei.

Prin substituţie se înţelege că relaţia a = b între elementele a şi b implicǎ faptul cǎ elementul a poate fi substituit prin elementul b în orice expresie care conţine elementul a fără să fie afectată validitatea expresiei respective.

IIa. Este definită o lege de compoziţie „+” astfel încât expresia a + b este în K, ∀ a, b∈K.IIb. Este definită o lege de compoziţie „*” astfel încât expresia a * b (abreviat ab) este înK, ∀ a, b∈ K.IIIa. Există un element 0∈ K, astfel încât a + 0 = a, ∀ a∈ K.IIIb. Există un element 1∈ K, astfel încât a * 1 = a, ∀ a∈ K.IVa. a + b = b + a, comutativitatea legii +.IVb. a * b = b * a, comutativitatea legii *.Va. a + (b * c) = (a + b) * (a + c), distributivitatea + faţă de *.Vb. a * (b + c) = (a * b) + (a * c), distributivitatea * faţă de +.VI. ∀a∈ K, ∃ a’∈ K, astfel încâta * a’ = 0, şia + a’ = 1.∃ x,y ∈ K, astfel încât x ≠ y.Se poate remarca faptul că nu s-a precizat nimic în legătură cu numărul sau tipul elementelor care alcătuiesc mulţ imea K. Exist ă mai multe mulţimi care satisfac aceste postulate. Câteva dintre acestea vor fi exemplificate în continuare.Pentru ca un set de postulate să fie valid acesta trebuie să fie consistent. Consistenţa revine la demonstrarea faptului că nici unul dintre postulate nu contrazice oricare dintre celelalte postulate din setul considerat. Verificarea consistenţei se poate face prin examinarea fiecărui postulat, pentru a demonstra că nici un postulat nu contravine oricărui grup posibil de postulate, dar abordarea este extrem de laborioasă. Există, însă, o alte cale mult mai simplă, pentru verificarea consistenţei. Pentru aceasta este necesar să se găsească doar un singur exemplu de algebr ă booleană despre care se ştie, în mod independent, că este consistentă. Dacă o astfel de structură algebrică satisface toate postulatele lui Huntington, atunci postulatele (în sine) sunt consistente.

Cea mai simplă algebră booleană constă din numai două elemente, notate prin 1 şi 0, definite că satisfac:

1’ = 0, 0’ = 10 + 0 = 0 * 0 = 1 * 0 = 0 * 1 = 0.

Se remarcă faptul că postulatele I, II, III şi VII sunt satisfăcute prin definiţ ie. Satisfacerea legilor de comutativitate (IVa şi IVb) este evidentă iar verificarea legilor de distributivitate (Va şi Vb) necesit ă doar alcătuirea listelor de valori de-o parte şi de alta a ecuaţiilor, pentru toate combinaţiile de valori ale variabilelor a, b şi c. Postulatul VI este imediat verificabil atribuind valori (0 şi 1) variabilei a.

11


3. altă cerinţă importantă este independenţa postulatelor. Aceasta revine la verificarea faptului că nici unul dintre postulate nu poate fi dedus din celelalte. Postulatele, aşa cum au fost exprimate sunt independente. Această verificare este mult mai complexă, si nu este esenţială pentru scopul acestei abordǎri. Pe de altă parte, nu este necesară abordarea algebrelor Boole-ene printr-un set independent de axiome. Există multe abordări ale subiectului care includ între axiome anumite teoreme, din raţiuni de simplificare a modului de prezentare.

Se poate trage o primă concluzie pe marginea aparatului formal introdus.O algebră Booleană se defineş te, în general, peste o mulţime K ⊇ B ≡ {0,1} înzestrată cu două operaţii, notate aditiv + şi respectiv multiplicativ *, care satisfac legile de comutativitate şi distributivitate. Mulţimea B conţine întotdeauna cele două elemente notate 0 şi 1. Acestea sunt elementele neutre ale operatorului aditiv şi, respectiv, multiplicativ:

a* 1 = a, a + 0 = a ,∀a∈B.În fine, oricare element a din B are un complement, notat în cele ce urmează prin a’. Relaţiile importante dintre un element şi complementul său sunt enunţate astfel:

a * a’ = 0 şi a + a’ = 1, ∀a∈B.

Este important, de reţinut, că ambele elemente ale mulţimii B nu trebuie privite ca fiind numere, sunt doar notate prin două numere. La fel de bine se pot utiliza alte două simboluri distincte, dar tradiţional se utilizează 0 şi 1.Aceste simboluri corespund, din punct de vedere tehnologic, unor stări distincte ale unor dispozitive fizice care implementează operatorii acestor algebre.

Se poate remarca cu u şurinţă faptul că algebra Booleană diferă, ca structură algebrică, de algebra obişnuită prin distributivitatea ambilor operatori, pe de-o parte, şi prin apariţia complementului, pe de-altă parte.

O privire mai atentă asupra postulatelor lui Huntington relevă faptul că anumite postulate sunt grupate în perechi iar fiecare postulat dintr-o pereche poate fi obţinut din celălalt postulat prin interschimbarea simbolurilor 0 şi 1, ca ş i a operatorilor + şi *. Astfel se poate remarca: a + 0 = a, prin interschimbarea amintită devine a * 1 = a, iariii. + (b * c) = (a + b) * (a + c) se transformă în a * (b + c) = (a * b) + (a * c).

Oricare teoremă care poate fi demonstrată în algebra booleană, are o teoremă duală care este, de asemenea, adevărată. Cu alte cuvinte, fiecare pas din demonstraţia unei teoreme poate fi înlocuit prin dualul acestuia, producând demonstraţia teoremei duale.Teoremele fundamentale ale algebrei Booleene

În continuare sunt enunţate principalele teoreme, cele care permit o manipulare convenabilă a algebrei Booleene. Unele dintre teoreme sun numite leme deoarece acestea au un rol mai limitat de aplicabilitate, furnizând relaţii utilizate în construcţia demonstraţiei unor rezultate cu grad ridicat de generalitate, teoremele.Atât lemele cât şi teoremele vor fi enunţate dar vor fi demonstrate numai o parte (cele mai semnificative) demonstraţiile celorlalte leme şi teoreme fiind lăsate ca exerciţii.

Lema 1Elementele 0 şi 1 sunt unice.

Demonstraţie: se presupune că există două elemente 0, notate prin 01 şi 02. În baza postulatului IIIa, pentru orice elemente w1 şi w2 din K au loc relaţiile:w1 + 01 = w1 şi w2 + 02 = w2.Acum fie w1 = 02 şi w2 = 01:

02 + 01 = 02 şi 01 + 02 = 01.

12


Utilizând comutativitatea operatorului + şi proprietatea de tranzitivitate a egalităţii, rezultă:01 = 02.Prin dualitate se poate demonstra şi unicitatea elementului 1.

Lema 2Pentru orice element w ∈ K au loc relaţiile:

w + w = w şiw * w = w.

Lema 3Pentru orice element w ∈ K au loc relaţiile:

w + 1 = 1 şiw * 0 = 0.

Lema 4Elementele 0 şi 1 sunt distincte iar 1’ = 0.

Lema 5Pentru orice elemente w1 şi w2 din K au loc relaţiile:w1 + w1w2 = w1, şiw1(w1 + w2) = w1.Lema 6Complementul unui element w ∈ K, w’, este unic.

Lema 7Pentru orice element w ∈ K, (w’)’ = w.

Lema 8Oricare ar fi elementele u, v şi w ∈ K, are loc relaţia:u * ( (u + v) + w) = ( (u + v) + w) * u.Teorema 1Oricare ar fi elementele u, v şi w ∈ K, au loc relaţiile:

3. + (v + w) = (u + v) + w, şi u * (v * w) = (u * v) * wTeorema 2

Pentru orice pereche de elemente u şi v ∈ K, se verifică relaţiile:u + u’v = u + v şiu(u’ + v) = uv.Teorema 3Următoarele două relaţii sunt adevărate oricare ar fi elementele u şi v ∈ K:(u + v)’ = u’ * v’ şi(u * v)’ = u’ + v’.

Există şi o defini ţie alternativă a algebrelor Booleene. Aceasta este utilizată, între altele, pentru construcţii ale algebrelor Booleene definite ca latice complementate distributive. Acest mod de construcţie leagă algebrele Booleene mai strâns de alte structuri matematice.

Definiţia alternativă este orientată spre o abordare prin teoria mulţimilor (se va vedea, în continuare, motivaţia). Dacă S este o mulţime de n elemente, atunci există n2 perechi de elemente (u,v) ∈ S2 (produsul cartezian S x S se notează prin S2).

Definiţia 1

13


O relaţie R definită peste S2 este o submulţime din S2, iar scrierea (u,v) ∈ R ⊆ S2 este echivalentă scrierii u R v.

Există două categorii de relaţii care sunt de un interes particular în acest context:= Relaţiile de echivalenţă, şi= Relaţiile de ordonare parţială.

Definiţia 2= relaţie de echivalenţă este reflexivă, simetrică şi tranzitivă. Reflexivitatea: u R u;

Simetria: daca u R v, atunci v R u.Tranzitivitatea: dacă u R v şi v R w, atunci u R w.

Introducerea relaţiei de ordine parţială conduce la o latice.

Definiţia 34. ordonare parţială ≤ peste S este o relaţie care satisface următoarele proprietăţi pentru oricare trei elemente u, v, w ∈ S:

Reflexivitatea: u ≤ u;Antisimetria: dacă u ≤ v şi v ≤ u atunci u = v;Tranzitivitatea: dacă u ≤ v şi v ≤ w, atunci u ≤ w.

Dacă P este o submulţime, a mulţimii parţial ordonate S, atunci elementul u din S este o margine superioară pentru P, dacă şi numai dacă p ≤ u, oricare ar fi p din P.În mod similar elementul v din S este o margine inferioară pentru P, dacă şi numai dacă v ≤ p, oricare ar fi p din P.Se notează prin U şi V mulţimea tuturor marginilor superioare, respectiv inferioare pentru P. Dacă um din U este o margine superioară cu proprietatea um ≤ u, oricare ar fi u din U, atunci se spune că um este cea mai mică margine superioară (cmmms) pentru P şi se notează prin

sup(P) . Similar se introduce cea mai mare margine inferioară (cmmmi) care se notează prin inf(P).

Definiţia 4O mulţime parţial ordonată în care fiecare element are atât o cea mai mare margine inferioară cât şi o cea mai mică margine superioară este o latice.

Prin inducţie completă se poate arăta că în orice latice S există un cel mai mic element notat prin 0, astfel încât 0 ≤ s pentru orice element s din S. În mod asemănător se arată existenţa unui cel mai mare element în S notat prin 1, cu proprietatea s ≤ 1, oricare ar fi elementul s din laticea S. Dacă elementele p ş i q sunt din laticea S atunci, se notează, pentru uşurinţa scrierii, prin p + q = sup(p, q), iar prin p * q = inf(p, q).

Teorema 4O latice complementată distributivă (o latice care satisface postulatele V şi VI ale lui Huntington) este o algebră Booleană.

Demonstraţie: Operatorii postulatului II au fost introduşi prin inf şi respectiv sup. Deoarece 0 este cel mai mic element atunci, sup(u, 0) = u + 0 = u, iar dacă 1 este cel mai mare element atunci, inf(u, 1) = u * 1 = u ceea ce demonstrează satisfacerea postulatului III. Cel mai mic element p * q = inf(p, q), şi respectiv cel mai mare element p + q = sup(p, q), nu depind de ordinea elementelor astfel încât sunt

14


satisfăcute şi legile postulatului IV. Deoarece postulatele V şi VI au fost incluse în ipoteză, rezultă că laticeaeste o algebră Booleană.

Astfel, se poate arăta că ∀ a, b ∈ B, ∃ z ∈ B astfel încât z = inf(a,b) = a∧b (se spune că z este marginea inferioară), şi ∀ a, b ∈ B, ∃ t ∈ B astfel încât t = sup(a,b) = a∨b (se spune că t este marginea superioară). Privitor la operatorii ∧ şi ∨ se poate arăta că amândoi distribuie unul în raport cu celălalt şi se poate, de asemenea, arăta că:

∀ x ∈ B, ∃ x’ ∈ B astfel încâtx ∨ x’ = 1, unde 1 este elementul maxim, iarx ∧ x’ = 0, unde 0 este elementul minim.

Proprietăţile algebrelor BooleeneSpre deosebire de postulate, proprietăţile sunt, în fapt, teoreme şi de aceea sunt demonstrabile.Metoda generală de demonstrare a acestor proprietăţi se bazează pe postulatele algebrelorBooleene utilizându-se mult inducţia matematică.

(I) Asociativitatea:a + (b + c) = (a + b) + c = a + b + c,a * (b* c) = (a * b) * c = a * b * c.(II) Idempotenţa:a + a = a,a * a = a.(III)a + 1 = 1,a * a = a.

a + (a * b) = a,a * (a + b) = a.

(V) Involuţia:(a’)’ = a

(VI) Legile De Morgan:(a + b)’ = a’ * b’,(a * b)’ = a’ + b’.(VII)a + a’ * b = a + b,a * (a’ + b) = a * b.

(VIII) Consensus:a * b + a’ * c + b * c = a * b + a’ * c ,(a + b) * (a’ + c) * (b + c) = (a + b) * (a’ + c) .

Exceptând proprietatea (V) Involuţia, se poate remarca o dublă reprezentare a fiecă rei proprietăţi (identităţi, în fapt) ale algebrelor Booleene. Această remarcă se concretizează în „principiul Dualităţii”, aşa cum este acesta formulat în definiţia următoare.

Principiul DualităţiiOrice identitate dintr-o algebră Booleană se transformă într-o altă identitate dacă au loc următoarele inter-schimbări:

15


Operatorii + şi *,Elementele 0 şi 1.

Exemplul 2: Identitatea a + 1 = 1, se transformă, prin aplicarea principiului dualităţii, înidentitatea: a * 0 = 0.□

O algebră Booleană se identifică, tradiţional, prin numele mulţimii suport, B. Există, în acest sens, următoarele exemple clasice:Algebra comutatorilor,Algebra submulţimilor unei mulţimi (numită şi algebra claselor), Algebra Booleană aritmetică,Algebra Booleană a funcţiilor Booleene.

Algebra comutatorilor este un sistem algebric care constă din mulţimea {0,1}, doi operatori binari, notaţi ŞI (*), respectiv SAU (+), şi un operator unar, notat NU (’), unde:

0 + 0 = 0, 0 * 0 = 0,0 + 1 = 1, 0 * 1 = 0, 0’ = 1,1 + 0 = 1, 1 * 0 = 0, 1’ = 0,1 + 1 = 1, 1 * 1 = 1.

Se remarcă faptul că, în conformitate cu definiţia dată, algebra comutatorilor poate fi enunţată astfel: ({0,1}, +, *, 0,1).Se poate verifica uşor validitatea postulatelor pentru această algebră Booleană.De reţinut că există o proprietate exclusivă a acestei algebre:a + b = 1 dacă şi numai dacă a = 1 ori b = 1,a * b = 0 dacă şi numai dacă a = 0 ori b = 0.

Algebra submulţimilor este un sistem algebric construit peste o mulţ ime nevidă S (S ≠ ∅) numită mulţimea univers, pentru care se consideră toate submulţimile distincte posibile ale acesteia. Dacă notăm prin |S| cardinalitatea mulţimii S, atunci mulţimea tuturor submulţimilor mulţimii S are 2|S| elemente.Această algebră are drept operator aditiv (+) reuniunea (∪), iar intersecţia (∩) este operatorul multiplicativ (*).

Cu alte cuvinte, se poate scrie: (K, +, *, 0, 1) = (2|S|, ∪, ∩, ∅, S), unde s-a notat mulţimea tuturor submulţimilor distincte ale mulţimii S prin 2|S| (notaţia tradiţională). Dacă S = {a, b} atunci K ={∅, {a}, {b}, {a, b}}. Verificarea postulatelor în acest caz este, de asemenea, simplă.

Remarcabil relativ la această algebră este de reţinut teorema Stone (de reprezentare):

Teorema de izomorfism (Stone)Orice algebră Booleană finită este izomorfă algebrei Booleene a submulţimilor unei anumite mulţimi finite S.

Algebra Booleană aritmetică se construieşte peste numerele naturale.Astfel, se consideră n numere prime distincte şi fie p produsul acestora. Se notează prin Dn mulţimea tuturor divizorilor acestui produs (p). Se folosesc notaţiile aritmetice consacrate, cmmdc şi cmmmc pentru cel mai mare divizor comun şi, respectiv, cel mai mic multiplu comun.Se notează prin 1, numărul întreg 1 şi va fi distinct de elementul 1 Boolean evidenţiat în definiţia algebrelor Booleene.

16


Atunci se poate scrie: (B, +, *, 0, 1) = (Dn, cmmmc, cmmdc, 1, p).

Dacă, spre exemplu, p = 2 x 3 x 5 = 30, atunci Dn = {1, 2, 3, 5, 6, 10, 15, 30}.Este interesant de remarcat că atunci când Dn este privită ca fiind alcătuită din produse de divizori primi netriviali, şi sunt utilizate în clar mulţimile acestor divizori, atunci se poate scrie o formulă apropiată, comparativ, celei realizate pentru algebra submulţimilor:Dn={∅,{2},{3},{5},{2,3},{2,5},{3,5},{2,3,5}}, deoarece 1 nu are nici un divizor netrivial.

Acum apare evident izomorfismul acestei algebre cu algebra submulţ imilor unei mulţimi, în cazul de faţă exemplificându-se – pentru raţiuni de simplitate - cu doar trei elemente distincte.

Algebra binară este construită peste mulţimea suport minimală B = {0,1} iar operaţiile binare + şi * sunt disjuncţia, respectiv, conjuncţia, adesea denumite sumă, respectiv, produs sau, încă, SAU, respectiv ŞI.Spaţiul multidimensional descris de variabilele cu valori binare este notat prin Bn. Acest spaţiu mai este referit prin cubul n-dimensional (hipercub) din cauza generalizării reprezentării spaţiului B3 care geometric descrie un cub peste triedrul natural.Un punct din Bn este reprezentat printr-un vector cu n ranguri binare. Atunci când sunt asociate variabile binare dimensiunilor spaţiului boolean Bn , un punct se poate identifica prin valorile corespunzătoare acestor variabile. Un literal este o valoare, o instanţiere, a unei variabile sau a complementului acesteia. Un produs de n literali reprezintă un punct dinspaţiul şi se spune că reprezintă un cub zero-dimensional. Se utilizează curent referirea unui produs de literali prin denumirea generică cub.

Algebra funcţiilor Booleene de n variabile este construită astfel:(Fn(B), +, *, 0, 1 ), unde:(i) Fn(B) este mulţimea funcţiilor Booleene de n variabile definite peste Bn, cu valori în B, n

≥ 1.(ii) + reprezintǎ adunarea acestor funcţii,(iii) * reprezintǎ multiplicarea acestor funcţii,(iv) 0 este funcţia identic nulă, iar(v) 1 este funcţia constantă 1.

Această algebră a funcţiilor scalare joacă un rol deosebit în fundamentele matematice ale analizei şi sintezei dispozitivelor numerice pentru că operatorii ş i elementele acesteia se pot implementa prin dispozitive care se pot produce industrial în mod eficient. Studiul proprietăţilor acestei algebre arată modul în care sunt utilizabili operatorii şi elementele acesteia pentru modelarea conceptelor dezvoltate în calculul algebrico-analitic tradiţional.

Funcţiile BooleeneO funcţie scalară din Fn(B) incomplet specificată este definită peste o partiţie a mulţimii Bn. Valorile din domeniul de definiţie (adesea referite generic prin puncte) unde funcţia nu este definită, se numesc valori neprecizate ale funcţiei, sau, condiţii neprecizate (don’t care, este termenul anglo-saxon). Aceşti vectori din domeniul de definiţie al unei funcţii se referă, în fapt, la valori care nu sunt utilizate şi, prin urmare valorile funcţiei respective nu sunt observate în acele puncte.

Un interes deosebit îl prezintă funcţiile vectoriale definite peste Bn cu valori în Bm unde m >

17


1. O astfel de funcţie este considerată echivalentă unui vector de funcţii din Fn(B). Valorile neprecizate ale funcţiilor vectoriale pot fi distincte pentru fiecare dintre cele m componente ale respectivei funcţii. Acest aspect se datorează faptului că punctele neprecizate pot fi proprii unor anumite componente ale vectorului de funcţii. Din acest motiv funcţiile vectoriale incomplet specificate sunt considerate ca fiind definite peste Bn, dar cu valori în mulţimea {0,1,*}m , unde prin simbolul * s-a notat condiţia de nedefinire, de neprecizare, a funcţiilor scalare. Pentru fiecare componentă scalară a unei funcţii vectoriale se poate defini o partiţie a domeniului de definiţie după valorile luate. Astfel, toate punctele în care o funcţie scalară ia valorile 0, 1 şi * se numesc, tradiţional, 0-set, 1-set, şi respectiv *-set (off set, on set şi respectiv dc set, în literatura anglo-saxonă). Nu există pericolul unei confuzii între notaţiapunctelor din codomeniu desemnând valori nedefinite, pe de-o parte, şi operatorul multiplicativ al acestei algebre deoarece tradiţ ional operatorul multiplicativ este omis utilizându-se simpla juxtapunere (juxtapunerea a două variabile, spre exemplu, este echivalentă produsului acestora).

O generalizare, într-un anumit sens, a noţiunii de funcţie booleană este relaţia booleană. O relaţie booleană este definită, în principiu, între spaţii Booleene. Astfel, unui punct dintr-un domeniu se asociază mai multe puncte din codomeniu (spre deosebire de funcţii unde se asociază un singur punct din codomeniu). Relaţiile Booleene şi optimizarea acestora joacă un rol deosebit în sinteza şi optimizarea circuitelor, reţelelor, multi-nivelP Pentru funcţiile Booleene, în speţă funcţiile de variabile binare cu valori binare, au fost introduse numeroase definiţ ii şi notaţii în vederea evidenţierii unor aspecte analitice mai importante ale acestora. O parte dintre acestea, cele mai semnificative, vor fi, succint, enunţate în cele ce urmează.Mulţimea variabilelor unei funcţii este numită mulţimea suport, sau pe scurt, suportul funcţiei.

Reprezentări ale funcţiilor BooleeneSunt posibile mai multe modalităţi de descriere ale unei funcţii Booleene. O caracteristică comună a acestor funcţii, care se va reflecta în toate aceste modalităţi de descriere, este faptul că funcţiile discrete de variabilă discretă au domeniul de defini ţie finit ş i implicit, astfel de funcţii sunt reprezentabile prin enumerări finite. Adeseori, însă volumul enumerării acestor funcţii poate fi considerabil sau chiar prohibitiv. Modalităţile de reprezentare pot fi clasificate ca fiind formele tabelare, expresiile sau formulele Booleene şi diagramele de decizii binare.

Formele tabelare, cronologic fiind primele utilizate, pot fi privite ca fiind alcătuite din enumeră ri ordonate de perechi de valori constituite din punctul domeniului de definiţie şi valoarea funcţiei în respectivul punct. Ca mod de implementare au suport evident în alcătuirea memoriilor. Punctele sunt vectori binari, la fel şi valorile funcţiei fiind binare scalare sau vectoriale. Au fost utilizate în aplicaţiile de asistenţă automată a proiect ării calculatoarelor în primele tentative de acest fel. Odată cu creşterea suportului funcţiilor reprezentarea devine incomodă iar metodele dezvoltate pentru acest mod de reprezentare nu s-au dovedit a fi printre cele mai performante.

Formulele Booleene, pe scurt formulele sau expresiile, au avantajul unei dezvoltări analitice de referinţă. Întreg aparatul teoretic utilizează această formă de reprezentare. Există numeroase aplicaţii care, sub o formă sau alta, sunt dezvoltate având la bază obiecte implementate prin structuri echivalente acestei forme de reprezentare. Ca formă de reprezentare are cele mai multe metode dezvoltate şi cu performanţe printre cele mai bune. Dimensiunile reale ale funcţiilor reprezentabile prin formule sunt superioare celor reprezentabile prin formele tabelare. Printre obiectele dezvoltate cu această reprezentare cele

18


mai cunoscute sunt cele corespunzătoare sumelor de produse (produselor de sume) în două sau mai multe nivele.

Diagramele de decizii binare (Binary Decision Diagrams, termenul în original, abreviat BDD) au fost iniţial introduse de Lee şi apoi reluate de Akers, pentru reprezentarea prin arbori sau grafuri aciclice direcţionate cu rădăcini, a funcţiilor binare de variabile binare, scalare. Aceste reprezentări permit manipulări de funcţii cu complexitate superioară celor reprezentabile prin formule Booleene.

Reprezentarea propusă de Akers utilizează pentru o decizie evaluarea unei variabile din suportul funcţiei. Utilizând această structură, ulterior, Bryant a introdus diagramele de decizii ordonate (Ordered Binary Decision Diagrams, cu abrevierea OBDD) şi a demonstrat existenţa unor algoritmi performanţi de manipulare a acestor forme de reprezentare.Schimbând maniera de decizie prin evaluarea unei funcţii în locul evaluării unei variabile, Karplus a introdus grafele aciclice direcţionate numite ITE (abrevierea sintagmei if-then- else) apreciate ca fiind o generalizare a OBDD. Există funcţii ale căror reprezentări prin ITE sunt mai compacte decât prin OBDD.

Formulele BooleeneExistă numeroase situaţii în care anumite proprietăţi ale unor dispozitive, reale sau simulate, virtuale, sunt exprimate prin formule construite peste algebrele Booleene. Existǎ o legătură de mare importanţă între formulele Booleene, pe de-o parte, şi funcţiile Booleene, pe de-altă parte.

O variabilă Booleană este o variabilă care ia valori din mulţimea B. Prin literali se înţeleg variabile Booleene care pot fi asertate sau complementate (negate). Variabilele sunt cele mai simple exemple de funcţii Booleene.

Expresiile construite prin simboluri legate prin operatorii * şi + sunt cele mai simple exemple de formule Booleene. Formulele pot fi dezvoltate ierarhic utilizând paranteze. O formulă booleană se defineşte după cum urmează.

Definiţia 2: Se considerǎ o algebră Booleană B şi n simboluri x1, x 2, …, xn, atunci mulţimea formulelor Booleene peste cele n simboluri este alcătuită din:

1. Elementele mulţimii B care sunt formule,2. Simbolurile x1, x2, …, xn care sunt formule,3. Dacă g şi h sunt formule, atunci tot formule sunt şi

• (g) + (h),• (g) * (h) şi• (h)’.

Un şir de caractere este o formulă Booleană dacă şi numai dacă aceasta se obţine printr-un număr finit de aplicări ale regulilor 1, 2 şi 3.

Se poate remarca din definiţia anterioară că numărul formulelor Booleene de n variabile este infinit.

Este esenţial de văzut modul în care unei formule Booleene F, corect definite, i se poate asocia o funcţie Booleană, de asemenea, corect definită.

Se considerǎ F, o formulă Booleană conţinând n simboluri, atunci funcţia f , de n variabile, corespunzătoare acestei formule se defineşte astfel:

19


Definiţia 3: Dacă F = b∈ B, atunci formula reprezintă funcţia constantă definită prin:f(x1, x2, …, xn) = b, ∀ (x1, x2, …, xn) ∈ Bn;Dacă F = xi, atunci formula reprezintă o funcţie proiecţie definită prin:f(x1, x2, …, xn) = xi, ∀ (x1, x2, …, xn) ∈ Bn;Dacă formula este de forma G + H, ori G * H, ori G’, atunci funcţia de n variabile corespunzătoare se defineşte după cum urmează:(g + h) (x1, x2, …, xn) = g(x1, x2, …, xn) + h(x1, x2, …, xn), (g * h) ( x1, x2, …, xn) = g(x 1, x2, …, xn) * h(x1, x2, …, xn), (g’) (x1, x2, …, xn) = (g(x1, x2, …, xn))’(x1, x2, …, xn) ∈ Bn.

Numărul de funcţii Booleene de n variabile definite peste o algebră booleană finită este finit.

Exemplul 2. Se consideră algebra construită peste mulţimea B = {0,1, a’,a}.Se consideră mulţimea simbolurilor ca fiind {x,y}, atunci, o formulă Booleană cu aceste două simboluri poate fi, spre exemplu, F = a’ * x + a * y’. (Tradiţional operatorul * se poate omite, fiind subînţeles, utilizându-se simpla juxtapunere a simbolurilor.)Funcţia Booleană de două variabile f: B2 → B, corespunzătoare formulei Booleene F = a’ * x + a * y’, va avea domeniul de definiţie:B2 = {(0,0), (0,1), (0,a’), (0,a), (1,0), (1,1), (1,a’), (1,a), (a’,0), (a’,1), …} şi poate fi definită punctual (deoarece domeniul de definiţie este finit) evaluând expresia considerată în fiecare punct al domeniului de definiţie:f(0,0) = a, f(0,1) = 0, f(0,a’) = a, f(0,a) = 0, f(1,0) = 1, ….□

Teorema de descompunere a unei funcţii Booleene (Claude Shannon).

Fie f: Bn → B o funcţie Booleană, atunci are loc identitatea:f(x1, x2, …, xn) = x1’ f(0, x2, …, xn) + x1 f(1, x2, …, xn),

∀ (x1, x2, …, xn) ∈ Bn,

Formulele canonice

Formulele canonice de reprezentare ale unei funcţ ii sunt unice pentru o funcţie dată. Există forme canonice din categoria expresiilor Booleene, dar există şi forme canonice din categoria diagramelor de decizii binare, acestea sunt diagramele de decizii binare ordonate.Atunci când se compară două forme canonice se ţine seama de specificul respectiv. Astfel, dac ă se compară reprezentări canonice OBDD atunci comparaţia va avea loc între doi arbori sau două grafe aciclice orientate cu rădăcini.

Astfel de forme sunt utile atunci când se compară două funcţii în vederea stabilirii identităţii lor. Adeseori în proiectare se aleg anumite formule de reprezentare ale unei funcţii în funcţie de natura tehnologiei utilizate, criteriile de performanţă etc. Pentru evitarea unor erori care pot apărea în procesul de calcul al unei formule de implementare pentru o funcţie dată se procedează, în general, la validarea funcţională a formulei implementate. Există mai multe metode de validare funcţională. Una dintre cele mai simple este calculul formei atât pentru funcţia considerată cât şi pentru formula sa de implementare.

Teorema de reprezentare

O funcţie f: Bn → B este Booleană dacă şi numai dacă aceasta poate fi exprimată prin identitatea:

20


f ( X ) = ∑ f ( A) X A

A∈{0,1}n

În identitatea de mai înainte s-au utilizat notaţiile :

X = (x1, x2, …, xn), A = (a1, a2, …, an) ∈ {0,1} , iar X x1 x2 xn .

Prin expresia xia

i se înţelege xi' dacă ai = 0 , şi xi dacă ai = 1. Termenii produs XA

astfel construiţi se numesc mintermi şi sunt fiecare în parte unic asociaţi unui anumit punct din domeniul de definiţie al funcţiei.Prezenţa lor în forma canonică disjunctivă este validată de valorile (nenule) corespunzătoare ale funcţiei.Demonstraţia acestei teoreme decurge simplu, utilizând sistematic teorema Shannon.

Exemplul 3Se consideră o funcţie de trei variabile (cazul n = 3). Aplicând teorema de reprezentare se obţine următoarea formulă canonică:

f (x ,x2

,x3

) = f (0,0,0)x' x' x' + f (0,0,1)x' x'x3

+ f (0,1,0)x'x2

x'

1 1 2 3 1 2 1 3f (0,1,1)x 'x

2x

3+ f (1,0,0)x x' x' + f (1,0,1)x x'x

3+ f (1,1,0)xx

2x'

1 1 2 3 1 2 1 3

f (1,1,1)x1 x2 x3

+

+

21


Termenii produs utilizaţi, mintermii, sunt prezenţi în formula canonică disjunctivăa unei funcţiei oarecare dacă funcţia respectivă are valori nenule în punctele corespunzătoare.

Se remarcă faptul că formula reflectă valorile funcţiei în toate punctele domeniului său de definiţie. Particularizarea sau personalizarea formulei canonice este exclusiv dependentă de aceste valori.

3.ANALIZA CIRCUITELOR COMBINAŢIONALE

Un circuit combinaţional C, este definit prin relaţiile dintre intrǎri şi ieşiri :fi : Bn → B, (B={0,1}),

zi = fi(x1,x2, …, xn),

unde :4. zi , 0 ≤ i ≤ m-1, este una dintre liniile de ieşire ale circuitului, iar5. x0, x1, …, xn-1 sunt liniile de intrare în circuitul combinaţional considerat (diagrama

modelului circuitelor combinaţionale, este prezentatǎ în figura 1).

x0z0

x1z1

. Circuit Combinaţional

. C .

. .

xn-1

.

zm-1

Figura 1. Reprezentarea modelului unui circuit combinaţional

1. Introducere

Se poate remarca, din relaţia care leagǎ liniile de intrare de liniile de ieşire, dependenţa în exclusivitate a valorilor ieşirilor de valorile aplicate intrǎrilor.Ca particularitate, funcţiile Boole-ene sunt, întotdeauna, funcţii cu domeniul de definiţie finit. Aşa cum au fost prezentate mai sus funcţiile fi au 2n puncte, n-uple, distincte în domeniul lor de definiţie (produsul cartezian al mulţimii B cu aceasta însǎşi de n ori).Datoritǎ faptului cǎ funcţiile au un domeniu de definiţie cu 2n n-uple distincte, iar funcţiile pot lua doar

douǎ valori, atunci numǎrul funcţiilor distincte, astfel considerate, este 22n .

Exemplul 1.1Funcţiile distincte cu douǎ variabile sunt :

Tabelul 1.1 Mulţimea tuturor funcţiilor Boole-ene cu douǎ variabile.x1 x0 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 10 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 11 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 11 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Dintre acestea, se remarcǎ, pentru ilustrarea exemplului :

22


4. funcţiile constante 0 şi 1, respectiv f0 şi f15 ;5. funcţiile identic x1 şi x0, respectiv f3 şi f5 ;6. funcţiile x1’ şi x0’, respectiv f12 şi f10;7. funcţiile SAU şi ŞI, respectiv f7 şi f1.

◊

Circuitele combinaţionale pot fi introduse prin enumerarea valorilor funcţiei corespunzǎtoare punctelor, în numǎr finit, domeniului de definiţie sau printr-o descriere comportamentalǎ a circuitului. Cea de-a doua cale este reductibilǎ la prima.

Exemplul 1.2Se considerǎ un circuit combina ţional care realizeazǎ suma a douǎ numere binare a şi b fǎrǎ semn reprezentate fiecare printr-un singur rang. Un astfel de circuit se numeşte, tradiţional, semi-sumator.

Circuitul, se poate remarca, este introdus printr-o descriere comportamentalǎ. Acestei descrieri se poate asoca, simplu, o descriere enumerativǎ punct cu punct, dupǎ cum urmeazǎ :

((a,b) | suma, transportul) :{ ((0, 0) | 0, 0), ((0, 1) | 1, 0), ((1, 0) |1, 0), ((1, 1) | 0, 1) }.

Se remarcǎ utilizarea unui mod de scriere explicit atât al valorilor argumentelor a şi b cât şi al valorilor funcţiilor de ieşire suma şi transportul, separând prin caracterul barǎ verticalǎ ( | ) punctul curent din domeniul de definiţie, de valorile funcţiilor în acel punct. Acest mod de scriere este mult rǎpândit în literaturǎ.

Cele douǎ funcţii sunt exprimabile separat ca formule Boole-ene utilizând fie valorile 1 (acolo unde funcţia este asertatǎ), fie valorile 0 (acolo unde funcţia este complementatǎ). În acest exemplu se va considera exprimarea celor douǎ funcţii prin aserţiuni.

Pentru aceasta se construiesc formulele celor douǎ funcţii utilizând teorema de reprezentare a algebrelor Boole-ene :

suma(a,b) = a’b + ab’ ; transportul(a,b) = ab.

S-a utilizat notaţia, mult răspândită, a’ pentru variabila a complementată.

Existǎ o strânsǎ coresponden ţǎ între definirea punct cu punct (numitǎ şi definirea prin tabela de adevǎr) şi scrierea prin formule a unei funcţii. În realitate, ambele cuprind aceeaşi informaţie. Se poate remarca, din forma canonic ǎ disjunctivǎ, cǎ produsele variabilelor funcţiilor sunt calculate acolo unde funcţia ia valoarea 1. Produsele respective se numesc, tradiţional, termeni produs (din cauza analogiei, curent practicate, dintre funcţia ŞI şi Multiplicarea numerelor reale) şi se calculeazǎ astfel :

iv. valoare 0 a variabilei, variabila apare în produs complementatǎ,v. valoare 1 a variabilei, variabila apare în produs asertatǎ.

Pentru termenii produs se mai utilizeazǎ , alternativ, denumirea de mintermi. Mintermii sunt indiciaţi, curent, cu valorile zecimale corespunz ǎtoare scrierii binare a mintermului. Astfel formulele pentru cele douǎ funcţii pot fi scrise, în aceeaşi ordine, astfel :

suma(a,b) = m1 + m2 ; transportul(a,b) = m3.

Construcţia formulelor prin punctele unde funcţiile sunt complementate se poate deduce similar sau se poate calcula simplu utilizând relaţiile De Morgan aplicate formulei deduse pentru punctele unde funcţiile sunt asertate. Este un foarte bun exerciţiu.

1.1 Dualitatea şi Legile DeMorgan

Dualitatea este o proprietate foarte utilă a algebrelor booleene. Expresia duală a unei expresii Boole-ene se deduce prin:

4. înlocuirea operatorului ŞI (⋅), prin operatorul SAU (+) şi reciproc;5. înlocuirea constantei 0, prin constanta 1 şi reciproc;6. în timp ce, variabilele expresiei rămân neschimbate.

23


Orice teoremă ori propoziţie demonstrată din algebra booleană ca fiind adev ărată, are întodeauna o duală, deasemenea adevărată. Dualitatea este, în esenţă, o meta-teoremă, cu alte cuvinte o teoremă despre teoreme.

Cu toate că dualitatea nu cuprinde, în sine, o modalitate directă de simplificare a expresiilor booleene, aceasta oferă posibilitatea deducerii unor noi teoreme din cele deja cunoscute ajuntând astfel în procesul de simplificare al expresiilor.

Astfel, teorema de unificare x ⋅ y + x ⋅ y’ = x, are duala formulată astfel (x + y) ⋅ (x + y’) = y.

O demonstraţie a dualei teoremei de unificare decurge, succesiv, în două etape astfel:= aplicând legea de distributivitate se poate transcrie expresia membrului stâng al dualei teoremei de unificare:

(x + y) ⋅ (x + y’) = x ⋅ (x + y’) + y ⋅ (x + y’),= în continuare, expresia obţinută devine:

⋅ (x + y’) + y ⋅ (x + y’) = x + y ⋅ x = x ⋅ ( y + 1) = x,ceea ce trebuia demonstrat.

Se consideră expresia: f = abc + a’(b + c), pentru care se calculează duala. O cale simplă de calcul a dualei poate fi imaginată prin divizarea expresiei date în sub-expresii mai mici pentru care efortul de calcul poate fi mai uşor controlat: f = e1 + e2, unde e1 = abc, iar e2 = a’(b + c).Se notează, tradiţional, duala expresiei f prin fD, rezultând că:fD = e1D ⋅ e2D.Aplicând principiul dualităţii sub-expresiei e1D, rezultă:

e1D = a + b + c.Similar, se calculează sub-expresia:

e2D = a’ + bc.Rezultatul final arată astfel :

fD = (a + b + c)( a’ + bc).

Legea DeMorgan oferă o modalitate teoretică de complementare a unei funcţii, de complexitate modică. Expresia complementară a unei expresii date se formează pornind de la expresia originală prin înlocuirile:

5. oricare literal, prin complementul său (x prin x’ şi reciproc),6. oricare constantă, prin complementara sa (0 se substituie prin 1 şi reciproc),7. operatorul ŞI se substituie prin operatorul SAU şi reciproc.

Această teoremă, aplicată chiar operatorilor ŞI şi SAU arată relaţiile cu operatorii complementariSAU-NU respectiv ŞI-NU:(x + y)’ = x’ ⋅ y’,(x ⋅ y)’ = x’ + y’.

Relaţiile anterioare pot fi interpretate astfel: Operatorul SAU-NU aplicat unor variabile, este identic cu operatorul Ş I aplicat variabilelor respective dar complementate, în timp ce operatorul ŞI-NU aplicat unor variabile este identic cu operatorul SAU aplicat variabilelor respective dar complementate.

Se consideră expresia booleană de trei variabile E(a,b,c) = a’b’c + a’bc + ab’c + abc’. Complementara acesteia se calculează, pas cu pas astfel:

(E(a,b,c))’ = (a’b’c + a’bc + ab’c + abc’)’,(E(a,b,c))’ = (a’b’c)’ ⋅ (a’bc)’ ⋅ (ab’c)’ ⋅ (abc’)’,

(E(a,b,c))’ = (a + b + c’) ⋅ (a + b’ + c’) ⋅ (a’ + b + c’) ⋅ (a’ + b’ + c),(E(a,b,c))’ = (a + ab’ + ac’ + ab + bc’ + b’c’ + c’) ⋅ (a’ + a’b’ + a’c + a’b + bc + a’c’ + b’c’),

(E(a,b,c))’ = (a + bc’ + b’c’ + c’) ⋅ (a’ + bc + b’c’),(E(a,b,c))’ = (a + c’)(a’ + bc + b’c’),

(E(a,b,c))’ = abc + ab’c’ + a’c’ + b’c’,(E(a,b,c))’ = abc + b’c’ + a’c’.

P metodă, puţin mai simplă, pentru calculul formal al complementului expresiei unei funcţii constă în calculul dualei expresiei funcţiei urmat de complementarea fiecărui literal.

24


Astfel, complementul expresiei booleene de trei variabile din exemplul precedent ar putea fi calculat după cum urmează:ED(a,b,c) = (a’ + b’ + c) ⋅ (a’ + b + c) ⋅ (a + b’ + c) ⋅ (a + b + c’),Complementând fiecare literal din expresia dualei rezultă:

(E(a,b,c))’ = (a + b + c’) ⋅ (a + b’ + c’) ⋅ (a’ + b + c’) ⋅ (a’ + b’ + c).

De remarcat faptul că duala unei expresii şi legea DeMorgan aplicat ă aceleiaşi expresii nu sunt unul şi acelaşi lucru. Procedeul de obţinere al dualei este similar cu menţiunea că literalii nu sunt complementaţi pe durata procesului de calcul. Astfel, duala funcţiei SAU-NU este funcţia Ş I-NU şi reciproc, iar duala funcţiei ŞI este funcţ ia SAU şi reciproc. Atunci când se aplică, unei funcţii, teorema dualităţii se obţine o cu totul altă funcţie. Prin aplicarea legii DeMorgan unei funcţii anumite se obţine complementara respectivei funcţii.

1.2 Formele Canonice

Compararea în raport cu identitatea, spre exemplu, a douǎ funcţii Boole-ene exprimate algebric (formule algebrice) este mult facilitatǎ dacǎ se utilizezǎ o formǎ etalon pentru codificarea, reprezentarea, funcţiilor respective. Termenul etalon trebuie înţeles în sensul unei standardizǎri, a unei unicit ǎţi, a scrierii algebrice pentru funcţiile binare de variabilǎ binarǎ. În literaturǎ formele acestea se numesc forme canonice. Formele canonice sunt forme unic determinate de funcţia pe care o reprezintǎ şi reciproc. Deîndatǎ ce douǎ funcţii au aceeaşi formǎ canonicǎ, acestea sunt identice. În mod frecvent se utilizeazǎ douǎ forme canonice :

∀ Forma canonicǎ disjunctivǎ, care se mai numeşte şi suma de produse (sum of products este termenul anglo-saxon cu binecunoscuta abreviere SOP) şi

∀ Forma canonicǎ conjunctivǎ, numitǎ deasemenea şi produs de sume.Existǎ şi alte forme canonice, cum ar fi forma canonicǎ exclusiv-disjunctivǎ, spre exemplu, şi lista ar putea continua.

1.2.1 Sumele de produse

S-au utilizat deja în exemplul semi- sumatorului aceste sume şi s-au precizat modalitǎţile de construcţie a acestor sume. Teoretic privind construcţia acestor sume se poate remarca faptul

25


cǎ sunt utilizate anumite funcţii predefinite numite mintermi. În principiu fiecare minterm este asociat unui punct specific din domeniul de definiţie al funcţ iei şi este propriu domeniului de defini ţie. Un minterm este constituit prin conjuncţia tuturor variabilelor funcţiei (o variabilǎ apare o singurǎ datǎ), iar fiecare variabilǎ apare în formǎ asertatǎ (directǎ , dacǎ în punctul respectiv variabila apare cu valoarea 1) şi în formǎ complementatǎ (negatǎ, dacǎ variabila în punctul respectiv are valoarea 0).Fiecare minterm este ponderat prin conjuncţie cu valoarea funcţiei în punctul corespunzǎtor mintermului.

1.2.2 Produsele de sume

Teorema involuţiei stabileşte cǎ prin complementarea complementului unei expresii, formule, booleene E se obţine expresia E. Aplicând de douǎ ori teorema De Morgan se poate deduce a doua formǎ canonicǎ a unei formule booleene. Aceastǎ formǎ se numeşte forma canonicǎ conjunctivǎ sau, încǎ, dezvoltarea în maxtermi.

Procedeul de construcţie al celei de-a doua forme canonice este dual celui utilizat pentru construcţia formei canonice disjunctive.Sunt utilizate exclusiv punctele în care funcţia ia valoarea 0. Pentru fiecare dintre aceste puncte sunt constituiţi maxtermii, cǎte unul pentru fiecare punct..Un maxterm este definit prin disjuncţ ia, suma, variabilelor funcţiei (fiecare apare o singurǎ datǎ fie asertatǎ, fie complementatǎ). Variabila apare în maxterm în formǎ asertatǎ dacǎ în acel punct variabila respectivǎ are valoarea 0 şi apare în formǎ complementatǎ dacǎ în acel punct variabila are valoarea 1.Este exact regula opusǎ celei cu care se construiesc mintermii.Produsul tuturor maxtermilor unei funcţii constituie forma canonicǎ conjunctivǎ sau, altfel spus, produsul de sume al respectivei funcţii.

Exemplu 1.3Se considerǎ produsul cartezian B3 pentru care se calculeazǎ toţi maxtermii :

Tabelul 1.2.Maxtermii spaţiului B3

a b c Maxtermii

0 0 0 a + b + c = M0

0 0 1 a + b + c’ = M1

0 1 0 a + b’ + c = M2

0 1 1 a + b’ + c’ = M3

1 0 0 a' + b + c = M4

1 0 1 a' + b + c’ = M5

1 1 0 a' + b’ + c = M6

1 1 1 a' + b’ + c’ = M7

◊

Exemplul urmǎtor aratǎ modul în care sunt calculate cele douǎ forme canonice în cazul unei funcţii arbitrare

26


4.CLASE DE CIRCUITE COMBINATIONALE

Tehnologiile utilizate pentru producerea circuitelor integrate prezintǎ, adesea, particularităţi proprii tehnologiilor respective. Faptul că aceeaşi funcţie logică poate avea mai multe expresii algebrice are un impact deosebit de util atunci când particluarităţile unei tehnologii impun utilizarea unui anumit stil de proiectare.

Dar nu numai tehnologiile aduc în discuţie stilurile de proiectare.Se întâmplă, adeseori, să să trebuiască să se utilizeze anumite circuite, pentru că sunt acestea sunt disponibile la furnizor sau sunt deja achiziţionate, ori pot apare constrângeri, din raţiuni economice, care impun utilizarea unei anumite familii tehnologice de circuite etc.

p

s &

27


u 5.

&t

u

q&

s

u p+

q q& +

zt r

u s

r& + &

s+

ut z

r

u&

t v6.

v

(a) (b)Figura 1. Circuitul exemplului 1.

Exemplul 1. Se consideră funcţia următoare:z(p, q, r,s,t, u, v) = psu + ptu + qsu + qtu + rsu + rtu + v.Această funcţie este exprimată, deja, în formă minimală printr-o sumă de produse. Implementarea acesteia, utilizând porţi ŞI, SAU, necesită şase porţi ŞI cu câte trei intrări şi o poartă SAU cu şapte intrări, aşa cum se poate urmări în figura 1(a). Costul total, în literali, al implementării acestei funcţii este 19.

Există posibilitatea ca prin factorizarea expresiei iniţiale, a funcţiei z, să se obţină o implementare cu un cost mai scăzut:

z = (ps + pt + qs + qt + rs + rt)u + v (1)z = ((p + q + r)s + (p + q +r)t)u + v (2)z = (p + q + r)(s + t)u + v (3)

Notând expresiile obţinute dupǎ cum urmeazǎ:Proiectarea Logică

w = p + q + r (4)x = s + t (5)

Expresia (3) se poate rescrie astfel:

28


z = wxu + v (6)

În această exprimare algebricǎ funcţia z necesită doar două por ţi SAU cu câte două linii de intrare, o poartă SAU cu trei linii de intrare şi o poartă ŞI tot cu trei linii de intrare. Costul expresiei (3) este de doar nouă literali (pentru că w şi x sunt consideraţi literali independenţi, fiind funcţii intermediare). Implementarea în formă factorizată a funcţiei z este ilustrată în figura 1(b).

Această implementare se numeşte, generic, circuit multi-nivel.Un astfel de circuit reduce mult numărul de porţi şi fire (conexiuni) dar, din cauza numărului crescut de nivele logice, timpul de întârziere al circuitului poate fi mai mare, depinzând mult de tehnologia de realizare, comparativ cu implementarea în două nivele ilustrată în figura 1(a).

8. Implementarea circuitelor combinaţionale utilizând doar porţi ŞI-NU ori doar porţiSAU-NU

Anumite tehnologii pot produce predilect fie porţi ŞI-NU, fie porţi SAU-NU. Din acest motiv implementarea unui circuit combinaţional utilizând fie doar porţi ŞI-NU, fie doar porţi SAU-NU constituie o aplicaţie practică. Este util, în abordarea care urmează, să fie reamintite teoremele DeMorgan:

(uv)’ = u’ + v’, (u + v)’ = u’v’, şiu + v = (u’v’)’, uv = (u’ + v’)’

Utilizând aceste teoreme se poate afirma că o funcţie ŞI-NU poate fi implementată printr-o poartă SAU ale cărei intrări sunt inversate (negate). În mod similar o funcţie SAU-NU poate fi implementată printr-

o poartă ŞI având intrările negate.

p&

p&

p&

q+

z

q+

z

q&

zu u u

& & &v v v

(a) (b) (c)

Figura 2. Conversia unui circuit ŞI - SAU într-un circuitŞINU - ŞINU

Se consideră, pentru început, doar circuite exprimate în sume de produse numite, adeseori, circuite ŞI - SAU. Conversia unui astfel de circuit într-un circuit alcǎtuit exclusiv cu porţi ŞINU-ŞINU este prezentată în figura 2.

p'&

p'+

p'+

q'q'+

z+

z

q'+

z'u' u’ u’

& + +v' v' v'

(a) (b) (c)

Figura 3. Conversia unui circuit ŞI-SAU într-un circuitSAU-NU – SAU-NU.

Circuitul iniţial, prezentat în figura 2(a) este transformat într-un circuit funcţional echivalent inversând atât ieşirile porţilor ŞI cât şi intrările porţii SAU, corespunzătoare (conform (w’)’ = w), aşa cum se poate vedea în figura 2(b). În continuare, se poate remarca lesne cǎ o poartă SAU cu intrările negate este echivalentă funcţional cu o poartă ŞI–NU (figura 2(c)).

Conversia unui circuit ŞI – SAU într-un circuit SAU-NU – SAU-NU este prezentată în figura 3.

29


p+

p+

p+

q&

z

q&

z

q+

zu u u

+ + +v v v

(a) (b) (c)

Figura 4. Conversia unui circuit SAU – ŞI într-un circuitSAUNU - SAUNU

Circuitele SAU – ŞI se convertesc utilizând un procedeu similar. Astfel, conversia unui circuit SAU – ŞI într-un circuit format doar cu porţi SAU-NU este prezentată în figura 4.Această conversie transformă, deasemenea, circuitul iniţial (figura 4(a)) într-altul funcţional echivalent şi are ca procedeu inversarea ieşirilor porţilor SAU şi inversarea intr ărilor porţii ŞI (figura 4(b)). Având în vedere că o poartă ŞI cu intrările negate este echivalentă funcţional unei poarţi SAU-NU, se obţine circuitul echivalent constituit doar din porţi SAU-NU (figura 4(c)).

Conversia unui circuit SAU–ŞI, simplu, într-un circuit care utilizeazǎ exclusiv cu porţi ŞI-NU este prezentată în figura 5.

p+

p'+

p'&

q&

z

q’&

z

q’&

z'u’ u’u

+ + &v’ v’v

(a) (b) (c)

Figura 5. Conversia unui circuit SAU – ŞI într-un circuitŞI-NU – ŞI-NU

Această conversie urmează un procedeu, similar unuia utilizat anterior, prin care în circuitul iniţial (prezentat în figura 5(a)) se inversează variabilele de intrare şi liniile de intrare în porţile SAU în (figura 5(b)). În continuare, având în vedere că o poartă SAU cu liniile de intrare negate este echivalentă funcţional unei porţi ŞI-NU şi prin negarea liniei de ieşire a porţii z (pentru omogenitatea transformǎrii) se obţine conversia finală (figura 5(c)).

Procedeele utilizate pentru circuitele cu două nivele sunt aplicabile şi circuitelor multinivel atunci când se intenţionează constituirea unor circuite multinivel alcătuite doar din porţi având aceeaşi funcţionalitate (ŞI-NU ori SAU-NU).

2. Utilizarea decodoarelor şi multiplexoarelor

Decodoarele şi multiplexoarele sunt circuite combinaţionale complexe, realizate integrat, fiind utilizabile şi pentru implementarea unor circuite combinaţionale arbitrare, altele decât cele pentru care au fost proiectate. Aceste dispozitive sunt circuite integrate pe scara medie (MSI) şi pot oferi, pentru proiecte de complexitate mică şi medie, soluţii surprinzător de eficiente. Datoritǎ complexitǎţii funcţionale a acestor circuite MSI costul proiectǎrii logice se exprimǎ prin numǎrul de capsule utilizate.Cu cât sunt utilizate mai puţine capsule în tehnologia MSI, cu atât este mai performantǎ proiectarea cu aceste circuite.

G1 y0

y1

G2a

30


G2by2

y3

A74x138

y4

By5

y6

Cy7

Figura 6. Diagrama generalǎ adecodorului 74X138.

Decodoarele. Acestea mai sunt numite şi demultiplexoare, sunt circuite combinaţionale având, în principiu, n linii de intrare şi mai multe linii de ieşire. Fiecare linie de ieşire, a unui decodor, corespunde unui anumit minterm al spaţiului Boole-ean cu n variabile, Bn ={0, 1}n.

În figura 6 este prezentat decodorul 74x138. Acesta are trei linii de intrare de validare (G1, G2a şi G2b) şi trei lini de intrare de date (A, B şi C). Liniile de ieşire ale acestui decodor sunt notate y0, y1, … şi y7. Acestea sunt active atunci când au valoarea 0. Liniile de validare G1, G2a şi G2b sunt, de asemenea, active atunci când au valoarea 0.Funcţionarea liniilor de ieşire este descrisǎ de urmǎtoarele relaţii:

valid = G1 ⋅ (G 2 a ) '⋅ (G 2b) ',

y0 ' = A '⋅ B '⋅ C '⋅ valid,y1 ' = A ⋅ B '⋅ C '⋅ valid,y 2 ' = A '⋅ B ⋅ C '⋅ valid,y3 ' = A ⋅ B ⋅ C '⋅ valid,y 4 ' = A '⋅ B '⋅ C ⋅ valid,y5 ' = A ⋅ B '⋅ C ⋅ valid,y6 ' = A '⋅ B ⋅ C ⋅ valid,y7 ' = A ⋅ B ⋅ C ⋅ valid,

(8 – 15) Atâta timp cât semnalul valid are valoarea 0 (ceea ce înseamnǎ cǎ G1= 0, G2a = 1 şi G2b = 1) liniile de ieşire, toate, vor fi inactive (au valoarea 1). Atunci când semnalul valid are valoarea 1, se activeazǎ o singur ǎ linie de ieşire corespunzǎtor valorilor liniilor de intrare de date A, B şi C. Astfel, dacǎ valid = 0 şi A = 1, iar B = 0 şi C = 0, este activatǎ linia de ieşire y1 (y1 = 0), iar toate celelalte linii de ieşire sunt inactive (yi = 1, pentru i = 0, 2, 3, 4, 5, 6, 7).Pentru astfel de decodor se utilizezǎ notaţia, genericǎ, decodor 3:8. Aceasta este o denumire mult rǎspânditǎ, şi foarte expresivǎ. În aceastǎ manierǎ se pot introduce, generic, decodoare n : 2n, unde n este numǎrul de linii de date ale decodorului generic.În afara acestui decodor existǎ şi decodorul 74x139, care într-o capsulǎ cu 16 pini (aceeaşi capsulǎ este utilizatǎ şi pentru 74x138) conţine douǎ decodoare independente de tipul 2 : 4. Fiecare decodor 2 : 4 are o linie de intrare de validare unicǎ, separatǎ, activǎ tot prin valoarea 0.

Pare, într-un fel, neobişnuit faptul cǎ liniile de ieşire sunt active prin valori 0. Atunci când au apǎrut aceste circuite (din familia MSI) industria circuitelor de comutaţie era dominatǎ de tehnologia bipolarǎ TTL. O caracteristicǎ intrinsecǎ a acestei familii de circuite face ca viteza de comutaţie a circuitelor inversoare (ŞI-NU, spre exemplu) sǎ fie mai mare decât a celor ne-inversoare (ŞI, spre exemplu). Cualte cuvinte, aceste circuite decodoare erau proiectate sǎ se conecteze, preferenţial, la circuite inversoare (ŞI-NU, spre exemplu).

Deoarece orice funcţie booleană poate fi exprimată printr-o sumă de mintermi se poate lesne realiza că prin utilizarea unui decodor potrivit ales şi a unei porţi SAU (presupunând că liniile de ieşire ale decodorului sunt active prin valoarea 1) este fezabilă implementarea respectivei funcţii direct printr-o sumă de mintermi corespunzătoare, fǎrǎ o prealabilǎ minimizare, în principiu. Deoarece liniile de ieşire sunt active prin valori 0, porţile SAU sunt înlocuite prin porţi SAU cu liniile intrare inversate, ceea ce este echivalentul porţilor ŞI-NU. În tehnologia TTL porţile ŞI-NU erau componenta de bazǎ, având o vitezǎ de comutaţie superioarǎ.

Mai mult, orice circuit combinaţional cu n linii de intrare şi m linii de ieşire poate fi implementat direct, în principiu printr-un singur decodor, potrivit ales şi m porţi ŞI-NU corespunzătoare.

31


Procedeul implementării unei funcţii booleene printr-un decodor generic şi o poartă are drept date de intrare expresia în sumă de mintermi a respectivei funcţii. Decodificatorul este ales, ori proiectat, astfel încât să genereze toţi mintermii variabilelor de intrare.Liniile de intrare ale porţii sunt conectate la mintermii corespunzători, după cum este definită funcţia.

Exemplul 2. Se consideră un circuit sumator pentru un bit având funcţionarea descrisă prin următorul tabel de adevăr:Tabelul 1. Tabelul de adevăr alunui sumator binar cu un rang.

x y ti te suma0 0 0 0 00 0 1 0 10 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 1

Se remarcǎ faptul cǎ sumatorul pentru un singur rang binar impelementeazǎ douǎ funcţii distincte, suma şi transportul spre rangul superior te. Din tabelul 1 se deduc ecuaţiile liniilor de ieşire ale funcţiilor sumatorului:

suma(x, y, ti) = Σm(1,2,4,7),te(x, y, ti) = Σm(3,5,6,7).

vi. +Decodor

3:8 1suma

ti20

2

y 21

3

x 22

4+

5te

6

7

Figura 7. Implementarea unui sumatorcu un rang utilizând un decodificator şi

două porţi SAU.

În acest exemplu sunt trei variabile de intrare producând în total opt mintermi. În consecinţă, se alege un decodor generic cu trei linii de intrare de date şi opt linii de ieşire - similar celui prezentat anterior, 74x138. Pentru facilitarea înţelegerii exemplului nu vor fi considerate liniile de intrare de validare iar liniile de ieşire vor fi presupuse active prin valoarea 1. Schimbarea valorii active a liniilor de ieşire corespunde, în cazul practic, alegerii unor porţi SAU cu intrǎrile negate, echivalente (în fapt) unor porţi ŞI-NU.Implementarea genericǎ este prezentată în figura 7. Decodorul generează toţi cei 8 mintermi pentru cele trei linii de intrare x, y şi ti.Poarta corespunzătoare liniei de ieşire suma, pentru sumatorul boolean cu un rang, calculează disjuncţia mintermilor 1, 2, 4 şi 7. Poarta corespunzătoare liniei de ieşire te, pentru transportul spre rangul următor,

32


formează disjuncţia mintermilor 3, 5, 6 şi 7. Mintermul 0 este singurul minterm neutilizat în aceastǎ aplicaţie.În acest exemplu sunt trei variabile de intrare producând în total opt mintermi. În consecinţă, se alege un decodor generic cu trei linii de intrare de date şi opt linii de ieşire - similar celui prezentat anterior, 74x138. Pentru facilitarea înţelegerii exemplului nu vor fi considerate liniile de intrare de validare iar liniile de ieşire vor fi presupuse active prin valoarea 1. Schimbarea valorii active a liniilor de ieşire corespunde, în cazul practic, alegerii unor porţi SAU cu intrǎrile negate, echivalente (în fapt) unor porţi ŞI-NU.Implementarea genericǎ este prezentată în figura 7. Decodorul generează toţi cei 8 mintermi pentru cele trei linii de intrare x, y şi ti.Poarta corespunzătoare liniei de ieşire suma, pentru sumatorul boolean cu un rang, calculează disjuncţia mintermilor 1, 2, 4 şi 7. Poarta corespunzătoare liniei de ieşire te, pentru transportul spre rangul următor, formează disjuncţia mintermilor 3, 5, 6 şi 7. Mintermul 0 este singurul minterm neutilizat în aceastǎ aplicaţie.

Capacitatea de decodare depinde de numǎrul liniilor de intrare. Numǎrul liniilor de intrare poate

+5V G1y0 d0

G2ay1 d1

y2 d2G2b

y3 d374x138

y4 d4A

x0y5 d5

Bx1 y6 d6

x2

Cy7 d7

x3G1 y0 d8

validG2a

y1 d9

y2 d10

G2by3 d11

74x138y4 d12

Ay5 d13

By6 d14

Cy7 d15

Figura 8. Implementarea unui decodor binarcu 4 linii de date, utilizând decodoare 74x138.introduce o limitare a utilizǎrii decodoarelor. Atunci când este necesarǎ o extindere a capacitǎţii de decodare se pot aplica procedee de conectare, în cascadǎ, a mai multor decodoare disponibile astfel încât sǎ se obţinǎ un decodor echivalent extins.Exemplul 3. Se consideră proiectarea unui decodor având patru linii de date şi 16 linii de ieşire atunci când sunt disponibile doar decodoare 3 : 8.

Multiplexoarele. Aceste circuite mai sunt numite, adeseori, selectoare. Aceste dispozitive au două grupuri de linii de intrare şi o singură linie de ieşire furnizând valoarea asertată a ieşirii iar, la anumite modele, este furnizată şi valoarea complementară a acesteia. Primul grup de linii de intrare sunt numite linii de date spre deosebire de cel de-al doilea grup de linii de intrare care sunt numite linii de selecţie. Valorile binare plasate pe liniile de selecţie sunt interpretate drept adresa binară a uneia dintre liniile de date. Astfel, dacă un multiplexor are n linii de selecţie atunci, corespunzător, vor fi 2n linii de date ale multiplexorului respectiv.

33


Există, deasemenea, o linie de activare sau de validare a liniei de ieşire. Această linie de validare este activă, de regulă, prin valori 0. Atunci când linia de validare are valoarea 1 linia de ieşire are valoarea constantă indiferent de valorile liniilor de date şi/sau selecţie.

Valid

D0

D1

D2W

D3 MPX

D4

8:1Y

D5

D6

D7

A B CFigura 7. Multiplexor cu 8 linii de date.

Linia de ieşire, Y, satisface relaţia:Y = (D0A’B’C’ + D1A’B’C + D2A’BC’ + D3A’BC +

D4AB’C’ + D5AB’C + D6ABC’ + D7ABC)Valid (7)

Utilizarea circuitului multiplexor pentru implementarea funcţiilor booleene este sugerată de ecuaţia (7). Astfel, cu un multiplexor 8:1 se poate implementa orice funcţie booleeană f(u , v, w)cu trei variabile. Pentru aceasta este suficient să se atribuie liniilor de date valorile constante 0 sau 1, corespunzătoare funcţiei respective:D0 = f(0,0,0), D1 = f(0,0,1), ... şi D7 = f(1,1,1).Se poate remarca că utilizănd acelaşi multiplexor 8:1, se poate implementa orice funcţie de patru variabile deoarece o funcţie de patru variabile f(t, u, v, w) poate fi scrisă astfel:f(t, u, v, w) = t f(1, u, v, w) + t’ f(0, u, v, w) (8) Deoarece f(1, u, v, w) şi f(0, u, v, w) sunt funcţii de trei variabile rezultă că liniilor Di, 7 ≤ i ≤ 0, li se vor atribui expresii constante ori care depind doar de variabila t. Deoarece expresiile în variabila t sunt extrem de simple (sunt doar două expresii netriviale: t şi t’) rezultă că efortul de implementare al unei funcţii booleene cu patru variabile printr-un multiplexor 8: 1, este minim. Se poate remarca, în acest sens, că:

7. oricare patru funcţii de două variabile se pot implementa printr-o singură capsulă conţinând patru multiplexoare 2:1,

8. oricare două funcţii de trei variabile se pot implementa printr-o singură capsulă conţinând două multiplexoare 4:1,

9. oricare funcţie de patru variabile se poate implementa printr-o singură capsulă conţinând un multiplexor 8:1 şi

10. oricare funcţie de cinci variabile se poat implementa printr-o singură capsulă conţinând un multiplexor 16:1.

Implementarea funcţiilor booleene având mai multe variabile, decât au fost amintite anterior, poate fi făcută, în anumite limite, cu un minim de efort. Abordarea teoretică face uz de o descompunere similară celei din relaţia (8) dar se factorizează două sau mai multe variabile. Expresiile rezultate în urma factorizării variabilelor se numesc expresii reziduale (care urmează să fie implementate la pinii liniilor de date ale multiplexorului utilizat).Aceste expresii reziduale pot fi simplificate utilizând tehnicile cunoscute şi apoi utilizând, eventual, un număr mic de porţi suplimentare pentru implementarea expresiilor reziduale se obţine implementarea dorită.

Exemplul 3. Se consideră implementarea funcţiei majoritate utilizând un multiplexor 4:1. Tabelul de adevăr al funcţiei majoritate arată astfel:

Tabelul 2. Funcţia majoritate.

34


a b c f Remarci0 0 0 0 ab = 00 → f = 00 0 1 0 ab = 00 → f = 00 1 0 0 ab = 01 → f = c0 1 1 1 ab = 01 → f = c1 0 0 0 ab = 10 → f = c1 0 1 1 ab = 10 → f = c1 1 0 1 ab = 11 → f = 11 1 1 1 ab = 11 → f = 1

Din tabelul 2, care descrie funcţiea majoritate, se poate alcătui un tabel mai aproape de scopul implementării funcţiei printr-un multiplexor 4:1. Acest tabel arată astfel:

Tabelul 3. Funcţia majoritateexprimată convenabil în

raport cu multiplexorul 4:1.

a b f0 0 00 1 c1 0 c1 1 1

Corespunzǎtor tabelului 3 se poate găsi o implementare a funcţiei majoritate f printr-un multiplexor 4:1, aşa cum se poate vedea din figura 8.

= D0

C D1 MPX

C4:1

f

D2 Y

= D3

S2 S1

A B

Figura 8. Implementareafuncţiei majoritate printr-un

multiplexor 4 :1.O altă cale de soluţionare a implementării funcţiilor booleene cu un număr mare de variabile este extinderea capacităţii multiplexoarelor existente, disponibile, prin interconectarea structurată a acestora, obţinând astfel multiplexoare cu un număr mare de linii de selecţie.

Exemplul 4. Un multiplexor 16:1 poate fi realizat, spre exemplu, din cinci multiplexoare 4: 1 aşa cum se arată în figura 9.

d0

D0 MPXd1

D1

4:1

d2 YD2

d3

D3 S2 S1

d4 D0 MPXd5

35


D1

4:1

d6 Y

D2

d7

D0 MPXD3 S2 S1

D1

4:1

Y

d8

D2

D0 MPX D3 S2d9

D1

4:1 S1

d10 YD2

A Bd11 D3 S2 S1

d12

CD0 MPXd13

D1

4:1

d14 YD2 D

d15

D3 S2 S1

Figura 9. Multiplexor 16:1realizat cu cinci multiplexoare 4:1.

Sunt disponibile, curent, multiplexoare cu 2, 4, 8 şi 16 linii de date. Astfel:8. 74x150 este un multiplexor cu 16 linii de date, patru linii de selecţii dar având disponibilă linia

de ieşire doar complementată. Capsula acestui dispozitiv are 24 de pini. Multiplexoarele următoare au capsulele cu 16 pini.

9. 74x151 este un multiplexor cu opt linii de intrare având disponibile ambele faze ale liniei de ieşire.

10. 74x153 este un multiplexor cu patru linii de intrare, două asemenea multiplexoare în aceeaşi capsulă, având liniile de selecţie comune dar liniile de validare sunt separate, câte una pentru fiecare multiplexor.

11. 74x157 este un multiplexor cu două linii de date şi o linie de selecţie, sunt patru asemenea multiplexoare într-o capsulă având comune linia de selecţie şi linia de validare, liniile de ieşire sunt disponibile doar asertate.

12. 74x158 este un multiplexor similar cu 74x157 exceptând faptul că liniile de ieşire sunt disponibile doar complementate.

Există multiplexoare având linii de ieşire cu trei stări. La aceste multiplexoare linia de validare forţează linia de ieşire în starea de impedanţă ridicată (circuitul apare ca având, practic, linia de ieşire neconectatǎ). Multiplexorul 74x251 este similar cu multiplexorul 74x151 ca mod de conectare la pinii capsulei şi ca funcţionalitate dar liniile de ieşire sunt cu trei stări (atât linia asertată cât şi cea complementată). Într -o situaţie similară sunt multiplexoarele 74x253 şi 74x257 versiuni, ale dispozitivelor 74x153 şi 74x157, liniile de ieşire având trei stări.

Exemplul 5. Se consideră, încǎ o datǎ, sumatorul binar cu un singur rang din exemplul 2.

36


Este o funcţie vectorială deoarece implementează atât suma rangului respectiv cât şi transportul spre rangul imediat următor. Procedeul de proiectare poate fi ilustrat considerând funcţia suma. Cele două variabile x şi y sunt conectate, în această ordine, la pinii de selecţie ai multiplexoarelor 4:1. Linia x este conectată la pinul S2 iar linia y este conectată la pinul S1. Valorile liniilor de date sunt determinate din

tabelul de adevăr al sumatorului. Atunci când (x,y) = (0,0), ieşirea suma este egală cu ti deoarece sumaQ0 când ti = 0 şi suma = 1 când ti = 1. Din acest motiv trebuie ca variabila ti să fie aplicată la pinii D0 ai ambelor multiplexoare. Într-o manieră similară se determină că pinii D1, D2 şi D3 aparţinând multiplexorului dedicat funcţiei suma au valoarea ti. Similar se determină valorile celorlalţi pini aparţinând multiplexorului care calculează transportul spre rangul următor, te.

37


D0 MPX0

D0 MPX

D1

4:1 ti

D1

4:1

Ysuma

ti

Y

te

D2 D2

1D3 S2 S1

D3 S2 S1

x y x y

Circuitele SAU-EX (suma-modulo-2) sunt adesea implementate prin multiplexoare. În figura 11 este prezentatǎ o astfel de implementare, pentru poarta SAU-EX cu douǎ variabile, x şi y.

0D

0 MPX∀ 4:1

1

D1

YSAU-EX(x,y)

D2

0D3 S2 S1

x y

Figura 11. Implementarea cicuituluiSAU-EX, utilizând un multiplexor 4 :1.

Memoriile cu conţinut fix

Memoriile cu conţinut fix, denumirea anglo-americanǎ fiind Read Only Memory (abrevierea fiind ROM), sunt dispozitive matriciale conţinând valori binare adresabile printr-un vector de valori binare care conţine adresa unei locaţii. Unei locaţii i se asociaz ǎ, de regulă un vector binar. Iniţial memoriile cu conţinut fix erau programate în momentul în care erau produse, în fabrică.

Mai nou aceste memorii pot fi programate, eventual re-programate, de utilizator prin mijloace proprii, specifice. Organizarea internă, generică, a unei memorii cu conţinu fix este descrisă în figura 11.

Arie de memoriiDecodor den linii de adresă adrese la nivel 2n linii (2n cuvinte a câte m biţi fiecare)

de cuvânt cuvânt

Ieşirim linii de

38


date

Figura 12. Organizarea internă a unei memorii cuconţinut fix.

Se consideră o memorie cu conţinut fix având 16 384 de biţi (16kb) formată dintr-o matrice de 128 x 128 de puncte care sunt sau nu sunt conductoare.Circuitul, aşa cum se poate urmări în figura 12, are opt linii de ieşire şi 11 linii de adresă în total, fiind organizat în 2 048 de cuvinte de opt biţi fiecare (2 kocteţi). Pentru fiecare combinaţie de intrare este generată o combinaţie de ieşire, în conformitate cu specificaţiile utilizatorului.

Decodorde

adrese Matrice de memorii cu

7 linii de

7 : 128128

128 linii x 128 biţi / linie =de

adresă având 16 384 biţilinii

128 liniide ieşire. 16kbiţi

(programaţi11 linii prin mascare)

de

adresă128 de liniiîn total.

4 linii de adresăBloc de 8 multiplexoare 16:1

8 linii de ieşire

Exemplul 1.4.

Se considerǎ funcţia de trei variabile defnitǎ prin tabelul :

Tabelul 1.3.Funcţia exemplului 1.4.

x2 x1 x0 f0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 11 0 1 11 1 0 11 1 1 1

Suma de produse pentru aceastǎ funcţie se calculeazǎ cu mintermii m3, m4, m5, m6 şi m7 :P = x2

' x1 x0 + x2 x1' x0

' + x2 x1' x0 + x2 x1 x0

' + x2 x1 x0 .

39


Produsul de sume se calculeazǎ prin maxtermii M0, M1 şi M2 :

f = (x2 + x1 + x0 )(x2 + x1 + x0' )(x2 + x1

' + x0 )◊

5.SINTEZA CIRCUITELOR COMBINAŢIONALE

Minimizarea logică exactă

Minimizarea logică exactă vizează rezolvarea găsirii unei acoperiri minimale.Este considerată o problema clasicǎ în teoria funcţiilor binare de variabile discrete şi primul rezultat remarcabil în găsirea unei acoperiri minime a fost formulat de Quine şi McCluskey. Soluţia problemei, aşa cum a fost formulată de autori, se bazează pe teorema lui Quine, teoremă care delimitează spaţiul căutărilor soluţiei optime.

Teorema Quine

Există o acoperire minimă care este primă.

Demonstrație Se consideră o acoperire minimă care nu este alcătuită din implicanţi primi. Fiecare implicant care nu este prim poate fi înlocuit printr-un implicant prim care-l conţine. Astfel, mulţimea rezultată de implicanţi este o acoperire şi are aceeaşi cardinalitate ca ş i acoperirea iniţială. În consecinţă, există o acoperire minimă care este alcătuită doar din implicanţi primi.

Teorema Quine permite limitarea căutării unei acoperiri minimale la acele acoperiri care constau exclusiv din implicanţi primi. Se remarcă faptul ca teorema se poate generaliza pentru a manevra definiţii mai largi ale acoperirii minime, unde costul unui implicant este întotdeauna mai mic sau egal cu costul unui implicant pe care -l conţine. Teorema se aplicǎ, spre exemplu, cazului de minimizare al numărului literalilor pentru funcţiile scalare (cu o singurǎ ieşire).

E. McCluskey a formulat căutarea unei acoperiri minime ca o problema de acoperire într-un tabel de implicanţi primi. Se va aborda aceasta formulare considerând funcţii scalare complet definite.

Un tabel de implicanţi primi este, în fapt, o matrice binarǎ A ale cărei coloane sunt în corespondenţă biunivocǎ cu implicanţii primi ai funcţiei f, iar rândurile sunt în corespondenţăbiunivocǎ cu mintermii funcţiei. Un element ai,j∈A este 1 dacǎ şi numai dacǎ cel de-al j-lea prim acoperǎ (conține) cel de-al i-lea minterm.

O acoperire minimǎ este o mulţime minimǎ de coloane care acoperă toate liniile, sau echivalent: o mulţime minimǎ de primi ce acoperǎ (conţin) toţi mintermii funcţiei.

Se poate observa cǎ:Problema acoperirii poate fi v ǎzutǎ ca fiind problema găsirii unui vector binar x reprezentând o mulţime de implicanţi primi cu cardinalitate ( |x| ) minimǎ astfel încât :

Ax >= 1 (1)Matricea A poate fi privitǎ ca matricea de incidenţǎ a unui hipergraf ale cărui noduri corespund mintermilor, iar arcele corespund implicanţilor primi. Într-o astfel de modelare, problema acoperirii corespunde unei acoperiri cu arce ale hipergrafului.

Exemplul 2.6. Fie funcţia scalarǎ de trei variabile a, b şi c:

f(a, b, c) = a’b’c’ + a’b’c + ab’c + abc + abc’

Se poate verifica cu uşurinţǎ faptul cǎ implicanţii primi ai acestei funcţii sunt aceştia:

40


6. 0 0 * |17. * 0 1 |17. 1 * 1 |19. 1 1 * |1

Ţinând seama de implicanţii primi p, q, r şi s, matricea A aratǎ astfel:

p q r svii. 1 0 0 0viii. 1 1 0 011. 0 1 1 0= 0 0 1 1= 0 0 0 1

Vectorul x = [1101]T reprezintă o acoperire, pentru cǎ Ax >= 1.Se poate afirma cǎ vectorul x selecteazǎ implicanţii primi p,q şi s.

Minimizarea exactǎ poate fi rezolvatǎ calculând întâi tabelul de implicanţi primi şi apoi soluţionând problema de acoperire rezultatǎ.

De remarcat faptul cǎ problema de acoperire în acest caz este unatǎ, deoarece toate clauzele de acoperire pot fi exprimate ca o disjuncţie de implicanţi. Dificultatea abordǎrii constǎ din intractabilitatea problemei de acoperire şi din mǎrimea tabelului de implicanţi.

13. funcţie scalarǎ binarǎ cu n variabile binare poate avea 3n/n primi şi 2n-1 mintermi. De aceea, un algoritm exponenţial al unei probleme de mǎrime exponenţialǎ este probabil sǎ necesite un timp lung de calcul şi un volum mare de memorie.

Rezultatele actuale arat ǎ cǎ multe probleme practice de minimizarea logicǎ ale unor funcţii dificile pot fi rezolvate exact prin algoritmi performanţi care exploateazǎ natura problemei şi structuri de date eficiente.

Tabelul de implicanţi poate fi redus. Se pot extrage coloanele esenţiale corespunzătoare implicanţilor primi esenţiali, deoarece aceştia oricum trebuie sǎ aparţinǎ oricărei soluţii. Se pot înlătura liniile dominante şi coloanele dominate.

Extracţia implican ţilor primi esenţiali şi înlăturarea coloanelor dominate şi a liniilor dominante se poate face iterativ. Se obţine astfel, în final, tabelul redus al implicanţilor primi.

Dacǎ tabelul redus se întâmplǎ sa fie vid, atunci s-a gǎsit soluția deja, prin implicanţii primi esenţiali anterior extraşi.

Altfel, tabelul redus, numit uneori şi tabel ciclic, modelează așa-zisul miez ciclic al problemei.

Metoda originalǎ propusǎ de E. McCluskey revine la branşǎri, adică se aleg diferite combinaţii de coloane (implicanţi primi) şi se evalueazǎ costul corespunzǎtor.

41


Chiar dacǎ alegerea unei coloane (un prim implicant) poate conduce la simplificǎri bazate pe regulile de dominanţǎ şi de esenţiali, procesul este exponenţial (în cel mai defavorabil caz) în raport cu mǎrimea tabelei reduse.

Exemplul 2.7. Se considerǎ matricea A din exemplul 2.6.

p q r sR 1 0 0 0S 1 1 0 0∀ 0 1 1 0Q 0 0 1 1(vi) 0 0 0 1

Se remarcǎ imediat cǎ implicanţii p şi s sunt esenţiali. Aceasta revine la a spune cǎ implicanţii primi p şi s aparţin oricărei acoperiri.

Din acest motiv, coloanele corespunzătoare pot fi şterse la fel ca şi liniile incidente lor. Dupǎ procesul de reducere al matricei, matricea astfel obţinutǎ are o singurǎ linie şi douǎ coloane, arǎtând astfel :

q r101 1 1

În acest caz matricea ilustreazǎ faptul cǎ oricare dintre cei doi implicanţi q şi r poate fi folosit pentru a completa o acoperire minimǎ.

Matricea redusǎ nu este ciclicǎ şi nu este necesar, în consecinţǎ, un proces de branşare.

În concluzie, existǎ douǎ soluţii ale problemei acoperirii prime pentru aceastǎ funcţie:

{p, q, s} şi {p, r, s}.

O altǎ abordare clasicǎ, numitǎ, adesea metoda lui Petrick, constǎ în scrierea clauzelor de acoperire ale tabelului (redus) de implicanţi în forma unui produs de sume.

Fiecare clauzǎ (sau, echivalent, fiecare sumǎ din acest produs) corespunde unui minterm şi aceasta reprezintǎ disjuncţia implicanţilor primi care acoperă respectivul minterm.

Produsul de sume este apoi transformat într-o suma de produse ce este satisfǎcutǎ ori de câte ori un termen al sǎu ia valoarea 1.În acest caz, termenii produs reprezintǎ implicanţii primi care au fost aleşi.

Costul unei acoperiri este legat de numărul de literali din produs. Ca rezultat, o acoperire minimǎ este identificatǎ prin orice termen produs al SDP având cei mai puţini literali.

Exemplul 2.8. Se aplicǎ metoda lui Petrick matricei A (tabelului cu incidenţa implicanţilor primi, cum mai este numit) din exemplul 2.6.

p q r sP 1 0 0 0Q 1 1 0 02. 0 1 1 0Q 0 0 1 1P 0 0 0 1

42


Clauza care stabileş te acoperirea primului minterm este p; clauza relativǎ la cel de-al doilea minterm este p +q, etc. Produsul de sume aratǎ astfel:

(p)(p + q)(q + r)(r + s)(s) = 1

Calculând produsele se obţine forma sumǎ de produse (SDP):

pqs + prs = 1

ceea ce exprimǎ faptul cǎ exista douǎ acoperiri minime având aceeaşi cardinalitate, 3.

Prima acoperire este alcǎtuitǎ din aceastǎ submulţime {p, q, s} a implicanţilor primi, iar a doua reprezintǎ submulţimea {p, r, s} a implicanţilor primi.

De remarcat cǎ metoda lui Petrick s-ar fi putut aplica, încǎ mai eficient, tabelului redus de implicanţi primi şi ar fi condus la o singura clauzǎ:

β+γ =1

Astfel, ori implicantul prim q ori implicantul prim r, împreunǎ cu implicanţii primi esenţiali {p, s} determină o acoperire minimǎ cu implicanţi primi ai funcţiei considerate.

Chiar dacǎ exprimarea produsului de sume şi alegerea termenului produs din suma de produse sunt imediate, transformarea produsului de sume într-o sumǎ de produse (SDP) implicǎ un număr exponenţial de operaţii.Acest fapt limitează metoda Petrick la tabele cu dimensiuni relativ mici.

Algoritmul Quine -McCluskey poate fi extins la funcţ ii vectoriale prin calculul implicanţilor primi multi-ieşire şi a tabelului (matricii) implicanţilor primi, în mod corespunzǎtor.

Extensii pentru ca sǎ opereze cu funcţii incomplet specificate sunt, de asemenea, relativ

43


44

universitatea ioan slavici de curs_proiectare... · web viewun minterm este constituit prin...

Documents