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:

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).

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(x₀), 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).

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

P_i+1=P_i+  (3.1)

unde P_i+1 este noul produs partial obtinut prin adunarea la precedentul (P_i) a produsului de un bit al lui Y deplasat la stanga corespunzator (echivalent cu inmultirea cu 2, adica x_i). Rezultatul (P=10110110₂=182₁₀) se obtine la finele ultimei iteratii. Pe parcursul operarii, conform cu (3.1), fiecare iteratie necesita stocarea doar a doua numere (P_i, 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, P_i+1 este noul produs partial obtinut prin deplasarea la dreapta (echivalenta cu impartirea la 2, adica ) a precedentului produs P_i 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.