Booth-algoritmen er en multiplikasjonsalgoritme som lar oss multiplisere de to signerte binære heltallene i henholdsvis 2-er. Det brukes også til å fremskynde ytelsen til multiplikasjonsprosessen. Det er veldig effektivt også. Den fungerer på strengbitene 0-er i multiplikatoren som ikke krever noen ekstra bit, bare skift strengbitene lengst til høyre og en streng på 1-er i multiplikatorbitvekt 2^ktil vekt 2^msom kan betraktes som 2^{k+ 1}- 2^m .

Følgende er den billedlige representasjonen av Booths algoritme:

I flytskjemaet ovenfor, innledningsvis, AC og Q_{n + 1} bits er satt til 0, og SC er en sekvensteller som representerer den totale biten som er satt n, som er lik antall biter i multiplikatoren. Det er BR som representerer multiplikante biter, og QR representerer multiplikatorbiter . Etter det møtte vi to biter av multiplikatoren som Q_nog Q_{n + 1}, der Qn representerer den siste biten av QR, og Q_{n + 1}representerer den inkrementerte biten av Qn med 1. Anta at to biter av multiplikatoren er lik 10; det betyr at vi må trekke multiplikatoren fra delproduktet i akkumulatoren AC og deretter utføre den aritmetiske skiftoperasjonen (ashr). Hvis de to av multiplikatorene er lik 01, betyr det at vi må utføre addisjonen av multiplikaanden til delproduktet i akkumulator AC og deretter utføre den aritmetiske skiftoperasjonen ( Ashr ), gjelder også Q_{n + 1} . Den aritmetiske skiftoperasjonen brukes i Booths algoritme for å skifte AC- og QR-biter til høyre med én og forblir fortegnsbiten i AC uendret. Og sekvenstelleren dekrementeres kontinuerlig til beregningssløyfen gjentas, lik antall biter (n).

Jobber med Booth-algoritmen

1. Sett de binære bitene Multiplikand og Multiplikator som henholdsvis M og Q.
2. Til å begynne med satte vi AC og Q_{n + 1}registrerer verdien til 0.
3. SC representerer antall multiplikatorbiter (Q), og det er en sekvensteller som kontinuerlig dekrementeres til lik antall biter (n) eller nådd til 0.
4. En Qn representerer den siste biten av Q, og Q_n+1viser den økte biten av Qn med 1.
5. På hver syklus av messealgoritmen, Q_nog Q_{n + 1}biter vil bli sjekket på følgende parametere som følger:
   1. Når to biter Q_nog Q_{n + 1}er 00 eller 11, utfører vi ganske enkelt den aritmetiske forskyvningsoperasjonen til høyre (ashr) til delproduktet AC. Og bitene av Qn og Q_{n + 1}økes med 1 bit.
   2. Hvis bitene av Q_nog Q_{n + 1}er viser til 01, vil multiplikandbitene (M) bli lagt til AC (akkumulatorregisteret). Etter det utfører vi riktig skiftoperasjon til AC- og QR-bitene med 1.
   3. Hvis bitene av Q_nog Q_{n + 1}er viser til 10, vil multiplikandbitene (M) trekkes fra AC (akkumulatorregisteret). Etter det utfører vi riktig skiftoperasjon til AC- og QR-bitene med 1.
6. Operasjonen fungerer kontinuerlig til vi nådde n - 1 bit i booth-algoritmen.
7. Resultater av multiplikasjonsbinærbitene vil bli lagret i AC- og QR-registrene.

Det er to metoder som brukes i Booths algoritme:

markdown-bilder

1. RSC (Right Shift Circular)

Den forskyver biten lengst til høyre av det binære tallet, og deretter legges det til begynnelsen av de binære bitene.

2. RSA (Right Shift Arithmetic)

Den legger til de to binære bitene og forskyver deretter resultatet til høyre med 1-bits posisjon.

b+ tre

Eksempel : 0100 + 0110 => 1010, etter å ha lagt til det binære tallet, skift hver bit med 1 til høyre og sett den første biten av resultanten til begynnelsen av den nye biten.

Eksempel: Multipliser de to tallene 7 og 3 ved å bruke Booths multiplikasjonsalgoritme.

år . Her har vi to tall, 7 og 3. Først av alt må vi konvertere 7 og 3 til binære tall som 7 = (0111) og 3 = (0011). Sett nå 7 (i binær 0111) som multiplikant (M) og 3 (i binær 0011) som en multiplikator (Q). Og SC (Sequence Count) representerer antall biter, og her har vi 4 biter, så sett SC = 4. Den viser også antall iterasjonssykluser av messens algoritmer og deretter kjører sykluser SC = SC - 1 gang.

Det numeriske eksemplet på Booths multiplikasjonsalgoritme er 7 x 3 = 21 og den binære representasjonen av 21 er 10101. Her får vi resultanten i binær 00010101. Nå konverterer vi den til desimal, som (000010101)₁₀= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

jordnøtt vs peanøtt

Eksempel: Multipliser de to tallene 23 og -9 ved å bruke Booths multiplikasjonsalgoritme.

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

Q_{n + 1} = 1, betyr det at utgangen er negativ.

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