AOR G5 Racunarska Aritmetika 1

10.5.2011

1

5. RAUNARSKA ARITMETIKA

Operacije sa celobrojnim podacima

Dr Neboja MilenkoviElektronski fakultet u Niu

PREDSTAVLJANJE NUMERIKIH PODATAKA U RAUNARU

Podela podataka prema vrednostima:

celobrojni i realni, osnovi brojnog sistema:

binarni, dekadni, heksadecimalni itd., tome da li se vodi rauna o znaku podatka:

oznaeni i neoznaeni,

N. Milenkovi, Arhitektura i organizacija raunara 2011

Prema duinama podataka

Podela podataka prema duinama podataka: za celobrobrojne podatke na

bajtove (8 bitova), polurei (16 bitova), rei (32 bita) i dvostruke rei (64 bita),

za realne podatke na format jednostruke preciznosti (32 bita),format dvostruke preciznosti (64 bita),proireni formati itd.


Odvojeni podskupovi instrukcija

Za rad sa celobrojnim odnosno realnim podacima procesori koriste odvojene podskupove instrukcija. N i MIPS hit kt i ADD j i t k ij Naprimer, u MIPS arhitekturi, ADD je instrukcija sabiranja celobrojnih podataka, a ADD.S i ADD.D su instrukcije sabiranja realnih podataka predstavljenih sa pokretnom zapetom u formatu jednostruke i dvostruke preciznosti respektivno.


Binarna i dekadna aritmetika

Unoenje podataka u raunar zahteva njihovo prevoenje iz dekadnog u binarni oblik. Po izvrenoj obradi, podaci se pri izdavanju prevode iz binarnog u dekadnii oblik.

Ima primena raunara u kojima se ne doputa Ima primena raunara u kojima se ne doputa ovo dvostruko prevoenje brojeva iz jednog u drugi brojni sistem, jer se time unose greke.

Pri takvim zahtevima, podaci se u raunaru predstavlju u dekadnom obliku. Tada se dekadni podaci kodiraju slogovima binarnih cifara, BCD kodovima.


Predstavljanje znaka broja

Neka je X oznaeni m-to cifreni ceo broj u brojnom sistemu sa osnovom BX= xm-1xm-2...x1x0

Pri prostom iskazivanju znaka dodaje se cifra Pri prostom iskazivanju znaka dodaje se cifra znaka xm sa znaenjem:

0 znak +, B-1 znak -Primer: +101102 0101102, a

-101102 1101102


10.5.2011

2

Komplementno predstavljanje brojeva

Potreba da se jedinstveni hardver sabiraa koristi za operacije sabiranja i oduzimanja, odnosno sabiranja oznaenih brojeva, dovela je do komplementnog iskazivanja znaka. Postoje dva tipa komplemenata oznaenih podataka: komplement osnove ikomplement najvee cifre.


Definicija komplemenata

Oba tipa komplemenata definiu se istovetno 0xm-1xm-2...x1x0, ako je X0,

Kt(X) = Qt -|X|, ako je X< 0 .{B B 1}t{B, B-1}.

Kod komplementa osnove, KB(X),QB = Bm+1 ,

a kod komplementa najvee cifre, KB-1(X), QB-1 = Bm+1 -1.


Veza izmeu komplemenata

Iz ove razlike proistie i veza izmeu ova dva tipa komplemenata negativnog broja X

KB(X) = KB 1(X) +1KB(X) KB-1(X) +1 Komplement najvee cifre dobija se kao dopuna

svake cifre datog broja do cifre B-1, i dodavanja cifre B-1 kao cifre znaka.


Primeri

Naprimer, K9(-328) moe se dobiti kaoK9(-328)=9999-328= 9671

Iz K10(X) = K9(X) +1 dobija seK10(-328) = 9671+1=9672

K1(-11012)=111112-11012= 100102K2(-11012)=100102 +12= 100112


Vrednost broja u dvojinom komplementu


Polarizovano predstavljanje brojeva

Polarizovani oblik broja X je x=X+P, gde je P polarizacija ili pomak, veliine P=Bm ili P=Bm1, a m je broj cifara u X (bez cifre znaka).

Ovom transformacijom se vrednosti broja X iz opsega [-Bm, Bm1] pri polarizaciji P= Bm preslikavaju u opseg vrednosti [0, 2Bm1] polarizovanog broja x.


10.5.2011

3

Polarizovano predstavljanje brojeva

Pri polarizaciji P= Bm1 vrednosti broja X iz opsega [-(Bm1), Bm] takoe se preslikavaju u opseg vrednosti [0, 2Bm1] polarizovanog broja x .


Primer predstavljanja oznaenih brojeva


Oduzimanje sabiranjem komplemenata

Operacija oduzimanja svodi se na operaciju sabiranja komplemenata oznaenih brojeva.

Pri korienju komplemenata osnove pri sabiranju prenos iz pozicije znaka se ignorie j p p j g(gubi).

Pri korienju komplemenata najvee cifre prenos iz pozicije znaka naknadno se dodaje sumi komplemenata u poziciji najmanje teine.


Pojava prekoraenja

Pri sabiranju komplemenata sabiraka moe doi do prekoraenja kapaciteta korienog formata brojeva.

Kriterijum za ustanovljenje prekoraenja je sledei:ako je cifra prenosa iz pozicije znaka razliita od cifre prenosa u poziciju znaka dolo je do prekoraenja.

U tom sluaju dobijeni rezultat je nekorektan. Izlaz iz ovoga mogao bi biti u korienju dueg formata brojeva.


PARALELNI BINARNI SABIRAIJednobitni potpuni binarni sabira


Potpuni binarni sabiraa. blok ema, b. logika ema

. ...aa Potpuni ss bpu

.

a.

pbinarnisabira~

b

b.

b

pu pipi


10.5.2011

4

PARALELNI SABIRAI SA SERIJSKIM PRENOSOM

Neka su a=a3a2a1a0 i b=b3b2b1b0 etvorobitnibinarni brojevi.N ii l ik i i k d Napiimo logike izraze za sumu i prenos kodpotpunog binarnog sabiraa u sledeem obliku:si = ai bi pi-1 ,pi = aibi+(ai bi)pi-1, i=0,1,2,3,pri emu je p-1 prenos u poziciju najmanje teine, a p3 je prenos iz pozicije najvee teine.


Pomone funkcije

Uvedimo funkcije gi=aibi i ti =aibi. Funkcija giesto se naziva generator prenosa, jer se zagi=1 u i-toj poziciji generie prenos u (i+1)-vupoziciju, a funkcija ti prosleiva prenosa, jer seza ti=1 prenos iz (i-1)-ve pozicije prosleuje u(i+1)-vu poziciju. Sada se izrazi za si i pi mogunapisati u obliku:si =ti pi-1,pi =gi+tipi-1, i=0,1,2,3.


Prenos izraen preko g i t funkcija

Na osnovu izraza za pi moe se prenos izpozicije najvee teine p3 izraziti kao funkcijasamo ulaza a3a2a1a0 i b3b2b1b0 i prenosa p-1:p3=g3+t3p2=g3+t3(g2+t2p1)=p3 g3 3 p2 g3 3 (g2 2 p1)g3+t3(g2+t2(g1+t1p0))p3=g3+t3(g2+t2(g1+t1(g0+t0p-1)))

Dobijeni izraz sugerie blok emu paralelnogbinarnog sabiraa prikazanu na sledeemslajdu.


Paralelni sabira sa serijskimprenosom

Ovakav paralelni binarni sabira naziva se paralelni sabira sa serijskim prenosom (engl. ripple-carry adder, skr. RCA)

PBS PBS PBS PBS

p2 p1 p0

p-1

s3 s2 s1 s0

a3 a2 a1 a0b3 b2 b1 b0

p3


Vreme prostiranja kroz sabira

Maksimalno vreme sabiranja na ovakvomsabirau irine n bitova odreeno je vremenomprostiranja prenosa kroz svih n pozicija sabiraa.

Neka jeT ti j k j d bit iT1-vreme prostiranja prenosa kroz jednobitnipotpuni sabira sa dvostepenom logikom,Te -vreme prostiranja signala kroz jedan logikielement,onda je vreme sabiranjaTsRCA= nT1 = 2nTe


SABIRAI SA PARALELNIM PRENOSOM

. ..Modifikovani potpuni sabira~

pi-1pi-1

siai

ai

bi

bi

gi

ti

sia. b.

gi ti

p3=g3+t3g2+t3t2g1+t3t2t1g0+ t3t2t1t0p-1


10.5.2011

5

Logika za formiranje prenosa

MPS MPS MPS MPS

p2 p1 p0 p-1

s3 s2 s1 s0

a3 a2 a1 a0b3 b2 b1 b0

g3 g2 g1 g0t3 t t t0p3

p-1

p-1

p-1p-1

s3 s2 s1 s0g3g3

g2

g2g2

g1

g1

g1g1

g0

g0

g0g0

g0

t3

t3

t3

t3

t3

t2

t2

t2 t2

t2

t2

t2

t1

t1t1

t1

t1

t1

t1

t0

t0

t0t0

t0



Ovakav sabira naziva se paralelni sabirasa paralelnim prenosom (engl. carry look-ahead adder, skr. CLA).

Odlikuje se kratkim vremenom sabiranja Odlikuje se kratkim vremenom sabiranja,koje iznosiTsCLA = 4Tei nezavisnou vremena sabiranja od irine sabiraa n.


Nedostaci sabiraa sa paralelnim prenosom

Nedostaci su mu: veliki obim logike, potreba za korienjem u k-toj poziciji (k =

0 1 1) ILI l ik l t k+20,1,...,n-1) ILI logikog elementa sa k+2 ulaza i k+1 I logikih elemenata sa 2k+2 ulaza,

veliki faktor izlaza (engl. fan-out) korienih logikih elemenata (do 6 kod etvorobitnog sabiraa za t2 i t1).


SABIRAI SA IZBOROM PRENOSA

Vreme sabiranja na sabirau sa serijskim prenosom moe se skratiti ako se skrati put prostiranja prenosa kroz ovakav sabira.

To se moe postii deobom n bitova sabiraka na krae grupe bitova recimo duine k tako da jekrae grupe bitova, recimo duine k, tako da je n = mk.

Ideja je da se u okviru svih m grupa sabiranje vri paralelno.

Dakle, umesto jednog n-bitnog sabiraa imamo m k-bitnih sabiraa.


Zahtevi za paralelan rad

U svim k-bitnim grupama sabiraka, osim grupe najmanje teine, ulazni podatak je i prenos iz prethodne grupe manje teine. p p g p j

Vrednost ovog prenosa poznata je tek po okonanju sabiranja u prethodnoj grupi. A za paralelan rad svih m k-bitnih sabiraa potrebno je ove vrednosti znati na samom poetku sabiranja.


Udvajanje sabiraa u k-bitnim grupama

Ta vremenska neusaglaenost moe se prevazii korienjem u svakoj od m-1 grupa po dva k-bitna sabiraa sa serijskim prenosom: jednog sa pretpostavljenim prenosom 0 iz prethodne grupe, i drugog sa pretpostavljenim prenosom 1 iz prethodne grupe.

Samo u grupi najmanje teine nije potrebno ovo udvajanje sabiraa, jer je vrednost prenosa u ovu grupu unapred poznata.


10.5.2011

6

Izbor sume

Iz kog od dva sabiraa u okviru svake grupe bitova uzeti sumu? Iz onog sabiraa koji za pretpostavljeni prenos iz prethodne grupe ima vrednost koja je upravo odreena sabiranjem uvrednost koja je upravo odreena sabiranjem u prethodnoj grupi. Ovaj izbor vri se korienjem u svakoj grupi po k multipleksera tipa (2,1).

Otuda i naziv sabira sa izborom prenosa (engl. Carry-Select Adder, skr. CSLA) za ovaj tip sabiraa.


ema sabiraa sa izborom prenosa

pp

0 0 0 a3..0

a7..4a11..8a15..12 b15..12 b11..8 b7..4

b3..0p07p0

11p015

S0

p-1p3

S1S2S3

S4S5S6S7S8S9S10S11S12S13S14S15

1 1 1

MUX(2,1)

p17p111

p115

p15 Y2Y3Y4


Logika za izbor suma u grupama

Izbori suma u okviru grupa vre se signalimaodreenim sledeim logikim izrazima:Y2 = p3Y3 = p07 + p17p3 Y4 = p011 + p111Y3 = p011 + p111p07 + p111p17p3

Izraz Y3 = p07 + p17p3 govori da se prenos izdruge grupe moe dobiti generisanjem prenosau toj grupi (p07 =1) ili prosleivanjem prenosa p3iz prve grupe kroz drugu grupu (p17p3 =1).

Ista logika vai za Y4.



Ukupno vreme sabiranja jeTSCSLA=TgRCA+(m-2)2Te+TMUX =

k2Te+2(m-2)Te+3TeT CSLA= (2k+2m 1)TTSCSLA= (2k+2m-1)Tegde je Te vreme prostiranja kroz jedan logikielement, a (TMUX)max=3Te .

Cena za ovo poveanje brzine je skoro dvostruko vei obim hardvera sabiraa sa izborom prenosa (CSLA) u odnosu na sabirasa serijskim prenosom (RCA)


MNOENJE PROSTO OZNAENIH BROJEVA

Neka su dati prosto oznaeni mnoenik a i mnoilac ba=amam-1 ... a1a0 , b=bmbm-1 ... b1b0 .Treba izraunati proizvod c=ab.

U zapisu operanada a i b cifre u poziciji m su cifre znaka, a ostale cifre odreuju veliinu (apsolutnu vrednost broja).

Proizvod c je duine 2m+1 bita, sa cifrom znaka odreenom izrazom c2m= (am bm), i apsolutnom vrednou odreenom izrazom lallbl.


Dve varijante mnoenja

Mogue su dve varijante mnoenja: mnoenje poev od cifre najmanje teine

mnoioca, i mnoenje poev od cifre najvee teine

mnoioca.mnoioca.Pri mnoenju na oba naina parcijalni proizvodi

moraju biti meusobno pozicionirani u skladu sa svojim teinama. To se postie time to se parcijalni proizvodi veih teina pomeraju ulevo u odnosu na parcijalne proizvode manjih teina, u skladu sa teinama cifara mnoioca.


10.5.2011

7

Mnoenje poev od cifre najmanje teine


Mnoenje poev od cifre najvee teine


ema mnoaa poev od cifre najmanje teine

P Bm-1m-1m

m

0 0

(pomeri udesno)

+

Am m-1

m

0

(saberi)

(znak)

(napuni A)

(napuni B)(obri{i P)

M

START

KRAJ

Blokupravljanja


Aktivnosti u pripremi i toku mnoenja

Mnoa sadri registre A, B i P i paralelni binarni sabira.

U pripremi mnoenja, mnoenik i mnoilac unose se u registre A i B respektivno, dok se pomoni registar P brie. p g

U toku mnoenja, sadraji registara P i B se pomeraju udesno, i to tako da cifra iz pozicije 0 registra P prelazi u poziciju m-1 registra B. Cifra znaka mnoioca izuzeta je iz ovog pomeranja.

Cifra znaka proizvoda formira se po okonanju izraunavanja apsolutne vrednosti proizvoda.


Blok upravljanja mnoaem

Mnoau je pridodat blok upravljanja, sa unutranjim registrom M koji broji iteracije j g j j jpotrebne do zavretka mnoenja.

Isprekidanim linijama oznaena su mesta delovanja (upravljake take) upravljakih signala, navedenih izmeu zagrada.


Algoritam mnoenja prosto oznaenih celih brojeva poev od cifre

najmanje teine

Po zavretku mnoenja

Mno`enje_1

A a B bP 0M m

B = 10 da

ne

Po zavretku mnoenja, proizvod je prisutan u registrima P i B, i to polovina vee teine u P a polovina manje teine u B.

Pozicija m registra P sadri cifru znaka proizvoda.

M M-1

P P +A m-1..0 m-1..0

P A Bm m m

(P,B) >> 1

Kraj

M > 0ne

da


10.5.2011

8

Vreme potrebno za mnoenje

Neka su:TS - vreme sabiranja sadraja registara P i A,TP - vreme pomeranja sadraja registara P i B,TI - vreme pripreme mnoenja i odreivanja znaka proizvoda, ik - broj jedinica u mnoiocu b, k m.TM = TI + kTS + mT P


Srednja vrednost vremena mnoenja

Poto su verovatnoe pojavljivanja cifara 0 i 1 u mnoiocu jednake, moemo uzeti da je k = m/2, pa je srednja vrednost vremena mnoenjapa je srednja vrednost vremena mnoenja


MNOENJE PREKODIRANJEM MNOIOCA

Broj jedinica u mnoiocu moe se smanjiti kada su u njemu jedinice grupisane u blok, odnosno zauzimaju vie susednih pozicija, kao u primeru b = 1011110. Kako blok od r jedinica odreuje

r rvrednost 2r1, a 2r je jedinica praena sa r nula, to se data vrednost za b moe izraziti kao b = 1(10000)0 10(0001)0. U zagradama su navedene vrednosti 2r i 1 pozicionirane na mestu jedinice najmanje teine bloka jedinica.


Prekodiranje mnoioca

Ova razlika se moe prikazati i kao b=110000, gde oznaava da 1 ima negativan znak. Zamena podniza 01111 u mnoiocu podnizom 1000 naziva se

111

mnoiocu podnizom 1000 naziva se prekodiranjem mnoioca.

Prekodiranjem mnoioca njegova vrednost se ne menja.


Primer


Pravila prekodiranja

Datom broju X dodati 0 iza cifre najmanje teine. Ii kroz dati broj X s desna u levo, poev od dodate cifre 0.

Analizirati par susednih cifara, i odreivati cifru po cifru prekodiranog broja Y Ako pri tome u Xpo cifru prekodiranog broja Y. Ako pri tome u X naiemo na promenu cifara sa 0 na 1 (10), cifru 1 iz X zamenjujemo cifrom u Y. Pri promeni cifara sa 1 na 0 (01), cifru 0 iz X zamenjujemo cifrom 1 u Y.

Ako nema promene cifara (obe nule ili obe jedinice), u Y unosimo cifru 0.


10.5.2011

9

Pravila prekodiranja

Cifra X(i) je cifra datog broja koja se prekodiranjem zamenjuje cifrom Y(i), uzimajui u obzir i susednu niu cifru X(i-1).

Moe se uoiti da je Y(i)=X(i1)X(i)


BOOTH-ov ALGORITAM MNOENJA

Prekodiranje mnoioca otvara nove mogunosti pri mnoenju. Jedna od njih je direktno mnoenje oznaenih brojeva datih u obliku dvojinih komplemenata.

Takav postupak mnoenja predloio je A.D. Booth 1951. godine.


Prekodiranje u toku mnoenja

Neka su mnoenik a i mnoilac b dati svojim dvojinim komplementima Pomnoimo advojinim komplementima. Pomnoimo aprekodiranim mnoiocem b, poev od cifre najmanje teine. Vrednosti parcijalnih proizvoda, dobijenih mnoenjem cifrom u poziciji iprekodiranog mnoioca, date su u tabeli na prethodnom slajdu.


Hardver mnoaa po Booth-ovom algoritmu

P Bmm 0 0

(napuni B)

(pomeri udesno)

(obri{i P)

-1

+

Am 0

(saberi)

(oduzmi)

(napuni A)

(obri{i P)

Komp

M

START

KRAJ

Blokupravljanja


Booth-ov algoritam mnoenja

Registar B produen je za jedan bit (za pomonu cifru za

Mno`enje_2

A a B b

P 0M m

m..0

B 0-1

B =0 i B =10 -1 B =1 i B =00 1ne ne

pomonu cifru za prekodiranje mnoioca).

U bloku (P, B) a>>1 sa a>>1 oznaeno je aritmetiko pomeranje udesno.

M M-1

P P+A P P- A

(P,B) a>> 1

0 -1 0 -1

M > 0

da da

neda

Kraj


Dokaz Booth-ovog algoritma

U knjizi, na 195 stranici.


10.5.2011

10

MNOENJE PREKODIRANJEM PAROVA CIFARA MNOIOCA

Probajmo da mnoimo ne pojedinanim prekodiranim ciframa mnoioca, ve prekodiranim parovima cifara mnoioca. U tom sluaju dobijaju se vrednostitom sluaju dobijaju se vrednosti parcijalnih proizvoda koje su navedene u etvrtoj koloni tabele 5.5. Sa bpi+1,ioznaena je vrednost prekodiranih cifara bi+1 i bi svedena na poziciju i.


Parcijalni proizvodi formirani prekodiranim parovima cifara

Izmeu ove vrednosti i cifara mnoioca u prve tri kolone tabele 5.5 postoji l d sledea veza

bpi+1,i = bi +bi-1 2bi+1


Ubrzanje mnoenja

injenica da se, pored mnoenja sa +1 i -1, amnoi i sa +2 i -2 ne oteava mnoenje. U tim sluajevima dovoljno je vrednost +a odnosno -a pomeriti za jedno mesto ulevo, ime se ona mnoi sa 2.

Ovim se broj parcijalnih proizvoda prepolovljuje u odnosu na mnoenje originalnim mnoiocem ili mnoenjem prema Booth-ovom algoritmu.

Sukcesivni parcijalni proizvodi, formirani prekodiranjem parova cifara mnoioca, meusobno su pomereni za po dve binarne pozicije.


Primer 5.5 Prekodiranjem parova cifara mnoioca

pomnoiti (+13) sa (-6). (+13)(-6) a=01101 b=11010. Poto mnoilac 11010 ima neparan broj cifara,

produimo ga dodavanjem jo jedne cifre znaka (1), i pomone cifre 0 iza pozicije najmanje teine.


Primer 5.5

Mnoenje 01101 sa -2 zahteva formiranje dvojinog komplementa od -1101, a to je 10011 i njegovo pomeranje ulevo. Prvi parcijalni proizvod 100110 produen je ciframa znaka 111do pozicije znaka parcijalnog proizvoda najveedo pozicije znaka parcijalnog proizvoda najvee teine.

Pri sabiranju parcijalnih proizvoda prenos iz pozicije znaka se ignorie (gubi).

Dekadni ekvivalent dobijenog proizvoda je c= -28+27+25+24+21= -256+178= -78.


Hardver mnoaa

Ovaj nain mnoenja u literaturi je poznat i kao Booth-ovo mnoenje prekodiranjem sa osnovom 4 (engl. radix-4 Booth

di )recoding). Hardver mnoaa po ovom algoritmu

razlikuje se od mnoaa sa slike 5.9 u sledeim elementima.


10.5.2011

11

Hardver mnoaa Bloku upravljanja dostavlja se i cifra iz

pozicije 1 registra B (to odgovara cifri bi+1),

Sadraj registara (P,B) pomera se it tiki d i ij d iaritmetiki za dve pozicije udesno, i

Izmeu registra A i ulaza u sabira dodaje se pomera za jednu poziciju ulevo i upravljaki signal pomeri ulevo.


Da li ii dalje? Logino je pokuati

da se mnoi prekodiranjem tri cifre mnoioca. Parcijalni proizvodi koji se tada dobijaju prikazani su tabelom 5.6.

Sa bpi+2,i oznaena je prekodirana vrednost cifara mnoioca u pozicijama i+2 do i svedena na poziciju i.


CELOBROJNO DELJENJE

Neka su dati celobrojni pozitivni binarni deljenik a i delilac b:a= a a a a b= b b b ba= an-1an-2...a1a0 , b= bm-1bm-2...b1b0 .

Izraunati celobrojni kolinik q i celobrojni ostatak r tako da je a = qb+r , 0r

10.5.2011

12

Hardver delitelja

P Bm-1mm+1 0 0

(napuni B)

(pomeri ulevo)

(upis cifre

(cifra znaka)

+

Am

m+2

m+1 0

(saberi)

(oduzmi)

(napuni A)

(napuni B) kol.)

(napuni P)

Komp

M

START

KRAJ

Blokupravljanja


Algoritam deljenja

Ovo je takozvano deljenje sa obnavljanjem parcijalnog ostatka.

Da bi kolinik imao (P,B)

AOR G5 Racunarska Aritmetika 1

Documents

Transcript of AOR G5 Racunarska Aritmetika 1