Creeaza.com - informatii profesionale despre


Simplitatea lucrurilor complicate - Referate profesionale unice



Acasa » referate » informatica
Metode de inmultire binara

Metode de inmultire binara



Metode de inmultire binara

            Asa cum este cunoscut, operatia de inmultire, la modul general, se realizeaza asupra operanzilor constituiti de inmultitor (multiplier) si deinmultit (multiplicand), notati, pentru o anumita rigoare cu X, respectiv Y. Fiind supusi prelucrarii de catre calculator, operanzii sunt reprezentati prin numere binare pe care le consideram, intr-o prima instanta, pentru simplitate, ca fiind intregi si fara semn. Rezultatul tintit consta din produsul (product) notat cu P, si care, fapt indeobste cunoscut din aritmetica conventionala, se obtine prin apelarea in mod repetat la fundamentala operatie de adunare.

            Astfel, pentru inceput, expunem tentativa formarii lui P prin adunarea operandului Y la el insusi de X ori. Traducand aceasta procedura in termenii limbajului de descriere hardware adoptat, rezulta secventa din figura 3.1:


Text Box: 	multiplier 1
	declare register  CQ[7:0], M[7:0], CM[7:0], CP[15:0]; 
	declare bus INBUS[7:0], OUTBUS[7:0];
BEGIN	  :  CP:=0, M:=INBUS;
                  CQ:=INBUS, CM:=M;
TEST1	  :  if CQ=0 or M=0  then go to  OUTPUT,
ADD	  :  CP:=CP+1, CM:=CM-1;
TEST2	  :  if CM≠0 then go to ADD,
SUB	  :  CQ:=CQ-1, CM:=M;
TEST3	  :  if CQ≠0 then go to ADD,
OUTPUT: OUTBUS[7:0]:=CP[15:8];
                    OUTBUS[7:0]:=CP[7:0];

Fig.3.1

Fara a pierde din generalitate, consideram dimensiunea operanzilor, deci latimea magistralei INBUS/OUTBUS de 8 biti. Dispozitivul de inmultire (multiplier) contine registrele CQ pentru stocarea initiala a lui X, si M pentru stocarea pe intreaga durata a procesului de calcul a lui Y. Produsul P va fi inmagazinat in registrul CP prevazut in mod firesc, de dimensiune dubla. La configuratia de registre prezentata se mai adauga CM, companion a lui M, a carui continut este periodic improspatat din M, la fiecare inceput de adunare a lui Y. In urma incarcarii operanzilor si a initializarii continutului lui CP (operatii elementare prevazute la doua impulsuri de tact distincte prin enunturile etichetate cu BEGIN), este tatonat faptul ca unul, sau ambii, dintre operanzi este zero (enunt cu echitetata TEST1), situatie in care se economiseste, costisitoarea ca timp, buclarea prevazuta de metoda.

Fiecare Y este adunat la continutul lui CP, unitate cu unitate sub controlul continutului din CM (enunturile cu etichetele ADD si TEST2). Succesiv adunarii unui Y, se decrementeaza continutul lui CQ si se reface cel al lui CM (enunt SUB). In acest fel, X se pierde gradual, unitate cu unitate, pana cand ajungand la 0 (tatonat prin TEST3), operatia se incheie prin predarea, mai intai a partii mai semnificative a produsului si apoi la un proxim impuls de tact, a celei mai putin semnificative (enunt OUTPUT).

            Supusa lupei de analiza prin prisma impactului performanta/cost, procedura prezentata sufera nu atat prin investitia in circuistica intrucat partea specifica acestui dispozitiv de inmultire (registrul companion CM, dimensiunea dubla a lui CP, precum si faptul ca toate registrele prevazute cu litera prefix C – de la “count” – sunt prevazute cu

functia de numarare) putem considera ca se afla, grosier, intr-un echilibru, cu ceea ce au specific celelalte inmultitoare, asa dupa cum vom vedea. Ceea ce restrange aria de aplicabilitate a metodei aproape exclusiv la domeniul didactic este timpul de calcul prohibitiv, care, facand abstractie de incarcarea operanzilor intrare si predarea rezultatului, revendica, in termeni de impulsuri de tact, o complexitate de O(), n fiind admisa dimensiunea operanzilor.

            Prin contrast, prezentam in continuare metoda de inmultire conventionala, denumita, in mod sugestiv, “paper and pencil” ([HePa03], [Ital 99], [Haye 98]), care in versiune de implementare in calculator, nu apeleaza la iterarea doar a simplilor pasi de adunare vazuti anterior, ci a unora mai complecsi, de adunare-deplasare. Dar sa expunem mai intai, clasica operatie de inmultire in versiune binara, apeland, de aceasta data, la un exemplu care implica operanzii X  si Y=, unde  si  reprezinta cifrele binare ale celor doua numere(fig. 3.2).

Text Box:         1110 = y3y2y1y0 = Y
        1101 = x3x2x1x0 = X
        1110…….  x0*Y*20 
      0000……… x1*Y*21
    1110……….  x2*Y*22
  1110………… x3*Y*23               
10110110…… P=

Fig. 3.2

Procedura se bazeaza pe formarea prealabila a produselor de un bit ale operandului Y , decalarea progresiva a acestora cu un bit inspre stanga  incepand cu bitul cel mai putin semnificativ al lui X(x0), si, in final, adunarea produselor de un bit decalate (). Aceasta metoda este neadecvata pentru implementarea in calculator intrucat stocarea intermediara a produselor de un bit decalate solicita excesiv resursa memorie, revendicand, in cazurile practicate, vaste spatii de memorare.



O prima imbunatatire sub aspectul semnalat, consta in formarea, in maniera secventiala, a unui produs partial cumulativ, care, initial, este 0 si la care se aduna, in mod succesiv, produse de un bit ale lui y corespunzator decalate la stanga (fig. 3.3).

Fig. 3.3

Astfel, se observa ca in mod recurent, in pasul (i+1) se face uz de iteratia:

Pi+1=Pi+                                              (3.1)

Fig.3.4

unde Pi+1 este noul produs partial obtinut prin adunarea la precedentul (Pi) a produsului de un bit al lui Y deplasat la stanga corespunzator (echivalent cu inmultirea cu 2, adica xi). Rezultatul (P=101101102=18210) se obtine la finele ultimei iteratii. Pe parcursul operarii, conform cu (3.1), fiecare iteratie necesita stocarea doar a doua numere (Pi, respectiv ), evitand anterior semnalata deficienta a metodei clasice. Caracteristic acestei proceduri este faptul, observabil lesne in fig. 3.3, ca toate produsele partiale, inclusiv cel final isi pastreaza  neschimbata pozitia, fiind deplasate la stanga, in mod progresiv, produsele de un bit ale lui Y. O a doua imbunatatire, echivalenta celei de mai sus prin prisma spatiului de memorare revendicat, se bazeaza, de asemenea, pe formarea, in aceeasi maniera secventiala, a unui produs partial cumulativ, care initial este si el 0, dar care nu este fix ca pozitie, ci el sete deplasat, de aceasta data, la dreapta si la care se aduna, in mod succesiv, produse de un bit ale lui Y, care isi pastreaza neschimbata pozitia (fig. 3.4).

Astfel, se observa ca, in mod recurent, in pasul (i+1) se face uz de iteratia compusa:                                   (3.2)

unde, din nou, Pi+1 este noul produs partial obtinut prin deplasarea la dreapta (echivalenta cu impartirea la 2, adica ) a precedentului produs Pi la care s-a adunat produsul de un bit al lui Y nedeplasat ().

            Chiar daca echivalente, asa cum mentionam anterior, cele doua proceduri se deosebesc prin prisma implementarii intrucat cea bazata pe iteratia (3.1) necesita, asa cum poate fi lesne observat, un sumator pe 2n biti (n fiind din nou dimensiunea operanzilor, pe cand la procedura bazata pe iteratia (3.2) este suficient un sumator pe n biti, ceea ce justifica preferinta pentru a doua varianta de implementare, pe care o vom adopta in cele ce urmeaza.

Text Box:     
        1110 = y3y2y1y0 = Y
        1101 = x3x2x1x0 = X
00000000… P0:=0
        1110 x0*Y*20        
00001110 P1:=P0+x0*Y*20
      0000.. x1*Y*21
00001110P2:=P1+x1*Y*21
    1110. x3*Y*22
01000110P3:=P2+x2*Y*22
  1110x3*Y*23 
10110110P4:=P3+x3*Y*23=P
Text Box:         1110 = y3y2y1y0 = Y
         1101 = x3x2x1x0 = X
00000000….. P0:=0
        1110. x0*Y  
00001110.P0:=P0+x0*Y
  00001110..P1:=2-1*P0
        0000.x1*Y              
  00001110..P1:=P1+x1*Y
    00001110P2:=2-1*P1
        1110.x2*Y
    01000110P2:=P2+x2*Y
      01000110.P3:=2-1*P2
        1110.x3*Y
      10110110.P3:=P3+x3*Y 
        10110110..P4:=2-1*P3=P









Politica de confidentialitate

.com Copyright © 2019 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 PROIECT DE LECTIE Clasa: I Matematica - Adunarea si scaderea numerelor naturale de la 0 la 30, fara trecere peste ordin
 Proiect didactic Grupa: mijlocie - Consolidarea mersului in echilibru pe o linie trasata pe sol (30 cm)
 Redresor electronic automat pentru incarcarea bateriilor auto - proiect atestat
 Proiectarea instalatiilor de alimentare ale motoarelor cu aprindere prin scanteie cu carburator

Lucrari de diploma

vezi toate lucrarile de diploma
 Lucrare de diploma - eritrodermia psoriazica
 ACTIUNEA DIPLOMATICA A ROMANIEI LA CONFERINTA DE PACE DE LA PARIS (1946-1947)
 Proiect diploma Finante Banci - REALIZAREA INSPECTIEI FISCALE LA O SOCIETATE COMERCIALA
 Lucrare de diploma managementul firmei “diagnosticul si evaluarea firmei”

Lucrari licenta

vezi toate lucrarile de licenta
 CONTABILITATEA FINANCIARA TESTE GRILA LICENTA
 LUCRARE DE LICENTA - FACULTATEA DE EDUCATIE FIZICA SI SPORT
 Lucrare de licenta stiintele naturii siecologie - 'surse de poluare a clisurii dunarii”
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
 Proiect atestat informatica- Tehnician operator tehnica de calcul - Unitati de Stocare
 LUCRARE DE ATESTAT ELECTRONIST - TEHNICA DE CALCUL - Placa de baza
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 Proiect atestat tehnician in turism - carnaval la venezia




Raport de Cercetare - Promovarea aplicatiilor de vedere artificiala
Proiect de specialitate: Operator tehnica de calcul - Circuite logice pentru functiile 'si-nu', 'sau-nu'
Analiza de senzitivitate a unei probleme de programare liniara
MICROSOFT WORD
Infrastructura tehnologica a CE. Server-e Web
Functiile unui sistem informational
Sistemul de operare Windows XP
Sumatoare paralele pe principiul conservarii transportului


Termeni si conditii
Contact
Creeaza si tu