Reprezentarea numerelor si operatiilor aritmetice 1 Clasificarea nr

Reprezentarea numerelor si operatiilor aritmetice
1) Clasificarea nr: intregi (I) si reale (I.F) (poz/negative).

2) Sistemul de reprezentare={Baza,Simboli}

a) Sistemul zecimal: B=10, S={0,…,9}

b) Sisteme tip binar

binar: B=2, S{0,1} bit

octal: B=2³=8, S{0,…,7}

hexazecimal: B=2⁴=16, S={0,…,9,A,B,C,D,E,F}

Conversii:

- binar-octal: se imparte nr in grupe de cate 3 biti de la dreapta la stanga

- octal-binar: se reprezinta fiecare cifra octala pe 3 biti de la stanga la dreapta

- binar-hexa: se imp. nr binar in cate 4 biti de la LSB la MSB

- hexa-binar: fiecare cifra hexa se inlocuieste cu grupul de 4 biti care il reprezinta

(sistemul hexa)

	2^3	2^2	2^1	2^0
0	0	0	0	0		8	1	0	0	0
1	0	0	0	1		9	1	0	0	1
2	0	0	1	0		A	1	0	1	0
3	0	0	1	1		B	1	0	1	1
4	0	1	0	0		C	1	1	0	0
5	0	1	0	1		D	1	1	0	1
6	0	1	1	0		E	1	1	1	0
7	0	1	1	1		F	1	1	1	1

-binar-zecimal: .

(_i-simbolii sistemului; bⁱ-baza la puterea i)
3) Reprezentarea numerelor intregi in binar

- intreg: 16 biti (short) si 32 biti (long)

Semnul ocupa pozitia MSB. (0-pozitiv; 1-negativ) (bit 15 – short si bit 31 - long).

Short  [-2¹⁵, 2¹⁵-1]=[-32.768,32.767]

Long  [-2³¹,2³¹-1]

Conventii standard:

1) VA&S (M&S) (VA=valoare absoluta; S=semn; M=medel)

Numarul 0 in hexa este: +0=0000_H ; -0=8000_H.

2) C1 (complement fata de 1)

Complementul fata de 1 al unui numar este imaginea binara obtinuta prin inversarea fiecarei pozitii binare. Un incon-venient este faptul ca C1 pastreaza dubla imagine a lui 0.

Ex: n1=111=01101111; n2=-123=10000100;

n1+n2=11110011 => C1(n1+n2)=10001100

3) C2 (complement fata de 2); C2=C1+1

Complementul fata de 2 al unui numar se obtine incepand de la MSB pana se intalneste valoarea 1 se pastreaza, apoi restul se complementeaza. C2 are o singura reprezentare pentru 0.

Ex: 84=01011000

C1(84)=10100111; C2(84)=C1(84)+1=10101000.


4) Reprezentarea numerelor reale si operatii aritmetice.

Metode de reprezentare a numerelor.

I.F; Sgn=0 (pozitiv) sau 1 (negativ).

1) Reprezentarea in virgula fixa (Fixel Point)

n = n _I + n _F ;

65362879=.65362879x10⁴

Mantisa normalizata presupune ca prima cifra din dreapta numarului sa fie diferita de 0 si tot ce ramane la stanga sa fie 0. Procedura de normalizare reprezinta deplasarea spre stanga cu un numar k de pozitii si majorarea exponentului cu k.

Rezolutia este precizia de reprezentare a numerelor. Numarul de cifre alocat pentru mantisa defineste precizia de reprezentare. Eroarea maxima de reprezentare este (n_M = numarul de biti al mantisei).

;

2) Reprezentarea in virgula mobila (Flouting Point)

a) Reprezentarea in sistem binar virgula mobila in simpla precizie – utilizeaza 32 biti

Exp este in C2 si Exp[-128,127]; mantisa este normalizata.

Exp OFFSET = Exp + 128  [0,255]

1-128 subunitar ; 129-255 supraunitar

b) Reprez. in virgula mobila cu un bit ascuns (Hidden bit)

- reprez in dubla precizie (se prelungeste mantisa la 55 biti).

Permite reprezentarea cu 16 zecimale evacte.



Conversia partii fractionare din zecimal in binar

Conversia se face exact atunci cand procedeul iterativ se opreste la partea fractionara 0. O conversie periodica din program depisteaza perioada. Conversia completa este atunci cand se parcurg 23/55 de biti.

Operatii aritmetice efectuate cu numere reale in virgula mobila

a) Adunarea: Se aranjeaza operanzii conform marimilor (operandul mai mic se deplaseaza catre dreapta). Operanzii negativi se transforma in C2. Mantisa se normalizeaza, si se modifica doar in cazul in care rezultatul este negativ. Daca numerele au acelasi semn se poate depasi (carry) => rezultatul se deplaseaza la dreapta cu un pas si exponentul se majoreaza cu o unitate. Exponentul se minoreaza daca avem depasire inferioara.

b) Inmultirea: se pierde precizia.

5) Algebra logica

1) a) Negatia (Inversare, Complementare):

b) Conjunctia (Produs, Si/And)

Conjunctia da rezultatului valoarea 1 numai daca toate variabilele implicate au valoarea logica 1.

x and y = x  y = xy

; =1 daca e negat si 0 daca nu.

c) Disjunctia (Suma, Sau/Or)

Suma da rezultatului valoarea 0 numai daca toate variabilele implicate au valoarea logica 0.



; daca e negat si x_k daca nu.

2) Proprietati:

a) a  0 = 0 ; a + 1 = 1 ; b) a  1 = a ; a + 0 = a

c) a  a … a = a ; a + a +…+ a = a

d) Asociativitate si comutativitate: a  (b+c) = a  b + a  c

Forma disjunctiva canonica

. Reprezinta suma logica a termenilor produs asociati acelor puncte in care functia e 1 logic. Intr-un termen canonic, valoarea bitului se ia direct daca e 1 si 0 invers.

Forma conjunctiva canonica

. Reprezinta produsul logic al termenilor canonici disjunctivi asociati punctelor in care functia e 0 logic. In termenul canonic individual pentru toti bitii, bitii 0 se iau direct si bitii 1 se iau negat.

Teoremele lui DeMorgan

(Negata sumei este egala cu produsul negatiilor). (Suma negatiilor este egala cu produsul negat).

3) Operatorul NAND reprezinta negarea unui produs.

Operatorul NOR reprezinta negarea unei sume.

;

Operatorul XOR (merge numai pe 2 biti)

6) Reprezentarea spatiului logic n dimansional S_n in cod ciclic – reflectat (cod Gray)

1) Distanta binara intre doua puncte (distanta Hamming)

d_H = numarul de biti prin care difera codurile celor 2 puncte

Daca d_H(C_i,C_j)=1 atunci C_i este adiacent cu C_j. Daca d_H(C_i,C_j)=0 atunci C_i si C_j sunt identice. In spatiul S_n un punct are n coduri adiacente.

2) Crearea secventei codului Gray

Se alege un cod de baza (in general codul cu toti bitii 0). Urmatoarele coduri din secventa se obtin prin complementari ale codului urmator, pornind de la LSB si indeplinind conditia de adiacenta a noului cod fata de cel anterior.

Axele de simetrie arata proprietatea de simetrie sau reflexie a codului.

Nr	x3	x2	x1	x0		Nr	x3	x2	x1	x0
0	0	0	0	0		0	0	0	0	0
1	0	0	0	1		1	0	0	0	1
2	0	0	1	0		3	0	0	1	1
3	0	0	1	1		2	0	0	1	0
4	0	1	0	0		6	0	1	1	0
5	0	1	0	1		7	0	1	1	1
6	0	1	1	0		5	0	1	0	1
7	0	1	1	1		4	0	1	0	0
8	1	0	0	0		C	1	1	0	0
9	1	0	0	1		D	1	1	0	1
A	1	0	1	0		F	1	1	1	1
B	1	0	1	1		E	1	1	1	0
C	1	1	0	0		A	1	0	1	0
D	1	1	0	1		B	1	0	1	1
E	1	1	1	0		9	1	0	0	1
F	1	1	1	1		8	1	0	0	0

7) Reprezentarea bidimensionala a S_n

1) Diagramele Karnaugh

n biti – k biti  linii => 2^k

- j = n-k biti  coloane => 2^n-k

Diagrama este o matrice din linii si coloane. Fiecare linie/coloana capata un cod propriu, format din k biti/n-k biti.

Diagrama va avea 2^k linii si 2^n-k coloane. Minimizarea functiei reprezinta de fapt gruparea unui numar par (putere a lui 2) de casute aflate de o parte si de alta a axei de simetrie a spatiului.
2) Subspatii ale spatiului n dimensional

Un subspatiu S_k  S_n, , reprezinta o multime 2^k coduri, unde n-k biti sunt constanti, iar k biti parcurg intreg ciclul de variatie. Exista 2ⁿ subspatii de tip S₀.

. Prin utilizarea diagramei Karnaugh se descopera foarte usor acoperirea unui subspatiu cu ajutorul aceleiasi functii logice pe baza axelor de simetrie. Astfel rezulta forma de simplificare (minimizare) a expresiilor logice ale functiilor. Important este descoperirea subspatiilor acoperite integral de 1 daca functia este disjunctiva sau 0 daca functia este conjunctiva. Prima data se observa subspatiile acoperite cu aceeasi valoare, apoi se inlocuiesc toate punctele subspatiului cu expresia care caracterizeaza subspatiul, iar termenii rezultati se insumeaza.


Comparatoare binare de marime

(Magnitudine comparator)

Fie doua numere intregi X, Y de n biti.

(comparator intre 2 numere pe n biti cu posibilitatea de transport prin intrarile a,e,b si iesirile de transport A,E,B)

a/A=1 – canal X > canal Y; b/B=1 – canal Y > canal X; e/E=1 – canal X = canal Y. Singurele combinatii pentru o buna functionare sunt: 100,010,001.

Comparator pe n biti. Fiecare celula depinde de 2n+3 intrari.

Fie =1 functia logica care decide daca X>Y; =1 daca Y>X; =1 daca X=Y => A = a + e ; B = b + e; E = e.

Pentru stabilirea rezultatului decizia se ia de la semnificativ la mai putin semnificativ. Elementul critic in procesul de decizie este componenta de transport. Daca raspunsul ar avea o intarziere “tau” vom avea p”tau” timpi de asteptare pana la stabilizarea rezultatului.

Pentru n=1 avem comparator elementar pe un bit:

; ;

Pentru ,  avem 2 nivele de prelucrare => .

Pentru  avem 3 nivele de prelucrare => .

Pentru n=2 avem comparator pe 2 biti:

=1 pentru: x=1 si y=0; x=2 si y=0; x=2 si y=1; x=3 si y=0; x=3 si y=1; x=3 si y=2. Pentru =1 vor fi alte 6 cazuri, iar pentru =1 restul de 4 cazuri.

In forma canonica: 4 inversoare; 6 modulo “SI” de cate 4 intrari; 1 “OR” de cate 6 intrari => 34 intrari. In forma minimala: 2 inversoare; 1 AND x 2 in; 2 AND x 3 in; 1 OR x 3 in => 13 intrari.

(1-) (0-) (-1) (00) (11) (-0)

3 sau 2 1 sau 0 3 sau 1 > 0 3 > 2 sau 0

min2 > max1

Pentru n=3 avem un comparator pe 3 biti:

In forma canonica: 6 inversoare a 28 AND x 6 intrari fiecare; 1 modul OR de 28 de intrari => cost = 202.

;

;;

;

; ; .

Costul in forma minimala: 1 CI (3 inv; 1 AND x 2 in); 1 CI (2 AND x 3 in); 2CI (4 AND x 4 in); 1 CI (1 OR x 7 in) = 34.

Impachetarea in circuite standard pe AND: 6 inversoare intr-o capsula de 14 pini.

Modulele in AND de 2 intrari sunt 3 module intr-o capsula. Cele de 4 intrari sunt 2 intr-o capsula.