Inmultitoare binare si algoritmi

Binary multipliers (Inmultitoare binare)

1 Caracteristici generale ale implementarii operatiei de inmultire in calculator

Fie: X - multiplier;

Y - multiplicand; X*Y=P

P - product;

Pentru a efectua produsul exista mai multe solutii:

Bazata pe utilizarea unui numarator care sa asigure adunarea repetata a multi­plicand-ului Y la el insusi de un numar de ori egal cu valoarea multiplier-ului X;

Operatia se poate efectua adunand produsele partiale de 1 bit corespunzator deplasate dupa clasicul exemplu al efectuarii operatiei cu creionul pe hartie. Stocarea acestor produse intermediare de 1 bit deranjeaza prin spatiul de memorie revendicat de aceea in calculator nu se implementeaza aceasta forma ci o proxima forma.

Bazata pe calculul unor produse parsiale de tipul . Intr-o maniera secventiala pastrand fix ca pozitie produsul partial si deplasandu-l pe Y se efectueaza adunari repetate.

Uneori este favorabil sa nu se pastreze fix produsul ca pozitie ci sa se pastreze fix ca pozitie Y, deplasandu-l nu la stanga ca in cazul c) ci deplasand produsul partial la dreapta.

2 Dispozitiv secvential pentru inmultirea numerelor reprezentate in semn-marime

Vom prezenta o structura de dispozitiv de inmultire care permite corespunzator unor operanzi de n biti efectuarea operatiei de inmultire in n cicluri de clock. Pentru a efectua operatia sunt necesare 3 registre in care sa fie stocati in prima instanta operanzii, intr-o alta instanta produsele intermediare si in ultima instanta produsul final. Vom considera ca operatia de inmultire se efectueaza intre numere fractionare pe 8 biti dintre care bitul cel mai semnificativ este bitul de semn.

Schema este compusa din urmatoarele componente:

magistrala bidirectionala, impartita in 2 parti;

3 registre, fiecare pe 8 biti:

registrul Q(quetient) stocheaza initial operandul inmultitor(multiplier) X;

registrul M stocheaza pe tot parcursul operatiei celalalt operand de­inmultitul Y;

registrul A(acumulator) initial este sters si el impreuna cu registrul Q formeaza un registru de deplasare pe 16 biti, in acest registru A.Q vor fi stocate produsele partiale si in final rezultatul inmultirii pe 2*8=16 biti dintre care cei mai semnificativi sunt in registrul A si cei mai putin semnifi­ca­tivi sunt in registrul Q.

un sumator parallel pe 8 biti;

o unitate de control care se ocupa de semnalele de control.

unde , si sunt bitii de semn, iar , si bitii de marime.

Avand in vedere ca partile de marime ale numerelor sunt pe 7 biti produsul poate fi pe maxim 14 biti. Operatia se desfasoara printr-o secventa de pasi de adunare/deplasare descrisi astfel:

Deplasarea la dreapta cu o pozitie este echivalent cu a imparti numarul la 2.

Pe parcursul operatiei bitul inmultitorului care a fost deja operat nu mai este necesar ulterior in cadrul calculelor ti el poate fi eliminat. Renuntarea la el se face prin deplasarea dublului registru A.Q cu o pozitie la dreeapta si proximul bit va fi in rangul sel mai putin semnificativa registrului Q.

Testarea valorii lui se face mereu din bitul al registrului Q si acesta e aranjamentul favorabil care a facut ca in calculator implementarea operatiei sa se realizeze prin inmultitor deplasabil si prin produs partial deplasabil(a 4-a versiune din paragraful anterior). Pe aceasta schema au fost marcate valori pentru legaturi care reprezinta dimensiunea legaturii, exceptie facand acele legaturi constituite dintr-un singur fir. Semna­lele de control au fost reprezentate printr-o linie intrerupta spre deosebire de cele de date care sunt reprezentate printr-o linie continua.

Functionarea unei asfel de structuri se poate descrie principial in doua moduri distincte: fie printr-o ordinograma("flow chart"), fie printr-o descriere printr-un limbaj hard de tipul VHDL. Ordinograma este o schema logica care este caracterizata prin doua categorii de blocuri:operative si decizionale. Blocurilor operative li se aloca microoperatiile care pot fi "aglomerate" pe acelasi impuls de clock, iar blocurilor decizionale le corespunde testerea anumitor conditii in functie de care pot fi efectuate salturi, respectiv pot aparea bucle in reprezentarea prin ordinograma.

Ordinograma:

COUNT7 reprezinta starea nemodificata a lui 1 peste tot in numaratorul COUNT, adica stare corespunzatoare starii pasilor(celor 7 pasi de adunare/deplasare ) cand se iese din aceasta bucla dupa SAU-EXCLUSIV in bitulse introduce semnul si se face ajustarea produsului.

Pentru descrierea functionala care este prezentata printr-o ordinograma, alternativa se obtine printr-un limbaj de descriere hardware VHDL(Very Hardware Description Language) a lui Charles Bebbage.

O descriere VHDL a unui sumator incomplet este:

entity half-adder is

port(x,y:in bit,sum,carry:out bit);

end half-adder;

arhitecture behavior of half-adder is

begin

sumx XOR y;

carryx and y;

end behavior;

arhitecture structure of half-adder is

component xor-circuit port(a,b:in bit,c:out bit);

end component;

component nand-gate port(d,e:in bit,f:out bit);

end component;

signal alpha:bit;

begin

XOR:xor-circuit portmap(ax,by,csum);

NAND1:nand-gate portmap(dx,ey,falpha);

NAND2:nand-gate portmap(dalpha,ealpha,fcarry);

end structure;

Exista doua parti esentiale:

partea de entity, care constituie un enunt formal al structurii sistemului ca si cand ar avea o singura componenta. Aceasta parte descrie conexiunile sistemului cu sisteme, dispozitive externe fara a descrie in nici un fel comportarea si structura interna a sistemului. Prin partea de entity se specifica numele sistemului si se specifica semnalele de intrare/iesire(in/out) cu numele acestora. Se precizeaza ca semnalele se identifica prin teminalele lor, care poarta si denumirea de porturi. Se face distinctie intre iesiri si intrari prin numele in/out si se specifica dimensiunea iesirilor si intrarilor prin numarul de biti, care in cazul in care dimensiunea este de un bit se scrie "bit". Partea de entity corespunzator acestui sistem corespunde in forma grafica unui dreptunghi cu doua intrari(x, y) si 2 iesiri(sum, carry).

Fig.

Partea de entity reprezinta descrierea sistemului la nivelul cel mai inalt.

pentru descrierea comportamentului sistemului si a descrierii structurii interne a acestuia exista doua structuri din arhitecture:

• behavior, care face uz de o notatie bogata cu care este inzestrat limbajul, si in aceasta descriere intervine notatia "" care inseamna atribuire de semnale in conformitate cu care variabilele de iesire sum si carry li se atribuie functii booleene predefinite in cadrul limbajului, care conecteaza variabilele de intrare de tipul x si y. In cadrul descrierii se uziteaza de paranteze ( ), de begin si end, in care intervin variabile cu o relatie intre ele intr-o forma specifica limbajelor de programare. Limbajul este bogat in posibilitati de descriere a funcsiilor schemelor.De exemplu:

carryx and y;

if xy='11' then carry=1 else carry=0;

De asemenea limbajul are multe posibilitati:daca aceasta functie este realizata pentru un circuit caracterizat printr-un timp de propagare de 5 nsec, descrierea in cadru limbajului se face astfel:

carryx and y after 5 ns;

Tabelul de adevar tipic primului rang al sumatorului in care primul carry este 0 este urmatorul:

o       structural, in cazul in care se insista asupra structurii interne atunci circuitul si schemele cu un ordin de marime mai mic si atunci sunt descrise in maniera entity, specificandu-se semnalele de intare respectiv semnalele de iesire ale acestora. Legaturile interne(lines, bass) sunt specificate prin signals, dandu-se dimensiunea lor.

In final, intre begin si end, se specifica fiecare tip de circuit, dandu-se de fapt asa numita lista de conexiune specifica cablajului dintre circuitele componente ale sistemului sau dispozitivelor.

O descriere printr-un limbaj de tipul VHDL este flexibil, ea poate fi mai concisa decat o descriere de tip ordinograma, dar apelarea la aceasta in vederea prezentarii este o chestiune greoaie si prin urmare nu vom apela la descrieri, ci la un limbaj de descriere hardware simplificat, care prezinta cateva carecteristici ale VHDL-ului. Vom apela la un limbaj simplificat caracterizat prin:

Se declara registrele prin numele acestora, prin denumirea lor, si prin ordinea rangurilor(de exemplu A[7]);

Se apeleaza la o descriere similara a magistralelor;

Un singur bistabil este inregistrat ca un registru de dimensiune 1;

Microoperatiile care pot fi efectuate neconflictual prin acelasi impuls de clock se separa prin virgula, iar cele care se efectueaza la clock-uri diferite se despart prin " ; ".

In cadrul programului de descriere se inlantuie microoperatiile in ordinea naturala a executiei, fiind separate prin " ; ".

In aceste programe este posibila aparitia unor salturi de tip neconditionat prin "go to" sau salturi conditionate, precedate de testarea conditiilor de tip "if . then".

Consideram structura ca fiind bistabil de tip M-S care pot fi citite/scrise pe acelasi impuls de clock.

De exemplu descrierea unui inmultitor de viteza scazuta care apeleaza la numaratoare:

multiplier bc(IOBUS[16:0]);

register Q[15:0],CQ,MS,CP[31:0];

BEGIN: Q:=INBUS[15:0], QS:=INBUS[16];

CM:=INBUS[15:0], MS:=INBUS[16], CQ:=Q, CP:=0;

TEST1: if CO=0 or CM=0 then goto DONE,

ADD : CQ:=CQ-1, CP:=CP+1;

TEST2: if CQ0 then goto ADD,

SUB : CM:=CM-1, CQ:=Q;

TEST3: if CM0 then goto ADD,

DONE : INBUS[16]:=QS xor MS, INBUS[15:0]:=CP[31:16];

INBUS[15:0]:=CP[15:0];

END.

multiplier (in:INBUS;out:OUTBUS);

register A[7:0],Q[7:0],M[7:0],COUNT[2:0];

BEGIN : A:=0, COUNT:=0, M:=INBUS;

Q:=INBUS;

TEST1 : if Q=0 then goto Bi;

ADD : A[7:0]:=A[6:0]+M[6:0],

Bi : A[7:0]:=0; A[6:0].Q:=A.Q[7:1], COUNT:=COUNT+1;

TEST2 : if COUNT7=0 then goto TEST1,

FINISH: A[7]:=Q[0] xor M[7], Q[0]:=0;

OUTBUS:=A;

OUTBUS:=Q;

END.

3 Dispozitiv de inmultire Robertson

Inmultirea numerelor in complement de 2

Din anteriorul paragraf a rezultat ca reprezentarea numerelor in semn-marime este simplu de implementat, si ca urmare atunci cand avem numere de reprezentat in complement de 2 s-ar putea apela la anteriorul dispozitiv astfel: pentru operanzi negativi se complementeaza de 2 respectivi operanzi si se efectueaza operatia in termeni de numere in reprezentarea semn-marime iar in final, daca e cazul(un operand e pozitiv si altul negativ), se comple­menteaza de 2 produsul. O astfel de procedura ar apela la dispozitivul deja facut. Anterioara descriere implica un "sacrificiu" de 3 impulsuri de clock in cazul cel mai defa­vorabil, adica un operand este poziziv si altul e negativ. Pertru fiecare complementare se sacrifica un impuls de clock, prin urmare aceasta alternativa de implementare este inacceptabila ca performanta. In aceste conditii s-a apelat la dispozitivul Robertson in complement de 2.

Exemplu:

Din prima relatie cu -X rezulta justificarea denumirii de complement de 2.

Complementul de 2 poate fi interpretat ca o parcurgere dinspre partea semnificativa spre partea cea mai putin semnificativa.

Exemplu:

In versiunea Robertson 19 este reprezentat astfel:

Se foloseste aceiasi schema si pentru numere pozitive si pentru numere negative, pornindu-se de la bitul cel mai putin semnificativ. Plecand de la reprezentarea lui Robertson a complementului de 2 operatia de inmultire se poate efectua tratand numerele pozitive si negative intr-un mod unitar ca si cand ar fi pozitive, prin parcurgerea dinspre partea mai putin semnificativa cea mai semnificativa, si tratand bitul de semn ca si un bit ordinar al numarului. Se poate utiliza structura dispozitivului de inmultire in semn-marime la care se vor mai efectua unele ajustari. Efectuam analiza celor 4 cazuri posibile acceptand ca,fara a pierde din generalitate, vom considera inmultirea a 2 numere fractio­nare in reprezentarea:

Reprezinta o inmultire a 2 numere fara semn(pozitive) prin pasi de deplasare succesivi descrisi de:

Se parcurg fara sa apara nimic special de semnalat. Acei biti din X incepand cu care au valoarea 0, produsul partial pe parcursul acestor biti avand tot timpul valoarea 0 iar in bitul cel mai semnificativ al acumulatorului se introduce tot timpul 0. Cand se intalneste intrucat multiplicantul este negativ, produsul partial este negativ, si devenind negativ se introduce 1 in pentru ca in impartirea la 2 in complement de 2 implica introducerea de "leading 1" in loc de "leading 0".

In acest caz se se parcurg aceiasi pasi succesivi descrisi la pasul a pana in final cand in ultimul pas, cel corespunzator bitului de semn, se efectueaza asa numitul pas de corecti in care din produsul partial 0 trebuie sa se obtina produsul negativ reprezentat in complement de 2 si acesta se realizeaza printr-o scadere:

Ambele numere sunt negative si in acest caz se recurge la introducerea in a unui 1 in procesele de deplasare si in plus se adauga pasul de corectie de la cazul c.

Pot fi operate numere negative ti pozitive in complement de 2 printr-o structura care fata de cea cunoscuta de la semn-marime se deosebeste prin faptul ca operatia de adunare nu se executa pe 7 biti ci pe 8 biti si de aceea se impune controlul logic al bitului care se incarca in cel mai semnificativ bit al acumulatorului si acest lucru se face printr-un fanion:

F=( and ) or F

Prin urmare structura inmultitorului Robertson cu corespunzatoarea sa descriere comportamentala in limbajul de descriere Heyes este urmatoarea:

Fig:

C2 multiplier(in:INBUS;out:OUTBUS);

register A[7:0],Q[7:0],M[7:0],COUNT[2:0],F;

bus INBUS[7:0],OUTBUS[7:0];

BEGIN  : A:=0, COUNT:=0, F:=0;

INPUT  : M:=INBUS;

Q:=INBUS;

TEST1  : if Q[0]=0 then goto RSHIFT,

ADD : A[7:0]:=A[7:0]+M[7:0], F:=(Q[0] and M[7])or F;

RSHIFT : A[7]:=F, A[6:0].Q:=A.Q[7:1],

COUNT:=COUNT+1,

if COUNT7=0 then goto TEST1;

TEST2  : if Q[0]=0 then goto OUTPUT,

SUBTRACTION: A[7:0]:=A[7:0]+M[7:0],

Q[0]:=0;

OUTPUT : OUTBUS:=A;

OUTBUS:=Q;

END.

Cu c1,c12,,c6 au fost notate semnalele de control, ele fiind puse in dreptul instructiu­niilor pe care le executa.

Exemplu:

Sinteza unitatii de control

Aceasta sinteza se poate face dupa 2 metode: in logica cablata ("hardwired"), care i se atribuie lui John von Neumann, si microprogramata ("microprogrammed"), care i se atribuie lui M.V. Wilkes.

Solutia cablata se poate realiza prin 4 metode:

metoda tabelei de stari(state-table method)

metoda on-hot;

metoda delay-element;

metoda sequence-counter.

1. Metoda tabelului de stari (state-table method)

Unitatea de control este considerata ca o masina secventiala cu un numar finit de stari. Plecand de la descrierea comportamentului intrare/iesire a schemei, fie prin mai modernul stil al unui limbaj de descriere hardware dar si prin clasicul stil al ordinogramei, se elaboreaza asa numitul tabel de stari,care prezinta cate un rand distinct pentru fiecare stare interna(starea memorata a masini corespunzatoare actiunii unui impuls de clock) si prezinta cate o coloana corespunzatoare fiecarui vector de intrare posibil.

Daca notam cu starile interne si cu i,j un vector posibil atunci avem urmatoarele 2 tabele: reprezinta starea interna urmatoare sireprezinta vectorul binar disponibil la asa numitele iesiri primare sau iesiri observabile. Aceasta descriere comportamentala este atribuita masinii mai generale Mealy, dar s-a dovedit in practica proiectarii metodelor de control ca vectorii de iesire sunt independenti de vectorii de intrare, ei depinzand in mod exclusiv de stari interne.

Prin urmare avem un vector de iesire corespunzator fiecarei stari , avem o descriere compacta care este atribuita asa numitei masini Moore. Pasii de sinteza corespunzatori acestei metode sunt:

Pasul 1: identificarea numarului de stari care sa acopere descrierea comportamentala a masinii secventiale("controller") constituita de unitatea de control. Admitand ca aceasta descriere comportamentala are la modul general P stari, se vor lua(cel mai mic intregcu valoarea logaritmului) elemente de memorare care, fara a pierde din generalitate, le consideram bistabile de tip D(Master-Slave).

Pasul 2: se confera celorbistabile cate un cod.

Pasul 3: se elaboreaza tabela de excitatie bazat pe care se scriu ecuatiile logice in forma minimizata corespunzatoare partii de logica combinationala a masinii secventiale.

Ordinograma corespunzatoare va fi prezentata in cele ce urmeaza:

Implementarea cu bistabile

2. Metoda one-hot (delay-element method)

Preambulul la introducerea acestei metode este constituita express de critica metodei prezentate. Daca metoda tabelului de stari prezinta avantajul unui numar minim de elemente de memorare(bistabile D) nu rezulta in mod clar, predictibil, complexitatea partii de logica combinationala(porti cu multe intrari), si uzual aceasta prezinta conexiuni complexe neordonate(de tip random) care fac depanarea si mentenanta unei astfel de realizari dificila. In consecinta in detrimentul unui metode optime din punctul de vedere al elementelor de memorare au aparut celelalte doua metode dintre care metoda on-hot se caracterizeaza prin faptul ca exista o relatie de cvasi 1 la 1 intre starile descrieri intrare-ie­sire prin ordinograma si elementele de memorare ale metodei sau altfel zis daca ordino­grama are P stari interne atunci vom avea P elemente de memorare, care fara a pierde din generalitate le vom considera bistabile de tip D. Caracteristica acestei metode este ca corespunzator fiecarei stari interne avem activ(adica pe "1") la un moment dat unul si numai unul dintre elementele de memorare(bistabil), care se admite in starea on-hot ("calda"), constituind astfel denumirea metodei. Aceasta caracteristica rezulta in mod direct din ordinograma astfel incat "sacrificiul" constituit dintr-un numar mai mare de elemente de memorare va fi compensat prin diminuarea in complexitate, printr-un numar mai redus de circuite necesar sintezei de logica combinationala.

Aceasta metoda se aplica la masini RISC simple si la asa numitele controler-e de aplicatii specifice. Pasii metodei on-hot sunt urmatorii:

Pasul 1:identificarea numarului de stari care sa acopere descrierea comportamentala si atribuirea cate unui bistastabil de tip D pentru fiecare stare interna.

Pasul 2:codificarea starilor interne atribuind un cod distinct fiecarui bistabil.

Pasul 3:elaborarea ecuatiilor logice care determina starea de "1" a bistabilelor de tip D prin urmarirea conditiilor rezultate din ordinograma. Aceasta procedura se efectueaza si pentru semnalele de control dupa care se trece la implementarea ecuatiilor rezultate.

Exemplu:

(Pas 3)

Implementare:

3. Metoda delay-element

La ambele metode avem o corespondenta de 1 la 1 intre elementele de memorare si starile puse in relief pe ordinograma. La metoda delay-element avem cate un element de intarziere notat cu DE pentru fiecare bloc operativ din ordinograma.

Observatii:

Metoda delay-element se elaboreaza plecand de la descrierea din ordinograma sau de la o descriere printr-un limbaj hardware.

De fiecare data cand in ordinograma avem de-a face cu o numire a mai multor ramuri in transpunerea in circuite acest lucru apare ca un circuit SAU.

Tratarea blocurilor de decizie se face astfel: daca in ordinograma avem un bloc de decizie de felul de mai jos atunci transpunerea lui in circuite este urmatoarea:

Acest DE(delay-element) nu este o linie de intarzierede tip pasiv ci el reprezinta uzual un bistabil de tip D care este prevazut cu un clock. 

Toate aceste elemente DE au un semnal comun l si aceasta afirmatie atrage dupa sine faptul ca atunci cand sunt multe elemente DE si clock-ul trebuie sa ajunga la mai multe elemente simultan apare fenomenul de clock skew("alunecare de clock"). Cu cat acest lant este mai laung cu atat mai mult aceste elemente pot fi afectate de fenomenul de clock skew. In aceasta metoda investitia consta in elementele de intarziere DE. Daca avem n stari atunci avem n elemente DE fata de

elemente de la cealalta metoda. Aici partea de logica combinationala prin aceste multiplexoare pe 1 bit devine simpla. Aceasta metoda prin claritatea transpunerii ordinogramei functionale este preferabila in vederea mentenantei(intretinerii) pentru ca se depaneaza mai usor.

4. Metoda sequence-counter

Aceasta metoda se preteaza atunci cand, comportamental, untitatea de control pe care o avem de proiectat parcurge in mod iterativ de mai multe ori o bucla functionala si uziteaza de o schema care poarta numele de numarator de secventa.

Fig:

Metoda sequnce-counter uziteaza de o astfel de schema a carui detaliu este prezentat mai sus. Cand trebuie sa aplicam metoda se pune problema determinarii valorii lui k, care reprezinta numarul de faze.

Se analizeaza care este partea din ordinograma care se repeta de cele mai multe ori, adica ciclul cel mai lung, si in functie de numarul de blocuri ale ciclului se alege k(k se va lua egal cu numarul de blocuri ale ciclului respectiv).

Dupa determinarea numarului k se determina numarul de bistabile RS, care se alege egal cu numarul de cicluri din ordinograma. O ordinograma este constituita din 3 parti: o parte de incarcare o informatiei, o parte repetitiva si o parte finala de de terminare si de predare a rezultatelor. In aceste conditii putem deja face o conturare a solutiei tehnice pentru problema noastra. In exemplul nostru k va fi 2 si in mod conjunctural vom avem:

Logica combinationala este simpla.

4 Algoritmul lui Booth

Robertson si-a bazat metoda pe o observatie legata de complementul de 2. Elementul deranjant la Robertson este ca daca avem operanzi pe n biti acest lucru implica activarea de n ori a sumatorului parallel.Cum performanta calculatorului este afectata de timpul de adunare, care incarca ca performanta solutia de inmultire, se pune problema gasirii unei metode de accelerare care sa depinda de configuratia binara particulara a inmultitorului si anume daca inmultitorul prezinta portiuni constituite din siruri de "0" sau de "1" atunci se poate beneficia de metoda lui Booth in vederea surmontarii penalitatii de performanta tipica procedurii lui Robetson pe care am facut-o.

a row of 1's(un sir de 1)

Fara a pierde din generalitate sa admitem ca X este un numar fractionar si vom spune ca aportul lui la X*Y este dat de urmatoarea relatie:

Se observa ca se realizeaza doar doua activari ale sumatorului paralel. Daca avem biti ai inmultitorului si daca acestia sunt 01, sugerand ca inmultitorul este parcurs de la stanga la dreapta, atunci in vederea obtinerii produsului se efectueaza o adunare a lui Y la produsul partial. Daca sunt 10 atunci se efectueaza o scadere a lui Y din produsul partial, iar in situatia in care cei doi biti sunt 00 sau 11, suntem pe parcursul baleerii unui sir de 1 sau 0 si nu se efectueaza nici o operatie. Algoritmul lui Booth este echivalent cu "recodificarea" inmultitorului intr-o forma speciala("a signed digit form"), in care se uziteaza de 3 semne si anume: 1 cand se face o adunare(cand cei doi biti adiacenti consultati sunt 01), 0 cand sunt 00 sau 11 si cand sunt 10.

De exemplu:

multiplier recording =

In reprezentarea in complement de 2 a numarului, pentru a putea lua in considerare si ultimul bit, se mai considera implicit un bit de 0(cel de dupa bara verticala).

Algoritmul lui Booth are urmatoarea forma in limbajul de descriere Heyes:

Booth mutiplier(in:INBUS;out:OUTBUS);

register A[7:0],Q[7:-1],M[7:0],COUNT[2:0];

bus INBUS[7:0],OUTBUS[7:0];

BEGIN : A:=0, COUNT:=0,

INPUT : M:=INBUS;

Q:=INBUS, Q[-1]:=0;

SCAN : if Q[0]Q[-1]=0 then A[7:0]:=A[7:0]+M[7:0],

goto TEST;

else if Q[0]Q[-1]=10 then A[7:0]:=A[7:0]-M[7:0];

TEST : if COUNT7=1 then goto OUTPUT,

RSHIFT: A[7]:=A[7], A[6:0].Q:=A.Q[7:-1],

COUNT:=COUNT+1, goto SCAN;

OUTPUT: OUTBUS:=A, Q[0]:=0;

OUTBUS:=Q;

END. end Booth multiplier

Schema se complica fata de Robertson pentru ca avem cand adunare cand scadere.

Algoritmul lui Booth modificat

Cand inmultitorul este format din alternante de 1 si 0 nu se beneficiaza de observatia lui Booth ci se inrautateste per globalperformanta inmultitorului, astfel s-a ajuns la algoritmul lui Booth modificat. La acest algoritm se ia in considerare situatia de "0 izolat" respectiv de "1 izolat" si in cazul unui "0 izolat" se efectueaza doar 0 scadere, iar in cazul lui "1 izolat" se efectueaza doar o adunare. Daca avem bitii:

. x_i x_i+1 x_i+2

0 1.. "an izolated 0"

(doar o scadere)

.0 1 0.. "an izolated 1"

(doar o adunare)

Se spune ca se apeleaza la o noua recodificare a inmultitorului, recodificare care poarta numele de "canonica" si care se efectueaza prin intermediul unui fanion("flag") F, care initial este pus pe 0 si va fi pus pe 1 doar daca la parcurgerea de la dreapta spre stanga al inmultitorului se intalneste un sir de 1(2 sau mai multi de 1) si va fi repus pe 0 doar daca se intalneste un sir de 0(2 sau mai multi de 0). Daca atribuim flag-ului F o valoare booleana, recodificarea Booth canonica se executa bazat pe urmatorul tabel:

(tabel)

De exemplu:

In limbajul de descriere Heyes algoritmul lui Booth modificat va arata astfel:

modified Booth algorithm(in:INBUS;out:OUTBUS);

register A[7:0],Q[8:0],M[7:0],COUNT[2:0],F,OVR;

bus INBUS[7:0],OUTBUS[7:0];

BEGIN : A:=0, COUNT:=0, F:=0,

INPUT : M:=INBUS;

Q[7:0]:=INBUS[7:0], Q[8]:=INBUS[7];

ZEROTEST: if Q=0 then goto OUTPUT,

if M0 then goto SCAN,

Q:=0, goto OUTPUT;

SCAN : if F=0 then

begin

if Q[0]Q[1]=01 then

A[7:0]:=A[7:0]+M[7:0], OVR:= ;

else

if Q[0]Q[1]=11 then

A[7:0]:=A[7:0]-M[7:0], OVR:= , F:=1;

end

else goto TEST;

if F=1 then

begin

if Q[0]Q[1]=00 then

A[7:0]:=A[7:0]+M[7:0], OVR:= , F:=0;

else

if Q[0]Q[1]=10 then

A[7:0]:=A[7:0]-M[7:0], OVR:= ;

end

TEST : if COUNT7=1 then goto OUTPUT,

RSHIFT : A[7]:=(A[7] and M[7] and)or(F and)or

(F and M[7] and OVR),

A[6:0].Q:=A.Q[8:1], COUNT:=COUNT+1, goto SCAN;

OUTPUT : OUTBUS:=A, Q[1]:=0;

OUTBUS:=Q;

END. end mBooth multiplier.

ORQ ORM