Sinteza unui dispozitiv secvential de inmultire a numerelor binare reprezentate in complement de doi prin procedurile Andrew Booth

Sinteza unui dispozitiv secvential de inmultire a numerelor binare reprezentate in complement de doi prin procedurile Andrew Booth

In baza procedurii Robertson, aportul sirului la produsul P = X*Y este dat, in cazul specificat (3.11), de partea din produsul P pe care o notam cu si carei valoare, luand in consideratie ponderile asociate bitilor prin analogie cu cele din fig. 3.3, este :

unde s-a facut uz de cunoscuta dezvoltare +.+1). Interpretand cele din (3.12), rezulta ca cele (k+1) adunari reclamate pentru aportul la produsul P a partii data de (3.11) pot fi substituite prin doar doua operatii, o adunare si o scadere. Mai exact, la parcurgerea secventei binare de la stanga la dreapta, atunci cand se intalneste o tranzitie din 0 in 1, adica avem perechea binara=01, se efectueaza o operatie de adunare, tot asa cum atunci cand se intalneste o tranzitie din 1si 0, adica avem perechea binara =10 se efectueaza o operatie de scadere. Cand insa nu avem tranzitii, cand bitii formeaza siruri cu valori binare identice (prin (3.12) s-a aratat cazul unui sir de unitati binare, dar in mod simplu, rezulta ca si un sir de zerouri binare se comporta similar), adica atunci cand perechea binara este fie =00, fie =11, nu se efectueaza nicio operatie.

Mergand pe aceeasi linie, dar dorind sa punem in relief si alte caracteristici, din care nou fara a pierde din generalitate, sa consideram ca avem un numar fractionar negativ, de forma :

In acest caz, luand in consideratie (3.6), pentru produsul final P putem scrie:

Relatia (3.14) confirma, pe o parte, anterioarele supozitii si, pe de alta parte, se poate arata ca evaluarea lui P se realizeaza in mod corect, in sensul ca :

Legat de (3.13) mai trebuie sa facem o remarca vizand situatia bitului celui mai putin semnificativ (least significant bit - lsb) relativ la inspectie. Asa cum am convenit, simultan se tatoneaza, de la stanga la dreapta, valoarea a doi biti, dar cand se ajunge la lsb, acesta ramane singur. Aceasta implica extensia, multiplier-ului X cu un bit de zero la dreapta celui lsb, prin care nu se afecteaza valoarea, deci, de fapt, pentru X_c2 din (3.13), avem:

unde =0 este bitul adaugat.

Sintetizand cele expuse si luand in consideratie extensia lui X cu =0 la dreapta, putem introduce ceea ce literatura denumeste recodificarea lui Booth (Booth's recoding) [Parh 00] [Heye 98],[Heye 94], aceasta constand din recodificarea multiplier- ului (multiplaier recoding) in asa numita signed digit form caracterizata prin faptul ca cifrele multiplier- ului sunt prevazute cu semn. In acest sens, apelam la conventia conform careia multiplier- ul X este parcurs de la stanga la dreapta fapt sugerat si de notatia perechii de biti , incepand deci cu i= n-1 si terminand cu i= 0, fiind bitul curent) si atunci cand perechea =01 pentru bitul curent al formei recodificate se foloseste 1 (de fapt +1), iar cand perechea =10 pentru bitul curent al formei recodificate se foloseste (de fapt, -1), in ambele celelalte doua situatii, pentru =00 si =11, utilizandu-se de 0 pentru bitul curent al formei recodificate. Astfel, considerand multiplier-ul operatiei noastre exemplul fig. 3.9, fig. 3.12; forma sa recodificata Booth, pe care o notam , se obtine conform cu cele din fig.3.13. Ca valoarea lui este corecta, rezulta pe baza calculului:

S-a insistat asupra recodificarii multiplaier-ului pentru ca, in fond, ea sta la baza producerii de inmultire Both in sensul ca ea indica microoperatile pe care trebuie sa le realizeze, la un moment dat dispozitivul de inmultire (un bit de 1 in (fig. 3.13) semnificand ca trebuie executata o adunare urmata de o deplasare, un bit de semnificand ca trebuie executata o scadere urmata de o deplasare, iar un bit de 0 determina doar o deplasare). Mai mentionam ca spre deosebire de procedura Booth la care se efectua o singura scadere si aceea doar pentru un multipleier X negativ, procedura Booth, asa cum se prefigureaza va apela mult mai frecvent la operatia de scadere, dar acest fapt nu deranjeaza avand in vedere implementarea simpla a acestei operatii prin adunarea complementului de doi (fig. 3.11). Apare insa un aspect legat de scaderi si anume acela ca, pe parcursul procedurii, pot aparea in mod alternativ in functie de valorile operanzilor produse partial atat pozitive cat si negative, ori acest lucru are importanta prin prisma operatiei de deplasare la dreapta care impune introducerea in bitul cel mai semnificativ (moust significant bit - msb ) a unei valori binare care sa nu afecteze valoarea (0 pentru un produs partial pozitiv si 1 pentru unul negativ). Dezideratul reliefat isi gaseste o solutie tehnica simpla prin recircularea valorii binare a msb. Cu aceste precizari si adoptand o adoptand o prezentare comparativa in raport cu procedurile deja expuse, prezentam in fig. 3.14 in termenii limbajului devenit uzual, secventa de cod corespunzatoare procedurii Booth. Conex de aceasta, in fig.3.15 avem dispozitivul hardware a carui sinteza sa necesite cat mai putine modificari fata de celelalte scheme (fig. 3.6, fig. 3.11), astfel incat reconfigurarea sa se realizeze cat mai simplu.

Comentand algoritmul, este de remarcat declararea registrului Q, care are adaugat, fata de registrul omolog de la celelalte versiuni, rangul Q [-1], pentru a face pereche cu Q[0], asigurand efectuarea inspectiei simultane a doi biti. Functia de deplasare la dreapta a registrului Q se extinde si asupra acestui al 8- lea rang (vezi enuntul cu eticheta RIGHTSHIFT ). Starea lui Q [-1] se impune initializata, asa cum am convenit, prin stergerea continutului sau, actiune atribuita semnalului , care controleaza incarcarea celorlalte ranguri ale registrului Q cu multipleier-ul X din INBUS. Tot asa cum la intrare se impun specificate, la iesire, rangurile lui Q, care contin partea mai putin semnificativa a produsului fiind descarcata prin in OUTBUS.

Esentiala caracteristica distinctiva o constituie testarea simultana a valorilor unei perechi de biti, incepand cu perechea bitilor mai putin semnificativi si progresand bit cu bit inspre cel de semn pe masura ce multiplier-ul este deplasat la dreapta. Ar mai fi de remarcat recircularea continutului rangului msb ar registrului A(A[7]: = A[7]), precum si faptul ca la scrierea codului (fig. 3.14), tratarea bitului de semn a fost atribuita partii centrale (corpului) a procedurii si nu partii finale (de ajustare si predare a rezultatului) cum s-a solutionat la metodele anterioare ceea ce implica unele modificari de configurarea enunturilor.

In fig. 3.16 este parcurs prin noua procedura acelasi caz exemplu de inmultire abordat in fig. 3.9 respectiv in fig.3.12. Ca o prima observatie, ar fi faptul ca secventa de operatii, inclusiv de semnale de control, corespunde intocmai structurii binare a inmultitorului recodificat (fig. 3.13) parcurs - in mod evident prin discutiile purtate - de la lsb inspre msb. A doua observatie este legata de complexitatea metodei exprimata in functie de numarul semnalelor de control generate care dau o masura pentru capacitatea de trecere (throughput), implicit performanta proceduri. Daca, sub acest aspect, ne-am fi asteptat ca abordarea exemplului sa duca prin metodele anterioare (fig.3.9 respectiv fig.3.12) la acelasi rezultat, conjunctural multiplier- ul X avand, atat in cod SM, cat si in cod acelasi numar de unitati binare (5) cat si de zerouri (3). Dar prin procedura Booth, speram sa castigam in performanta si lucrul acesta nu s-a intamplat. Motivatia o gasim daca analizam forma din fig. 3.13, care implica acelasi numar de activari a sumatorului (5) ca si celelalte metode. (Este momentul sa subliniem ca nu conteaza ca unele (3) din numarul total (5) de activari ale sumatorului il folosise pe acesta in calitate de scazator intrucat semnalele de complementare () si de adunare () sunt derivate de acelasi impuls de CLOCK, chiar daca sunt usor decalate - il precede pe - pentru ca strobarea (prin ) rezultatului la iesirea schemei combinationale care este sumatorul sa se faca in mod corect.) Se poate conchide ca procedura Booth o imbunatatire de performanta la exemplu din fig. 3.16 datorita configuratiei binare a multipleier- ului X. Dar in situatia cand X_c2 prezinta siruri dimensional semnificative de unitati sau de zerouri binare, atunci la corespondenta forma recodificata creste numarul de zerouri, ceea ce duce la imbunatatirea performantei prin cresterea capacitatii de trecere.

Este insa posibil ca un anumit multiplier sa prezinte frecvente alternante a bitilor (de tipul 0101), caz in care poate aparea, nu o imbunatatire, ci o degradare, chiar dramatica, de performanta. Astfel, daca avem in cadrul lui X un 1 flancat de 0-uri (010), atunci in termeni de procedura Robertson, este revendicata o singura operatie de adunare (corespunzatoare lui 1), pe cand, in termeni de procedura Booth sunt necesare o adunare (corespunzatoare perechii 10), succedata imediat de o scadere (corespunzatoare perechii 10). Totusi, analizand mai amanuntit tripletul =010, avem situatia din fig.3.17, unde prin am notat recodificarea Booth, conform cu fig. 3.13.

Fara dificultate se poate observa ca cele doua operatii corespunzatoare lui poate fi substituite printr-o adunare. Adica, atunci cand la parcurgerea lui se intalneste tripletul , trebuie efectuata o singura operatie de adunare, asa cum este prezentat si pentru . Prin rationamente similare, atunci cand parcurgand pe se intalneste tripletul =101, trebuie efectuata o singura operatie de scadere, asa cum este prezentat pentru in fig.3.18.

Cele doua noi forme , respectiv , corespund unei noi recodificari a multiplier-ului, asa numita recodificare canonica (canonical multiplier recording), careia ii corespunde asa numita conical signed digit form [Haye 88]. Aceasta noua recodificare sta la baza unei noi proceduri atribuite lui Booth, care, pentru a putea fi distinsa de anterioara, a primit denumirea de procedura Booth modificata (modified Booth 's algorithm[Parh 00][Haye 98],[Bo Ti 05](de unde indicii MB ai anterioarelelor forme din fig.3.17 si fig.3.18). Recodificarea canonica pastreaza regulile utilizate la anterioara forma ( se conserva corespondentele pentru perechile binare din si 00 → 0, respectiv 11 → 0, cu exceptia valorilor izolate de 1, respectiv 0, cand regulile de codificare sunt cele din fig.3.17, respectiv fig.3.18. Ca si anterior, sunt inspectati simultan doi biti, dar deplasarea la dreapta se realizeaza, de fiecare data cu cate o singura pozitie binara, in consecinta, pentru a detecta daca un anumit bit este izolat sau nu trebuie retinuta intre "istoria"valorilor binare traversate. In acest sens se apeleaza la un bistabil fanion (flag) care urmareste sa distinga intre valori binare izolate si doua sau mai multe valori identice, adica un sir (run) de valori. Notam flag-ul cu R (de la run, si pentru a-l distinge de F de la procedura Robertson) si specificam urmatoarele conventii de setare a acestuia :

Initial, R este sters;

Se parcurge multiplier-ul , de aceasta data, de la dreapta spre stanga, inspectandu-se simultan, ca si anterior, cate doi biti. Fiind parcurgere in sens invers fata de anterioara procedura Booth se impune extensia multiplier-ului cu un bit la stanga lui msb. Pentru a nu afecta valoric multiplier-ul, se realizeaza extensia bitului de semn.

Daca la parcurgerea anterior specificata, a multiplier-ului se intalneste perechea de biti =01, starea lui R nu se modifica. Daca in schimb, se intalneste perechea =11, atunci starea lui R trebuie modificata, flag-ul fiind setat pe 1.

Daca la parcurgerea, in continuare a multiplier-ului se intalneste perechea de biti =10, starea lui R nu se modifica. Daca, in schimb, se intalneste perechea =00, atunci starea lui R trebuie modificata, flag-ul fiind resetat pe 0.

Conventiile 3 si 4 sunt aplicate, alternativ, in mod repetat pana la traversarea intregii secvente binare a lui

Sintetizand toate regulile referitoare la obtinerea recodificarii canonice a multiplier - ului, obtinem cele cuprinse in tabelul din fig.3.19, in care in calitate de intrari avem perechi de biti inspectata , formata din bitul curent si cel imediat succesiv la stanga , precum si valoarea curenta a flag-ului R. Iesirile sunt reprezentate de valoarea curenta a bitului (cu semn) al formei recodificate, respectiv noua stare in care trece flag - ul R , notata . Comentand tabelul, se observa ca tripletii(0,1,0) respectiv (1,0,1) corespund cazurilor unor valori binare flancate de valori opuse, atunci cand se efectueaza doar o operatie, adunare (=1) in cazul lui 1 izolat, respectiv scadere ( ) in cazul lui 0 izolat. Apoi tripletii (0,0,1), respectiv (1,1,0) marcheaza inceputurile unor siruri de 0-uri, respectiv 1-uri, cand are loc bascularea flag - ului R. La tripletii (0,1,1), respectiv (1,0,0) exista incertitudine cu priviri la faptul ca tranzitia, prezenta in ambele cazuri, reprezinta un bit izolat sau un sir de biti, ceea ce determina sa nu fie efectuata vreo operatie (, in ambele cazuri) si starile flag - ului sa fie conservate. Aceasta din urma, situatie se petrece si in cazul tripletilor extremi (0,0,0), respectiv (1,1,1).

Sa aplicam cele cuprinse in fig.3.19 la multiplier - ul cazului exemplu din fig.3.9, fig.3.12 si fig.3.16. Multiplier - ul este parcurs de la dreapta la stanga, primul triplet (1,1,0) fiind format din si R=0 (initial) si el determina, conform fig.3.19 si R=1, dupa care urmatorul triplet este si R=1, si asa mai departe. Interpretand configuratia obtinuta pentru , avem:

-

Revenind la tabelul din fig.3.19, parcurgerea lui X de la dreapta la stanga, incepand cu cifrele binare de cea mai mica pondere si cu extensia spre stanga a bitului de semn, este fireasca, permitand evidentierea prin forma decodificata, doar in acest mod, a numerelor pozitive de cele negative. Tot din respectivul tabel, poate fi dedusa in mod facil, ecuatia booleara corespunzatoare setarii flag -ului R, anume :

in care prin R s-a notat iesirea bistabilului corespunzator flag-ului.

In acelasi context al detalierilor legate de noua recodificare a lui X ar mai fi de semnalat un aspect aparte legat de valorile izolate ce pot duce la repetarea unei anumite unitati binare cu semn (1, respectiv ), principial de mai multe ori pana la intalnirea unei unitati binare de semn contrar (vezi si exemplul din fig. 3.20, intre cei doi extremi apar doi de 1). Acest fapt se deosebeste radical fata de anterioara recodificare Booth a carei caracteristica, prin aceasta prisma, este ca unitatile binare cu semn (1 si ) se alternau (putand sau nu sa fie separate de valori 0, vezi si exemplul din fig. 3.13). Tradusa in termeni de operatii, respectiva alternanta a adunarilor si scaderilor exclude aparitia depasirii capacitatii registrelor, a overflow-ului. Dar la noua recodificare Booth, datorita aspectului semnalat, este posibila aparitia overflow-ului, ca, de altfel, si la metoda Robertson. La ambele metode, fenomenul overflow este important prin prisma valorii care se introduce in rangul cel mai semnificativ al registrului A (la noi A[7]) la deplasarea la dreapta. Daca la procedeul Robertson, aparitia overflow-ului (spre exemplu, inmultind cu , apar, in cascada, 6 situatii de overflow la toate adunarile, exceptand prima) este "benigna" in sensul ca valoarea deplasata in A[7] este prestabilita din considerente deja discutate si, in consecinta, am ignorat fenomenul. In cazul noii proceduri Booth, overflow-ul revendica o analiza speciala, aparitia lui fiind in stransa corelatie cu semnele valorilor operate - in A[7] pentru produsele partiale, respectiv in M[7] pentru multiplicand- , precum si cu "istoria" operatilor urmarita prin starea flag-ului R. Legat de acesta din urma, investigand in fig. 3.19, putem observa faptul ca, parcurgand X in sensul convenit, atunci cand R devine 0, se efectueaza o adunare succedata de o shift-are si, pe parcursul cat R ramane 0, se mai pot realiza adunari (dar numai adunari, nu si scaderi) urmate de shift-ari sau doar shift-ari. In mod similar, parcurgand X in acelasi sens convenit, atunci cand R devine 1, se efectueaza o scadere, succedata de o shift-are si, pe parcursul cat R ramane 1, se mai pot realiza scaderi (dar numai scaderi, nu si adunari) urmate de shift-ari sau doar shift-ari.

Inainte de a trece la analiza situatilor care se pot ivi relative la contextul mentionat, precizarilor de mai sus sa le adaugam unele notatii legate de cele patru variabile booleene de interes. Astfel, prin R notam starea flag-ului de istoric, prin OVR notam starea unui imaginar bistabil flag indicator al starii de overflow, prin A[7] notam starea rangului cel mai semnificativ (de semn) a unui produs partial, toate cele trei stari considerate la momentul terminarii unui pas de adunare sau scadere, si, in fine, prin M[7] notam starea perpetua, pe parcursul inmultirii, a rangului de semn al multiplicand-ului. Examinand, in mod exhaustiv, combinatiile binare ale acestor variabile, obtinem tabelul din fig. 3.21.

Ultima coloana a tabelului corespunde variabilei asociata urmatoarei valori care se introduce in A[7] (next A[7], NA[7]) in procesul de deplasare dreapta. Valorile din aceasta coloana rezulta dupa investigatii efectuate dupa modelul sugerat in fig. 3.21. Pentru inceput, se considera R=0 ceea ce implica operatii de adunare. Apoi, se ia perechea binara (0,0) pentru vechea (de dinaintea adunarii) valoare din A[7] si cea (perpetua) din M[7] si se combina cu toate perechile posibile pentru rangul [6] in conditiile in care in acest rang se capteaza sau nu transport (carry=1, respectiv 0). Rezulta cele patru situatii din fig. 3.22, pentru fiecare evaluandu-se noua (de dupa adunare) valoare din A[7] si variabila OVR (operand EX-OR valorile de carry rezultate din rangurile 6 si 7). Pentru perechea (OVR, A[7]) se obtin (0,0) si (1,1), in ambele situatii insa adunand doua numere pozitive deci rezultatul trebuie sa fie pozitiv, ceea ce este evident doar pentru perechea (0,0). In celalalt caz, (1,1), rezultatul este negativ (A[7]nou=1), dar se genereaza si OVR=1, ceea ce previne ca NA[7]=1, si, deci, pentru ambele cazuri, NA[7]=0 (vezi cvartetii (0,0,0,0) si (0,1,1,0)

din fig. 3.20).

R OVR A[7] M[7] NA[7]

Fig.3.21

Investigarea descrisa pentru combinatia (0,0) pentru (A[7] vechi, M[7]), trebuie sa fie repetata, cand R=0, si pentru celelalte

combinatii ((0,1), (1,0) si (1,1)), dupa care totul trebuie reluat pentru R=1.

Lucrurile se pot simplifica intrucatva, intrucat R=1 (scadere) si M[7]=1, poate fi asimilat cu R=0 si M[7]=0, dar, in general, o scadere asistata de calculator este recomandabila.

Pentru coloana NA[7] din fig. 3.21 rezulta valori logice definite (0 si 1), unele dintre acestea marcate cu " * ", asupra carora vom reveni, iar unora dintre cvartetii binari le corespunde semnul " - ", folosit in scopul evidentierii unor combinatii imposibile in sensul ca, in nici unul din cele patru cazuri, nu poate fi generat overflow. Insistand asupra cvartetului (0,1,0,0), se observa ca la M[7]=0, atunci cand A[7]=0, rezulta OVR=0, precum si atunci cand A[7]=1, rezulta OVR=1, deci este exclusa (OVR, A[7]=10) (partial demonstrat si in fig. 3.22).

Adoptand pentru respectivii cvarteti o valoare logica indiferenta (don't care, d), pentru obtinerea expresiei booleene minimizate a lui NA[7] facem uz de diagrama Veitch - Karnaugh din fig. 3.23. Acoperirea favorabila a unitatilor binare in combinatie cu valori d, duce la urmatoarea expresie pentru NA[7] :

Concluzia sintetizata in relatia (3.18) se putea anticipa in sensul ca in A[7] se recirculeaza anterioara valoare din respectivul rang dupa modelul si cu motivatia de la prima procedura Booth exceptand cazurile de overflow, cand valoarea obtinuta dupa operatie in A[7] nu este corecta (spre exemplu, la adunarea a doua numere pozitive, rezulta A[7] =1, iar la adunarea a doua numere negative, rezulta A[7] =0), dar prin OVR=1 operat EX - OR cu valoarea din A[7].

Consideram totusi utila introspectia in intimitatea mecanismelor procedurii intrucat ea ne poate conduce inspre variante cel putin echivalente pentru sinteza schemelor. In acest context, sa revenim la cvartetii a caror valori NA[7] din fig. 3.21 au fost marcate cu "* ". Chiar daca, efectuand analize de tipul celei din fig. 3.22, rezulta valorile definite din coloana NA[7]; cvartetii binari corespunzatori acestora este exclus sa apara pe parcursul procedurii, motivatia acestui fapt nefiind imposibilitatea generarii overflow-ului ca in cazul cvartetilor carora le corespunde "- " pentru NA[7]. Luand, spre exemplu, cvartetul (0,0,0,1) si analizand cazurile posibile dupa modelul din fig. 3.21, putem constata ca raman de interes doar situatiile din fig. 3.24, dar nici una dintre acestea nu poate sa apara in realitate. Astfel, concentrandu-ne asupra cazului a) si luand in consideratie ca prin deplasare la dreapta valoarea absoluta a produsului partial va fi cel mult egala cu respectiva valoare injumatatita, pentru toate situatiile practice cand R=0 (de fapt se scade valoarea multiplicand-ului Y dintr-o valoare oricum mai mica decat Y), este exclusa aparitia lui carry=1, ceea ce implica eliminarea combinarii lui R=0 si M[7]=1 cu OVR=0 si A[7]=0.

Cazurile b) si c) din fig. 3. 24, care ar corespunde unor prealabile conditii de overflow (A[7]A[6]=01 in urma deplasarii lui A), se exclud, de asemenea, prin rationamente asemanatoare. Intrucat si ceilalti cvarteti - carora le corespund valori NA[7] marcate cu "* " - (0,0,1,0) cu corespondentul echivalent comportamental (1,0,1,1), respectiv (1,0,0,0) echivalent comportamental cu deja analizatul (0,0,0,1) -, supusi unor astfel de analize, conduc la concluzii similare, se poate amenda sinteza pentru functia booleana NA[7].

In fig. 3.25 se prezinta o diagrama Veitch - Karnaugh in care pentru anterioarele unitati binare corespunzatoare cvartetilor (0,0,1,0) si (1,0,1,1) apar, in virtutea celor de mai sus, valori logice indiferente d, care valori apar, suplimentar, pentru cvartetii pereche (0, 0,0,1) si (1,0,0, 0). Uzitand de valorile d intr-un mod diferit fata de cel preconizat la fig. 3.23, acoperirea favorabila a unitatilor binare conduce la urmatoarea expresie pentru NA[7] :

In conformitate cu (3.19), aparitia overflow-ului este complet mascata, fiind ignorata in totalitate la sinteza dispozitivului de inmultire. Desigur, in termeni de circuite, castigul nu este spectaculos (in ultima instanta, o poarta EX-OR), dar, in ansamblu, cu luare in consideratie a performantei (stiuta fiind lentoarea portilor EX-OR fata de alte porti, independent de tehnologie [ITRS01], [Wake00] ),uzitand de (3.19) poate rezulta o imbunatatire. Aceasta este posibil sa se piarda, in parte sau integral, cand avem un multiplicand Y negativ (M[7]=1) si multiplier-ul X are in pozitiile cele mai putin semnificative unul sau mai multi biti de 0. In aceste conditii, prin deplasari succesive ale lui X pana la atingerea primului sau bit de 1, in A[7] ar trebui sa se introduca 0 (NA[7]=0), ori prin (3.19) rezulta si, in mod fals, se introduc unitati binare, ceea ce se impune evitat.

Odata comentate aspectele specifice legate de procedura Booth modificata, prezentam in fig. 3.26, in termenii limbajului deja familial, secventa de cod pentru noua metoda. Rezultatul sintezei dispozitivului hardware asociat este dat in fig. 3.27. Prezentand

lucrurile comparativ cu celelalte dispozitive de inmultire, se remarca faptul ca registrul Q este pe 9 biti, ca si in fig. 3.15, dar de data aceasta rangul suplimentar (Q[8]) este folosit pentru stocarea initiala a semnului fiind intercalat intre registrele A si Q. De fapt, semnul multiplier-ului X este dublat, aparand, la inceput, in rangurile Q[8] si Q[7]. Pe de alta parte, la acest algoritm a fost introdus un test al faptului daca unul dintre operanzi este zero, situatie in care se trece direct la predarea rezultatului zero in magistrala OUTBUS.

In fine, ultimul element distinctiv al sintezei din fig. 3.26 il reprezinta flag-ul R, a carui stare, in baza ecuatiei (3.19) este operata EX-OR cu starea lui M[7], dand valoarea particulara care se introduce in A[7]. Mai exact, in rangul A[7] (a carui stare este initializata, prin c₀, impreuna cu celelalte ranguri ale lui A) se introduce fie valoarea 0, la c₄, fie rezultatul EX-OR-ului,la c₉, ambele aceste semnale de control fiind prevazute sa apara, la momentele oportune si simultan cu c₃ care are menirea de a "impinge" inspre dreapta valorile binare din A[7] pana la Q[1]. Acestea sunt operatiile care vizeaza registrul A si care au fost sugerate ca in fig. 3.27. Mai trebuie remarcata implementarea particulara a ecuatiei booleene (3.17) folosind intrarile asincrone, de setare si resetare ale unui bistabil considerat, fara a pierde din generalitate, de tip D, aceasta reprezentand, evident, doar una din variantele de sinteza posibile.

Si pentru ca tot am amintit de variante de sinteza, sa fructificam concluziile anterioarei dezbateri relativ la valoarea de introdus in A[7] "grefand" modificarile ce se impun atat la secventa de cod din fig. 3.26, cat si la sinteza din fig. 3.27. Acestea sunt rezumate in fig. 3.28, fiind de remarcat, cu referire la cod, completa renuntare la enuntul prevazut cu eticheta TES1, implicit a semnalului c₄, problema shift-arii peste 0-urile "din coada" lui X, atunci cand Y este negativ, fiind rezolvata corect prin ecuatia (3.18), OVR fiind 0. Desigur, in enuntul RIGHTSHIFT, se substituie (3.19) prin (3.18) si se elimina si c₉, deplasarea pe intreaga lungime A .Q, inclusiv inspre rangul A[7], fiind asigurata prin c₃ (vezi partea de schema din fig. 3.28). La prima vedere mai simpla, aceasta solutie tehnica ar putea aduce o degradare globala de performanta intrucat lantul celor doua porti EX-OR (prima generand variabila OVR prin operarea EX-OR a lui cu intrarea de carry in bitul de semn, , iar a doua implementand (3.18)), ar putea revendica cresterea perioadei trenurilor impulsurilor de CLOCK. Iar din considerente de functionare fiabila, un flag OVR in locul marcat punctat in fig. 3.28, este de dorit. Setarea acestuia ar urma sa se faca la fiecare activare a sumatorului paralel printr-un semnal (corespunzator decalat pentru a asigura acoperirea propagarii semnalelor pe caile cele mai defavorabile). Concluziv, balansand cele doua versiuni, se poate afirma ca ele se prezinta intr-un quasi-echilibru, decisiva la alegere fiind tehnologia disponibila.

Ca si in cazul celorlalte metode de inmultire, in fig. 3.29 aplicam procedura Booth modificata la acelasi caz, exemplul tratat in fig. 3.9, fig. 3.12 si fig. 3.16. Ca si la anterioara metoda Booth, secventa operatiilor este conforma intocmai cu structura binara a inmultitorului recodificat canonic (fig. 3.20) parcursa de la lsb inspre msb. Remarcam, de asemenea, ca in fig. 3.29 a fost prevazuta coloana OVR cu toate ca exemplul a fost parcurs prin procedura din fig. 3.26. Valoarea variabilei OVR nu a mai fost marcata, in cazul exemplului considerat ea pastrand valoarea initiala 0, care operata EX-OR cu valoarea bitului A[7] da aceeasi valoare pentru NA[7], care urmeaza a fi introdusa in rangul cel mai semnificativ din A.

Facand referiri finale la complexitatea si performanta procedurii Booth modificate, aceasta se incadreaza in clasa de algoritmi deja prezentati, putand insa obtine, in cazul unor structuri binare favorabile (subaspectul recodificarii canonice) a multiplier-ului (cu precadere cand numarul de biti este mare, probabilitatea de a profita de caracteristicile de accelerare ale metodei devenind sporite), substantiale reduceri ale capacitatii de trecere. Chiar daca redusa, o astfel de imbunatatire, constand din eliminarea unei activari a sumatorului paralel, poate fi constatata la exemplul din fig. 3.29.