curs proiectare;kl;

Proiectare logică

CAPITOLUL 1

1.BAZELE ARITMETICE ALE CALCULATOARELOR

În acest capitol vom prezenta problemele de bază ale aritmeticii: sisteme de numeraţie , baze de numeraţie, conversia numerelor dintr-o bază în alta pentru numere întregi şi fracţionare, operaţiile elementare cu numere în aceeaşi bază, pentru a trece apoi la reprezentarea numerelor în calculator şi la codurile pentru reprezentarea informaţiei.

1. 1. SISTEME DE NUMERAŢIEUn sistem de numeraţie este totalitatea regulilor de

reprezentare a numerelor cu ajutorul simbolurilor denumite cifre. Sistemele de numeraţie pot fi poziţionale (în care valoarea unei cifre depinde de poziţia ei) şi nepoziţionale (în care valoarea cifrei este aceeaşi în oricare poziţie). Sistemul zecimal este poziţional. Sistemul roman este nepoziţional , în general, având însă şi unele elemente poziţionale (anumite cifre plasate înaintea unor alte cifre le micşorează valoarea

1.1.1.Baza sistemului de numeraţieÎntr-un sistem de numeraţie cifra este un simbol care

reprezintă o cantitate întreagă. Numărul de astfel de simboluri permise pentru a reprezenta un număr se numeşte baza sistemului de numeraţie.

3

Sorin Adrian Ciureanu

ExempluSistemul binar (două cifre) : cifrele 0 şi 1;Sistemul zecimal (zece cifre):cifrele 0,1,2,3,4,5,6,7,8,9.Reprezentarea numerelorUn număr raţional, format din partea întreagă şi partea

fracţionară, se poate reprezenta în trei forme, într-un sistem cu baza de numeraţie b:

1) reprezentarea poziţională în care cifrele sunt scrise fiecare cu valoarea lor poziţională:

mnnn aaaaaaaa ................... 210121 2)reprezentarea algebrică care este o sumă de produse dintre

fiecare cifră şi puterea bazei corespunzătoare valorii cifrei :

m

mn

nn

n babababababa

............ 1

10

01

11

1 )3)forma restrânsă a reprezentării precedente:

n

miiiba

unde: b=baza sistemului de numeraţie

ia cifre1n numărul de cifre în partea întreagă

m numărul de cifre în partea fracţionarăna cifra cea mai semnificativă

ma =cifra cea mai puţin semnificativă

Orice cifră ai trebuie să fie mai mică decât baza b care , prin definiţie trebuie să reprezinte numărul maxim de simboluri .

ExempleUn număr întreg exprimat în baza x va fi:

N(x)=0

01

11

1 .... xaxaxaxa nn

nn

Un număr întreg exprimat în baza 10 va fi:

4

Proiectare logică01

11

1)10( 1010.......1010 aaaN n

nn

n

Numărul 1234(10) exprimat în această formă,începând cu cifra cea mai puţin semnificativă:1234(10)=4.100+3.101+2.102+1,103

1.1.2.Conversia numerelor întregi dintr-o bază în alta

Conversia numerelor întregi din baza 10 în baza bFie un număr x Z+. Dacă x<b atunci x(10)=x(b)

Dacă x≥b atunci trecerea din baza 10 în baza b se face în felul următor:

Conform teoremei împărţirii cu rest , avem sirul de egalităţi, în care semnificaţiile sunt: numătrul x, baza b, resturi ri şi câturi qi

x = bq0+r0

q0 = bq1+r1

q1 = bq2+r2

…………….……………..……………..Qk-1= bqk+rk

oprindu-ne la acel k pentru care qk = 0 ( adică atunci cînd câtul a devenit mai mic decât baza b).

x(10)=(rk rk-1……r1r0)(b)

Algoritmul de conversie presupune, deci, împărţirea numărului la baza b. Se obţine un cât şi un rest. Noul cât se împarte la bază şi se continuă la fel cu câturile succesive. Algoritmul continuă până când se obţine un cât 0. Resturile obţinute, în ordine inversă, reprezintă cifrele numărului iniţial în baza b.

ExempleSă se treacă numărul 27(10) din baza 10 în baza 2.

5


27 = 2.13+113 = 2.6 + 16 = 2.3 + 03 = 2.1 + 11 = 2.0 + 1 27(10) = 11011(2)

Algoritmul se poate formula şi altfel. Ne oprim atunci când câtul devine mai mic decât baza. În acest caz numărul în noua bază este format din ultimul cât urmat de resturile succesive, de la ultima împărţire la prima.

Să se treacă numărul 27(10) în baza 8.27 =8.3 + 33 =8.0 + 327(10) = 33(8)

Conversia numerelor subunitare din baza 10 în baza bFie numărul subunitar în baza 10:x(0,1….)Conversia numărului în baza b se face prin înmulţiri

succesive cu baza, separând partea întreagă rezultată.x.b = x1 + r-1 x1 (0,1….) 0 ≤ r-1 <bx1b = x2 + r-2 x2 (0,1….) 0 ≤ r-2 <b…………….…………….xm-1 b = xm + r -m xm (0,1….) 0 ≤ r-m <bProcedeul are un număr infinit de paşi. În practică se

alege un anumit număr de paşi în funcţie de precizia cerută.

ExempleSă se treacă numărul 0,375 din baza 10 în baza 2 şi

în baza 8.0,375.2 = 0,750 0,750.2 = 1,500

6

Proiectare logică

0,500.2 = 1 0,375(10) = 0,011(2)

0,375.8 = 3,0000,375(10) = 0,3(8)

Conversia numerelor reale din baza 10 în baza b . Fie z R+ . Numărul z se poate exprima sub forma

z=[ z] + z , partea întreagă şi partea fracţionară a numărului z.

Se parcurg următoarele etape:1) Se realizează conversia părţii întregi.2) Se realizează conversia părţii subunitare.3) Se concatenează cele două rezultate, punând

virgula între ultima cifră rezultată din conversia părţii întregi şi prima cifră rezultată din conversia părţii fracţionare.

Exemplu1)Să se treacă numărul 27,375 din baza 10 în baza 2.Din exemplele precedente avem:27(10)=11011(2)

0,375(10) =0,011(2)

Rezultă:11011,011(2)

Conversia numerelor reale din baza b în baza 101)Se trece de la reprezentarea poziţională a

numărului la reprezentarea algebrică în baza b.2)Se efectuează calculele în baza 10 şi se obţine

tocmai reprezentarea poziţională în baza 10.Exemplu Să se facă conversia numărului

10101,0110 din baza 2 în baza 10.10101,0110=1.20 +0.21 +1.22 +0.23 +1.24 +

7


+0.2-1 +1.2-2 +1.2-3 +0.2-4 = 1+4+16+0,25+ 0,125= 21,375

Pentru trecerea unui număr dintr-o bază oarecare x în baza 10 , dezvoltarea este:

11

33

22

110)10( ..............

nn xnxnxnxnnN

Exemplu123)4( N

21)10( 4.14.23 N )10(27

Invers, un număr N în baza 10 se trece în baza x prin împărţirea lui N la x şi apoi prin împărţirea câturilor succesive la x până ce câtul devine mai mic decât x. Rezultatul este format din ultimul cât urmat de resturile succesive, ultimul cât fiind pe poziţia cea mai semnificativă. Exemplu Să se scrie numărul )1(256 o în baza x=16.

256:16=16 rest =016:16 =1 rest = 0

1 este mai mic decât 16. Numărul în noua bază este 100

1.1.3.Operaţii aritmetice elementare

Operaţiile aritmetice elementare, adunarea, scăderea, înmulţirea şi împărţirea, se fac la fel ca şi în baza 10 numai că în loc de 10 se iau x unităţi, adică x unităţi dintr-o poziţie formează o unitate din poziţia cu semnificaţie imediat superioară.

Nu se pot face operaţii cu numere scrise în baze diferite. Este necesar ca în prealabil numerele să fie aduse în aceeaşi bază.

Exemple

)4(2

)4(1

321

123

N

N

21 NN 123 + 321=1110(4) 21 NN = )4(1110

8

Proiectare logică

21.NN 123 .321=123+3120+110100=110003(4)

În `general în sistemele de calcul datele sunt reprezentate în baza 2. Deoarece atât instrucţiunile cât şi datele sunt reprezentate pe 32 , 64 biţi sau chiar mai mulţi biţi, este greu de manipulat în baza doi şi atunci se alege baza 16 (hexazecimal). Fiind o bază de numeraţie mai mare decât 10 , trebuie alese simboluri pentru 10,11,12,13,14, 15, simboluri care sunt: 10→A 12→C 14→E 11→B 13→D 15→F

Tabel 1.1. Primele caractere în bazele 10,16 şi 2.Baza 10 Baza 16 Baza 2

0123

0123

0000000100100011

4567

4567

0100010101100111

891011

89AB

1000100110101011

12131415

CDE

1100110111101111

Pentru a trece un număr din baza 2 în baza 16 , sau invers, nu este necesar să trecem intermediar prin baza 10 . Se poate aplica următoarea regulă:

N(2)→N(16)

Se împarte numărul în binar de la dreapta la stânga în grupuri de 4 biţi şi apoi, conform tabelului 1, se exprimă fiecare grup de 4 biţi într-un număr hexa. Exemplu:

Fie un număr în binar N(2) = 1101110000011001

9


Se împarte în grupuri de 4 biţi 1101 1100 0001 1001 care corespund în tabelul 1 cu: D C 1 9

Rezultă: N(16)=DC19N(16)→N(2) Se caută pentru D, C, 1, 9 grupurile

corespunzătoare în baza 2: N(2)=1101 1100 0001 1001Aplicaţii 1)-Să se scrie o funcţie recursivă care să transforme un

număr în baza 10 într-un număr în baza b.Să se scrie programul pentru b≤9.Să se scrie programul în limbaj C.Soluţie:

Program# include <stdio.h># include < conio.h>/*se transformă un număr din baza 10 în baza b*/void transform (int n,int b) {int rest=n%b; if(n>=b) transform(n/b,b); printf(„%d’’,rest);}main( ) {int n,b; clrscr ( ); printf(„n=”); scanf(„%d”,&n); printf(„%baza=”);scanf(„%d”,&b); transform(n,b);

2) -Să se adune numerele : N1=1234(10) şi N2=ABCD(16)

Soluţie: Nu se pot face operaţii aritmetice cu numere în baze diferite în mod direct. Trebuiesc aduse la o bază comună.N1= 1234(10) 1234:16 = 77 rest 2 77:16 = 4 rest 13→D N1=4D2(16)

N1+N2=4D2(16) + ABCD(16) = B09F(16)

3)-Să se efectueze între numerele N1=1000(10) şi N2=5000(10) următoarele operaţii logice : 21 NN 21 NN

10

Proiectare logică

21 NN , unde operaţiile înseamnă sau, şi, suma modulo 2 (sau exclusiv), la nivel de bit, după următoarele tabele:

0 10 0 11 1 1

0 10 0 01 0 1

0 10 0 11 1 0

Soluţie: Numerele fiind date în baza 10 iar operaţiile fiind la nivel de bit, este necesar ca numerele să fie trecute în baza 2. Apoi trebuie executate la nivel de bit operaţiile.

N1 1000:16=62 rest 8 62:16=3 rest 14 N1=3E8(h)=0011 1110 1000(2)

N2 5000:16=312 rest 8 312:16=!9 rest 8 19:16=1 rest 3 N2=1388(h)=0001 0011 1000 1000(2)

N1=0000 0011 1110 1000N2=0001 0011 1000 1000N1 N2 = 0001 0011 1110 1000N1 N2 = 0000 0011 1000 1000N1 N2 = 0001 0000 0110 0000 4)-Pot fi a,b,c laturile unui triunghi dacă avem egalitatea

aaax= bbbx+cccx

oricare ar fi baza de numeraţie, cu a,b,c, < x ?Soluţie: a+ax+ax2 = b+bx+bx2 + c+cx+cx2

x2(b+c-a)+x(b+c-a) + b+c-a = 0(b+c-a)(x2+x+1) = 0 (b+c-a) =0 b+c=a

Ca să fie laturile unui triunghi trebuie ca a>b+c . Cum a=b+c nu se poate ca a,b,c, să fie laturile unui triunghi.

11


5)-Câte numere îndeplinesc condiţia ca aa(h) să aibă în reprezentarea binară numărul de 0 egal cu numărul de 1?

Soluţie:În binar următoarele numere pe 4 biţi au NR0=NR1 :0011=3 0101=5 0110=6 1001=9 1010=A 1100=B

1.2. REPREZENTAREA NUMERELOR ÎN CALCULATOR

Numerele reprezentate în calculator pot fi: -cu semn -fără semn.

Numerele fără semn sunt reprezentate în binar sau într-un cod binar zecimal.

Pentru numerele cu semn se utilizează o cifră semn, 0 pentru plus şi 1 pentru minus. Cifra de semn este cea mai semnificativă. Pentru un număr de n cifre sunt necesare n+1 poziţii. În mod formal, între cifra de semn şi număr există o virgulă. După modul de amplasare a virgulei există două forme de reprezentare a numerelor:

-cu virgula fixă -cu virgula mobilă.În forma cu virgula fixă, virgula care separă partea întreagă

de partea fracţionară este aşezată într-o poziţie bine definită a cuvântului binar.

În forma cu virgulă mobilă fiecare număr este reprezentat de două valori:

-mantisa, care indică mărimea exactă a numărului într-un anumit domeniu,-exponentul, care indică ordinul de mărime a numărului, fiind puterea la care se ridică baza mantisei. Exponentul indică, deci, implicit poziţia virgulei binare.

1.2.1. Reprezentarea numerelor în virgulă fixăExistă trei forme uzuale de reprezentare a numerelor în

virgulă fixă:-Reprezentare în mărime şi semn (MS)

12

Proiectare logică

-Reprezentare în complement faţă de 1 (C1)-Reprezentare în complement faţă de 2 (C2)Reprezentare în mărime şi semn (MS)

Un număr N este

0,10,0

NădacNNădacN

N

Exemplu:8=0,1000-8=1,1000

Dezavantajele acestei reprezentări sunt.-pentru adunare şi scădere se solicită circuite mai complexe;-există două reprezentări pentru valoarea 0 +0 = 0,0000 -0 = 1,0000Reprezentare în complementul faţă de 1

Un număr N este

0,10,0

NădacNNădacN

N

unde N se obţine prin negarea fiecărui bit din N.Exemplu:N= 8=0,1000N = -8=1,0111Reprezentare în complementul faţă de 2

Un număr N este:

0)(,1

0,0

2 NădacNCNădacN

N

Unde C2(N), complementul faţă de 2 al număruluiN , se obţine în felul următor: se explorează numărul de la dreapta la stânga până la primul 1 şi se lasă aceste cifre neschimbate , apoi se neagă fiecare bit.

Exemplu:+8 = 0,1000

13


-8 1,1000În calculatoare se utilizează de obicei complementul faţă de 2

Adunarea în C2 Regula de adunare a două numere reprezentate în C2 este:-Se adună numerele bit cu bit, inclusiv bitul de semn, şi se ignoră eventualul transport de la bitul de semn.-Dacă apare depăşire , atunci se semnalază eroare şi rezultatul este invalidat. În cazul exemplelor următoare, cu numere pe patru biţi, depăşirea apare cînd rezultatul va fi mai mare decât 15(10)

-La adunarea numerelor de acelaşi semn apare depăşire dacă şi numai dacă rezultatul are semn contrar semnului numerelor.

ExempleExemplul 1 N1=5 N2=3

Este un caz de adunare a două numere pozitive a căror sumă este 8<15, deci fără eroare. Reprezentarea lor în binar, cu cifră de semn şi suma lor este:

N1 0,0101+ N2 0,0011

0,1000 = 8(10)

Exemplul 2 N1=10

N2= 9Este un caz de două numere pozitive a căror sumă este 19 >16, există depăşire, deci eroare.

N1 0,1010N2 0,1001 1,0011 ↓ 1→depăşire.

Exemplul 3 N1 = −3

N2 = −9

14

Proiectare logică

Este un caz de adunare a două numere negative, fără depăşire, cu ignorarea bitului de transport la semn şi cu rezultat în C2 .Numerele în binar, cu bit de semn:

N1 1,0011 N2 1,1001Complementele faţă de 2, cu bit de semn:

N1 1,1101 + N2 1,0111

11,0100 cu bitul de transport la semn ignorat

Rezultatul în C2 este 1,0100 şi dacă îl complementăm din nou obţinem 0,1100, adică 12.

Exemplul 4 N1 = −12 N2 = −14Este un caz de adunare a două numere negativa a căror sumă este |−26 |>16 , deci cu depăşire şi cu rezultat eronat.

Numerele în binar: N1 1,0100 N2 1,0010

Complementele faţă 2: N1 1,0100 + N2 1,0010

10,0110 rezultat eronatLa adunarea a două numere de acelaşi semn apare eroare prin depăşire numai dacă rezultatul are semn contrar semnului numerelor.

Scăderea în C2

Scăderea în C2 se face duoă următoarea regulă: se calculează complementul faţa de 2 al scăzătorului şi se adună acesta la descăzut.

În cazul numărului de semn contrar, rzultatul este corect întotdeauna deoarece nu poate exista depăşire .

15


ExempluN1 = 8(10)=1000(2) = 0,1000N2 = 7(2) = 0111(2) = 0,0111N1−N2 = 0,1000 − 0,0111= 0,1000+1,1001 = 0,0001= 1(10)

1.2.2. Reprezentarea numerelor în virgulă mobilăAceastă formă de reprezentare se utilizează pentru unii

vectori foarte mari sau foarte mici sau pentru numerele cu parte fracţionară. Faţă de reprezentarea în virgulă fixă, în virgulă mobilă există avantajul de a nu mai exista depăşiri.

Un număr N poate fi scris în virgulă mobilă astfel:N = M·2E

unde: M = mantisa numărului E = exponentul număruluiM = SMc1 c2….cn

E = SE e1 e2…..em

unde: SM semnul mantisei SE semnul exponentului c1 c2….cn cifrele mantisei e1 e2…..em cifrele exponentului

Numărul de cifre ale mantisei şi exponentului diferă în funcţie de standardul de reprezentare. În standardul IEEE există:-format scurt E-8 biţi M-23 biţi-format lung E-11 biţi M-52 biţiSemnul mantisei şi al exponentului:

SME =

negativestenumaruldacapozitivestenumaruldaca

10

Numărul biţilor pentru exponent determină domeniul de mărime al numerelor reprezentate. Numărul biţilor pentru mantisă determină precizia de exprimare a numărului.

În primă fază orice număr N este adus la forma N = (±,f)·2±e

unde: N este numărul ce trebuie reprezentat în virgulă mobilă f este partea fracţionară a lui N

16

Proiectare logică

±1,f se numaeşte mantisă şi trebuie să respecte relaţia de normalizare 1 ≤ |1,f| < 2±e este exponentul bazei 2

Exemplul 1N = 2525(10) = 11001(2) = 1.1001·24 f=1001 mantisae=4 exponentul Exemplul 2

3231

N

1

543215

01234

2.1111,111111,0

222222

222223231

N

f=1111 mantisa e=−1 exponentul Exemplul 3

N 81

N=2

3 )001,0(281

=.-1,0.2-3 f=0 mantisa3e exponentulReprezentarea numerelor în virgulă mobilă are două forme

standard:-Reprezentarea în VM simplă precizie-Reprezentarea în VM dublă precizie

1.2.2.1.Reprezentarea în VM simplă precizie În reprezentarea simplă precizie, cuvântul are 32 biţi şi are

următoarea formă: 32 31 24 1S C=e+127 f

S - semnul numărului N

S

0,10,0

NN

Pentru cazul N=0 , S este nedeterminat.

17


C –caracteristica ocupă poziţiile 31-24 din reprezentare şi este construită în aşa fel încât să fie pozitivă. C=e+127 şi dacă C ≥ 127 e ≥0 C < 127 e < 0Valoarea maximă a caracteristicii este 28 -1 = 255 deci exponentul maxim admis în simpla precizie este emax = 255 – 127 =128f – Poziţiile 23-1 reprezintă mantissa, normalizată de obicei.

Vom lua exemplele anterioare şi le vom trece în VM simplă precizie,

Exemplul 1 25 = 1,1001 · 24 S = 0f = 1001C = e + 127 = 4 + 127 = 131 = 10000011

Cuvîntul este32 31 24 23 10 10000011 100100

Exemplul 2 121111,1

3231

S = 0f = 1111C = -1 + 127 = 126 = 01111110

Cuvântul este32 31 24 23 10 01111110 1111000 0

Exemplul 3 320,1

81

S = 1f = 0

18

Proiectare logică

C = -3 + 127 = 124 = 01111100Cuvântul este: 32 31 24 23 10 01111110 1111000 0

1.2.2.3. Reprezentarea în VM dublă precizie În dublă precizie cuvântul are 64 biţi.C este pe 11 cifre binare şi are valoarea maximă:Cmax = 211 -1 =2047emax = 2047 – 1023 = 1024f ocupă 52 poziţii binare

Exemplul 1

Să se reprezinte în VM dublă precizie N=−124,0625124,0625=11111,0001=1,1111000001·26

S=1f = 1111000001C = e+1023=6+1023=1029=10000000101Reprezentarea în VM dublă precizie este ,în general:64 63 53 52 1S C=e+1023 f

În exemplul curent:64 63 52 52 11 10000000101 111100……………………….0

Exemplul 2

Încercăm un exemplu invers, adică fiind dat un număr în reprezentarea VM simplă precizie pe 32 biţi să se afle numărul N.

Fie reprezentarea 32 31 24 23 11 10000101 100 1111 0000 1111 0010 0001

S=1 numărul este negativC=10000101=133 e=133+127=6

19


f= 100 1111 0000 1111 0010 0001N=−1,100111100000010001·26

=−1100111,100001111000010000=−103,5296+

1.2.2.3. Operaţii în VMAdunarea şi scăderea a două numere în VM se efectuează astfel:-Se compară cei doi exponenţi pentru a-l determina pe cel mai mare.-Se aliniază mantisa numărului cu exponent mai mic prin deplasarea virgulei exponentului mai mare.-Se adună sau se scad mantisele aliniate, păstrând exponentul comun.-Eventual se normalizează mantisa, concomitent cu modificarea rezultatului.

Exemplul 1 (adunare)

N1 = 43

N2 =7 Să se efectueze N1 +N2

N1 = 0011,02.1,111,022

222 121

2

01

·22

N2 = 7=111=1,11.22

N1 +N2 =(0,0011+1,11)=1,1111·22

Nu este necesară normalizarea.Exemplul 2 (scădere)

N2 =9 N1 =34N1 =34=100010=1,00010·25

N2 =9=1001=1,001·23 =0,01001·25

N1 -N2 =(1,00010-0,01001)·25 =0,01001.25 =1,1001.24

Înmulţrea şi împărţirea în VM se efectuează astfel:-Se adună sxau se scad exponenţii.-Se inmulţesc sau se împart mantisele.-Se normalizează rezultatul.

Exemplul 1 (înmulţire)N1 =5 N2 =9N1 =5 =101=1,01·22

20

Proiectare logică

N2 =9=1001=1,001·23

N1 ·N2 =(1,01·1,001)22+3 =1,01101·25=101101=45

Exemplul 2 (împărţire)N1 =5 N2 =10N1 =101=1,01·22

N2 =10=1010=1,010·23

N1:N2 = (1,01:1,01)·22-3 = 1,0·2-1 = (0,1)2 = (0,5)10

1.3. CODURI DE REPREZENTARE A INFORMAŢIEI

Deoarece informaţiile în calculator sunt în sistemul binar iar informaţiile externe accesibile omului sunt în sistemul zecimal sau numere într-o anumită limbă, este necesar a transforma informaţiile externe în informaţii interne şi invers. Această translatie se realizează prin operaţia de codificare

codificareInformaţia internă informaţia externăFie două mulţimi A şi B . A codifica elementele mulţimii

A prin mulţimea B înseamnă a face să corespundă fiecărui element aA o secvenţă de elemente bB.

Exemplu:Fie A={0,1,2,3,4,5,6,7,8,9} B={0,1}Codificarea lui 5 A înseamnă asocierea unei secvenţe de

cifre binare din B: codificare 5 → 0101În mod curent simbolurile mulţimii A (alfabet) se numesc

caractere, ele cuprizînd litere, cifre, semne de punctuaţie etc. Există o clasificare a codurilor din punct de vedere al

semnelor utilizate:-coduri NUMERICE- în care sunt reprezentate doar numere:

21


- coduri ALFANUMERICE-în care sunt şi litere, semne de punctaţie etc.

În calculatoare există coduri care codifică litere, cifre sau semne prin mulţimea B={0,1}.

O problemă principală care se pune este următoarea: dacă mulţmea A are un număr N de caractere, ce lungime trebuie să aibă secvenţa i I de elemente din B pentru a se putea pune toate cele N caractere într-o într-o reprezentare f:A→I. Dacă n este lungimea secvenţei, atunci combinările cu repetiţii care se pot face cu două elemente 0 şi 1 luate câte n vor fi 2n . Deci condiţia este:

N ≤ 2n

De exemplu, pentru a codifica cifre zecimale sunt necesare 4 cifre binare. n=4 N=10 24 =16 24 ≥ NPentru a putea codifica cifre hexazecimale avem : n=4 N=16

1.3.1.Coduri numerice

Codurile numerice se împart şi ele în două categorii:- coduri ponderate şi- coduri neponderate .

1.3.1.1.Coduri ponderateÎn codurile ponderate se asociază fiecărei cifre zecimale o

tetradă binară în care fiecare rang are o anumită pondere indicată de configuraţia codului. Deci o cifră zecimală într-un cod ponderat se poate scrie conform relaţiei:

N =

n

iiiqa

0 undeai = {0,1}

qi = reprezintă ponderea poziţiei corespunzătore a codului.Cel mai cunoscut cod ponderat este codul binar-zecimal,

cunoscut ca CBZ

22

Proiectare logică

Codul CBZ

În CBZ ponderile sunt 8421 (q0 =0, q1 = 2, q2 =4, q3 =8) , motiv pentru care este cunoscut sub denumirea de cod 8421.

De exemplu:7=0111=1.20 +1.21 +1.22 +0.23.

Codul 8421 este numit codul CBZ natural, întrucât fiecare cifră zecimală este înlocuită cu un grup de 4 cifre binare corespunzătoare numeraţiei naturale în sistemul binar.

Tabelul 1. 2. Coduri ponderateNr 8421 2421 4221 5421 7421 642(-1)0 0000 0000 00000 0000 0000 00001 0001 0001 0001 0001 0001 00112 0010 0010 0010 0101 0010 00103 0011 0011 0011 0010 0011 01014 0100 0100 0110 0100 0100 01005 0101 1011 1001 1000 0101 01116 0110 1100 1100 1001 0110 10007 0111 1101 1101 1010 0111 10118 1000 1110 1110 1011 1001 10109 1001 1111 1111 1100 1010 1101

În structura unităţilor centrale există unităţi aritmetice logice , denumite UAZ, (unităţi aritmetice zecimale) care, utilizând decodoare binar-zecimale şi zecimal-binare, pot să implementeze toate operaţiile aritmetico—logice folosite în binar. Utilizarea UAZ-urilor duce la o viteză sporită dar şi la un număr de erori mai mare şi, implicit, la un cost mai mare.

In tabelul 2 sunt date alte exemple de coduri ponderate: 2421, 4221, 5421, 7421.În aceste coduri ponderate unele numere se pot exprima în mai multe variante şi din această cauză este

23


necesar să se aleagă doar una din variante în funcţie de necesităţile aplicaţiei.

1.3.1.2.Coduri neponderate

În tabelul 1.3 se reprezintă principalele coduri neponderate utilizate.

Codul Exces 3 se obţine din codul 8421 prin adunarea la fiecare tetradă a cifrei trei (0011). Rezultă astfel un cod de autocomplementare din care s-a eliminat combinaţia 0000 ce ar putea fi confundată cu lipsa de informaţie.

Codul Gray se caracterizează prin faptul că trecerea de la o cifră zecimală la următoarea se face prin modificarea unui singur rang binar din tetradă.Acest cod se utilizează la minimizarea funcţiilor prin metoda Karnaugh.

Codul 2 din 5 utilizează pentru codificarea cifrelor zecimale, cinci poziţii binare, cu următoarea restricţie: fiecare combinaţie de cod conţine doi biţi semnificativi.

Tabelul 1.3. Coduri neponderateZecimal Exces 3 Gray 2din5

(74210)0 0011 0000 000111 0100 0101 991012 0101 0011 001103 0110 0010 010014 0111 0110 010105 1000 0111 011006 1001 9191 100017 1010 0100 100108 1011 1100 101009 1100 1101 11000

24

transmiţător

Proiectare logică

1.3.1.3. Coduri pentru detectarea erorilor şi coduri pentru corectarea erorilor

În transmisia de date, în urma transmisiei, la recepţie pot apărea diferite erori cauzate de zgomotele din canalul de transmisie.

Există două modalităţi de tratare a acestor erori: -detecţia erorilor; -corecţia erorilor.

Detecţia unei erori înseamnă determinarea apariţiiei unei erori la recepţie.

Corecţia unei erori înseamnă detecţia erorii şi corecţia ei., cu alte cuvinte înseamnă determinarea rangului bitului din secvenţa de transmitere a informaţiei care a produs eroare.Pentru detecţia erorilor se utilizează coduri ca:

-coduri cu bit de paritate -codul 2din 5 -codul Check Sum-codul detector de erori CRC-suma de control Fletcher

Pentru corectarea erorilor se utilizează:-codul Hamming.

Coduri cu bit de paritateMecanismul utilizării bitului de paritate în detecţia unei

erori constă în compararea bitului de paritate recepţionat cu cel de la primire calculat.

25

Octet recepţionatOctet transmisPt

comparare

Pr Pr

Pc

Eroare

canal


Fig.1.1.Mecanismul utilizării bitului de paritate în detecţia unei erori

De obicei entitatea fundamentală de transmisie este octetul. Unui octet i se ataşează în unitatea de transmisie un bit de paritate, Pt . după următooarele reguli: se face suma biţilor de transmisie şi rezultatul este Pt . Acasta împreună cu octetul de transmis se trimit pe canalul de emisie iar receptorul primeşte bitul de paritate Pt pe care il redenumeşte bit de paritate recepţionat Pr Receptorul, la rândul său, calculează din octetul recepţionat paritatea calculată Pc . Apoi se compară Pc cu Pr. . Dacă sunt egale (Pc=Pr =0 sau Pc =Pr =1), atunci nu este detectată eroare. Dacă sunt diferite, adică (Pr =0, Pc =1) sau (Pr =1, Pc =0) atunci se detectează eroare.

Detecţia erorilor prin bitul de paritate are dezavantajul că poate detecta numai un număr impar de erori (1,3,5….). La apariţia unui număr par de erori acestea nu se pot detecta prin bitul de paritate. De remarcat că în următoarele exemple am folosit paritatea impară, adică bitul de paritate este 1, la un număr impar de 1, deci la detectarea sumei modulo 2 în valoare adevărată. În unele cazuri se foloseşte paritatea pară, adică bitul de paritate este 1 la un număr par de 1, deci detectarea sumei modulo 2 în valoare negată. Se dă mai jos un tabel de coduri ale bitului de paritate pentru o transmisie pe 4 biţi.

26

Proiectare logică

Tabelu l. 4. Coduri ale bitului de paritate pentru o transmisie pe 4 biţi.

Reprezentare zecimală

Coduri bit paritate

0 000001 000112 001013 001104 001105 010106 011007 011118 100019 10010

Codul 2 din 5Pentru a putea detecta şi un număr par de erori se utilizează

codul 2 din 5, deoarece acest cod permite la fiecare număr exact doar 2 biţi de 1. De remarcat că şi în cazul acestui cod este posibil să nu se detecteze eroarea dar rata de apariţie a erorilor este mult mai mică.

Exemplu:Dacă se transmite 7(10001) şi dacă ultimii doi biţi se

recepţionează eronat, se primeşte 10010 adică 8. Bitul de paritate e neschimbat, se primeşte prin cod un număr valid şi detecţia nu apare la două erori.

Codul CHECK- SUMPentru perifericele care stochează date la blocuri de mari

dimensiuni, se calculează Check-Sum-ul unui bloc prin suma tuturor cuvintelor fără transport. Check- Sum-ul calculat pentru blocul de emisie se compară cu cel calculat la recepţie şi dacă sunt egale nu există eroare.

27

BLOCcu nxmcuvinte

BLOCRecepţionat

m biţi

emisie CSc

CSr

comparare

CSeeroare


Fig.1.2. Mecanismul detectării erorilor prin Check-Sum.ExempluFie un bloc cu n=4 cuvinte pe m=32 biţi de următoarea

formă: A B 0 11 C 3 42 3 4 56 0 7 0

CS = 3 A E A CStrimis

Codul detector de erori CRC (polinomial)Ideea algoritmului CRC este de a considera mesajul ca un

singur număr binar care să fie împărţit repetat cu o valoare fixată, suma de control fiind restul împărţirii. Mesajul de transmis este interpretat ca un polinom cu coeficienţi 0 şi 1. Un cadru de k biţi este văzut ca ca o listă de coeficienţi pentru un polinom de grad k-1. Bitul cel mai semnificativ este coeficientul lui xk-1 .

ExempluFie mesajul de transmis: 23(10) = 17(h) =10111(2)

Polinomul ataşat este: P(x) = 1.x4 + 0.x3 +1.x2 + 1.x1 +1.x0 = = x4 + x2 + x1 +x0

Polinomul de transmis P(x) se împarte la un polinom fix , împărţitor, G(x), restul fiind R(x). La recepţie polinomul Preceptat(x) se împarte la acelaşi polinom împărţitor G(x) şi rezultă un rest R' (x) . Dacă R(x) = R' (x) transmisia s-a făcut corect. Algoritmul pentru CRC este:

n cu

vint

e28

Proiectare logică

1. Fie r gradul polinomului generator G(x). Se adaogă r biţi la capătul mai puţin semnificativ al mesajului. Mesajul va avea n+r biţi.

2. Se împarte acest polinom la polinomul G(x).3. Restul este adăogat la capătul cel mai puţin semnificativ al

mesajului, apoi se transmite.Receptorul poate alege una din următoarele metode:

1. Separă mesajul şi suma de control. Calculează suma de control pentru mesaj (după ce adaogă r de 0) şi compară cele două sume de control.

2. Calculează suma de control a întregului mesaj şi verifică dacă obţine ca rezultat zero.

Alegerea unui polinom generator nu este simplă. Sunt utilizate trei polinoame - CRC-12 = x12 + x11 + x3 + 2.x1 + 1 (e=6 biţi)- CRC-16 = x16 +x15 + x2 + 1- CRC – CCITT = x16 + x12 +x5 +1 - Se detectează toate erorile sigulare, duble, cu număr impar de biţi, toate erorile în rafale de lungime 16 sau mai mici.

ExempluFie polinomul generator = 10111Pentru împărţire folosim un registru de 4 biţi. Împărrţirea se face astfel:

Registru =0Se adaogă 4 biţi de zero la sfârşitul mesajului.while (mai există biţi în mesaj){se şiftează registrul la stânga cu un bit şi se citeşte

următorul bit al mesajului pe poziţia 0,

if(bitul 1 a fost eliminat la pasul anterior prin şiftare)registru = registruV polinom

Suma de control FletcherLa sfârşitul anilor 70 s-a pus la punct o tehnică de

transmitere a datelor, cu rezultate ca CRC dar necesitând un

29


timp de calcul mai redus, cunoscută sub numele de suma de control Fletcher.

Câmpul de verificare se compune din 2 variabile de 8 biţi fiecare. Pe măsură ce fiecare octet din blocul de date este procesat, valoarea acestuia este adunată la prima variabilă iar restul împărţirii acesteia cu 255 devine noua valoare a variabilei.A doua variabilă este restul împărţirii la 255 al sumei dintre valoarea precedentă şi valoarea curentă a primei variabile. Se pot adăuga 2 noi octeţi care puşi la sfârşitul blocului de date să ducă la o sumă de control 0 la verificarea de către primitor. Primul octet calculat este 255 minus restul împărţirii la 255 a sumei celor 2 variabile de control. Al doilea octet este 255 minus restul împărţirii la 255 a sumei dintre primul octet şi prima variabilă de control.

int i; byte sum1, sum2, sum1=0; sum2=0; for(i=1; i<=black.length;i++) {sum1=(sum1+block(i))% 255, Sum2=(sum1+sum2)%255;}

check1=255-(sum1+sum2)%255,check2=255-(sum1+check1)%255,

Algoritmul Fletcher permite o detecţie a erorilor comparabilă cu cea a algoritmului CRC dar la un nivel cu un ordin mai mic, fiind recomandat implementării de procesoare mai lente. Coduri corectoare de eroriUnul din cele mai cunoscute coduri detectoare şi corectoare de erori singulare este codul Hamming (7,4). Această notaţie arată că avem 7 biţi dintre care 4 sunt biţi de date iar restul de 3 sunt biţi de paritate.

Organizarea biţilor în cuvânt este:

P1 P2 d1 P3 d2 d3 d4

30

Proiectare logică

Unde: P1 ,P2 ,P3 sunt biţi de paritated1 ,d2 ,d3 d4 sunt biţi de date

Biţii de paritate sunt calculaţi astfel:P1 = d1+d2 +d4

P2 = d1+d3 +d4

P3 = d2+d3 +d4

La codare se determină cuvântul de cod determinat de cei 4 biţi de date şi de cei 3 biţi de paritate după formula:

P1 = d1+d2 +d4

P2 = d1+d3 +d4

P3 = d2+d3 +d4

La decodare se calculează cu cei trei biţi de paritate, după formula:

1cP =P1 + d1+d2 +d4

2

cP =P2 +d1+d3 +d43

cP =P3 + d2+d3 +d4

-Dacă 1

cP =2

cP =3

cP =0 înseamnă că nu există eroare.-Dacă

1cP =

2cP =

3cP ≠0 atunci valoarea în binar dată de această

triadă este bitul în eroare conform notaţiei

P1 P2 d1 P3 d2 d3 d4

b1 b2 b3 b4 b5 b6 b7

-Dacă 3

cP 2cP 1

cP = 111 atunci b7 =1 şi rezultă că eroarea este la bitul de date d4 .-Dacă

3cP 2

cP 1cP = 110 atunci b6 =1 şi rezultă că er0area este la

bitul de date d3 .-Dacă

3cP 2

cP 1cP = 001 atunci b1 = 1 şi rezultă că eroarea este

la bitul de paritate P1 . Exemplul 1

31


Fie de transmis codul 1001 deci:

d1 = 1, d2 =0, d3 = 0. d4 =11

cP =1+0+1 =02

cP =1+0+1=03

cP =0+0+1=1Deci codul Hamming este la tranmisie 0 0 1 1 0 0 1 (sunt subliniaţi biţii de paritate)La decodare (recepţie), biţii de date recepţionaţi sunt:

1

0

0

1

4

3

2

1

r

r

r

r

d

d

d

d

Rezultă la fel ca la codare, deci fără eroare la biţi de date.Biţii de paritate recepţionaţi:

1

0

0

3

2

1

r

r

r

P

P

P

Nici la biţii de paritate nu s-au recepţionat eroriBiţii de paritate calculaţi sunt:

1cP =

4211rrrr dddP =0+1+0+1=0

2cP =

4312rrrr dddP =0+1+0+1=0

3cP =

4223rrrr dddP =1+0+0+1=0

Deoarece 1

cP 2cP 3

cP sunt 000, nu este eroare.

Exemplul 2

32

Proiectare logică

Presupunem că cuartetul Hamming recepţionat este 0011011l dacă bitul de date 6 (b6 ) care corespunde lui d3 s-a primit eronat. Să vedem cum codul Hamming detectează şi corectează această eroare.Calculăm biţii de paritate:

1cP =

4211rrrr dddP =0+1+0+1=0

2cP =

4312rrrr dddP =0+1+1+1=1

3cP =

4223rrrr dddP =1+0+1+1=1

3cP 2

cP 1cP =110 rezultă că b3 este eronat şi deci d3 este eronat.

La corecţie 13 rd şi deci d3 calculat =0

Exemplul 3 Presupunem că cuartetul Hamming recepţionat este 0111001 deci b2 este eronat respectiv P2 este eronată. Biţii de paritate sunt;

.1

cP =4211rrrr dddP =0+1+0+1=0

2cP =

4312rrrr dddP =1+1+0+1=1

3cP =

4323rrrr dddP =1+0+0+1=0

În acest caz datele s-au recepţionat corect dar bitul de paritate 2 este incorect. Coreclţia este P2 corectat =0.

1.3.2.Coduri ALFANUMERICE

Codurile alfanumerice reprezintă toate caracterele unui alfabet prin secvenţe de cifre binare. Alegerea numărului de poziţii binare necesare reprezentării este o problemă dificilă, acestea trebuind să îndeplinească pe lângă condiţia N≤2N şi o serie de alte condiţii legate de asigurarea protecţiei la transmisia informaţiei.

33


Codul ASCII Codul ASCII (American Standard Code for Information

Interchange) este un cod standard de reprezentare a caracterelor prin valori întregi pe 7 biţi. Acest cod a fost introdus pentru a se obţine o compatibilitate între diferitele tipuri de echipamente utilizate la procesarea datelor. Este compus din:

Codul ASCII STANDARD şi Codul ASCII EXTINS. Codul ASCII STANDARD Acest cod a apărut în aniii 60-70 şi este un cod pe 7 biţi

care constă în 128 caractere (27 ) atribuite unor caractere, numere, semne de punctuaţie şi celor mai uzuale caractere speciale. Cele 34 caractere de control sunt desemnate prin nume abreviate. Caracterele de control se utilizează pentru transmiterea datelor şi aranjarea textului într-un anumit format. Există trei tipuri de caractere de control: de formatare, de separare a informaţiei şi de control al comunicaţiei. Tabelul 1.5 Codul ASCII (7biţi)-STANDARD

b3 b2

b1 b0

b6 b5 b3

000 001 010 011 100 101 110 111

0000 NULL DLE 0 @ P " p0001 SOH DC1 ! 1 A Q a q0010 STx DC2 " 2 B R b r0011 ETx DC3 # 3 C S c s0100 EOT DC4 $ 4 D T d t0101 ENO NAK % 5 E U e u0110 ACK SYN & 6 F V f v0111 BEL ETB * 7 G W g w1000 BS CAN ( 8 H X h x1001 HT EM ) 9 I Y i y1010 LF SUB : J Z j z1011 VT ESC + : K [ k {

34

Proiectare logică

1100 FF FS , < L \ l |1101 CR GS - = M ] m }1110 SO RS > N ^ n –1111 SI US / ? O ] o DEL

Dintre caracterele de formatare a textului menţionăm BS (Back Space), retur de car (RC Carriage Retur), tabulare orizontală (HT Horizontal Tabulation).

Separatorii de informaţie se utilizează pemtru separarea datelor în secţiuni, de exemplu în paragrafe şi pagini. Acestea cuprind caractere cum sunt separatorul de înregistrare RS (Record separator),şi separatorul de fişier FS(File separator).

Caracterele de control al comunicaţiei se utilizează la transmisia textului. Exemple de asemenea caractere sunt: STx(Start of text) şi ETx(End of text) care se pot utiliza pentru ăncadrarea unui mesaj transmis pe liniile comunicaţie Codul ASCII RESTRÂNS este pe 8 biţi şi cuprinde caractere de e 128 e 255. Acestea reprezintă caractere suplimentare matematice, grafice, caractere speciale sau din diverse limbi. Codul UNICODE şi ISO/IEC ICE 10646 UNICODE este un set de caractere specificat de un consorţiu de producători importanţi de calculatoare din SUA. A fost elaborat cu scopul de a elimina dificultăţile cauzate de utilizarea seturilor de caractere codificate diferit în programele elaborate pentru mai multe limbi. Începând cu versiunea 1.1, UNICODE este compatibil cu standardul ISO 10646, a cărui primă vesiune a fost elaborată în 1993 de organizaţiile ISO (International Standard Organization) şi IEC (International Electrotechnical Commission). Numele standardului UNICODE provine de la Universal Multiple Octet Codet Character Set, întâlnit şi sub forma acronimului UCS (Universal Character Set). Versiunea curentă a standardului 10646 este 30UCS şi a fost primul set de caractere standardizat elaborat cu scopul de a

35


include în final toate caracterele utilizate în toate limbile, ca şi alte simboluri cum sunt cele matematice. UCS este folosit atât pentru reprezentarea internă a datelor în sistemele de calcul cât şi pentru comunicaţiile de date. În versiunile uzuale ale UCCS, codul unui caracter este reprezentat prin 4 cifre hexazecimale, deci pe 2 octeţi (versiunea UCS-2). Există şi o formă pe patru octeţi (UCS-4) pentru a garanta faptul că spaţiul de codificare va fi suficient şi în viitor. În UCS-2 există 65536 coduri ce sunt împărţite pe 256 linii cu câte 256 celule fiecare. Primul octet al codului unui caracter indică numărul liniei, al doilea octet numărul celulei. Primele 128 de caractere din linia 0 reprezintă caracterele ASCII. Întreaga linie 0 conţine aceleaşi caractere ca şi cele definite de standardul 8859-1. Octetul unui caracter din standardul 8859-1 poate fi transformat în reprezentarea UCS prin adăugarea de zerouri în faţa acestuia. UCS cuprinde aceleaşi caractere ca şi ASCII. În forma pe 4 octeţi pot fi reprezentate peste două milioane caractere diferite (232 ). Primul bit al primului octet trebuie să fie 0, astfel încât se utilizează doar 31 de biţi din 32. Acest spaţiu este împărţit în 128 de grupe , fiecare cu câte 256 de planuri. Primul octet de cod indică numărul grupei, al doilea numărul planului, al treilea numărul liniei, al patrulea numărul celulei. Caracterele care pot fi reprezentate în forma UCS-2 aparţin planului 0 din gruppa 0 , numit plan multilincv de bază BMP (Bazic Multilingual Plan). Încă nu au fost alocate poziţiile în afara planului BMP iar în practică se lucrează pe 2 octeţi.

Crearea unui cod Să creem un cod pentru un pachet de cărţi de joc cu 52 de cărţi care să răspundă la următoarele caracteristici, adică să scrie paternul binar în următoarele cazuri:

Toate cărţile de pică Toate cărţile de roşu

36

Proiectare logică

Toate cărţile de 6 indiferent de culoare Toate cărţile mai mari decât 8 Toate cărţile mai mari decât 4, de culoare roşie

Toate cărţile cu figuri (J,Q,K)Soluţie:Cărţile de joc sunt de 4 feluri: cupă, caro, pică, treflă.

Culorile sunt de două feluri : roşii(cupă şi caro) şi negre (pică şi treflă). Pentru cele patru feluri de cărţi sunt necesari 2 biţi iar

dacă se codifică într-un anumit fel se poate face ca unul din cei 2 biţi să codifice culoarea.

Tabelul 1.6.

Pentru a codifica cele 13 tipuri de cărţi sunt necesari 4 biţi. Exemplu de tip de codificare:

Tabelul 1.7.b3 b4 b5 b6 carte

0 0 1 0 1

0 0 1 1 2

0 1 O 0 3

0 1 O 1 5

0 1 1 0 6

0 1 1 1 7

1 0 O 0 8

1 0 0 1 9

1 0 1 0 10

37

b1 b2 fel culoare

0 0 cupă roşu

0 1 caro roşu

1 0 pică negru

1 1 treflă Negru


1 0 1 1 As

1 1 0 0 J

1 1 0 1 Q

1 1 1 0 K

Cu acest cod putem răspunde la toate paternurile, inclusiv la cel cu figurile, deoarece am codificat b3 = b4 = 11 toate figurile (J,Q,K). 1. Toate cărţile de pică 10xxxx

2 .Toate cărţile de roşu 0xxxxx 3. Toate cărţile de 6 indiferent de culoare xx0110 4, Toate cărţile mai mari decât 8 xx1xxx

5. Toate cărţile mai mari decât 4, de culoare roşie 0xx1006. Toate cărţile cu figuri (J,Q,K) xx11xx

38

Proiectare logică

CAPITOLUL 2

2.BAZELE LOGICE ALE SISTEMELOR DE CALCUL

2.1.FORMALISMUL MATEMATIC AL PROIECTĂRII LOGICE. ALGEBRA BOOLE.

Bazele algebrei Boole au fost puse de matematicianul şi logicianul englez George Boole (1815-1864). A fost concepută ca o metodă simbolică pentru tratarea funcţiilor logice dar a fost dezvoltată şi aplicată şi în alte domenii ale matematicii. In anul 1938 Claude Shanon a utilizat-o pentru prima dată în analiza şi sinteza circuitelor de comutaţie.

În anul 1854 apare la New York, în editura Dover Publication, lucrarea lui Boole An Investigation of the Laws of Thought . 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

39


acesteia. În linii mari activitatea de proiectare actuală în domeniul circuitelor digiitale 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: - uşa este deschisă atâta timp cât există o persoană în imediata sa proximitate ( aproximativ 50 cm de-o parte şi de alta a uşii) ş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ă. 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

40

Proiectare logică

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 întotdeauna o 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 devă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 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 a 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.

I.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 în K, (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 +

41


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ât a ’ = 0, şi a + 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 alta 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’ = 1 1 * 1 = 1 + 1 = 1 + 0 = 0 + 1 = 1, şi 0+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ă si verificarea legilor de distributivitate (Va şi Vb) necesită doar alcătuirea listelor de valori pe-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. O 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

42

Proiectare logică

cum au fost exprimate, sunt independente. Această verificare este mult mai complexă, si nu este esenţială pentru scopul cestei abordǎri. Pe de altă parte, nu este necesară abordarea algebrelor Booleene 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.

Algebra Boole este ,deci, o structură în care- mulţimea {0,1} este mulţimea elementelor algebrice;- operaţiile definite sunt:1. operaţia aditivă de tip SAU, notată cu +, care se

desfăşoară după următorul tabel: + 0 1

0 0 1

1 1 1

2.- operaţia multiplicativă de tip ŞI care se desfăşoară după următorul tabel:

43


. 0 1

0 0 0

1 0 1 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.

Principiul dual. 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, iar a+ (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 in demonstraţia unei teoreme poate fi înlocuit prin dualul acestuia, producând astfel demonstraţia teoremei duale.

Teoremele fundamentale ale algebrei Booleene Enunţăm principalele teoreme, cele care permit o manipulare convenabilă a algebrei Booleene. Unele dintre teoreme sunt 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,

44

Proiectare logică

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 1 Elementele 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 w2din 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. Utilizând comutativitatea operatorului + şi proprietatea de tranzitivitate a egalităţii, rezultă: 01= 2. Prin dualitate se poate demonstra şi unicitatea elementului 1. Lema 2 Pentru orice element w∈K au loc relaţiile: w+ w = w şi w* w = w.Lema 3 Pentru orice element w∈K au loc relaţiile: w+ 1 = 1 şi w* 0 = 0. Lema 4 Elementele 0 şi 1 sunt distincte iar 1’ = 0. Lema 5 Pentru orice elemente w1şi w2 din K au loc relaţiile: w1+ w1w2= w1, şi w1(w1+ w2) = w1. Lema 6 Complementul unui element w∈K, w’, este unic. Lema 7 Pentru orice element w∈K, (w’)’ = w. Lema 8 Oricare ar fi elementele u, v şiw∈K, are loc relaţia: u* ( (u+ v) +w)= ( u+ v) +w) * u. Teorema 1 Oricare ar fi elementele u, v şi w∈K, au loc relaţiile: u+ (v+ w) = (u+ v) + w, şi u* (v* w) = (u* v) * w.Teorema 2 Pentru orice pereche de elemente u şi v∈K, se verifică relaţiile: u+ u’v= u+ v şi u(u’ + v) = uv.Teorema 3 Următoarele două relaţii sunt adevărate oricare ar fi elementele u şi v∈K (u+ v)’ = u’ * v’ şi (u* v)’ = u’ + v’. Proprietăţile algebrelor Booleene Spre deosebire de postulate, proprietăţile sunt, în fapt, teoreme şi de aceea sunt demonstrabile. Metoda generală de demonstrare a

45


acestor proprietăţi se bazează pe postulatele algebrelor Booleene utilizându-se mult inducţia matematică.

Idempotenţa : x+x=x xx=x Comutativitatea: x+y=y+x xy=yx Asociativitatea: (x+y)+z=x+(y+z)=x+y+z (xy)z = x(y.z)=xyz Elementul neutru: pentru adunare este 0 x+0=x pentru înmulţire este 1 x1=x Distributivitatea: x(y+z) =xy+xz x+y.z= (x+y ) (x+z)

Complementarea: 1 xx principiul terţiului exclus

xx = 0 principiul contradicţiei (complementul mai poate fi notat x’)

Legile lui de Morgan: yxyx .

Generalizare: xi

n

i

n

iix

11

yxxy

Generalizare:

n

iii

n

i

xx11

Involuţia (negarea negaţiei) : xx Legea absorbţiei: forma aditivă x+xy = x x+ x y = x+y forma multiplicativă x(x+y) = x x( x +y) = xy

Algebre booleene O algebră Booleană se identifică, tradiţional, prin numele mulţimii suport, B. Există, în acest sens, următoarele exemple

46

Proiectare logică

clasice:Algebra comutatorilor, Algebra submulţimilor unei mulţimi (numită şi algebra claselor), Algebra booleană aritmetică, Algebra Booleană a funcţiilor Booleene.

Aplicaţii

Să se aducă la forma cea mai simplă următoarele expresii, utilizând postulatele algebrei boleene:

1) )( ABCABE Soluţie

comutivitate + distrib. idempotenţă absorbţie

ABABABCABAABBCE

2) ).)(( CBACBAE Soluţie: contradicţie+ complementaritate+ distributivitate comutativitate

CBACACBCCBACBACBAAE .

3) )(.( CBAACBBAACBCABE

Soluţie: terţiu exclus+ contradicţie

)(()()( CBAAACCCBBBAE contradicţie

= 0))(( CBACBA

4) ))()()()()(( ACCABACBCABAE

Soluţie:

47


Se utilizează identitatea : ABABA ))((

ABCACACCBCBBABAE )])()][()()][()([(

5) ABCCABCBACBABCACBAE

Soluţie terţiu

exclusBAABBBAAAB

ABBABACCABCCBACCBAE

)(

.)()(.)(.

6) CBACBACBACBACBAE Soluţie: terţiul exclus

BACAACCABBACACABCCBABBCAE )(.)()(. terţiul exclusabsorbţie

BACBAACBACACBACAC ..)1(...)(

7) .. ABCCABCBABCACBAE Soluţie: terţiul exclus absorbţie

ABCBACCCABA

CABACCACABBBACBBCAE

.)

.)()(

8) Să se aplice teorema lui De Morgan următoarelor expresii:

)( DCBAE Soluţie:

DCBADCBADCBAE .

DCBADCBAE Soluţie:

DCBADCBADCBAE DCBA

48

Proiectare logică

2.2. FUNCŢII LOGICE. CIRCUITE LOGICE.

Funcţii logice. Fie mulţimea Z={0,1}. O funcţie logică de n variabile este o aplicaţie definită pe Zn luând valori în Z

F:Zn→ZRealizând o corespondenţă biunivocă dintre mărimile

electrice ce caracterizează circuitul, pe de o parte , şi simbolurile 0 şi 1, pe de altă parte, se poate stabili funcţia reprezentată de circuitul logic. Varibila de intrare este semnalul electric de intrare iar valoarea funcţiei logice logice rezultă la ieşirea din circuit (este răspunsul circuitului).

Aşa cum pentru descrierea unor funcţii logice mai complexe sunt folosite expresii logice (construite din litere ce desemnează variabile şi simbolurile operaţiilor logice) pentru implementarea funcţiilor logice se vor folosi circuite obţinute prin conectarea unor circuite elementare ( porţi logice).

Funcţiile logice pot fi reprezentate prin prin tabele (tabele de adevăr ) care înscriu valoarea funcţiei pentru fiecare variabilă şi prin expresii logice. Ele descriu funcţionarea unui circuit elctronic logic.

Circuitele electronice se pot clasifica în două mari categorii:

-circuite analogice -circuite logiceCircuitele analogice sunt cele care utilizează semnalul

analogic, adică un semnal sub formă de unde într-o plajă de tensiuni {-u,+u}

Circuitele logice utilizează două semnale logice, 0 şi 1, fiecăruia corespunzându-i un anumit nivel de tensiune. Pentru primele circuite logice nivelele de tensiune erau:

49


0 logic tensiunea U E {0 V , 0,3 V}1 logic tensiunea U E {3,5 V , 5V}Circuitele logice sunt circuite electronice alimentate la o

sursă de tensiune, la intrarea cărora se aplică semnale electrice (tensiune sau curent) şi la ieşirea cărora se obţin răspunsuri electrice. Circuitele logice se împart în două categorii:

-circuite logice combinaţionale-circuite logice secvenţialeCircuitele combinaţionale sunt acele circuite care nu

memorează rezultatul la ieşire. Din această categorie fac parte porţile logice care stau la baza altor circuite combinaţionale mai complexe ca: decodoare, multiplicatoare, sumatoare, comparatoare etc.

Circuitele secvenţiale sunt acele circuite care memorează rezultatul final. Cel mai cunoscut circuit secvenţial este bistabilul care stă la baza unor circuite mai complexe ca numărătoare, registre de memorie, registre de deplasare stânga dreapta ş.a.

2.2.1.CIRCUITE LOGICE COMBINAŢIONALE. PORŢI LOGICE

Circuitele combinaţionale nu au memorie. Funcţionarea lor poate fi descrisă prin funcţii logice. Funcţiile logice elementare şi simbolurile circuitelor care le implementează se numesc generic porţi logice. Porţile logice sunt cele mai cunoscute circuite combinaţionale. .

O poartă logică este un dispozitiv electronic numeric elementar care implementează o funcţie logică elementară. Ea are una sau mai multe intrări digitale/binare, reprezentînd 0 logic sau 1 logic, şi are ca ieşire o funcţie simplă de aceste intrări.

50

Proiectare logică

Starea de potenţial ridicată are semnificaţia de 1. Aceasta este convenţia logic pozitivă. Pentru circuitele integrate se adoptă convenţia logic pozitivă. Cele mai utilizate porţi logice sunt:

Inversorul NU(NOT)Funcţia “NU” logic are următoarea interpretare:- ieşirea sa este adevărată (1 logic) dacă intrarea sa este falsă (0 logic)- ieşirea sa este falsă (0 logic) dacă intrarea sa este adevărată (1 logic).

xf

Poarta ŞI (AND) Funcţia “ŞI” logic are următoarea interpretare:- dacă cel puţin una din intrări se află în 0 logic, atunci ieşirea va fi în 0 logic- dacă ambele intrări sunt în 1 logic atunci ieşirea va fi în 1 logic.

yxf

Poarta SAU (OR)Funcţia “SAU” logic are următoarea interpretare:- ieşirea sa este adevărată (1 logic) dacă cel puţin una din intrări este adevărată (1 logic)- ieşirea sa este falsă (0 logic) dacă ambele intrări sunt false (0 logic).

yxf

x f

x

yf

x

y f

51


Poarta ŞI-NU (NAND)Funcţia “ŞI-NU” logic are următoarea interpretare:

- ieşirea sa este falsă (0 logic) dacă ambele intrări sunt adevărate (1 logic)- ieşirea sa este adevărată (1 logic) dacă cel puţin una din intrări este falsă (0 logic).

yxf .

Poarta SAU-NU (NOR)Funcţia “SAU-NU” logic are următoarea interpretare:- ieşirea sa este falsă (0 logic) dacă ambele intrări sunt adevărate (1 logic)- ieşirea sa este adevărată (1 logic) dacă cel puţin una din intrări este falsă (0 logic).

yxf

Poarta SAU-EXCLUSIVFuncţia SAU-EXCLUSIV are următoarea semnificaţie:-semnalează coincidenţa intrărilor prin ieşire falsă (0 logic);-realizează suma modulo-2 , .

f=x y

x

yf

x

y f

y

xf

52

Proiectare logică

Există şi porţi cu mai multe intrări dar funcţiile logice se pot implementa şi cu porţi cu numai două intrări

Sistemele logice combinaţionale, oricât de complicate ar fi, se realizează cu porţi logice elementare. O poartă logică elementară implementează o funcţie logică cu cel mult 2 intrări. Astfel, funcţiile elementare sunt “ŞI”, “SAU”, “NU”, “SAU-Exclusiv”, sau negările lor: “ŞI-NU”, “SAU-NU”. In practică, porţile logice sunt implementate sub forma de circuite integrate. Pe un circuit integrat se găsesc 1, 2, 3, 4, 6 porţi logice, în funcţie de numărul de intrări.

2.2.2.IMPLEMENTAREA FUNCŢIILOR LOGICE

O funcţie y=f(x1,x2,x3,…….xn) este o funcţie logică dacă domeniul de definiţie este reprezentat de produsul cartezian (0,1)n

, deci: f : (0,1)n → {0,1} Având în vedere această definiţie se poate spune că o

funcţie logică (booleană) pune în corespondenţă o combinaţie binară asociată produsului cartezian cu una din valorile 0 sau 1. Domeniul de definiţie al unei funcţii logice de n variabile este format din 2n puncte (combinaţii) , iar numărul de funcţii este de 2 la puterea 2n. De exemplu, cu două variabile se pot forma 16 funcţii .

Funcţiile logice pot reprezenta un circuit logic format din circuitele elementare (porţi logice). Implementarea unei funcţii se face printr-o schemă logică formată din porţi logice cu două intrări şi o ieşire. Există şi porţi cu mai multe intrări dar, în general, orice expresie logică poate fi implementată cu circuite SAU, ŞI , cu numai două intrări şi cu inversoare.

Un circuit electronic poate fi redat printr-o schemă bloc, o ecuaşi de funcţionare şi o schemă logică.

53


Exemple de implementări pentru expresii logice. Exemplul 1:

Să se implementeze un NAND cu 7 intrări cu:a) porţi ŞI cu două intrări şi inversoare.b) porţi SAU cu două intrări şi inversoare;

a)Soluţie:

7654321 xxxxxxxy Implementare cu porţi ŞI cu două intrări şi cu inversoare:

21 xx4321 xxxx

43 xx

65 xx

765 xxx

2

1

xx

4

3

xx

6

5

xx

7x

y

7654321 xxxxxxxy Soluţie: Aplicând formula lui de Morgan:

7654321 xxxxxxxy =

7

17654321

iixxxxxxxx

b) Implementare cu porţi SAU cu două intrări şi cu inversoare:

54

Proiectare logică

y

4321 xxxx

765 xxx

21 xx

43 xx 65 xx

7x

2

1

xx

4

3

xx

6

5

xx

7654321 xxxxxxxy Exemplul 2:

Să se reprezinte expresia 431421432321 xxxxxxxxxxxxy a)cu porţi ŞI cu două intrări şi cu inversoare;b)cu porţi SAU cu două intrări şi cu inversoare a)

431421432321 xxxxxxxxxxxx y

y

2

1

xx

3x

4x

4x

4x

3

2

xx

2

1

xx

3

1

xx

431 xxx

421 xxx

432 xxx

321 xxx432321 xxxxxx

431421 xxxxxx

y

Conform teoremei lui de Morgan:y= x1x2x3+x2x3x4+x1x2x4+x1x3x4

b)

55


321321 xxxxxx

432432 xxxxxx

421421 xxxxxx

431431 xxxxxx

y

3

2

1

xxx

4

3

2

xxx

4

2

1

xxx

4

3

1

ˆxxx

431421432321 xxxxxxxxxxxxy Exemplul 3:

Să se implementeze expresia:

))()()(( 431421432321 xxxxxxxxxxxxy a)cu porţi ŞI cu două intrări şi cu inversoare;

))()()(( 431421432321

431421432321

xxxxxxxxxxxxxxxxxxxxxxxy

56

Proiectare logică

y

2

1

xx

3x

4x

4x

4x

3

2

xx

2

1

xx

3

1

xx

y

xxxxxx 21321

432432 xxxxxx

421421 xxxxxx

431331 xxxxxx

))()()(( 431421432321 xxxxxxxxxxxx b)cu porţi SAU cu două intrări şi cu inversoare

))()()(( 431421432321

431421432321

xxxxxxxxxxxxxxxxxxxxxxxxy

(Conform teoremei lui de Morgan.)

57


321 xxx

321 xxx

432321 xxxxxx

421 xxx

431 xxx

431421 xxxxxx

y

3

2

1

xxx

4

3

2

xxx

4

2

1

xxx

4

3

1

xxx

2.3. FUNCŢII LOGICE. FORMA CANONICA

O funcţie logică (booleană) este o funcţie f(x1 ,x2 …..xn)

unde xi ={0,1} , i= n1 . Orice funcţie logică poate fi reprzentată în două moduri: prin expresii boleene şi prin tabele de adevăr.

Există patru forme de reprezentre funcţiilor logice:-Forma Canonică Disjunctivă FCD-Forma Canonică Conjunctivă FCC-Forma Normal Disjunctivă FND-Forma Normal Conjunctivă FNC FCD este o sumă de conjuncţii. Numărul variabilelor din

fiecare conjuncţie este egal cu numărul termenilor funcţiei.De exemplu:

4321432143214321

321321321321

),,,(),,(

xxxxxxxxxxxxxxxxfxxxxxxxxxxxxf

58

Proiectare logică

este un produs de disjuncţii. Numărul variabilelor din fiecare disjuncţie este egal cu numărul termenilor funcţiei.De exemplu:

))()((),,,())()((),,(

4321432143214321

321321321321

xxxxxxxxxxxxxxxxfxxxxxxxxxxxxf

FND este o sumă de conjuncţii. Numărul variabilelor din fiecare conjuncţie poate fi diferit denumărul termenilor funcţiei. FNDeste forma unei funcţii la care se ajunge după minimizare în forma de minimizare disjunctivă.De exemplu:

4314321

321321

),,,(),,(

xxxxxxxfxxxxxxf

FCD este un produs de disjuncţii în care numărul variabilelor sdin fiecare disjuncţie poate diferi .FNC este forma unei funcţii la care se ajunge după minimizare în forma de minimizare dijunctivă.

Termenii din FCD se mai numesc şi mintermi (mi) iar termenii din FCC se mai numesc maxtermi (Mi). De exemplu:

Tabelul 2.1f(x1,x2) Mintermi Maxtermi

213

212

211

210

xxmxxmxxmxxm

213

212

211

210

xxMxxMxxMxxM

f(x1,x2,x3)3210 xxxm

3211 xxxm

3212 xxxm

3213 xxxm

3214 xxxm

3215 xxxm

3216 xxxm

3217 xxxm

3210 xxxm

3211 xxxm

3212 xxxm

3213 xxxm

3214 xxxm

3215 xxxm

3216 xxxm

3217 xxxm

59


Realizarea fizică a formei FCD se face după următoarea regulă:

Forma Canonică Disjunctivă a unei funcţii (FCD) se obţine prin sumarea logică a conjuncţiilor corespunzătoare valorior de 1 ale funcţiei. Notând cu Qk conjuncţia elementară, avem_

FCD=

n

kk

n

kk QQ

11 (legea de Morgan) Realizarea fizică a Formei Canonice Conjunctive (FCC) se

face după regula:FCC a unei funcţii se obţine prin produsul logic al

disjuncţiilor corespunzătoare valorilor 0 ale funcţiei.Notând cu Dk disjuncţia elementară, avem:

FCC

n

k

n

kkk DD

1 1 (legea de Morgan)

n:21

n:21

n:21

1Q

2Q

nQ

yn

21

n

21

n

21

1D

2D

nD

y

FCD FCC Exemple:

Exemplul 1

1)Să se aducă la forma FCD şi FCC expresia 321. xxxy

60

Proiectare logică

Tabelul 2.2. Tabel de adevăr x1 x2 x3 E0 0 0 00 0 1 10 1 0 00 1 1 11 0 0 11 0 1 11 1 0 01 1 1 1

Forma canonică disjunctivă:

FCD= 321321321321321 .. xxxxxxxxxxxxxxx Forma canonică conjunctivă

FCC= ))()(( 321321321 xxxxxxxxx

y

3

2

1

xxx

3

2

1

xxx

3

2

1

xxx

3

2

1

xxx

FCD

y

3

2

1

xxx

3

2

1

xxx

3

2

1

xxx

FCC

61


Exemplul 2: Să se realizeze un dispozitiv numeric cu trei intrări şi o ieşire astfel încât să avem semnalul majoritar de la intrare Tabelul 2.3.Tabel de adevăr.

Funcţiile canonicee:

FCD= 321321321321 xxxxxxxxxxxx

FCC= ))()()(( 321321321321 xxxxxxxxxxxx

3

2

1

xxx

y

62

x1 x2 x3 y 0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 1

Proiectare logică

y

3

2

1

xxx

3

2

1

xxx

3

2

1

xxx

3

2

1

xxx

FCD

y3

2

1

xxx

3

2

1

xxx

3

2

1

xxx

FCC

3

2

1

xxx

Exemplul 3

Să se realizeze un dispozitiv numeric care să transforme codul 8421 în codul Exces 3 pe patru biţi.

Soluţie:Dispozitivul numeric va avea 4 intrări şi 4 ieşiri. Vom scrie

FCD şi FCC pentru fiecare coloană în parte, deci de patru ori.

63

Sorin Adrian Ciureanu Tabelul 2.4. Tabel de adevăr.

x1 x2 x3 x4 y1 y2 y3 y4

0 0 0 0 0 0 1 10 0 0 1 0 1 0 00 0 1 0 0 1 0 10 0 1 1 0 1 1 00 1 0 0 0 1 1 10 1 0 1 1 0 0 00 1 1 0 1 0 0 10 1 1 1 1 0 1 01 0 0 0 1 0 1 11 0 0 1 1 0 1 11 0 1 0 1 1 0 11 0 1 1 1 ] 1 01 1 0 0 1 1 1 11 1 0 1 0 0 1 01 1 1 0 0 0 0 11 1 1 1 0 0 1 0

43214321

4321432143214321432143211

xxxxxxxx

xxxxxxxxxxxxxxxxxxxxxxxxyFCD

43214321

4321432143214321432143212

xxxxxxxx


43214321

4321432143214321432143213

xxxxxxxx


43214321

4321432143214321432143214

xxxxxxxx


64

Proiectare logică

2.4 MINIMIZAREA FUNCŢIILOR LOGICE

Utilizarea formelor canonice de reprezentare a funcţiilor logice presupune un cost foarte mare datorat numărului mare de intrări în circuit. De aceea este necesar să se minimizeze funcţiile. A minimiza o funcţie înseamnă a-i micşora numărul de variabile de intrare.

Există mai multe metode de realizare a acestui scop dintre care cele mai cunoscute sunt:

-metoda KARNAUGH şi-metoda QUINE - MC CLUSKY.

2.4.1.METODA KARNAUGH

Metoda KARNAUGH pentru o funcţie de n variabile constă în aranjarea variabilelor într-un tabel de 2n „căsuţe”. Dispunerea căsuţelor se face în aşa fel încât căsuţele vecine să aibă coduri care diferă printr-un singur bit. Din acest motiv, codurile căsuţelor, pe orizontală şi pe verticală, sunt în cod Gray. Codul Gray este:

2 biţi00, 01, 11,103 biţi000, 001, 011, 010, 110, 111.101 ,100Fiecare căsuţă are un număr de căsuţe vecine egal cu

numărul variabilelor de intrare . Fizic, în tabel căsuţele vecine sunt adiacente pe orizontală sau pe verticală dar nu şi pe diagonlă. Tabelul trebuie privit ca o sferă unde prima şi ultima linie sunt vecine, la fel şi prima şi ultima coloană.

Regulele de minimizare sunt următoarele:Pentru forma disjunctivă FND: Se grupează celulele din

jurul lui 1 în grupe de puteri ale lui 2, adică 2,4,8,16,32….Întâi

65


se încearcă să se facă grupe de 1 cât mai mari, apoi, pe măsură ce înaintăm, încercăm cu valori cât mai mari; dacă o valoare de 1 este înconjurată doar de zerouri (sus, jos, dreapte, stânga) atunci valoarea respectivă rămâne neminimizată.

-Pentru a scrie termenul minimizat din grup se scriu acele variabile care au valoare comună, pe orizontală şi pe verticală, cx

dacă valoarea este 1 şi cx dacă este zero. Astfel, pentru o funcţie de 4 variabile, pot apărea următrtoarele situaţii:

- dintr-un grup de 8 de 1 , rămîne un termen (conjuncţie) de o variabilă;

- dintr-un grup de 4 de 1, rămâne un termen (conjuncţie) de 2 variabile;

- dintr-un grup de 2 de 1, rămâne un termen (conjuncţie) de 3 variabile;

- dintr-o singură valoare de 1 rămâne mintermenul de 4 variabile

Regula este că o variabilă din tablou poate fi ataşată la oricâte grupuri de 1, dar condiţia este ca orice variabilă să fie luată la minimizare cel puţin odată. Este posibil ca, în afară de valorile de 0 şi 1 , să avem şi valori indiferente(ori 0, ori 1) acestea notându-se cu x. Aceste valori pot fi ataşate grupurilor de 1 dar nu pot fi luate în considerare singure, adică un grup de x trebuie să conţină şi un 1.

Exemple1) Fie tabelul KARNAUGH:

x1x2

x3x400 01 11 10

00 1 1 0 001 1 1 1 1

66

Proiectare logică

11 1 1 0 010 1 1 0 0

Grupăm pe 1 din primele două coloane şi obţinem

termenul comun 1x . Grupăm pe 1 din linia doua şi obţinem

termenul comun 43.xx .

Deci funcţia va fi: 143. xxxy

2)Fie tabelul KARNAUGH pentru 4321 ,,( xxxxf )

x1x2

x3x400 01 11 10

0 0 x x 0

01 x 1 1 x11 x 1 1 x10 0 x x 0

- Din coloanele 2 şi 3 avem x2

- Din liniile 2 şi 3 avem x4

Deci : 42 xxy

3)Fie tabelul Karnaugh pentru o funcţie de 5 variabile f(x1,x2,x3,x4,x5)

000 001 011 010 110 111 101 100

67


00 1 1 x x 1 1 x 1

01 1 1 x x 0 0 0 111 1 1 x x 0 0 0 x10 1 1 x x 1 1 1 1

-Din primele 4 coloane rezultă 1x .-Din linia 1 şi linia 4 vecine rezultă 5x

-Din coloanele 1 şi 8 rezultă 32.xx

Deci: 325154321 ,,,( xxxxxxxxxf Pentru forma conjunctivă FNCRegulele sunt aceleaşi doar că aici se grupează 0-urile iar

dacă valorile comune sunt 0, se ia xi şi dacă sunt 1 se ia ix .Vom lua aceleaşi exemple ca la FND şivom scrie FNC.1)

x1x2

x3x400 01 11 10

00 1 1 0 001 1 1 1 1

11 1 1 0 010 1 1 0 0

)())(( 4311314 FNDlacaxxxxxxxyvitatedistributi

2)

68

4

3

2

1

xxxx

Y1

Y2

Y3

Y4

DN

Proiectare logicăx1x2

x3x400 01 11 10

00 0 x x 001 x 1 1 x

11 x 1 1 x

10 0 x x 0

42 xxy 3)

x1x2x3

x4x5000 001 01

1010 110 111 10

1100

1 1 x x 1 1 x 11 1 x x 0 0 0 11 1 x x 0 0 0 x1 1 x x 1 x 1 1

distributivitate

325131132 )())(( xxxxxxxxxxy

Aplicaţii ale minimizării KARNAUGH1) Să se proiecteze un dispozitiv numeric cu 4 comutatoare

astfel încât când se apasă simultan două dintre ele becul să se aprindă.

69


Tabelul 2.5. Tabel de adevăr.x1 x3 x3 x4 y 0 0 0 0 00 0 0 1 00 0 1 0 00 0 1 1 10 1 0 0 00 1 0 1 10 1 1 0 10 1 1 1 11 0 0 0 01 0 0 1 11 0 1 0 11 0 1 1 11 1 0 0 11 1 0 1 11 1 1 0 11 1 1 1 1

x1x2

x3x400 01 11 10

00 0 0 1 001 0 1 1 1

11 1 1 1 1

70

Proiectare logică

10 0 1 1 1

eFCD xxxxxxxxxxxxy 14123242143 ))()()(( 431321421432 xxxxxxxxxxxxyFCC

Se calculează şi FCDy şi FCCy şi apoi se face costul pentru fiecare formă şi se alege costul minim.

))()()()()(( 424143323121 xxxxxxxxxxxxyFCD

321431421432 xxxxxxxxxxxxyFCC

ŞI SAU NU C

FCDy 12 6 0 18

FCCy 4 12 0 16

FCDy 6 12 4 22

FCCy 12 4 4 20

FCCy are costul minim 2)Să se proiecteze un dispozitiv numeric care să scoată la ieşire complementul faţă de 2

Tabelul 2.6. Tabel de adevăr.x1 x2 x3 x4 T1 T2 T3 T4

0 0 0 0 0 0 00 0 0 1 1 1 1 10 0 1 0 1 1 1 0

71


0 0 1 1 1 1 0 10 1 0 0 1 1 0 00 1 0 1 1 0 1 10 1 1 0 1 0 1 00 1 1 1 1 0 0 11 0 0 0 1 0 0 01 0 0 1 0 1 1 11 0 1 0 1 0 1 01 0 1 1 0 1 0 11 1 0 0 0 1 0 11 1 0 1 0 0 1 11 1 1 0 0 0 1 01 1 1 1 0 0 0 1

Tabelele Karnaugh sunt:T4

x3x4

x1x200 01 11 10

00 0 1 1 0

01 1 1 1 111 1 1 1 110 0 1 1 0

T4=x1

T3

72

Proiectare logicăx3x4

x1x200 01 11 10

00 0 1 0 101 0 1 0 110 0 1 0 111 0 1 0 1

212213 1

xxxxxxT

T2

x3x4

x1x200 01 11 10

00 0 1 1 1

01 1 0 0 011 1 0 0 010 0 1 1 1

TxxxxxxxxxxxxxxxxT 42142142142121422 )(.)()(

T1 x3x4

x1x200 01 11 10

00 0 1 1 101 1 1 1 111 0 0 0 010 1 0 0 0

)()()(

4213

1243124343214331421

xxxxxxxxxxxxxxxxxxxxxxT

Dispozitivul numeric este:

73

2n:1


3)Să se proiecteze un dispozitiv numeric cu 4 intrări care să scoată la ieşire votul majoritar.

Vom face direct tabelul Karnaugh.x1x2

x3x400 01 11 10

00 0 0 x 0

01 0 x 1 x

11 x 1 1 110 0 x 1 x

32424321 xxxxxxxxyFCD

))()()(( 421321243143 xxxxxxxxxxxxyFCC

))()()( 32424321 xxxxxxxxyFCD

421321432431 xxxxxxxxxxxxyFCC

ŞI SAU NU costFCD 8 4 0 12FCC 4 12 O 16FCD 4 8 6 20

74

Proiectare logică

FCC 12 3 12 24 FCD are costul minim.

2.4.2.METODA QUINE-Mc CLUSKEY

Metoda Quine-Mc Cluskey este o metodă algebrică de minimizare a funcţiilor boolene folosite în cazul unui număr mare de variabile, pentru care diagramele Karnaugh devin greu de utilizat. Metoda se pretează programării unui calcul automat de minimizare. Minimizarea are loc în 2 paşi:

a) Stabilirea implicanţilor primi.b) Calculul acoperirii minimale pentru funcţia respectivă.1. Implicanţi primi.Un implicant este un produs logic care derivă dintr-un grup

de mintermi care au proprietatea de a avea o parte comună şi o altă parte care asumă toate combinaţiile posibile. ( mintermii sunt termenii formei canonice disjunctive –FCD- a unei funcţii logice). De exemplu:

IMPLICANTunestezywxxzywzyxwzyxw )(

Implicanţii pot deriva din grupe de 2,4.8.16 mintermi. Cu cât grupa de mintermi este mai mare cu atât mai mare va fi minimizarea. Grupa de mintermi majoră este cea care nu este conţinută de nici o altă grupă. Un implicant care derivă dintr-o grupă majoră se numeşte implicant prim. Un implicant prim este deci un implicant care nu este conţinut în nici un alt implicant major (de dimensiuni mai mari)

75


PRIMIMPLICANTunestezyzywxxwxwxwzy

ywxzyxwzyxwzyxw

)(

Funcţia obţinută prin însumarea tuturor implicanţior primi nu este însă cea mai simplă posibil. Suma minimă trebuie să conţină numai implicanţi primi dar nu toţi implicanţii primi. Se aleg numai implicanţii esenţiali. Un implicant prim esenţial este un implicant prim care are cel puţin un miniterm neconţinut în alt implicant prim.

Utilizând reprezentarea geometrică a numerelor binare într-un spaţiu n-dimesional prin cuburi n-dimensionale, pentru un cub 3-dimensional vor fi subcuburi 2-dimensionale, subcuburi 1-dimensionale şi subcuburi 0-dimensionale Sub această formă se reprezintă,în mod obişnuit, numerele binare în minimizarea funcţiilor booleene prin metoda Quine-McCluskey.

Îngeneral, configuraţiile binare sunt reprezentate prin n-cuburi în spaţiul n-dimensional (hipercub). Construcţia unui n-cub este o operaţie recursivă în care se proiectează copia unui n-cub şi se adaugă un 0 la toţi identificatorii cubului de plecare. Apoi se permută un 1 la toţi identificatorii cubului proiectat.

Se sustituie valorile bitului de intrare (wxyz) cu valorile de ieşire a funcţiei f. Prin unirea punctelor în care funcţia are valoarea 1 se obţin subcuburi care dau mulţimea implicanţilor. Din subcubul cu dimensiunea cea mai mare se obţin impicanţii primi.

Orice vârf al unui n-cub este legat de n vârfuri. De exemplu,orice vârf al unui 2-cub este legat de 2 vârfuri, orice vârf al unui 3.cub este legat de 3 vârfuri ş.a.m.d. Un r-subcub al unui n-cub este un ansamblu de 2r puncte, cu n-r biţi corespunzători, în timp ce alţi biţi asumă toate configuraţiile posibile. De exemplu un 2-cub (subcub al unui 3-cub) este un ansamblu de 22 = 4 puncte şi 3-2=1bit corespunzător.

76

Proiectare logică

Forma canonică disjunctivă a funcţiei f este:

wxzwxyzywxyzzwxyzyxwzyxwzyxwzyFCD Funcţia obţinută nu este cea mai simplă formă. Suma

minimă trebuie să conţină numai imprimanţi primi dar nu toţi imprimanţii primi. Se aleg imprimanţii primi esenţiali, adică acei imprimanţi primi care conţin cel puţin un miniterm neconţinut în alt imprimant prim. Forma minimă va fi :

wxyzy

77


Să substituim în cubul 4-dimensional configuraţiile bitului de intrare (wxzy) cu valoarea funcţiei f la ieşire. Unind vârfurile în care funcţia f la ieşire are valoarea 1 şi obţinem 3 subcuburi ( un 2-subcub şi două 1-subcuburi.

Din subcuburile în care vârfurile au valoarea 1 derivă grupa de mintermi din care se obţin Implicanţii .

Din subcuburile de dimensiuni mai mari se obţin implicanţii primi.

2. Acoperire minimală a unei funcţiiO acoperire a unei funcţii vectoriale este o mulţime (listă)

de implicanţi care conţin (acoperă) minterminii acelei funcţii. Mărimea(cardinalitatea) unei acoperiri este numărul său de implicanţi.

O acoperire minimă este o acoperire de cardinalitate minimă. Obiectivul minimizării logice combinaţionale exacte este tocmai determinarea unei acoperiri minime.

O acoperire iredundantă este o acoperire care nu este un superset propriu al niciunei alte acoperiri penntru aceeaşi funcţie.

78

Proiectare logică

O acoperire este minimală în raport cu conţinerea singulară dacă nici un implicant nu este conţinut în orice alt implicant al acoperirii-

Stabilirea implicanţilor primi.În acest scop se parcurg următorii paşi:Pasul 1 Se porneşte de la forma canonică disjunctivă.

Fiecare termen canonic este reprezentat sub formă de număr binar, prin n-uplul de zerouri şi unităţi, corespunzătoare termenului respectiv.

Pasul 2 Termenii canonici astfel scrişi se împart în grupe, în funcţie de ponderea acestora, adică numărul de 1 din n-uplul respectiv.

Pasul 3 Grupele de termeni canonici sunt aranjate pe o coloană, în ordine crescătoare a ponderilor. Acest lucru este util deoarece doi termeni canonici se pot asocia formând un cub 1-dimensional numai dacă fac parte dintr-un grup ale căror ponderi diferă cu o unitate.

Pasul 4 Se compară fiecare termen al unei grupe cu toţi termenii unei grupe de pondere mai mare cu o unitate. Dacă numerele binare respective sunt adiacente, cei doi termeni se pot asocia formând un subcub 1-dimensional, notat printr-un număr binar care are pe poziţia prin care cei doi termeni diferă un x, ceea ce înseamnă că variabila corespondentă acelei poziţii lipseşte.

Cei doi termeni care au format subcubul 1-dimensional se bifează iar iar termenul normal care reprezintă subcubul rezultat se înscrie pe o nouă coloană. Toţi termenii normali (subcuburile 1-dimensionale) rezultaţi în urma comparării a două grupe din coloana termenilor canonici formează o grupă în coloana subcuburilor 1-dimensionale. Prin urmare această coloană va conţine, în cazul general, cu o grupă mai puţin decât coloana termenilor canonici (cuburi 0-dimensionale).

Pasul 5 Se ia r=1. Se compară fiecare termen al unei grupe din coloana subcuburilor r-dimensionale cu toţi termenii grupei

79


cu pondere mai mare cu o unitate. Pentru ca 2 asemenea termeni să se poată asocia formând un subcub (r+1)- dimensional, trebuie ca în ambii termeni simbolul x să fie pe aceleaşi poziţii. Doi termeni care îndeplinesc această condiţie şi sunt adiacenţi se asociază şi formează un subcub (r+1)-dimensional care se notează cu un număr binar. În acest număr apare încă un x pe poziţia prin care cei doi termeni diferă. Termenii care formează acest subcub se bifează, iar subcubul (r+1) dimensional se înscrie pe o nouă coloană. În general, această c0oloană are cu o grupă mai puţin decât coloana subcuburilor r-dimensionale. Dacă se obţine de mai multe ori un anumit termen, acesta se consideră o singură dată.

Pasul 6 Se măreşte r cu o unitate şi se repetă pasul 5 până cînd subcuburile ultimei coloane nu se mai pot asocia în scopul formării unui subcub de dimensiune superioară.În acest monent prima etapă a algoritmului Quine-McCluskey este încheiată. Termenii rămaşi nebifaţi în coloanele rezultate formează grupul implicanţilor primi în funcţia considerată.

Exemplul 1.

Să se minimizaze funcţia de cinci variabile, dată sub forma canonică disjunctivă

(FCD): 30,29,28,26,23,19,18,15,14,12,10,8,7,4,3,0

,,,,)( 54321

k

mxxxxxxfki

i

În tabelul următor sunt date operaţiunile descrise anterior.

80

Proiectare logică

Tabelul 2.7Subcuburi

0-dimensiuniSubcuburi

1-dimensiuneSubcuburi

2-dimensiuni

Gru

pa In

dici

x1 x2 x3 x4 x5

Gru

paIn

dici

x1 x2 x3 x4 x5

Gru

paIn

dici

x1 x2 x3 x4 x5

0 0 0 0 0 0 x 0 0,40,8

0 0 x 0 0 x0 x 0 0 0 x

0 0,48,120,84,12

0 x x 0 0

(0 x x 0 0)

1 48

0 0 1 0 0 x0 1 0 0 0 x

1 4,128,108,12

0 x 1 0 0 x0 1 0 x 0 x0 1 x 0 0 x

1 8,1012,14 8,1210,14

0 1 x x 0

(0 1 x x 0)

2 3101218

0 0 0 1 1 x0 1 0 1 0 x0 1 1 0 0 x1 0 0 1 0 x

2 3,73,113,1910,1110,1410,2612,1412,2818,1918,26

0 0 x 1 1 x0 x 0 0 1 x0 1 0 1 1 x0 1 0 1 x x0 1 x 1 0 xx 1 0 1 0 x0 1 1 x 0 xx 1 1 0 0 x1 0 0 1 x x1 x 0 1 0 x

2 3,711,15 3,719,23 3,11 7,15 3,19 7,2310,1114,1510,1426,3010,2614,3012,1428,3012,2814,30

0 x x 1 1

x 0 x 1 1

(0 x x 1 0)

(x 0 x 1 1)

0 1 x 1 1

x 1 x 1 0

(x 1 x 1 0)

x 1 1 x 0

(x 1 1 x 0)

3 71114192628

0 0 1 1 1 x0 1 0 1 1 x0 1 1 1 0 x1 0 0 1 1 x1 1 0 1 0 x1 1 1 0 0 x

3 7,15 7,2311,1514,1514,3019,2326,3028,2928,30

0 x 1 1 1 xx 0 1 1 1 x0 1 x 1 1 x0 1 1 1 x xx 1 1 1 0 x1 0 x 1 1 x1 1 x 1 0 x1 1 1 0 x x1 1 1 x 0 x

4 15232930

0 1 1 1 1 x1 0 1 1 1 x1 1 1 0 1 x1 1 1 1 0 x

81


După aplicarea regulilor de găsire a implicanţilor primi ai funcţiei, rezultă:

532542421542541321

43215431432154321 ),,,,(xxxxxxxxxxxxxxxxxx

xxxxxxxxxxxxxxxxxf

Această expresie se obţine inlocuind în termenii rămaşi ne bifaţi în tabel, zerourile cu variabilele corespunzătoare poziţiei respective, unităţile cu variabilele poziţiei respective negate, unităţile cu variabilele poziţiei respective nenegate şi omiţând variabilele corespunzăzoare poziţiilor pe care apare x. Pentru a găsi forma minimă disjunctivă a unei funcţii trebuie aleşi numai acei implicanţi primi care includ toţi termenii canonici ai funcţiei şi conduc la la o formă a funcţiei realizată cu cost minim. Implicanţii primi care respectă această condiţie formează acoperirea cu cost minim. Pentru a afla acoperirea cu cost minim trebuie căutate toate acoperirile pentru funcţia dată din care se alege acoperirea care îndeplineşte condiţia de cost minim faţă de un anumit criteriu de cost. Costul Cn se defineşte ca fiind suma costurilor implicanţilor primi din acoperirea considerată. Costul unui implicant prim al unei funcţii de n variabile, din care lipsesc r variabile, adică un subcub r-dimensional, este n-r, deoarece fiecare variabilă necesită un contact.. Atunci costul acoperirii este dat de relaţia:

1

0

),(n

rrn rngC

Unde gr este numărul grupurilor r-dimensionale din acoperirea consideratăş iar însumarea se face pentru toate subcuburile de dimensiune 0< r < n . Costul Cn al unei acoperiri este minim atuci cînd suma costurilor implicanţilor primi este minimă.

În cazul circuitelor de comutare cu porţi, costul circuitelor este în general cu atât mai mic cu cât numărul de porţi este mai mic, iar porţile respective au un număr cât mai mic de intrări. Acesta este costul minim Cn . Din acest motiv, atunci cînd funcţia

82

Proiectare logică

se realizează cu porţi, se alege acoperirea cu costul Cp definit de relaţia :

1

0

1

0

1

0

)1()(n

r

n

r

n

rrrp rngrgrngpCRC

care este minim. În relaţia de mai sus, p este numărul implicanţilor primi ai acoperirii. De obicei acoperirea cu număr minim de elemente satisface atât condiţia de Cn minim cât şi condiţia de Cp minim. Algoritmul de obţinere a acoperirii cu cost minim, plecând de la mulţimea implicanţilor primi, obţinuţi în etapa anterioară, este următorul :

a)Se construieşte un tabel al implicanţilor primi, având drept cap de linie implicanţii primi ai funcţiei şi cap de coloană termenii canonici ai funcţiei. La intersecţia dintre o linie şi o coloană se pune un semn, de exemplu un asterisc, dacă implicantul prim de pe linia respectivă include termenul canonic de pe coloana respectivă.

Tabelul 2.8.Implicanţi primix1 x2 x3 x4 x5

Indici Termeni canonici Obs.0 4 8 3 10 12 18 7 11 14 19 26 28 15 23 29 30

1 0 0 1 x (18,19) * *2 x 0 1 0 (18,26) * *1 1 1 0 x (28,29) * *0 x x 0 0 (0,4,8,12) * * * *0 1 x x 0 (,8,10,12,14) * * * *0 x x 1 1 (3,7,11,15) * * * *x 0 x 1 1 (3,7,19,23) * * * *0 1 x 1 x (10,11,14,15) * * * *x 1 x 1 0 (10,14,26,30) * * * *x 1 1 x 0 (12,14,28,30) * * * *

b) Se inspectează tabelul construit la punctul a). Dacă pe o anumită coloană există un singur semn, ceea ce înseamnă că termenul canonic din acea coloană este inclus într-un singur implicant prim, atunci implicantul prim de pe linia insemnată devine jmplicant prim esenţial şi intră obligatoriu în forma minimă a funcţiei. Se construieşte un nou tabel, al implicanţilor neesenţiali, care rezultă eliminând din tabelul implicanţilor primi

83


implicanţii primi esenţiali şi coloanele cu termenii canonici incluşi în exact . De asemenea, se elimină liniile pe care nu au mai rămas semne şi coloanele care au semne pe aceleaşi rânduri ca şi o altă coloană din tabelul implicanţilor primi neesenţialui, adică dacă mai mulţi termeni canonici sunt incluşi în aceiaşi implicanţi primi neesenţiali se reţine un singur reprezentant al acestora, deoaece orice implicant care îl include pe acesta va include automat şi pe cei omişi.

Tabelul 2.9Nr.

Implicanţi primi

x1 x2 x3 x4 x5

Indici Termeni canonici Obs.10 18 11 14 26 30

1 1 0 0 1 x (18,19) *2 1 x 0 x 0 (18,26) * * A3 0 1 x x 0 (8,10,12,14) * *4 0 x x 1 1 (3,7,11,15( *5 0 1 x 1 x (10,11,14,15

)* * A

6 x 1 x 1 0 (10,14,26,30)

* * * * A

7 x 1 1 x 0 (12,14,28,30)

* *

c)Se inspectează tabelul implicanţilor primi neesenţiali în scopul găsirii unei acoperiri cu cost Cp minim, pentru toţi termenii canonici rămaşi în tabel. În unele cazuri se pot găsi mai multe acoperiri care satisfac această condiţie,fiecare având acelaşi cost. În acest caz funcţia are mai multe forme minime disjunctive.

d)Făcând suma booleană a implicanţilor primi esenţiali găsiţi la punctul b) şi a celor neesenţiali făcând parte din acoperirea obţinută la punctul c) se obţine forma minimă disjunctivă a funcţiei date.

Pentru exemplul considerat anterior, funcţia dată prin expresia (2.21), se obţine tabelul implicanţilor primi din tabelul 2.8. Inspectând acest tabel se obţin implicanţii primi esenţiali

5425414321 ,, xxxxxxxxxx

84

Proiectare logică

După eliminarea termenilor canonici acoperiţi de aceşti implicanţi primi se obţine tabelul implicanţior primi neesenţiali 2.9. Luând implicanţii de pe rândurile marcate cu A,

5424215431 ,, xxxxxxxxxxse obţine acoperirea minimală căreia îi corespunde forma minimală disjunctivă a funcţiei:

),,,,( 54321 xxxxxf 5425414321 xxxxxxxxxx 5424215431 , xxxxxxxxxx Analizând tabelul 2.9. rezultă că mai există şi alte acoperiri

minimale pentru această funcţie. Penru găsirea acestora se foloseşte următorul algoritm:

a)Se împarte mulţimea implicanţilor primi esenţiali în submulţimi Mi stfel încât elementele unei submulţimi să conţină toţi implicanţii primi neesenţiali care includ termenul canonic cu indicele i. Notând implicanţii primi neesenţiali din tabelul 2.9 cu numărul lor de ordine, rezultă submulţimile:

7,6;6,2

;7,6,5,35,4;2,1;6,5,3

3026

14111810

MMMMMM

b)Se alcătuieşte cu elementele mulţimilor Mi expresia formală în care suma se interpretează ca operaţie logică SAU iar produsul ca operaţie logică ŞI

)76)(62)(7653)(54)(21)(653( Ec)Efectuând calculele. Ţinând seamade faptul că i+i=i şi că

i(i+j)=1, unde işi j sunt elemente ale mulţimilor Mi , se obţine o nouă formă a expresiei E, o sumă de produse.Fiecare din aceste produse de implicanţi primi reprezintă una din acoperirile mulţimii termenilor canonici din tabela implicanţilor primi neesenţiali. Expresia devine:

6.1.5.74.6.1.5.72.5.72.5.74.2.5.75.6.1.3.75.2.3.75.6.14.6.15.2.64.2.6)5.6.14.6.15.24.2)(5.73.76()54)(6.12)(53)(76()76)(62)(54)(21)(653(

E

d) Se ia forma minimală a expresiei precedente în care intră

85


numai produse cu cost minim.Termenii acestei expresii reprezintă acoperirile cu cost minim. Forma minimală, considerând costul CR . este:

2.5.75.6.14.6.1.5.2.64.2.6min EAceastă expresie conţine cele cinci acoperiri cu cost Cn

minim ale tabelului 2.9.Costul fiecărei acoperiri este 10.Deoarece fiecare din cele cinci acoperiri are acelaşi număr de elemente, ele au acelaşi cost Cp .

86

Proiectare logică

CAPITOLUL 3

3. CIRCUITE LOGICE

3.1.CIRCUITE LOGICE COMBINAŢIONALE

Circuitele combinaţionale sunt acele circuite logice care nu memorează rezultatul la ieşire. Din categoria lor fac parte porţile logice care stau la baza altor circuite mai complexe ca: multiplexoarele şi demultiplexoarele, codificatoarele şi decodificatoarele, comparatoarele, circuitele aritmetice combinaţionale etc

.3.1.1. MULTIPLEXOARE

Un circuit multiplexor (MUX) este un circuit care are rolul de a pune la ieşire (E) una dintre cele 2n intrări ( I0 , I1 ,……I2

n-1) selectate de cele n intrări de selecţie (S0 , S1 ,…….Sn-1). Codul binar al selecţiei S va selecta intrarea ce va fi pusă la ieşire.

1:2n

3210 IIII

1

1

0

nS

SS

E

12 nI

87


Fig.3.1.Schema bloca unui multiplexor.

Selectarea intrării se face printr-un cuvânt de adresă.Un multiplexor poate avea 2n intrări şi o ieşire. Se notează cu

MUX(2n : 1). Multiplexoarele , numite pe scurt MUX pot fi privite drept un mod rapid de a selecta o ieșire dintr-un număr de semnale. Un circuit de tip MUX are un set de intrări de adresare (în număr de n), un set de intrări de date (în număr de 2n) și o ieșire. Mai există uneori și o intrare de validare a funcționării (activă pe 0) și o ieșire care reprezintă semnalul selectat complementar (valabil pentru circuite digitale)

Exemple:Multiplexor cu două intrări (MUX 2 : 1)

1:

0I

E0S

1I

2

0

0

S

I

0

1

SI E

Ecuaţia de funcţionare este: 1000 ISISE Fig. 3.2.Schema bloc, schema logică şi ecuaţia

de funcţionare a unui MUX(2:1).Multiplexor cu patru intrări MUX (22 : 1)

3210 IIII

1

0

SS

E1:22

Ecuaţia de funcţionare este:

301201101010 ISSISSISSISSE

88

Proiectare logică

Fig.3.3. Schema bloc şi ecuaţia de funcţionare a unui MUX (22 : 1)

3I

E

0S1S

0I

1I

2I

Fig. 3.4..Implementarea unui MUX (22 : 1)

Multiplexor cu 8 intrări MUX (23 : 1)

1:23

76543210 IIIIIIII

2

1

0

SSS

E

Ecuaţia de funcţionare este:

70126012

501240123012201210120012

ISSSISSS

ISSSISSSISSSISSSISSSISSSE

89


Fig. 3.5. Schema bloc şi ecuaţia de funcţionare a unui MUX (23 : 1)

E

0

0

1

2

ISS

S

1

0

1

2

ISS

S

2

0

1

2

IS

SS

3

0

1

2

ISSS

4

0

1

2

IS

S

S

5

0

1

2

ISS

S

6

0

1

2

IS

S

S

7

0

1

2

ISSS

Fig.3.6.Implementarea unui MUX (23 : 1)

3.1.2.DEMULTIPLEXOARE

Un demultiplexor, DEMUX(2n : 1), este un circuit logic combinaţional care are rolul de a pune în legătură o intrare I cu o ieşire dintre cele 2n (E0,E1,E2,……….En-1), selectată de codul generat de intrările de selecţie (S0,S1,S2.........Sn-1).

n2:1

I

1

1

0

nS

SS

1210 ............ nEEE

90

Proiectare logică

Fig.3.7Schema bloc a unui demultiplexor.

Exemple de demultiplexoare:Demultiplexor cu două ieşiri DEMUX (1:2)

I

2:10S

10 EE

I

I

0E

0S

1EEcuaţiile de funcţionare, pentru fiecare ieşire, sunt:

ISEISE o 010

Fig.3.8.Schema bloc, schema logică şi ecuaţiile de funcţionare ale unui DEMUX(1:2)

Demultiplexor cu patru ieşiri [DEMUX ((1:22)]

22:1

I

1

0

SS

3210 EEEE

91


Ecuaţiile de funcţionare ale celor patru ieşiri sunt:ISSEISSE 011010 ISSEISSE 013012

3210 EEEE

10SS 10SS 10SS 10SS

I

Fig.3.9.Schema bloc; euaţiile de funcţionare şi schema logică ale unui demultiplexor cu patru ieşiri

Demultiplexor cu opt ieşiri [DEMUX (1:23)]

32:1DEMUX

76543210 EEEEEEEE

I

2

1

0

SSS

Ecuaţiile de funcţionare ale celor opt ieşiri sunt:

ISSSEISSSEISSSESSSE

ISSSEISSSEISSSEISSSE

1127012601250124

0123012201210120

Fig.3.10.Schema bloc şi ecuaţiile de funcţionare ale unui demultiplexor cu opt ieşiri

92

Proiectare logică

2

0

1

SS

S

2

0

1

SSS

2

0

1

SSS

2

0

1

SSS

2

0

1

S

S

S

2

0

1

SSS

2

0

1

S

SS

0

1

2

S

SS

I

2E

4

3

E

E

6

5

E

E

7E

1E

0E

Fig.3.11. Implementarea unui demultiplexor cu opt ieşiri

93


3.1.3.APLICAŢII ALE MULTIPLEXOARELOR ŞI DEMULTIPLEXOARELOR

Există mai multe aplicaţii ale multiplexoarelor şi ale demultiplexoarelor în sistemele de calcul, cum ar fi:

a)Comutarea mai multor surse de informaţii către o singură destinaţie.

b)Implementarea funcţiilor logice.c)Conversia paralel/serie a datelor, aplicând datele în

paralel la intrările de date şi modificând succesiv codul selecţiei.

d)Realizarea magistralelor de transmitere a informaţiilor.a) Comutarea mai multor surse de informaţii către o

singură destinaţie.Fie numerele pe patru biţi:A=A0A1A2A3 B=B0B1B2B3 C=C0C1C2C3 D=D0D1D2D3

Să se realizeze un circuit din MUX-uri care să poată dirija unul din cele patru numere către ieşire.

Soluţie: Deoarece numerele sunt pe patru biţi, vom utiliza 4 MUX-uri (4:1), iar selecţia numerelor se va face cu semnalele S0

şi S1 legate în comun pentru cele patru mux-uri. Vom forma cuvântul cu numărul transmis iar în fiecare mux vor intra cele patru cifre binare de pondere i (AiBiCiDi) cu i={0,1,2,3}.

94

Proiectare logică

)1:4(MUX )1:4(MUX )1:4(MUX )1:4(MUX

0000 DCBA 1111 DCBA 2222 DCBA 3333 DCBA

10SS

0E 1E 2E 3E

unde:

S0S1 E0 E1 E2 E3

00 A0 A1 A2 A3

01 B0 B1 B2 B3

10 C0 C1 C2 C3

11 D0 D1 D2 D3

Fig. 3.12.Schema bloc şi tabelul de funcţionare a unui circuit logic pentru comutarea mai multor surse de

informaţie către o singură destinaţie

b)Implementarea funcţiilor logige.La baza metodei de proiectare a funcţiilor logice doar cu

MUX-uri stă teorema de expansiune a lui Shanon. Este dată sub două forme:

1)-F(x1, x2, x3………xn) = F(0,x2…..xn). 1x +F(1,x2….xn).x1

2)-F(x1,x2……xn) =F(1,x2…..xn)+ x

1 ). (F(0,x2…..xn)+x1)

95

Sorin Adrian CiureanuForma 1) se aplică pentru forma disjunctivă şi forma 2) se

aplică pentru forma conjunctivă.Exemplul 1

Să se implementeze funcţia de trei variabile:321321 ),,( xxxxxxfy

Aplicăm teorema lui Shanon:132132321 ),1(.).,,0()( xxxfxxxfxxxf

Aplicăm din nou teorema lui Shanon fiecăreia dintre cele două funcţii:

213213213213 ),1,1(),0,1(.),1,0(),0,0( xxxfxxxfxxxfxxxfy

Rezultă:

1.11),1,1(1.01),0,1(

.10),1,0(0.00),0,0(

33

33

333

33

xxfxxf

xxxfxxf

Vom implementa funcţia f(x1,x2,x3) cu ajutorul unui MUX (4:1) în care pe selecţii punem primele două variabile iar pe cele patru intrări punem cele patru funcţii rezultate din teorema lui Shanon.

01 Sx

12 Sx y

00 I 31 xI 12 I 13 I

Fig.3.13. Schema bloc a unui MUX(4:1) pentru implementarea unei funcţii logice de trei variabile.

96

Proiectare logică

Exemplul 2

Fie funcţia :

43214321 ),,,( xxxxxxxxf

Aplicăm teorema lui Shanon:

21432143

214321434321

),1,1(),0,1(),1,0(),,0,0()(

xxxxfxxxxfxxxxfxxxxfxxxxf

Aplicăm încă odată teorema lui Shanon:

32143214

32143214

32143214

321432144,321

),1,1,1(),9,1,1(),1,0,1(),0,0,1(),1,1,0(),0,1,0(

),1,0,0(),0,0,0(),,,(

xxxxfxxxxfxxxxfxxxxfxxxxfxxxxf

xxxxfxxxxfxxxxf

unde;

1),1,1,1(1),1,1,0(1),0,1,1(1),0,1,0(1),1,0,1(1),1,0,0(1),0,0,1(),0,0,0(

44

44

44

444

xfxfxfxfxfxfxfxxf

Alegem pentru implementare un MUX(8:1.

97


1:8MUX

11111114x

23

12

01

SxSxSx

Y

Fig.3.14. Schema bloc a unui MUX (8>10) pentru implementarea unei funcţii logice de patru variabile.

3.1.4.CODIFICATOARE

Codificatoarele sunt circuite logice combinationale cu n intrări si m ieşiri de adresă, folosite pentru a realiza conversia unui număr

zecimal in cod binar sau BCD.

Codificatorul de adresă simplu furnizeaza la ieşire un cuvânt binar de m biţi atunci când numai una din cele n intrări ale sale

este activată. Numărul de cuvinte rezultate la ieşire este n=2m-1 si este egal cu numărul de intrări.

Fig.3.15.Schema bloc a unui codificator.

Exemplu - Codificator de adresă cu n=7 =>m=3 biti

98

Proiectare logicăTabel de adevăr

Intrări IeşiriI1 I2 I3 I4 I5 I6 I7 A2 A1 A0

1 0 0 0 0 0 0 0 0 10 1 0 0 0 0 0 0 1 00 0 1 0 0 0 0 0 1 10 0 0 1 0 0 0 1 0 00 0 0 0 1 0 0 1 0 10 0 0 0 0 1 0 1 1 00 0 0 0 0 0 1 1 1 1

Iesiri rezultate: A0 = I1 + I3 + I5 + I7 A1 = I2 + I3 + I6 + I7

A2 = I4 + I5 + I6 + I7

7654321 IIIIIII

2

1

0

A

A

A

Fig. 3.16.Implementarea unui codificator de adresă cu trei ieşiri

Codificator zecimal-BCD La activarea unei intrări apare la ieşire codul BCD al cifrei corespunzătoare intrării activate. De exemplu: la activarea intrării I5 la ieşire va apare codul 0101.

Tabel de adevăr

I0 I1 I2 I3 I4 I5 I6 I7 I8 I9 D C B A

1 0 0 0 0 0 0 0 0 0 0 0 0 0

99


0 1 0 0 0 0 0 0 0 0 0 0 0 1

0 0 1 0 0 0 0 0 0 0 0 0 1 0

0 0 0 1 0 0 0 0 0 0 0 0 1 1

0 0 0 0 1 0 0 0 0 0 0 1 0 0

0 0 0 0 0 1 0 0 0 0 0 1 0 1

0 0 0 0 0 0 1 0 0 0 0 1 1 0

0 0 0 0 0 0 0 1 0 0 0 1 1 1

0 0 0 0 0 0 0 0 1 0 1 0 0 0

0 0 0 0 0 0 0 0 0 1 1 0 0 1

97531 IIIII

A

7642 IIII

B D

98 II7654 IIII

C

Fig.3.17. Implementarea unui codificator zecimal-BCD

3.1.5.DECODIFICATOAREDecodificatoarele sunt circuite logice combinaţionale cu N intrări si m ieşiri, care activeaza una sau mai multe ieşiri in funcţie de cuvântul de cod aplicat la intrare (m=2N). Un decodificator (N:2N) are N intrări de date pe care primeşte codul binar al unui număr în domeniul 0-2N-1. La un moment dat o singură ieşire este activă şi anume cea cu indexul egal cu numărul prezentat la

100

Proiectare logică

intrare. Se poate spune că decodificatorul generează pe cele 2N

ieşiri toţi minitermii de N variabile de la intrare.

Fig. 3.18. Schema bloc a unui decodificator.Exemplu - decodificator cu 2 intrări si 4 ieşiri

Tabel de adevărA1 A0 Y0 Y1 Y2 Y3

0 0 1 0 0 00 1 0 1 0 01 0 0 0 1 01 1 0 0 0 1

01 AA

3

2

1

0

YYYY

Fig. 3.19..Implementarea unui decodificator cu două intrări şi patru ieşiri.

Cel mai cunoscut decodificator este decodificatorul binar-zecimal , BCD-zecimal. Acasta primeşte la intrare datele în codul BCD şi activează o singură linie la ieşire, corespunzătoare

101


codului aplicat la intrare. La aplicarea unui cod binar pe intrări, circuitul va activa o singură linie de ieşire. De exemplu, pentru intrarea 0101 se va activa y5 . Pentru cele patru variabile de intrare există 16 combinaţii. Doar 10 dintre ele sunt acceptabile şi anume cele între 0şi 9, celelalte sunt interzise.

zecimalbinartorDecodifica

DCBA

10987654321 yyyyyyyyyy

Fig.3.20.Schema bloc a unui decodificator BCD-zecimal.

Tabel de adevăr

A B C D y0 y1 y2 y3 y4 y5 y6 y7 y8 y9

0 0 0 0 1 0 0 0 0 0 0 0 0 0

0 0 0 1 0 1 0 0 0 0 0 0 0 0

0 0 1 0 0 0 1 0 0 0 0 0 0 0

0 0 1 1 0 0 0 1 0 0 0 0 0 0

0 1 0 0 0 0 0 0 1 0 0 0 0 0

0 1 0 1 0 0 0 0 0 1 0 0 0 0

102

Proiectare logică

0 1 1 0 0 0 0 0 0 0 1 0 0 0

0 1 1 1 0 0 0 0 0 0 0 1 0 0

1 0 0 1 0 0 0 0 0 0 0 0 1 0

1 0 1 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1

STĂRI INTERZISE

103


DCBA

DCBA

DCBA

DCBA

DCBA

DCBA

DCBA

DCBA

DCBA

DCBA

210

543

9876

Fig.3.21.Schema logică a decodificatorului BCD-zecimal.

Decodificatorul BCD-7segmente este utilizat la comanda dispozitiveor de afişare numerică realizate din 7 segmente luminoase (leduri, cristale lichide, becuri)se

gmen

teBC

Dto

rDe

codi

fica

7

gfedcba

A

B

C

Da

b

c

d

e

fg

Fig.3.22.Schema bloc a unui decodificator BCD-7segmente.

104

Proiectare logică

Tabel de adevăr

D C B A cifra a b c d e f g

0 0 0 0 0 1 1 1 1 1 1 0

0 0 0 1 1 0 1 1 0 0 0 0

0 0 1 0 2 1 1 0 1 0 1 1

0 0 1 1 3 1 1 1 1 0 0 1

0 1 0 0 4 0 1 1 0 0 1 1

0 1 0 1 5 1 0 1 1 0 1 1

0 1 1 0 6 0 0 1 1 1 1 1

0 1 1 1 7 1 1 1 0 0 0 0

1 0 0 0 8 1 1 1 0 0 1 1

1 0 0 1 9 1 1 1 0 0 1 1

Să realizăm prin minimizare fiecare segment din cele 7.

00

000

01

01

11

11 10

10 0

1

1

1

1

1

1

1

x

xx

xxx

DCBA

0

ACCABADa ..

105


CACABA

a

Fig.3.23..a Schema logică a unui decodificator BCD-7

segmente (segmant a).

00

0

00

01

01

11

11 10

10 01

1

1

1

1

1 1

1

x

xx

xxx

DCBA

1

DCBADb ..

b

D

BA

DC

Fig.3.23.b Schema logică a unui decodificator BCD-7 segmente (segment b).

106

Proiectare logică

00

0

00

01

01

11

11 10

10 0

1

1

1

1

1

1 1

1

x

xx

xxx

DCBA

DCBAc

c

DCBA

Fig.3.23.c.Schema logică a unui decodificator BCD-7

segmente (segmenc).

00

000

01

01

11

11 10

10 0

1

1

1

1

1

x

xx

xxx

DCBA

0 00

CBACBACBAd

107


00

0

00

01

01

11

11 10

10 0

1

1

1

x

xx

xxx

DCBA

00 0

00

BCACBAe

00

0

00

01

01

11

11 10

10 0

1

1

1

1

1

1 1

1

x

xx

xxx

DCBA

0

))(( BADCBAf

00

0

00

01

01

11

11 10

10

01

1

1 1

1 1

1

x

xx

xxx

DCBA

0

s

))(( CBADCBg

108

Proiectare logică

3.1.6.COMPARATOARE

Comparatoarele sunt circuite combinaţionale care compară numere cu un anumit număr de biţi, furnizând la ieşire trei semnale: A>B A=B A<B

3.1.6.1.Comparatoare pe un bit(C1)

1C1

1

B

A

BABABA

(A>B)= BA 1 (A<B)= 11 BA (A=B)= 11 BA

109

A1 B1 A>B A=B A<B

0 0 0 0 10 1 0 1 01 0 1 0 01 1 0 0 1


1

1

1

1

1

1

1

1

B

ABA

BABA

)().

BABA

)( BA

Fig.3.24.Schema bloc, tabelul de funcţionare şi schema logică a unui comparator pe 1 bit.

3.1.6.2.Comparatoare pe 2 biţi (C2)

Vom implementa un comparator pe n biţi prin metoda iteraţiei, adică utilizând comparatoare de rang inferior. Vom implementa un comparator C2 utilizând un C1 .Fie:

A=A1A2

B=B1B2

110

Proiectare logică

1C

2C

1

1

BA

2

2

BA

11 BA

11 BA

11 BA

22 BA

22 BA

22 BA

BA

BA

BA

Fig.3.25.Implementarea unui comparator pe pe 2 biţi.

3.1.6.3. Comparator pe 3 biti ( C3)

Schema rămâne ca cea precedentă doar că se înlocuieşte al doilea C1 cu C2 format de intrările A2 A3 şi B2 B3 .

111


1C

2C

1

1

BA

2B

11 BA

11 BA

11 BA

BA

BA

BA

3232 BBAA

3232 BBAA

3232 BBAA 3A2A

3B

Fig.3.26. Implementarea unui comparator pe 3 biţi.

3.1.6.4.Comparator pe n biţi (Cn)

Un comparator pe n biţi (Cn) se realizează dintr-un comparator pe un bit (C1) pe poziţiile cele mai semnificative şi un comparator pe (n-1) biţi (Cn-1).

3.1.7. CIRCUITE ARITMETICE COMBINAŢIONALE

3.1.7. 1.SumatoareSumatorul este un circuit care realizează suma aritmetică a

operanzilor aplicaţi pe intrări.A nu se confunda această operaţie cu operaţia logică SAU, numită de multe ori şi sumă logică (confuzia poate apare datorită aceleiaşi notaţii: simbolul +). Sumatorul pentru operanzi de un bit are două intrări la care se aplică operanzii, notate aici cu A1 A2 şi transportul anterior T0 .

112

A1 B1 T0↓ ↓ ↓

↓ ↓R1 T1

S1

Proiectare logică

Semnalele scoase de sumator sunt R1 (rezultatul) şi transportul posterior T1 .

Fig.3.27.. Tabel de adevăr şi schema bloc a unui sumator pe un bit

Tabelele Karnaugh şi ecuaţiile de funcţionare sunt:

10110100

01

1

110 0

001

11BA0T

TBATBATBATBAR 111110110111

10110100

01

11 1

0 0 00 1

11BA0T

0101111 TATRBAT

113

A1 B1 T0 R1 T1

0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1


1B

0T

1T

1A

1R

1

1

BA

0

1

TB

0

1

TA

1T

ig.328.Implementarea unui sumator pe un bit.

114

Proiectare logică

Sumatorul paralel pe n biti

Pornind de la sumatorul pe un bit, putem crea sumatorul pe n biţi după următoarea schemă:

1iT

11S12SiS1nS1

nn BA

1nT

nRnT

ii BA1iT

iR

22 BA1T 11 BA

0T

22 RT 11 RT

Fig.3.29.Schema bloc a unui sumator pe n biţi.

Deci, adunând două numere:

12........................1

121

B..........

.....................

BBBBB

AAAAAA

inn

inn

se obţine rezultatul: 121 ...................... RRRRRR inn şi

transportul; nT

nS

1nn AA 1A 1nn BB 1B

nT..1nn RR 1R

Fig.3.30. Simbolul sumatorului pe n biţi.

115


3.1.7.2.MULTIPLICATOARE

Multiplicatorul pe un bit (n=1)

Circuitul combinaţional care realizează înmulţirea a două cuvite de 1 bit este multiplicatorul elementar. Poarta logică ŞI realizează înmulţirea biţilor A1 şi B1 iar sumatorul complet de 1 bit adună produsul cu cel realizat de de bitul mai puţin semnificativ.

Fie A=A1

B=B1

2

1

AA

1R

Multiplicatorul pe 2 biţi (n=2)

Fie A=A2A1

B=B2B1

A înmulţi, conform regulilor de înmulţire, înseamnă:A2A1 .

B2B1

(A2A1)(A1B1) (B2A2)(B2A1)

Deci trebuiesc 4 multiplicatoare pe un bit pe primul nivel, iar pe nivelul doi trebuie un sumator cu un rang mai mare decât doi , deci trei. În acesta al doilea produs trebuie deplasat la

116

Proiectare logică

stânga înainte de a intra în sumator, deci va intra de pe poziţia doi.

123 RRR3T

3S

11AB 21AB 12 AB 22AB

Rezultatul este T3R3R2R1

Fig,3.31. Implementarea multiplicatorului pe 2 biţi.

Multiplicatorul pe trei biţi (n=3)Fie : A=A3A2A1

B=B3B2B1

A înmulţi cele două numere înseamnă: A3A2A1.( B3B2B1

(B1A3)(B1A2)(B1A1) (B2A3)(B2A3)(B2A1) (B3A3)(B3A2)(B3A1)

117


Pe primul nivel trebuiesc 9 multiplicatoare pe un bit ( nouă porţi ŞI), pe nivelul doi un sumator pe 4 biţi (S4) în care al doilea produs este deplasat la stînga cu o poziţie la intrarea în sumator, iar pe nivelul trei un sumator pe 5 biţi (S5) în care al treilea produs este deplasat la stânga cu două poziţii la intrarea în sumator.

4S

5s

312111 ABABAB 322212 ABABAB 332313 ABABAB

1R2R3R4R

4T

12345 RRRRR5T

Rezultatul este: T5 R5 R4 R3 R2 R1

Fig.3.32. Multiplicatorul pe trei biţi.

118

Proiectare logică

Multiplicatorul pe n biţi (Mn)

Fie două numere:

A=AnAn-1…….A2A1 ŞI B=BnBn-1……..B2B1

Respectând iteraţiile de construcţie de până acum, rezultă că pentru realizarea multiplicatorului pe n biţi trebuie următoarele:

-Nivelul 1 Pe acest nivel trebuie 2n multiplicatoare pe 1 bit.

-Nivelul 2 Un sumator Sn+1 pe n+1 biţi iar al (n -1) –lea produs deplasat spre stânga cu o poziţie şi intră începând cu a doua pondere a sumatorului Sn+1 .

Nivelul 3 Un sumator Sn+2 pe n+2 biţi iar cel al (n-2) lea produs este deplasat spre stânga cu o poziţie şi intră începând cu cu a treia pondere a a sumatorului Sn+2

Nivelul 4 Un sumator Sn+3 pe n+3 biţi iar al (n-3)lea produs este deplasat sprestânga cu o poziţie şi intă începând cua 4-a pondere a sumatorului Sn+3

………………………

……………………….

……………………….

………………………..

……………………….

Nivelul n Un sumator S2n-1 pe 2n-1 biţi iar primul produs este deplasat spre stânga cu o poziţie şi intră ăncepând cu a n-a ponere a sumatorului S2n-1 .

119


3.1.7.3.Circuite ŞI şi SAU la nivel de bit

Să se proiecteze circuite pe 4 biţi care să realizeze funcţiile ŞI şi SAU la nivel de bit între A=A3A2A0A1 şi B=B3B2B1B0

0123 AAAA0123 BBBB

0123 SISISISI 0123 SAUSAUSAUSAU

Fig.3.33. Circuit ŞI şi SAU la nivel de bit.

3.1,7.4. Unitate aritmetico- logică

O unitate aritmetico-logică (UAL)este un dispozitiv numeric care furnizează atât operaţii ARITMETICE cât şi LOGICE. Vom prezenta un tip de UAL care utilizează doar circuite combinaţionale.

Să proiectăm o UAL care ,în funcţie de cod (dat de biţii S3S2S1S0), va efectua anumite operaţii, 8 aritmetice şi 8 logice, ţinând cont că 4 biţi de cod permit 16 operaţii.

Lungimea cuvântului este de 4 biţi. La operaţiile de adunare şi scădere se ia şi cifra de semn iar cuvântul este de 3 biţi

Vom utiliza dispozitive numerice implementate ca : multiplexoare (1:2, 1:4), sumatoare (S4 pe 4 biţi),

120

Proiectare logică

complementoare faţă de 2, circuite de negare, circuite ŞI şi SAU pe 4 biţi.

COD

S3S2S1S0

OPERAŢIE

0 0 0 0 BA

0 0 0 1 BA

0 0 1 0 BA

0 0 1 1 BA

0 1 0 0 A

0 1 0 1 B

0 1 1 0 BA

0 1 1 1 BA

1 0 0 0 BA

1 0 0 1 BA

1 0 1 0 BA

1 0 1 1 BA

1 1 0 0A B

1 1 0 1 BA

1 1 1 0 BA

1 1 1 1 BA

121


&0

0

0

&0

0

0

&0

0

0

&0

0

0

??

1

4SI

4SAU

4S

4S 2:1

2:1

2:1

2:1

2:1

2:1

2:1

2:1

2:1

2:12:1

2:1

3S

3S

3S

3S

2S

2S

2S

2S

2S

2S

2S

2S

3R

2R

1R

0R

23

45

67

89

1011

1213

1415

16

17

3231

3029

28

2726

2425

2322

20

18

19

21

Fig.3.34.UAL cu circuite combinaţionale.

122

Proiectare logică

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

33 2233 BB CCBB

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

1ssO

3333 AABA 2222 AABA

11 2121 AA CACA00 2020 AA CACA

22 2222 AA CACA33 2323 AA CACA

22 2222 BB CCBB11 2211 BB CCBB

00 2200 BB CCBB

1111 AABA 0000 AABA

3300 BB 2200 BB

1100 BB 0000 BB

3333 AAAA 2222 AAAA 1111 AAAA 0000 AAAA

3333 BBBB 2222 BBBB 1111 BBBB 0000 BBBB

3333 AAAA 2222 AAAA 1111 AAAA 1111 AAAA

3333 BBBB2222 BBBB 1111 BBBB 0000 BBBB

2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

17 18 19 20

24

28

23

27

3231

2221

2625

3029

1

Fig. 3.35. Intrările în circuitele din fig.3.34

123


3.1.8. ARII LOGICE PROGRAMABILE.

Circuitele logice combinaţionale (CLC), care intervin frecvent în numeroase aplicaţii, se fabrică sub formă integrată, Aşa sunt , de exemplu, decodoarele de adresă, decodoarele BCD-zecimal, MUX-urile, DEMUX-urile etc.

În situaţiile în care o anumită aplicaţie necesită un anumit CLC care nu se fabrică sub formă integrată, acesta va trebui realizat ptactic cu circuite integrate existente. O asemenea soluţie, în cazuri mai complicate, cere multe circuite integrate cu numeroase conexiuni între ele, ceea ce duce la ocuparea unui spaţiu mare pe cablaj şi la scăderea fiabilităţii montajului. În asemenea situaţii sunt foarte utile ariile logice programabile care conţin într-o singură capsulă de circuit integrat numeroase porţi logice interconectabile, astfel încât să se poată realiza prctic o gamă extrem de variată de CLC-uri. Ideea de bază a circuitului este aceea că în punctele de conexiune interne sunt plasate fuzibile care în procesul de programare pot fi arse sau nu, rezultând în felul acesta schema dorită.

În figura 3.39. este reprezentată schema unei astfel de arii logice programabile. Pe schemă s-au notat prin legăturile de tip fuzibil. Circuitul este livrat cu toate fusibilele intacte ţşi este astfel coceput încât programatorul să aibă posibilitatea să ardă oricare fuzibil.

Semnalul de intrare Ik este aplicat unui buffer ce are rolul de a asigura curentul necesar bunei funcţionări a porţilor logice cărora li se aplică semnalul. Porţile logice ŞI sunt legate prin fuzibil la ieşirile directe şi negate ale tuturor buferelor de intrare Practic, în urma programării, un circuit ŞI va fi legat fie la ieşirea directă, fie la cea negată unui bufer de intrare. Rezultă că numărul de intrări ale circuitului ŞI va fi cel mult egal cu

124

Proiectare logică

numărul intrărilor în aria logică programabilă. O poartă logică ŞI realizează funcţia uk (constituent al unităţii).

110110 ...........

nin

iik xxxu

0ŞI

1ŞI 1nŞI

0I

0I0I

1I1I

1I

1nI

1nI1nI

0O

1O

1nO

EC

Fig.3.36 Schema logică a unei arii logice programabile

125


Circuitele SAU, conectabile la toate ieşirile circuitelor circuitelor de tip ŞI, permit obţinerea formei disjunctive canonice a unei funcţii booleene

k

m

kj uy

1

Dacă m<k, înseamnă că mai rămân porţi ŞI disponibile cu care se vor putea modela alte funcţii. Numărul maxim de funcţii ce pot fi modelate este dat de numărul circuitelor SAU. Sumatoarele modulo doi de la ieşire permit obţinerea funcţiei sau a inversei acesteia (au rolul de inversor programabil). La ieşire circuitul este prevăzut cu bufere cu trei stări controlate de o bornă comună EC (Chip Enable) ceea dce permite conectarea circuitului la magistrale.

Circuitul este foarte flexibil. Printr-o folosire raţională a intrărilor şi ieşirilor unui circuit integrat se pot modela chiar mai multe CLC.

Entru exemplificare, să se realizeze un circuit logic combinaţional (CLC) cu trei intrări şi două ieşiri a cărui funcţionare să fie descrisă de funcţiile:

321212

32132211

.......

xxxxxyxxxxxxxy

Se folosesc trei intrări, cinci circuite ŞI şi două circuite

SAU. Dezavantajul ariilor programabile este acela că, odată

programată aria, conţinutul acesteia nu se mai poate şterge şi nu se mai poate reutiliza.

126

Proiectare logică

3.2.CIRCUITE LOGICE SECVENŢIALE

Circuitele secvenţiale, spre deosebire de cele combinaţionale, au rolul de a memora informaţia .Cele mai utilizate sunt circuitele bistabile care stau la baza majorităţii circuitelor secvenţiale.

Pentru un circuit combinaţional, care nu are memorie, starea la un moment dat depinde numai de starea intrărilor la acel moment.

In cazul circuitelor secvenţiale starea la un moment dat depinde, în afară de starea intrărilor la acel moment, şi de starea imediat anterioară. Circuitele secvenţiale au memorie. Ieşirile depind deci nu numai de intrări ci şi de valorile anterioare ale ieşirilor. Există o reacţie de la ieşri la intrări .

Prin starea sistemului se înţelege ansamblul valorilor logice ale ieşirilor.

3.2.1.Circuite bistabile

Un circuit bistabil este un circuit logic secvenţial care poate avea la ieşire două stări stabile 0 logic şi 1 logic. Este posibil să păstreze la ieşire oricare dintre cele două stări logice un timp nedefinit şi numat o comandă aplicată pe intrări din exterior poate declanşa modificarea stării logice la ieşire. Deci, un astfel de circuit mamorează o anumită stare logică dintre două comenzi externe.

Ieşirile circuitelor logice bistabile nu mai depind numai de intrări ci şi de anumite valori anterioare ale ieşirilor, existând astfel reacţii de la ieşiri la intrări. Aceste reacţii produc întârzieri ale semnalelor la trecerea lor prin porţile logice. Timpul cu care este întârziat semnalul este nul la porţile ideale dar la porţile reale trebuie luat în consideraţie.

Există două moduri de funcţionare:-modul asincron

127


-modul sincron.Modul asincron este acelaşi penru toate tipurile de bistabile.

Circuitele au două intrări: set (S) şi reset ( R ).)(setS

)(resetR

Q

Q

Fig.3.37.Circuit bistabil.Schema bloc.

Un circuit secvenţial este asincron dacă modificarea stării intrărilor determină imediat schimbarea stării ieşirilor, fără a mai fi nevoie de alt semnal de comandă.

Dacă numai unele intrări au astfel de comportare ele se numesc ieşiri asincrone sau prioritare. Atunci când pe intrarea S apare un nivel de 0 logic, ieşirea Q a bistabilului trece în 1 logic, chiar după dispariţia nivelului de zero. Atunci când apare pe intrarea R un nivel de 0 logic, ieşirea Q a bistabilului trece în 0 logic, chiar şi după dispariţia nivelului de 0.

Circuit bistabil.Tabel de funcţionareR S Q0 1 01 0 11 1 Q0 0 1 Situaţie

nepermisă

Observaţii

128

Proiectare logică

-Modul asincron este prioritar modului sincron în sensul că atunci când pe intrările S sau R avem un 0, bistabilul trece în 1 sau 0 şi anulează modul sincron.

-Pe intrările S şi R nu putem avea semnal de 0 deoarece ar însemna o imposibilitate logică.

-Atunci când intrările S şi R sunt în aer ( nu avem semnal pe ele) modul asincron nu funcţionează şi funcţionează numai modul sincron.

Q

RS

FIg.3.38. Circuit bistabil. Exemplu de funcţionare a modului asincron.

Modul sincron.Modul sincron presupune existenţa unui tren de impulsuri

care se aplică pe o intrare de ceas (clock) a bistabilului. Există de asemenea şi intrări sincrone în funcţie de tipul bistabiluui.

Fiecare tip de bistabil are o ecuaţie sincronă în care ieşirea Q se poate schimba doar la frontul pozitiv al ceasului (din 0 în 1) sau negativ (din 1 în 0).

Bistabilul D

Ck

Q

Q

S

R

D

Fig.3.39. Circuit Bistabil D

129


Ecuaţia de funcţionare este Qn=D şi se aplică la frontul pozitiv al ceasului. Deci, la bistabilul de tip D, la tranziţia ceasului din 0 în 1,intrarea D se va regăsi pe ieşirea Q.

CkD

QFig.3.40.Exemplu de funcţionare a unui bistabil numai în

sincron.

In exemplul de mai sus se observă că ieşirea Q se poate modifica doar pe frontul pozitiv al ceasului Ck, indiferent de ce schimbări au loc penru intrarea D între două tranziţii pozitive ale ceasului.

În fig.3.41 se dă funcţionarea mixtă a modului sincron şi asincron pentru bistabilul de tipul D.

CkD

S

R

Fig.3.41.Funcţionarea mixtă, sincron şi asincron, pentru bistabilul D.

130

Proiectare logică

Observaţii:Se vede că modul asincron este prioritar modului sincron, în

sensul că atunci când pe S sau R avem un nivel de 0 bistabilul va trece în 1 respectiv 0.

Bistabilul J-K

Bistabilul J-K acţionează la front negativ (o tranziţie de la 1 la 0) şi are în mod sincron o funcţionare dată de tabelul de mai jos.

Ck

Q

Q

S

R

J

K

Fig.3.42.Bistabil J-K

Tabel de funcţionare

J K Qn-1

0 0 Qn

0 1 0

1 0 1

1 1 nQ

La o tranziţie din 1n 0 ieşirea (notată cu Q n+1) după aplicarea frontului va avea valoarea lui J, dacă J>K au valori diferite. Dacă J=K=0, atunci Qn+1=Qn , adică se păstrează starea

131


precedentă. Dacă J=K=1, bistabilul trece în starea opusă celei anterioare, Qn+1 = nQ .

CK

J

K

Q

Fig. 3.43. Funcţionarea unui bistabil J-K în modul sincron.

Se observă că la fiecare tranziţie din 1 în 0 a ceasului valoarea lui Q se modifică conform tabelului de funcţionare a bistabilului J-K

J

K

R

S

Q

CK

FIg.3.44.Diagrama de fincţionare mixtă a unui bistabil J-K (atât sincron cât şi asincron).

132

Proiectare logică

La fel ca şi la bistabilul D , în funcţionarea mixtă , modul asincron este prioritar modului sincron, în sensul că atunci când pe intrările S sau R este un nivel 0 bistabilultrece în mod automat pe 1 sau 0. Dacă pe intrările S sau R este un nivel de 0 atunci modul sincron nu funcţionează atât timp cât semnalul 0 persistă.

3.2.2.Aplicaţii ale bistabilelor

3.2.2.1. Circuite numărătoareCircuitele numărătoare sunt cele care au rolul se a număra

inpulsurile care vin pe adrese de ceas. Există implementări ale numărătoarelor atât în modul sincron cât şi în modul asincron. Modul sincron de funcţionare a numărătoarelor înseamnă că impulsurile ajung în acelaşi timp pe toate intrările de clock ale bistabilelor ce fac parte din numărător. Modul asiscron înseamnă că impulsurile nu ajung toate la intrările bistabilelor din numărător ci, de obicei numai la un singur bistabil.

Vom studia un singur tip de numărător asincron, cu bistabile J-K.La sintetizarea acestui tip de numărător ţinem seama de următoarele consideraţii:

- Impulsurile de numărat ajung numai într-un singur bistabil, pe celelalte bistabile intrările de clock sunt realizate de ieşirile bistabilelor anterioare.

- Primul bistabil va avea o perioadă de două ori mai mare decât a impulsurilor de numărat, al doilea bistabil o perioadă de 4 ori mai mare, al treilea de 8 ori şi aşa mai departe. Acest lucru se realizează punând intrările J-Kde la fiecare bistabil la 1; în felul acesta la fiecare impuls fiecare bistabil va trece în starea opusă.

- La fiecare impuls de ceas ieşirile bistabilelor, cel mai puţin semnificativ fiind cel în care intră intră ceasul, vor costrui în binar numărul de impulsuri numărate până în acel moment.

133


Ca exemplu dăm un numărător ce numără până la 23=8 , constituit di trei bistabile J-K.

1

1

1

1

1

KCkI

1

1

Q

Q

1

1

2

2

Q

Q

2

2

2

KCkI

1

1

3

3

3

KCkI

3

3

Q

Q

Fig.3.45.Numărător cu trei bistabili J-K.

1 2 3 4 5 6 7 8Ck

1Q

2Q

3Q

Fig.3.46.Diagrama de impulsuri pentru numărătorul 23

cu trei bistabili J-KTabel de adevăr

Ck Q1 Q2 Q3

0 0 0 01 1 0 02 0 1 03 1 1 04 0 0 15 1 0 16 0 1 17 1 1 18 0 0 0

Pentru un numărător de modulo 2n sunt necesare n bistabile legate după modelul de mai sus. Pentru realizarea unui

134

Proiectare logică

numărător modulo p, un număr care să nu fie o putere a lui 2, trebuie resetat numărătorul atunci cănd ajunge la valoarea p de numărat. Practic numărul p, decodificat în binar, va constitui intrările într-o poartă ŞI-NU care va generaun impuls de 0 ce va intra pe toate intrările de reset (R ) ale tuturor bistabilelor componenete din numărător.

Exemple:1) Să se implementeze un numărător modulo 33

Pentru reset la 33, în binar 100001, sunt necesare 6 bistabile.

2

2

R

Q

4

4

Q

Q

4

4

R

Q

5

5

R

Q

6

6

R

Q

1

1

R

Q

3

3

R

Q

123456 QQQQQQ

1Ck 2Ck 3Ck 4Ck5Ck 6Ck

Fig.3.47.Numărător modulo 33.

2)Să se implementeze un numărător care să numere descrescător impulsurile (-1) de la valoarea iniţială de 1 pentru toate bistabilele. Să se implementeze în două cazuri:

a)modulo 63 (în binar…………..b)modulo 50 (în binar 110010)Soluţie Pentru a putea număra descrescător impulsurile, legăturile,

în loc să se facă dela Q anterior la ceasul următor, se fac de la Q

135


anterior la ceasul următor. Când se ajunge la 0 se setează, prin intrările de set, valoarea de 1 la toate bistabilele.

1

1

Q

Q

3

3

Q

Q

4

4

Q

Q

4

4

Q

Q

5

5

Q

Q

6

6

Q

Q

2Ck 3Ck 4Ck 5Ck 6Ck2Q

2Q

1S 2S 3S 4S 5S 6S

456 QQQ 123 QQQ

1Ck

S Fig.3.48.Numărător descrescător modulo 63.

1

1

Q

Q

3

3

Q

Q

4

4

Q

Q

4

4

Q

Q

5

5

Q

Q

6

6

Q

Q

1Ck 2Ck 3Ck 4Ck 5Ck 6Ck2Q

2Q

1S 2S 3S 4S 5S 6S

654321 RRRRRR

123456 QQQQQQ

Fig.3.49. Numărător descrescător modulo 50.

136

Proiectare logică

3.2.2.2. Registre

Registrele sunt o altă aplicaţie importantă a bistabilelor şi sunt de două mari categorii:

1) Registre de stocare (memorare a informaţiei)2) Registre de deplasare a informaţiei.

1). Registrele de stocare (memorare a informaţiei) au rolul de a păstra informaţia. Implementarea acestor registre se face cu bistabile de tip D care sunt cele mai adecvate acestui mod de funcţionare. Fiecare bistabil va memora un bit, deci nunărul de bistabile necesare va fi dat de lungimea cuvântului memorat. În figura 3.50 este dat un registru de memorie pe 4 biţi.

CK

QD AA

CK

QD BB

CK

QD CC

CK

QD DD

ZZZZ AAAAdatedeparalelăIntrare

WRITE

LSIsau

datedeparalelaIesire

Fig.3.50.Registru de memorieScrierea în registru se face în mod sincron pe intrările de

date Di (i=numărul de bistabile D). Memorarea informaţiei are loc în momentul frontului pozitiv al ceasului (Ck,clock). Citirea din registru se face în mod automat prin ieşirile Q ale fiecărui bistabil în parte

Registre de deplasare

137


Registrele de deplasare sunt circuite care, la fiecare impuls de tact aplicat, îşi deplasează conţinutul spre dreapta sau spre stânga cu câte o celulă. Aceste registre se realizează cu bistabili de tipul D .

Există mai multe tipuri de registre de deplasare:După sensul de deplasare registrele de deplasare pot fi:-SISO (Serial Input-Serial Output) Cu deplasare la dreapta (SISO-SH) (Shift Reight)

Cu deplasare la stânga (SISO-SL) )Shift Left) Bidirecţional.

-SIPO(Serial Input-Paralel Output) -PISO (Paralel imput-Serial Output)

PIPO (Paralel Imput-Paralel Output)Informaţia se deplasează bit cu bit (spre dreapta sau spre

stânga)la fiecare impuls de ceas.După modul de deplasare a informaţiei registrele pot fi: -Registre de deplasare seriale-Registre de deplasare în inel.În registrele de deplasare seriale există o intrare serie şi o

ieşire serie iar informaţia care intră pe intrarea serie va fi regăsită pe ieşirea serie.

În registrele de deplasare în inel ieşirea este conectată la intrarea serie. In acest mod se recirculă informaţia în cadrul registrului.

Implementarea acestor tipuri de registre se face cu bistabile J-K în care ieşirile Q şi Q a le unui bistabil se leagă cu bistabilul următor la intrările J respectiv Q (Q anterior → j şi Q anterior →K). În felul acesta, pe intrările J şi K vom avea totdeauna valori opuse (J=0, K=1 sau J=1,K=0). Conform ecuaţiei de funcţionare a bistabilului J-K, când J şi K au valori opuse, valoarea Q a bistabilului va treceîn starea lui J. La fiecare impuls de ceas valoarea unui bistabil va fi dată de valoarea bistabilului anterior.

Registru de deplasare stânga dreapta

138

Proiectare logică

0

0

QKCK

QJ

1

1

QKCK

QJ

2

2

QK

CKQJ

3

3

QK

CKQJ

TACT

serieIntrare serieIesiire

ceas

Q1 Q2 Q3 Q4

0 0 0 0 0Ck1 I1 0 0 0Ck2 I2 I1 0 0Ck3 I3 I2 I1 0Ck4 I4 I3 I2 I1

Ck5 I5 I4 I3 I2

Fig.3. 51. Registru de deplasare stânga-dreapta (ST-DR)( schema bloc şi tabelul de funcţionare)

Se oservă din tabel că, la fiecare impuls de ceas conţinutul registrului se mută cu câte o poziţie spre dreapta. Semnalul de ieşire va fi identic cu del de intrare dar întîrziat cu un număr de perioade de ceas egal cu numărul de bistabile.

Registru de deplasare în inelÎn acest registru ieşirea se pune la intrarea serială, astfel

încât informaşia se recirculă. Un astfel de registru este caracterizat prin funcţia Y=Qintrare ceea ce înseamnă că prin reacţie se asigură înscrierea conţinutului ultimeimcelule în prima.

Registru combinat (de memorie şi deplasare)

Într-o serie de aplicaţii este util ca registrul să aibă pe lângă intrarea serie (ca în cazul RD) şi intrări paralele (ca în cazul RM). Un astfel de registru este prezentat în figura 3.52.

139


1

20MUX

A

1

20MUX

A

1

20MUX

A

1

20MUX

A

CKD A0

CKD B0

CKD C0

CKD D0

1

20MUX

1A 1B 1C 1D

P

S

T

T

CM

IS serieiesire

paraleleIntrari

paraleleiesiri

Fig.3.52.Registru combinat de memorie şi de deplasare

În funcţie de valoarea semnalului CM avem: pentru CM=0 se obţine un RD st-dr care funcţionează cu tactul ST iar pentru CM=1 schema se transformă într-un registru de memorie cu

inscriere paralelă de date ,cu tactul pT .Registru universalUn astfel de registru cumulează funcţiile tuturor registrelor

prezentate anterior. Este prevăzut şi cu o intrare asincronă pentru ştergerea informaţiei, CLEAR. Schema se realizează cu celule binare de tipul D sincrone şi cu ajutorul unor multiplexoare.(fig.3.53)

140

Proiectare logică

MUX

YAA

3210

10

MUX

YAA

3210

10

MUX

YAA

3210

10

103210

AA

MUXY

RQCK

D

1

R

QCKD

2

R

QCKD

3

)(/ DRSTIS

P

S

TT

1

0

AA

)/( STDRIS iA iB iC

clear

paraleleIntrari

Fig.3.53.Registru universal.

3.2.2.3.Memorii

Memoria FIFO(First In First Aut)Caracteristica de bază a unei astfel de memorii este faptul că

primul cuvânt înscris va fi şi primul citit. Memoria se poate realiza cu ajutorul unor registre de deplasare stânga-dreapta. Numărul registrelor va fi determinat de lungimea cuvântului ce urmează a fi memorat. Capacitatea memoriei(numărul cuvintelor memorate) va fi dată de lungimea registrului (numărul de celule binare din care este format registrul). În figura 3.54. este dată schema unei memorii FIFO pentru cuvinte de patru biţi. Dacă la

141


scjemei folosim registre de deplasare formate din câte patru celule, capacitatea memoriei va fi de patru cuvinte.

S

D

TiSRD

Q

2

S

D

TiSRD

Q

1

S

D

TiS

RDQ

3

S

D

TiSRD

Q

4

parale

laIes

ire

parale

laIntr

are

Tact

Fig.3.54. Memorie FIFO pentru cuvinte de patru biţi. Memorie LIFO (Last In First Aut)

Memoria LIFO este de fapt o memorie STIVA. Ea se caracterizează prin faptul că ultimul cuvânt înscris va fi primul citit. O asemenea memorie poate fi realizată cu ajutorul unor

registre universale (RU) cum se indică în figura

CKR

QQQRUQ

DRSTISAA

4

3

22

1

01

)(

CKR

QQQRUQ

DRSTISAA

4

3

23

1

01

)(

CKR

QQQRUQ

DRSTISAA

4

3

23

1

01

)(

CKR

QQQRUQ

DRSTISAA

4

3

21

1

01

)(

1x 2x 3x 4x0A1A

TactClear

datedeparalelaIntrare

datedeparalelaIesire

Fig.3.55. Memorie LIFO pentru cuvinte pe patru biţi.

142

Proiectare logică

3.2.2.4.Convertoare

Convertor paralel – serieÎn numeroase aplicaţii apare necesitate transformării unor

cuvinte de cod paralel ( cu acces simultan la toate simboluirile cuvântului) în cuvinte de cod serie (cu acces consecutiv la simbolurile cuvântului). Un asemenea convertor poate fi realizat cu un registru combinat aşa ca în figura 3.56. Funcţionarea se poate urmări cu ajutorul tabelului şi a diagramelor temporale din figură.

Cuvântul de cod ce urmează a fi convertit (x1x2x3x4) se aplică pe bornele de intrare paralelăAiBiCiDi) ale registrului.

Punem CM=1 şi la aplicarea unui impuls de tact pe borna pT cuvântul se va înscrie în registru. După aceasta punem CM=0, ceea ce va însemna transformarea registrului combinat în registru de deplasare stânga dreapta , astfel că în ritmul impulsurilor aplicate de la intrarea sT va avea loc evacuarea cuvântuluide cod pe ieşirea serie în ordinea x3x2x1x0.

PS

DCBA

TTCMDCBAIS

QQQQRC

1111

paralelăIntrare

serieIntrare

Comanda

143


CMST pT QA QB QC QD

1 1 1→0

x0 x1 x2 x3

Q 1→0 0 0 x1 x2 x3

Q 1→0 0 0 0 x1 x2

Q 1→0 0 0 0 0 x3

1 1 1→0

10x 1

1x 12x 1

3x

ST

PT

CM

t

t

t

Fig.3.56.Convertor paralel-serie (schema bloc, tabel de funcţionare şi diagrama de impulsuri).

Convertor serie-paralel

Acest tip de convertor transformă succesiunea serie de simboluri (cuvânt de cod serie) într-un cuvânt de cod paralel. Se utilizează un registru de deplasare şi un registru de memorie. Cuv\ntul de cod aplicat serrie pe intrarea IS se înscrie în registru în ritmul impulsurilor aplicate la intrarea sT . În momentul în care registrul s-a umplut se dă comanda de transfer al cuvântului recepţionat într-un registru de memorie pe ieşirile căruia va

144

Proiectare logică

apărea cuvântul de cod paralel (Fig. 3.56). Momentul transferului reprezintă o informaţie suplimentară care trebuie cunoscută dinainte pentru a putea forma corect comanda L.S.I.

iiii DCBARM

DCBA

S

DCBA

TISRD

QQQQ

... ISL

serieIntrare

Tact

paralel ăIntrare

ST IS QA QB QC QD

T→0 x4 0 0 0 0T→0 x3 x4 0 0 0T→0 x2 x3 x4 0 0T→0 x1 x2 x3 x4 0T→0 1

4x x1 x2 x3 x4 ←comandăL.S.I.

T→0 13x 1

4x x1 x2 x3

t

Tact

... ISL

145


Fig.3.57. Convertor serie-paralel (schema bloc, tabel de funcţionare, diagramă de funcţionare).

3.2.3.Circuite de memorie de tip PROM (Programable Read Only Memory)

Circuitele de memorie de tip PROM sunt memorii nevolatile (nu îşi pierd informaţia odată cu nealimentarea circuitului de tensiune). Ele sunt înscrise cu o anumită informaţie care apoi este citită în diverse aplicaţii.

Din punct de vedere tehnologic circuitele PROM au avut două etape de dezvoltare.

În prima etapă, înscrierea informaţiei se făcea de către un dispozitiv numit „arzător de PROM-uri”. Acest lucru se facea o singură dată şi apoi PROM-ul cu informaţia arsă era dat utilizatorilor. Dacă utilizatorii doreau să schimbe informaţia, PROM-ul era trimis din nou în fabrică, şters cu ultraviolete şi apoi inscris cu ajutorul arzătorului de PROM-uri.

A doua etapă este legată de apariţia aşa numitelor FLASH-PROMURI. Apărute ca o necesitate a micilor telefoane mobile, aceste circuite permiteau înscrierea informaţiei în timpul funcţionării lor, deci ON LINE. Principiul funcţionării circuitului PROM este acelaşi cu cel al funcţionării oricărei memorii, adică la o adresă dată de liniile de adresă (Adresă 1, Adresă 2,………….Adresă n) se citeşte o informaţie pe liniile de date (Date 1, Date 2, ……Date n). Orice PROM se caracterizează prin două elemente:

-Numărul de cuvinte care pot să fie înmagazinate în PROM, notat cu N;

-Lungimea cuvântului, în biţi, notată cu L.Spre exemplu pentru un PROM de tipul 256×4 (N=256

cuvinte de lungime L=4) numărul de biţi de adresă este n=log2256=log2.28=8

146

Proiectare logică

nAdresă

AdresăAdresă

21

mDate

DateDate

21

SELECTchipCS (

Fig.3.58. Schema bloc a unui PROM.

Modificarea geometriei PROM-urilorPrin modificarea geometriei unui PROM se înţelege

realizarea de circuite de memorie PROM ce au un număr de cuvinte sau o lungime de cuvânt diferite faţă de circuitul iniţial.

Modificarea lungimii cuvântului (L). Pentru a se realiza o configurare cu un număr de biţi schimbat (L1)faţă de cel iniţial L, se aleg un număr de promuri dat de relaţia:

-Nr. de promuri=

LL1

unde [ ] este partea întreagă a

raportului LL1

.-Aceste promuri se pun în paralel.-Intotdeauna modificarea lungimii cuvântului se face cu

L1>L.ExempluSă se realizeze dintr-un PROM 128 × 4 un alt circuit de

memorie 128 × 8.

147


Cum 2

481

LL

avem nevoie de 2 PROM-uri 128 × 4 pentru a realiza un circuit de memorie PROM 128 X 8.

4321

DateDateDateDate

8765

DateDateDateDate

7654321

ADADADADADADAD

7654321

ADADADADADADAD

Fig.3.59 . Schema bloc a unui PROM 128 × 8

Modificarea numărului de cuvinte (N).Pentru modificarea numărului de cuvinte de la N la N1 se

alege un număr de promuri egal cu

NN1

şi se selectează cu toate combinaţiile posibile semnalele CSC chip Select de la fiecare PROM în parte.

Exemplul 1

148

Proiectare logică

Să se extindă de la PROM-ul 128×4 la un PROM 236×4.

N=128=27 , N1 = 256 = 28, 2

22

7

8

1

NN

La PROM-ul 256 avem 8 biţi de adresă, deci cu bitul de

adresă AD 8 vom selecta cele 2 PROM-uri 128×4, restul parametrilor rămânând neschimbat,

4321

DateDateDateDate

7654321

ADADADADADADAD

4321

DateDateDateDate

7654321

ADADADADADADAD

8AD 8ADFig.3.60 .Schema bloc a unui PROM 2364

Exemplul 2Să se extindă PROM-ul de 128×4 la un PROM de 512 × 4.

149


N=128=27 , N1 =512=29 42

22 2

7

9

1

NN

Am considerat că CS este activ pentru valoarea de 1 logic.

432

DDD

7654321

ADADADADADADAD 1D

7654321

ADADADADADADAD 1D

2D

3D

4D4321

DDDD

7654321

ADADADADADADAD

8AD9AD

4321

DDDD

7654321

ADADADADADADAD

8AD9AD 9

8ADAD

9

8

AD

AD

4128 4128

Fig.3. 61 .Schema bloc a unui PROM 5124

Modificarea mixtă (modificarea lungimii L şi a numărului de biţi N)

Se aplică cele două metode combinat.ExempluUtilizând PROM-uri128×4,să se implementeze un PROM

512×16.

150

Proiectare logică

De la extensia numărului de biţi avem 4 PROM-uri, de la extensia numărului de cuvinte avem 4 PROM-uri. Rezultă o matrice de 4×4 PROM-uri de 128×4, deci 16 PROM-uri.

151


7654321

ADADADADADADAD

7654321

ADADADADADADAD 1D

2D

3D

4D4321

DDDD

7654321

ADADADADADADAD

8AD9AD

4321

DDDD

7654321

ADADADADADADAD

8AD9AD 9

8ADAD

9

8

AD

AD

4128 4128

7654321

ADADADADADADAD

7654321

ADADADADADADAD

8765

DDDD

7654321

ADADADADADADAD

8AD9AD

8765

DDDD

7654321

ADADADADADADAD

8AD9AD 9

8ADAD

9

8

AD

AD

4128 4128

8765

DDDD

4321

DDDD

8765

DDDD

7654321

ADADADADADADAD

7654321

ADADADADADADAD

7654321

ADADADADADADAD

8AD9AD

7654321

ADADADADADADAD

8AD9AD 9

8ADAD

9

8

AD

AD

4128 4128

7654321

ADADADADADADAD

7654321

ADADADADADADAD

7654321

ADADADADADADAD

8AD9AD

7654321

ADADADADADADAD

8AD9AD 9

8ADAD

9

8

AD

AD

4128 4128

1211109

DDDD

1211109

DDDD

1211109

DDDD

1211109

DDDD

16151413

DDDD

16151413

DDDD

16151413

DDDD

16151413

DDDD

Fig.3.62 .Schema bloc a unui PROM 51216.

152

Proiectare logică

Aplicaţii ale PROM-urilor

1)Convertoare de codConvertoarele de cod reprezintă trecerea de la o mulţime a

cuvintelor de cod la alta. Aceste convertoarea se pot implementa cu circuite combinaţionale utilizând diagramele Karnaugh pentru minimizarea funcţiilor.

O altă metodă de implementare este utilizarea unui PROM care va stoca la fiecare adresă funcţia de cod corespunzătoare. Astfel dacă avem un cod care va transforma cuvinte de m biţi (la intrare) în cuvinte de n biţi (la ieşire), vom utiliza un PROM de 2m×n, cu m adrese şi n biţi la ieşire.

De exemplu pentru un cod GRAY avem m=n=4 şi vom utiliza un PROM de 16 cuvinte de 4 biţi, unde fiecare din cele 16 cuvinte va avea stocat un PROM valoarei transformată prin codul GRAY.

2)Generarea unor secvenţe de impulsuriPentru generarea unor secvenţe de impulsuri de o perioadă

T se utilizează un PROM cu un număr de cuvinte egal cu T şi cu o singură ieşire (T×1). Acest PROM va avea pe liniile de adrese un numărător modulo T; la fiecare adresă va fi stocat un bit din secvenţa de impulsuri. De exemplu, dacă vrem să să genereze secvenţa de impulsuri 0001 0001 0001 …… luăm un PROM (4×1) şi un numărător modulo 4 iar informaţiile stocate în PROM sunt la: la adresa 00 găsim 0, la adresa 01 găsim 0, la adresa 10 găsim 0 şi la adresa 11 găsim 1.

153


CAPITOLUL 4.

APLICAŢII ALE PROIECTĂRII LOGICE

În acest capitol prezentăm aplicaţii atât combinaţionale cât şi secvenţiale, aplicaţii care fac obiectul acestui curs. Aplicaţiile secvenţiale nu sunt rezolvate prin metoda automatelor finite ci numai prin mijloacele expuse în această carte de proiectare logică.

4.1.Căutarea unei valori în registre

Să se proiecteze un dispozitiv numeric care să caute o valoare într-un şir de 8 registre şi să semnaleze registrul sau registrele unde se află valoarea căutată. Lungimea registrului şi a valorii căutate este de 4 biţi.

SoluţieProblema face parte din categoria problemelor de căutare

care trebuie transpuse din soft în hard.Pentru implementare utilizăm 9 registre de 4 biţi, 8 în care

există, în fiecare, valorile de căutat şi unu în care sunt valorile de referinţă.Se mai folosesc 8 comparatoare pe 4 biţi iar fiecare dintre ieşirile egal(=) va ataca o locaţie a unui registru de 8 biţi. În final, poziţiile pe care se găsesc valori de 1 dau numărul registrelor în care s-agăsit egalitatea.

154

Proiectare logică

3.C

omp

RE

F

3R

RE

F

RE

F

RE

FR

EF

RE

F

7R

6R

5R

4R

7.C

omp

6.C

omp

5.C

omp

4.C

omp

2R

2.C

omp

1R

1C

omp

RE

F

8R

8.C

omp

RE

F

REFERINŢE

)()(

)(

)(

)()(

)(

)( 8

76

5

432

1

Fig.4.1. Schema bloc a unui dispozitiv numeric de căutare.

4.2.Aflarea maximului dintre mai multe numereSă se proiecteze un dispozitiv numeric care să simuleze

operaţia de aflare a maximului dintre 4 numere. Numerele sunt reprezentate pe doi biţi şi sunt stocate în registre de doi biţi. Numărul registrelor (şi deci a numerelor) este de 4.

155


Soluţie Avem de aflat maximul dintre 4 numere pe doi biţi fiecare.

Algoritmul este de a compara, cu un comparator pe doi biţi, 2 numere alăturate. Rezultatul din comparatorul a două numere este ieşirea „mai mare” (>) care va fi utilizată pe următorul nivel pentru a multiplexa efectiv numărul mai mare.

Mai jos este dată implementarea acestui dispozitiv cu comparatoare pe doi biţi şi multiplexoare (2:1) cu selecţiile comandate de ieşirile comparatoarelor. Numerele de comparat sunt:

A=A2A1

B=B2B1

C=C2C1

D=D2D1

MAXIM

)1:2(MUX )1:2(MUX

biţiComparator 2

)1:2(MUX)1:2(MUX

biţiComp2. biţiComp2.

)1:2(MUX )1:2(MUX

21 AA 21 BB 21 CC 21 DD

Fig.4.2.Dispozitiv numeric pentru aflarea maximului dintre 4 numere.

156

Proiectare logică

4.3.Comanda unui semafor

Să se proiecteze un dispozitiv numeric care să comande un semafor. Pe culorile roşu şi verde se va sta 20 de secunde iar pe galben 3 secunde. Semaforul va merge doar în sensul ROŞU-GALBEL-VERDE după care secvenţa se va repeta.

SoluţieDeoarece semaforul trebuie să comute după 20 de secunde

din ROŞU→GALBEN, după 23 secunde din GALBEN→VERDE iar după 43 secunde din VERDE→ROŞU, utilizăm un numărător modulo 43. Vom utiliza trei bistabile, fiecare comandând culorile ROŞU, GALBEN, VERDE, bistabilele funcţionând în regim asincron. Deoarece când o culoare se aprinde trebuie stinsă cea precedentă, se va utiliza următoarea schemă:

-timp=20 secunde se va seta GALBEN şi reseta ROŞU-timp=23 secunde se va seta VERDE şi reseta GALBEN-timp=43 secunde se va seta ROŞU şi reseta verdePentru implementare trebuie un numărător modulo 43 care

va sesiza cele trei momente de timp:20=01010023=01011143=101011Totodată, momentul 43 va reseta numărătorul, secvenţa

repetându-se ciclic.Următoarea schemă redă implementarea acestui dispozitiv

de comandă pentru semafor.

157


6

5

4

3

2

1

Q

Q

QQ

QQ

6

5

4

3

2

1

QQQQQQ

6

5

4

3

2

1

QQQ

QQQ

43MODULONUMARATOR

roş

galben

verde

R

R

R

S

S

S

654321 QQQQQQ

ISTceas

RQ

GQ

VQ

Fig.4.3.Dispozitiv de comadă pentru semafor.

158

Proiectare logică

4.4.Afişare numericăSă se creeze un dispozitiv numeric care să afişeze, cu

ajutorul a două sisteme de afişare numerică cu 7 segmente, unul pus pe cifra unităţilor şi unul pe cifra zecilor, numerele în ordine crescătoare de la 00 la 99. Această afişare se va va desfăşura ciclic, adică după ce se va ajunge la 99 sistemul va începe iar să afişeze de la 00.

SoluţieUn sistem de afişare cu 7 segmente are patru intrări (în binar

de la 0000 la 1001) şi 7 ieşiri reprezentate de cele 7 segmente care vor decodifica cele 9 cifre de la intrare, afişându-le. În cazul nostru utilizăm un numărător modulo 10 pentru fiecare dintre cele două sisteme de afişare, unul pe cifra unităţilor şi unul pe cifra zecilor. Clockul pentru sistemul de afişare pe cifra unităţilor va fi dat de un generator de impulsuri cu T=1sec. Clockul pentru sistemul de afişare a zecilor este dat atunci când numărătorul de pe cifra unităţilor ajunge la a zecea cifră (9). Amândouă numărătoarele sunt resetate asincron după ce ajung la cifra 9 şi apoi fiecare continuă să numere de la 0.

)(7

zecilorcifraSEGMENTE

AFISAREDESISTEM

)(7

unitatilorcifraSEGMENTE

AFISAREDESISTEM

RESETMODULONUMARATOR

10

4321 IIII

RESETMMODULONUMARATOR

10

4321 QQQQ

4

3

2

1

QQQQ

4

3

2

IIII I

CLOCK)1( ST

CLOCK

Fig.4.4.Dispozitiv de afişare numerică.

159


4.5. Simularea unui ceas

Ssă se creeze un dispozitiv numeric care să simuleze funcţionarea unui ceas, afişând timpul în ore, minute şi secunde.

SoluţiePentru a simula un ceas utilizăm 6 sisteme de afişare cu 7

segmente , câte două pentru secunde, minute şi ore. Fiecare sistem de afişare va avea pe cele 4 intrări un numărător , deci vor fi 6 numărătoare. Numărătoarele pentru afişarea secundelor vor fi unul modulo 10 şi unul modulo 6. Cele pentru afişarea minutelor vor fi tot unul modulo 10 şi unul modulo 6. Numărătoarele pentru ore vor fi unul modulo 10 şi unul modulo 2

.Reseturile pentru numărătoare se vor face individual pentru fiecare numărător, în funcţie de modulo de numărare.

Ceasurile pentru numărătoare din acest dispozitiv vor fi în următorul mod:

-Primul numărător de la secunde va avea ceasul (clockul) un tren de impulsuri cu perioada de o secundă (T=1s).

-Al doilea numărător de la secunde va avea ceas atunci când primul numărător va ajunge la 10.

-Primul numărător de la minute va avea ceas atunci când numărătoarele de la secunde vor ajunge la 60 (primul la 0, al doilea la 6).

-Al doilea numărător de la minute va avea clock atunci când primul va ajunge la 10.

-Primul numărător de la ore va avea clock aunci când numărătoarele de la minute vor ajunge la 60 (promul la 0 al doilea la 6).

-Al doilea numărător de la ore va avea clock atunci când primul numărător va ajunge la 10.

Schema unui astfel de disozitiv numeric este dată în figura 4.5.

160

Proiectare logică

SISTEM DE AFIŞARE7 SEGMENTE

(SECUNDE)


(MINUTE)


(MINUTE)


(ORE)

SISTEM DE AFIŞARE 7 SEGMENTE

(ORE)

14

13

12

11

IIII

SISTEM DE AFIŞARE7 SEGMENTE(SECUNDE) NU

MĂR

ĂTOR

SECU

NDE

NUM

ĂRĂT

ORM

INUT

ENU

MĂR

ĂTOR

MIN

UTE

NUM

ĂRĂT

OROR

ENU

MĂR

ĂTOR

ORE

NUM

ĂRĂT

ORSE

CUND

ERE

SET

RESE

TRE

SET

RESE

TRE

SET

RESE

T

24

23

22

21

IIII

34

33

32

31

IIII

44

43

42

41

IIII

54

53

52

51

IIII

64

63

62

61

IIII

14

13

12

11

IIII

24

23

22

21

I

III

34

33

32

31

IIII

44

43

42

41

IIII

54

53

52

51

IIII

64

63

62

61

IIII

ck

ck

ck

ck

ck

Ck (T=1S)

Fig.4.5.Schema unui dispozitiv numeric care simulează un ceas.

161


4.6. Afişare alfanumerică

Sistem de afişare alfanumeric pe 35 punctePentru afişarea informaţiilor alfanumerice se utilizează o

matrice de leduri cu 7 linii şi 5 coloane. Afişarea informaţiei se face prin aprinderea unui număr de leduri într-o anumită combinaţie specifică fiecărui caracter în parte. Aprinderea ledurilor are loc fie prin baleierea liniilor fie prin baleierea coloanelor, într-un ritm suficient de rapid, astfel încât să se creeze senzaţia unei baleieri continue.

Matricea are 35 puncte, unde 0 înseamnă LED stins şi 1 înseamnă LED aprins. Fiecare caracter alfanumeric este memorat (pe linii sau cooane) într-o memorie de tip PROM, numită generator de caractere.

În tabelul 4.1. este ilustrat modul de generare al caracterului F prin baleiere pe linie.

În tabelul 4.2. este ilustrat modul de generare al caracterului F prin baleiere pe coloană.

Tabelul 4.1. Modul de generare al caracterului F prin baleiere pe linie.

Codul ASCII A3A2A1 Q1Q2Q3Q4Q5

b7b6b5b4b3b2b1

A10A9A8A7A6A5A4

000 1 1 1 1 1001 1 0 0 0 0

1000110 010 1 0 0 0 0011 1 1 1 1 0100 1 0 0 0 0101 1 0 0 0 0110 1 0 0 0 0

162

Proiectare logică

Tabel 4.2. Modul de generare a caracterului F prin baleiere pe coloane.

Codul ASCII A3 0 0 0 0 1B7 b6 b5 b4 b3 b2 b1 A2 0 0 1 1 0A10 A9 A8 A7 A6 A5 A4 A1 0 1 0 1 0

1 0 0 0 1 1 0

Q1 1 1 1 1 1Q2 1 0 0 0 0Q3 1 1 1 1 0Q4 1 0 0 0 0Q5 1 0 0 0 0Q6 1 0 0 0 0Q7 1 0 0 0 0

Semnalele de comandă se obţin din generatorul de caractere de la adresele specificate prin A7A6A5A4A3A2A1 . Pentru ambele moduri de afişare semnalele A3A2A1 se schimbă asigurând baleierea liniilor, respectiv a coloanelor, pentru fiecare caracter în parte. Semnalele de adresă cele mai semnificative A10A9A8A7A6A5A4 rămân neschimbate formând codul caracterului. Cu cele 7 semnale de adresă b7 = A10, b6 =A9, b5 =A8, b4 =A7 , b3=A6, b2=A5, b1=A4 se pot adresa 128 caractere, aceste adrese respectând codul ASCII.

O modalitate de realizare a unui afişor alfanumeric este prezentată în figura 4.6. Acest afişor este realizat cu baleiere pe coloane. În cadrul setului standard caracterele sunt unic determinate prin cei 6 biţi mai puţin semnificativi ai codului ASCII şi deci bitul 7 poate fi neglijat. Pe cele 6 intrări de adresă mai semnificative ale generatorului de caractere se aplică codul ASCII al caracterului ce urmează a fi afişat. Pe cele 3 intrări de adrese mai puţin semnificative se aplică codul coloanei. Adresele de coloane se generează cu un numărător modulo 5, ciclic, într-

163


un ritm suficient de rapid astfel încât să se creeze senzaţia de afişare continuă. Coloanele afişorului se acţionează pe rând de către un decodificator. Pe cele 7 linii, sincron cu activarea coloanei, se aplică codul de comandă al LED-ului din generatorul de caractere.

321 AAA

9

8

7

6

5

4

AAAAAA

7

6

5

4

3

2

1

QQQQQQQ

GENERATORDE

IMPULSURI

DECODOR

NUMĂRĂTORMODULO 5

6

5

4

3

2

1

bbbbbb

123 AAA

Fig.4.6.Sistem de afişare alfanumeric.

164


BIBLIOGRAFIE

1. Isvan Sztoianov, De la poarta TTL la microprocesoare, Editura Tehnică, Bucureşti, 1987

2. Vasile Pop şi V.Popovici, Circite de comutare, aplicaţii în calculatoarele electronice, Ed.Facla,1976.

3. Dan Nicula , Electronică digitală.Carte de învăţătură, Editura Universotăţii Transilvania, Braşov,2012.

4. Dan Nicula, Electronică digitală.Laboraaator, Editura Universităţii Transilvania, Braşov, 2009.

5. Nicolae Cupcea, Electronică digitală, Andrei Club Cisco, 2013.

6. I. Bucur , Proiectare logică.Probleme. 2013.7. S.D. Ahghel, Electronică digitală,8. Sabina Buzoi, Proiectare logică, SCRIBD

INC.2014.

166


CUPRINS

Pg.PROIECTARE LOGICĂ

1 CAPITOLUL ! BAZELE ARITMETICE ALE CALCULATOARELOR 31.1. SISTEME DE NUMERAŢIE………………… 3

1.1.1. BAZA UNUI SISTEM DE NUMERAŢIE 31.1.2. CONVERSIA NUMERELOR DINTR-O BAZŞ ÎN ALTA… 51.1.3. OPERAŢII ARITMETICE ÎN BINAR, OCTAL ŞI

HEXAZECIMAL…………………………………………….8

1.2. REPREZENTAREA NUMERELOR ÎN CALCULATOR…………… 121.2.1. REPREZENTAREA NUMRELOR ÎN VIRGULĂ FIXĂ…... 121.2.2. REPREZENTAREA NUMERELOR ÎN VIRGULĂ

MOBILĂ……………………………………………………..16

1.2.2.1. REPREZENTAREA ÎN VM SIMPLĂ PRECIZIE… 171.2.2.2. REPREZENTAREA ÎN VM DUBLÎ PRECIZIE….. 191.2.2.3. OPERAŢII ÎN VM………………………………….. 19

1.3. CODURI DE REPREZENTARE A INFORMAŢIEI………………… 201.3.1. CODURI NUMERICE……………………………………… 22

1.3.1.1. CODURI PONDERATE……………………………. 221.3.1.2. CODURI NEPONDERATE………………………… 241.3.1.3. CODURI PENTRU DETECTAREA ŞI CORECTAREA ERORILOR………………………………..

25

1.3.2. CODURI ALFANUMERICE……………………………….. 332 CAPITOLUL 2. BAZELE LOGICE ALE SISTEMELOR DE CALCUL 39

2.1. ALGEBRA BOOLE…………………………………………………… 392.2. FUNCŢII LOGICE. CIRCUITE LOGICE…………………………….. 49

2.2.1. PORŢI LOGICE…………………………………………….. 502.2.2. IMPLEMENTAREA FUNCŢIILOR LOGICE……………… 53

2.3. FORMA CANONICĂ A FUNCŢIILOR LOGICE…………………… 572.4. MINIMIZAREA FUNCŢIILOR LOGICE---------------------------------- 64

2.4.1. METODA KARNAUGH………………………………….. 642.4.2. METODA QUINE-McKLUSKEI………………………….. 73

3 CAPITOLUL 3. CIRCUITE LOGICE…………………………………... 853.1. CIRCUITE LOGICE COMBINAŢIONALE………………………….. 85

3.1.1. MULTIPLEXOARE…………………………………………. 853.1.2. DEMULTIPLEXOARE………………………………………. 883.1.3. APLICAŢII ALE MULTIPLEXOARELOR ŞI

DEMULTIPLEXOARELOR…………………………………92

168

Proiectare logică3.1.4. CODIFICATOARE…………………………………………... 963.1.5. DECODIFICATOARE………………………………………. 993.1.6. COMPARATOARE………………………………………….. 1063.1.7. CIRCUITE ARITMETICE COMBINAŢIONALE…………. 108

3.1.7.1. SUMATOARE…………………………………… 1083.1.7.2. MULTIPLICATOARE 1123.1.7.3. CIRCUITE SAU ŞI ŞI LA NIVEL DE BIT……….. 1163.1.7.4 UNITATE ARITMETICO-LOGICĂ……………... 117

3.1.8. ARII PROGRAMABILE…………………………………….. 1203.2. CIRCUITE SECVENŢIALE………………………………………….. 123

3.2.1. CIRCUITE BISTABILE…………………………………….. 1233.2.2. APLICA ŢII ALE BISTABILELOR………………………. 129

3.2.2.1. NUMĂRĂTOARE………………………………. 1293.2.2.2. REGISTRE……………………………………… 1323.2.2.3. MEMORII………………………………………… 1373.2.2.4. CONVERTOARE…………………………………. 139

3.2.3. CIRCUITE PROMO………………………………………… 1434 CAPITOLUL IV. APLICAŢII ÎN PROIECTAREA LOGICĂ…………. 149

4.1 CĂUTAREA UNEI VALORI ÎN REGISTRE………………………… 1494.2 AFLAREA MAXIMULUI DINTRE MAI MULTE NUMERE…… 1504.3 COMANDA UNUI SEMAFOR…………………………………….. 1524.4 AFIŞARE NUMERICĂ……………………………………………….. 1544.5 SIMULAREA UNUI CEAS………………………………………….. 1554.6 AFIŞĂRE ALFANUMERICĂ……………………………………….. 157

BIBLIOGRAFIE…………………………………………………………………… 161

169

curs proiectare;kl;

Documents