horatiuvlad.com computationala_cocan.pdf3 partea ÎntÂia bazele aritmetice ale sistemelor de calcul...

Moise COCAN

2008 – 2009

REPROGRAFIA UNIVERSITĂŢII “TRANSILVANIA” DIN BRAŞOV

user

Rectangle

3

PARTEA ÎNTÂIA

BAZELE ARITMETICE ALE SISTEMELOR

DE CALCUL

CAPITOLUL I

SISTEME DE NUMERAŢIE

Reprezentarea informaţiei într-un sistem de calcul se realizează cu ajutorul

sistemelor de numeraţie şi al codurilor.

1. Conceptul de sistem de numeraţie

Prin sistem de numeraţie înţelegem totalitatea regulilor de reprezentare a

numerelor cu ajutorul unor simboluri numite cifre.

Sistemele de numeraţie se clasifică în:

- poziţionale (de exemplu: sistemele binar, zecimal, hexazecimal),

- nepoziţionale (de exemplu: sistemul roman).

În sistemele de calcul se folosesc sistemele de numeraţie poziţionale pentru

reprezentarea informaţiei. De acestea ne vom ocupa în continuare.

Orice sistem de numeraţie poziţional este caracterizat prin numărul total de

simboluri (cifre) distincte ale sistemului, denumit baza sistemului de numeraţie,

număr ce va fi notat în continuare prin b.

Exemple de sisteme de numeraţie:

a) Sistemul binar, are baza 2; cifrele sunt 0, 1;

b) Sistemul octal, are baza 8; cifrele sunt 0, 1, 2, 3, 4, 5, 6, 7;

c) Sistemul zecimal, are baza 10; cifrele sunt 0, 1, 2, 3, 4, 5, 6, 7, 8, 9;

d) Sistemul hexazecimal, are baza16; cifrele sunt 0, 1, 2, 3, 4, 5, 6, 7, 9, A, B,

C, D, E, F.

Sistemele de calcul folosesc acele sisteme de numeraţie care prin caracteristicile

lor prezintă avantaje în ceea ce priveşte realizarea circuitelor şi calculelor (de exemplu:

sistemul binar, hexazecimal, octal).

1.1. Teorema sistemelor de numeraţie

Reprezentarea numerelor într-un sistem de numeraţie cu baza b, b N*, b>1 este

justificată teoretic prin teorema 1, numită teorema sistemelor de numeraţie, care la

rândul ei face apel la lemele 1 şi 2.

Lema 1. Fie b N* ,b >1. Oricare ar fi numărul natural N N

* există numerele

naturale n, a0, a1, ... , an, N0, N1, ... , Nn-1, astfel încât:

N = b N0 + a0 , 0 a0 < b

N0 = b N1 + a1 , 0 a1 < b

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

Nn-2 = b Nn-1 + a n-1 , 0 an-1 < b

4

Nn-1 = an , 0 < an 1, 0 ai 1.. Oricare ar fi numărul N > 0, există numerele

naturale n, a0, a1, ... , an unic determinate astfel încât:

N = an bn

+ an-1 bn-1

+ ... + a1b + a0 , unde 0 < an 0 şi secvenţele finite an an-1 ... a1a0 de numere naturale

ai 0 facem să-i corespundă secvenţa finită de numere

naturale

an an-1 ... a1a0 ,

unde

ai < b , 0 i n , an 0 şi N =

n

i

i

iba0

.

Prin urmare:

an an-1 ... a1a0 = an bn

+ an-1 bn-1

+ ... + a1b + a0 .

2. Când se impune să se menţioneze baza sistemului de numeraţie (de exemplu,

în cazul în care se lucrează cu mai multe baze), este obişnuit să se noteze an an-1 ...

a1a0(b).

Într-un sistem de numeraţie cu baza b, un număr raţional N format din parte

întreagă şi parte fracţionară se poate reprezenta într-una din următoarele trei forme:

N =

n

mi

i

i

m

m

n

n

n

n

mnnn

ba

babababababa

aaaaaaaa1

1

0

0

1

1

1

1

210121

,

unde b este baza sistemului, ai sunt cifre, n+1 este numărul de cifre al părţii întregi, m

este numărul de cifre ale părţii fracţionare, an este cifra cea mai semnificativă, a-m este

cifra cea mai puţin semnificativă;

0 ai b-1 , m i n , 0 < an b-1.

Dacă m = 0, numărul N este întreg.

Este evident faptul că cele trei forme sunt echivalente.

Nu ne propunem să intrăm în detalii pur teoretice; menţionăm însă faptul că

orice număr real xR se reprezintă în mod unic sub forma:

x = [x]+{x} , [x]Z , 0{x}<1,

unde [x] reprezintă partea întreagă a lui x, iar {x} partea fracţionară a lui x.

Sistemele de numeraţie, în funcţie de bază au o serie de proprietăţi care

constituie criteriile pentru selectarea lor în operaţiile de codificare, prelucrare sau

transmitere a informaţiei.

5

De exemplu, sistemul binar care posedă două cifre 0 şi 1, este cel mai potrivit

pentru a fi utilizat în sistemele de calcul care sunt construite în principal din elemente cu

două stări stabile, putându-se obţine o reprezentare fizică a informaţiei prin atribuirea

uneia dintre stările dispozitivului a cifrei 0 iar celeilalte a cifrei 1.

Prin conectarea mai multor elemente de acest tip se obţine un dispozitiv numit

registru. Registrul va putea deci conţine o succesiune de cifre binare (biţi), a cărei

lungime depinde de numărul elementelor conectate. Un exemplu de registru cu 8 biţi,

care conţine numărul (11001001)(2), este prezentat mai jos:

1 1 0 0 1 0 0 1

Observaţie: Pentru separarea părţii întregi de partea fracţionară vom utiliza punctul în locul

virgulei.

În legătură cu reprezentarea numerelor într-o bază se pun următoarele probleme:

1. Stabilirea raportului de mărime între două numere reprezentate în aceeaşi

bază.

2. Stabilirea unor reguli (algoritmi) de efectuare a sumei, produsului, etc. a două

numere reprezentate în aceeaşi bază.

3. Elaborarea unor algoritmi pentru reprezentarea unui număr într -o bază dată.

4. Conversia unui număr dintr-un sistem de numeraţie în altul (dintr-o bază în

alta).

1.3. Compararea numerelor reprezentate într-o bază

Teorema următoare furnizează un criteriu de stabilire a raportului de mărime

între două numere naturale reprezentate în aceeaşi bază.

Teorema 3. Fie a, cN, a = amam-1 a1a0(b) şi c = cncn-1 c1c0(b). Atunci a<c dacă

şi numai dacă m<n sau m = n şi ap<cp, unde p este cel mai mare i astfel încât

ai ci , deci p = max{i / ai ci }.

1.4. Algoritmi pentru calculul sumei şi produsului a două numere reprezentate în

aceeaşi bază

Ne propunem acum să formulăm un algoritm pentru adunarea a două numere

naturale reprezentate în baza b şi să schiţăm un algoritm pentru înmulţirea a două

numere naturale.

Fie a , c N , a = amam-1 a1a0(b) , c = cncn-1 c1c0(b) ; vrem să găsim cifrele

so,s1, ale numărului a + c în baza b.

Avem:

a = a0 + a1b + a2b2 + + amb

m

c = c0 + c1b + c2b2 + + cnb

n

Din a0 < b , c0 < b, rezultă a0 + c0 < 2b deci a0 + c0 = 1b + s0, 0 s0 < b,

1 = 0 sau 1 = 1 sau mai precis:

s0=a c daca a c b deci

a c b daca a c b deci

0 0 0 0 1

0 0 0 0 1

0

1

, ( )

, ( )

Rezultă că:

6

a + c = s0 +(a1 + c1 + 1)b + (a2 + c2)b2 +

Este evident faptul că:

(a1 + c1 + 1) < 2b

de unde

(a1 + c1 + 1) = 2b + s1 , 0 s1 0:

i = 0 ai-1+ci-1+i-1 <b

şi atunci

si-1 = ai-1 + ci-1 +i-1 -b.

Dacă m = n numărul a + c are:

1. m cifre , dacă am + cm + m n , atunci rămân adevărate cele mai de sus

luând cn+1 = = cm = 0.

Reprezentăm în pseudocod algoritmul de adunare a două numere naturale

reprezentate în baza b;

Pasul 1. Citeşte m, n; a0, a1,…,am; c0,c1,…,cn;

Pasul 2. Dacă m>n atunci cn+1 := cn+2 :=…:= cn := 0

altfel dacă m<n atunci am+1 := am+2 := … := an :=0;

Pasul 3. Pentru i := 0, max(m,n) execută

εi := 0;

Dacă ai + ci + εi< b atunci si := ai+ bi+ εi ; εi+1 := 0

altfel si := ai+ bi+ εi-b ; εi+1 := 1;

Pasul 4. Dacă εi= 0 atunci scrie s0, s1,…,si-1

altfel scrie s0, s1,…,si-1, 1.

Pasul 5. Stop.

Înmulţirea a două numere naturale în baza b se reduce în esenţă, la următoarele

tipuri de operaţii:

1. Înmulţirea unui număr natural a cu o putere bj

a bazei b;

2. Înmulţirea unui număr natural a cu o cifră a sistemului de numeraţie

(deci cu un număr natural j , 0 j <b);

3. Adunarea în baza b.

1. Fie a = amam-1 a1a0(b) = ambm+ am-1b

m-1+ +a1b+a0.

Atunci

a bj = amb

m+j + am-1b

m+j-1 + +a1b

1+j+a0b

j = amam-1 a1a0

orij

0...00 .

2. Dacă i şi j sunt două numere naturale mai mici decât b, atunci ij < b2, de unde,

folosind teorema împărţirii cu rest pentru numere naturale avem:

ij = bq(i,j) + r(i,j) , 0 r(i,j) < b , 0 q(i,j) <b ,

7

câtul q = q(i,j) şi restul r(i,j) împărţirii numărului ij prin b depinzând de i si j.

Fie

a = amam-1...a1a0(b) =

m

i

i

iba0

şi j o cifră a sistemului de numeraţie cu baza b , deci 0j<b. Atunci rezultă:

aj =

m

i

i

i jba0

=

m

i

i

ii bjarjabq0

,, = r a j bi

i

i

m

( , )

0

+ q a j bi

i

i

m

( , )

1

0

În sfârşit, dacă

c = cncn-1...c1c0(b) = c bj

j

j

n

0

atunci

ac = ac b ac bj

j

j

n

j

j

j

n

0 0

( ) .

1.5. Algoritmul sistemelor de numeraţie

Algoritmul de reprezentare a numerelor naturale N (date într-o anumită bază)

într-o baza b, cunoscut sub denumirea de algoritmul sistemelor de numeraţie este

reprezentat, în pseudocod, în continuare.

Pasul 1. Citeşte N, b;

Pasul 2. i := 0;

Pasul 3. Repetă ai := N mod b ; N := [N/b] ; i := i + 1 ;

până_când N = 0;

Pasul 4. Scrie a0, a1,…,ai-1;

Pasul 5. Stop.

Exemplu:

12345(10) = 11000000111001(2) .

1.6. Conversia numerelor dintr-o bază în alta

Existenţa şi utilizarea mai multor sisteme de numeraţie impune problema

conversiei dintr-un sistem în altul. Deoarece limbajul sistemelor de calcul este binar,

vom menţiona în special trecerea din baza 10 (sau o putere a lui 2) în baza 2 şi din baza

2 în baza 10 (sau o putere a lui 2).

Prezentăm în continuare două metode de conversie şi anume:

1.6.1. Metoda substituţiei

(i). Trecerea unui număr N din baza b în baza h, calculele făcându-se în baza

(destinaţie) h

Acest procedeu este utilizat la introducerea datelor numerice în sistemele de

calcul, datele primind astfel o reprezentare binară.

8

Considerăm numărul N în baza b. Pentru a obţine numărul N în baza h, atât baza

b cât şi cifrele ai se scriu în baza h şi se efectuează ridicările la putere, înmulţirile şi

adunările necesare, în baza h.

Exemplu:

1234(5) = ?(2) .

1234(5) = 153 + 25

2 + 35 + 4 =

= 1(101)3 + (10)(101)

2 + (11)(101) + 100 =

= 1111101 + 110010 + 1111 + 100 =

= 11000010(2);

1(5) = 1(2) ; 2(5) = 10(2) ; 3(5) = 11(2) ; 4(5) = 100(2) ; 5(5) = 101(2).

Caz particular. Dacă b = 2k (deci baza b este o putere a lui 2) atunci trecerea la

baza 2 se face mai simplu transformând fiecare cifră a numărului în baza 2 şi scriindu-le

în grupe de câte k cifre.

Exemplu.

726(8) = 111010110(2) ;

8 = 23 ; 7(8) = 111(2) ; 2(8) = 010(2) ; 6(8) = 110(2).

(ii). Trecerea unui număr din baza b în baza h, calculele făcându-se în baza (de

pornire) b

Acest procedeu este utilizat de sistemele de calcul pentru furnizarea rezultatelor,

deoarece baza veche este 2, iar baza nouă este cea obişnuită (în genera l 10).

Se scrie noua bază h în baza b şi se împarte numărul N la h scris în baza b,

conform algoritmului sistemelor de numeraţie. Acest algoritm evidenţiază faptul că

oricare ar fi două numere N şi h (h≠1, N>h) au loc relaţiile:

N = h* N0 + a0 , 0 ≤ a0 < h ;

N0 = h*N1 + a1 , 0 ≤ a1 < h ;

N1 = h*N2 + a2 , 0 ≤ a2 < h ;

…………………………………

Nm-2 = h*Nm-1 + am-1 , 0 ≤ am-1 < h ;

Nm-1 = h*Nm + am , 0 < am < h ,

unde a0 , a1 , …, am-1 , am sunt cifrele numărului N în baza h.

Exemplu: 5(2) = 101; 100110111(2) = 2221(5) .

Resturile în ordine inversă sunt 10, 10, 10, 1, care în baza 5 sunt respectiv 2, 2,

2, 1 deci am obţinut rezultatul menţionat iniţial.

Caz particular. Dacă h = bk , este posibilă o simplificare esenţială şi anume, fiecare

grup de câte k cifre ale numărului dat, de la marca zecimală spre stânga pentru partea

întreagă şi de la marca zecimală spre dreapta pentru partea fracţionară, se transformă în

baza h.

Exemple: a). 11110101111(2) = 3657(8) ;

b). 11110101111(2) = 7AF(16) ;

c). 11010.001010011(2) = 32.123(8) .

(iii). Trecerea unui număr din baza b în baza h prin intermediul unei baze

intermediare g

Metoda se reduce la cele două anterioare de la baza b se poate trece la baza g,

calculele făcându-se în noua bază (deci primul procedeu), iar de la baza g la baza h

calculele se execută în baza veche (al doilea procedeu).

De obicei baza intermediară g este 10.

9

Exemplu:

7635(8) = 2391(12)

7635(8) = 783 + 68

2 + 38

1 + 5 = 7512 + 664 + 24 + 5 =

= 3584 + 384 + 29 = 3997 (10) = 2391(12) .

Observaţie: Deoarece în sistemele de calcul nu se pot introduce decât numere cu un număr

finit de cifre (în special în partea fracţionară), numerele reale vor fi întotdeauna

aproximate prin numere raţionale.

1.6.2. Metoda împărţirii / înmulţirii bazei.

Prin această metodă se realizează conversia unui număr N din baza b în baza h

utilizând aritmetica în baza h.

Conversia părţii întregi a numărului se obţine prin împărţiri succesive la baza h,

iar conversia părţii fracţionare prin înmulţiri succesive în baza h.

Considerăm numărul N din baza b care se poate scrie:

N(b) = [N](b) + {N}(b).

Dar

[N](b) = anhn + ... + a1h

1 + a0h

0 ,

cifrele ai (i = 0,1,…,n) fiind deocamdată necunoscute, dar se pot determina prin

împărţirea succesivă a lui [N](b) la h conform procedeului următor:

000

1

1)(...

][a

h

ahaha

h

Nn

n

b

110

2

2)(1...

][a

h

ahaha

h

Nn

nb

......................................................................………….

kk

k

kn

n

bka

h

ahaha

h

N

0

1

1)(...

][.

Procesul de împărţire se încheie în momentul în care [N](b) < h . Se obţine în

final:

[Nn](b) = an , 0 < an < h .

Observaţie: Cifra cea mai puţin mai semnificativă a numărului [N](h) este a0, iar cifra cea mai

semnificativă a numărului este an .

Partea fracţionara a numărului N(b) se va scrie în baza h astfel:

....}{ 2

2

1

1)(

m

mb hahahaN

Cifrele a-i (i = 1,2,…,m) se pot determina prin înmulţiri succesive ale părţii

fracţionare cu baza h conform următorului procedeu:

1

}{

11

21)(

)(1

...*}{

ahahaahN

bN

m

mb

2

}{

21

32)(1

)(2

...*}{

ahahaahN

bN

m

mb

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

10

k

N

km

mkkbk ahahaahN

bk

)(}{

1

1)(1 ...*}{

Cifra a-1 reprezintă cifra cea mai semnificativă a numărului {N}(h), iar cifra a-m

reprezintă cifra cea mai puţin semnificativă.

1.6.3. Exemple

I. Să se treacă numărul 34562(7)

A) în baza 5;

1) făcând calculele în baza 5 ;

2) făcând calculele în baza 7;



B) în baza 8;





A. 1. 3(7) = 3(5), 4(7) = 4(5), 5(7) = 10(5), 6(7) = 11(5), 2(7) = 2(5), 7 = 12(5);

34562(7) = 3(12)4 + 4(12)

3 + 10(12)

2 + 1112 + 2 =

= 212303 + 20442 + 1440 + 132 + 2 = 240424 (5)

2. 34562(7) = 240424(5)

34562(7) = 5(7)5111(7)+4(7)

5111(7) = 5(7)1014(7)+2(7)

1014(7) = 5(7)130(7)+4(7)

130(7) = 5(7)20(7)+0(7)

20(7) = 5(7)2(7)+4(7)

2(7) = 5(7)0(7)+2(7)

3. 34562(7) = 374 + 47

3 + 57

2 + 67 + 2 =

= 32401 + 4343 + 549 + 67 + 2 =

= 7203 + 1372 + 245 + 42 + 2 = 8864(10)

8864(10) = 51772(10)+4(10)

1772(10)= 5354(10)+2(10)

354(10) = 570(10)+4(10)

70(10) = 514(10)+0(10)

14(10) = 52(10)+4(10)

2(10) = 50(10)+2(10)

4. 34562(7) = 11(111)4 + 100(111)

3 +101(111)

2 + 110111 + 10 =

= 1110000100011 + 10101011100 + 11110101 + 101010 + 10 =

= 10001010100000(2) 34562(7) = 240424(5)

B. 1. 3(7) = 3(8), 4(7) = 4(8), 5(7) = 5(8), 6(7) = 6(8), 2(7) = 2(8), 10(7) = 7(8)

34562(7) = 374 + 47

3 + 57

2 + 67 + 2 =

= 34541 + 4527 + 561 + 67 + 2 =

= 16043 + 2534 + 365 + 52 + 2 = 21240 (8)

11

2. 34562(7)= 21240(8)

34562(7)=11(7) 3142(7)+0(7)

3142(7) =11(7) 255(7)+4(7)

255(7) =11(7) 23(7)+2(7)

23(7) =11(7) 2(7)+1(7)

2(7) =11(7) 0(7)+2(7)

3. 34562(7) = 3 74 + 4 7

3 + 5 7

2 + 6 7 + 2 =

= 3 2401 + 4 343 + 5 49 + 6 7 + 2 =

= 7203 + 1372 + 245 + 42 + 2 = 8864 (10)

4. 34562(7) = 10001010100000(2)

II. Să se transforme numărul 234.128 (10) în baza 8.

234 = 298 + 2 2

29 = 38 + 5 5

3 = 08 + 3 3

0.128 8 = 1.024 1

0.024 8 = 0.192 0

0.192 8 = 1.536 1

0.193

Pentru a obţine o conversie mai exactă, procesul de înmulţire mai poate continua.

Dar, cu trei zecimale exacte, putem scrie că 234.128 (10) = 352.101(8).

III. Să se transforme numărul 175.1285 (10) în baza 4.

175 = 434 + 3 3

43 = 104 + 3 3

10 = 24 + 2 2

2 = 04 + 2 2

0.12854 = 0.5140 0

0.51404 = 2.0560 2

0.05604 = 0.2240 0

0.22404 = 0.8960 0

0.89604 = 3.5840 3

0.58404 = 2.3360 2

Pentru a obţine o conversie mai exactă, procesul de înmulţire mai poate

continua. Cu şase zecimale exacte putem scrie că 175.1285 (10) = 2233.020032(4).

1.7. Rezumat

Se numeşte sistem de numeraţie totalitatea regulilor de reprezentare a numerelor

cu ajutorul unor simboluri distincte numite cifre. Pentru reprezentarea informaţiei în

memoria sistemelor de calcul se folosesc sistemele de numeraţie poziţionale (binar,

zecimal, hexazecimal, etc.), adică sistemele de numeraţie în care valoarea oricărei cifre

în cadrul oricărei reprezentări depinde esenţial de poziţia pe care o ocupă în cadrul

reprezentării

Orice sistem de numeraţie poziţional este caracterizat prin numărul total de

simboluri (cifre) distincte ale sistemului, denumit baza sistemului de numeraţie, număr

ce va fi notat în continuare prin b.

Exemple de sisteme de numeraţie: Sistemul binar, are baza 2; cifrele sunt 0, 1;

Sistemul octal, are baza 8; cifrele sunt 0, 1, 2, 3, 4, 5, 6, 7; Sistemul zecimal, are baza

10; cifrele sunt 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; Sistemul hexazecimal, are baza16; cifrele sunt

0, 1, 2, 3, 4, 5, 6, 7, 9, A, B, C, D, E, F.

Sistemul binar este cel mai potrivit pentru a fi utilizat în sistemele de calcul care

sunt construite în principal din elemente cu două stări stabile, putându-se obţine o

reprezentare fizică a informaţiei prin atribuirea uneia dintre stările dispozitivului a cifrei

0 iar celeilalte a cifrei 1. Prin conectarea mai multor elemente de acest tip se obţine un

12

dispozitiv numit registru. Registrul conţine aşadar o succesiune de cifre binare (biţi), a

cărei lungime depinde de numărul elementelor conectate.

Teorema sistemelor de numeraţie demonstrează faptul că oricare ar fi numărul N

> 0, şi baza b N * , b >1, există numerele naturale n, a0, a1, ... , an unic determinate

astfel încât N să admită reprezentarea:

N = an bn

+ an-1 bn-1

+ ... + a1b + a0 ,

unde 0 < an < b ,0 ai < b pentru i = 0 , 1 , ... , n -1.

În legătură cu reprezentarea numerelor într-o bază se pun următoarele patru

probleme:

1). Stabilirea raportului de mărime între două numere reprezentate în aceeaşi

bază. În acest context se dă un rezultat care decide care dintre două numere date este

mai mar

2). Stabilirea unor algoritmi pentru calculul sumei şi produsului a două numere

reprezentate în aceeaşi bază. Algoritmul pentru calculul sumei se prezintă integral, iar

pentru algoritmul de calcul al produsului se prezintă cele trei proceduri componente ale

sale.

3). Elaborarea algoritmului sistemelor de numeraţie (pentru reprezentarea unui

număr într-o bază dată).

4). Conversia unui număr dintr-un sistem de numeraţie în altul.. Se detaliază

principalele metode de conversie (metoda substituţiei şi metoda împărţirii/înmulţirii

bazei)

CAPITOLUL 2

ELEMENTE DE TEORIA CODIFICĂRII

2.1. Cod. Codificare. Limbaje de codificare

Necesitatea realizării unei comunicări cât mai simple între om şi sistemele de

calcul a condus la utilizarea codurilor (sau, cu alte cuvinte, a limb ajelor de codificare).

Conversia informaţiei numerice din sistemul zecimal (sistem de numeraţie

utilizat frecvent de om) este un exemplu de codificare.

În general, definim codificarea elementelor mulţimii (sistemului informaţional)

S1 prin elementele mulţimii (sistemului informaţional) S2, ca fiind orice modalitate de a

reprezenta distinct elementele mulţimii S1 prin secvenţe de elemente din S2.

Orice aplicaţie injectivă cod : S1 → S2 , unde S2 reprezintă mulţimea secvenţelor

de elemente din S2 se numeşte cod şi defineşte o codificare a lui S1 prin S2.

Menţionăm două moduri de realizare a codificării şi anume:

- prin metodă directă;

- prin limbaj de codificare.

Metoda directă, fără mari posibilităţi de utilizare, constă în evidenţierea unui

mecanism care să posede atâtea stări distincte câte elemente are sistemul informaţional

(de codificat) S1.

13

Exemple:

i. Un bec având două stări stabile distincte (aprins şi stins) poate realiza

codificarea unui sistem informaţional cu două stări distincte.

ii. Un zar cu 6 stări stabile distincte poate realiza codificarea unui sistem

informaţional cu 6 stări distincte.

Inconvenientul metodei directe constă în faptul că este foarte greu sau chiar

imposibil să se realizeze un mecanism cu un număr suficient de mare de stări stabile

distincte.

Această insuficienţă a metodei directe o elimină folosirea limbajelor de

codificare.

Un limbaj de codificare L este definit printr-un triplet:

L ≡ {alfabet, structură morfologică, atribuire semantică}.

Alfabetul este o mulţime cel mult numărabilă şi nevidă de elemente distincte

numite litere, caractere sau simboluri.

Exemple:

i. A2 = {0,1};

ii. A10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

iii. An = {A, B, C, …, X, Y, Z}.

Pe un alfabet se introduce o relaţie de ordine. Este uşor de constatat faptul că pe

alfabetul binar (A2), alfabetul zecimal (A10) şi alfabetul natural (An) relaţia de ordine

este “ ≤ ”.

Numărul de caractere ale unui alfabet se numeşte baza limbajului de codificare

peste alfabetul respectiv.

Un limbaj (de codificare) este format din cuvinte.

Definiţia 1. Un cuvânt peste alfabetul A este o aplicaţie:

c : {1, 2, …, n}→ A.

Numărul n reprezintă lungimea cuvântului c; se va nota prin l(c).

Vom nota c = c(1)c(2)…c(n), prin urmare un cuvânt este o succesiune finită de

simboluri, c(j) fiind al j-lea simbol al cuvântului c; cuvintele de lungime 1 se identifică

cu caracterele.

Notăm: A+ - mulţimea cuvintelor peste alfabetul A,

A* = A

+ { λ },

unde

: A

este cuvântul nul, a cărui lungime, prin convenţie, este zero.

Structura morfologică (morfologia unui limbaj) defineşte regulile de

compunere a cuvintelor limbajului respectiv sau, cu alte cuvinte, operaţiile ce se pot

executa asupra cuvintelor limbajului.

În definirea unui limbaj de codificare există două operaţii de bază şi anume:

- concatenarea (juxtapunerea);

- substituţia.

Definiţia 2. Dacă c1, c2 A*, se numeşte concatenarea (juxtapunerea) cuvintelor c1,

c2 cuvântul c = c1c2 definit astfel:

c1c2 : {1, 2,…, l(c1) + l(c2)} A* ,

14

.)()(1)(,))((

)(1,)()(

21112

11

21

clcljcldacăcljc

cljdacăjcjcc

Definiţia 3. Operaţia de substituţie este aplicaţia:

s : A* A

* A

*

care asociază perechii de cuvinte (c1, c2) A* A

* cuvântul c3 = s(c1, c2) A

* obţinut

prin substituţia unui subcuvânt al lui c2 prin c1.

Exemplu:

c1 = αβαβ , c2 = αβγαβ , c3 = αβαβαβαβ = (αβ)4 ;

cuvântul c3 s-a obţinut prin substituţia γ c1 .

Definiţia 4. Numărul de caractere ale cuvintelor unui limbaj defineşte formatul

limbajului.

Deosebim următoarele tipuri de limbaje:

- cu format definit;

- cu format liber (variat).

Limbajul cu format liber nu are restricţii de format, în timp ce limbajul cu format

definit are proprietatea că l(c) = f (constant), () c L A*.

Definiţia 5. Atribuirea semantică este operaţia care realizează corespondenţa

bijectivă între mulţimea elementelor sistemului informaţional şi o submulţime a

mulţimii elementelor limbajului (eventual întreaga mulţime a elementelor

limbajului).

2.2. Limbaje peste un anumit alfabet. Operaţii cu limbaje

Observaţie:

Mulţimea A+ înzestrată cu operaţia de concatenare “ ” : A

+ A+

A+, definită prin (c1,c2) c1c2 este un semigrup, ce poartă numele de

semigrup liber peste alfabetul A; mulţimea A joacă rol de sistem de

generatori pentru semigrupul (A+, ), identificând elementele sale cu cuvintele

de lungime 1, deoarece orice cuvânt cA+ se exprimă în mod unic ca

juxtapunerea a l(c) cuvinte de lungime 1:

c = c1c2....cl(c) , cj = c(j) , 1 j l(c).

Definiţia 6. Monoidul (A*,,) în care operaţia “” coincide pe A

+ cu operaţia de

concatenare (juxtapunere) şi în plus:

c = c = c , c A*,

se numeşte monoid liber peste alfabetul A.

Definiţia 7. Un limbaj pe alfabetul A este o parte L a monoidului liber A*, deci L

A*, sau altfel spus, L (A

*).

Definiţia 8. Puterea lexicografică a unui limbaj este definită prin numărul cuvintelor

distincte ce se pot forma un acel limbaj, deci card (L).

Într-un limbaj L cu baza b şi formatul f avem:

card (L) = bf.

Definiţia 9. Fie L1, L2 (A*). Se numeşte reuniune a limbajelor L1 şi L2 limbajul

notat L1 L2 şi definit astfel:

L1 L2 = {c | c L1, sau c L2}.

15

Definiţia 10. Fie L1, L2 (A*). Se numeşte produs al limbajelor L1 şi L2 limbajul

notat L1L2 şi definit astfel:

L1L2 = {c | c = c1c2, c1 L1, c2 L2}.

În mod echivalent, limbajul L1L2 se mai numeşte concatenarea limbajelor L1 şi

L2.

Prin definiţie avem:

L = L = , L P (A*),

deci limbajul vid, , este element nul faţă de produs.

Limbajul {}, constituit numai din cuvântul nul, este element neutru faţă de

produs, deoarece:

{}L = L{} = L, L P (A*).

Observaţie:

Orice aplicaţie injectivă : S1 L P (A*) este un cod, ce realizează

codificarea elementelor sistemului informaţional S1 prin cuvinte (din L) peste

alfabetul A*. Limbajul L este numit limbaj de codificare.

Uneori, prin abuz de limbaj, limbajul de codificare se numeşte, mai scurt, cod.

Definiţia 11. Puterea a n-a a unui limbaj L se defineşte în mod recurent astfel:

L0 = {λ};

L1 = L;

Ln+1

= LnL, () nN, n 1.

Observaţie:

Produsul este distributiv faţă de reuniune adică avem:

a. L1(L2 L3) = L1L2 L1L3 ,

b. (L1 L2)L3 = L1L3 L2L3 ,

oricare ar fi L1, L2, L3 P(A*).

Definiţia 12. Închiderea prin produs sau iteratul limbajului L este limbajul:

L* = {L

n / n 0}.

Închiderea restrânsă a limbajului L este limbajul:

L+ = {L

n / n 1}.

2.3. Limbaje generate de gramatici

Un interes deosebit pentru informatica teoretică îl prezintă acele limbaje pentru

care există un mod de definire finitar, adică un mod de definire ce poate fi în întregime

precizat printr-o mulţime finită de cuvinte într-un limbaj oarecare.

Menţionăm două tipuri de definire finitară a limbajelor şi anume: procedee care

plecând de la un cuvânt oarecare răspund dacă cuvântul respectiv aparţine sau nu

limbajului (procedee analitice utilizând conceptul de automat) şi procedee care

generează cuvintele unui limbaj (procedee generative utilizând conceptul de

gramatică). În cele ce urmează vom trata succint procedeele generative.

Definiţia 13. O gramatică generativă (sau, mai scurt, gramatică) este un

4 - uplu G = (AN, AT, x0, F), unde AN este alfabetul simbolilor neterminali,

AT este alfabetul simbolilor terminali, x0 AN este simbolul iniţial, iar F

16

este o mulţime finită de perechi de cuvinte din (AN AT)*, F = {(uj, vj) / 1 ≤ j

≤ m}, astfel încât orice cuvânt uj conţine cel puţin un simbol neterminal.

Este evident că:

F AAA TN

*)( ** )()( TNTNN AAAA .

Vom numi perechile (uj, uj) reguli şi dacă (ui, vj)F vom nota aceasta cu

ujvj .

Definiţia 14. Cuvântul c1 generează direct cuvântul c2 în gramatica G dacă există

regula uj vj în F astfel încât c1 = p1ujs1, c2 = p1vjs1. Vom nota aceasta cu

c1 c2.

Definiţia 15. O derivare în gramatica G este un şir de cuvinte {c0, c1,…,cm} astfel încât

cj cj+1, 0 ≤ j ≤ m. Numărul m este lungimea derivării. În cazul în care {c0,

c1,…,cm} este o derivare vom mai nota aceasta prin c0 c1 … cm .

Definiţia 16. O formă propoziţională în gramatica G = (AN, AT, x0, F) este un cuvânt

c (AN AT)* pentru care există o derivare x0 c în gramatica G. Vom nota

cu FP(G) mulţimea formelor propoziţionale ale lui G.

Limbajul generat de gramatica G =(AN, AT, x0, F) este mulţimea

L(G) = FP(G) AT*, deci mulţimea L(G) = {c / c AT

*, x0 c}.

Exemple:

i. G = ({x0}, {i1, i2}, x0, {x0 i1i2, x0 i1x0i2});

L(G) = { nn ii 21 / n = 1,2,…}.

ii. Gp = ({x0}, {v,1, ,,}, x0, {x0x01, x0v1, x0x0x0, x0x0x0,

x0x0});

L(Gp) mulţimea formulelor bine construite ale calculului propoziţional.

iii. Gf = ({x0}, {i1,…,in}, x0, {x0c1,…,x0cn}), cjAT*, j= n,1 ;

L(Gf)={c1,c2,…,cn}.

iv. G = ({, , , , , , x1, x2}, {0,…, 9, A,…, Z, +, *, , (,)}, , F),

F = {

x1,…, x1, x1x1,…, x1x1, x10x1,…, x19x1, x10x2,…, 9x2,

x20x2,…, x29x2, x2};

L(G) = {< expresiile aritmetice construite folosind identificatori, întregi,

operatorii +, *, , şi parantezele ( si ) >}.

Gid = ({ x1}, {0,…, 9, A,…, Z}, , {x1,…, x1, x1x1,…, x1x1,

x10x1,…, x19x1, x1});

L(Gid) = { identificator }.

Gnum = ({, x2}, {0,…, 9}, , {0x2, …, 9x2, x20x2,…, x29x2, x2});

L(Gnum) = { constantă }.

În funcţie de forma regulilor unei gramatici, Chomsky a introdus (1959) trei

tipuri de gramatici şi în funcţie de aceasta trei tipuri de limbaje, care ocupă o poziţie

centrală în teoria limbajelor.

Definiţia 17. a. O gramatică G = (AN, AT, x0. F) se numeşte dependentă de

context (sensibilă la context) dacă fiecare regulă u v satisface

condiţia l(u) ≤ l(v).

b. O gramatică G = (AN, AT, x0. F) se numeşte independentă de

context (insensibilă la context) dacă fiecare regulă u v satisface

condiţia l(u) = 1, iar v ≠ λ.

17

c. O gramatică G = (AN, AT, x0. F) se numeşte regulată dacă pentru

orice (u v) F au loc l(u) = 1 şi v AT* AT

*AN, v ≠ λ.

Gramatica dependentă de context se mai numeşte gramatică de tipul 1,

gramatica independentă de context se mai numeşte gramatică de tipul 2, iar gramatica

regulată se mai numeşte gramatică de tipul 3.

Gramatica pentru care nu s-a impus nici una din restricţiile din definiţia

precedentă se numeşte gramatică de tipul 0 (zero).

Definiţia 18. Un limbaj dependent de context (de tipul 1) este un limbaj generat de o

gramatică dependentă de context. Un limbaj independent de context (de tipul 2) este

un limbaj generat de o gramatică independentă de context. Un limbaj regulat (de tipul

3) este un limbaj generat de o gramatică regulată.

Observaţie:

Orice gramatică de tipul 3 este de tipul 2, orice gramatică de tipul 2 este de

tipul 1, iar orice gramatică de tipul 1 este de tipul 0. Aceste relaţii de

incluziune sunt adevărate şi pentru familiile de limbaje de tipul 3, 2, 1. 0, deci

L3 L2 L1 L0,

unde am notat prin Li familia limbajelor de tipul i, i = 0, 1, 2, 3 . Teorema 1. Fiecare din familiile Li (i = 0, 1, 2, 3) conţine toate limbajele finite.

Teorema 2. Fiecare din familiile Li (i = 0, 1, 2, 3) este închisă faţă de operaţia de

reuniune.

Teorema 3. Familiile L1, L2, L3 sunt închise faţă de produs.

2.5. Exemple reprezentative de codificări

1. Considerăm alfabetul A = {i1,i2,....,in}, card(A)= n > 1 cu ordinea i ij j1 2 j1

< j2 şi alfabetul B = {1, 2,.., n} cu ordinea naturală.

Aplicaţia : A* B

* definită prin:

,...)...(

,0)(

12121jjjjiii kkjjj k

cu semnificaţia evidentă: 1

21121 .......

k

kkk njnjjjjjj ,

este un cod ce realizează codificarea cuvintelor c A* prin cuvinte din B

*, sau

astfel spus, prin numere naturale.

2. Aplicaţia : {0,1,2,..,b-1}* {0,1,2,..,h-1}

*, b, h N

*, b > 1 , h > 1 definită

prin:

(N(b)) = N(h), N(b) N

este un cod.

3. Limbajul de codificare peste alfabetul A = {0,1} cu ordinea naturală 0 < 1, se

numeşte limbaj de codificare binar şi ocupă un loc central în teoria codificării. Un

asemenea limbaj are forma L ({0,1}*).

18

Un cod definit de o aplicaţie injectivă : S1 L ({0,1}*), capabil să

codifice elementele sistemului informaţional S1, trebuie să satisfacă cerinţa ca puterea

lexicografică a limbajului L să fie mai mare sau egală cu card(S1).

Aplicaţia de mai sus în cazul în care limbajul L are formatul definit şi anume

f = 4, realizează codificarea unui sistem informaţional cu 16 stări distincte; este aşa

numitul cod DCB (Decimal Coded Binary), (N(10)) = N(2) definit astfel:

0(10) 0000(2)

1(10) 0001(2)

2(10) 0010(2)

3(10) 0011(2)

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

15(10) 1111(2)

4. Codul Gray (binar reflectat) este tot o aplicaţie injectivă (N(10)) {0,1}*,

definită cu ajutorul limbajului de codificare binar de format definit (f = 4), deci capabilă

să codifice un sistem informaţional cu 16 stări distincte.

Corespondenţa pe care o realizează codul Gray:

N N( ) ( )10 2

este prezentată în detaliu în continuare:

0(10) 0000(2)

1(10) 0001(2)

2(10) 0011(2)

3(10) 0010(2)

4(10) 0110(2)

5(10) 0111(2)

6(10) 0101(2)

7(10) 0100(2)

8(10) 1100(2)

9(10) 1101(2)

10(10) 1111(2)

11(10) 1110(2)

12(10) 1010(2)

13(10) 1011(2)

14(10) 1001(2)

15(10) 1000(2)

Remarcăm faptul că două combinaţii de cod consecutive sunt adiacente (adică

diferă printr-o singură poziţie a combinaţiilor de cod, aceeaşi în ambele combinaţii); de

asemenea prima combinaţie de cod este adiacentă cu ultima ceea ce face ca succesiunea

combinaţiilor de cod să fie circulară.

19

5. Codul EBCDIC (Extended Binary Coded Decimal Interchange Code) este

realizat de limbajul de codificare binar de format definit (f = 8), deci permite

codificarea elementelor unui sistem informaţional cu 28 elemente si implicit este capabil

sa codifice oricare din cele 64 caractere ale limbajului natural:

A 11000001

B 11000010

……………………

1 11110001

2 11110010

……………………

9 11111001 .

2.6. Coduri implicate în reprezentarea informaţiei în memoria sistemelor de

calcul

Codurile sunt aplicaţii cod : (-1,1) {-0} R (în cazul codului direct şi al

codului invers ) şi aplicaţie cod : (-1,1) R (în cazul codului complementar). Simbolul

-0 este introdus pentru ca aplicaţiile respective să fie uniforme. Sunt utilizate codurile

direct, complementar şi invers.

2.6.1. Codul direct

Definiţia 19. Codul direct este aplicaţia, notată [ ]dir, şi definită astfel:

[ ]dir : (-1,1) {-0} R,

unde:

[a]dir =

0,a-1-b

1.>bN,,0,1

0,

adacă

badacăb

adacăa

Observaţii:

i. Codul direct realizează corespondenţele:

)1,0(][

)1,0( dir

),1(][

)0,1( bbdir .

ii. Aplicaţia [ ]dir este injectivă. Astfel, dat fiind [a]dir , există un singur a, al

cărui cod direct este [a]dir .

Teorema 5. Dacă aR , bN , b>1 atunci:

nbn

nbn

diraaaadacăaaab

aaaadacăaaa[a]

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

....0,...0.=

21)(21

21)(21.

Observaţie: Codul direct poate fi extins pentru numere naturale şi mai departe

pentru numere raţionale. Codul direct al unui număr N este (în cazul b = 2 şi

lungimea registrului n + 1) dat de relaţia:

[N]dir= a an

n

i

i

i

n

2 20

1

,

20

unde an reprezintă bitul de semn şi ia valoarea 0 dacă N 0 şi valoarea 1 dacă N

0, iar ai ( 0 i n-1) sunt biţii numărului N, deci are reprezentarea:

S an1 an2 ...... a1 a0

unde:

S =

0,1

0,0

Ndacă

Ndacă

Codul direct al unui număr raţional N este:

[N]dir= a an

n

i

i

i m

n

2 21

unde elementele care intervin au aceeaşi semnificaţie ca mai sus.

Exemple: Dacă lungimea registrului este n = 5, atunci:

a. [13]dir = 01101;

b. [-13]dir = 11101;

c. [-0,6875]dir = 11011;

0.68752 = 1.375 a –1 = 1,

0.3752 = 0.75 a –2 = 0,

0.752 = 1.5 a –3 = 1,

0.52 = 1.0 a –4 = 1.

Acest mod de reprezentare prezintă avantajul de a fi foarte asemănător scrierii

obişnuite, dar are dezavantaje din punctul de vedere al realizării calculelor; realizarea

unei operaţii de adunare sau scădere a două numere nu depinde numai de funcţia de

executat ci şi de semnul numerelor respective.

2.6.2 Codul complementar

Definiţia 20. Codul complementar este aplicaţia notată [ ]compl, definită astfel:

[ ]compl : (-1,1) R

unde:

[a]compl =

01daca,

10daca,

aab

aa , bN

* , b >1

Observaţii.

i. Codul complementar realizează corespondenţele următoare:

)1,0[][

)1,0[ compl

),1(][

)0,1( bbcompl

ii. Aplicaţia [ ]compl este injectivă.

Teorema 6. Dacă aR , bN *

, b>1, atunci au loc relaţiile:

0,},...,1{,....0dacă,...).1(

....0dacă,....0][

21)(21

21)(21

inbn

nbn

compl aniaaaabbbb

aaaaaaaa

21

unde:

0.b1b2…bn = 1 – 0.a1a2…an .

Observaţie:

Codul complementar al unui număr algebric N este, în cazul b = 2, dat de

relaţia:

[N]compl =

0,2221

0,220

1

1

Ndacăa

Ndacăa

min

mi

i

n

n

mi

i

i

n

,

unde ii aa 1 reprezintă complementul faţă de 1 al cifrei ai (-m i n-1).

Exemple: În cazul registrului de lungime de lungime n = 5 avem:

a. [13]compl = 01101;

b. [-13]compl = 10011,

deoarece –13= -1101(2); se trece la cod complementar 1101 0011, deci se

obţine rezultatul menţionat.

2.6.3. Codul invers

Definiţia 21. Codul invers este aplicaţia notată [ ]inv , definită astfel:

[ ]inv : [-1+b-n

, 1){-0}R

unde

[a]inv =

01,

0,

10,

abdacăabb

adacăbb

adacăa

nn

n .

b N, b>1 ,nN.

Observaţii.

i. Codul invers realizează corespondenţele:

)1,0(][

)1,0( inv

),1[][

)0,1[ nn bbbinvb

i. Aplicaţia [ ]inv este injectivă.

Teorema 7. Dacă aR ,bN , b>1, atunci au loc relaţiile:

[a]inv=

nbn

nbn

aaaadacăaaa

aaaadacăaaa

....0....0

....0....0

21)(21

21)(21

unde c =b-1-c , c fiind o cifră în baza b.

Exemple: În cazul registrului de lungime n = 5 avem:

22

a. [13]inv = 01101;

b. [-13]inv = 10010,

deoarece –13= -1101(2) ; trecem numărul în cod invers 11010010, deci

[-13]inv = 10010.

Observaţie: Cele trei coduri coincid în cazul numerelor pozitive şi diferă în cazul numerelor

negative.

Reformulând relaţiile care exprimă codurile pentru cazul în care virgula se

consideră plasată după prima poziţie binară a numărului, numărul negativ N poate fi

scris sub forma N = a0 20+N

*, unde a0 reprezintă cifra semn, iar N

* are forma:

N*

=

inverscoduluicazulîna

arcomplementcoduluicazulîna

directcoduluicazulîna

n

i

i

i

nn

i

i

i

n

i

i

i

1

1

1

2

,22

,2

unde ai reprezintă cifrele numărului, n-numărul de cifre la dreapta mărcii zecimale,

ii aa 1 .

23

2.7. Rezumat

Necesitatea realizării unei comunicări cât mai simple între om şi sistemele de

calcul a impus introducerea conceptelor de cod, codificare şi limbaje de codificare.

Conversia informaţiei numerice din sistemul zecimal (sistem de numeraţie

utilizat frecvent de om) într-un alt sistem de numeraţie este un exemplu de codificare.

În general, definim codificarea elementelor mulţimii sistemului informaţional S1

prin elementele mulţimii sistemului informaţional S2, ca fiind orice modalitate de a

reprezenta distinct elementele mulţimii S1 prin secvenţe de elemente din S2.

Se menţionează două modalităţi de realizare a codificării şi anume: metoda

directă şi metoda bazată pe conceptul de limbaj de codificare.

Un limbaj de codificare L este definit printr-un tripletul

L ≡ {alfabet, structură morfologică, atribuire semantică}.

Alfabetul este o mulţime cel mult numărabilă şi nevidă de elemente distincte

numite litere, caractere sau simboluri, înzestrată cu o relaţie de ordine. Se exemplifică

alfabetele binar A2 = {0,1}, alfabetul zecimal A10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, alfabetul

latin al literelor majuscule An = {A, B, C, …, X, Y, Z}, cu ordinea naturală.

Structura morfologică defineşte regulile de compunere a cuvintelor limbajului

respectiv sau, cu alte cuvinte, operaţiile ce se pot executa asupra cuvintelor limbajului

(concatenarea sau juxtapunerea şi substituţia).

Atribuirea semantică este operaţia care realizează corespondenţa bijectivă între

mulţimea elementelor sistemului informaţional şi o submulţime a mulţimii elementelor

limbajului (eventual întreaga mulţime a elementelor limbajului).

Se defineşte semigrupul liber (A+, ) peste alfabetul A, monoidul liber (A

*,,)

peste alfabetul A, conceptul de limbaj pe alfabetul A care este o parte L a monoidului

liber A*, deci L A

*, sau altfel spus, L (A

* ) şi puterea lexicografică a unui limbaj

reprezentată prin numărul cuvintelor distincte ce se pot forma un acel limbaj, deci card

(L).

Se definesc operaţiile de bază cu limbaje (reuniune, produs, puterea unui limbaj,

închiderea prin produs a unui limbaj şi închiderea restrânsă).

Se introduce conceptul de gramatică, limbaj generat de o gramatică, se prezintă

clasificarea, după Chomsky, a gramaticilor (limbajelor) şi se demonstrează principalele

proprietăţi de închidere ale diverselor familii de limbaje (faţă de reuniune şi produs).

Se structurează mulţimea (A*) a limbajelor peste alfabetul finit A ca spaţiu

metric complet. Se prezintă şase exemple reprezentative de codificări (codificarea

mulţimii cuvintelor unui limbaj peste un alfabet finit prin numere naturale, conversia

: {0,1,2,..,b-1}* {0,1,2,..,h-1}

*, b, h N

*, b > 1 , h > 1 definită prin (N(b)) = N(h),

N(b) N, codul DCB (Decimal Coded Binary), codul Gray (binar reflectat), codul

EBCDIC (Extended Binary Coded Decimal Interchange Code), numărul convenţional

al unui implicant al unei funcţii booleene).

Se studiază codurile implicate în reprezentarea informaţiei în memoria

sistemelor de calcul (codul direct, codul complementar şi codul invers) ca fiind

aplicaţii cod : (-1,1) {-0} R (în cazul codului direct şi al codului invers ) şi

aplicaţie cod : (-1,1) R (în cazul codului complementar).

Se examinează operaţiile aritmetice cu numere reprezentate în coduri (suma

codurilor complementare şi a codurilor inverse), se demonstrează rezultatul fundamental

că suma codurilor complementare (inverse) este egală cu codul complementar (invers)

24

al sumei, se prezintă algoritmi pentru adunare şi scădere în cod direct, complementar şi

invers, înmulţirea în cod complementar (metoda Roberston, metoda Booth).

CAPITOLUL 3

REPREZENTAREA INFORMAŢIEI ÎN

MEMORIA SISTEMELOR DE CALCUL

Sistemul de numeraţie utilizat în sistemele de calcul este sistemul binar. În

funcţie de soluţia aleasă pentru a indica poziţia virgulei şi semnul există mai multe

moduri de reprezentare a datelor numerice.

Poziţia fixă sau variabilă a virgulei determină reprezentarea numită în virgulă

fixă, respectiv în virgulă mobilă (flotantă).

3.1. Reprezentarea informaţiei numerice în virgulă fixă

În sistemele de calcul se operează cu numere de lungime fixă , numărul de cifre

(în general 16, 32 sau 64 poziţii binare) fiind determinat de numărul de poziţii din care

sunt construite registrele utilizate.

O poziţie binară se mai numeşte bit (binary digit) şi reprezintă o locaţie (zonă)

capabilă să memoreze o cifră binară. Un octet (byte) reprezintă o succesiune de 8 biţi.

Ne vom limita la a considera situaţiile în care lungimea registrului este 2, 4 sau 8 octeţi

(bytes).

Virgula nu este realizată fizic în sistemul de calcul, iar poziţia ei este stabilită

iniţial prin proiectare şi nu poate fi schimbată.

Blocurile aritmetice ale sistemelor de calcul care lucrează în virgulă fixă

consideră virgula plasată în faţa celei mai semnificative cifre a numărului, deci numerele

cu care se operează sunt subunitare. Pentru a indica semnul numărului există mai multe

tehnici, fiecare dintre acestea determinând un mod de reprezentare.

a)

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

b)

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

c)

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

Reprezentarea în virgulă fixă poate fi extinsă pentru numerele întregi.

Dacă

N = anan-1…a1a0 (2)

atunci

N/2n+1

= 0.anan-1…a1a0 (2) unde

`12/ nN <1.

25

Reprezentarea numărului întreg N se reduce la reprezentarea numărului

subunitar N/215

, în cazul lungimii registrului de 2 octeţi, o poziţie fiind rezervată pentru

semn, utilizându-se oricare din codurile menţionate.

Este de remarcat faptul că se poate astfel reprezenta orice număr întreg N care

satisface condiţiile:

-215

N <215

-1.

Exemple:

i. Numărul N = 13(10) = 1101(2) este reprezentat astfel:

0 1 2 3 15

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

deoarece 11012-15

=0.000000000001101.

ii. Numărul N = -13(10) = 1101(2) este reprezentat după cum urmează:

a. în cod direct

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

b. în cod invers

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

c. în cod complementar

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

3.2. Reprezentarea informaţiei numerice în virgulă mobilă

Reprezentarea în virgulă mobilă s-a impus datorită necesităţii de a reprezenta în

sistemele de calcul numere foarte mari sau foarte mici cu un grad de precizie ridicat. La

baza acestui mod de reprezentare se situează reprezentarea numerelor reale (mai precis a

numerelor raţionale) cu ajutorul mantisei şi exponentului; exponentul indică ordinul de

mărime al numărului printr-o putere a bazei, iar mantisa exprimă mărimea numărului în

cadrul ordinului respectiv .

Dacă baza aleasă este b rezultă următoarea reprezentare a numărului (unică dacă

numărul este normalizat, adică dacă prima cifră după marca zecimală este nenulă):

N = (SM) Mantisa b(SE)Exponent

,

unde SM reprezintă semnul mantisei, iar SE semnul exponentului.

În cazul în care lungimea registrului este 4 octeţi (4 bytes), adică de 32 biţi, o

reprezentare posibilă în binar (b = 2) este următoarea:

0 1 6 7 8 31

SE EXPONENT SM MANTISA

Exemple:

i. N = - 0.101127 ;

0 1 6 7 8 31

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

26

ii. N = 0.110112-4

;

0 1 6 7 8 31

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

Pentru reprezentarea semnului este utilizată convenţia deja cunoscută, 0 pentru

numere pozitive, 1 pentru numere negative.

Reprezentarea menţionată poate fi îmbunătăţită, prin introducerea conceptului

de caracteristică (C), deoarece este suficient să se exprime implicit numai semnul

mantisei (M), nefiind necesar un bit special pentru semnul exponentului (E).

Definiţia 23. Se numeşte caracteristică a unui număr N, numărul C dat de relaţia C =

E + 64 , unde E este exponentul numărului exprimat în baza 16, adică:

N = (SM)M 16(SE)E

.

Pentru caracteristică sunt rezervaţi 7 biţi, deci 0 C 27-1, adică 0 C 127

prin urmare -64 E 63.

Cu aceasta, reprezentarea în virgulă mobilă simplă precizie are forma:

0 1 7 8 31

S C M

| Caracteristica (biţii 1-7) Mantisa (biţii 8-31)

S – Semnul mantisei (bitul 0)

iar reprezentarea în virgulă mobilă dublă precizie are forma:

0 1 7 8 63

S C M

| Caracteristica (biţii 1-7) Mantisa (biţii 8 -63)


Exemple: Exemple de reprezentare a numerelor în simplă precizie, cu caracteristica

reprezentată în cod invers, iar mantisa în cod complementar:

i. N = 1234;

1234(10) = 4D2(16) ;

4D2(16) = 0.4D2163 ;

E = 3 => C = 67 => C=1000011 (2) ;

0.4D2(16) = 0.010011010010(2)

0 1 0 0 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 … 0 0

0 1 7 8 31

ii. N = -1234;

1 0 1 1 1 1 0 0 1 0 1 1 0 0 1 0 1 1 1 0 … 0 0

0 1 7 8 31

27

iii. N = 0.00123456;

E = -2; C = 62 = 111110(2)

0.50E87A(16) = 0.010100001110100001111010(2)

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

0 1 7 8 31

iv. N = - 0.00123456 ;

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

0 1 7 8 31

Observaţie:

Reprezentarea informaţiilor numerice (alfaumerice) în sistemele de calcul se

realizează cu ajutorul codului ASCII extins (American Standard Cod for

Information Interchange), un caracter fiind reprezentat pe un octet.

3.3. Operaţii aritmetice cu numere reprezentate în virgulă mobilă

3.3.1. Adunarea şi scăderea

Considerăm numerele cu care lucrăm sub forma normalizată, adică:

N = (S)(0.M)(16)16C, S = + sau - ; 0.M 0.1 .

Fie numerele:

N1 = (S1)(0.M1)(16) 16C

1 , N2 = (S2)(0.M2)(16)16C

2 .

Dacă notăm C = C1 – C2 atunci distingem două situaţii:

a. În cazul C > 0 avem:

N1 + N2 = ((S1)(0.M1)(16) + (S2)(0.M2)(16)16-C

)16C

1;

b. În cazul C < 0 avem:

N1 + N2 = ((S1)(0.M1)(16)16C + (S2)(0.M2)(16))16

C1.

Reprezentarea în pseudocod a algoritmului de adunare a celor două numere este

următorul:

Pasul 1. Citeşte N1, N2 (S1, M1, C1, S2, M2, C2);

Pasul 2. C := C1 - C2;

Pasul 3. Dacă C = 0 atunci C := C1

altfel dacă C > 0 atunci C := C1; 0.M2 := 0.M216- C

altfel C := C2; 0.M1 := 0.M116 C

;

Pasul 4. 0.M := 0.M1 + 0.M2;

Pasul 5. Dacă 0.M > 0.1

atunci 0.M = 0.M16-1

; C = C + 1;

altfel dacă 0.M < 0.01 atunci 0.M = 0.M161; C = C – 1;

Pasul 6. Stop.

Algoritmul de scădere are structură identică.

3.3.2. Înmulţirea şi împărţirea

28

Date fiind numerele:

N1 = (S1)(0.M1)(16)16C

1 , N2 = (S2)(0.M2)(16)16C

2 ,

Produsul lor este:

P = (S)(0.M)(16)16C,

unde:

S = S1 S2 , “ “ este suma modulo 2;

(0.M)(16) = (0.M1)(16) (0.M2)(16) ;

C = C1 + C2 – 64.

Rezultatul obţinut nu este normalizat; este necesară normalizarea acestuia, cu

modificarea corespunzătoare a caracteristicii.

Dacă cele două numere sunt:

N1 = (S1)(0.M1)(16) 16C

1 (deîmpărţitul)

şi

N2 = (S2)(0.M2)(16) 16C

2 (împărţitorul),

atunci câtul este:

N = N1 N2 = (S)(0.M)(16) 16C,

unde:

S = S1 S2 , “ “ este suma modulo 2;

(0.M)(16) = (0.M1)(16) (0.M2)(16) ;

C = C1 - C2 .

Normalizarea câtului se realizează în acelaşi mod cu normalizarea rezultatului

oricărei operaţii aritmetice a două numere reprezentate în virgulă mobilă.

3.4. Standardul IEEE P754

3.4.1. Structura şi semnificaţia standardului

Standardul IEEE (Institute for Electrical and Electronics Engineers) P754 reprezintă o noua modalitate modernă de reprezentare a numerelor în virgulă mobilă.

A fost realizat în Advanced Micro Devices (AMD), pentru reprezentarea pe 32,

64 sau 128 de biţi şi implementat pe procesorul virgulă mobilă Am 29325.

Standardul IEEE P754 realizat pe 32 de biţi are următoarea structură:

31 30 29 28 27 26 25 24 23 22 3 2 1 0

27 2

6 2

5 2

4 2

3 2

2 2

1 2

0 2

-1 … 2

-20 2

-21 2

-22 2

-23

S

Exponent(E) Fracţia(F)

Bitul 31 este bitul semn şi indică semnul numărului reprezentat; 0 pentru

numere nenegative şi 1 pentru numere negative; numărul 0 poate avea ambele semne.

Exponentul E este o succesiune de 8 biţi care este un număr întreg fără semn şi

reprezintă o putere a lui 2; valoarea de bază este 127 adică pentru un număr oarecare de

forma 2a (deci pentru exponentul adevărat) valoarea exponentului este

E = a + 127.

29

Partea fracţionară (F) este un întreg fără semn, ocupă 23 biţi; cifra cea mai

semnificativă a părţii fracţionare este pe poziţia bitului 22, iar cifra cea mai puţin

semnificativă a părţii fracţionare este dată de bitul 0.

Valoarea numărului memorat în reprezentarea de mai sus este ( -1)S2

E-127 (1.F).

Un număr în virgulă mobilă este interpretat folosind următoarele convenţii:

1. Dacă E = 0 şi F = 0 , valoarea este ( -1)S (0), deci (+0) sau (-0);

2. Dacă E = 0 şi F 0, valoarea este un număr nenormalizat; un număr

nenormalizat reprezintă o entitate de ordin de mărime mai mic decât 2-126

şi mai mare

decât 0, dacă S = 0.

3. Dacă 0 < E < 255, valoarea este egală cu (-1)S2

E-127(1.F) şi reprezintă un

număr normalizat; reprezintă o cantitate de mărime mai mare sau egală cu 2-126

şi mai

mică decât 2128

, dacă S = 0.

Exemple:

i. Numărul +3.5 poate fi reprezentat astfel:

+3.5 = 11.1(2)20 = 1.11(2)2

1;

S = 0; E = 1(10)+127(10) = 128(10) = 10000000(2);

F = 11000000000000000000000;

31 30 23 22 17 16 1 0

0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 … 0 0 0

S

E F

Concatenând aceste câmpuri rezultă cuvântul virgula mobilă 40600000 (16).

ii. Pentru numărul N = -11.375 avem:

F = 01101ori17

0...100

deci reprezentarea este:

31 30 23 22 17 16

1 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0 … 0 0 0

S

E F

Concatenarea acestor părţi furnizează cuvântul virgula mobilă C1360000 (16).

4. Dacă E = 255 şi F = 0, valoarea este ( -1)S(∞), deci (+∞/- ).

5. Dacă E = 255 şi F 0, valoarea este nenumerică (Not A Number, sau

prescurtat NAN).

30

Valoarea (NAN) nu reprezintă o valoare numerică şi este interpretat ca un

simbol sau ca un semnal. Este folosit pentru a indica operaţii invalide (de exemplu

apariţia unei situaţii 00.0 generează un NAN), sau ca operand-input.

Există două tipuri de NAN şi anume:

- NAN semnalizator cu reprezentarea:

31 30 23 22 17 16 1 0

x 1 1 1 1 1 1 1 1 1 x x x x x x … x x x

S

- NAN nesemnalizator cu reprezentarea:

31 30 23 22 17 16 1 0

x 1 1 1 1 1 1 1 1 0 x x x x x x … x x x

S

în care cel puţin unul din ultimii 22 biţi are valoarea 1. x - marchează faptul că poate fi

utilizată orice cifră dintre 0 şi 1.

6. Formatul întreg (model IEEE) este permis. Numerele întregi sunt reprezentate

pe 32 biţi, ca în figura următoare:

x 31 30 29 28 27 8 7 6 5 4 3 2 1 0

231

230

229

228

227

… 28 2

7 2

6 2

5 2

4 2

3 2

2 2

1 2

0

Valoarea maximă a unui întreg ce poate fi reprezentat este 231

–1, iar valoarea

minimă -231

(luând complementul faţă de 2).

3.4.2. Operaţii cu numere reprezentate în standardul IEEE P754

Operaţiile aritmetice (adunarea, scăderea, înmulţirea, împărţirea) ce se

efectuează, în general, asupra numerelor reprezentate în virgulă mobilă rămân valabile

şi în cazul standardului P754. Se impun însă câteva precizări specifice acestui mod de

reprezentare.

3.4.2.6. Rotunjirea

Rotunjirea se efectuează ori de câte ori o operaţie furnizează un rezultat exact

care nu poate fi reprezentat complet (exact) în formatul propus.

De exemplu să presupunem că o operaţie în virgulă mobilă produce un rezultat

exact egal cu :

1.101010101010101010101010123

a cărei parte fracţionară a mantisei are 25 biţi, iar formatul IEEE în virgulă mobilă

acceptă numai 23. Se pune problema rotunjirii rezultatului, deci al aproximării prin

reprezentarea care să concorde cu formatul.

Există 4 posibilităţi de rotunjire ale standardului IEEE şi anume:

31

1. Rotunjirea la cel mai apropiat; rezultatul exact este rotunjit prin reprezentarea cea

mai apropiată de rezultatul exact, care se poate încadra in format.

Exemplul 1. Valoarea

220

+2-4

+2-5

= 1.0000000000000000000000011 220

23 de ori

este rotunjită prin valoarea

220

+2-3

= 1.00000000000000000000001220

. 22 de ori

2. Rotunjirea spre - ; se realizează prin valoarea cea mai mare, mai mică sau egală

cu rezultatul exact, care se încadrează în formatul considerat. Rotunjirea este realizată

atât pentru virgulă mobilă cât şi pentru format întreg.


220

+2-4

+2-5

= 1.0000000000000000000000011 220

23 de ori


220

= 1.00000000000000000000000220

.

3. Rotunjirea spre + ; se realizează prin valoarea cea mai mică, mai mare sau egală

cu valoarea exactă, care se încadrează în formatul considerat. Rotunjirea este realizată

atât pentru virgulă mobilă cât şi pentru format întreg.

Exemplul 1. Valoarea 220

+2-4

+2-5

se rotunjeşte prin următoarea valoare mai

mare în virgulă mobilă, deci prin:

220

+2-3

= 1.00000000000000000000001 220

. 22 de ori

4. Rotunjirea spre 0; realizează rotunjirea prin suprimarea poziţiilor din valoarea

exactă care depăşesc formatul considerat.


220

+2-4

+2-5

= 1.0000000000000000000000011 220

23 de ori


220

= 1.00000000000000000000000220

23 de ori

3.4.2.7. Exemple

Să se reprezinte numerele:

a. N1 = 78656;

b. N2 = -78656;

c. N3 = 0.00213456;

d. N4 = -0.00213456;

în virgulă mobilă, precizie simplă, cu mantisa reprezentată în cod complementar iar

caracteristica în cod invers.

e. Să se reprezinte aceleaşi numere în standardul IEEE P754.

S C M

0 1 7 8 31

32

N = (SM)M(16) 16(SE)E

; C = E+64;

a. 78756(10) = 13340(16)

N1 = 0.1334 165

E = 5 implică C = 5 + 64 = 69

C = 1000101(2)

M = 0.0001001100110100(2)

0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0 0 1 1 0 1 0 … 0

S 7 8 31

b.

1 1 0 0 0 1 0 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 0 … 0

S 7 8 31

c. 0.00213456 16 = 0.0341529

0.0341529 16 = 0.5464473

0.5464473 16 = 8.74315

0.74315 16 = 11.890508

0.890508 16 = 14.248128

0.248128 16 = 3.970048

0.00213456(10) = 0.008BE3(16) = 0.8BE3(16) 16-2

;

E = -2 implică C = 62; 62 = 111110 (2);

0.8BE3(16) = 0.1000101111100011(2);

0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 1 1 1 1 0 0 0 1 1 0 ... 0

S 1 7 8 9 31

d.

1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 … 0

S 7 8 9 31

e. În standardul IEEE P754, (-1)S2

E-127 (1.F) este valoarea numărului reprezentat în

registrul:

0 1 8 9 31

S E F

i. 78656(10) = 13340(16);

78656(10) = 10011001101000000(2) = 1.0011001101000000 216

;

E – 127 = 16 implică E = 143; 143 = 10001111 (2);

S = 0;

F = 00110011010…0;

0 1 8 9 31

0 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 0 …

.

.

0

33

ii. - 78656(10) = - 13340(16);

0 1 8 9 31

1

0

1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 0 …

.

.

0

iii. 0.00213456(10) = 0.008BE3(16) = 0.000000001000101111100011(2);

0.00213456(10) = 1.000101111100011 2-9

(2);

S = 0;

E – 127 = -9;

E = 118; E = 01110110(2);

F = 0001011111000110…0;

0 1 8 9 31

0 0

1

1

1

0

1

0

1

0

0

1

1

0

1

1 0

1

0 0 0

1

1 0 1

0

1 1 1

0

1 0 0 1

.

1

.

…

..

0

iv. - 0.00213456(10) = - 0.000000001000101111100011(2);

0 1 8 9 31

1

0

0

1

1

1

0

1

0

1

0

0

1

1

0

1

1 0

1

0 0 0

1

1 0 1

0

1 1 1

0

1 0 0 1

.

1

.

… 0

3.5. Rezumat

Menţionăm existenţa a două moduri de reprezentare a datelor numerice, în

funcţie de soluţia aleasă pentru a indica poziţia mărcii zecimale şi a semnului.

Poziţia fixă sau variabilă a mărcii zecimale determină reprezentarea numită în

virgulă fixă, respectiv în virgulă mobilă (flotantă).

În cazul reprezentării informaţiei numerice în virgulă fixă, în sistemele de

calcul se operează cu numere de lungime fixă , numărul de cifre (în g eneral 16, 32 sau

64 poziţii binare) fiind determinat de numărul de poziţii din care sunt construite

registrele utilizate.

O poziţie binară se mai numeşte bit (binary digit) şi reprezintă o locaţie (zonă)

capabilă să memoreze o cifră binară. Un octet (byte) reprezintă o succesiune de 8 biţi.

Ne vom limita la a considera situaţiile în care lungimea registrului este 2, 4 sau 8 octeţi

(bytes).

Virgula nu este realizată fizic în sistemul de calcul, iar poziţia ei este stabilită

iniţial prin proiectare şi nu poate fi schimbată.

Blocurile aritmetice ale sistemelor de calcul care lucrează în virgulă fixă

consideră virgula plasată în faţa celei mai semnificative cifre a numărului, deci numerele

cu care se operează sunt subunitare. Pentru a indica semnul numărului există mai multe

tehnici, dependente de codul folosit (direct, complementar, sau invers), fiecare dintre

acestea determinând un mod de reprezentare în cazul numerelor negative.

Reprezentarea în virgulă mobilă s-a impus datorită necesităţii de a reprezenta în

sistemele de calcul numere foarte mari sau foarte mici cu un grad de precizie ridicat. La

baza acestui mod de reprezentare se situează reprezentarea numerelor reale (mai precis a

numerelor raţionale) cu ajutorul mantisei şi exponentului; exponentul indică ordinul de

mărime al numărului printr-o putere a bazei, iar mantisa exprimă mărimea numărului în

cadrul ordinului respectiv .

34

Dacă baza aleasă este b rezultă următoarea reprezentare a numărului (unică dacă

numărul este normalizat, adică dacă prima cifră după marca zecimală este nenulă):

N = (SM) Mantisa b(SE)Exponent

,

unde SM reprezintă semnul mantisei, iar SE semnul exponentului.

În reprezentarea în virgulă mobilă se utilizează conceptul de caracteristică (în

locul exponentului), deoarece este suficient să se exprime implicit numai semnul

mantisei (M), nefiind necesar un bit special pentru semnul caracteristicii (C).

Se numeşte caracteristică a unui număr N, numărul C dat de relaţia C = E +

64 , unde E este exponentul numărului exprimat în baza 16, adică:

N = (SM)M 16C-64

.

Cu aceasta, reprezentarea în virgulă mobilă simplă precizie are forma:

0 1 7 8 31

S C M



iar reprezentarea în virgulă mobilă dublă precizie are forma:

0 1 7 8 63

S C M



Se tratează operaţiile cu numere reprezentate în virgulă mobilă (adunare,

scadere, înmulţire, împărţire).

Capitolul se încheie cu prezentarea aspectelor teoretice şi aplicative relative la

standardul IEEE P754 (structură, operaţii).

35

PARTEA A DOUA

BAZELE LOGICE ALE SISTEMELOR

DE CALCUL

CAPITOLUL II

STRUCTURI ALGEBRICE IMPLICATE ÎN

PROIECTAREA ŞI OPTIMIZAREA CIRCUITELOR

2.1. Latice

Definiţia 1. O latice este o mulţime L nevidă, înzestrată cu o relaţie binară, “ “, ale

cărei elemente satisfac următoarele proprietăţi:

i. x x, xL, (reflexivitate);

ii. (x y si y x) x = y x, yL, (antisimetrie);

iii. (x y si y z) x z x, y, zL, (tranzitivitate);

iv. x, yL, sL astfel încât ( x s si s si (zL: (x z si y z)) s z,

(existenţa unui cel mai mic majorant);

v. x, yL, pL astfel încât (p x si p y si (zL:(z x si z y)) zp,

(existenţa unui cel mai mare minorant).

Observaţie: Din proprietăţile (i) (ii) şi (iii) şi din definiţia 1 rezultă că L este o mulţime

parţial ordonată în raport cu relaţia ““ iar din (iv) şi (v) rezultă că pentru oricare două

elemente există un cel mai mic majorant comun şi un cel mai mare minorant comun.

Relativ la definiţia anterioară considerăm operatorii :

“”: L LL, x y: = p, x, y L

şi

“”: L LL, x y: = s, x, y L.

Propoziţia 1. Au loc următoarele proprietăţi x, y, z L:

i. x x = x, x x = x (idempotenţa);

ii. x y = y x, x y = y x (comutativitatea);

iii. x (y z) = (x y) z,

x (y z) = (x y) z), (asociativitatea);

iv) x (x y) = x, x (x y) = x (absorbţia).

Observaţie: O latice se poate defini şi ca o mulţime L nevidă înzestrată cu două operaţii

““ şi ““ care satisfac proprietăţile din propoziţia precedentă. În acest caz, relaţia de

ordine parţială din prima definiţie se regăseşte astfel:

x y: x y = x (sau x y = y).

Definiţia 2. O latice se numeşte distributivă dacă satisface şi proprietăţile:

36

i. x (y z) = (x y) (x z) x, y, z L;

ii. x (y z) = (x y) (x z) x, y, z L.

Definiţia 3. Într-o latice distributivă L, un element 0L cu proprietăţile x 0 = x, x 0

= 0 se numeşte prim element al laticei, iar un element 1 L cu proprietăţile x 1=1 şi

x 1 = x se numeşte ultim element al laticei.

Observaţie:

Relativ la relaţia de ordine dintr-o latice, primul element dacă există, are

proprietatea că xL, x 0 iar ultimul element tot dacă există are proprietatea că

xL, x 1.

Definiţia 4. O mulţime nevidă L în care s-a definit o relaţie binară, ale cărei elemente

satisfac proprietăţile (i), (ii) şi (iii) şi una din proprietăţile (iv) sau (v) din definiţia 1 se

numeşte semilatice.

Propoziţia 2. (Principiul dualităţii) Din orice afirmaţie adevărată relativă la elementele

unei latice şi la operatorii ““ şi ““ se deduce o altă afirmaţie adevărată dacă se

schimbă ““ cu ““ şi invers.

Propoziţia 3. x, y, L avem x y = x dacă şi numai dacă x y = y.

Demonstraţie:

Implicaţia “”: x y = y (x y)= y;

Implicaţia “”: x y = x (x y)= x.

Exemplu: Mulţimea numerelor naturale N înzestrată cu operaţiile "" şi "" definite de:

n m = max {n, m} n, m N;

n m = min {n, m} n, m N,

este o latice.

Demonstraţie:

i. n m = max{n, m} = max{m, n}= m n,

ceea ce dovedeşte comutativitatea;

ii. n (m p) = max {n, max {m, p}} = max{n, m, p} =

max{max{n, m}, p} = (n m) p,

ceea ce dovedeşte asociativitatea;

iii. n (m n) = max {n, min {m, n}}= n , ceea ce dovedeşte absorbţia.

Egalităţile pereche se demonstrează analog.

Exemplu:

Mulţimea numerelor naturale N înzestrată cu operaţiile "" şi "" definite de:

n m: = cmmdc (n, m) n, m N;

n m: = cmmmc (n, m) n, m N,

are de asemenea o structură de latice.

Definiţia 5. Într-o latice L care admite prim şi ultim element, elementul x’ L se numeşte

complement al lui x L dacă şi numai dacă x’ x = 0 şi x’ x =1.

37

Propoziţia 4. Într-o latice distributivă dacă un element are un complement atunci acest

complement este unic.

2.2. Algebra booleană

Definiţia 6. Se numeşte algebră booleană orice latice distributivă cu prim şi ultim

element, în care orice element admite complement.

Din această definiţie rezultă imediat următoarea propoziţie.

Propoziţia 5. Într-o algebră booleană (A, , , 0,1, ), unde “”, “” sunt operaţiile

ce definesc laticea, 0 şi 1 sunt primul respectiv ultimul element al laticei iar operatorul

: A A pune în corespondenţa lui x A complementul său x A, sunt valabile

următoarele afirmaţii:

i. a b = b a, a b = b a, a, b A;

ii. a (b c) = (a b) c, a (b c) = (a b) c, a, b, c A;

iii. a (a b) = a, a (a b) = a, a, b A;

iv. a (b c) = (a b) (a c),

a (b c) = (a b) (a c), a, b, c A;

v. (a a) b = b, (a a) b = b, a, b A.

Observaţie:

Se poate defini algebra booleană independent de noţiunea de latice, ca fiind o

mulţime nevidă A înzestrată cu două operaţii binare ““, ““, şi o operaţie unară “ “

ce satisfac relaţiile din propoziţia 5.

Propoziţia 6. Într-o algebră booleană au loc:

i. a a =a, a a =a, a A (idempotenţa);

ii. a b =a a b =b.

Demonstraţie:

Rezultă imediat din propoziţia 1 şi propoziţia 2 dacă ţinem cont că algebra

booleană a fost definită ca latice.

În mod echivalent avem:

i. a = a (a b) = (a a) (a b) = [a (a b)] [a (a b)] = a a;

a = a (a b) = (a a) (a b) = [a (a b)] [a (a b)] = a a;

ii. () a b = (a b) b = b;

() a b = a (a b) = a;

Definiţia 7. Dacă a, b A, A algebră booleană, spunem că a este mai mic decât b (sau b

este mai mare decât a, sau a este un minorant al lui b, sau b este un majorant al lui a,

sau a este un subelement al lui b, sau a este conţinut în b, sau b conţine a) şi vom nota

a b, dacă a b = a, sau, echivalent a b = b. Relaţia ““ se numeşte relaţie de

incluziune booleană.

Observaţie:

Relaţia ““ este o relaţie de ordine parţială pe A deoarece este relaţia de ordine

parţială din definiţia laticei care este algebra booleana A. Din aceleaşi motive elementul a

38

b (respectiv a b) este cel mai mic majorant comun (respectiv cel mai mare minorant

comun) al elementelor a si b.

Propoziţia 7. Dacă niia

,1 A şi

n

iiab

1 , atunci b este cel mai mic element care

conţine toate elementele niia

,1. Aşadar:

i. ai b, ni ,1 ;

ii. ai f, ni ,1 b f.

Dacă n

iiac

1 atunci c este cel mai mare element care este conţinut în toate

elementele niia

,1. Aşadar:

i’. c ai ni ,1 ;

ii’. g ai ni ,1 g c.

Definiţia 8. Într-o algebră booleană primul şi ultimul element al laticei se numesc

elementul zero respectiv elementul unitate.

Definiţia 9. Algebra booleană A se numeşte nedegenerată dacă conţine cel puţin două

elemente.

Observaţie:

O condiţie necesară şi suficientă ca o algebră booleană A să fie degenerată este ca

1 = 0.

Propoziţia 8. (Principiul dualităţii, în algebrele booleene)

Dacă într-o afirmaţie adevărată privind operaţiile "", ""," " şi elementele 0

şi 1 înlocuim "" cu "", "" cu "", 0 cu 1 şi 1 cu 0 lăsând operaţia " " neschimbată,

obţinem tot o propoziţie adevărată (numită duala primei propoziţii).

Propoziţia 9. În orice algebră booleană A, sunt adevărate următoarele afirmaţii:

i. a = a , a A;

ii. a = b a =b, a, b A;

iii. ba = a b, ba = a b, a, b A, (relaţiile De Morgan);

iv. a b b a a, b A.

Observaţie:

Din propoziţia precedentă se obţine

ba =a b , ba =a b,

prin urmare intersecţia poate fi definită cu ajutorul reuniunii şi complementarei şi analog

reuniunea poate fi definită cu ajutorul intersecţiei şi complementarei.

Observaţie: Înlocuind în ba =a b pe b cu a rezultă că 1 = 0. Prin

complementare rezultă că 0 = 1.

39

Definiţia 10. Pentru două elemente a, b A diferenţa lor este dată de relaţia

a - b: = a b.

Observaţie:

Din definiţia de mai sus rezultă că 1- a =a, a A.

Teorema 1. (de reprezentare a lui Stone) Orice algebră booleană este izomorfă cu un corp de părţi.

Definiţia 11. Pentru o mulţime cu () mulţimea părţilor lui , mulţimea

K(), K se numeşte corp de părţi dacă şi numai dacă este închisă faţa de

complementare şi reuniune, adică:

i. A K CA = -A K,

ii. A, B K A B K.

În consecinţă, orice algebră booleană finită are 2n

elemente unde n este numărul

atomilor algebrei (Dacă A este algebră booleană atunci a A se numeşte atom dacă şi

numai dacă b A: b a b =0 sau b = a).

Deci se pot defini algebre booleene (B(p), , , ) cu p N* elemente dacă şi

numai dacă n N: p = 2n (adică dacă şi numai dacă p este o putere a lui 2).

2.3. Inel boolean

Definiţia 12. Se numeşte inel o mulţime nevidă I înzestrată cu două operaţii (legi de

compoziţie) “+” şi ““ care verifică proprietăţile:

i. a + b = b + a, a, b I , (comutativitatea);

ii. a + (b + c) = (a + b) + c, a, b, c I, (asociativitatea);

iii. 0 I: a + 0 = 0 + a = a, a I, (existenţa elementului neutru);

iv. a I, -a I: a + (-a) = (-a) + a = 0, (existenţa elementului simetric);

v. a (b + c) = a b + a c, a, b, c I,

(a + b) c = a c + b c, a, b, c I,

(distributivităţile la dreapta şi la stânga ale operaţiei ““ faţă de “+”);

vi. a (b c)=(a b) c, a, b, c I, (asociativitatea).

Definiţia 13.

i. Un inel (I, +, ) cu proprietatea ca 1 I: a 1 = 1 a = a, a I se

numeşte inel cu element unitate.

ii. Un inel (I, +, ) cu proprietatea a b = b a, a, b I se numeşte inel

comutativ.

Definiţia 14.

Un inel (I, +, ) cu element unitate şi cu proprietatea că a a = a, a I se

numeşte inel boolean.

Propoziţia 11. În orice inel boolean (I, +, ) au loc următoarele proprietăţi:

i. a + a = 0, a I;

ii. a + b = 0 a = b, a, b I;

iii. a b = b a, a, b I;

40

iii. a 0 = 0 a = 0, a I.

Propoziţia 12. a + b = c b = a + c a = b + c, a, b, c I.

2.4. Legătura dintre algebra booleană şi inelul boolean

Teorema 2. Orice algebră booleană A este un inel boolean cu următoarele definiţii ale

operaţiilor de adunare şi înmulţire:

a + b: = (a-b) (b-a) (= (a b) (b a));

a b: = a b.

Reciproc, orice inel boolean I este o algebră booleană cu următoarele definiţii ale

operaţiilor de reuniune, intersecţie şi complementare:

a b = a + b + a b;

a b = a b;

a = 1 + a.

Mai mult, în ambele cazuri elementul neutru faţă de “+” şi elementul neutru faţă

de “ “ din inelul boolean coincid cu elementul zero respectiv elementul unitate din

algebra booleană.

2.5. Exemple reprezentative: (X), X≠Ø; B(2), B(4), Z2

i. Mulţimea părţilor unei mulţimi.

Pentru o mulţime X , mulţimea (X) a părţilor lui X înzestrată cu operaţiile

de reuniune, intersecţie şi complementare din teoria mulţimilor, fo rmează o algebră

booleană:

(X) ={A | A X};

: (X) (X) (X), AB={ x X | x A sau x B}, A,B (X);

: (X) (X) (X), AB={ x X | x a şi x B }, A,B (X);

: (X) (X), A = { x X | x A}, A (X).

Propoziţia 13. ( (X), , , ) este o algebra booleană în care primul element este

iar ultimul element este X, mulţimea totală.

ii. Algebra booleană binară.

Mulţimea B(2) ={0, 1} înzestrată cu operaţiile definite în tabelele 1, 2, 3

Suma logică Produsul logic Complementara

0 1 0 1 x x

0 0 1 0 0 0 0 1

1 1 1 1 0 1 1 0

Tabelul 1. Tabelul 2. Tabelul 3.

41

formează o algebră booleană în care primul element este 0, iar ultimul element este 1.

Verificarea condiţiilor ce trebuie să fie îndeplinite pentru ca (B(2), , , , 0, 1) să aibă

structură de algebră booleană o facem prin epuizarea tuturor valorilor ce le pot avea

variabilele.

iii. Algebra booleană cu patru elemente.

B(4) ={0, a, b, 1} înzestrată cu operaţiile definite în tabelele 6, 7, 8

0 a b 1 0 a b 1 x x

0 0 a b 1 0 0 0 0 0 0 1

a a a 1 1 a 0 a 0 a a b

b b 1 b 1 b 0 0 b b b a

1 1 1 1 1 1 0 a b 1 1 0


şi cu 0 prim element, iar 1 ultim element, formează o algebra booleană.

Se pot pune în evidenţă, din tabelele reuniunii şi intersecţiei relaţiile de incluziune

(de ordine) dintre elemente:

0 a, 0 b, 0 1, (0 este cel mai mic element),

a 1, b 1, 0 1, (1 este cel mai mare element),

a b sau b a nu sunt adevărate deoarece a b = 0 şi a b =1 şi deci nu există relaţie

de ordine între a şi b. Rezultă astfel că într-adevăr relaţia de ordine ce se poate defini în

general într-o algebră booleană este doar parţială.

Verificarea condiţiilor din definiţia algebrei booleene se poate face ca la exemplul

anterior însă cu un volum de calcule sporit.

iv. Clasa de resturi modulo 2.

Z2 ={0, 1} împreună cu operaţiile de adunare şi înmulţire modulo 2 are o structura

de inel boolean. Tabelele operaţiilor din inel sunt:

0 1 0 1

0 0 1 0 0 0

1 1 0 1 0 1

Tabelul 9. Tabelul 10.

Acest inel boolean (Z2, , ) este echivalent, pe baza teoremei 1 cu o algebră

booleană înzestrată cu operaţiile:

a b = a b (a b), a b = a b, a = 1 a.

Definind concret operaţiile de reuniune, intersecţie şi complementare se obţin

tabelele:

0 1 0 1 x x

0 0 1 0 0 0 0 1

42

1 1 1 1 0 0 1 0


Din structura acestor tabele rezultă că algebra booleană cu care este echivalent

inelul claselor de resturi modulo 2 este chiar algebra booleană binară (B(2), , , ).

2.6 Rezumat

Structurile algebrice de bază implicate în proiectarea şi optimizarea circuitelor

sunt laticile, algebrele booleene şi inelele booleene.

O latice este o mulţime nevidă, înzestrată cu o relaţie binară (reflexivă,

antisimetrică şi tranzitivă), ale cărei oricare două elemente admit un cel mai mare

minorant şi un cel mai mic majorant. Echivalent, o latice poate fi definită şi ca o mulţime

nevidă înzestrată cu două operaţii comutative, asociative, idempotente care satisfac

totodată şi relaţiile de absorbţie. Un principiu al dualităţii are loc în orice latice: din

orice afirmaţie adevărată relativă la elementele unei latice şi la operatorii din definiţie se

deduce, prin inversarea operatorilor, o altă afirmaţie adevărată.

Se numeşte algebră booleană orice latice distributivă cu prim şi ultim element, în

care orice element admite complement. Primul şi ultimul element din latice se vor numi

element “zero” şi respectiv element “unitate” ale algebrei booleene. Existenţa

complementelor permite definirea unui operator unar de complementariere (negare).

Principiul dualităţii într-o algebră booleană va impune, suplimentar, ca negaţiile să

rămână neschimbate, iar constantele 0 şi 1 să se inverseze.

Inelul boolean este un inel (cu operaţia aditivă comutativă, asociativă, cu element

neutru şi cu toate elementele simetrizabile; cu operaţia multiplicativă asociativă şi

distributivă faţă de operaţia aditivă) cu element unitate (element neutru faţă de operaţia

multiplicativă) în care operaţia multiplicativă este idempotentă (orice element multiplicat

cu el însuşi rămâne neschimbat).

Structurile de algebră booleană şi inel boolean sunt echivalente: orice algebră

booleană poate fi organizată ca un inel boolean şi reciproc, orice inel boolean poate fi

organizat ca o algebră booleană. Mai mult, în ambele cazuri, elementele neutre din inelul

boolean coincid cu elementul zero respectiv elementul unitate din algebra booleană.

Exemple reprezentative de algebre/inele booleene: mulţimea părţilor unei

mulţimi (X), algebra booleană binară B(2), algebra booleană cuaternară B(4), inelu l

claselor de resturi modulo 2 Z2.

43

CAPITOLUL III

FUNCŢII BOOLEENE ŞI EXPRESII REED-MULLER

3.1. Funcţii booleene

Fie B(2)=({0, 1}, , , ) algebra booleană binară.

Definiţia 1. Se numeşte funcţie booleană de n variabile o aplicaţie f:

(B(2))n B(2) unde (B(2))

n reprezintă produsul cartezian B(2)B(2). . . . B(2).

Observaţie: Domeniul de definiţie al unei funcţii booleene de variabile este o mulţime

compusă din 2n elemente; se pot defini atunci

n22 funcţii booleene de n variabile

distincte.

Exemplu: Pentru cazul n = 1 rezultă, din observaţia anterioară că există 22

= 4 funcţii

distincte fi : B(2) B(2), 3,0i .

x f0(x) f1(x) f2(x) f3(x)

0 0 0 1 1

1 0 1 0 1

Tabelul 1.

f0(x)= x x = 0, funcţia contradicţie;

f1(x)= x, funcţia identitate;

f2(x)=x, funcţia negaţie;

f3(x)= x x = 1, funcţia “lege logică” sau tautologie.

Exemplu:

Pentru cazul n = 2 avem 222 =16 funcţii booleene de două variabile booleene fi:

B(2)B(2) B(2), 5,0i .

x y f0(x, y) f1(x, y) f2(x, y) f3(x, y) f4(x, y) f5(x, y) f6(x, y) f7(x,

y)

0 0 0 0 0 0 0 0 0 0

0 1 0 0 0 0 1 1 1 1

1 0 0 0 1 1 0 0 1 1

1 1 0 1 0 1 0 1 0 1

Tabelul 2.

x y f8(x, y) f9(x, y) f10(x, y) f11(x, y) f12(x, y) f13(x, y) f14(x, y) f15(x, y)

0 0 1 1 1 1 1 1 1 1

44

0 1 0 0 0 0 1 1 1 1

1 0 0 0 1 1 0 0 1 1

1 1 0 1 0 1 0 1 0 1

Tabelul 2 (continuare).

Relativ la aceste funcţii, definite mai sus prin valorile pe care le iau pe mulţimea

valorilor posibile ale variabilelor lor, se remarcă următoarele:

f0(x, y) 0, funcţia identic 0 (contradicţie);

f1(x, y) = x y, funcţia “şi”;

f2(x, y) = x y;

f6(x, y) = zx , funcţia suma modulo 2 (sau exclusiv);

f7(x, y) = x y, funcţia sau (suma logică);

f8(x, y) = x y = yx , funcţia “nici” a lui Pierce;

f9(x, y) = xy, funcţia “echivalenţă”;

f13(x, y) = x y, funcţia “implicaţie”;

f14(x, y) = xy = yx , funcţia “numai” a lui Schäffer;

f15(x, y) 1, funcţia lege logică (tautologie).

3.2. Formulele de interpolare Lagrange

Teorema 1. Orice funcţie booleană f: (B(2))n B(2) poate fi pusă sub forma

f ),...,(1 n

xx =nB

n))2((),...,

2,

1(

(f ),...,1

(n

x

1 x

2 ... x n

) (1)

sau

f ),...,(1 n

xx = nB

n))2((),...,

2,

1(

(f ),...,1

(n

x1

1

x2

2

... xn

n

) (2)

unde disjuncţia din prima formulă şi conjuncţia din cea de-a doua se iau după toate n-

uplele (1, 2,..., n) (B(2))n, iar pentru orice x B(2) am notat x

0 =x şi x

1 = x.

Observaţie:

Formula (1) se numeşte prima formulă de interpolare a lui Lagrange, iar

membrul drept se numeşte forma canonică disjunctivă a funcţiei booleene f(x1, x2,...,

xn). Formula (1) este echivalentă cu:

f ),...,(1 n

xx =nB

n))2((),...,

2,

1(

( 11

x 2

2

x ... n

nx

) (1’).

Formula (2) se numeşte a doua formulă de interpolare Lagrange, iar membrul

ei drept se numeşte forma canonică conjunctivă a funcţiei booleene f(x1, x2, . . . xn).

Formula (2) se mai poate scrie:

45

f ),...,(1 n

xx = nB

n))2((),...,

2,

1(

( x1

1

21

x ... x

nn

) (2’).

Rezultă din (1’) şi (2’) că prima formulă fundamentală de reprezentare a funcţiilor

booleene (1) este utilă atunci când avem un număr mare de nerealizări (de zerouri) ale

funcţiei şi un număr mic de realizări, iar a doua formulă fundamentală de reprezentare (2)

este recomandată în caz contrar, deci atunci când avem un număr mic de nerealizări (de

zerouri) şi un număr mare de realizări (de valori 1) ale funcţiei.

Definiţia 2. i. Se numeşte constituent al nulului (sau maxterm) suma logică de forma

11

x 2

2

x ... n

nx

, unde xi B(2), ni ,1 şi i B(2), ni ,1 .

ii. Se numeşte constituent al unităţii (sau minterm) produsul logic de

forma 11

x 2

2

x ... n

nx

, unde xi B(2), ni ,1 şi i B(2),

ni ,1 .

Observaţie:

Justificarea denumirii de constituent al nulului rezidă în faptul că:

nBn

))2((),...,2

,1

(

( x1

1

22

x ... x

nn

) = 0.

Justificarea denumirii de constituent al unităţii constă în relaţia:

nBn

))2((),...,2

,1

(

( 11

x 2

2

x ... n

nx

) = 1.

Exemplu:

Pentru n = 3 avem 23

= 8 mintermi şi 8 maxtermi. Explicităm câţiva dintre

aceştia:

zyxmm 0) 0 0(0

, zyxMM 0) 0 0(0

,

zyxmm 1) 1 0(3

, zyxMM 0) 1 0(2

,

zyxmm 0) 1 1(6

, zyxMM 1) 0 1(5

,

zyxmm 1) 1 (17

, zyxMM 1) 1 1(7

.

Regula de determinare a fost următoarea: indicele mintermului (0, 3, 6 respectiv

7) l-am transformat în baza 2. Toate numerele de la 0 la 7 se exprimă în baza 2 pe exact 3

poziţii şi ele epuizează toate combinaţiile posibile de 0 şi 1 pe care le pot lua variabilele

x, y, z. Prin urmare scrierea în baza 2 a indicelui fixează argumentul pentru care

minteremul ia valoarea 1. Expresia mintermului va fi atunci conjuncţia variabilelor cărora

în explicitare le corespunde valoarea 1 şi a negaţiilor variabilelor cărora în explicitare le

corespunde valoarea 0.

46

Analog, expresia maxtermului va fi disjuncţia variabilelor cărora prin explicitarea

indicelui în baza 2 le corespunde valoarea 0 şi a negaţiilor variabilelor cărora le

corespunde valoarea 1 în aceeaşi explicitare a indicelui.

Observaţie: Regula de mai sus este de fapt regula generală de determinare a expresiilor

minternilor şi respectiv maxtermilor de indice dat.

Propoziţia 1. Conjuncţia a doi mintermi distincţi este identic nulă iar disjuncţia a doi

maxtermi distincţi este identic 1.

Teorema 2. Orice funcţie booleană f : (B(2))nB(2) poate fi reprezentată sub forma:

),...2

,0(1

),...2

,1(1

),...,2

,1

(n

xxfxn

xxfxn

xxxf

Observaţie: Ţinând seama de faptul că f(1,x2,...xn) şi f(0, x2...xn) sunt funcţii numai de variabile

x2, x3,...,xn continuând raţionamentul din teorema anterioară cu x2 şi apoi,

succesiv, şi cu celelalte variabile, obţinem o expresie arborescentă care generează

funcţia f.

3.3. Sisteme complete de funcţii booleene

Definiţia 3. Se numeşte sistem complet de funcţii booleene o mulţime de funcţii

booleene cu ajutorul cărora se poate exprima orice funcţie booleană.

Observaţie:

Funcţia “nici”, funcţia “numai”, setul de funcţii “şi” şi “nu”, setul de funcţii “sau”

şi “nu”, setul de funcţii „ ” (adunare modulo 2) şi „ ” (înmulţire modulo 2) formează,

fiecare în parte, un sistem complet de funcţii booleene.

3.4. Simplificarea funcţiilor booleene

Funcţiile booleene pot fi exprimate printr-un număr mare de expresii. Pentru a

compara aceste expresii, din punctul de vedere al complexităţii lor, e necesar să se

stabilească anumite criterii. În acest scop a fost introdusă noţiunea de cost asociat unei

expresii date.

Funcţiile cost cele mai utilizate sunt:

- numărul total de variabile (litere) cuprinse în expresie;

- numărul total de operatori (contacte) cu care se realizează expresia;

Aceste criterii nu sunt însă suficiente pentru obţinerea unei reprezentări optimale

a funcţiilor prin scheme electrice.

Prin simplificarea (minimizarea) funcţiilor booleene se va întelege reducerea la

minimum a numărului variabilelor şi a simbolurilor de funcţii implicate în reprezentarea

unei funcţii booleene date.

Distingem două categorii de metode de simplificare:

- metode analitice, bazate pe calcule efectuate în expresia funcţiei booleene date

pe baza proprietăţilor algebrei booleene binare.

- metode grafice, bazate pe asocierea unor tabele sau a unor matrice de

combinaţii din care, prin grupări corespunzătoare, rezultă diverse reduceri.

47

Prin combinarea celor două categorii de metode rezultă aşa numitele metode

grafo-analitice.

3.4.1. Metode analitice (Quine McCluskey)

Metoda Quine McCluskey este o metodă analitică pentru simplificarea funcţiilor

booleene şi are la bază conceptul de implicant, alături de noţiunile prezentate anterior, de

minterm şi maxterm.

Pentru simplificarea scrierii, în cele ce urmează vom folosi pentru conjuncţie

simbolul “”, sau nimic, adică în loc de 11

x 2

2

x ... n

nx

vom scrie

11

x 2

2

x n

nx

... .

În continuare, prin simplificare vom înţelege procedeul de trecere de la o

expresie a unei funcţii booleene la o expresie cu un număr mai mic de apariţii ale

variabilelor.

Definiţia 4. i. Un produs de k variabile I = 11

y 2

2

y ..... k

ky

, unde yi 1{x , x2 , nx..., }

i k 1, se numeşte implicant al unităţii.

ii. Daca I f sau altfel spus I f (adică I = 1 implică f = 1 şi f = 0

implică I = 0), unde f : (B(2)) n B(2) este o funcţie booleană,

atunci I se numeşte implicant al funcţiei f.

Definiţia 5. Implicantul kk

yyyI

...22

11

al funcţiei f este un implicant prim al

acestei funcţii dacă şi numai dacă oricare ar fi I’ un produs obţinut din I

prin înlăturarea a cel puţin unei variabile, I’ nu mai este implicant al lui f

(adică dacă şi numai dacă I încetează să mai fie implicant al lui f de îndată

ce înlăturăm din el cel puţin o variabilă).

Observaţie: Implicanţii primi sunt minimali în sensul că au un număr minim de variabile, fapt

pentru care au un rol important în problema simplificării funcţiilor booleene.

Definiţia 6. Doi implicanţi I1 şi I2 care diferă prin forma unei singure variabile se

numesc vecini (adică p x şi px sunt vecini, unde p este un produs de

variabile sau negaţii ale lor altele decât variabila x).

Definiţia 7. Expresia (formula) unei funcţii booleene care este disjuncţia tuturor

implicanţilor săi primi se numeşte expresie (formulă) caracteristică.

Oricare altă expresie (formulă) care conţine numai implicanţi primi va fi

numită expresie (formulă) redusă, iar expresiile (formulele) care conţin

un număr minim de implicanţi primi se numesc expresii (formule)

minimale.

48

Simplificarea funcţiilor se realizează în două etape. În prima etapă se determină

expresia (formula) caracteristică; în cea de-a doua etapă se determină formulele minimale

pornind de la formula caracteristică. Pentru a distinge cele două etape prima se va numi

de simplificare iar cea de-a doua de minimizare.

Metoda Quine-McCluskey constă în efectuarea sistematică şi completă a

operaţiilor de compunere a vecinilor, adică a operaţiilor de forma: pxppx .

Fie m = {m1, m2,...,mm} mulţimea mintermilor ce intră în forma canonică

disjunctivă a funcţiei booleene f : (B(2))n B(2).

Fiecărui minterm nia

nxia

xia

xim ...22

11

îi asociem vectorul

),...,2

,1

(ni

aiaiaia şi numărul

n

jjiaiq

1

.

Fie A = {a1,a2,...,am}, Q = {q1, q2, ... ,qm}; fie P = {p1, p2, ..., pr} mulţimea

numerelor distincte din Q.

Fiecărui număr pi P îi asociem o submulţime Ai A în felul următor:

aj Ai qj = pi.

Se obţine astfel o partiţie a mulţimii A, A Aii

r

1

deoarece evident

Ai Aj = () ij.

Fiecare clasă Ai care compune partiţia are proprietatea că vectorii ce-i aparţin au

exact pi componente diferite de 0.

Două clase Ai şi Ak pentru care p pi k 1 se numesc vecine.

Constituenţii unităţii (mintermii) vecini se găsesc atunci în clase vecine, prin

urmare, în cazul folosirii unei metode de căutare a vecinilor, căutarea se reduce la

căutarea în două clase vecine deoarece doi vecini p x şi px au vectorii asociaţi ce

diferă prin valoarea unei singure componente, în timp ce doi vectori din aceeaşi clasă

diferă printr-un număr par de componente, iar doi vectori din două clase nevecine diferă

printr-un număr mai mare sau egal cu 2 de componente.

In aceste condiţii algoritmul de simplificare este următorul:

i. Se aduce funcţia booleană la FCD şi se determină mulţimea

m = {m1, m2,...,mm};

ii. fiecărui minterm mi , i n 1, i se asociază vectorul ai , i n 1, ;

iii. se determină q ai ijj

n

1

, i n 1, ;

iv. se ordonează vectorii ai în ordinea crescătoare a valorilor qi şi se

determină clasele Ai ;

v. se execută operaţia de compunere pentru toate perechile de implicanţi

vecini, comparând implicanţii din clasele vecine şi se marchează (eventual cu

liniuţă) variabilele care dispar prin compunere;

vi. din vechiul tabel se constituie un nou tabel în care sunt trecuţi toţi

vectorii care n-au intrat în nici o compunere precum şi vectorii rezultaţi din

compunere.

49

vii. dacă tabelul este ireductibil faţă de operaţia de compunere atunci

algoritmul se încheie, altfel se revine la pasul (v).

Observaţie: i. Un implicant poate intra în compunere cu mai mulţi implicanţi vecini (atât din

clasa vecină superioara cât şi din clasa vecină inferioară).

ii. La transcrierea formulei caracteristice din tabelul ireductibil se ţine cont că

fiecărui vector din tabel îi corespunde un implicant prim care se determină

prin realizarea conjuncţiei variabilelor ce au componenta corespunzătoare 1 şi

a negaţiilor variabilelor ce au componenta corespunzătoare 0; variabilele

cărora le corespunde o liniuţă în vector lipsesc.

Prezentăm în continuare etapa de minimizare a algoritmului Quine McCluskey.

Fie rPPPP ,,2,1 mulţimea implicanţilor primi ai funcţiei booleene

mmmmBBf ,,,m şi 22: 21

4 mulţimea minternilor ce dau forma canonică

disjunctivă a lui f .

Fiecărui constituent al unităţii im i se asociază un vector boolean

iraiaiaia ,,2,1 astfel încât

kpi

kpi

ika

m dacă , 0

m dacă , 1, rk ,1 şi suma

booleană r

kkPikaiS

1 .

Considerăm funcţia m

iiSrPPPF

1,,

2,

1 şi fie sQQQQ ,,2,1

mulţimea implicanţilor primi ai lui F , iar

t

tqPtPtPtP ,,2

,1 mulţimea

implicanţilor primi ai lui f care apar în sttQ ,1 , .

Teorema 3. Pentru orice t

q

j

tj

Pfst

1

expresia ,1

este o expresie (formulă)

minimală a funcţiei f.

Datorită acestei propoziţii, algoritmul de minimizare este următorul:

i. Se determină mulţimile mmmmm ,,2

,1

a mintermilor şi

mulţimea rPPPP ,,2,1 a implicanţilor primi;

ii. Se determină vectorii booleeni iraiaiaia ,,2,1 după regula

kpi

kpi

ika

m dacă , 0

m dacă , 1, rk ,1 , mi ,1 ;

iii. Se asociază mintermilor im sumele booleene r

kkPikaiS

1 ;

50

iv. Se construieşte funcţia m

kiSkPPPF

1,,2,1

şi se simplifică

obţinându-se mulţimea sQQQQ ,,2,1 a implicanţilor săi primi;

v. fiecărui stQtQ ,1 i se asociază submulţimea

t

tq

tt PPPtP ,,, 21 P astfel încât tjP apare în Qt , tqj ,1 ;

vi. expresiile tq

j

tjPf

1

sunt expresiile minimale ale lui f .

Observaţie:

i. Numărul total de expresii reduse ale funcţiei f este egal cu numărul de

implicanţi primi ai funcţiei F asociate.

ii. Din mulţimea tuturor expresiilor reduse ale aceleiaşi funcţii f se alege, în

funcţie de scopul urmărit, sau expresia care conţine un număr minim de implicanţi primi

sau expresia în care termenii disjuncţiei au un număr minim de variabile.

Algoritmul de minimizare prezentat mai sus poate fi substituit de construcţia unui

tabel (numit matricea implicantă) în care să se marcheze mintermii implicanţi ai fiecărui

implicant prim al funcţiei.

Tabelul este de forma:

mintermi

implicanţi primi

m1 m2 ... mm

P1 ...

P2 ...

Pn

şi din el se vor alege pentru expresia redusă a funcţiei acei implicanţi primi care acoperă

(in tabel) toţi mintermi, deci întreaga funcţie.

3.4.2 Metode grafice

Metodele grafice de simplificare a funcţiilor booleene se bazează pe reprezentarea

tabelară a funcţiilor booleene şi pe proprietatea de adiacenţă a codurilor binare (de

exemplu, a codului binar reflectate, numit şi codul Gray).

Reprezentarea numerelor într-un sistem de numeraţie este o codificare, fiecărui

număr corespunzându-i o combinaţie de cifre; în codul binar, cifrele utilizate pentru

reprezentarea numerelor vor fi 0 şi 1.

Metodele grafice de simplificare utilizează esenţial reprezentarea tabelară a

funcţiilor booleene. Reprezentări grafice tabelare posibile pentru funcţiile de două, trei şi

respectiv patru variabile sunt:

51

x2

x1

0 1

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

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

x2x3

x1

00 01 10 11

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

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

x3x4

x1x2

00 01 10 11

00 f (0, 0, 0, 0) f (0, 0, 0, 1) f (0, 0, 1, 0) f (0, 0, 1, 1)

01 f (0, 1, 0, 0) f (0, 1, 0, 1) f (0, 1, 1, 0) f (0, 1, 1, 1)

10 f (1, 0, 0, 0) f (1, 0, 0, 1) f (1, 0, 1, 0) f (1, 0, 1, 1)

11 f (1, 1, 0, 0) f (1, 1, 0, 1) f (1, 1, 1, 0) f (1, 1, 1, 1)

3.4.2.1. Diagrame Veitch

O posibilă reprezentare tabelară o constituie diagramele Veitch. Acestea pun în

evidenţă mintermi (maxtermi) ce apar în FCD (FCC) corespunzătoare funcţiei. Modelele

acestor diagrame pentru funcţii de două, trei şi respectiv patru variabile, sunt:

x2 x2 x2 x2

x1

x1 x2

(1, 1) x1x2

(1, 0)

x1

x1 x2

(1, 1)

x1 x2

(1, 0)

x1 x1 x2

(0, 1)

x1x2

(0, 0)

x1 x1 x2

(0, 1)

x1 x2

(0, 0)

pentru mintermii de două variabile pentru maxtermii de două variabile

x 2 x2

x1 x1 x2x3

(1, 1, 0)

x1 x2 x3

(1, 1, 1) x1x2 x3

(1, 0, 1)

x1x2x3

(1, 0, 0)

x1 x1 x2x3

(0, 1, 0)

x1 x2 x3

(0, 1, 1)

x1x2 x3

(0, 0, 1)

x1x2x3

(0, 0, 0)

x3 x 3 x3

pentru mintermii de trei variabile

x2 x 2

x1 x1 x2 x3

(1, 1, 0)

x1 x2 x3

(1, 1, 1)

x1 x2 x3

(1, 0, 1)

x1 x2 x3

(1, 0, 0)

52

x1 x1 x2 x3

(0, 1, 0)

x1 x2 x3

(0, 1, 1)

x1 x2 x3

(0, 0, 1)

x1 x2 x3

(0, 0, 0)

x3 x3 x 3

pentru maxtermii de trei variabile

x2 x2 x2 x2

x4 x4 x1

x1

x4

x4

x1

x4

x1

x4

x3 x3 x3 x3 x3 x3

pentru mintermii de patru variabile pentru maxtermii de patru variabile

3.4.2.2. Diagrame Karnaugh

Mult mai eficientă este utilizarea de diagrame Karnaugh pentru reprezentarea

tabelară a funcţiilor booleene care este conformă cu codul binar reflectat. Specificul

acestor diagrame constă în atribuirea de valori din mulţimea {0,1} variabilelor de pe linia

şi respectiv coloana tabelului astfel încât combinaţiile ce se realizează să fie vecine două

câte două. Astfel, diagramele Karnaugh pentru funcţii de două, trei şi respectiv patru

variabile sunt:

x2

x1

0 1

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

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

x2x3

x1

00 01 11 10

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

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

x3x4

x1x2

00 01 11 10

00 f (0, 0, 0, 0) f (0, 0, 0, 1) f (0, 0, 1, 1) f (0, 0, 1, 0)

01 f (0, 1, 0, 0) f (0, 1, 0, 1) f (0, 1, 1, 1) f (0, 1, 1, 0)

11 f (1, 1, 0, 0) f (1, 1, 0, 1) f (1, 1, 1, 1) f (1, 1, 1, 0)

10 f (1, 0, 0, 0) f (1, 0, 0, 1) f (1, 0, 1, 1) f (1, 0, 1, 0)

Exemplu:

Să se simplifice următoarea funcţie booleeană:

53

f :(B(2))3 B(2), f(x1,x2,x3) = x1 x2 x1x2 x3 x1x2 x1 x2x3 .

Pentru construirea diagramei Veitch funcţia trebuie pusă sub forma canonică

disjunctivă:

f(x1, x2, x3) = (x1 x2 (x3 x3)) (x1x2 (x3 x3)) x1x2x3 x1 x2 x3 =

= x1 x2 x3 x1x2x3 x1x2 x3 x1 x2x3 x1 x2 x3 x1 x2x3 .

Atunci diagrama Veitch asociată este de forma:

x2 x2

x1 1 1 1 0

x1 1 0 1 1

x3 x3 x3

Punând în evidentă toate asocierile maximale posibile de celule limitrofe se

deduce formula caracteristică a funcţiei:

f(x1, x2, x3)= x1 x2 x2 x3 x1x3 x2x3 x1 x3 x1x2,

obţinută prin disjuncţia tuturor implicanţilor primi.

Tot din modul de realizare a asocierilor rezultă două formule reduse ale aceleiaşi

funcţii:

f(x1, x2, x3) = x2x3 x1 x3 x1x2 ,

f(x1, x2, x3) = x1x3 x1 x2 x2 x3.

Pentru simplificarea funcţiilor booleene de 5 sau 6 variabile metodele grafice

utilizează diagrame spaţiale a căror construcţie va fi descrisă mai jos. Simplificarea

funcţiilor de mai mult de 6 variabile ar trebui să utilizeze diagrame “rep rezentate grafic”

în patru dimensiuni. Nemaiputând face efectiv o astfel de reprezentare metodele grafice

îşi pierd utilitatea imediată, dar nu excludem posibilitatea generalizării procedeului de

simplificare bazat pe diagramele Veitch-Karnaugh.

Pentru prezentarea mai clară a extinderii principiilor de simplificare grafică de la

cazul n = 4 la cazurile n = 5 şi n = 6, reprezentăm cele două respectiv patru “nivele” ale

unei diagrame tridimensionale în plan, în figurile 3 şi 4.

x2 x2 x2 x2

x4 x4 x1

x1

x4

x4

x

1 x4

x

1 x4

x3 x3 x3

x3 x3 x3

x5 x5

Figura 3.

I x2 x2 II x2 x2

54

x4 x4 x1

x1

x4

x4

x5

x

1 x4

x1

x4

x3 x3 x3

x3 x3 x3

IV x2 x2 III x2 x2

x4 x4 x1

x1

x4

x4

x5

x

1 x4

x1

x4

x3 x3 x3

x3

x3 x3

x6 x6

Figura 4.

Observaţie: Suprapunerea celor patru “nivele” ale diagramei corespunzătoare cazului n = 6

trebuie făcută respectând ordinea I, II, III, IV sau o permutare circulară a acesteia.

Modul în care au fost “grupate” diagramele păstrează proprietatea de a

corespunde unor combinaţii adiacente oricare două celule alăturate în plan orizontal sau

pe verticală.

3.5 Funcţii booleene incomplet definite

Definiţia 9. O funcţie booleană 22: Bn

Bf pentru care o parte a coeficienţilor

formelor canonice nu sunt definiţi se numesc funcţii incomplet definite

sau simplu funcţii incomplete.

Observaţie: În aplicaţiile practice apar deseori funcţii incomplete. Se consideră atunci că

aceşti coeficienţi nedefiniţi pot lua valori arbitrare 0 sau 1.

Se notează cu 22:0

Bn

Bf şi respectiv 22:1

Bn

Bf funcţiile

booleene obţinute din 22: Bn

Bf înlocuind cu 0 şi respectiv 1 toţi coeficienţii

nedefiniţi. Vom avea atunci

nxxxfnxxxf ,..,2

,11

,..,2

,10

, nBnxxx 2,..,2

,1

şi vom nota 10 ff , prin urmare considerăm relaţia de ordine parţiala indusă de

implicaţie.

Orice funcţie 22: Bn

Bg cu proprietatea că 10

fgf poate fi obţinută

din funcţia incompletă f prin particularizarea coeficienţilor nedefiniţi.

55

Vom nota în continuare funcţia incompletă f prin perechea 1

,0

ff formată din

marginea inferioară f 0 şi marginea superioară f1 a sa.

10

22:1

,0

fgfBn

Bgfff

Propoziţia 2. Fie f o funcţie booleana incompletă, 1

,0

fff .

Atunci 10

fgf implică 01

fgf şi *0

**1

fgf .

Datorită acestei propoziţii are sens urmatoarea definiţie:

Definiţia 10. Funcţia booleană incompletă 0

,1

fff se numeşte funcţie

incompletă inversă a funcţiei incomplete f f f 0 1, , iar funcţia

booleană incompletă *0

,*1

* fff se numeşte funcţia incompletă

duală a funcţiei incomplete 1

,0

fff .

Observaţie:

Mulţimea funcţiilor booleene incomplete este definită de mulţimea perechilor de

funcţii booleene comparabile în raport cu relaţia de implicaţie.

Notăm 22: Bn

BffB

F mulţimea funcţiilor booleene de n variabile

booleene şi 10

:'1

,0

fgfB

FgfB

FfffiB

F .

Observaţie: iB

FB

F deoarece orice funcţie booleană poate fi interpretată ca o funcţie

booleană incompletă cu f f f , , f f .

Teorema 4. Mulţimea B

F a funcţiilor booleene poate fi organizată ca latice cu ajutorul

relaţiei de ordine parţială indusă de implicaţie.

Teorema 5. Mulţimea iB

F a funcţiilor booleene incomplete poate fi organizată ca

semilatice în raport cu relaţia de ordine parţială următoare:

(f0, f1) (g0, g1) (g0 f0 şi f1 g1)

Observaţie: Semilaticea funcţiilor booleene incomplete admite ca ultim element pe (0,1), deci

funcţia incompletă nedefinită în nici un argument.

Într-adevăr () f = (f0,f1) iB

F implică 0 f0 f1 1. Rezultă (f0,f1) (0, 1).

3.6 Funcţia inversă şi funcţia duală a unei funcţii booleene

Definiţia 11. Dată fiind funcţia booleeană f Bn

B:( ( )) ( )2 2 se numeşte funcţie

booleană inversă ataşată lui f, funcţia F Bn

B:( ( )) ( )2 2 care satisface relaţiile:

56

0),...,2

,1

(),...,2

,1

(

1),...,2

,1

(),...,2

,1

(

nxxxF

nxxxf

nxxxF

nxxxf

( ) ),...,2

,1

(n

xxx ( ( ))Bn

2 .

Definiţia 12. Se numeşte funcţie duală a funcţiei booleene f Bn

:( ( ))2 B(2) funcţia

booleana f B Bn*

:( ( )) ( )2 2 obţinută prin aplicarea principiului

dualităţii formelor normale conjunctive sau disjunctive ale lui f,

adică:

f ( ,..., ),x x xn1 2

=

nBn

))2((),...,2

,1

(

(f ),...,1

(n

1

x 2

x ... nx

)

implică

f*

( ,..., ),x x xn1 2

=

nBn

))2((),...,1

(

f( ),...,1

(n

1

x 2

x ... nx

)

respectiv

f ( ,..., ),x x xn1 2

=

nBn

))2((),...,2

,1

(

(f ),...,1

(n

11x 22

x ... nnx )

implică

f*

( ,..., ),x x xn1 2

=

nBn

))2((),...,1

(

( f ),...,1

(n

11x 22

x ... nnx )

Observaţie:

Între funcţia duală şi funcţia inversă ale unei funcţi booleene există relaţia:

f*

( ,..., ),x x xn1 2

= f (1

x ,2

x ,…,n

x ).

3.8. Structuri Reed-Muller

Pentru studiul design-ului şi implementării circuitelor de comutaţie (switching

circuits) de obicei se utilizează operaţiile algebrei booleene.

În ultimii ani s-a conturat o altă modalitate de descriere bazată pe operaţiile

modulo-2 ale algebrei claselor de resturi modulo-2, operaţii uşor adaptabile

implementării pe calculator.

Operaţiile de bază ale algebrei modulo-2, pe care o vom nota GF(2), sunt

adunarea modulo-2 şi înmulţirea modulo-2, elementele acesteia fiind întregii modulo-2,

adică cifrele 0 şi 1, deci GF(2) = {0,1}.

Dăm în continuare tabelele celor două operaţii:

a b 0 1 a b 0 1

57

0 0 1 0 0 0

1 1 0 1 0 1

Adunarea modulo-2 Înmultirea modulo-2

Se remarcă faptul că adunarea modulo-2 este identică cu operaţia din algebra

booleana “sau-exclusiv” (EOR), iar înmulţirea modulo-2, cu operaţia “şi” din algebra

booleană.

a b a b a b a b

0 0 0 0 0 0

0 1 1 0 1 0

1 0 1 1 0 0

1 1 0 1 1 1

Operaţia “sau-exclusiv” Operaţia “şi”

Singura diferenţa între descrierea în algebra modulo-2 şi cea în algebra booleană

e aceea dintre “sau-exclusiv” şi “sau-inclusiv”; în timp ce 1+1=1 în algebra booleană,

11=0 în algebra modulo-2.

Această diferenţă, aparent nesemnificativă, conduce la diferenţe mari în metodele

design-ului şi implementării.

Cerinţele de bază ale oricărei structuri (algebre) care urmăreşte să descrie şi să

opereze cu circuite de comutaţie sunt următoarele:

- să fie complet funcţională; să permită o reprezentare algebrică distinctă pentru

fiecare funcţie posibilă de un număr dat de variabile;

- să fie flexibilă; să permită maleabilitate în funcţionare astfel ca algoritmii

design-ului să poată fi realizaţi şi folosiţi cu uşurinţă;

- să fie realizabilă; operaţiile de bază şi orice alte operaţii funcţionale de înalt

nivel să aibă corespondente fizice în circuitele de comutaţie.

Se pot extinde conceptele introduse în algebra modulo-2 la algebrele modulo-p,

cu p întreg prim. În cazul p neprim, algebra corespunzătoare nu este complet funcţională.

Este posibil ca algebrele notate GF(q), unde q reprezintă numărul valorilor, şi q

este prim sau putere a unui număr prim q = pk, p-prim, să aibă proprietăţi de

funcţionalitate completă.

3.8.1. Algebra (GF(2), , )

Dacă a, b şi c sunt variabile bivalente şi şi reprezintă adunarea, respectiv

înmulţirea modulo-2, rezultă următoarele proprietăţi:

i. închidere a b şi a b sunt tot bivalente;

ii. asociativitate a (b c) = (a b) c = a b c;

a (b c) = (a b) c = a b c;

iii. comutativitate a b = b a; a b = b a;

58

iv. distributivitate a (b c) = a b a c;

v. a 0 = a; a 1 = a;

vi. a a = 0.

Rezultă că:

a b = a b

a b = a b a b

1 aa

sunt operaţiile ce conferă mulţimii GF(2) structură de algebră booleană.

Stabilim în continuare forma generală a expresiilor algebrice. În cele ce urmează

nu vom face distincţie între înmulţirea modulo-2 şi “şi” boolean şi vom folosi acelaşi

simbol (juxtapunerea).

3.8.2. Expresii Reed – Muller

Expresia booleană standard, de o variabilă, are forma

f(x1)= 1110 xdxd ,

unde di = 0 sau 1 (i = 0, 1) sunt valorile funcţiei. Din formulele de Morgan rezulta:

f(x1)= d x d x0 1 1 1 .

Prin urmare

f(x1)=d0(x1 1) 1)(d1x1 1) 1) =

=((d0x1 d0) 1)(d1x1 1) 1 =

=d0d1x1 d0d1x1 d1x1 d0x1 d0 =

=d0 (d0 d1)x1

f(x1)=c0 c1x1 peste GF(2), unde ci = 0 sau 1.

Coeficienţii acestei noi expresii se pot exprima în funcţie de coeficienţii din forma

iniţială utilizând matricea transformării modulo-2:

c

c

d

d

0

1

0

1

1 0

1 1

peste GF(2)

deoarece

c0 = d0

c1 = d0 d1 = 0110 dddd

Simbolic, putem scrie:

c = T1 d

şi se poate extinde acest concept la funcţiile de mai multe variabile.

În cazul n = 2, variabilele fiind x1 şi x2 forma normală canonică disjunctivă este:

f(x2,x1) = d0m0 d1m1 d2m2 d3m3

Deoarece mimj = 0 pentru ij (doi mintermi sunt mutual exclusivi), deci nu pot fi

simultan egali cu 1, se poate înlocui suma logică (“sau-inclusiv”) cu suma modulo-2

(“sau-exclusiv”), fără a altera validitatea expresiei. Avem, deci:

f(x2,x1) = d0m0 d1m1 d2m2 d3m3 =

59

= d x x d x x d x x d x x0 2 1 1 2 1 2 1 2 3 2 1

= d0(x2 1)(x1 1) d1(x2 1)x1 d2(x1 1)x2 d3x2x1=

= d0 (d0 d1)x1 (d0 d2)x2 (d0 d1 d2 d3)x2x1

Deci

f(x2,x1) = c0 c1x1 c2x2 c3x2x1 peste GF(2)

unde

c d

c d d

c d d

c d d d d

0 0

1 0 1

2 0 2

3 0 1 2 3

adică

3

2

1

0

3

2

1

0

1111

0101

0011

0001

d

d

d

d

c

c

c

c

sau

c = T2 d peste GF(2).

Matricea transformării T2 poate fi exprimată astfel în funcţie de T1:

T2 = T

T T

1

1 1

0

.

În general, în cazul a n-variabile, matricea transformării Tn se poate exprima

recursiv astfel:

Tn =T

T T

n

n n

1

1 1

0, pentru n>0 şi T0 = (1) peste GF(2).

Forma generală (în cazul a n-variabile) a funcţiei (şi respectiv a expresiei care o

defineşte) este:

f(xn, xn-1,...x1) =c0 c1x1 c2x2 c3x2x1 c4x3 c5x3x1 … 12 nc xnxn-1...x1

peste GF(2) sau

f(xn,xn-1,...,x1)= c x x xi n n

i

i n i n i

n

, , ,...

1 1

0

2 1

1 1 ,

unde suma este suma peste GF(2), deci , iar i,j sunt 0 sau 1 astfel încât

x x xk k k

0 11 , .

Expresia ce defineşte funcţia f este o sumă de produse modulo-2, cunoscută sub

denumirea de expresie Reed-Muller.

În această expresie avem 2n termeni posibili. Termenii se numesc deseori -

termi (sau pitermi) şi sunt notaţi prin i.

Indicele i al pitermului i este echivalentul zecimal al numărului binar format prin

concatenarea cantităţilor i,n,i,n-1,...,i,1, unde i,1 este luat ca bitul cel mai puţin

semnificativ, deci

i(10 )= i,ni,n-1...i,2i,1 (2) .

60

Astfel:

x x x x x x x x x6 3 1 6

1

5

0

4

0

3

1

2

0

1

1 37

şi

23 = x x x x x x x x x5

1

4

0

3

1

2

1

1

1

5 3 2 1 .

Observăm că:

x i i

2 1

şi 0 = 1.

Cu acestea, notaţia prescurtată a expresiilor Reed-Muller (expresiilor RM) este:

f(xn,xn-1,...,x1) = c i i

i

n

0

2 1

,

peste GF(2).

3.10 Rezumat

Funcţiile booleene sunt funcţii definite pe o structură de algebră booleană binară

(au valori de intrare/ieşire 0 şi 1). Funcţiile booleene pot fi descrise print tabele de adevăr

(precizând valoarea de ieşire pentru fiecare combinaţie posibilă de valori de intrare) sau

prin expresii algebrice ce utilizează operatorii algebrei booleene care acţionează asupra

operanzilor variabile booleene.

Din multitudinea expresiilor algebrice posibile de descriere a unei funcţii

booleene se evidenţiază: formele canonice (pentru asigurarea unei unicităţi de

reprezentare, obţinute pe baza formulelor de interpolare Lagrange), formele

caracteristice (obţinute prin disjuncţia implicanţilor primi), formele minimale

(obţinute prin selectarea unui număr minim de implicanţi primi suficienţi pentru

descrierea corectă a funcţiei).

Funcţiile booleene speciale care intervin în scrierea formelor canonice

disjunctive/conjunctive sunt mintermii (constituenţi ai unităţii, luând valoarea 1 pentru

o singură combinaţie de intrare) şi repsectiv maxtermii (constituenţi ai nulului, luând

valoarea 0 pentru o singură combinaţie de intrare).

Seturi speciale de funcţii booleene sunt sistemele complete de funcţii booleene,

seturi de operatori necesari şi suficienţi pentru a descrie algebric orice funcţie booleană.

Perechile disjuncţie-negaţie, conjuncţie-negaţie şi adunare-înmultire modulo 2 sunt

exemple de sisteme complete de funcţii booleene.

Pentru obţinerea formelor minimale pentru funcţiile booleene se poate face apel la

metoda analitică de simplificare (Quine McCluskey) sau la metodele grafice de

simplificare (diagramele Veitch-Karnaugh).

Funcţia inversă a unei funcţii booleene se obţine prin aplicarea negaţiei iar

funcţia duală prin aplicarea principiului dualităţii uneia dintre formele canonice ale

funcţiei iniţiale. Fiecare dintre acestea e complet determinată de funcţia iniţială şi

reciproc şi de aceea, în practică, se va folosi cea mai simplă dintre expresii.

O funcţie booleană pentru care o parte a coeficienţilor formelor canonice nu sunt

definiţi se numeşte funcţie incomplet definită. Atribuind diverse combinaţii de valori

coeficienţilor nedefiniţi se obţin diverse funcţii booleene ataşate funcţiei incomplet

definite. Pentru construcţia circuitului de comutaţie asociat funcţiei incomplet definite

se va folosi forma minimală cea mai avantajoasă din setul de forme minimale

corespunzătoare funcţiilor ataşate.

61

Funcţiile booleene de variabile polivalente se tratează prin intermediul

funcţiilor booleene de variabile booleene explicitându-se fiecare variabila multivalentă cu

ajutorul variabilelor bivalente.

Structura Reed-Muller (inelul boolean al claselor de resturi moduo 2) este

adesea utilizată, alaturi de algebra booleană, pentru studiul proiectării şi implementării

circuitelor de comutaţie. Pentru a se stabili legături între coeficienţii formelor canonice

ale funcţiilor din algebra booleană şi coeficienţii pitermilor din expresiile Reed-Muller,

concepte de matrice, transformare, polinom au semnificaţii bine precizate. Pentru

realizarea transformărilor de coeficienţi se pot utiliza matricele de transformare definite

recursiv folosind produsul Kronecker sau triunghiul lui Pascal.

Expresii Reed-Muller generalizate pot fi deasemenea asociate funcţiilor

booleene pentru a se obţine, cu ajutorul aceloraşi operatori modulo 2 combinaţi cu negaţii

aplicate asupra anumitor variabile (stabilite prin numărul de polaritate), expresii cu cost

scăzut de construcţie a circuitului combinaţional asociat.

Circuitele elementare de construcţie a circuitelor combinaţionale sunt circuitele

poartă (care efectuează una dintre operaţiile logice de disjuncţie, conjuncţie, negaţie,

sau-exclusiv). Sumatorul binar cu o poziţie şi sumatorul binar cu n poziţii sunt două

exemple reprezentative de implementare fizică a funcţiilor booleene.

62

Test de autoevaluare1 (Verificaţi-vă cunoştinţele!) Perseveraţi pentru a obţine soluţiile date în finalul testului!

1. Să se realizeze următoarele conversii:

a) 23.375 (10) = _______________________ (2)

b) 10110110 (2) = _______________________ (16)

c) 0.09375 (10) = _______________________ (2)

d) 34.625 (10) = _______________________ (2)

e) 213 (16) = _______________________ (10)

f) FA5(16) = _______________________ (10)

g) 378 (9) = _______________________ (12)

h) 2000 (3) = _______________________ (10)

i) 10(6) = _______________________ (5)

2. Să se determine secvenţele de cod direct, invers şi complementar,

reprezentate pe

n = 8 poziţii, pentru următoarele numere întregi:

a) 47, b) -27, c) 125, d) -129, e)-66, f) -65.

3. Să se determine echivalentul zecimal al secvenţei de cod complementar

de mai jos:

a) 10011, b) 110000, c) 001011, d) 0000000, e)

110011001

4. Să se determine echivalentul zecimal al secvenţei de cod invers de mai

jos:

a) 10011, b) 110000, c) 001011, d) 0000000, e)

110011001

5. Să se realizeze adunarea în cod complementar şi în cod invers pentru

numerele de mai jos. Să se interpreteze rezultatul. (reprezentările se

vor face pe n = 5 poziţii)

a) - 15 b) - 7 c)

+13

+ 7 -13 -

12

6. Să se reprezinte în virgula mobilă, utilizând forma normalizată stabilită

în funcţie de puterile lui 16, numerele:

a) -31.625, b) 0.0025, c) 256.125

63

7. Să se reprezinte în standardul IEEE P754, simplă precizie, următoarele

numere:

a) +1.101 25

b) -1.01011 2-126

c) +1.0 2127

d) +0

e) -0

f) +2-128

g) +NAN

8. Să se determine numărul scris în baza 10 care are următoarea formă de

reprezentare în formatul standardului IEEE P754:

a) 0 10000011 01100000000000000000000

b) 1 10000000 00000000000000000000000

c) 1 00000000 00000000000000000000000

d) 1 11111111 00000000000000000000000

e) 0 11111111 11010000000000000000000

f) 0 00000001 10010000000000000000000

g) 0 00000011 01101000000000000000000

h) 0 00000000 10000000000000000000000

9. Utilizând standardul de reprezentare în virgulă mobilă IEEE P754, să se

reprezinte:

a) cel mai mare număr pozitiv reprezentabil în format (notă: + nu

este număr),

b) cel mai mic număr strict pozitiv reprezentabil în format,

c) cel mai mic număr strict pozitiv, reprezentabil în forma

nenormalizată.

Soluţii (Test de evaluare ):

1.

a) 10111.011(2)

b) B6 (16)

c) 0.00011(2)

d) 100010.101(2)

e) 531(10)

f) 4005(10)

g) 222(12)

h) 54(10)

i) 31(5)

64

2. a) D 00101111 b) 10011011 c)

01111101

I 00101111 11100100

01111101

C 00101111 11100101

01111101

d) nu poate fi e) 11000010 f)

11000001

reprezentat 10111101

10111110

10111110

10111111

3. a) –13 b) –16 c) 11 d) 0 e) -103

4. a) –12 b) –15 c) 11 d) 0 e) –102

5. a) –8 b) C 12 eroare de depasire c) 1

I 11 eroare de depasire

6. a) -1F.A(16)

11000010000111110100000000000000

b) 0.00A3D7(16)

00111110101000111101011100001010

c) 100.2(16)

01000011000100000000001000000000

7. a) 0 10000100 10100000000000000000000

b) 1 00000001 01011000000000000000000

c) 0 11111110 00000000000000000000000

d) 0 00000000 00000000000000000000000

e) 1 00000000 00000000000000000000000

f) 0 00000000 10000000000000000000000

g) 0 11111111 01101110000000000000000

8. a) +1.01124 b) -12

1 c)-0 d) -

e) +NAN

f) 1.10012-126

g) 1.011012-124

h) 0.12-127

9. a) 01111111011111111111111111111111

b) 00000000010000000000000000000000 = 2-128

c) 00000000100000000000000000000000 = 2-126

65

Test de autoevaluare2 (Verificaţi-vă cunoştinţele!)

Perseveraţi pentru a obţine soluţiile date în finalul testului!

1. Precizaţi care este numărul elementelor unui inel boolean? Motivaţi

răspunsul.

2. Prezentaţi tablele operaţiilor structurilor Post în cazuri le q = 4 si q = 5.

3. Care dintre urmăoarele afirmaţii sunt adevărate?

a). Algebra booleană (B(2), , , ) este echivalentă cu structura Post

(P(2), +, , ‘);

b). Algebra booleană (B(4), , , ) este echivalentă cu structura Post

(P(4), +, , ‘).

Motivaţi răspunsul.

4. Dacă A şi B sunt propoziţii, care dintre următoarele formule sunt

echivalente?

a). AB; b). (AB)(BA); c). (A B); d). (AB)(AB);

e). AB).

5. Simplificaţi următoarele funcţii booleene:

). 3212132121321 ),,( xxxxxxxxxxxxxf .

.

),,,().

4321

432143214321432143214321

43214321432143214321

xxxx

xxxxxxxxxxxxxxxxxxxxxxxx

xxxxxxxxxxxxxxxxxxxxf

utilizând:

a). metoda implicanţilor primi;

b). diagrame Veitch;

c). diagrame Karnaugh.

6. Pentru funcţia booleană f : B(2)3B(2), definită tabelar mai jos:

X1 X2 X3 f

0 0 0 1

0 0 1 1

0 1 0 1

0 1 1 0

1 0 0 0

1 0 1 1

1 1 0 0

1 1 1 1

să se determine:

a) forma canonică disjunctivă,

b) forma canonică conjunctivă,

c) forma caracteristică,

d) forma minimală (formele minimale),

e) expresia Reed-Muller asociată,

66

7. Să se determine expresiile algebrice pentru funcţiile f, g : P(3)2P(3),

definite mai jos, unde P(3) are o structură Post de dimensiune 3. Să se deducă şi formele

simplificate, utilizând diagramele Karnaugh ternare.

X1 X2 f g

0 0 2 1

0 1 2 0

0 2 1 2

1 0 0 1

1 1 0 0

1 2 1 2

2 0 0 1

2 1 2 1

2 2 1 2

8. Prezentaţi tablele operaţiilor structurilor Galois (GF(4), , ) şi

(GF(5), , ) şi precizaţi care dintre aceste structuri se bucură de proprietatea de

completă funcţionalitate.

Răspunsuri:

1. n2 elemente, unde n este numărul atomilor săi (vezi legătura dintre algebra

booleană şi inelul boolean).

2. .4q

x 'x ''x '''x ''''

x

0 1 2 3 0

1 2 3 0 1

2 3 0 1 2

3 0 1 2 3

.5q

+ 0 1 2 3 4

0 0 1 2 3 4

1 1 1 2 3 4

2 2 2 2 3 4

3 3 3 3 3 4

4 4 4 4 4 4

0 1 2 3 4

0 0 0 0 0 0

1 0 1 1 1 1

2 0 1 2 2 2

3 0 1 2 3 3

4 0 1 2 3 4

67

x 'x ''x '''x ''''

x '''''x

0 1 2 3 4 0

1 2 3 4 0 1

2 3 4 0 1 2

3 4 0 1 2 3

4 0 1 2 3 4

3. a). este adevărată deoarece cele trei operaţii ( _,, ) coincid cu operaţiile

)',,( .

b). nu este adevărată deoarece cele trei operaţii ( _,, ) nu coincid cu operaţiile

)',,( .

4. a). ~ b). ~d), c) ~e).

5. ). Formulele minimale sunt:

213132321 ),,( xxxxxxxxxf şi .),,( 322131321 xxxxxxxxxf

). Formula redusă a funcţiei este unică şi are forma:

4342324131214321 ),,,( xxxxxxxxxxxxxxxxf .

6.

a). 321321321321321321 ),,( xxxxxxxxxxxxxxxxxxf .

b). ))()((),,( 321321321321 xxxxxxxxxxxxf .

c). 321321313221321 ),,( xxxxxxxxxxxxxxxf .

d). 321313221321 ),,( xxxxxxxxxxxxf .

e). dTccxxxf i

i

i 3

7

0

123 ;),,(

.

7. Expresia funcţiei f rezultă din diagrama asociată acesteia:

0 1 2

0 2 0 0

1 2 0 2

2 1 1 1

+ 0 1 2 3 4 5

0 0 1 2 3 4 5

1 1 1 2 3 4 5

2 2 2 2 3 4 5

3 3 3 3 3 4 5

4 4 4 4 4 4 5

5 5 5 5 5 5 5

0 1 2 3 4 5

0 0 0 0 0 0 0

1 0 1 1 1 1 1

2 0 1 2 2 2 2

3 0 1 2 3 3 3

4 0 1 2 3 4 4

5 0 1 2 3 4 5

68

aceasta este: m0+m3+m5+1.m6+1.m7+1.m8 .

Forma simplificată este:

1.j2(x2)+1.j0(x1)+m0+m3+ m5 = 1.j2(x2)+1.j0(x1)+j0(x2)j0(x1)+j1(x2)j0(x1)+

+j1(x2)j2(x1).

Expresia funcţiei g rezultă din diagrama asociată acesteia:

0 1 2

0 1 1 1

1 0 0 1

2 2 2 2

aceasta este: 1.m0+1.m1+ 1.m2+1.m5+m6+m7+m8 .

Forma simplificată este:

1.j0(x2)+1.j1(x2)j2(x1)+j2(x2).

8.

(GF(4), , ) nu este structură complet funcţională.

(GF(5), , ) este structură complet funcţională.

0 1 2 3

0 0 1 2 3

1 1 2 3 0

2 2 3 0 1

3 3 0 1 2

0 1 2 3

0 0 0 0 0

1 0 1 2 3

2 0 2 0 2

3 0 3 2 1

0 1 2 3 4

0 0 1 2 3 4

1 1 2 3 4 0

2 2 3 4 0 1

3 3 4 0 1 2

4 4 0 1 2 3

0 1 2 3 4

0 0 0 0 0 0

1 0 1 2 3 4

2 0 2 4 1 3

3 0 3 1 4 2

4 0 4 3 2 1

69

Universitatea Transilvania Braşov

Facultatea de Matematică şi Informatică

Catedra de Informatică Teoretică

Învăţământ la Distanţă

Tema de control (1) Disciplina: Logică Computaţională

1. Să se realizeze următoarele conversii:

a) 423.75 (10) = _______________________ (2)

b) 10110110111(2) = _______________________ (16)

c) 0.0009375 (10) = _______________________ (2)

d) 234.1625 (10) = _______________________ (2)

e) 213A(16) = _______________________ (10)

f) FA5CD(16) = _______________________ (10)

g) 31278 (9) = _______________________ (12)

h) 200011 (3) = _______________________ (10)

i) 12345(6) = _______________________ (5)

2. Să se determine secvenţele de cod direct, invers şi complementar,

reprezentate pe n = 10 poziţii, pentru următoarele numere întregi:

a) 147, b) -57, c) 125, d) -100 e)-77, f) -95.

3. Să se determine echivalentul zecimal al secvenţei de cod complementar

de mai jos:

a) 1110011, b) 11100000, c) 001110011, d) 000000011,

e) 110011001

4. Să se determine echivalentul zecimal al secvenţei de cod invers de mai

jos:

a). 1110011, b). 11100000, c). 001110011, d). 000000011,

e) 110011001

5. Să se realizeze adunarea în cod complementar şi în cod invers pentru

numerele de mai jos. Să se interpreteze rezultatul. (reprezentările se

vor face pe n = 5 poziţii)

a). - 17 b). - 8 c). +17

+ 5 -15 - 14

70

6. Să se reprezinte în virgula mobilă, utilizând forma normalizată stabilită

în funcţie de puterile lui 16, numerele:

a). -231.625, b). 0.0025375, c). 2560.125

7. Să se reprezinte în standardul IEEE P754, simplă precizie, următoarele

numere:

a) +12345(10)

b) -111.01011 2-12

c) +145.012 2120

d) +0.375

e) –0.1234

f) +2-127

g) -NAN

8. Să se determine numărul scris în baza 10 care are următoarea formă de

reprezentare în formatul standardului IEEE P754:

a) 0 11110000 01101100000000000000001

b) 1 10000000 11000000000000000000000

c) 1 00000001 00000000000000000000000

d) 1 11111111 10000000000000000000000

e) 0 11111111 11010000000000000000000

f) 0 00000111 10011100000000000000000

g) 0 00000111 01101000000000000000000

h) 1 00000111 11100000000000000000000

9. Utilizând standardul de reprezentare în virgulă mobilă IEEE P754, să se

reprezinte:

a) + şi -,

b) cel mai mare număr întreg reprezentabil în format,

c) cel mai mic număr înreg reprezentabil în format.

71

Universitatea Transilvania Braşov

Facultatea de Matematică şi Informatică

Catedra de Informatică Teoretică

Învăţământ la Distanţă

Tema de control (2) Disciplina: Logică Computaţională

1. Care este numărul mintermilor, numărul maxtermilor şi numărul piter milor,

pentru o funcţie booleană de n variabile? Motivaţi răspunsul.

2. Prezentaţi tablele operaţiilor structurilor Post în cazurile q = 7 si q = 8.

3. Care sunt asemănările şi deosebirile dintre structura de algebră booleană

(B(n), , , ) şi structura Post (P(n), +, , ‘), pentru diverse valori ale lui *Nn ?

4. Prezentaţi 4 perechi de formula echivalente în algebra propoziţiilor

5. Simplificaţi următoarele funcţii booleene:

). 3213212132121321 ),,( xxxxxxxxxxxxxxxxf .

.

),,,().

432143214321

432143214321432143214321

43214321432143214321

xxxxxxxxxxxx

xxxxxxxxxxxxxxxxxxxxxxxx

xxxxxxxxxxxxxxxxxxxxf

utilizând:

a). metoda implicanţilor primi;

b). diagrame Veitch;

c). diagrame Karnaugh.

6. Pentru funcţia booleană f : B(2)3B(2), definită tabelar mai jos:

X1 X2 X3 f

0 0 0 1

0 0 1 0

0 1 0 1

0 1 1 1

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 1

să se determine:

a) forma canonică disjunctivă,

b) forma canonică conjunctivă,

c) forma caracteristică,

72

d) forma minimală (formele minimale),

e) expresia Reed-Muller asociată,

7. Să se determine expresiile algebrice pentru funcţiile f, g : P(3)2P(3),

definite mai jos, unde P(3) are o structură Post de dimensiune 3. Să se deducă şi formele

simplificate, utilizând diagramele Karnaugh ternare.

X1 X2 f g

0 0 2 1

0 1 2 0

0 2 2 2

1 0 1 1

1 1 1 0

1 2 1 2

2 0 1 1

2 1 2 0

2 2 1 2

8. Prezentaţi tablele operaţiilor structurilor Galois (GF(7), , ) şi

(GF(8), , ) şi precizaţi care dintre aceste structuri se bucură de proprietatea de

completă funcţionalitate.

73

CUPRINS

Partea întâia

BAZELE ARITMETICE ALE SISTEMELOR DE CALCUL

1. Conceptul de sistem de numeraţie……………………………………3

1.1. Teorema sistemelor de numeraţie ................................... ................ .........3

1.3. Compararea numerelor reprezentate într-o bază...................................... 5

1.4. Algoritmi pentru calculul sumei şi produsului a două numere

reprezentate în aceeaşi bază............................................ .................. ......5

1.5. Algoritmul sistemelor de numeraţie............................... ......................... 7

1.6. Conversia numerelor dintr-o bază în alta................................ ................. 7

1.6.1. Metoda substituţiei............................. ......................................... ............7

1.6.2. Metoda împărţirii/înmulţirii bazei................................ ............... ............9

1.6.3. Exemple............................................ .............. ......................................... 10

1.7. Rezumat.................................................................................................... 10

2. Elemente de teoria codificării....................................... ......................... 12

2.1. Cod. Codificare. Limbaje de codificare...... .............................................. 12

2.2. Limbaje peste un anumit alfabet. Operaţii cu limbaje.............................. 14

2.3. Limbaje generate de gramatici.................................................................. 15

2.5. Exemple reprezentative de codificări........................................................ 17

2.6. Coduri implicate în reprezentarea informaţiei în memoria

sistemelor de calcul................................................................................... 19

2.6.1. Codul direct............................................................................................... 19

2.6.2. Codul complementar....................... ........................... ...............................20

2.6.3. Codul invers............................................................... ............................... 21

2.7. Rezumat................................................................... .................................. 23

3. Reprezentarea informaţiei numerice în memoria sistemelor de

calcul.......... ................................................................................................ 24

3.1. Reprezentarea informaţiei numerice în virgulă fixă................................... 25

3.2. Reprezentarea informaţiei numerice în virgulă mobilă..............................58

3.3. Operaţii aritmetice cu numere reprezentate în virgulă mobilă.......... .........27

3.3.1. Adunarea şi scăderea.................................................................................. 27

3.3.2. Înmulţirea şi împărţirea.............................................................................. 27

3.4. Standardul IEEE P754................................................ ............................... 28

3.4.1. Structura şi semnificaţia standardului........................................................ 28

3.4.2. Operaţii cu numere reprezentate în standardul IEEE P754....................... 30

3.4.2.6. Rotunjirea.................................................................... ............................... 30

3.4.2.7. Exemple...................................................................... ................................ 31

3.5. Rezumat....................................................................... ............................... 33

74

Partea a doua

BAZELE LOGICE ALE SISTEMELOR DE CALCUL

2. Structuri algebrice implicate în proiectarea şi optimizarea circuitelor 35

2.1. Latice .............................................................................. ......................... .... 35

2.2. Algebra booleană ............................................................. ...................... ...... 36

2.3. Inel boolean ............................................. ....................................... .............. 37

2.4. Legătura dintre algebra booleană şi inelul boolean ........ ...................... ........ 39

2.5. Exemple reprezentative: (X), X≠Ø; B(2), B(4), Z2 ................................... .40

2.6. Rezumat.................................................................................................. ...... 42

3. Funcţii booleene şi expresii Reed-Muller ............................................... .. 43

3.1. Funcţii booleene......................................................................................... ....43

3.2. Formulele de interpolare Lagrange ............................... ............................. ...44

3.3. Sisteme complete de funcţii booleene ........................... ............................. ...46

3.4. Simplificarea funcţiilor booleene ........................ .......... ............................ ....46

3.4.1. Metode analitice (Quine McCluskey) ......................... .................. .............. ..47

3.4.2. Metode grafice ........................................................... .............. ........... ..........50

3.4.2.1. Diagrame Veitch ........................... ...................................... ........................ ..51

3.4.2.2. Diagrame Karnaugh ........ .............................................. .............................. ..52

3.5. Funcţii booleene incomplet definite ................................ ....................... .......54

3.6. Funcţia inversă şi funcţia duală a unei funcţii booleene . ............................. ..55

3.8. Structuri Reed-Muller .......................................................... ........................ ..56

3.8.1. Algebra (GF(2), , ) ..................................................... ............................ ..57

3.8.2. Expresii Reed – Muller ............. ....................................... ............................ ..58

3.10. Rezumat……………………………………………………………………. 60

4. Teste de verificare şi teme de control............................................................62

4.1. Test de autoevaluare1........................................................................................62

4.2. Test de autoevaluare2........................................................................................6 5

4.3. Tema de control 1........................................... ................................................... 69

4.4. Tema de control 2.............................................................................................. 71

Cuprins................................................................................ ...........................................73

horatiuvlad.com computationala_cocan.pdf3 partea ÎntÂia bazele aritmetice ale sistemelor de calcul...

Documents