1

SISTEME DE NUMERAIE

Sistemele de numeraie sunt ansambluri de reguli de reprezentare a numerelor cu ajutorul simbolurilor denumite cifre. Acestea pot fi poziionale cum este sistemul zecimal i nepoziionale cum este sistemul roman. ntr-un sistem poziional de baz B un numr N cu parte ntreag i parte fracionar, separate prin punct (virgul) se scrie sub forma urmtoare: (1.1) N = bn 1bn 2 bn 3 ...b1b0 b1b 2 b3 ...b (m 1) b m , simbolurile bi sunt coeficienii cu care se nmulesc puterile Bi ale bazei n dezvoltarea polinomial a numrului pentru obinerea valorii sale (exprimat n zecimal). N = bn1 Bn1 + bn2 Bn2 + bn3 Bn3 +...+ b1 B1 + b0 B0 + b1 B1 + b2 B2 + b3 B3 + m (1.2) +...+ b(m1) B(m1) + bm Bm = bi Bii=n1

Pentru oricare sistem de numeraie simbolul bazei sistemului se scrie cu cifrele unuzero 10, iar numrul semnelor distincte pentru cifrele sistemului este egal cu B (de exemplu, pentru sistemul zecimal (0, 1, 2,..., 8, 9), B = 10 ; n sistemul de numeraie binar (0,1), B = 2). Relaia (1.2) explic de ce astfel de sisteme sunt denumite poziionale; fiecare cifr bi, (din rangul i) intr n valoarea numrului respectiv cu o pondere dat de puterea i" a bazei B. Fiecare numr se obine din numrul anterior prin adugarea unei uniti la ultima cifr. n tabelul 1.1 sunt exprimate numerele naturale de la 033 n sistemele de numeraie cu baza B = 10, 2, 13, 16 (pentru fiecare poziie scriindu-se i puterea bazei). La sistemele de numeraie cu baza mai mic dect zece se utilizeaz tot semnele arabe (cele specifice pentru baza 10), iar la cele cu baza mai mare dect zece se introduc simboluri noi; de exemplu, pentru sistemul n baza 16 (hexazecimal) se introduc urmtoarele simboluri 10=A, 11=B, 12=C, 13=D, 14=E, 15=F. Specificarea bazei n care sunt exprimate numerele exist mai multe convenii ns, n general, pentru baza 16 se adaug litera H, iar pentru baza 8 se adaug litera Q. Exist algoritmi (reguli) de conversie a unui numr dintr-o baz n alta. Algoritmul de conversie zecimal-binar, N|10 N|2, pentru un numr ntreg se deduce pornind de la expresia (1.2) sub forma: (1.3) N = bn1 2 n1 + bn 2 2 n 2 + ... + b3 2 3 + b2 2 2 + b1 2 1 + b0 2 0 Prin mpriri succesive N = 2(bn 1 2 n 2 + bn 2 2 n 3 + ... + b3 2 2 + b2 21 + b1 21 + b1 ) + b0 unde: bn 1 2 n 2 + bn 2 2 n 3 + ... + b3 2 2 + b2 21 + b1 21 + b1 = N 1 i b0 este rest N 1 = 2(bn 1 2 n 3 + bn 2 2 n 4 + ... + b3 21 + b2 ) + b1 unde: bn 1 2 n 3 + bn 2 2 n 4 + ... + b3 2 1 + b2 = N 2 i b1 este rest (1.4) N k = 2(bn 1 2 n k 2 + ... + bn k 1 ) + bk unde: bn 1 2 n k 2 + ... + bn k 1 = N k i bk este rest se obin resturile care sunt tocmai biii numrului N exprimat n binar, de exemplu 93|10?|2 1

93=246+1 bn-7 = 1 46=223+0 bn-6 = 0 23=211+1 bn-5 = 1 11=2 5+1 bn-4 = 1 5=2 2+1 bn-3 = 1 2=2 2+0 bn-2 = 0 1=2 0+1 bn-1= 1 6 5 4 3 N = 1 2 + 0 2 + 1 2 + 1 2 + 1 2 2 + 0 21 + 1 2 0 = 93 10 Astfel: 93 10 =1011101 2 Algoritmul de conversie zecimal-binar, N|10 N|2, pentru un numr fracionar (subunitar) se deduce pornind de la expresia: N 2 = b1 2 1 + b2 2 2 + b3 2 3 + ... + b( m1) 2 ( m1) + b m 2 m (1.5) Prin nmuliri succesive cu 2 N 2 = b1 + b 2 2 1 + b3 2 2 + ... + b( m1) 2 ( m 2) + bm 2 ( m1)

N1 2 = b 2 + b3 2 1 + ... + b( m1) 2 ( m3) + b m 2 ( m 2) .. N k 1 2 = b k + b k 1 + ... + b m 2 ( m 2 ) unde: b 2 2 1 + b3 2 2 + ... + b( m1) 2 ( m 2) + b m 2 ( m1) = N1 ; b3 2 1 + ... + b( m1) 2 ( m3) + b m 2 ( m 2) = N 2

(1.6)

b k 1 + ... + b m 2 ( m 2 ) = N k se obin pri ntregi (0 sau 1) care sunt tocmai biii numrului N exprimat n binar, de exemplu 0.48932 10 = ? 2 . nmulirea se oprete cnd partea fracionar devine zero sau

cnd se consider satisfctor un numr de cifre binare pentru precizia stabilit. 0.48932 2 = 0 + 0.97864 b-1 = 0 0.97864 2 = 1 +0.95728 b-2 = 1 0.95728 2 = 1 +0.91456 b-3 = 1 0.91456 2 = 1 +0.82912 b-4 = 1 0.82912 2 = 1 +0.75824 b-5 = 1 0.75824 2 = 1 +0.51648 b-6 = 1 0.51648 2 = 1 +0.03296 b-7 = 1 0.48932 10 = 0.0111111... 2

N = 0 2 1 + 1 2 2 + 1 2 3 + 1 2 4 + 1 2 5 + 1 2 6 + 1 2 1 + ... = 0.48932 10 Pentru conversia zecimal-binar a unui numr ce prezint att parte ntreag, ct i parte fracionar se combin cei doi algoritmi. Din exemplele de mai sus s-a putut vedea c pentru conversia binar-zecimal, N|2 N|10, se adun puterile succesive ale lui 2, fiecare fiind nmulit cu bitul din poziia respectiv a numrului binar. Algoritmii dedui mai sus (1.4) i (1.6) pot fi aplicai i n cazul conversiei zecimal-octal, zecimal-hexazecimal etc. Conversiile directe octal-binar, hexazecimal-binar, ct i conversiile inverse binaroctal, binar-hexazecimal se realizeaz mult mai simplu datorit faptului c 8 i 16 sunt puterile lui doi (23, 24). Un numr (mai mic dect baza) n octal i n hexazecimal poate fi exprimat prin trei cifre binare (triad) respectiv prin patru cifre binare (tetrad).

2

Tabelul 1.1 Numerele naturale pn la 33 exprimate n bazele 10,2,16 i 13N 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 101 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 N10 100 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 23 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 N2 22 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 21 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 20 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 161 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 N16 100 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 1 131 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 N13 130 0 1 2 3 4 5 6 7 8 9 A B C 0 1 2 3 4 5 6 7 8 9 A B C 0 1 2 3 4 5 6 7

Deci conversiile n ambele sensuri se bazeaz pe corespondena dintre triade n numrarea binar i numerele pn la apte la numrarea n baza 8, respectiv dintre tetrade n numrarea binar i numerele pn la 15 n numrarea n baza 16. Exemple: 001 101.111 0102=15.788 unde: 0011, 1015, 1117, 0102; 2.048=10.00012 unde: 2010, 0000, 4100; 1001 0000 1111 0010 10102 = 90F.2A16 i 1D.C16 = 0001 1101.11002 unde: 10019, 00000, 1111F, 00102, 1010A, 00011, 1101D, 1100C. Conversiile inverse binar-hexazecimal, binar-octal se realizeaz delimitnd cuvntul binar de la dreapta spre stnga (sau pornind de la punctul prii fracionare n ambele sensuri) n tetrade sau triade i nlocuindu-le cu cifrele corespunztoare din sistemul hexazecimal, respectiv din sistemul octal. Conversiile directe hexazecimal-binar, octal-binar (care n fond sunt considerate codificri hexazecimal-binar, octal-binare se realizeaz simplu prin substituia cifrelor hexazecimale sau octale prin tetrade sau triade corespunztoare. 3

1.1

CODURI

Codificare presupune realizarea unei schimbri a formei de exprimare a informaiei, altfel spus o translatare de limbaj. Fie X = {x1, x2, x3, , xp} mulimea simbolurilor primare, emise de o surs de informaie i care urmeaz a fi codificate prin intermediul unor simboluri elementare dintr-o alt mulime B = {b1, b2, b3,, bn}. Prin operaia de codificare se asociaz fiecrui element x X al sursei primare de informaie o secven de simboluri bi B, astfel nct modelul de codificare va fi reprezentat prin corespondena biunivoc: x1 b1b3b1b4 = s1 x2 b2b1b2 = s2 x3 b3b1b1b5 = s3 xp b1b3b1b4 = sp Cuvintele de cod s1, s2, s3, ..., sp formeaz o nou mulime S = { s1, s2, s3, ..., sp }. Cu aceste consideraii putem acum defini codificarea ca o coresponden biunivoc ntre cele dou mulimi X i S, deci codificarea este o aplicaie bijectiv de forma f: X S. Codul este uniform dac toate cuvintele s1, s2, s3, ..., sp au aceeai lungime (dar n acest caz aplicaia nu este totdeauna surjectiv). n electronica digital mulimea B este mulimea binar {0,1}, deci cuvintele mulimii S (care formeaz codul pentru informaia primar) sunt cuvinte binare de o anumit lungime, n general de 8, 16, 24, 32 bii. Pentru microprocesoarele standard lungimea este de 8 bii, suportul fizic care implementeaz cuvntul poate fi un registru cu capacitatea minim de 8 bii sau o locaie din memorie, la fel cu capacitatea minim de 8 bii, reprezentate ca n tabelul 1.2. Tabelul 1.2 Reprezentarea unui cuvnt cu lungimea de 8 bii ntr-un registru sau o locaie de memorie. b7 b6 b5 b4 b3 b2 b1 b0

Bitul cel mai semnificativ (MSB)

Bitul cel mai puin semnificativ (LSB)

n tehnica microprocesoarelor informaia primar, care se codific sub form de cuvinte binare, poate fi compus numai din simboluri numerice (numere) sau att din simboluri numerice, ct i literale i semne de ortografie (evident cu semantica ce li se atribuie); rezult deci dou tipuri de coduri, numerice i respectiv coduri alfa-numerice. 1.1.1 Reprezentarea numerelor Prin intermediul cuvintelor binare se pot codifica numere din sistemul de numeraie binar, octal, zecimal, hexazecimal etc. rezultnd respectiv coduri binare, octal-binare, zecimal-binare, hexazecimal-binare etc. a) Reprezentarea numerelor ntregi fr semn. Corespondena ntre un numr n sistemul binar i un cuvnt (de cod) n binar poate fi chiar identitate, adic cuvntul de cod este chiar numrul respectiv ca n tabelul 1.3. Un cuvnt de 1 bait (8 bii) poate reprezenta numere ntre 0 i 255, deci o mrime fizica exprimat printr-un cuvnt de 8 bii poate fi msurata cu o rezoluie de 1/256. n cazul 4

cnd aceast rezoluie nu este satisfctoare pentru mrimea respectiv (se exprim printrun numr mai mare de 256) cuvntul care o reprezint n microprocesor va fi format din doi, trei sau mai muli octei alturai. Un numr zecimal m poate fi exprimat n binar printr-un numr de bii egal cu log2 m. Tabelul 1.3 Reprezentarea numrului binar ntreg echivalentul lui 17910Coeficienii Cuvntul binar Puterile bazei Valorile termenilor Total b7 1 27 127=1 28 b6 0 26 026= 0 Numr binar ntreg fr semn b5 b4 b3 b2 1 1 0 0 25 24 23 22 b1 1 21 121= 2 b0 1 20 120= 1

125= 124= 023= 022= 32 16 0 0 128+0+32+16+0+0+2+1=179

b) Reprezentarea numerelor fracionare fr semn. La fel ca i numerele ntregi, numerele fracionare binare pot fi reprezentate printr-un cuvnt binar, tabelul 1.4. Punctul (virgula) nu se reprezint fizic (n registru sau n locaia de memorie), dar programatorul trebuie s tie ntre care bii ai cuvntului este localizat. Uneori, fiecare numr binar de n bii (avnd valoarea maxim 2n-1) este nmulit (scalat) cu 2-n, deci se reduce la un numr subunitar, punctul (virgula) se consider ca fiind localizat n faa bitului celui mai semnificativ (valoarea maxim se reduce la 1-2-n, intervalul de reprezentare n microprocesor fiind ntre 0 i 1-2-n). Tabelul 1.4 Reprezentarea numrului binar fracionar echivalentul lui 22,37510Cuvntul binar Puterile bazei Valorile termenilor Total 1 24 124=1 6 0 23 023=0 Numr binar fracionar fr semn 1 1 0 0 22 122=4 21 121=2 20 020=0 2-1 02-1= 0 1 2-2 12-2= 0,25 1 2-3 12-3= 0,125

16+0+4+2+0+0+0,25+0,125=22,375

c) Reprezentarea numerelor cu semn. Pentru reprezentarea unui numr binar N ntreg, cu semn, de n-1 bii N = bn-2 bn-3 bn-4 b4 b3 b2 b1 b0 , cu valoarea absolut NN = bn2 2n2 + bn3 2n3 + bn4 2n4 + ... + b3 23 + b2 22 + b1 21 + b0 20 = bi 2ii =0 n2

(1.9)

n tehnica microprocesoarelor este necesar un registru sau o locaie de memorie cu capacitatea de n bii. Bitul bn-1 cel mai semnificativ (MSB) al registrului adugat la cei n-1 bii va reprezenta semnul numrului: bn-1 = 1 pentru minus, bn-1 = 0 pentru plus, tabelul 1.5 (a,b,c). Exist trei forme (mai uzuale) de reprezentare a numerelor binare cu semn: n mrime i semn, n complement fa de 1 i n complement fa de 2. Tabelul 1.5 (a,b,c) Codificarea numerelor 125Bit de semn 0 Reprezentarea numrului n baza 2 1 1 1 1 1 0 1 Valoarea n baza 10 +125 Reprezentare n mrime i a

5

1 0 1 0 1 27 (-1)2 = -1287

1 1 0 1 0 26 02 = 06

1 1 0 1 0 25 02 = 05

1 1 0 1 0 24 02 = 04

1 1 0 1 0 23 02 = 03

1 1 0 1 0 22 02 = 02

0 0 1 0 1 21 02 = 21

1 1 0 1 1 20 12 = 10

-125 +125 -125 +125 -125 -

semn n complement fa de 1 n complement fa de 2 Total -125

b c

d) Reprezentarea numerelor binare (cu semn) n mrime i semn. n aceast reprezentare bitul bn-1 = 1 pentru minus, bn-1 = 0 pentru plus, restul biilor bn-2bn-3b3b2b1b0, reprezint numrul n valoare absolut N, tabelul 1.5 a. Valoarea n zecimal a numrului cu semn se scrie sub forma:N = ( 1) n 1 bn 2 2 n 2 + bn 3 2 n 3 + ... + b1 2 1 + b0 2 0 = ( 1) n 1 bi 2 ib b i =0

[

]

n2

(1.10)

i se poate situa n intervalul:

2 n1 1 N 2 n1 1 . (1.11) Din relaiile (1.10) i (1.11) se deduce c un cuvnt de microprocesor standard (de un bait) poate exprima numere n domeniul -127+127. Zero are dou exprimri +000000000 i -010000000. Aceast reprezentare n mrime i semn are o utilizarea redus, doar n unele voltmetre digitale. Acest numr N cu semn, de lungime n-1 bii, poate fi reprezentat i scalat, adic mprit cu 2n-1, obinndu-se conform relaiei (1.11), domeniul de existen a valorii numrului: N (1.12) (1 2 n +1 ) n 1 (1 2 n + 2 ). 2 Pentru numrul scalat se consider c punctul (virgula) este situat totdeauna dup bitul de semn, MSB. e) Reprezentarea numerelor binare (cu semn) n complement fa de 1. Fie numrul N cu lungimea de n-1 bii: N = bn 2 bn3bn4 ...b4 b3b2 b1b0 (1.13) negatul acestui numr N (sau complementul fa de 1) se obine prin complementarea fiecrui bit: N = b n 2 b n 3 b n 4 ...b 4 b 3 b 2 b 1 b 0 (1.14) Practic, complementul unui numr se poate realiza cu o structur de circuit SAU EXCLUSIV. Adunnd relaiile (1.13) i (1.14) se obine: N + N = 111...111 (1.15) n 1 Codurile de n bii pentru numerele ntregi pozitive N 2 1 se obin, la fel ca la reprezentarea prin mrime i semn, adic este chiar numrul de n-1 bii la care se adaug n poziia cea mai semnificativ bn1 = 0 . Codurile pentru numerele negative de n-1 bii N 2 n1 1 se obin prin complementarea fiecrui bit bi b i , iar n poziia cea mai semnificativ se adaug bitul bn 1 = 1 , tabelul 1.5 b, adic: N n comp. de 1 = 1 b n 2 b n3 b n4 ...b 4 b 3 b 2 b 1 b 0 (1.16)

(

)

(

)

(

)

6

ntr-un registru de n bii se nscriu n complement fa de 1 numere (de n-1 bii) a cror valoare este n intervalul dat de relaia (1.11). Aceast valoare poate fi scalat la fel cu 2n-1 obinndu-se relaia (1.12), punctul (virgula) considerndu-se a fi situat dup bitul de semn. Zero are dou reprezentri: 0000 0000, 1111 1111. f) Reprezentarea numerelor binare (cu semn) n complement fa de 2. Codificarea numerelor binare cu semn n complement fa de doi este foarte utilizat, n tehnica microprocesoarelor, deoarece simplific efectuarea operaiilor aritmetice. Din relaia (1.15) se obine: N + N + 1 = 100 ...000 sau

2n N = N + 1 (1.17) n n care numrul 2 N este denumit complementul lui N fa de doi. Se convine a se exprima numrul negativ -N nu prin valoarea sa real, ci prin complementul lui fa de 2n i se scrie sub forma (-N):(1.18) Un numr pozitiv N de n-1 bii se codific n complement fa de doi, identic ca n complement fa de unu sau ca mrime i semn, adic sub forma unui cuvnt de n bii cu bitul cel mai semnificativ bn1 = 0 . Urmtorii n-1 bii sunt exact biii numrului N. Un numr negativ -N de n 1 bii se codific n complement fa de doi, relaia (1.18), ca i n complement fa de 1, dar n plus se adun unu la bitul cel mai puin semnificativ. Bitul de semn este bn 1 = 1 , deci cu bitul de semn cuvntul n cod complement de doi are n bii. Practic complementul fa de 2 al numrului -N se obine n felul urmtor: se complementeaz toi biii numrului N, se adun 1 la bitul cel mai puin semnificativ b0, se ataeaz bitul de semn (cel mai semnificativ) de valoare bn-1 =1. De exemplu: N = 125 10 1111101 2 , se complementeaz 0000010, se adun 1 la bitul cel mai puin semnificativ, 000 0010+ 1 =000 0011, i se adaug bitul de semn 1000 0011. Sau, ntr-o alt modalitate: numrul -125 0 pentru N < 0 (1.20)i =0 n2

N = ( 1) 2 n 1 + b i 2 ii =0

Din relaiile (1.20) se deduce c ntr-un cuvnt de n bii poate fi codificat un numr de n-1 bii a crui valoare se situeaz n intervalul: (1.21) 2 n 1 N 2 n 1 1 De exemplu, un cuvnt de un bait poate codifica numerele din intervalul [-128, +127] fiind cu 1 mai multe numere negative dect pozitive, iar pentru zero corespunde o singur reprezentare 0000 0000. Evident, i n complement de 2 numerele pot fi scalate (nmulite cu 2-n+1) adic aduse n intervalul: N (1.22) 1 n 1 1 2 n +1 2

7

Toate consideraiile privind codificarea numerelor cu semn s-au fcut pentru un numr ntreg de n bii ca n relaia (1.8). Acestea pot fi extinse i asupra numerelor fracionare date sub forma (1.1), dar n acest caz este necesar pentru codificare un cuvnt de lungimea n+m bii plus un bit de semn. Numerele fracionare pot fi apoi scalate prin mprire cu 2n-1, deci punctul (virgula) va fi situat dup bitul de semn. Toate aceste codificri scalate cu punctul (virgul) dup bitul de semn se mai numesc reprezentri n virgula fix. Dac numerele care se codifica au valori n afara intervalului dat de relaiile (1.11), (1.21) sau (scalate) de relaiile (1.12), (1.22), atunci se pot folosi cuvinte formate din mai muli octei. n cazul cnd un cuvnt extins pe mai muli octei nu satisface precizia de calcul, sau rezoluia cu care se reprezint o mrime fizic, se trece la reprezentarea n virgul mobil (flotant). g) Reprezentarea numerelor n virgul flotant. Un numr N reprezentat n virgul flotant are dou componente. Prima E, denumit exponent, d indicaii asupra ordinului de mrime al numrului, iar a doua, denumit mantis M, d indicaii asupra mrimii exacte a numrului ntr-un anumit domeniu. N=MBE n care B este baza (de obicei 2). Att pentru mantis, ct i pentru exponent se poate repartiza, ntr-o reprezentare pe un registru sau n memorie, mai mult dect un bait. De exemplu, n figura 1.6 sunt repartizai pentru numr 4 octei; n primii trei octei este reprezentat mantisa cu semnul corespunztor, iar n al patrulea octet exponentul cu semn. Tabelul 1.6 Reprezentarea numrului n virgul flotant pe patru octei consecutivi. Exponent Al patrulea b6 b5 b4 b3 b2 b1 b0 +/bait Al treilea bait Al doilea bait Primul bait

+/ b16 b8

b23 b15 b7

b22 b14 b6

b21 b13 b5

b20 b12 b4

b19 b11 b3

b18 b10 b2

b17 b9 b1

Mantis

Cu aceti patru octei se pot reprezenta numere n intervalul -2232127N2232127 (sau scalate n intervalul -1 2-128 N 12-128) adic numere de forma: XXX XXXX XXXX XXXX XXXX XXXX2 n care x are valoarea 1 sau 0. Un microprocesor standard proceseaz numerele n virgul flotant printr-un numr mare de operaii ceea ce necesit timp de calcul destul de lung i de aceea s-au realizat procesoare specializate (coprocesoare matematice) care preiau efectuarea unor astfel de calcule. 1.1.2 Coduri numerice

a) Coduri zecimal-binare (BCD) n aceast clas de coduri zecimal-binare, BCD (Binary Coded Decimal) mulimea X a sursei primare de informaie care trebuie codificat este format din simbolurile cifrelor 0,1,2,3,4,5,6,7,8,9, iar mulimea cuvintelor de cod trebuie s conin cel puin zece cuvinte distincte. Cuvintele de cod trebuie s aib cel puin patru bii, deoarece 23 < 10 < 24 = 16. Stabilind corespondene ntre mulimea cifrelor zecimale i mulimea celor 16 cuvinte 10 binare de patru bii se obin n total A16 posibiliti de codificare. Din acest mare numr de coduri posibile exist anumite variante mai uzuale care pot fi mprite n: coduri ponderate i coduri neponderate. 8

b) Coduri ponderate. Un cod ponderat asociaz fiecrei cifre zecimale o tetrad binar, iar ponderea fiecrui bit din tetrad este egal cu valoarea cifrei din denumirea codului, tabelul 1.7. Cifra zecimal codificat se obine prin suma biilor din cuvntul de cod, ponderai cu valoarea corespunztoare din denumirea codului. Tabelul 1.7 Coduri zecimal - binare.Numere n zecimal 0 1 2 3 4 5 6 7 8 9 8421 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 Coduri ponderate 2421 4221 0000 0001 0010 0011 0100 1011 1100 1101 1110 1111 0000 0001 0010 0011 0110 1001 1100 1101 1110 1111 Coduri zecimal - binare Coduri neponderate 7421 Exces 3 Gray 2 din 5 8421 cu bit de paritate 0000 0011 0000 00011 10000 0001 0100 0001 00101 00001 0010 0101 0011 00110 00010 0011 0110 0010 01001 10011 0100 0111 0110 01010 00100 0101 1000 0111 01100 10101 0110 1001 0101 10001 10110 0111 1010 0100 10010 00111 1001 1011 1100 10100 01000 1010 1100 1101 11000 11001

Pentru codul ponderat simbolizat prin 8421, n cuvntul din cod, bitul zero are ponderea 1(=2), bitul unu ponderea 2(=21), bitul doi ponderea 4(=22) i bitul trei ponderea 8(=23). Deoarece fiecare bit are ponderea numrrii n binar i cuvintele de cod chiar numerele succesive n sistemul binar natural, acest cod se mai numete codul zecimal-binar natural NBCD (Natural-Binary-Coded-Decimal). n terminologia curent este denumit (impropriu) doar codul BCD. De exemplu, cifra 9 se codific 1001, adic lx8+0x4+0x2+ +1x1 =9. Aceeai regul de fixare a ponderii bitului din cuvntul de cod, egal cu cea din notaia codului, se respect la toate celelalte coduri ponderate. De exemplu, 10112421 = 1x2+0x4+1x2+1x1 = 510; 10014221 =1x4+0x2+0x2+1x1 =510. Unele cifre zecimale pot fi reprezentate n mai multe variante. De exemplu, n codul 7421 pentru cifra 7 pot exista cuvintele 0111 sau 1000. Ambiguitatea este nlturat dac se utilizeaz din toate cuvintele de cod uniform numai acelea care corespund numrului maxim de bii semnificativi (0111). n cazul codului 2421 cifra 6 are dou cuvinte 1100 i 0110; s-a ales cuvntul de cod 1100 din motivele expuse n continuare. Codurile ponderate 2412 (codul Aiken dup numele profesorului Howard Aiken, care a realizat, ntre anii 19391944, la Universitatea Harward, o main de calcul automat MARK I, precursorul primelor calculatoare electronice) i 4221 au pentru primele patru cifre zecimale aceeai exprimare ca i codul 8421. n continuare, cuvntul corespunztor cifrei 5 se obine din cel al cifrei 4 prin complementare (complement de 1), aceeai regul se aplic pentru obinerea cuvntului de cod al cifrei 6 din cel al cifrei 3, respectiv 7 din 2, 8 din 1 i 9 din 0. Deci cele dou cifre zecimale complementare fa de 9 (0 cu 9, 1 cu 8, 2 cu 7, 3 cu 6, 4 cu 5) au cuvintele de cod obinute prin inversare. Codurile ce prezint aceast proprietate sunt denumite i coduri autocomplementare. c) Coduri neponderate. Codurile neponderate, cele mai uzuale, sunt cele prezentate n tabelul 1.6. Cuvntul de cod n EXCES 3 se obine din cuvntul de cod 8421, al cifrei zecimale respective, la care se adaug 0011, adic 3 n binar. n codul EXCES 3 se poate face distincie, pentru o locaie a memoriei sau un registru, ntre lipsa unei informaii nscrise i nscrierea lui zero,

9

deoarece zero este codificat prin 0011 (a disprut din cod cuvntul 0000, ceea ce reprezint lipsa unei informaii). d) Codul Gray. Acesta are proprietatea de adiacen, n sensul c trecerea de la o cifr zecimal la urmtoarea se face prin modificarea unui singur bit din cuvntul de cod. Acest cod este util pentru mrimile care cresc succesiv (traductoare unghiulare de poziie, codificarea n diagrama Karnaugh de minimizare a funciilor logice). n tabelul 1.8 este reprezentat, ntr-un registru cu capacitatea de un bait, cuvntul de cod 8421 pentru numrul zecimal 86. Dac numrul zecimal este mai mare de 99, atunci cuvntul de cod necesit mai mult de un bait. De exemplu, numrul 943810 va avea corespondentul 1001 0100 0011 1000 n cod 8421. i n codurile BCD se pot reprezenta numere cu semn, dar n acest caz este necesar n cuvntul de cod un bit n plus pentru reprezentarea semnului. Tabelul 1.8 Reprezentarea printr-un cuvnt de un bait a numrului 8610 n codul NBCD101 zeci 100 uniti 1 23 123=8 0 0 22 21 022=0 021=0 1 810 =80 0 20 020=0 0 23 023=0 1 1 22 21 122=4 121=2 0 (2+4) 10 =6 0 20 020=0

Total 80 + 6 = 86

Transmiterea informaiei prin medii puternic influenate de zgomote poate fi nsoita. de introducerea de erori. Verificarea transmiterii corecte a datelor se poate face cu ajutorul unor coduri speciale denumite coduri detectoare de erori. n codurile detectoare de erori fiecare cuvnt de cod are un numr par sau impar, de exemplu, de bii 1. La emisie se adaug sau nu fiecrui cuvnt un bit unu, astfel nct numrul de bii 1 s fie par sau impar (dup convenia codului). La recepie se numr n fiecare cuvnt numrul de bii 1 i se determin dac este par sau impar tiind, n felul acesta, dac, pe calea de transmisie, informaia a fost eronat. De exemplu, pentru codul 8421 cu bit de paritate, tabelul 1.6, cifra trei se reprezint astfel 10011, n care biii informaionali sunt 0011 (=3), iar bitul al cincilea =1 este bitul de paritate care se adaug la emisie, realiznd o paritate impar. Cu regulile expuse se poate verifica doar modificarea pe calea de transmisie a cuvntului de cod ca un numr impar de bii, modificarea cu un numr par nu poate fi sesizat i n plus nu se poate ti n care poziie a cuvntului s-a modificat bitul. Exist coduri mai complexe care pe lng faptul c determin bitul eronat i corecteaz acest bit, denumite coduri corectoare. e) Codul 2 din 5. Acesta prezint un cuvnt de cod de 5 bii, dintre care numai doi bii sunt semnificativi (au valori egale cu 1). n acest fel se realizeaz o unicitate a reprezentrii, ntruct din cele 25 = 32 de cuvinte posibile cu 5 bii numai 10 satisfac condiia (2 din 5). Acest cod creeaz posibilitatea controlului (detectrii) erorilor multiple la transmiterea informaiei. f) Coduri octal-binar i hexazecimal-binar Codul octal-binar realizeaz corespondena biunivoc ntre cifrele sistemului de numeraie n baza opt i cuvintele formate din trei bii (triade) n felul urmtor: 0000, 1001, 2010, 3011, 4100, 5101, 6110, 7111. La fel, codul hexazecimalbinar realizeaz corespondena biunivoc ntre cifrele sistemului de numeraie n baz 16 i 10

cuvintele succesive de patru bii (tetrade) din sistemul de numeraie binar n felul urmtor: 00000, 10001, 20010, 30011, 40100, 50101, 60110, 70111, 81000, 91001, A1010, B1011, C1100, D1101, E1110, F1111. 1.1.3 Coduri alfanumerice Codurile alfanumerice stabilesc o coresponden biunivoc ntre mulimea informaiei primare X (relaia (1.7)) format din cifre, litere i semne speciale, denumite, n general, caractere si mulimea cuvintelor (binare) de cod de o lungime oarecare. Codificarea datelor alfanumerice este necesar pentru a putea memora mesaje sau a reprezenta grafic mesaje. n mod normal este util a se codifica 88 de caractere distincte, n care sunt cuprinse 52 simboluri pentru minusculele i majusculele alfabetului, 10 simboluri pentru cifrele zecimale i 26 de caractere speciale (de punctuaie, comenzi etc.). Codificarea acestor caractere necesit minim 7 bii (27 = 128>88). n tehnica microprocesoarelor lucrndu-se cu un cuvnt de un bait, al optulea bit din cuvnt poate fi utilizat pentru verificarea paritii. La majoritatea microprocesoarelor s-a adaptat codul ASCII (American Standard Code for Information Interchange codul american standard pentru schimb de informaii), iar unele accept codul EBCDIC (Extended Binary Coded Decimal Interchange Code codul pentru transferuri cu codificarea zecimal-binar extins). Codurile ASCII i EBCDIC au o structur asemntoare, codul ASCII avnd o eficien mai mare n situaia comparrii unor caractere care urmeaz n secven normal (de exemplu, ordinea normal a literelor n alfabet). 0 ntrebare fireasc se pune uneori pentru codificare, cum poate s identifice P ntre codul unui numr i codul unui caracter alfanumeric n cazul cnd cele dou cuvinte sunt identice? Sarcina de a fi tratat deosebit acelai cuvnt revine programatorului prin modul de poziionare a celor dou cuvinte n spaiul memoriei. n cazul sistemelor industriale de comand n timp real un cuvnt binar de un bait poate codifica 8 variabile binare (care reprezint mrimi fizice cu dou stri), de exemplu, n tabelul 1.9. Aceti bii pot fi procesai separat ( ca n cazul circuitelor logice) sau se opereaz asupra ntregului cuvnt ceea ce este propriu sistemelor cu microprocesoare. Tabelul 1.9 Exprimarea binar a opt mrimi fizice ntr-un bait.Cuvntul de 8 bii b0 b1 b2 b3 b4 b5 b6 b7 Sistemul comandat Pomp Motor electric 1 Motor electric 2 Comutator Limitator de curs Temperatur Presiune For Variabile logice Bitul =0 Bitul = 1 Oprit Pornit Decuplat Cuplat Decuplat Cuplat Deschis nchis Nedepit Depit Valoarea minim Valoarea maxim Valoarea minim Valoarea maxim Valoarea minim Valoarea maxim

11

2

ELEMENTE DE ALGEBR BOOLEAN

Activitatea uman, n domeniul tehnic cel puin, se desfoar prin analiza i prelucrarea informaiei care se prezint sub diferite forme cu caracteristici diverse. Astfel, informaia poate fi: continu sau cuantificat, previzibil sau aleatoare, constant sau variabil, msurabil sau nemrginit. Posibilitile organismului uman sunt limitate n ceea ce privete identificarea, msurarea, prelucrarea i stocarea mrimilor care caracterizeaz materia i diverse fenomene i de aceea omul se folosete de mijloace tehnice concepute i realizate cu scopul reprezentrii i procesrii informaiilor. Folosirea semnalelor electrice (sarcin, tensiune, curent), magnetice sau optice sunt avantajoase din multe puncte de vedere pentru acest scop. Exprimarea cantitativ a informaiei se face prin diferii parametrii ai acestor semnale ca: amplitudine, form, frecven, faz. Domeniile valorilor acestor parametrii, ca mrimi analogice, sunt n submulimi ale mulimii numerelor reale i cel puin teoretic chiar pentru variaii orict de mici numrul valorilor este nelimitat. n teoria digital (digit - cifr, n limba englez) aceti parametri pot lua numai valori discrete. Acestea se reduc pentru majoritatea cazurilor uzuale la dou niveluri considerate prin convenie "1" (unu logic) i "0" (zero logic). n exprimarea curent referirea la unu sau zero logic se face prin cuvntul bit, abreviaie din l. englez BInary digiT (cifr binar). Algebra boolean (de la numele matematicianului englez George Bool, 1815-1864, care a pus bazele algebrei logice), a fost conceput ca o metod simbolic de tratare a funciilor logicii formale. Ulterior metoda a fost dezvoltat i aplicat i n alte domenii ale matematicii. Astfel, n anul 1938, Claude Shannon a folosit-o pentru prima oar la analiza circuitelor de comutaie. De atunci, algebra boolean s-a impus ca fiind cel mai important mijloc matematic de analiz i sintez a circuitelor de comutaie, deoarece ntre logica formal i circuitele de comutaie exist urmtoarea analogie: - logica studiaz valoarea de adevr sau fals a unor afirmaii care nu pot fi dect adevrul sau falsul; - circuitele de comutaie sunt realizate prin interconectarea unor comutatoare, iar starea acestora nu poate fi dect nchis sau deschis. Avnd n vedere cele menionate, rezult c din punct de vedere formal att logica ct i circuitele de comutaie vor putea fi tratate cu o algebr definit pe o mulime format din dou elemente, de exemplu 0 i 1. Algebra boolean este definit pe baza urmtoarelor axiome: Fie o mulime M compus din elementele x1, x2, xn mpreun cu operaiile "" i "+", ce vor fi definite ulterior. Aceast mulime formeaz o algebr dac: 1. Mulimea M conine cel puin dou elemente distincte x1 x2, x1 M i x2 M; 2. Pentru orice x1 M i x2 M avem: x1 x2 M i x1 + x2 M ; (2.1) 3. Operaiile "" i "+" au urmtoarele proprieti: a) sunt comutative: x1 x2 = x2 x1 ; x1 + x2 = x2 + x1 ; (2.2) b) sunt asociative: ( x1 x 2 ) x 3 = x1 ( x 2 x 3 ); (2.3) ( x 1 + x 2 ) + x 3 = x1 + ( x 2 + x 3 ) c) sunt distributive una fa de cealalt:

12

(2.4) x1 + ( x 2 x 3 ) = ( x1 + x 2 ) ( x1 + x 3 ) 4. Ambele operaii admit cte un element neutru cu proprietatea: x1 + 0 = 0 + x1 = x1 ; x1 1 = 1 x1 = x1 (2.5) unde 0 este elementul nul al mulimii iar 1 este elementul unitate al mulimii. 5. Dac mulimea M nu conine dect dou elemente, acestea trebuie s fie n mod obligatoriu elementul nul i elementul unitate, atunci pentru orice x M va exista un element unic notat x cu proprietile: x x = 0 , proprietate cunoscut sub numele de principiul contradiciei; x + x = 1 , proprietate cunoscut sub numele de principiul terului exclus. Elementul x este inversul elementului x. n definiia axiomatic a algebrei s-au folosit dou legi de compoziie notate cu simbolurile "+", respectiv "", precum i notaia x pentru elementul invers. n logic, respectiv n tehnic, pentru aceste legi de compoziie se folosesc denumiri i notaii specifice, aa cum rezult din tabelul 2.1.Tabelul 2.1 Denumirea operaiilorMatematic Prima lege de compoziie x1+x2 A doua lege de compoziie x1x2 Elementul invers Logic Disjuncie Tehnic SAU

x1 ( x 2 + x 3 ) = x1 x 2 + x1 x 3 ;

x1 x2Conjuncie

x1 x2I x1x2NU

x1 x2Negare

x2.1

x

x

INTERPRETAREA OPERAIILOR ALGEBREI BOOLEENE Semnificaia legilor de compoziie poate fi ilustrat n mai multe moduri: 1. Prin diagrama Venn, figura 2.1.

Figura 2.1 Ilustrarea semnificaiei legilor de compoziie prin diagrame 2. Cu ajutorul tabelelor de adevr. Prin tabelul de adevr se stabilete o coresponden ntre valorile de adevr ale variabilelor i valoarea de adevr a funciei.Tabelul 1.2 Tabelul de adevr al operaiilor de baz. x1 x2 x x1 x2 x1 x2 x00 01 10 11 0 0 0 1 0 1 1 1 0 1 1 0

13

Pentru o mai bun nelegere a sensului acestor operaii, ele vor fi ilustrate i cu ajutorul unor scheme simple realizate cu o surs de tensiune E, dou ntreruptoare K1, K2 i un bec B. ntreruptoarelor Ki li se asociaz variabilele xi astfel: Ki deschis xi = 0; Ki nchis xi = 1. Becul B va indica rezultatul operaiei astfel: dac rezultatul este zero becul B rmne stins iar n caz contrar se aprinde. Cu aceste precizri se poate urmrii uor funcionarea circuitelor din figura 2.2, ce realizeaz operaiile I, SAU, NU.

Figura 2.2 Ilustrarea semnificaiei legilor de compoziie prin circuite simple: a) circuit I; b) circuit SAU; c) circuit NU. n cazul circuitului inversor din figura 2.2 c, ntreruptorul K este normal nchis (becul B este aprins). La aplicarea semnalului de comand x ntreruptorul K se deschide i becul se stinge. 2.2 REGULI DE CALCUL N ALGEBRA BOOLEAN.

Plecnd de la axiome se deduc o serie de teoreme care vor forma reguli de calcul n cadrul algebrei. Sunt prezentate n continuare principalele teoreme fr demonstraii. 1. Principiul dublei negaiix=x

(2.6) (2.7) (2.8) (2.9) (2.10) (2.11)

Dubla negaie duce la o afirmaie. 2. Legile de idempoten 3. Legile de absorbie

xx ... x = x; x+x+ ... +x = x

(2.12) x1 + x2 = x1 x2 Cu ajutorul acestor formule se poate transforma produsul logic n sum logic i invers (prin trecerea negaiei de la termeni la argumente i invers). Verificarea acestor teoreme se poate face uor cu ajutorul tabelelor de adevr i cu observaia c dou funcii sunt egale dac iau aceleai valori n toate punctele domeniului de definiie. Pentru exemplificare s verificm prima teorem a lui De Morgan. Notm: (2.13) f 1 ( x1 x 2 ) = x1 x2 i f 2 ( x1 x2 ) = x1 x 2 Vom scrie valorile de adevr ale celor dou funcii n toate punctele domeniului de definiie, aa cum este indicat n tabelul 2.3.

x1 ( x1 + x2 ) = x1 ; x1 + x1 x2 = x1 4. Legile elementelor neutre x1=x; x0=0; x+0=x; x+1=1 5. Formulele lui De Morgan x1 x2 = x1 + x2

14

Tabelul 2.3 Verificarea egalitii a dou funcii x2 x1 x1x2 x1 f 1 = x1 x20 0 1 1 0 1 0 1 0 0 0 1 1 1 1 0 1 1 0 0

x21 0 1 0

f 2 = x1 x21 1 1 0

Din tabelul 2.3 se observ c funciile f1 i f2 iau aceleai valori n toate punctele domeniului de definiie deci sunt egale. 2.3 FUNCII BOOLEENE

2.3.1 Generaliti 0 funcie f: {0, l}n {0, 1} se numete funcie boolean. Cu alte cuvinte, o funcie de n variabile y=f(x1, x2 ...xn) ce se va caracteriza prin faptul c att variabilele ct i funcia nu pot lua dect dou valori distincte. Funcia va pune n coresponden fiecrui element al produsului cartezian n dimensional valorile zero sau unu. Asemenea funcii vor fi utile pentru caracterizarea funcionrii unor circuite construite cu elemente de circuit avnd dou stri, cum ar fi de exemplu: un ntreruptor nchis sau deschis, un tranzistor blocat sau n conducie etc. Funcionarea unui astfel de element de circuit va fi descris de o variabil boolean x. Dac considerm acum un ansamblu de ntreruptoare interconectate ntre ele ntr-un mod oarecare, unele nchise altele deschise, ele se reprezint ca n fig. 2.3.

Figura. 2.3. Asocierea unei funcii booleene cu o reea de ntreruptoare. Existena sau inexistena unei ci de curent ntre bornele terminale ale ansamblului va depinde de modul de interconectare al acestora, precum i de starea fiecruia n parte. Aceast dependen se exprim din punct de vedere matematic cu o funcie boolean de forma: y = f ( x1 , x2 ... xn ). (2.14) 2.3.2 Reprezentarea funciilor booleene Pentru reprezentarea funciilor booleene se folosesc n mod frecvent dou modaliti: a) tabelul de adevr; b) diagrama Karnaugh. Reprezentarea cu tabelul de adevr nseamn practic a marca ntr-un tabel corespondena ntre valorile de adevr ale variabilelor de intrare i valoarea de adevr a funciei n fiecare punct al domeniului de definiie.

15

Exemplu: fie funcia I y=x1x2. Fiind o funcie de dou variabile, domeniul de definiie este format din 22=4 puncte, corespunztor tuturor combinaiilor variabilelor de la intrare. Reprezentarea cu ajutorul diagramelor Karnaugh const n a marca punctele domeniului de definiie ntr-o diagram plan i precizarea valorilor funciei n fiecare din aceste puncte. Tabelul 2.4 Exemplu: Pentru funcia I definit prin tabelul 2.4 domeniul de definiie l reprezint vrfurile unui ptrat de latur unu, aa cum este indicat n fig. 2.4 a. 0 0 0 Diagrama Karnaugh, reprezentnd funcia SI este 0 1 0 desenat n fig. 2.4 c. Diagrama Karnaugh din fig. 2.4 c se 1 0 0 mai poate desena i sub forma prezentat n fig. 2.4 d. n 1 1 1 legtur cu aceasta din urm reprezentare, trebuie remarcat faptul c succesiunea combinaiilor corespunztoare variabilelor x1 i x2 trebuie scris n codul binar reflectat pentru a se pstra vecintile din diagrama original.x1 x2 y=x1x2

Figura 2.4 Reprezentarea unei funcii de dou variabile: a) domeniul de definiie; b) tabelul de adevr; c) i d) diagrame Karnaugh. n cazul unei funcii de trei variabile y = f(x1, x2, x3), domeniul de definiie este format din 23=8 puncte i reprezint vrfurile unui cub cu latura unu (fig. 2.5 a). Pentru funcii de trei variabile diagramele Karnaugh corespunztoare pot fi prezentate fie sub forma din fig. 2.5 b, fie aa cum este indicat n fig. 2.5 c.

Figura 2.5 Reprezentarea domeniului de definiie al unei funcii de trei variabile: a) cub cu latura unu; b i c) diagrame Karnaugh. n fig. 2.5 b coordonatele punctelor binar, ceea ce ne va permite s analizm considerare vrful cubului caracterizat reprezentarea din fig. 2.5 a, ca acest vrf 110 i 011. n diagrama Karnaugh din 16 domeniului de definiie au fost nscrise n mai uor vecintile. Dac lum n prin coordonatele 010 constatm, din este vecin cu urmtoarele vrfuri: 000, fig. 2.5 b constatm c vrful 010 este

vecin doar cu vrfurile 011 i 000. Pentru ca diagrama din fig. 2.5 b s fie echivalent cu reprezentarea din fig. 2.5 a, va trebui s pstreze aceleai vecinti, lucru ce devine posibil doar dac ne imaginm c latura din stnga a diagramei Karnaugh din fig. 2.5 b este identic cu cea din dreapta i cea de sus cu cea de jos. n fig. 2.5 c combinaiile corespunztoare variabilelor x2 x1 s-au scris n cod binar reflectat, iar coordonatele vrfurilor n zecimal. Cu aceste precizri cu privire la domeniul de definiie n fig. 2.6 este dat un exemplu de funcie de trei variabile reprezentat n trei moduri diferite.

Figura 2.6. Reprezentarea unei funcii de trei variabile: a) pe cubul cu latura unu; b i c) prin diagrame Karnaugh. Figura 2.7. Diagrama Karnaugh corespunztoare unei funcii de patru variabile

n fig. 2.7 este reprezentat diagrama Karnaugh pentru o funcie de patru variabile, unde prin sgei s-au marcat vecintile punctului de coordonate 0010. 2.3.3 Funcii booleene elementare Forma general a unei funcii booleene de n variabile este y = f(x1, x2, ..., xn). Domeniul de definiie al acestei funcii este format din m=2n puncte. Cum n fiecare din aceste puncte funcia poate lua numai valorile 0,1, rezult c numrul total al funciilor n booleene de n variabile este N = 2 2 . Se vor considera n cele ce urmeaz funciile booleene elementare de una i de dou 1 variabile. Pentru n=l funcia este de forma y=f(x) i numrul acestora este N = 2 2 = 4 , iar cele patru funcii sunt trecute n tabelul 2.5. Tabelul 1.5. Funcii booleene de o variabil Constanta unu Variabila x x Constanta zero Variabila negat x f1=1 f2=x f0=0 f3= x0 1 0 02

1 1

0 1

1 0

Pentru n=2 rezult N = 2 2 = 16 funcii de dou variabile, adic de forma y=f(x1,x2) reprezentate n tabelul 2.6. Tabelul 2.6 Funcii booleene de dou variabile.

17

Nr. crt 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1

Funcia logic y=f(x1 x2) 2 Elementul nul Elementul unu Funcie ce nu depinde de x1 Funcie ce nu depinde de x2 Negaia Negaia Conjuncia Negarea conjunciei Disjuncia Negarea disjunciei Echivalena Negarea echivalenei Implicaia direct Negarea implicaiei directe Implicaia invers Negarea implicaiei inverse f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 3

Domeniul de definiie x1 0101 x2 0011 4 0000 1111 0011 0101 1010 1100 0001 1110 0111 1000 1001 0110 1011 0100 1101 0010

Denumirea circuitului 5 CIRCUIT DESCHIS CIRCUIT NCHIS IDENTITATE IDENTITATE INVERSOR INVERSOR I - (AND) I NU (NAND) SAU - (OR) SAU NU (NOR) COINCIDENA (NXOR) SAU EXCLUSIV (XOR) INTERDICIE INTERDICIE

Figura 1.8

a b c d e f g h i j k l m n o p

Din examinarea tabelului 2.6 observm c: f0 i f1 nu sunt funcii, ci constante; f2, f3, f4 i f5 nu sunt funcii de dou variabile, ci doar de una singur; funciile apar n perechi (funcia i inversa ei). Definiia axiomatic a algebrei booleene prezentat apeleaz la dou legi dex2a b c

x2

x1d

x1 ____ x1. x2h

x1e

_ x1

x2f

_ x2

x1 x2g

x1 . x2

x1 x2

x1 x2i

x1 \/ x 2 _ x1\/ x 2m

x1 x2j

____ x1\/ x 2 _ x1 . x2n

x1 x2k

x1 + x 2 x1 _ x1 \/ x 2o

____

x1 x2l

x 1+ x 2

x1 x2

x1

x2

x2

x1

x2p

_ x1 . x2

Figura 2.8. Simbolurile circuitelor care realizeaz funciile booleene din tabelul 1.6 compoziie notate cu "" respectiv "+" n cazul n care mulimea M conine doar dou elemente, fiecrui element x i se asociaz un unic element x numit inversul elementului x. Acest lucru nseamn c n expresia oricrei funcii booleene de n variabile vor aprea numai aceste trei operaii elementare. Din punct de vedere practic acest lucru nseamn c

18

un sistem fizic al crui funcionare este descris de o funcie boolean se va putea realiza prin interconectare unui numr de trei tipuri de circuite elementare i anume: circuitul I (realizeaz operaia ""), circuitul SAU (realizeaz operaia "+") i circuitul INVERSOR (realizeaz inversarea). Se demonstreaz, c acelai sistem fizic poate fi realizat practic utiliznd un singur tip de circuit elementar de exemplu circuitul I-NU (NAND) sau circuitul SAU-NU (NOR). Aceste posibiliti de sintez se bazeaz pe scrierea funciilor booleene sub form disjunctiv respectiv conjunctiv canonic. Utilizarea circuitelor NAND sau NOR la realizarea unui sistem sunt echivalente din punct de vedere teoretic ns din punct de vedere practic alegerea este dictat de familia de circuite integrate cu care se lucreaz. De exemplu n familia de circuite integrate TTL Circuitul NAND se realizeaz uor motiv pentru care se prefer sinteza cu astfel de circuite pe cnd n familia de circuite ECL circuitul NOR se realizeaz mai uor i deci se va prefera sinteza cu acesta. 2.3.4 Forma canonic a funciilor booleene n numeroase aplicaii apare necesitatea reprezentrii analitice a funciilor booleene. n acest scop se recurge la aa numitele forme de dezvoltare. n algebra boolean se folosesc dou asemenea forme de dezvoltare. forma disjunctiv canonic (FDC), care presupune utilizarea unor funcii elementare numite constitueni ai unitii; forma conjunctiv canonic (FCC), care presupune utilizarea unor funcii elementare numite constitueni ai lui zero. Pentru o tratare sistematic a problemei, se introduc urmtoarele notaii: x pentru i = 1 (2.15) xi = x pentru i = 0 Definiia 1. Se numete constituent al unitii funcia elementar uk, caracterizat prin aceea c ia valoarea unu ntr-un singur punct al domeniului de definiie. n cazul unei funcii de n variabile, constituentul unitii va fi produsul logic (conjuncia) tuturor variabilelor negate sau nenegate, dup urmtoarea regul: i i i u k = x1 1 x 2 2 ... x n n (2.16) Pentru ca acest produs s fie unu ntr-un anume punct al domeniu-lui de definiie, este necesar ca toi termenii produsului s fie egali cu unu. Pentru ca un termen de forma i x j j s fie unu este necesar ca ij=xj. De aici rezult urmtoarea regul de scriere a funciei elementare uk: n conjuncia variabilelor, variabilele care iau n respectivul punct al domeniului de definiie valoarea zero se vor lua negate iar celelalte nenegate. Definiia 2. Se numete constituent al lui zero funcia elementar v1 care ia valoarea zero ntr-un singur punct al domeniului de definiie. n cazul unei funcii de n variabile, expresia constituentului se va scrie ca disjuncia tuturor variabilelor negate sau nenegate. i i i vi = x1 1 x2 2 ... x n n (2.17) Condiia de constituent al lui zero impune x jij

=0 pentru orice j ceea ce implic

i j = x j . Rezult c n scrierea constituentului lui zero v1, ntr-un anume punct al domeniului de definiie, se vor lua negate variabilele care iau valoarea unu n acel punct i nenegate cele care iau valoarea zero. Constituenii unitii uk se mai numesc i termeni minimali (minterm) ai funciei, iar constituenii v1 ai lui zero se mai numesc i termeni maximali (maxterm) ai funciei. 19

De exemplu n tabelul 2.7 s-au indicat constituenii unitii i ai lui zero n fiecare punct al domeniului de definiie pentru o funcie de trei variabile. Tabelul 2.7 Constituenii lui zero i unu pentru o funcie de trei variabile i i i x1 x2 x3 Exemplu de funcie v =x x x uk = x1 x2 x3 z1 2 3

i1

i2

i3

i

1

2

3

000 001 010 011 100 101 110 111

0 1 2 3 4 5 6 7

u= x1 u= x1 u= x1 u= x1 u= x1 u= x1 u= x1

x 2 x3 x 2 x3 x 2 x3 x 2 x3 x 2 x3 x 2 x3 x 2 x3

v0 = x1 x 2 x 3v1 = x1 x 2 x 3

0=0 1=1 2=0 3=1 4=1 5=0 6=1 7=0

v 2 = x1 x 2 x 3 v3 = x1 x2 x3 v4 = x1 x2 x3 v5 = x1 x2 x3 v6 = x1 x2 x3 v7 = x1 x2 x3

u= x1 x 2 x 3

n coloana a doua a tabelului 2.7 a fost notat prin i valoarea ne specificat a funciei booleene de trei variabile. n ultima coloan, prin specificarea valorilor, s-au dat exemple de funcii. Formele canonice ale unei funcii booleene de trei variabile sunt urmtoarele: FDC y = 0 u0 1 u1 2 u 2 3 u 3 4 u 4 5 u 5 6 u6 7 u7 (2.18) FCC y = ( 0 u0 )( 1 u1 )( 2 u 2 )( 3 u 3 )( 4 u 4 )( 5 u 5 )( 6 u6 )( 7 u7 ) (2.19) n cazul general al unei funcii de n variabile, forma disjunctiv canonic reprezint disjuncia tuturor constituenilor unitii pe care i are funcia:

FDC y = f ( x1 , x2 ,..., xn ) = i uii =1

n

(2.20)

Forma conjunctiv canonic a unei funcii de n variabile va reprezenta conjuncia tuturor constituenilor lui zero pe care i are funcia:

FCC y = f ( x1 , x2 ,..., xn ) = k u kk =1

n

(2.21)

Dac se revine la exemplul funciei de tei variabile prezentat n ultima coloan a tabelului 2.7 vor rezulta urmtoarele forme canonice:

FDC y = f ( x1 , x2 ,..., xn ) = i ui = u1 u3 u4 u6i =1

7

(2.22)

sau

y = x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 (2.23) Se observ c din expresia general dat de relaia 1.1 dispar termenii pentru care i=0 (deoarece 0ui=0 i 0 u k = u k )FCC y = f ( x1 , x2 ,..., xn ) = ( i ui ) = v0 v2 v5 v7i =1 7

(2.24)

sau

y = ( x1 x2 x3 ) x1 x2 x3 x1 x2 x3 x1 x2 x320

(

)(

)(

)

(2.25)

n cazul FCC din expresia general dat de relaia 1.2 dispar termenii pentru care k=1 (deoarece 1 vk = 1 i 1 v1 = v1 ). 2.3.5 Forma minim a funciilor booleene Avnd n vedere faptul c algebra boolean se va folosi la analiza i sinteza circuitelor de comutaie, nu este greu de anticipat c ntre gradul de complexitate al circuitului i cel al funciei pe care l descrie exist o legtur directa. Acesta este motivul pentru care n etapa de sintez a circuitelor de comutaie, dup definirea acestora, urmeaz n mod obligatoriu etapa de minimizare a funciei, avnd drept scop obinerea unei forme echivalente mi simple (forma minim). Realizarea practic a circuitului urmeaz a se face pe baza acestei forme simple. Avnd n vedere importana practic a minimizrii, n literatura de specialitate se gsesc descrise numeroase metode. Dintre acestea se vor prezenta pe scurt numai dou, i anume: metoda analitic; , metoda diagramelor Karnaugh. a) Metoda analitic Aceast metod de obinere a formei minime se bazeaz pe folosirea teoremelor algebrei booleene. Principiul metodei se va ilustra pe exemplul anterior al funciei de trei variabile. Se va pleca de la forma disjunctiv canonic (1.5) a funciei: y = u1 u3 u4 u6 = x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 (2.26) Avnd n vedere proprietatea de distributivitate care se aplic termenilor u1 i u3 respectiv u4 i u6 rezult: y = x1 x3 x2 x2 x1 x3 x2 x2 (2.27)

(

)

(

)

innd seama i de proprietatea terului exclus ( x x = 1 ) i de faptul c 1 este elementul unitate ( x 1 = x ), rezult forma disjunctiv minim (FDM) a funciei: y = x1 x3 x1 x 3 (2.28) Procednd similar se poate gsi i forma conjunctiv minim (FCM) a funciei. b) Metoda diagramelor Karnaugh Aceast metod nu reprezint altceva dect transpunerea operaiilor fcute la metoda analitic pe reprezentarea funciei prin diagrame Karnaugh, rezultnd astfel n final o metod expeditiv de minimizare. 0 diagram Karnaugh poate fi privit, dac se ia n consideraie produsul logic al coordonatelor, ca o reprezentare a funciei booleene prin termeni minimali (constitueni ai unitii). Vom ilustra aceasta n cazul unei funcii de trei variabile cu tabelul 2.7. Tabelul 2.7. Termenii minimali pentru o funcie de trei variabilex2 x3 x1 0 1 00 01 11 10

x1 x2 x3 x1 x2 x3

x1 x2 x3 x1 x2 x3

x1 x2 x3x1 x2 x3

x1 x2 x3 x1 x2 x3

Fiecare celul din diagrama Karnaugh reprezentat n tabelul 2.7 conine un termen minimal. Dou celule vecine conin termeni minimali, care difer prin valoarea unei singure variabile. Dac termenilor minimali din dou celule vecine li se aplic proprietatea de distributivitate i cea a terului exclus, se elimin variabila care i schimb valoarea. Pe

21

diagrama Karnaugh acest lucru revine la a scrie coordonatele comune ale ansamblului celor dou celule vecine. Acest proces poate fi urmrit pe exemplul ilustrat n figura 2.10.

Figura 2.10. Exemple de minimizare De exemplu: gruparea celulelor vecine care conin constituenii u1 i u3 ne conduce la expresia x1 x3 , iar gruparea celulelor vecine care conin constituenii u4 i u6 conduce la expresia x1 x3 . Forma disjunctiv minim a funciei rezult prin scrierea disjunciei grupurilor de coordonate comune ale gruprilor formate astfel: y = x1 x3 x1 x3 (2.29) Metoda poate fi generalizat astfel: 1. Dac grupul iniial de dou celule vecine este vecin la rndul su cu un alt grup de dou celule vecine, acestea se pot uni ntr-un singur grup de 4 celule vecine, ceea ce va permite eliminarea a dou variabile.

Figura 2.11. Exemple de minimizri pentru funcii de trei i patru variabile (forma disjunctiv minim) 2. Un grup de 2m celule vecine ocupate de uniti permite eliminarea a m variabile. 3. Fiecare celul ocupat de uniti trebuie s fac parte cel puin dintr-o grupare, dar poate fi inclus n mai multe. 4. Cel mai avansat grad de simplificare se obine dac unitile dintr-o diagram Karnaugh sunt grupate ntr-un numr minim de grupuri fiecare grup la rndul su coninnd un numr maxim de uniti.

22

Observaie. Pentru a putea aplica n mod succesiv proprietatea de distributivitate i teorema terului exclus numrul unitilor din gruprile formate trebuie s fie o putere ntreag a lui 2. n fig. 2.11 sunt date cteva exemple de minimizri ale unor funcii booleene de trei i patru variabile. Reguli similare pot fi deduse i pentru obinerea formei conjunctive minime. n acest caz, n diagrama Karnaugh se vor grupa zerourile. Se va scrie disjuncia coordonatelor grupului de zerouri vecine, iar forma minim va fi conjuncia acestor grupuri de coordonate. La scrierea coordonatelor grupurile de zerouri se va avea n vedere faptul c acestea reprezint termeni maximali. n fig. 2.12 se dau dou exemple de minimizare pentru obinerea formei conjunctive minime.

Figura 2.12. Exemple de minimizri pentru funcii de patru variabile (forma conjuctiv minim). n matricea Karnaugh se pot grupa zerourile ca i cnd ar fi uniti, obinndu-se FDM a funciei negate y (valabil i invers). Un astfel de exemplu este dat n figura 2.13. Figura 2.13. Exemplu de minimizare pentru obinerea formei disjunctive minime a funciei negate. c) Minimizarea funciilor incomplet definite Se spune despre o funcie c este incomplet definit dac n anumite puncte ale domeniului poate lua valoarea unu sau zero. Aceste puncte n diagrama Karnaugh vor fi notate cu simbolul x. Atunci cnd vom minimiza funcia vom lua n considerare valoarea unu sau zero a funciei booleene din aceste puncte astfel ca aceast alegere s ne conduc la o form minim mai simpl. De exemplu, atribuirea fcut n figura 2.14 a

23

Figura 2.14. Exemple de minimizri pe funcii incomplet definite: a) atribuireoptim a valorilor funciei; b) atribuire neoptimal a valorilor funciei.

ne conduce la forma minim cea mai simpl a funciei, pe cnd cea fcut n figura 2.14b ne va conduce la o expresie mai complicat a formei minime corespunztoare funciei booleene respective. 2.4 REPREZENTAREA FIZIC A VARIABILELOR

n practica electronic, dintre toate posibilitile de reprezentare a cifrelor binare cea mai uzual este prin dou niveluri distincte ale tensiunii (curentului), aceasta fiind o consecin a faptului c circuitele electronice, care au n structur un element ce prezint dou stri (tranzistorul bipolar sau uniplor n regim de comutaie) sunt cele mai folosite. Deci, n astfel de circuite, diferenei de potenial (fa de mas) ntr-un punct M, ntr-un anumit moment de timp t, i se poate asocia, prin convenie, valoarea binar "1" logic sau "0" logic. De fapt, pentru cele dou niveluri discrete de tensiune (nivel ridicat VH i nivel cobort VL) n practic, sunt considerate dou intervale VH i VL, separate printr-o zon interzis (n care tensiunea nu trebuie s aib valori), figura 2.15. n convenia de logic

Figura 2.15. Nivelurile de tensiune pentru intrri i ieiri asociate variabilelor booleene.

24

pozitiv, unui semnal logic "1" i corespunde intervalul de tensiune VH , mai ridicat fa de mas, iar unui semnal logic "0" i corespunde intervalul VL mai cobort. Invers, n convenia de logic negativ, VH corespunde lui "0" i VL lui "1". De exemplu pentru circuitele integrate TTL (Tranzistor - Tranzistor - Logic) exist urmtoarele valori: tensiunea de alimentare VCC = + 5V ( 0,25V); intervalul tensiunii de ieire pentru starea (High), "1" logic, VOH = 5V2,4V; intervalul tensiunii de ieire pentru starea (Low), "0" logic, VOL = 0,4V0,0V; intervalul tensiunii de intrare pentru nivelul "1" logic, VIH = 2 VCC; intervalul tensiunii de intrare pentru nivelul "0" logic, VIL = 0,0V0,8V. Pentru circuitele integrate de tip MOS variaiile produse de toleranele componentelor realizate practic, ct i cele datorate distorsiunilor i zgomotului, fac ca situaia ideal a dou niveluri unice de tensiune, corespunztoare celor dou valori logice, s fie imposibil de obinut practic. Astfel, informaia va fi reprezentat practic prin domenii sau benzi de tensiune. Pentru a se putea distinge ntre cele dou stri, trebuie prevzut o regiune intermediar interzis valorilor posibile ale tensiunii. Prin urmare au fost definite (figura 2.16) : VOH - nivelul de tensiune de ieire n starea "1" (High). n cazul seriei CMOS 4000 este minim VDD - 0,05V'' (tipic VDD - 0,01V") VOL - nivelul de tensiune de ieire. n starea 0 (Low). Valoarea sa maxim garantat este 0,05 V" (tipic 0,01 V"). VIH - nivelul de tensiune de intrare n starea "1" (SUS), pentru care nivelul logic de la ieire nu se schimb. Valoarea minim garantat este "70% VDD. VIL - nivelul de tensiune de intrare n starea 0 (JOS), pentru care nivelul logic de la ieire nu se schimb i valoarea maxim garantat este ,,30% VDD". Imunitatea la zgomot se definete ca tensiunea maxim de zgomot prezent la intrarea unui inversor (poart logic), care nu comut inversorul dintr-o stare logic n alta. Exist dou puncte pe caracteristica de transfer, n care ctigul inversorului este unitar, cu care se definesc marginile de zgomot.

Figura 2.16. Caracteristicile nivelurilor logice intrare-ieire. Circuitele CMOS rejecteaz impulsuri parazite de tensiune, de valori pn la 45% din valoarea tensiuni de alimentare, dar valoarea garantat de majoritatea fabricanilor este de 30%. Se definesc imunitile la zgomot : VNIL imunitatea la zgomot pentru nivelul LOW (JOS); VNIJ imunitatea la zgomot pentru nivelul HIGH (SUS). 25

Acestea au valori garantate de 30% din valoarea tensiunii de alimentare, ceea ce constituie al doilea avantaj (dup consum) important al circuitelor CMOS. Practic, imunitatea la zgomot este de 45... 50% din valoarea tensiunii de alimentare. Definim drept tranziie pozitiv a unui semnal, trecerea (frontul) semnalului din nivel logic JOS n nivel logic SUS, iar tranziie negativ din nivel logic SUS n nivel logic JOS. Circuitul TTL standard din figura 2.17 are o intrare multiemitor i un etaj de ieire n contratimp. Tranzistorul de intrare multiemitor T1 are o contribuie important asupra vitezei de comutaie a circuitului integrat, iar configuraia de ieire n contratimp mbuntete imunitatea la zgomot i viteza de comutaie. Fiecare intrare a tranzistorului multiemitor poate avea o diod pentru a reduce efectele liniei de transmisie prin amortizarea (limitarea) impulsurilor reflectate. ntruct efectele liniei de transmisie devin cu att mai importante cu ct fronturile impulsurilor sunt mai rapide, plasarea diodelor de limitare devine obligatorie pentru circuitele TTL rapide. Pentru cele mai multe aplicaii, circuitului TTL standard din figura 2.17 ofer cea mai bun combinaie de vitez i disipare de putere. Acest circuit este folosit n circuitele integrate pe scar mic (SSI = Small - Scale Integration) cum ar fi : inversoare, bufere, pori logice I - NU, pori logice SAU - NU, pori logice I - SAU - NU, expandare, circuite basculante i n circuitele integrate pe scar medie (MSI = Medium - Scale - Integration) cum ar fi : decodificatoare, memorii, multiplexoare, numrtoare, registre de deplasare, etc. Pentru o folosire corect este necesar cunoaterea caracteristicilor de intrare i ieire ale circuitului din figura 2.17. Orice dispozitiv folosit pentru a comanda un circuit TTL trebuie s poat absorbi i genera curent. Figura 2.17. Circuitul TTL standard Convenional, curentul care intr n circuit este considerat pozitiv, iar cel care iese este considerat negativ. 2.4.1 Caracteristica de intrare. n figura 2.18 este prezentat caracteristica tipic a curentului de intrare (IIN) n funcie de tensiunea de intrare (UIN). Un potenial sub 0,65 V pe intrarea A sau B (regiunea AB din fig. 2.18) va produce un curent care va curge de la sursa EC prin rezistorul R1, dioda baz-emitor a tranzistorului multiemitor i ieirea sursei de semnal (fig. 2.19, a) : E U BET 1 U IL (2.30) I IL = C R1 Figura 2.18.Caracteristica de intrare a unui circuit TTL n care UIL este tensiunea la intrarea A sau B. Pentru Ec = 5 V, UBET1 = 0,65 V, UIL = 0,4 V, R1 = 4 K se obine IIL = - 1 mA. n cele mai nefavorabile condiii de funcionare trebuie s avem IIL 1,6 mA. 26

Din relaia (2.30) se observ c pentru tensiuni de comand coborte (UIL), consumul de curent al intrrilor legate mpreun este acelai.

Figura 2.19. Circuit de intrare:a pentru curentul IIL; b pentru curenii IL i I.

Pentru valori ale tensiunii de intrare cuprinse n regiunea AB, tranzistorele T2, T4 sunt blocate, iar tranzistorul T3 este saturat. Tensiunea la ieire este independent de cea de la intrare i are valoarea constant (regiunea AB pe caracteristica de transfer din fig. 2.20) : (2.31) U OH = EC U D U BET4 = 5 0,65 0,65 = 3,7V Pentru tensiuni de intrare 0,65 V < UIN < 1,3 V (regiunea BC din fig. 2.18), tranzistorul T2 ncepe s conduc, T4 rmne blocat, iar T3 este deschis. n aceast regiune, n baza tranzistorului T2 se injecteaz un curent de valoare mic II (fig. 2.19, b), T2 are o amplificare mic (R2/R3), iar variaia tensiunii la ieire este lent (regiunea BC din fig.2.20). Pentru tensiuni de intrare mai mari de 1,3 V (regiunea CD din fig. 2.18), tranzistorul T4 intr n conducie untnd rezistena echivalent din emitorul lui T2 i astfel amplificarea acestuia crete (regiunea CD din fig. 2.20). Pe msur ce ne apropiem de punctul D, tranzistoarele T2T4 se satureaz, iar tensiunea la ieire ncepe s se limiteze, cu toate c tranzistorul T3 mai poate fi nc n conducie. Pentru tensiuni de intrare mai mari de 1,5... 1,6 V (regiunea DE din fig. 2.18),

Figura 2.20. Caracteristicile de transfer ale unui circuit TTL. tranzistoarele T2, T4 sunt saturate, T3 este blocat iar jonciunea emitor-baz a tranzistorului multiemitor T1 este blocat. 27

Dac celelalte intrri ale tranzistorului multiemitor T1 sunt lsate n gol sau au un nivel mai mare de 1,5.. .1,6 V, curentul pe o intrare IIH se nchide prin baza tranzistorului T4, iar dac cel puin o intrare este legat la mas, acest curent devine curent de colector pentru tranzistorul T1. Curentul IIH depinde de R1 i de h21eT1. Pentru tensiuni de intrare ridicate (UIH), consumul de curent al intrrilor legate mpreun crete cu numrul acestora. 2.4.2 Caracteristica de ieire. S-a artat c, dac cel puin pe una din intrrile circuitului integrat se aplic o tensiune cobort, T4 este blocat, iar T3 este n conducie. n acest caz, caracteristica tipic a curentului de ieire (I0) n funcie de tensiunea de ieire (U0) arat ca n figura 2.21. Pentru regiunea AB, T4 este blocat, iar T3 este saturat. Curentul furnizat de tranzistorul T3 este : EC U 0 U D U BET3 EC U 0 U D U CEsatT3 I0 = + (2.32) R3 R4 Pentru Ec = 5 V, UD = UBET3 = 0,65 V, UCesatT3 = 0,3 V, Uo = 0 V, R1 = 4 K, R4 = 130 , se obine IOS = 31 mA. Pentru cele mai nefavorabile condiii, valorile standard pentru Ios sunt 20 mA IOS 55 mA. Curentul Ios este disponibil la tranziia de la ieire din nivel cobort n nivel ridicat pentru a ncrca capacitatea de ieire.

Figura 2.21. Caracteristica de ieire a unui circuit TTL pentru nivel ridicat. Pentru regiunea BC, T4 rmne blocat, n schimb T3 nu mai este saturat, ci se afl n conducie. Curentul la ieire are expresia: h21eT3 + 1 EC U BET3 U D U 0 I0 = (2.33) R2 n acest caz, valoarea curentului furnizat de tranzistorul T3 n conducie trebuie s fie mai mare de 0,4 mA (IOH 0,4mA) pentru a putea comanda 10 pori fiecare cu IIH = 40 A (fig. 2.22, a). Dac pe intrrile circuitului integrat se aplic simultan o tensiune ridicat, s-a artat c T3 se blocheaz, iar T4 intr n conducie. n acest caz, caracteristica de ieire arat ca n figura 1.23. n regiunea AB a caracteristicii, tranzistorul T4 rmne saturat, curentul de baz fiind dat de expresia : E 2U D EC U D U ECsatT2 U D (2.34) I BT4 = C R1 R2 R3 n care tensiunea baz-emitor i baz-colector ale tranzistoarelor T1, T2, T3 n conducie direct s-a nlocuit cu tensiunea UD.

(

)(

)

28

Pentru Ec = 5 V, UD = 0,65 V, UCEsatT2 = 0,3 V, R1 = 4 K, R2 = 1,6 K, R3 = 1 K, se obine IBT4= 2,4 mA.

Figura 2.22. Circuit de ieire:a-pentru curentul IOH; b-pentru curentul IOL

Din caracteristicile din figura 2.23 se determin tensiunea la ieire (UOL) pentru un curent IOL = 16 mA (pentru a putea absoarbe curenii de intrare a 10 pori fig. 2.22, b , fiecare cu IIL = 1,6 mA) i trebuie s se obin UOL 0,4 V. Pentru funcionarea sigur a circuitului integrat de obicei se ia o margine de 0, 4 V, astfel c UILmax = 0,8 V i UIHmin = 2 V.

Figura 2.23. Caracteristica de ieire a unui circuit TTL pentru nivel cobort. Marginea de zgomot n c.c. este definit ca diferena ntre limitele domeniilor de tensiune garantate pentru strile logice ale unui circuit care comand i limitele domeniilor de tensiune permise ale unii circuit comandat: M H = U OH min U IH min = 2,4V 2V = 0,4V (2.35) M L = U IL max U OL max = 0,8V 0,4 = 0,4V n realitate, la T == 25C: M H = 3,5V 1,7V = 1,8V (2.36) M L = 1,4V 0,3V = 1,1V 29

ceea ce nseamn c nivelul 1 logic este mai bine protejat contra perturbaiilor. Cu toate acestea, unii fabricani indic pentru marginea de zgomot valoarea tipic de 1 V. Curentul absorbit de la sursa de alimentare pentru o poart se msoar pentru un semnal de intrare cu factor de umplere de 50% i cu o frecven suficient de mic pentru a nu lua n considerare i consumul suplimentar n timpul comutaiei. Pentru circuitul CDB 400E (4 pori NAND) Ic = 8 mA, deci puterea disipat tipic pentru Ec = 5 V este P = 40 mW/capsuI sau 10 mW/poart. Pentru evaluarea vitezei de comutaie a unei pori se definesc doi timpi (fig. 2.24): tPHL timpul de propagare a semnalului pentru comutarea ieirii din starea 1 logic n starea 0 logic i tPLH timpul de propagare a semnalului pentru comutarea ieirii din starea 0 logic n starea 1 logic. Pentru Ec = 5 V, TA == 25C i o ncrcare a ieirii cu 10 intrri tip poart TTL, avem tPHL = 8ns, tPLH = 12ns. Pentru un circuit TTL se definete i un timp de propagare mediu : t +t (2.37) t P = PHL PLH . 2 De obicei, tP = 10ns.

Figura 2.24. Formele de und pentru definirea timpilor de propagare. Timpii de propagare depind puternic de sarcin i mai puin de temperatur i de tensiunea de alimentare. 2.4.3 Circuitul TTL cu colectorul n gol Configuraia etajului de ieire n contratimp nu este potrivit pentru conectarea logic I-cablat (conectarea n paralel) datorit degradrii nivelului de tensiune 0 logic i posibilitii de distrugere a tranzistoarelor din etajul de ieire. Din aceast cauz a aprut circuitul TTL cu colectorul n gol, a crui schem tipic este dat n figura 2.25. Valoarea rezistenei RL, se determin din condiia de realizare a nivelelor logice la ieire i din compromisul dintre timpii de comutaie i consumul de putere. Valoarea maxim a rezistenei RL, se determin din condiia realizrii la ieire a nivelului 1 logic : E U OH (2.38) RLM = C nI OH + mI IH n care, UOH tensiunea necesar la ieire pentru nivelul 1 logic (de obicei UOH 2,4 V), IIH curentul absorbit de un etaj de ieire n starea 1 logic, n numrul circuitelor TTL legate n I cablat, curentul absorbit de un etaj de intrare din cele m circuite TTL de sarcin. Valoarea minim a rezistenei RL se determin din condiia realizrii la ieire a nivelului 0 logic.

30

EC U OL (2.39) I OL + mI IL n care UOL tensiunea necesar la ieire pentru nivelul 0 logic (de obicei UOL 0,4 V), IOL curentul absorbit de un etaj de ieire n starea 0 logic, IIL curentul absorbit de un etaj de intrare din cele m circuite TTL de sarcin. RLm =

Figura 2.25. Circuitul TTL cu colectorul n gol. Impedana de ieire n starea 1 logic datorit sarcinii rezistive este mult mai mare dect cea a ieirii n contratimp. Din aceast cauz utilizarea circuitelor TTL cu colectorul n gol trebuie fcut cu precauie, mai cu seam cnd se are n vedere viteza de comutaie, imunitatea la zgomot n c.a. i comanda unor capaciti mari. Exemplu : pentru Ec = 5 V, UOH = 2,4 V, UOL = 0,4 V, IOH = 0,25 mA, IOL = 16 mA, IIH = 0,04 mA, IL = 1,6 mA, n = 3, m = 4, se obine : RLM = 2 858, RLm, = 479. Pentru realizarea unor timpi de comutaia acceptabili i cu un consum de putere rezonabil, se alege RL= 1 K. Circuitele TTL rapide cu colectorul n gol pot fi obinute fie prin micorarea valorilor rezistenelor din schema din figura 2.25, fie adoptnd circuitul TTL din seria Schottky. 2.4.4 Circuitul TTL cu trei stri Ieirile circuitelor integrate TTL nu pot fi conectate n paralel pentru a realiza un SAU cablat, datorit impedanelor joase de ieire. Cu toate acestea, unele circuite TTL pot fi comandate pentru a realiza un circuit special cu trei stri (tri-state). n figura 2.26, a este prezent un asemenea circuit, n care pentru semnalul de comand DIS = 0, emitorul lui T1 este inut pe 1 logic iar dioda D este blocat. n aceste condiii semnalul de la ieire este egal cu negatul semnalului de la intrare. Dac, ns, DIS = 1, emitorul lui T2 este trecut pe 0 logic, ceea ce nseamn c i n emitorul lui T2 este 0 logic ; deci, tranzistorul T3 este blocat. Cu DIS = 1, dioda D se deschide, cobornd potenialul bazei tranzistorului T3 aproape de potenialul masei ; deci, i T3 se blocheaz. Cu T2, i T3 blocate, ieirea se afl n gol, deci prezint o impedan foarte mare. Atta timp ct DIS = 1, la linia de ieire pot apare semnale (date) de la alt circuit TTL. Unele circuite TTL, cum ar fi cele expandabile CDB 450, CDB 453, etc., au disponibile la pinii capsulei bazele tranzistorelor T3 i T4, care, conectate aa cum se arat n figura 2.26,b, realizeaz un circuit TTL cu trei stri. ntr-adevr, pentru DIS = 0, diodele D1 i D2 sunt blocate, deci la ieirea circuitului se realizeaz funcia SAUNU. Dac,

31

Figura 2.26. Circuite TTL cu trei stri logice:a-schema cu comenzi pe intrare i ieire; b-schema cu comenzi pe ieiri.

ns, DIS = 1, diodele se deschid innd bazele tranzistorelor din etajul de ieire la un nivel sczut, astfel nct acestea sunt blocate.

32

33.1

ARITMETICA NUMERELOR BINARE

ADUNAREA I SCDEREA

Operaiile de adunare i scdere a dou numere fr semn cu cte un bit fiecare sunt definite de tabelul 3.1. Tabelul 3.1. Operaiile de adunare i scdere pentru numere de 1 bit.Operanzi xy 00 01 10 11 Sum Suma S=x+y 0 1 1 0 Transport C 0 0 0 1 Operanzi xy 00 01 10 11 Diferen Diferen D=x-y 0 1 1 0 mprumut B 0 1 0 0

Adunarea a dou numere fr semn cu mai muli bii se efectueaz la fel ca n orice baz adunnd la suma a dou cifre curente transportul de la cifra anterioar. n tabelul 3.2 sunt date valorile sumei si i ale transportului ci+1 spre cifra binar urmtoare, obinute prin adunarea cifrelor xi, yi i a transportului ci, de la cifra anterioar. Tabelul 3.2 Operaia de adunare a cifrelor binare curente pentru numere cu mai muli bii.0 1 2 3 4 5 6 7 xi 0 0 0 0 1 1 1 1 Intrri yi 0 0 1 1 0 0 1 1 Ieiri ci 0 1 0 1 0 1 0 1 ci+1 0 0 0 1 0 1 1 1 si 0 1 1 0 1 0 0 1

n figura 3.1 este dat schema de principiu a unui sumator pentru dou cuvinte binare

Figura 3.1. Sumator pentru cuvinte binare cu n bii.

33

exprimate cu n bii. La fiecare celul de sumare exist intrrile xi, yi ale cifrelor binare de rang i i bitul de transport de la celula anterioar. Transportul final este notat cu C (carry). 3.1.1 Adunarea i scderea n complement fa de doi n cazul numerelor cu semn cu mai muli bii algoritmii de adunare i scdere depind de reprezentarea folosit. n reprezentarea (C2), ambele operaii se pot trata prin intermediul adunrii, lucru avantajos pentru realizarea circuitelor. Acest lucru este posibil deoarece este adevrat urmtoarea afirmaie (de fapt afirmaia definete n sens algebric un izomorfism): Suma algebric a doi operanzi reprezentai n (C2), executat prin sumarea binar a celor dou reprezentri produce acelai rezultat ca reprezentarea n (C2) a sumei executate natural, cu condiia s nu existe depiri. Depirea apare atunci cnd rezultatul nu se mai ncadreaz n domeniul numerelor reprezentabile dat de relaia: 2 n1 N 2 n1 2 m (3.1) Ea se manifest prin alterarea bitului de semn n urma operaiei. Exemplu. Fie dou numere ntregi cu 8 bii n gama (-128)(+127): 127+2=129>+127 depire; (127)2+(2)2=7FH+2H=81H =1000 0001=(-127)2? n care se vede c bitul de semn a luat valoarea eronat 1, deci rezultatul este incorect. Observm c suma. a doi operanzi de semne contrare nu va genera niciodat depire aritmetic. Justificarea afirmaiei privind sumarea n (C2), pentru dou numere ntregi a i b cu n bii, este urmtoarea:

(

)

a) Cazul 1): a 0, b 0

(a) 2 = a (a) 2 + (b) 2 = a + b (b) 2 = b iar (S)2 = (a + b)2 =a + b, deoarece S 0.

(3.2) (3.3)

b) Cazul 2): a < 0, b < 0 (a) 2 = 2 n a n n n n (3.4) (a) 2 + (b) 2 = 2 a + 2 b = 2 a + b + 2 n (b) 2 = 2 b unde ultimul termen scris n binar reprezint un transport deoarece 2 scris n binar este: 2 n = 100040 1 2... 4 3

(

)

n

i depete lungimea de n bii a rezultatului. Dac se neglijeaz acest transport, rezultatul este corect i exprim n (C2) valoarea negativ a sumei S. Pe de alt parte: ( S ) 2 = ( a + b) 2 = 2 n a + b (3.5) c) Cazul 3): a 0, b < 0 (cazul a < 0, b 0 este asemntor) (a )2 + (b)2 = a + 2 n b = 2 n + a b unde dac a - |b| 0, atunci 2 reprezint transport i se neglijeaz. Exist dou cazuri: 34

(3.6)

d)

(S )2 = (a + b )2 = (a b )2 = a be)a b S 7OVF-; 9=24-7=(-7)2 S2 =9+(-3)=9+(24-3)=24+6=OVF+ S2=6 La prima sumare apare o depire OVF ctre numere negative iar rezultatul 9 reprezint (-7) n (C2). A doua operaie genereaz de asemenea o depire dar n sens contrar, OVF+ ctre numere pozitive, lucru justificat prin interpretarea (-7)+(-3)=-10 2 operanzi, dac numrul depirilor OVF+ este egal cu cel al depirilor OVF-, (indiferent de succesiunea lor), atunci ele se compenseaz iar rezultatul este corect. n practic, un numrtor reversibil poate fi incrementat, respectiv decrementat, la apariia celor dou tipuri de depiri. Dac valoarea final a numrtorului este egal cu cea iniial, atunci rezultatul este corect. 3.1.3

Figura 3.2. Efectul depirilor aritmetice la operaii n complement fa de doi.

36

Justificarea afirmaiei se poate face observnd c n (C2) se lucreaz cu operaii modulo 2n. n acest caz numerele reprezentabile cu n+m bii (vezi relaia 3.1), se pot reprezenta pe un cerc ca n figura 2 n care numrul negativ minim -2n-l, reprezentat prin 2n-1 n (C2) este adiacent cu numrul maxim pozitiv 2n-1-2-m (2n-1-1, pentru numere ntregi). Depirile OVF- sau OVF+ reprezint traversarea acestei limite. Rezultatul fiecrei operaii pariale se poate deplasa pe cerc cu condiia ca n final s revin n domeniul iniial. Proprietatea menionat este util n unitile aritmetice (circuite digitale specializate pentru calcule aritmetice) prevzute cu sumare i acumulare a rezultatelor. n cazurile n care operanzii depesc ca lungime capacitatea unitii aritmetice de n bii, atunci ei se pot exprima prin mai multe cuvinte cu cte n bii juxtapuse iar operaiile de adunare i scdere se vor executa n mai muli pai efectund ntr-un pas o sum algebric pe primii n bii, n continuare pe urmtorii n bii (inndu-se seama i de transportul de la suma anterioar) .a.m.d. 3.2 NMULIREA NUMERELOR BINARE

n literatur sunt prezentai numeroi algoritmi de nmulire i mprire pentru numere reprezentate binar. Scopul acestor algoritmi const n reducerea complexitii circuitelor i a duratei de execuie. Spaiul nu permite descrierea tuturor metodelor n acest paragraf. Se vor prezenta numai cteva metode de principiu din care s rezulte tipurile de circuite digitale necesare implementrii operaiilor. 3.2.1 nmulirea Considernd dou numere ntregi, reprezentate n binar cu n bii, X = x n 1 ...x0 , Y = y n 1 ... y 0, xi , yi {0.1}

(3.9)

produsul lor P=XY va fi un numr cu 2n bii, dac X i Y se consider a fi fr semn i 2n-1 bii dac numerele X i Y se consider a fi cu semn n reprezentrile (MS), (C1) sau (C2). Acest fapt are loc pentru c domeniul numerelor cu semn cu n bii este |N|0, numere ntregi pentru care exist relaia cunoscut X=YQ+R, 0B, AB1 sau A1B sau AB, AB, AB, A