bazele aritmeticeale calculatoarelor numerice

Capitolul 2 - Bazele aritmetice ale calculatoarelor numerice

2. BAZELE ARITMETICE ALE CALCULATOARELOR NUMERICE2.1. Introducere 2.2. Sisteme de numeratie, conversii si operatii 2.2.1. Sisteme de numeratie 2.2.2. Conversia unui numar dintr-o baza n alta 2.2.2.1. Metoda substitutiei 2.2.2.2. Metoda mpartirii la / nmultirii cu noua baza 2.2.3. Operatii aritmetice n binar octal si hexazecimal 2.2.3.1. Operatii aritmetice n SN binar 2.2.3.2. Operatii aritmetice n SN octal 2.2.3.3. Operatii aritmetice n SN hexazecimal 2.3. Reprezentarea numerelor n calculator 2.3.1. Reprezentarea numerelor n virgula fixa 2.3.1.1. Reprezentarea unui numar prin marime si semn 2.3.1.2. Reprezentarea unui numar n complement fata de 1 (cod invers) 2.3.1.3. Reprezentarea unui numar n complement fata de 2 (cod complementar) 2.3.1.4. Reprezentarea n exces 2.3.2. Reprezentarea numerelor n virgula mobila 2.3.3. Coduri numerice si alfanumerice 2.3.3.1. Coduri numerice 2.3.3.2. Coduri alfanumerice 2.3.3.3. Coduri detectoare si corectoare de erori

13.01.2004

1 / 104


2.4. Operatii aritmetice n virgula fixa 2.4.1. Adunarea si scaderea binara 2.4.1.1. Adunarea si scaderea n cod direct 2.4.1.2. Adunarea si scaderea n cod complementar 2.4.1.3. Adunarea si scaderea n cod invers 2.4.2. nmultirea binara 2.4.2.1. nmultirea n cod direct 2.4.2.2. nmultirea n cod complementar 2.4.2.3. nmultirea cu puteri ale lui 2 2.4.2.4. nmultirea cu mai multe cifre 2.4.3 mpartirea binara 2.4.3.1. mpartirea binara prin metoda compararii 2.4.3.2. mpartirea binara cu refacerea restului partial 2.4.2.3. mpartirea binara cu refacerea restului partial 2.5. Operatii aritmetice n virgula mobila 2.5.1. Adunarea si scaderea numerelor reprezentate n virgula mobila 2.5.2. nmultirea numerelor reprezentate n virgula mobila 2.5.3. mpartirea numerelor reprezentate n virgula mobila 2.6. Operatii aritmetice cu numere zecimale codificate binar 2.6.1. Codificarea binara a numerelor zecimale 2.6.2. Adunarea si scaderea n cod binar-zecimal 2.6.3. nmultirea n cod binar-zecimal 2.6.3.1. nmultirea cu 10k 2.6.3.2. Metoda adunarii repetate 2.6.3.3. Metoda celor noua multipli ai denmultitului 2.6.4. mpartirea n cod binar-zecimal 2.6.4.1. Metoda compararii 2.6.4.2. Metoda refacerii restului partial 2.6.4.3. Metoda fara refacerea restului partial

13.01.2004

2 / 104


2. BAZELE ARITMETICE ALE CALCULATOARELOR NUMERICEPentru ntelegerea aspectelor legate de structura si functionalitatea sistemelor numerice de calcul se impune detinerea unor cunostinte ce privesc att prelucrarea informatiei numerice ct si mijloacele de implementare. n acest capitol se prezinta unele aspecte legate de reprezentarea numerelor si operatii aritmetice specifice calculatoarelor numerice. 2.1. Introducere Dupa cum s-a aratat resursele importante ale unui calculator numeric sunt reprezentate de cele de calcul si comanda, memorare , intrare iesire si comunicatii. n ceea ce priveste memoria interna aceasta este realizata din dispozitive cu doua stari stabile iar elementele de procesare a informatiei sunt bazate pe circuite logice care opereaza pe baza logicii bivalente. Aceste motive recomanda reprezentarea datelor n binar sub forma unor succesiuni de unitati si zerouri. Exista numeroase posibilitati pentru reprezentarea datelor, care difera prin expresibilitate, cost de implementare, efortul de conversie de la un format la altul, etc. Calculatoarele contin elemente de stocare a datelor de tipul registrelor, cu un numar finit de elemente (ranguri) care afecteaza precizia calculului. Uzual se spune ca reprezentarea este cu precizie finita aspect care presupune prezenta erorilor de procesare. Tipurile uzuale de date care se folosesc la nivelul hardware al unui calculator numeric sunt: - Bit: 0, 1; Sir de biti: secvente de biti cu urmatoarele lungimi uzuale: tetrada: 4 biti;

13.01.2004

3 / 104


-

octet / byte: 8 biti; semicuvnt: 16 biti; cuvnt: 32 biti; dublu cuvnt: 64 de biti,

Caracter: ASCII: cod de 7 biti, Zecimal: cifrele zecimale 0 9 codificate binar 0000 2 1001 2 (doua cifre zecimale pot reprezentate n doi octeti sau pot fi mpachetate ntr-un singur octet); ntreg (Virgula Fixa): fara semn; cu semn, reprezentare n: cod direct (semn si modul); cod invers (complement fata de unu ); cod complementar (complement fata de doi); Real (Virgula Mobila): precizie simpla; precizie dubla; precizie extinsa.

-

-

2.2. Sisteme de numeratie, conversii si operatii 2.2.1. Sisteme de numeratie Un sistem de numeratie (SN) este format din totalitatea regulilor de reprezentare a numerelor cu ajutorul unor simboluri numite cifre. SN sunt de doua tipuri: pozitionale si nepozitionale. SN pozitionale mai sunt cunoscute si sub denumirea de SN ponderate ntruct valoarea unei cifre depinde att de semnificatia sa intrinseca ct si de pozitia acesteia n respectivul numar. De exemplu, pentru numarul 1111 reprezentat n SN zecimal fiecare cifra 1 are o alta pondere (mii, sute, zeci, unitati). Un exemplu de sistem nepozitional, n care ponderea nu este influentata de pozitia cifrei este sistemul roman. Datorita simplitatii de reprezentare si efectuare a calculelor, n sistemele numerice se folosesc n exclusivitate sistemele pozitionale, un

13.01.2004

4 / 104


asemenea sistem fiind caracterizat prin baza care reprezinta numarul total de simboluri (cifre). Exemplu de baze uzuale: Sistemul zecimal, b=10, simboluri: 0,1,2,3,4,5,6,7,8,9; Sistemul binar, b=2, simboluri: 0,1; Sistemul octal, b=8, simboluri: 0,1,2,3,4,5,6,7; Sistemul hexazecimal, simboluri: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F. Pentru un numar ntreg N0, reprezentarea n baza b este un n tuplu N = xn-1 xn-2 . x2 x1 x0 care verifica urmatoarele doua conditii: a - 0 xi < b, i = n-1,,0; xn-1 0 ; b - N = xn-1 bn-1 ++ x1 b+ x0. Exemple b = 10, N = 4 52310 b = 8, N = 5738 b = 2, N = 1010012

= = =

4x103 +5x102 +2x10+3 5x82 +7x8+3 1x25 +0x24 +1x23 +0x22 +0x21 +1.

Numerele reale au o reprezentare asemanatoare, nsa contin punctul fractionar (sau virgula) care separa partea ntreaga de cea fractionara. Pentru un numar real r0, reprezentarea n baza b este secventa de simboluri (m tuplul) r = xm-1 x1 x0 . x-1 x-2 care verifica urmatoarele relatii: a - 0 xi < b, i = m-1,,0,-1,-2,; xm-1 0; b - nu exista un rang k astfel nct ncepnd de la acel rang xk = xk-1 ==b-1 c - r = xm-1 bm -1 ++ x1 b+ x0 + x-1 b-1 + x-2 b-2 + Exemple b=10, N=154.6430 =1x102 +5x10+4+3x10-1 +2x10-2 b=8, N=623.458 =6x82 +2x8+3+4x8-1 +5x8-2 b=2, N=101.0112 =1x22 +0x2+1+0x22 +1x21 +1. Pornind de la faptul ca la baza realizarii unui sistem numeric de calcul stau dispozitivele cu doua stari stabile, rezulta ca SN binar (care

13.01.2004

5 / 104


necesita numai doua cifre, 0 si 1) este cel mai potrivit pentru prelucrarea, codificarea si transmiterea informatiei n aceste echipamente. SN ale caror baze reprezinta puteri ale lui 2 prezinta de asemenea proprietatile sistemului binar, motiv pentru care sunt frecvent utilizate n tehnica de prelucrare automata a datelor (n special SN octal si SN hexazecimal). n ceea ce priveste SN zecimal acesta este cu precadere utilizat n anumite faze ale operatiilor de intrare- iesire. 2.2.2. Conversia unui numar dintr-o baza n alta ntr-un sistem de calcul datele sunt de regula reprezentate n mai multe sisteme de numeratie. Astfel datele de intrare si cele de iesire (rezultatele) sunt de regula reprezentate n baza 10 n timp ce n memorie si n unitatea de procesare baza de reprezentare este 2. Sunt situatii n care datele care se prelucreaza se reprezinta n baza 10, cifrele zecimale fiind reprezentate prin tetrade binare. Pentru reducerea efortului de procesare datele se reprezinta n memorie n bazele 8 sau 16. Existenta si utilizarea mai multor SN ridica problema conversiei dintr-un sistem n altul. n continuare vor fi prezentate doua metode frecvent utilizate si anume: a - metoda substitutiei; b metoda mpartirii la / nmultirii cu baza. 2.2.2.1. Metoda substitutiei Fie numarul N reprezentat n baza a N = an-1 n-1 + an-2 n-2 ++ a0 0 + a-1 -1 ++ a-m -m, (2.1) pentru care se doreste conversia n baza . Metoda substitutiei presupune scrierea numarului Na n forma0 m L + (a0 ) (10 ) + (a 1 ) (10)1 L + (a m ) (10 )

N = (an 1 ) (10 ) + (an 2 ) (10 )n 1

n 2

+

(2.2)

si conversia n baza pentru fiecare cifra (ai )a si (10) a . Exemple

13.01.2004

6 / 104


a. Sa se realizeze conversia n baza 2 a numarului N = (17)16 . Aplicnd relatia (2.2) se obtine0 N = (17 )16 = (1)16 (10 )1 + (7 )16 (10 )16 16

dar

(1)16 = (1)2 , (7 )16 = (111)2 , (10 )16 = (16 )10 = (10 000 )2n aceste conditii numarul N se va scrie= (10111 )2 = (0001 0111)2 N = (17 )16 = (1)2 (10000 )2 + (111)2 = (10000 )2 + (111 )2 =

b. Sa se realizeze conversia n baza 2 a numarului N = (54) 8 . Aplicnd relatia (2.2) se obtineN = (52 )8 = (5 )8 (10 )1 + (2 )8 (10 )0 8 8

dar

(5)8 = (101)2 , (2)8 = (10 )2 , (10)8 = (8)10 = (1000 )2n aceste conditii numarul N se va scrie= (101010 )2 = (101 010 )2 N = (52 )8 = (101 )2 (1000 )2 + (10 )2 = (101000 )2 + (10 )2 =

c. Sa se realizeze conversia n baza 10 a numarului N = (25) 8 . Aplicnd relatia (2.2) se obtineN = (25 )8 = (2 )8 (10 )1 + (5)8 (10 )0 8 8

dar

(2)8 = (2)10 ,(5)8 = (5)10 , (10)8 = (8)10n aceste conditii numarul N se va scrieN = (25 )8 = (2 )10 (8 )10 + (5)10 = 2 8 + 5 = (21)10

13.01.2004

7 / 104


d. Sa se realizeze conversia n baza 10 a numarului N = (10100) 2 . Aplicnd relatia (2.2) se obtineN = (10100 )2 = (1)2 (10 )4 + (0 )2 (10 )3 + (1)2 (10 )2 + 2 2 2 + (0)2 (10 )1 + (0 )2 (10 )0 =1 2 4 + 1 2 2 = (20 )10 2 2

dar

(2)8 = (2)10 ,(5)8 = (5)10 , (10)8 = (8)10n aceste conditii numarul N se va scrieN = (25 )8 = (2 )10 (8 )10 + (5)10 = 2 8 + 5 = (21)10

e. Sa se realizeze conversia n baza 10 a numarului N = (BF4.15) 16 . Aplicnd relatia (2.2) se obtine2 0 N = (BF 4 .15 )16 = (B )16 (10 )16 + (F )16 (10 )1 + (4 )16 (10 )16 + 16 1 2 + (1)16 (10 )16 + (5)16 (10 )16

dar

(B )16 = (11)10 , (F )8 = (15 )10 , (4 )16 = (4 )10 , (1)16 = (1)10 , (5 )16 = (5 )10 , (10 )16 = (16 )10n aceste conditii numarul N se va scrie2 N = (BF 4.15 )16 = (11)10 (16 )10 + (15 )10 (16 )1 + 10 0 1 2 + (4 )10 (16 )10 + (1)10 (16 )10 + (5)10 (16 )10 =

11 256 + 15 16 + 4 +1 0 .0625 + 5 0.00390625 = = 2816 + 240 + 4 + 0.0625 + 0 .01953125 = (3060 .08203125 )10

13.01.2004

8 / 104


Din analiza exemplelor a si b se desprinde concluzia ca din bazele care sunt puteri ale lui 2 conversia se poate realiza mecanic nlocuind cifrele numarului cu combinatiile binare corespunzatoare. n Tabelul 2.1 se prezinta combinatiile binare pentru cifrele sistemului octal (triade) respectiv hexazecimal (tetrade). Tabelul 2.1Octal 0 1 2 3 4 5 6 7 Binar 000 001 010 011 100 101 110 111 Hexazecimal 0 1 2 3 4 5 6 7 Binar 0000 0001 0010 0011 0100 0101 0110 0111 Hexazecimal 8 9 A B C D E F Binar 1000 1001 1010 1011 1100 1101 1110 1111

n ceea ce priveste conversia din binar ntr-o baza putere a lui 2 aceasta se poate realiza tot mecanic. n continuare se va exemplifica procedeul pentru conversiile binar octal si binar hexazecimal. Conversia binar - octal Fie r = xmxm-1 x1 x0 . x-1 x-2 reprezentarea binara a unui numar real r oarecare. Acelasi numar scris ca o combinatie liniara a puterilor lui 2 este: r = xm 2m+xm-1 2 m-1 +x1 2+x0 +x-1 2-1 +x-2 2-2 +.. . Deoarece o cifra octala se reprezinta printr-o grupare de trei biti, grupam expresia n triade: r = (x3k+2 23k+2 + x3k+1 23k+1 + x3k 23k )+. + (x2 22 + x1 2 + x0 ) + (x-1 2-1 + x-2 2-2 + x-3 2-3 )+. sau r = 23k (x3k+2 22 + x3k+1 2 + x3k 2)+. + (x2 22 + x1 2 + x0 ) + 2-3 (x-1 22 + x-2 2 + x-3 )+. respectiv

13.01.2004

9 / 104


r = 8k yk ++ 80 y0 + 8-1 y-1 + cu 0 yi =x3i+2 22 + x3i+1 2 + x3i < 8. Rezultatul demonstratiei de mai sus permite formularea urmatoarei reguli de conversie: fiind dat un numar real n forma binara , reprezentarea sa n octal se obtine grupnd cte trei cifrele binare ncepnd de la marca fractionara (punct, virgula), spre stnga respectiv dreapta. Dupa ce grupele extreme se completeaza (daca este cazul cu zerouri nesemnificative), fiecare triada se nlocuieste cu echivalentul sau octal. Conversia binar - hexazecimal Fie r = xmxm-1 x1 x0 . x-1 x-2 reprezentarea binara a unui numar real r oarecare. Acelasi numar scris ca o combinatie liniara a puterilor lui 2 este: r = xm 2m+xm-1 2 m-1 +x1 2+x0 +x-1 2-1 +x-2 2-2 +.. . Deoarece o cifra hexazecimala se reprezinta printr-o grupare de patru biti, grupam expresia n tetrade: r = (x4k+3 24k+3 + x4k+2 24k+2 + x4k+1 24k+1 + x4k 24k )+. + (x4 24 + x3 23 + x2 22 + x1 2 + x0 ) + + (x-1 2-1 + x-2 2-2 + x-3 2-3 + x-4 2-4 )+. sau r = 24k (x4k+3 23 + x4k+2 22 + x4k+1 2 + x4k 2)+. + (x3 23 + x2 22 + x1 2 + x0 ) + 2-4 (x-1 23 + x-2 22 + x-3 2 + x-4 )+. respectiv r = 16k yk ++ 160 y0 + 16-1 y-1 + cu 0 yi = x4i+3 23 + x4i+2 22 +x4i+1 2 + x4i < 16. Ca si n cazul precedent, rezultatul demonstratiei de mai sus permite formularea urmatoarei reguli de conversie: fiind dat un numar real n forma binara , reprezentarea sa hexazecimala se obtine grupnd cte patru cifre binare ncepnd de la marca fractionara (punct, virgula), spre stnga respectiv dreapta. Dupa ce grupele extreme se completeaza (daca este cazul cu zerouri nesemnificative), fiecare tetrada se nlocuieste cu echivalentul sau hexazecimal.

13.01.2004

10 / 104


Dupa cum s-a mai spus, conversiile inverse octal / hexazecimal binar se realizeaza prin nlocuirea fiecarei cifre octale / hexazecimale cu triada / tetrada corespunzatoare. Exemple a. Sa se converteasca n binar numerele A=(135.72) 8 si B=(5A23.B5D)16 . (A)2 = 001 | 011 | 101.111 | 010 (B)2 = 0101 | 1010 | 0010 | 0011.1011 | 0101 | 1101 b. Sa se converteasca n octal si n hexazecimal numarul binar (C)2 =1011010.11011. b1. (C)2 = 001 011 010 . 110 110 Pe baza corespondentei din tabelul 2.1 rezulta (C)8 =132.66. b2. (C)2 =0101 1010 . 1101 1000 dupa care se face corespondenta n conformitate cu Tabelul 2.1 si rezulta (C)16 =5A.D8. 2.2.2.2. Metoda mpartirii la / nmultirii cu noua baza Fie numarul real N reprezentat n baza a N = an-1 n-1 + an-2 n-2 ++ a0 0 + a-1 -1 ++ a-m -m, (2.3) pentru care se doreste conversia n baza . Pornind de la reprezentarea numerelor prin intermediul coeficientilor dezvoltarii polinomiale, n raport cu baza, conversia se poate realiza prin operatii repetate de mpartire / nmultire la / cu noua baza, dupa cum se converteste partea ntreaga respectiv cea fractionara. Deoarece se vor trata separat conversiile partilor ntreaga respectiv fractionara, numarul se va considera descompus sub forma N = NI + NF (2.4)

n care NI si NF sunt partile ntreaga respectiv fractionara ale numarului real N .

13.01.2004

11 / 104


Conversia numerelor ntregi Fie partea ntreaga NI , exprimata n baza , a unui numar real N: NI = an-1 n-1 + an-2 n-2 ++ a1 + a0 0 , care n baza poate fi exprimata astfel NI a = xn-1 n-1 + xn-2 n-2 ++ x1 + x0 0 , n care coeficientii xi urmeaza a se determina. Determinarea acestor coeficienti prin metoda mpartirilor succesive presupune mpartirea repetata a numarului la noua baza si retinerea resturilor conform procedeului de mai jos. NI / = xn-1 n-2 + xn-2 n-3 ++ x1 0 + x0 / Ctul = (N1 )I Restul

x0 , x1 ,

(N1 )I / = xn-1 n-3 + xn-2 n-4 ++ x2 0 + x1 /

Ctul = (N2 )I Restul .. (Nk )I / = xn-1 n-k-2 +.+ xn-k-1 0 + xk / xk Ctul = (Nk+1 )I Restul .

.

Dupa cum se observa n urma primei mpartiri rezulta x0 , (cifra cea mai putin semnificativa a rezultatului - CCMPS), apoi x1 s.a.m.d. Procedeul continua pna cnd ctul devine mai mic dect noua baza , ultimul rest fiind coeficientul xn-1 , (cifra cea mai semnificativa a rezultatului -CCMS). Din cele prezentate rezulta ca procesul de determinare a reprezentarii n noua baza este un proces iterativ cu un numar necunoscut de pasi la nceputul conversiei, ntruct se utilizeaza drept criteriu de stop obtinerea unui ct mai mic dect noua baza.

13.01.2004

12 / 104


Daca baza de plecare este 10, iar conversia se face n baza , atunci numarul de iteratii, respectiv numarul de cifre n noua reprezentare poate fi determinat nainte de nceperea conversiei potrivit relatieilog N + 1 daca N = k , k N n= [log N ] + 1 daca N k , k N

(2.5)

Conversia numerelor fractionare Fie partea fractionara NF , exprimata n baza , a unui numar real N: NF = a-1 -1 + a-2 -2 ++ a-m -m, care n baza poate fi exprimata astfel NFa = x-1 -1 + x-2 -2 ++ x-m-m , n care coeficientii x-i urmeaza a se determina. Determinarea acestor coeficienti prin metoda nmultirilor succesive presupune nmultirea repetata a numarului fractionar cu noua baza si retinerea partilor ntregi ale produselor conform procedeului de mai jos. NF x = x-1 + x-2 -1 +.+ x-m-m+1-1

x-1 ,

(N1 )F (N1 )F x = x-2 + x-3 +.+ x-m-m+2 x-2 , (N2 )F .. (Nk-1 )F x = x-k + x-k-1 -1 +.+ x-m-m+k x-k , (Nk )F . Cifra x-1 reprezinta CCMS iar x-k CCMPS a rezultatului. Procedura se opreste n momentul partea fractionara (Nk)Fa a rezultatului unei nmultiri devine zero, sau daca s-a atins precizia de conversie specificata.

13.01.2004

13 / 104


n situatia n care numarul fractionar care se converteste respecta relatiaNF = 1 k unde M , k N

(2.6)

atunci numarul se poate exprima n baza , n conditiile unei erori de conversie nule pe k ranguri. n situatia n care conditia (2.6) nu este respectata, pentru estimarea numarului de ranguri asociat rezultatului conversiei partii fractionare a unui numar se impune eroarea relativa de conversie erel conv care se poate exprima prin relatiae rel conv [% ] = N F N F N F 100 ,

(2.7)

unde NFa si NF sunt valorile numarului NF exprimate n cele doua baze. Pe de alta parte daca numarul convertit n baza are n F ranguri atunci erel conv se poate exprima ca fiinde rel conv [% ] = 1 nF 100

(2.8)

relatie din care rezulta numarul minim de ranguri n F , log erel conv daca erel conv = k , k N nF [ log e rel conv ] + 1 daca e rel conv k , k N

(2.9)

undee rel conv = e rel conv [%] 100

(2.10)

Combinnd relatiile (2.6) si (2.9) rezulta

13.01.2004

14 / 104


1 = k daca N F = M k , M , k N n F ( log erel conv ) daca e rel conv = k , k N (2.11) k ([ log e rel conv ] + 1) daca e rel conv , k N Din prezentarea efectuata rezulta ca numarul de pozitii binare pentru partea ntreaga se poate determina ntotdeauna cu exactitate apriori, n timp ce pentru partea fractionara acest lucru este posibil numai daca este respectata conditia in relatia (2.6).

Exemple a. Sa se converteasca n binar numarul N10 = 98.4352 cu o eroare erelconv < 0.82 % n caz ca nu este respectata conditia (2.6). 1. Se determina numarul de pozitii binare n I necesare pentru conversia partii ntregi: Deoarece 98 nu este o putere ntreaga a lui 2 n 1 = [log2 98]+1=[6.6147]+1=7 biti 2. Se converteste partea ntreaga: NI =98 98 = 2 x 49 + 0 ? a0 = 0 49 = 2 x 24 + 1 ? a1 = 1 24 = 2 x 12 + 0 ? a2 = 0 12 = 2 x 6 + 0 ? a3 = 0 6=2x 3+0 ? a4 = 0 3 = 2 x 1 + 1? a5 = 1 1 = 2 x 0 + 1? a6 = 1 Rezulta pentru partea ntreaga (NI)2 =1100010. 3. Deoarece conditia (2.6) nu este ndeplinita conversia se va face pe 6 ranguri pentru partea fractionara. si eroarea nu este o putere a bazei 2 rezulta n F = [-log2 0.0082] + 1 = [6.9301] + 1 = 8 biti Se converteste partea fractionara (NF)10 =0.4352.

13.01.2004

15 / 104


0.4352 x 2 = 0.8704 0.8704 x 2 = 1.7408 0.7408 x 2 = 1.4816 0.4816 x 2 = 0.9632 0.9632 x 2 = 1.9264 0.9264 x 2 = 1.8528 0.8528 x 2 = 1.7056 0.7056 x 2 = 1. 4112

? ? ? ? ? ? ? ?

a-1 = 0 a-2 = 1 a-3 = 1 a-4 = 0 a-5 = 1 a-6 = 1 a-7 = 1 a-8 = 1

Rezulta pentru partea fractionara (NF)2 =0.11100000 Pentru numarul N rezulta (N)2 =1100010.01101111. 4. Verificarea se realizeaza procedndu-se la conversia inversa, cu metodei substitutiei: (N)10 = 1x26 +1x25 +0x24 +0x23 +0x22 +1x21 +0x20 +0x2-1 +1x2-2 + -3 -4 +1x2 +0x2 +1x2-5 +1x2-6 +1x2-7 +1x2-8 =64+32+2+0.25+0.125+ +0.03125+0.0015625+0.0078125 = 98.43359375 0.4352 0 .4336 5. erel conv [% ] = 100 = 0 .367 % 0.4352 Observatie Rezultatul pentru partea zecimala este corect, ntruct s-a procedat la o rotunjire prin adaos a numarului de ranguri binare pentru aceasta parte. b. Sa se converteasca n octal numarul N10 = 234.128 cu o eroare < 0.42 % n caz ca nu este respectata conditia (2.6). 1. Se determina numarul de pozitii octale n I necesare pentru conversia partii ntregi: Deoarece 234 nu este o putere ntreaga a lui 8 n 1 = [log8 234]+1=[2.623]+1=3 cifre 2. Se converteste partea ntreaga: NI =234 234 = 8 x 29 + 2 ? a0 = 2 29 = 8 x 3 + 5 ? a1 = 5 3 = 8 x 0 + 3? a2 = 3

13.01.2004

16 / 104


Rezulta pentru partea ntreaga (NI)8 =352 3. Deoarece conditia (2.6) nu este ndeplinita ee converteste partea fractionara (NF)10 =0.128. 0.128 x 8 = 1.024 ? a-1 = 1 0.024 x 8 = 0.192 ? a-2 = 0 0.192 x 8 = 1.536 ? a-3 = 1 Rezulta pentru partea fractionara (NF)8 =0.101 Pentru numarul N rezulta (N)2 =352.101 4. Verificarea se realizeaza procedndu-se la conversia inversa, cu utilizarea metodei substitutiei: N10 3x82 +5x81 +2x80 +1x8-1 +0x8-2 +1x8-3 = = 192+40+2+0.125+0.001953125=234.127 5. erel conv [% ] =0.128 0.127 100 = 0 .78 % 0.128

c. Sa se converteasca n baza 4 numarul N10 = 175.1285 cu 6 pozitii n partea zecimala n caz ca nu este respectata conditia (2.6). 1. Se determina numarul de pozitii n I necesare pentru conversia partii ntregi: Deoarece 175 nu este o putere ntreaga a lui 4 n 1 = [log4 175]+1=[3.7256]+1=4 cifre 2. Se converteste partea ntreaga: NI =234 175 = 4 x 43 + 3 ? a0 = 3 43 = 4 x 10 + 3 ? a1 = 3 10 = 4 x 2 + 2 ? a2 = 2 2=0x 2+2? a3 = 2 Rezulta pentru partea ntreaga (NI)4 = 2233

3. Deoarece conditia (2.6) nu este ndeplinita conversia partii (NF)10 =0.1285 fractionare se va face pe 6 ranguri

13.01.2004

17 / 104


0.1285 x 4 = 0.514 0.514 x 4 = 2.056 0.056 x 4 = 0.224 0.224 x 4 = 0.896 0.896 x 4 = 3.584 0.584 x 4 = 2.336

? ? ? ? ? ?

a-1 = 0 a-2 = 2 a-3 = 0 a-4 = 0 a-5 = 3 a-6 = 2

Rezulta pentru partea fractionara (NF)4 = 0.020032 Pentru numarul N rezulta (N)4 = 2233.020032 4. Verificarea se realizeaza procedndu-se la conversia inversa, cu utilizarea metodei substitutiei: N10 = 2x43 +2x42 +3x41 +3x40 +0x4-1 +2x4-2 +0x4-3 +0x4-4 +3x4-5 +2x4-6 = = 128+32+12+3+0.125+0.0029296875+0.00048828125=175.1284125 5. erel conv [% ] =0.1285 0.1284125 100 = 0.0077 % 0.1285

d. Sa se determine N2 = P6 x Q8 unde P6 = 125 si Q8 = 17. Sa se converteasca n baza 4 numarul N10 = 175.1285 cu 6 pozitii n partea zecimala n caz ca nu este respectata conditia (2.6). 1. P se converteste P prin metoda substitutieiP = (125 )6 = (1)6 (10 )2 + (2 )6 (10 )1 + (5 )6 (10 )0 6 6 6

dar

(1)6 = (1)10 , (2 )6 = (2 )10 , (5 )6 = (5 )10 (10) 6 = (6 )10n aceste conditii numarul P se va scrie2 0 P = (125 )6 = (1)10 (6 )10 + (2 )10 (6 )1 + (5)10 (6 )10 10 = 36 + 12 + 5 = (53)10

2. P se converteste Q prin metoda substitutiei0 Q = (17 )8 = (1)8 (10 )1 + (7 )8 (10 )8 8

13.01.2004

18 / 104


dar

(1)8 = (1)10 , (7)8 = (7)10 , (10)8 = (8)10n aceste conditii numarul Q se va scrie0 Q = (17 )8 = (1)10 (8)1 + (7 )10 (8)10 = 8 + 7 = (15)10 10

3. Se determina produsul N10 = P10 x Q10 N10 = 53 x 15 = 795 4. Pentru a se efectua mai putine mpartiri N se converteste mai nti n baza 16 prin mpartiri succesive 795 = 16 x 9 + B ? 49 = 16 x 3 + 1 ? 3 = 16 x 0 + 3 ? Rezulta (N)16 = 31B 5. Utiliznd echivalentele din Tabelul 2.1 se obtine (N)2 = 0011 0001 1011 6. Verificarea se realizeaza procedndu-se la conversia inversa, cu metodei substitutiei: (N)10 = 0x211 +0x210 +1x29 +1x28 +0x27 +0x26 +0x25 +1x24 +1x23 + 2 1 +0x2 +1x2 +1x20 = 512+256+16+8+2+1= 795 2.2.3. Operatii aritmetice n binar octal si hexazecimal Operatiile aritmetice elementare ntr-un SN cu baza o putere a lui 2 urmeaza aceleasi reguli ca n zecimal, cu luarea n consideratie a principiului de numarare specific fiecarui SN. Este de mentionat ca numaratoarea n sistemul zecimal este realizata prin utilizarea consecutiva a celor zece simboluri (0, 1, 2, , 9); epuizarea acestora conduce la introducerea simbolului 1 pe o pozitie mai la stnga si reluarea pe pozitia initiala a secventei de simboluri (10, 11, 12, , a0 = B a1 = 1 a2 = 3

13.01.2004

19 / 104


19). Procesul continua n mod similar prin adaugarea cifrelor 2, 3 , , 9. Cnd se ajunge la 9 n pozitia secunda se continua cu adaugarea unei noi pozitii la stnga s.a.m.d. 2.2.3.1. Operatii aritmetice n SN binar Dupa cum s-a aratat pentru reprezentarea unui numar n SN binar se folosesc simbolurile 0 si 1. Respectnd regula de numarare zecimala, n conditiile operarii n exclusivitate cu cele doua simboluri se obtine urmatoarea secventa: 0, 1, 10, 11, 100, 101, 110, 111 1000, 1001, 1010, n Tabelul 2.2 sunt prezentate regulile pentru adunare si nmultire n binar. Tabelul 2.2 Adunare + 0 1 0 0 1 1 1 10 x 0 1 nmultire 0 0 0 1 0 1

n continuare se prezinta cte un exemplu pentru fiecare dintre operatiile elementare (adunare, scadere, nmultire si mpartire).Adunare 1 0 11 0 11 . 10 1 10 + 1 1 01 1 11 . 01 1 01 11 0 01 0 11 . 00 0 11 Scadere 1 1 01 11 0 . 1 01 1 1 0 0 01 01 1 . 0 11 1 0 1 1 00 01 1 . 0 10 0 1

nmultire 10 11 . 11 x 1 11 . 01 1 011 11

mpartire 1 1 1 0 1 1 1 0 . 1 1 1 11 0 1 1 10 1 10 0 1 0 . 0 1 1 0 00 11 11

13.01.2004

20 / 104


00 000 01 01 111 10 11 11 1 01 11 1 10 01 11 000 11 1 00 11 10 . 00 11

11 01 00 10 011 1 101 00 110 1 110 1 000 0

2.2.3.2. Operatii aritmetice n SN octal Dupa cum s-a aratat pentru reprezentarea unui numar n SN octal se utilizeaza simbolurile 0, 1, 2, ,7. Aplicnd regula de numarare zecimala, n conditiile operarii n exclusivitate cu cele opt simboluri se obtine urmatoarea secventa: 0, 1,2,3,4,5,6,7 10, 11,12,13,,17 20,21,23,23,,27 .. n Tabelul 2.3 sunt prezentate regulile pentru adunare si nmultire n octal. + 0 1 2 3 4 5 6 7 0 1 2 3 0 1 2 3 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 5 6 7 10 6 7 10 11 7 10 11 12 4 4 5 6 7 10 11 12 13 5 5 6 7 10 11 12 13 14 6 6 7 10 11 12 13 14 15 7 7 10 11 12 13 14 15 16 x 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 2 0 2 4 6 10 12 14 16 3 0 3 6 11 14 17 22 25 Tabelul 2.3 4 5 6 0 0 0 4 5 6 10 12 14 14 17 22 20 24 30 24 31 36 30 36 44 34 43 52 7 0 7 16 25 34 43 52 61

Ca si n cazul precedent, n cele ce urmeaza se prezinta cte un exemplu pentru fiecare dintre operatiile elementare (adunare, scadere, nmultire si mpartire).

13.01.2004

21 / 104

Capitolul 2 - Bazele aritmetice ale calculatoarelor numerice Adunare 2 57 . 4 3 2 + 1 44 . 6 1 3 4 24 . 2 4 5 Scadere 4 1 23 . 5 16 5 67 . 3 07 3 3 34 . 2 07

nmultire 17 53 . 21 6 x 4.3 570 165 2

mpartire 76 32 1 . 5 42 : 2 3 . 11 7 6 3 2 1 5 4 . 2 23 1 1 71 33 32 0 5 . 3 2 =4 77 1 4 62 2 = 14 754 13 755 == 7 7 7 2 713 3 =63 70 46 22 15 46

76 55 0701 0 4 45 2552 1 0 4 4 5 . 25 5 2

2.2.3.3. Operatii aritmetice n SN hexazecimal Reprezentarea unui numar n SN cu baza 16 (hexazecimal) implica utilizarea simbolurilor 0, 1, 2, ,7, 8, 9, A, B, C, D, E, F. Prin aplicarea regulii de numarare zecimala, n conditiile operarii cu cele 16 simboluri specifice rezulta urmatoarea secventa: 0, 1, 2, 3, 4, 5, 6 ,7, 8, 9, A, B, C, D, E, F 10, 11,12,13,,1D, 1E, 1F 20,21,23,23,,2f .. n Tabelele 2.4 si 2.5 sunt prezentate regulile pentru adunare si nmultire n hexazecimal. Tabelul 2.4 + 0 1 2 3 4 5 6 7 8 9 A B C D E F 2 3 4 5 6 7 8 9 A B C D E F 0 0 1

13.01.2004

22 / 104


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

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

2 3 4 5 6 7 8 9 A B C D E F 10

3 4 5 6 7 8 9 A B C D E F 10 11

4 5 6 7 8 9 A B C D E F 10 11 12

5 6 7 8 9 A B C D E F 10 11 12 13

6 7 8 9 A B C D E F 10 11 12 13 14

7 8 9 A B C D E F 10 11 12 13 14 15

8 9 A B C D E F 10 11 12 13 14 15 16

9 A B C D E F 10 11 12 13 14 15 16 17

A B C D E F 10 11 12 13 14 15 16 17 18

B C D E F 10 11 12 13 14 15 16 17 18 19

C D E F 10 11 12 13 14 15 16 17 18 19 1A

D E F 10 11 12 13 14 15 16 17 18 19 1A 1B

E F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C

F 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 1A 1A 1B 1B 1C 1C 1D 1D 1E

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

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

20 2 4 6 8 A C E 10 12 14 16 18 1A 1C 1E

30 3 6 9 C F 12 15 18 1B 1E 21 24 27 2A 2D

40 4 8 C 10 14 18 1C 20 24 28 2C 30 34 38 3C

5

6

70 7 E 15 1C 23 2A 31 38 3F 46 4D 54 5B 62 69

8 90 8 10 18 20 28 30 38 40 48 50 58 60 68 70 78 0 9 12 1B 24 2D 36 3F 48 51 5A 63 6C 75 7E 87

A0 A 14 1E 28 32 3C 46 50 5A 64 6E 78 82 8C 96

B

Tabelul 2.5 C D E F

0 0 5 6 A C F 12 14 18 19 1E 1E 24 23 2A 28 30 2D 36 32 3C 37 42 3C 48 41 4E 46 54 4B 5A

0 0 0 0 0 B C D E F 16 18 1A 1C 1E 21 24 27 2A 2D 2C 30 34 38 3C 37 3C 41 46 4B 42 48 4E 54 5A 4D 54 5B 62 69 58 60 68 70 78 63 6C 75 7E 87 6E 78 82 8C 96 79 84 8F 9A A5 84 90 9C A8 B4 8F 9C A9 B6 C3 9A A8 B6 C4 D2 A5 B4 C3 D2 E1

n continuare se prezinta cte un exemplu pentru fiecare dintre operatiile elementare (adunare, scadere, nmultire si mpartire) efectuate n SN hexazecimal.

13.01.2004

23 / 104

Capitolul 2 - Bazele aritmetice ale calculatoarelor numerice Adunare 7FA 4 + 52 1D D1 C 1 Scadere C4 1 2 A FB 5 1 4 5D

nmultire 1 4A. 2 F x B.1 1 4A 2 F

E3 00 5E 4 4A 7 F E4 4 . A7 F

mpartire A 5 7 BF 3A 74 2 DA 6 . 9A 3 17 2F2 = 25B 24 4 =1 7F 1 5C 23 0 20A 260 244 1C

2.3. Reprezentarea numerelor n calculator Uzual un echipament de calcul numeric preia datele si ofera rezultatele ntr-o forma accesibila utilizatorului. n ceea ce priveste prelucrarea, aceasta presupune exprimarea datelor ntr-o forma specifica procesorului. n consecinta exista doua formate de reprezentare a numerelor n calculator si anume formatul intern si formatul extern. Pentru reprezentarea interna se utilizeaza SN binar n mai multe forme diferentiate de solutia aleasa pentru indicarea pozitiei virgulei si semnului numarului. n acest sens pozitia fixa sau variabila a delimitatorului fractionar (punct sau virgula) determina reprezentarea n virgula fixa sau respectiv n virgula mobila. 2.3.1. Reprezentarea numerelor n virgula fixa

13.01.2004

24 / 104


n calculator se opereaza cu numere de lungime fixa, numarul de pozitii binare fiind determinat de lungimea registrelor de memorare. n formatul virgula fixa, virgula (punctul zecimal) nu este reprezentata fizic n calculator, pozitia sa fiind stabilita prin proiectare si neputnd fi schimbata. Uzual virgula se considera plasata n fata celei mai semnificative cifre a numarului, n aceste conditii numerele cu care se opereaza fiind subunitare. Observatie importanta. Numarul de biti pe care se reprezinta un numar este finit si fix, stabilindu-se n faza de proiectare a calculatorului. Din acest motiv n calculator nu se poate reprezenta dect un numar finit de valori, care pot fi interpretate diferit n cele doua formate (intern sau extern). Numerele care se pot reprezenta n calculator se numesc numere cu precizie finita (NPF) si au proprietati diferite fata de numerele din matematica. n cazul acestora poate aparea depasirea capacitatii de memorare deoarece NPF au un domeniu finit de valori, n sensul ca nu pot exista numere orict de mari sau orict de mici. Depasirile pot fi detectate hardware sau software. Urmatorul exemplu demonstreaza ca n cadrul NPF nu este valabila proprietatea de asociativitate. s Fie o masina cu urmatorul format admisibil: n care se pot reprezenta numere ntregi cuprinse ntre 999 si +999. Fie a = 600, b=500, c=400 n aritmetica clasica a+(b-c) = (a+b)-c respectiv 600+(500-400) =700 si (600+500)-400=700 asociativitatea fiind respectata. n cazul NPF (calculatoare) a+(b-c) = 600+(500-400) = 700, iar (a+b)-c = (600+500) - 400 = eroare. 1100 - depasire Numerele ntregi fara semn se reprezinta prin corespondentul lor binar (codul direct) numarul de biti pentru reprezentarea unui numar N fiind 2 n-1 N < 2 n . Pentru numerele cu semn exista trei reprezentari mai des utilizate si anume:

13.01.2004

25 / 104


1. semn marime; 2. complement fata de 2; 3. complement fata de 1. nainte de a trata fiecare mod de reprezentare se va defini notiunea de complement al unui numar N scris ntr-o baza b. a) Se numeste complement fata de baza b a numarului (N)b numarul ( N ) b definit prin relatia( N ) b = b n (N )b .

(2.12)

b)

Se numeste complement fata de b-1 a numarului (N)b( N ) b = b n (N )b b m .

numarul ( N )b definit prin relatia (2.13)

n relatiile de mai sus n si m reprezinta numarul de cifre ale partii ntregi respectiv fractionare ale numarului N iar b este baza SN n care se reprezinta numarul. Exemple a. Sa se determine C10 si C9 pentru numarul (N)10 = 175.32 n SN zecimal C10 = N = 10 n N si C 9 = N = 10 n N 10 mC10 (175 .32) = N = 10 3 175 .32 = 824 .68 C 9(175.32) = N = 10 3 175 .32 10 2 = 824 .67

b. Sa se determine C2 si C1 pentru numarul (N)2 = 1011.11 n SN binar C 2 = N = 2 n N si C1= N = 2 n N 2 mC 2(1011 .11) = N = 2 4 1011 .11 =10000 .00 1011 .11 = 0100 .01 C1(1011 .11) = N = 2 4 1011.11 2 2 = 10000 .00 1011 .11 0.01 = = 10000 .00 1100 .00 = 0100 .00 Daca n este numarul de cifre binare ale unui numar, atunci cel mai mare numar pozitiv care poate fi reprezentat este

13.01.2004

26 / 104


N = 2n 1,n

(2.14)

numarul de valori distincte fiind 2 . Pentru exemplificare n Tabelul 2.6 se prezinta valori tipice pentru n si 2 n si N. Tabelul 2.6 n= 2n = numar de valori N = valoarea maxima numar distincte reprezentabila de biti 8 256 255 16 65,536 65,535 32 4,294,967,296 4,294,967,295 64 1,844,674,407,370,955,616 1,844,674,407,370,955,615 n general domeniul finit de valori pentru numerele ntregi, reprezentate n formatul cu virgula fixa este: (2.15) unde Vmin si Vmax sunt cea mai mica respectiv cea mai mare valoare care se pot reprezenta pe n biti. Cele 2n valori distincte pot constitui reprezentari ale unor numere ntregi pozitive sau negative. 2.3.1.1. Reprezentarea unui numar prin marime si semn Scrierea unui numar prin marime si semn (sau n cod direct) este data de relatiaN = an 2 +n

D = [Vmin ,Vmax ] Z ,

i =m

a 2i

n1

i

(2.16)

unde a n este bitul de semn, iar a i sunt bitii numarului N. n privinta semnului a n care ocupa bitul cel mai semnificativ (MSb Most Significant bit) conventia este urmatoarea: a n = 0, daca N 0 ; a n = 1, daca N < 0 . Considernd reprezentarea pe m+n biti, conform relatiei (2.16) primul bit din stnga este asociat semnului, iar restul de n+m-1 biti contin marimea numarului egala cu reprezentarea binara a valorii N- figura 2.1.

13.01.2004

27 / 104


s 1

M marime n+m-1 biti

Fig. 2.1. Reprezentarea semn marime pe n+m biti.

Exemple a) + 9 = 0 1001 valoarea numarului bitul de semn b) - 6 = 1 0110 valoarea numarului bitul de semn c) -0.6875 = 1 1011 valoarea numarului bitul de semnReprezentarea semn marime prezinta avantajul apropierii de scrierea naturala, nsa din punctul de vedere al realizarii calculelor prezinta unele dezavantaje. Acestea se refera n primul rnd la necesitatea examinarii nainte de realizarea unei operatii (adunare sau scadere) a bitului de semn. Pe de alta parte, unitatea aritmetica se poate mult simplifica daca este orientata numai catre operatia de adunare. Acest deziderat se poate realiza prin alegerea convenabila a reprezentarii numerelor, recomandabila fiind reprezentarea n C2 (complement fata de 2). Un alt dezavantaj important este legat de reprezentarea numarului zero care este afectata de semn respectiv

[+0] d = 0 000 000 ; [- 0]d = 1 000 000 . Aceasta dubla reprezentare face ca un numar N ntreg reprezentat n cod direct pe n ranguri sa poata lua valori n gama 2 n1 + 1 N 2 n1 1 ,

(2.17)

ceea ce, de exemplu, face ca pentru

13.01.2004

28 / 104


-

n=8 domeniul de reprezentare sa fie D = [ 127 ,+127 ] Z ;

n=16 domeniul de reprezentare sa fie D = [ 32767 ,+32767 ] Z .

2.3.1.2. Reprezentarea unui numar n complement fata de 1 (cod invers) Pentru numere pozitive N 0 reprezentarea n complement fata de 1 este identica cu reprezentarea semn marime. Daca N < 0, atunci bitul de semn s = 1 siC1( N ) = 2 n1 1 N ,

(2.18)

unde n-1 este numarul de biti utilizati pentru reprezentarea marimii (fara semn). Calculul C(1) se poate face prin doua metode si anume: a. utiliznd definitia, respectiv

s =1 C1( N ) = 2n 1 1 N ; b. prin inversarea bitilor reprezentarii cu semn a valorii absolute |N| a numarului N.

Exemple Fie n = 7 si N = -123; sa se calculeze prin cele doua metode -1 C1(N) a. |N| = 123; C1(|N|) = 27 1 123 = 128 1 123 = 4 =0000 100 C1(N) = 1 0000100 = (1x27 + 1x22 )10 = (132) 10 b. (|N|) d = 0 1111011 C1(N) = 1 0000100 (s-a inversat fiecare bit).n ceea ce priveste reprezentarea numarului zero si n acest caz aceasta este afectata de semn respectiv

[+0] i = 0 000 000 ; [- 0]d = 1 111 111 . Aceasta dubla reprezentare face ca un numar N ntreg reprezentat n cod direct pe n ranguri sa poata lua valori n aceiasi gama ca n cazul codului direct. 2.3.1.3. Reprezentarea unui numar n complement fata de 2

13.01.2004

29 / 104


(cod complementar) Pentru numere pozitive N > 0 reprezentarea n complement fata de 2 este identica cu reprezentarile semn marime si n cod complementar fata de 1. Daca N < 0, atunci s = 1C 2( N ) = 2 n 1 N ,

(2.19)

unde n-1 este numarul de biti utilizati pentru reprezentarea marimii (fara semn). Calculul C(1) se poate face prin trei metode si anume: a. utiliznd definitia, respectiv

s = 1 C 2 ( N ) = 2n 1 N ; b. prin inversarea bitilor reprezentarii cu semn a valorii absolute |N| a numarului N la care se adauga 1, n pozitia cea mai putin semnificativa;

c. prin analiza de la dreapta la stnga a reprezentarii cu semn a valorii absolute |N| a numarului N. Primii biti de 0 si primul bit de 1 se lasa neinversati, apoi se inverseaza toti bitii, inclusiv bitul de semn (daca primul bit ntlnit este 1 se lasa neschimbat numai acesta). Exemple 1. Fie n-1 = 7 si N = -123; sa se calculeze prin cele trei metode C2(N) a. |N| = 123; M = 27 123 = 128 123 = 5 C2(N) = 1 0000101 b. (|N|) d = 0 1111011 C1(N) = 1 0000100 + (s-a inversat fiecare bit). 1 C2(N) = 1 0000101 c. 1. (|N|) d = 0 1111011 2. se analizeaza bitii de la dreapta spre stnga si se inverseaza C2(N) = 1 000010 1 bit neschimbat

13.01.2004

30 / 104


biti inversati 2. Fie n = 7 si N = -96; sa se calculeze prin cele trei metode -1 C2(N) a. |N| = 96; M = 27 96 = 128 96 = 32 C2(N) = 1 0100000 b. (|N|) d C1(N) C2(N) c. 1. (|N|) C2(N) = = = 0 1100000 1 0011111 + (s-a inversat fiecare bit). 1 1 0100000

= 0 1 100000 = 1 0 100000 biti neschimbati biti inversati

2. se analizeaza bitii de la dreapta spre stnga si se inverseaza

Reprezentarea n complement fata de 2 este cea mai utilizata pentru numerele algebrice datorita n primul rnd faptului ca elimina ambiguitatile legate de reprezentarea numarului zero. n C2 numarul zero are o reprezentare unica si anume [0] c = 0 000 000 . Aceasta unica reprezentare face ca un numar N ntreg reprezentat n cod complementar pe n ranguri sa poata lua valori n gama 2 n 1 N 2 n1 1

,

(2.20)

ceea ce va implica, de exemplu, pentru - n=8 domeniul de reprezentare sa fie D = [ 128 , + 127 ] Z ; -

n=16 domeniul de reprezentare sa fie D = [ 32768 ,+32767 ] Z . 2.3.1.4. Reprezentarea n exces

Necesitatea acestui tip de reprezentare este impusa de anumite avantaje pe care le ofera tratarea numerelor fara semn. Ideea care sta la baza acestei reprezentari cunoscuta si sub denumirea de reprezentare deplasata consta n adunarea la fiecare numar a unui exces reprezentat de regula de cel mai mic numar ntreg negativ care se poate reprezenta n calculator.

13.01.2004

31 / 104


De exemplu n reprezentarea C2 pe un octet domeniul D = [ 128 , + 127 ] Z se transforma prin adunarea excesului 128 nDexces 128 = [0 , + 255 ] Z . n aceste conditii celui mai mic numar negativ (-128)10 i va corespunde (00000000) 2 iar celui mai mare numar pozitiv (+127) 10 i va corespunde (11111111) 2 . Aceasta reprezentare simplifica efectuarea operatiei de comparare a numerelor, ceea ce este esential pentru realizarea hardware-ului implicat n operarea exponentilor la reprezentarea n virgula mobila. * * * Dupa cum s-a vazut prin reprezentarea n format virgula fixa se precizeaza un numar de ranguri la stnga virgulei pentru partea ntreaga, respectiv la dreapta acesteia pentru partea fractionara. n aceste conditii gama si precizia de reprezentare sunt determinate de numarul de ranguri. De exemplu pe 40 de ranguri pot fi manevrate numere de ordinul trilioanelor (1012 ) precizia fiind de o trilionime. Solicitari suplimentare ar putea fi rezolvate prin cresterea numarului de ranguri, aspect care nu este posibil ntruct acest numar este fixat pentru un anumit tip de calculator.

2.3.2. Reprezentarea numerelor n virgula mobila Necesitatea reprezentarii n calculator a numerelor foarte mari sau foarte mici, cu o precizie ridicata a condus la reprezentarea n virgula mobila (VM) . Reprezentarea n format VM utilizeaza reprezentarea stiintifica r = m x bE careia i sunt asociate trei componente: b baza; E exponentul; care indica ordinul de marime al numarului; m mantisa asociata marimii exacte a numarului ntr-un anumit domeniu.

13.01.2004

32 / 104


Exemple 6.342 = 0.6342 x 101 = 6.342 x 100 ; 0.0057 = 0.57 x 10-2 = 5.7 x 10-3 ; 5760 = 0.576 x 104 = 5.76 x 103 . Consideram ca pentru reprezentarea unui numar n virgula mobila se utilizeaza n biti din care e pentru exponent (care determina intervalul de valori) si m biti pentru mantisa (care determina precizia reprezentarii). Dupa cum se stie cu n biti se pot reprezenta 2n numere reale. ntre numere reale din matematica si numerele reale reprezentate n formatul cu virgula mobila exista diferente legate de domeniul finit si multimea discreta de valori. Domeniul finit de valori este determinat de capacitatea fizica limitata a memoriei calculatorului. Pentru a vedea cum se poate determina acest domeniu vom considera o masina ipotetica zecimala (baza de numeratie este 10) n care: - mantisa m este subunitara si pozitiva respectiv, 0 m < 1; - mantisa se reprezinta ca un numar cu semn si trei cifre, n domeniul 0.1 m < 1 sau zero; - exponentul se reprezinta ca un numar cu semn si doua cifre. Structura unui numar cu caracteristicile expuse precum si valorile pozitive minima si maxima sunt: mantisa exponent Structura: ? ? ? ? ? ? Vmin = - 99 9 - 99 = - 0.999 x 10-99 ; Vmax = +9 9 9 + 99 = + 0.999 x 10+99. Numarul de mantise pozitive distincte este Nm = 1800 {900 pentru m[999 , -100] Z si 900 m [+100 , +999] } Z, iar numarul de exponenti este Ne = 199 (toate valorile ntregi intre 99 si +99 inclusiv 0 ), deci rezulta ca n acest format se pot reprezenta n total N numere (pozitive si negative) N=Nm x Ne + 1 = 1800x199 + 1 = 358201 numere. O reprezentare a valorilor limite pe axa reala permite evidentierea situatiilor in care se produce depasire. Determinarea valorilor Vmin si Vmax

13.01.2004

33 / 104


permite identificarea pe axa reala, figura 2.2, a domeniilor de valori reprezentabile.

(1)

(2)

(3) (4)

(5)

(6)

(7)

-Vmax- 0.999 10+99 - 10+99

-Vmin- 0.100 x 10 -10-100-99

0

+Vmin+ 0.100 10-99 +10-100

+Vmax+ 0.999 10+99 + 10 +99

Fig. 2.2. Domeniile valorilor reale reprezentabile n VM.

Zonele marcate cu cifre in figura 2.2 reprezinta urmatoarele categorii de numere: 1. numere negative mai mici dect - 0.999 x 10 +99 ( - 10+99 ) , dar foarte mari in valoare absoluta; 2. numere negative intre - 0.999 x 10 +99 si - 0.100 x 10 -99 (- 10+99, -10-100 ); 3. numere negative foarte mici cu valoare absoluta mai mica dect 0.100 x 10 -99 (10-100 ); 4. zero; 5. numere pozitive foarte mici cu valoare absoluta mai mica dect 0.100 x 10 -99 (10-100 ); 6. numere pozitive intre + 0.100 x 10 -99 si + 0.999 x 10 +99 (+ 10-100 , -10+99); 7. numere foarte mari in valoare absoluta, pozitive mai mari dect + 0.999 x 10 +99 (+10+99); Domeniul de reprezentare va fi format din zonele ( numere 2 negative) si (6 - numere pozitive) la care se adauga zona 4 reprezentata de numarul zero. Daca n urma unei operatii aritmetice rezulta o valoare n zonele (1) sau (7) apare depasirea flotanta (inferioara daca rezultat < -Vmin sau superioara daca rezultat > +Vmax). Daca rezultatul se situeaza n zonele (3) sau (5) se semnalizeaza imposibilitatea reprezentarii pentru ca numerele sunt prea mici (negative zona 3, pozitive zona 5).

13.01.2004

34 / 104


Caracterul discret al reprezentarii n virgula mobila este dat de faptul ca multimile din zonele ( si (6) ale schemei din figura 2.2 sunt 2) multimi finite. Avnd n vedere ca multimea numerelor reale este o multime continua (ntre orice doua numere reale se gaseste o infinitate de asemenea numere) rezulta ca nu exista o corespondenta biunivoca ntre aceasta multime si multimea numerelor reprezentabile n virgula mobila. Numarul de cifre al mantisei determina precizia de reprezentare n domeniile 2 si 6 in timp ce numarul de cifre al exponentului afecteaza marimea acelorasi domenii. Mantisa se reprezinta uzual in forma normalizata (prima cifra din stnga diferita de zero) si intr-una din bazele 2, 4, 8, 16. Pentru a nu folosi exponenti negativi se introduce notiunea de caracteristica. Aceasta este egala cu exponentul cu semn deplasat, astfel nct sa ia valori intr-o multime de numere pozitive. De exemplu pentru un exponent in domeniul [-64, +63]Z, o deplasare cu +64 va conduce la o caracteristica in domeniul [0, +127]Z. Stabilirea formatului de reprezentare a numerelor reale n virgula mobila a constituit obiectul a numeroase studii care s-au concretizat n elaborarea n anul 1985 a standardului IEEE1 754. Astfel au fost alese doua forme standard: 00

formatul scurt sau de baza ( figura 2.3) , pe un cuvnt de 32 de biti care asigura o viteza mai mare de operare;01 08 09 31

s 1 bit

e 8 biti

f 23 biti

Fig. 2.3. Formatul scurt n VM al Standardului IEEE 754.

-

formatul lung sau dublu de baza ( figura 2.4), pe un cuvnt de 64 de biti care asigura o precizie mai mare de lucru.00 01 11 12 63

s 1 bit1

e 11 biti

f 52 biti

Fig. 2.4. Formatul lung n VM al Standardului IEEE 754. IEEE - Institute of Electrical and Electronics Engineers www.ieee.org

13.01.2004

35 / 104


n formatul scurt (simplu de lucru) semnificatiile sunt urmatoarele: - bitul 00: s = semnul mantisei (s = 1 mantisa negativa ); - bitii 01- 08: e = exponentul deplasat (deplasarea este 27 1 = 127); - bitii 09 - 31: f = mantisa normalizata/ fractia 2 . Valoarea unui numar r reprezentat ntr-un asemenea format este: daca e = 255 si f ? 0 atunci r = NAN (nu este un numar Not A Number); daca e= 255 si f = 0 atunci r = ( 1)s ; daca 0 < e < = 255 atunci; r = ( 1)s 2e (27

1

daca e= 0 si f ? 0 atunci ; r = ( 1)s 2 126 (0 . f ) daca e= 0 si f = 0 atunci r = ( 1)s 0 ( zero ) .

) (1. f ) ;(2.21)

n particular se obtin urmatoarele reprezentari n format scurt 0 00000000 00000000000000000000000 = +0 1 00000000 00000000000000000000000 = -0 0 11111111 00000000000000000000000 = +8 1 11111111 00000000000000000000000 = -8 0 11111111 00000100000000000000000 = NaN 1 11111111 00100010001001010101010 = NaN 0 10000000 00000000000000000000000 = +1 * 2**(128-127) * 1.0 = 2 0 00000001 00000000000000000000000 = +1 * 2**(1-127) * 1.0 = 2**(-126) 0 00000000 10000000000000000000000 = +1 * 2**(-126) * 0.12

cnd e?0, se presupune un bit egal cu 1 la stnga lui f; virgula se considera plasata ntre acest bit si primul bit explicit al mantisei.

13.01.2004

36 / 104


= 2**(-127) 0 00000000 00000000000000000000001 = +1 * 2**(-126) * 0.00000000000000000000001 = 2**(-149) (Cea mai mica valoare pozitiva) Conform relatiei (2.21) marimea numerelor reprezentate este n gama . 2 126 (1.0) r 2127 2 2 23

(

)

n formatul lung (dublu de baza) semnificatiile sunt urmatoarele: - bitul 00: s = semnul mantisei (s = 1 mantisa negativa ); - bitii 01 - 11: e = exponentul deplasat (deplasarea este 210 1 = 1023); - bitii 12 - 63: f = mantisa normalizata/ fractia 3 . Valoarea unui numar r reprezentat ntr-un asemenea format este: - daca e = 2047 si f ? 0 atunci r = NAN (nu este un unumar Not A Number); - daca e= 2047 si f = 0 atunci r = ( 1)s ; gama daca 0 < e < = 2047atunci; r = ( 1)s 2 e (210

1

daca e= 0 si f ? 0 atunci r = ( 1)s 2 1022 (1 + f ) ; daca e= 0 si f = 0 atunci r = ( 1)s 0 ( zero ) .

) (1+ f ) ;(2.21)

Conform relatiei (2.21) marimea numerelor reprezentate este n 2 126 (1.0) r 2127 2 23

(

)(2.22)

10 r = ( 1)s 2e (2 1) (1 + f ) , cu conditon e 0

Conform relatiei (2.21) marimea numerelor reprezentate este n gama 2 1022 (1.0) r 21023 2 52 .

(

)

3

idem 2.

13.01.2004

37 / 104


Conform relatiei (2.21) marimea numerelor reprezentate este n gama . 2 126 (1.0) r 2127 2 23 Exemplu Sa se reprezinte n formatul scurt numarul r= -348.562510 ,. a. se converteste r in baza 2 348 = 174 x 2 + 0 174 = 87 x 2 + 0 87 = 43 x 2 + 1 43 = 21 x 2 + 1 21 = 10 x 2 + 1 rI = 101011100 10 = 5 x 2 + 0 5= 2x2+1 2= 2x1+0 1= 0x2+1 0.5625 x 2 = 1.125 0.1250 x 2 = 0.250 0.2500 x 2 = 0.500 rF = 0.1001 0.5000 x 2 = 1.000 r =1010 11100.1001 se trece rezultatul in forma normalizata r =1.0101 1100 1001 0000 0000 000 x 28 (pentru a se obtine mantisa pe 23 de biti s-a completat doua grupe de cte 4 si o grupa cu 3 de zero; c. se reprezinta n VM s = 1 (negativ) e = 127 + 8 = 13510 = 8716 = 1000 01112 f = 0101 1100 1001 0000 0000 000 Rezulta reprezentarea in virgula mobila r = 1 1000 0111 0101 1100 1001 0000 0000 000 d. Verificare b.

(

)

13.01.2004

38 / 104


r = (-1)1 x 2135-127 x 1. 0101 1100 1001 0000 0000 000 1. 1101 1100 1001 0000 0000 000 = 1+2-1 +2-2 +2-4 +2-5 +2-6 +2-9 +2-12 = 1+0.25+0.0625+0.03125+0.015625+0.001953125+ +0.000244140625=1.361572265625 r = (-1)1 x 28 x 1.361572265625=-256x1.361572265625=348.5625 naintea unor consideratii referitoare la precizia de reprezentare, ctiva termeni si concepte specifice erorilor de calcul, dintre care cu o parte s-a operat n subcapitolele precedente. Precizia constituie un termen asociat cu lungimea cuvntului, respectiv numarul de biti disponibili pentru reprezentarea numarului. De exemplu, n cazul unui registru de 8 biti, considernd ca se reprezinta numai numere naturale precizia de reprezentare va fi de 1/2 8 respectiv 1/256. Acuratetea reprezinta o masura a apropierii unei aproximari fata de valoarea exacta. De exemplu numarul 12 se exprima exact pe 4 biti (1100) iar numarul 0.66650390625 pe 11 biti (0.10101010101- partea fractionara. Daca se impune n acest din urma caz o reprezentare pe 8 biti se obtine 0.10101010 (echivalent reprezentare 0.6640625). Dupa cum se observa a doua reprezentare este mai precisa (8 biti n loc de 4) dar are o acuratete mai mica. Gama reprezinta multimea numerelor reprezentabile ntr-un sistem dat. De exemplu pentru reprezentarea numerelor ntregi n C2 pe patru biti, aplicnd relatia (2.20) se obtine gama [-8,7]nZ. Rezolutia constituie marimea diferentei (respectiv a distantei ) dintre doua numere adiacente. n cazul reprezentarii n virgula fixa aceasta distanta este constanta n interiorul gamei, n timp ce la reprezentarea n virgula mobila distanta este variabila si depinde de marimea exponentului. Trunchierea (rotunjirea prin lipsa) este un procedeu utilizat atunci cnd precizia nu este suficienta pentru reprezentarea numarului dat. De exemplu daca se doreste reprezentarea numarului pi = 3.141592654 ntr-un dispozitiv capabil sa memoreze numai 6 cifre zecimale, atunci

13.01.2004

39 / 104


numarul pi1 = 3.14159 va reprezenta numarul pi cu e eroare de trunchiere de 0.000002654. Rotunjirea este metoda de selectie a celei mai apropiate valori de valoarea initiala a numarului. n zecimal, daca cifra aflata la dreapta ultimei cifre care se poate reprezenta este = 5, atunci ultima cifra reprezentabila se incrementeaza cu unu (n caz contrar aceasta ramne neschimbata). Erori specifice reprezentarii numerelor n virgula mobila. Datorita preciziei finite de reprezentare apar erori care pot fi acceptate sau nu de catre o aplicatie data. De exemplu diferenta 1000000-1 n VM va conduce tot la 1000000 n conditiile unei erori mai mari dect 1. La analiza reprezentarii n VM intereseaza urmatoarele aspecte: numarul numerelor reprezentabile; numarul care are valoarea/marimea cea mai mare; numarul diferit de zero care are valoarea/marimea cea mai mica; - determinarea celei mai mari distante dintre doua numere succesive; determinarea celei mai mici distante dintre doua numere succesive. Stabilirea numarului numerelor reprezentabile se face tinnd cont de numarul de valori pe care le pot lua cmpurile distincte ale reprezentarii n VM: - semnul poate lua doua valori; - numarul de exponenti este n exp= (E-e)+1, unde E, e sunt cel mai mare respectiv cel mai mic exponent; - primul rang al partii fractionare (mantisei) este b-1 unde b este baza; - celelalte ranguri ale mantisei b f-1 unde f este numarul rangurilor semnificative ale mantise n baza b; - zero. n aceste conditii pot fi reprezentateNrrepr = 2 ((E e ) + 1) (b 1) b f 1 + 1 ,

(2.23)

unde Nrepr este numarul de numere reprezentabile.

13.01.2004

40 / 104


Observatie n cazul exponentului nu toate combinatiile de biti sunt valide. De exemplu n standardul IEEE 754 , desi n simpla precizie sun rezervati 8 biti, cel mai mic exponent este 126 si nu 128, exponentii interzisi fiind pentru reprezentarile speciale zero si infinit. Cel mai mic numar reprezentabil Nmin (cu cel mai mare exponent b E si cea mai mare mai mica fractie normalizata b -1 ) va fiN min = b e 1 .

(2.24)

Cel mai mare numar reprezentabil Nmax (cu cel mai mare exponent b E si cea mai mica mai mica fractie normalizata diferita de zero b -1 ) va fiN max = b E 1 b f .

(

)

(2.25)

Cea mai mica distanta ntre doua numere consecutive Dmin care apare atunci exponentul are cea mai mica valoare b e si se modifica cel mai putin semnificativ bit al fractiei b -f va fiDmin = b e f .

(2.26)

Cea mai mare distanta ntre doua numere consecutive Dmax care apare atunci exponentul are cea mai mare valoare b E si se modifica cel mai putin semnificativ bit al fractiei b -f va fiDmin = b E f .

(2.27)

Exemplu Sa se determine elementele de mai sus urmatoarea reprezentare n VM (figura 2.5): - bit de semn; - exponent pe doi biti n exces 2; - fractie pe 3 biti normalizata fara 1 ascuns;00 01 02 03 05

s 1 bit

e 2 biti

f 3 biti

13.01.2004

Fig. 2.5. Formatul41 / 104 exemplu. VM pentru


Datele aferente reprezentarii vor fi: e=-2, E=1, nexp = (E-e)+1=4; multimea exponentilor va fi {-2, -1, 0, 1}4 ; cea mai mica fractie f min =b -1 =2 -1 =(0.5)10 =(0.100)2 ; cea mai mare fractie f max=1-b -f =1-2 -3 =(0.875)10 =(0.111)2; modulul celui mai mic numar reprezentabil1 N min = b e 1 = 2- 2-1 = 2 3 = = 0.125 10 0 10 = (0.001 2 0 ) 2 8 cel mai mare numar reprezentabilN max = b E 1 b f = 21 1 2 3 = 2 (2 0.125 ) = = 7 = (0.175 101 )10 = 0 .111 21 2 4

(

)

(

)

(

(

)

)

Nrrepr = 2 ((E e ) + 1) (b 1) b f 1 + 1 = 2 ((1 + 2) + 1) (2 1) 231 + 1 = 2 4 2 2 + 1 = 33 distanta minima ntre doua numere reprezentabile 1 Dmin = b e f = 2 23 = 2 5 = = (0 .03125 )10 = 32= (0 .00001 )2VF = 0.001 2 2 2VM

numarul reprezentarilor

(

)

distanta maxima ntre doua numere reprezentabile 1 Dmin = b E f = 213 = 2 2 = = (0.25)10 = 4= (0 .01)2VF = 0.010 21 2VM

(

)

2.3.3. Coduri numerice si alfanumerice

4

Cele 4 combinatii n binar vor fi 00, 01, 10, 11 sau avnd n vedere excesul se obtin exponentii 2, -1, 0, 1.

13.01.2004

42 / 104


Dupa cum s-a aratat calculatorul prelucreaza numere reprezentate n SN binar n timp ce utilizatorul uman opereaza curent cu numere exprimate n SN zecimal, cu cuvinte specifice unei anumite limbi, cu anumite semne grafice, etc. Pentru translatarea ntre celor doua maniere de reprezentare, evident fara alterarea continutului informational se utilizeaza codificarea. A codifica elementele unei multimi A prin elementele unei alte multimi B nseamna a realiza o corespondenta ntre fiecare element a A o secventa de elemente b B . Un cod este o functie f : A I unde I este multimea secventelor care se pot forma cu elemente din B. n ceea ce priveste multimea A acesta se numeste alfabet iar elementele acesteia (cifre, litere, semne de punctuatie etc.) sunt caractere. Codurile n care sunt reprezentate numai numere se numesc coduri numerice iar cele n care pe lnga numere contin si litere, caractere speciale etc. se numesc coduri alfanumerice. Avnd n vedere reprezentarea interna n cod binar, respectiv B = {0,1} , n continuare vor fi tratate coduri care codifica litere si cifre prin combinatii de elemente ale multimii B. Daca multimea A are un numar de N caractere, un caracter poate fi codificat printr-o secventa de n elemente din B dacaN 2n (2.28) Exemplu Sa se determine numarul minim de biti care pot codific a cele zece cifre ale SN zecimal.

Dinn log 2 10 =

relatia

(2.28)

rezulta

n log 2 N

respectiv

1 = 3.322 . n aceste conditii rezulta ca numarul minim de log 2 biti utilizati pentru codificarea unei cifre zecimale este n=4.

2.3.3.1. Coduri numerice Codurile binar-zecimale care asigura codificarea binara a numerelor zecimale pot fi ponderate sau neponderate. Codurile ponderate asociaza fiecarei cifre zecimale o tetrada binara, n care fiecare rang are o anumita pondere. Pentru exemplificare n

13.01.2004

43 / 104


Tabelul 2.7 se prezinta o serie de coduri numerice ponderate cu o frecventa mai ridicata de utilizare. Tabelul 2.7 Zecimal 8421 2421 4221 5421 7421 0 0000 0000 0000 0000 0000 1 0001 0001 0001 0001 0001 2 0010 0010 0010 0010 0010 3 0011 0011 0011 0011 0011 4 0100 0100 0110 0100 0100 5 0101 1011 1001 1000 0101 6 0110 1100 1100 1001 0110 7 0111 1101 1101 1010 0111 8 1000 1110 1110 1011 1001 9 1001 1111 1111 1100 1010 Codul 8421 este un cod n care cifrele binare de la stnga la dreapta au respectiv ponderile 2 3 , 22 ,21 , 20 . Codurile 2421 si 4221 se caracterizeaza prin utilizarea ponderii 2 n doua pozitii distincte ale tetradei, iar tetradele care reprezinta cifre zecimale a caror suma este egala cu 9 sunt complementare. O alta particularitate consta n faptul ca primele cinci tetrade au n prima pozitie 0 iar ultimele cinci au n aceiasi pozitie cifra 1. Codul 5421este caracterizat de faptul ca cifrele 5 se -9 deosebesc de cifrele 0-4 numai prin valoarea primului bit.

Codul 7421 utilizeaza ponderile 7, 4, 2, 1. Aceste ponderi introduc o ambiguitate n ceea ce priveste reprezentarea cifrei 7 (0111 sau 1000). Pentru nlaturarea acesteia se introduce o restrictie si anume considerarea combinatiei cu cei mai multi biti 1 respectiv 0111. Codurile neponderate nu presupun existenta cte unei ponderi care sa fie asociata fiecarei tetrade binare. n Tabelul 2.8 sunt prezentate cteva coduri neponderate create pornind de la considerente impuse de utilizarea lor. Tabelul 2.8 Zecimal Exces 3 Gray 2 din 5

13.01.2004

44 / 104


Zecimal Exces 3 Gray 2 din 5 0 0011 0000 00011 1 0100 0001 00101 2 0101 0011 00110 3 0110 0010 01001 4 0111 0110 01010 5 1000 0111 01100 6 1001 0101 10001 7 1010 0100 10010 8 1011 1100 10100 9 1100 1101 11000 Codul Exces 3 se obtine din codul 8421 pri adunarea la fiecare tetrada a cifrei 3 (0011) n binar. Rezulta un cod cu proprietatea de autocomplementare5 din care s-a eliminat combinatia 00006 . Codul Gray se caracterizeaza prin aceea ca trecerea de la echivalentul binar al unei cifre zecimale la urmatorul se face prin modificarea unui singur rang binar. Codul 2 din 5 utilizeaza pentru codificarea cifrelor zecimale cinci pozitii binare, n conditiile n care fiecare combinatie trebuie sa contina cte doi biti unitari. Aceasta restrictie asigura unicitatea reprezentarii si creeaza posibilitatea controlului asupra transmisiei informatiilor codificate n acest mod.

2.3.3.2. Coduri alfanumerice Numarul limitat al caracterelor alfanumerice (spre deosebire de numerele reale la care gama este infinita) permite ca un ntreg set de caractere sa fie reprezentat pe un numar limitat de biti. n practica s-au impus doua sisteme de codificare a caracterelor alfanumerice ASCII si EBCDIC. Codul ASCII (American Standard Code for Information Interchange) utilizeaza pentru reprezentarea caracterelor alfanumerice cte 7 biti pe caracter. Tabelul 2.95 6

Doua tetrade ale caror echivalente zecimale nsumate dau 9 sunt complementare. Pentru a face distinctie ntre valoarea 0 si absenta unui semnal se exclude combinatia 0000.

13.01.2004

45 / 104

Capitolul 2 - Bazele aritmetice ale calculatoarelor numericeHEX DEC CHR CTRL HEX DEC CHR HEX DEC CHR HEX DEC CHR00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 NUL SOH STX ETX EOT ENQ ACK BEL BS HT LF VT FF CR SO SI DLE DC1 DC2 DC3 DC4 NAK SYN ETB CAN EM SUB ESC FS GS RS US ^@ Â ^B ^C ^D Ê ^F ^G ^H Î ^J ^K ^L ^M ^N Ô ^P ^Q ^R ^S ^T Û ^V ^W ^X ^Y ^Z 20 21 22 23 24 25 26 27 28 29 2A 2B 2C 2D 2E 2F 30 31 32 33 34 35 36 37 38 39 3A 3B 3C 3D 3E 3F 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 SP ! " # $ % & ' ( ) * + , ? . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? 40 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D 4E 4F 50 51 52 53 54 55 56 57 58 59 5A 5B 5C 5D 5E 5F 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ 60 61 62 63 64 65 66 67 68 69 6A 6B 6C 6D 6E 6F 70 71 72 73 74 75 76 77 78 79 7A 7B 7C 7D 7E 7F 96 97 98 99 100 101 102 103 104 105 106 107 108 109 100 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 ` a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~ DEL

7 Exista posibilitatea reprezentarii a 2 coduri, asignarea acestora la caractere valide fiind evidentiata n Tabelul 2.9 Codurile 00h 1Fh si 7Fh nu sunt afisabile fiind caractere de control utilizate pentru transmisie, controlul afisarii/tiparirii, ct si pentru alte scopuri, semnificatiile acestora fiind cuprinse n Tabelul 2.10.

13.01.2004

46 / 104


Tabelul 2.10CHR NUL SOH STX ETX EOT ENQ ACK BEL BS HT LF VTS emnificatie NULl S tart Of Heading S tart of TeXt End of TeXt End Of Transmission ENQuiry ACKnowledge BELl BackS pace Horizontal Tabulation Line Feed Vertical Tabulation

CHR FF CR SO SI DLE DC1 DC2 DC3 DC4 NAK SYN ETB

S emnificatie Form Feed Carriage Return S hift Out S hift In Data Link Escape Device Control 1 Device Control 2 Device Control 3 Device Control 4 Negative AcKnowledge SYNchronous idle End of Transmission Block

CHR CAN EM SUB ESC FS GS RS US SP DEL

S emnificatie CANcel End of Medium SUBstitution ESCape File S eparator Group separator Record separator Unit separator S Pace DELete

Toate celelalte caractere litere, cifre, semne de punctuatie, spatiul sunt reprezentabile. Tratarea cifrelor 0 9 este similara cu a literelor mici si mari ceea ce simplifica manipularea caracterelor7.

Codul EBCDIC (Extended Standard Code for Information Interchange) utilizeaza pentru reprezentarea caracterelor alfanumerice cte 8 biti pe caracter, permitnd codificarea a 256 caractere evidentiate n Tabelele 2.11.si 2.12..Adesea codul pe 7 biti este reprezentat pe un octet, MSb avnd semnificatia bitului de paritate.

7

Pentru a transforma reprezentarea alfanumerica a unei cifre n valoarea sa numerica se scade 30h iar pentru a transforma codul unei majuscule n codul corespunzator al minusculei se aduna 20h.

13.01.2004

47 / 104

Capitolul 2 - Bazele aritmetice ale calculatoarelor numerice Tabelul 2.11Dec Hex Code Dec Hex Code Dec Hex Code Dec Hex Code 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F IFS IGS IRS IUS CAN EM BS VT FF CR SO SI DLE DEL HT NUL SOH STX ETX 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 20 21 22 23 24 25 26 27 28 29 2A 2B 2C 2D 2E 2F 30 31 32 33 34 35 36 37 38 39 3A 3B 3C 3D 3E 3F SUB NAK EOT SYN ENQ ACK BEL LF ETB ESC 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 40 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D 4E 4F 50 51 52 53 54 55 56 57 58 59 5A 5B 5C 5D 5E 5F !] $ * ) ; ^ [ . < ( + |! & space 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 60 61 62 63 64 65 66 67 68 69 6A 6B 6C 6D 6E 6F 70 71 72 73 74 75 76 77 78 79 7A 7B 7C 7D 7E 7F : # @ = " | , % _ > ? /

13.01.2004

48 / 104

Capitolul 2 - Bazele aritmetice ale calculatoarelor numerice Tabelul 2.12Dec Hex Code Dec Hex Code Dec Hex Code Dec Hex Code 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 80 81 82 83 84 85 86 87 88 89 8A 8B 8C 8D 8E 8F 90 91 92 93 94 95 96 97 98 99 9A 9B 9C 9D 9E 9F j k l m n o p q r a b c d e f g h i 160 A0 161 A1 162 A2 163 A3 164 A4 165 A5 166 A6 167 A7 168 A8 169 A9 170 AA 171 AB 172 AC 173 AD 174 AE 175 AF 176 177 178 179 180 181 182 183 184 185 B0 B1 B2 B3 B4 B5 B6 B7 B8 B9 ~ s t u v w x y z 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 219 220 222 223 C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 CA CB CC CD CE CF D0 D1 D2 D3 D4 D5 D6 D7 D8 D9 DB DC DE DF } J K L M N O P Q R { A B C D E F G H I 224 225 226 227 228 229 230 231 232 233 E0 E1 E2 E3 E4 E5 E6 E7 E8 E9 S T U V W X Y Z \

234 EA 235 EB 236 EC 237 ED 238 EE 239 240 241 242 243 244 245 246 247 248 249 251 252 254 255 EF F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 FB FC FE FF 0 1 2 3 4 5 6 7 8 9

186 BA 187 BB 188 BC 189 BD 190 BE 191 BF

218 DA

250 FA

221 DD

253 FD

13.01.2004

49 / 104


2.3.3.3. Coduri detectoare si corectoare de erori n timpul transmisiei si prelucrarii datelor pot apare erori datorate, n primul rnd, zgomotelor care afecteaza nivelurile fizice de tensiune specifice semnalelor digitale. Pentru detectarea si eventual corectarea acestor erori se utilizeaza coduri cu proprietati speciale. Aceste coduri contin pe lnga bitii utili o serie de biti de control cu ajutorul carora se identifica si corecteaza eventualele erori de transmisie. Codurile detectoare de erori au urmatoarea proprietate: aparitia unei singure erori transforma un cuvnt valid intr-un cuvnt invalid. O metoda pentru detectia erorilor este metoda bitului de paritate a carui idee de baza consta n adaugarea unei cifre binare in plus la fiecare cuvnt al unui cod dat, pentru a face ca numarul de biti de 1 din fiecare cuvnt sa fie impar sau par. Este util sa definim distanta 8 dintre 2 coduri cuvnt ca numarul de cifre care trebuie sa fie schimbate intr-un cuvnt pentru a rezulta alt cuvnt. (de exemplu distanta Hamming a codului ASCII este 1). Un cod este cod detector de erori daca distanta sa minima este mai mare sau egala cu 2. De exemplu adaugarea unui bit de paritate plasat la stnga codului normal ASCII al unui caracter va determina pentru acest cod o distanta Hamming egala cu 2. Acest bit se calculeaza ca suma modulo 29 n cazul paritatii pare si cu valoarea negata a acesteia n cadrul paritatii impare procedeu ilustrat n figura 2.6.PI PP 26 25 24 23 22 21 20 Caracter

0 1

1 0

1 1

1 1

0 0

0 0

1 1

0 0

0 1

d e

Biti de paritate

Codul ASCII

Fig. 2.6. Adaugarea bitului de paritate la codul ASCII: PI paritate impara; PP paritate para.

Prin acest procedeu se va obtine o tabela a codurilor ASCII cu 256 de caractere dintre care jumatate sunt invalide. La receptie se recalculeaza

8 9

Aceasta distanta este cunoscuta ca distanta Hamming.0 0 = 0 0 1 = 1 1 0 = 1 1 1 = 0

13.01.2004

50 / 104


bitul de paritate iar la neconcordanta se va solicita retransmisia, care nu este ntotdeauna o solutie convenabila. n practica este larg utilizata si metoda codului polinomial cunoscut si sub denumirea de cod cu redundanta ciclica sau cod CRC ( Cyclic Redundancy Code). CRC sunt bazate pe tratarea sirurilor de biti ca polinoame cu coeficienti 0 si 1. De exemplu bitii cuvntului cu 6 biti 110001 se reprezinta prin polinomul P(x) =1x5 +1x4 +0x3 +0x2 +0x1 +1x0 = x5 + x4 +1 Aritmetica polinomiala n acest caz este modulo 2, potrivit regulilor teoriei algebrice. Nu exista transport la adunare sau mprumut la scadere, adunarile si scaderile fiind identice, operndu-se cu functia SAUEXCLUSIV. De exemplu 1001+ 10010101 0101 1100 1100 La utilizarea acestei metode, pentru a transmite un cadru (formatie) de biti caruia i se ataseaza un polinom Q(x) emitatorul si receptorul convin asupra unui polinom generator P(x) a carui lungime trebuie sa fie mai mica dect a lui Q(x). La transmisie se procedeaza astfel: 1. se adauga la Q(x) r biti (r este gradP) obtinndu-se cadrul mbunatatit; 2. se mparte cadrul mbunatatit la P(x); 3. restul rezultat (care are ntotdeauna r sau mai putini biti) se scade modulo 2 din cadrul mbunatatit. 4. diferenta T(x) (divizibila modulo2 cu P(x)) este cea care se transmite. La receptie se efectueaza mpartirea T(x):P(x), si daca rezulta rest nul, rezulta ca transmisia s-a efectuat corect. Refacerea lui Q(x) n caz ca nu sunt erori presupune separarea n T(x) a r cifre din zona nesemnificativa. Exemplu Fie cadrul de biti 1101101 sau Q(x)=x6 + x5 + x3 + x2 +1

13.01.2004

51 / 104


Polinomul generator este 1011 sau P(x)=x3 + x+1 Sa se determine cadrul transmis T(x), din care sa se refaca apoi Q(x) respectiv cadrul de biti initial. 1. Se adauga 3 biti (gradul lui P(x) este 3) la cadrul initial obtinndu-se cadrul mbunatatit 1101101000 2. Se mparte cadrul mbunatatit la P(x) 110 101 - 11 10 - 1 1 110 1 01 11 100 011 111 101 - 10 10 - 10001011 1111101 ct =1111101 1 r 1 00 11 110 101 011 es t =0111

0 1 1

3. Se scade restul din cadrul mbunatatit si rezulta polinomul care se transmite, respectiv T(x). 11011010000000000111 1101101111

13.01.2004

52 / 104


4. Verificarea la receptie, presupune efectuarea mpartirii T(x):P(x) 110 101 - 11 10 - 1 1 110 1 01 11 100 011 111 101 - 10 10 - 11111011 1111101 ct =1111101 1 r 1 01 11 101 101 000 es t =0000

1 1 0

5. Restul fiind 0000 rezulta ca transmisia s-a efectuat corect, iar refacerea cadrului initial eliminnd ultimele 3 cifre din T(x), respectiv Q(x) = 1101101 La transmiterea datelor se folosesc urmatoarele trei polinoame generatoare, considerate standarde internationale: CCITT-32: P(x) = x32 + x26 + x23 + x22 + x16 + x12 + +x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 CRC-16: P(x) = x16 + x15 + x2 + 1 CRC-CCITT: P(x) = x16 + x12 + x5 + 1 CRC-XMODEM: P(x) = x16 + x15 + x10 + x3 12bit-CRC: P(x) = x12 + x11 + x3 + x2 + x + 1 10bit-CRC: P(x) = x10 + x9 + x5 + x4 + x + 1 8bit-CRC: P(x) = x8 + x2 + x + 1

13.01.2004

53 / 104


Dupa cum s-a mentionat, la receptia unui mesaj eronat se cere retransmisia acestuia. Pentru a evita retransmisia se apeleaza la codurile corectoare de erori . Un cod este cod corector de erori (CCE) atunci cnd cuvntul de cod corect poate fi ntotdeauna dedus din cuvntul eronat. ntre CCE un loc aparte revine codului Hamming, care n cazul unei corectii singulare are distanta 3. Numarul minim de biti de control pentru a asigura aceasta distanta se determina cu relatia2k m + k + 1 , (2.29) unde m este numarul de biti de informatie, iar k - numarul de biti de control. Vom explica n continuare constructia unui cod Hamming cu m = 7 (mesaj original in ASCII). Din relatia lui Hamming (2.29) rezulta k = 4, astfel nct 4 biti de control trebuie adaugati celor 7 biti de informatie, rezultnd un cod ASCII pe 11 biti cu 4 biti redundanti. Asignarea celor 4 biti redundanti la cuvintele originale se va face astfel nct sa poata fi identificata o eroare la un singur bit. Fiecarui bit din cuvntul codificat, incluznd si bitii redundanti de verificare i este asignata de biti C8 C4 C2 C1 , corespunzator Tabelului 2.13. n acest tabel echivalentul zecimal al combinatiilor binare reprezinta pozitia bitilor care sunt verificati ncepnd cu pozitia 1. n cuvntul de 11 biti care se transmite C1 ocupa pozitia 1, C2 a doua s.a.m.d. , conform reprezentarii din figura 2.7.

Tabelul 2.13C8 D0 0 0 0 0 0 0 1 1 1 1 C4 0 0 0 1 1 1 1 0 0 0 0 C2 0 1 1 0 0 1 1 0 0 1 1 C1 1 0 1 0 1 0 1 0 1 0 1 Pozitie bit verificat 1 2 3 4 5 6 7 8 9 10 11

13.01.2004

54 / 104


11 B7

10 B6

9 B5

8 C8

7 B4

6 B3

5 B2

4 C4

3 B1

2 C2

1 C1

Fig. 2.7. Structura unui cuvnt ASCII cu patru biti de verificare: Bi biti utili; Cj - biti de verificare.

Modul de amplasare a bitilor de verificare n pozitii corespunznd puterilor lui 2, se numeste Cod de Corectare a unei Erori Singulare (CCES) sau Single Error Connecting (SEC), si faciliteaza procesul de localizare a erorii. Valorile celor 4 biti de verificare sunt determinati functie de paritatea (para sau impara avuta n vedere) prin evaluarea sumelor modulo 2 S1 , S1 , S4 , S8 . conform relatiilor de mai jos:S1 = C1 B1 B2 B4 B5 B7 S 2 = C 2 B1 B3 B4 B6 B7 S 4 = C 4 B2 B3 B4 S8 = C8 B5 B6 B7

(2.30) (2.31) (2.32) (2.33)

Sumele Si trebuie sa realizeze paritatea para pentru pozitiile care au 1 n coloanele aferente bitilor de verificare Ci dupa cum urmeaza: S1 S2 S4 S8 = 0 pentru grupul de biti {1,3,5,7,9,11} ; = 0 pentru grupul de biti {2,3,6,7,10,11} ; = 0 pentru grupul de biti {4,5,6,7} ; = 0 pentru grupul de biti {8,9,10,11} .

Din relatiile (2.30)(2.33) rezulta (impunnd tipul paritatatii) valorile care se vor transmite pentru bitii de control C , C2 , C4 , C8 . La 1 receptie se evalueaza sumele, iar cnd acestea corespund tipului paritatii transmise, transmisia se considera corecta. n cazul cnd una sau mai multe sume nu corespund tipului de paritate, exista un bit eronat a carui pozitie se determina prin adunarea indicilor sumelor eronate 10 .

10

Se are n vedere faptul ca un bit n este verificat de catre bitii ale caror pozitii nsumate dau n (de exemplu bitul 7 este verificat de catre bitii din pozitiile 1, 2, 4 deoarece 1+2+4=7.

13.01.2004

55 / 104


n cele ce urmeaza se va considera un exemplu pentru care se va presupune paritate para (suma 0 la un numar par de biti 1). 1. Sa se determine bitii reduntanti de verificare la transmisia codului ASCII al caracterului a (9710 = 1100001)11 B7 1 10 B6 1 9 B5 0 8 C8 ? 7 B4 0 6 B3 0 5 B2 0 4 C4 ? 3 B1 1 2 C2 ? 1 C1 ?

S1 = C1 B1 B2 B4 B5 B7 = 0 C1 1 0 0 0 1 = 0 C1 = 0 S 2 = C 2 B1 B3 B4 B6 B7 = 0 C2 1 0 0 1 1 = 0 C2 = 1 S 4 = C4 B2 B3 B4 = 0 C4 0 0 0 = 0 C4 = 0 S8 = C8 B5 B6 B7 = 0 C8 0 1 1 = 0 C8 = 0

astfel nct se transmite urmatoarea formatie de 11 biti11 B7 1 10 B6 1 9 B5 0 8 C8 0 7 B4 0 6 B3 0 5 B2 0 4 C4 0 3 B1 1 2 C2 1 1 C1 0

2. Sa se determine ce caracter a fost transmis daca a fost receptionata urmatoarea formatie de 11 biti 10010111001 (7 biti ai codului ASCII si 4 biti de verificare11 B7 1 10 B6 0 9 B5 0 8 C8 1 7 B4 0 6 B3 1 5 B2 1 4 C4 1 3 B1 0 2 C2 0 1 C1 1

Se evalueaza sumele SiS1 = C1 B1 B2 B4 B5 B7 = 1 0 1 0 0 1 = 1 impar a S 2 = C2 B1 B3 B4 B6 B7 = 0 0 1 0 1 0 = 0 para S 4 = C 4 B2 B3 B4 = 1 1 1 0 = 1 C4 impar a S8 = C8 B5 B6 B7 = 1 0 0 1 = 0 para

13.01.2004

56 / 104


de unde rezulta ca S1 si S4 sunt impare, un bit a fost transmis eronat a carui pozitie este 1+4=5 deci bitul numarul 5 trebuie corectat astfel nct formatia de 11 biti devine

11 B7 1

10 B6 0

9 B5 0

8 C8 1

7 B4 0

6 B3 1

5 B2 0

4 C4 1

3 B1 0

2 C2 0

1 C1 1

Se extrag bitii de control din pozitiile 1, 2, 4, 8 astfel nct rezulta11 B7 1 10 B6 0 9 B5 0 8 C8 7 B4 0 6 B3 1 5 B2 0 4 C4 3 B1 0 2 C2 1 C1 -

Respectiv7 B7 1 6 B6 0 5 B5 0 4 B4 0 3 B3 1 2 B2 0 1 B1 0

Vectorul binar este (1000100) 2 = (68)10 care este codul ASCII al caracterului D. Observatii 1. n cazul aparitiei a doua erori acestea pot fi detectate, nsa numai una poate fi corectata. Pentru a corecta 2 erori distanta Hamming minima trebuie sa fie 5. n general pentru a detecta p erori distanta Hamming trebuie sa fie p+1 , iar pentru corectarea a p erori aceasta distanta trebuie sa fie 2p+1. 2. Schema de detectare si corectare a unei erori poate fi vizualizata pe un hipercub n vrfurile caruia sunt plasate codurile valide si invalide. Distanta Hamming separa codurile valide, n timp ce un cod invalid este plasat mai aproape de un cod valid, aspect ce faciliteaza detectarea si corectarea unei erori singulare.

13.01.2004

57 / 104


2.4. Operatii aritmetice n virgula fixa 2.4.1. Adunarea si scaderea binara Cele doua operatii vor fi tratate pentru reprezentarea n codurile direct, complementar si invers. 2.4.1.1.Adunarea si scaderea n cod direct Cele doua operatii vor fi tratate unitar conform relatiei: op = xs y s sop (2.34) unde : op reprezinta operatia efectiva ce se va efectua ntre cei doi operanzi; xS , yS - semnele celor doi operanzi (1 pentru -, 0 pentru +); sOP - operatia ce se doreste a fi efectuata ( 1 pentru -, 0 pentru +). n ceea ce priveste operatia (sau exclusiv) dupa cum s-a mai aratat aceasta este definita astfel: 0 0 = 0; 0 1 = 1; 1 0 = 1; 1 1 = 0. Pe baza celor prezentate, valoarea operatorului op se determina cu ajutorul Tabelului 2.14. Tabelul 2.14 xs ys Sop Op xs ys Sop Op 0 0 0 0 + + + + 0 0 1 1 + + 0 1 0 1 + + 0 1 1 0 + + 1 0 0 1 + + 1 0 1 0 + + 1 1 0 0 + + 1 1 1 1 n cazul n care prin evaluarea semnelor rezulta scadere, scazatorul va putea fi nlocuit prin complementul sau fata de 2 (C2),

13.01.2004

58 / 104


operatia fiind practic nlocuita cu o operatie de adunare11 , n Tabelul 2.15 fiind prezentate cele 4 situatii posibile. Tabelul 2.15Situatii posibile Operatia de executat(+ A) + (+ B ) (+ A) + ( B) ( A ) + ( + B) ( A ) + ( B )

A+ B

A+B

A+B

A+ B

Adunarea numerelor se executa asupra cifrelor numerelor A si B n conformitate cu regulile adunarii binare. Semnul sumei C precum corectitudinea rezultatului obtinut se stabilesc n functie de existenta (Tabelul 2.16) sau nu a (Tabelul 2.17) transportului de la CCMS12 la bitul de semn. Tabelul 2.16Semnul rezultatului Cs Semnificatia sumei Corectie(+ A) + (+ B ) (+ A) + ( B) ( A ) + ( + B) ( A ) + ( B )

+(0)Adevarata marime C Nu

-(1) Compleme ntul C2 Recomple mentare (rC213 )

-(1) Compleme ntul C2 Recomple mentare (rC2)

-(1)Adevarata marime C

(rezultat corect)

Nu (rezultat corect) Tabelul 2.17

Semnul rezultatului Cs Semnificatia sumei Corectie

(+ A) + (+ B )

(+ A) + ( B)

( A ) + ( + B)

( A ) + ( B )

+(0)Adevarata marime C Eroare de depasire

+(0)Adevarata marime C


-(1)Adevarata marime C Eroare de depasire

Nu (rezultat corect)


Acest lucru este posibil deoarece A B = A + (0 B ) = A + B CCMS Cifra Cea Mai Semnificativa 13 rC2 recomplementare, operatiile se fac invers celor de la obtinerea C2 (se scade 1, dupa care complementeaza).11 12

13.01.2004

59 / 104


STARTCiteste operanzii A, B si semnele As si Bs < As : Bs A*= A = A*= A A*= C2(A) >

B*= C2(B) B*= B

B*= B

C* = A*+ B*

Nu Transport ? Da As = Bs Cs=As Cs = 1 (-) Nu

Da Da As = Bs Nu Cs = 0 (+) Cs=As

C= C*

C = rC2(C*) C= C*

Scrie suma C si semnul Cs

Semnaleaza eroare depasire

STOP

13.01.2004

60 / 104


Algoritmul descris n Tabelele 2.16 si 2.17 poate fi transpus n schema logica simplificata din figura 2.8. Exemplu Fie A=(10/16) 10 = (0.625) 10 si B=(7/16) 10 = (0.4375) 10 reprezentate n binar pe cinci biti (patru pentru valoare, unul pentru semn) prin A=(01010)2 si B=(00111)2 Sa se calculeze C1 =A+B, C2 =A-B, C3 =-A+B, C4 =-A-B C1 * = A + B 1 0 0 1 0 0 1 1 0 0 + 1 1

0 0 0 1

S-a generat transport de la CCMS la bitul de semn numerele A si B fiind de acelasi semn rezultatul este incorect deoarece se depaseste capacitatea de reprezentare pe 4 biti - ntr-adevar (0.625) 10 + (0.4375) 10 = (1.0625) 10 obtinndu-se un numar supraunitar. C2 * = A - B = = A + C2(B) C2 = C2 * 0 1 1 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 1 1 +

S-a generat transport de la CCMS la bitul de semn numerele A si B fiind de semne contrare rezultatul este corect ncadrndu-se n capacitatea de reprezentare pe 4 biti - ntr-adevar (0.625) 10 - (0.4375) 10 = (0.1675) 10 obtinndu-se un numar subunitar respectiv 1/8 + 1/16 = 3/16 C3 * = -A + B = = C2(A) + B C3 = rC2(C2 * ) 1 0 1 1 0 1 0 1 1 1 0 0 1 1 0 1 0 + 1 1 1

13.01.2004

61 / 104


Nu s-a generat transport de la CCMS la bitul de semn rezultatul pe 4 biti obtinndu-se prin recomplementare -(1/8+1/16)=-3/16. C4 * = -A - B 1 1 1 S-a generat transport de la CCMS la bitul de semn numerele A si B fiind de acelasi semn rezultatul este incorect deoarece se depaseste capacitatea de reprezentare pe 4 biti - ntr-adevar -(0.625) 10 - (0.4375) 10 = -(1.0625) 10 obtinndu-se un numar supraunitar n valoare absoluta. 2.4.1.2. Adunarea si scaderea n cod complementar Pentru efectuarea operatiilor de adunare si scadere cu operanzi reprezentati n C2 exista 4 metode: - adunarea directa; - scaderea directa; - adunarea prin scaderea complementului; - scaderea prin adunarea complementului. La oricare din aceste 4 metode bitul de semn este tratat ca un bit al numarului. Utilizarea C2 face posibila transformarea scaderii n adunare motiv pentru care n cele ce urmeaza va fi tratata numai aceasta operatie. n Tabelul 2.18 sunt prezentate cele 4 situatii care pot aparea la adunarea a doua numere A si B exprimate n C2. Tabelul 2.18Situatii posibile Operatia de executat(+ A) + (+ B)

1 0 0 1 0 0

1 1 0

0 + 1 1

(+ A) + ( B)

( A ) + ( + B)

( A ) + ( B )

A+ B

A+B

A+B

A +B

Adunarea numerelor se executa asupra cifrelor numerelor A si B n conformitate cu regulile adunarii binare. Adunarea se efectueaza rang cu rang, ncepnd cu rangurile mai putin semnificative, inclusiv rangurile de semn. Eventualul transport care apare la stnga rangului de semn se neglijeaza.

13.01.2004

62 / 104


Interpretarea rezultatului si eventualele corectii necesare sunt prezentate n Tabelul 2.19 (nu exista transport de la CCMS) si Tabelul 2.20 (exista transport de la CCMS) Tabelul 2.19Semnul rezultatului Cs Semnificatia sumei Corectie(+ A) + (+ B ) (+ A) + ( B) ( A ) + ( + B) ( A ) + ( B )

+(0)Adevarata marime C Nu

-(1) Compleme ntul C2Nu

-(1) Compleme ntul C2Nu

-(1) Compleme ntul C2Eroare de depasire

(rezultat corect)

(rezultat corect

(rezultat corect

Tabelul 2.20Semnul rezultatului Cs Semnificatia sumei Corectie(+ A) + (+ B ) (+ A) + ( B) ( A ) + ( + B) ( A ) + ( B )

+(0)Adevarata marime C Eroare de depasire



-(1)Complement ul C2



Nu (rezultat corect

Exemplu Fie A=(8/16) 10 = (0.5) 10 si B=(7/16) 10 = (0.4375) 10 reprezentate n binar pe cinci biti (patru pentru valoare, unul pentru semn) prin A=(01000)2 si B=(00110)2 Sa se calculeze C1 =A+B, C2 =A-B, C3 =-A+B, C4 =-A-B prin reprezentare n C2 pe 5 biti C1 = A + B 1 0 0 1 1 1 0 1 1 0 + 0 0

0 0 0

13.01.2004

63 / 104


Nu s-a generat transport de la CCMS la bitul de semn numerele A si B fiind pozitive rezultatul este corect - ntr-adevar (0.5) 10 + (0.4375) 10 = (0.9375) 10 obtinndu-se un numar subunitar reprezentabil cu semn pe 5 biti. C2 = A - B = = A + C2(B) 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 +

C2 = C2 *

Transport de la CCMS

Transport de la bitul de semn se ignora

S-a generat transport de la CCMS la bitul de semn numerele A si B fiind de semne contrare rezultatul este corect ncadrndu-se n capacitatea de reprezentare pe 4 biti - ntr-adevar (0.5) 10 - (0.4375) 10 = (0.0625) 10 obtinndu-se un numar subunitar reprezentabil cu semn pe 5 biti. C3 = -A + B = = C2(A) + B 1 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 + 0 0 0

C3 = rC2(C3 )

Nu s-a generat transport de la CCMS la bitul de semn rezultatul pe 4 biti obtinndu-se prin recomplementare 0.5+0.4375=-0.0625. C4 = -A - B 1 1 1 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 + 0 0 0

Transp. De la CCMS Transport de la bitul de semn se ignora

S-a generat transport de la CCMS la bitul de semn numerele A si B fiind de acelasi semn

bazele aritmeticeale calculatoarelor numerice

Documents