Booth-algoritmen er en multiplikationsalgoritme, der giver os mulighed for at multiplicere de to fortegnede binære heltal i henholdsvis 2's komplement. Det bruges også til at fremskynde udførelsen af ​​multiplikationsprocessen. Det er også meget effektivt. Det virker på strengbits 0'erne i multiplikatoren, der ikke kræver yderligere bit, forskyd kun strengbittene længst til højre og en streng på 1'er i en multiplikatorbitvægt 2^ktil vægt 2^mder kan betragtes som 2^k+1- 2^m .

Følgende er den billedlige repræsentation af Booth's Algorithm:

I ovenstående flowchart, indledningsvis, AC og Q_{n + 1} bit er sat til 0, og SC er en sekvenstæller, der repræsenterer det samlede antal bitsæt n, som er lig med antallet af bits i multiplikatoren. Der er BR der repræsenterer multiplikante bits, og QR repræsenterer multiplikator bits . Derefter stødte vi på to bits af multiplikatoren som Q_nog Q_{n + 1}, hvor Qn repræsenterer den sidste bit af QR, og Q_{n + 1}repræsenterer den øgede bit af Qn med 1. Antag, at to bits af multiplikatoren er lig med 10; det betyder, at vi skal trække multiplikatoren fra partialproduktet i akkumulatoren AC og derefter udføre den aritmetiske skiftoperation (ashr). Hvis de to af multiplikatorerne er lig med 01, betyder det, at vi skal udføre additionen af ​​multiplikaanden til delproduktet i akkumulator AC og derefter udføre den aritmetiske skiftoperation ( Ashr ), herunder Q_{n + 1} . Den aritmetiske skiftoperation bruges i Booths algoritme til at flytte AC- og QR-bits til højre med én og forbliver fortegnsbitten i AC uændret. Og sekvenstælleren dekrementeres kontinuerligt, indtil beregningsløkken gentages, svarende til antallet af bit (n).

Arbejder på Booth Algorithm

1. Indstil Multiplikand og Multiplikator binære bits som henholdsvis M og Q.
2. Til at begynde med indstillede vi AC og Q_{n + 1}registrerer værdi til 0.
3. SC repræsenterer antallet af multiplikatorbit (Q), og det er en sekvenstæller, der kontinuerligt dekrementeres, indtil det er lig med antallet af bit (n) eller nås til 0.
4. En Qn repræsenterer den sidste bit af Q, og Q_n+1viser den øgede bit af Qn med 1.
5. I hver cyklus af kabinealgoritmen, Q_nog Q_{n + 1}bits vil blive kontrolleret på følgende parametre som følger:
   1. Når to bit Q_nog Q_{n + 1}er 00 eller 11, udfører vi blot den aritmetiske skift til højre (ashr) til delproduktet AC. Og biterne af Qn og Q_{n + 1}øges med 1 bit.
   2. Hvis bits af Q_nog Q_{n + 1}er viser til 01, vil multiplikand-bittene (M) blive tilføjet til AC (akkumulatorregisteret). Derefter udfører vi den rigtige skiftoperation til AC- og QR-bittene med 1.
   3. Hvis bits af Q_nog Q_{n + 1}er viser til 10, vil multiplikandbittene (M) blive trukket fra AC (akkumulatorregisteret). Derefter udfører vi den rigtige skiftoperation til AC- og QR-bittene med 1.
6. Operationen fungerer kontinuerligt, indtil vi nåede n - 1 bit i booth-algoritmen.
7. Resultaterne af de binære multiplikationsbits vil blive gemt i AC- og QR-registrene.

Der er to metoder, der bruges i Booths algoritme:

markdown billeder

1. RSC (Right Shift Circular)

Det forskyder bit længst til højre i det binære tal, og derefter tilføjes det til begyndelsen af ​​de binære bit.

2. RSA (Right Shift Arithmetic)

Den tilføjer de to binære bit og flytter derefter resultatet til højre med 1-bit position.

java program loop

Eksempel : 0100 + 0110 => 1010, efter at have tilføjet det binære tal forskyd hver bit med 1 til højre og sæt den første bit af resultant til begyndelsen af ​​den nye bit.

Eksempel: Gang de to tal 7 og 3 ved at bruge Booths multiplikationsalgoritme.

Flere år . Her har vi to tal, 7 og 3. Først og fremmest skal vi konvertere 7 og 3 til binære tal som 7 = (0111) og 3 = (0011). Indstil nu 7 (i binær 0111) som multiplikant (M) og 3 (i binær 0011) som en multiplikator (Q). Og SC (Sequence Count) repræsenterer antallet af bits, og her har vi 4 bit, så sæt SC = 4. Den viser også antallet af iterationscyklusser af standens algoritmer og derefter kører cykler SC = SC - 1 gang.

Det numeriske eksempel på Booths multiplikationsalgoritme er 7 x 3 = 21, og den binære repræsentation af 21 er 10101. Her får vi resultanten i binær 00010101. Nu konverterer vi den til decimal, som (000010101)₁₀= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

jordnødde vs jordnødde

Eksempel: Gang de to tal 23 og -9 ved at bruge Booths multiplikationsalgoritme.

Her er M = 23 = (010111) og Q = -9 = (110111)

Q_{n + 1} = 1, betyder det, at outputtet er negativt.

Derfor er 23 * -9 = 2'er komplement af 111100110001 => (00001100111)