Boothov algoritem je algoritem množenja, ki nam omogoča množenje dveh predznačenih binarnih celih števil v komplementu 2. Uporablja se tudi za pospešitev delovanja procesa množenja. Je tudi zelo učinkovit. Deluje na nizovih bitov 0 v množitelju, ki ne zahteva nobenega dodatnega bita, le premakne skrajno desne bite niza in niz 1 v bitni teži 2 množitelja.^kdo teže 2^mki se lahko šteje za 2^{k+ 1}- 2^m .

Sledi slikovna predstavitev Boothovega algoritma:

V zgornjem diagramu poteka na začetku AC in Q_{n + 1} biti nastavljeni na 0, in SC je števec zaporedja, ki predstavlja skupni niz bitov n, ki je enako številu bitov v množitelju. obstajajo BR ki predstavljajo množilni biti, in QR predstavlja množilni biti . Po tem smo naleteli na dva bita množitelja kot Q_nin Q_{n + 1}, kjer Qn predstavlja zadnji bit QR, in Q_{n + 1}predstavlja bit Qn, povečan za 1. Recimo, da sta dva bita množitelja enaka 10; pomeni, da moramo od delnega produkta v akumulatorju AC odšteti množitelj in nato izvesti operacijo aritmetičnega premika (ashr). Če sta oba množitelja enaka 01, to pomeni, da moramo izvesti seštevanje množitelja k delnemu produktu v akumulatorju AC in nato izvesti operacijo aritmetičnega premika ( Ashr ), vključno z Q_{n + 1} . Operacija aritmetičnega premika se uporablja v Boothovem algoritmu za premik bitov AC in QR v desno za enega, bit predznaka v AC pa ostane nespremenjen. In števec zaporedja se nenehno zmanjšuje, dokler se računska zanka ne ponovi, kar je enako številu bitov (n).

Delo na algoritmu Booth

1. Nastavite binarne bite množitelja in množitelja na M oziroma Q.
2. Na začetku smo nastavili AC in Q_{n + 1}registrira vrednost na 0.
3. SC predstavlja število bitov množitelja (Q) in je zaporedni števec, ki se nenehno zmanjšuje, dokler ni enak številu bitov (n) ali doseže 0.
4. Qn predstavlja zadnji bit Q in Q_n+1prikazuje povečan bit Qn za 1.
5. V vsakem ciklu algoritma kabine Q_nin Q_{n + 1}biti bodo preverjeni pri naslednjih parametrih, kot sledi:
   1. Ko dva bita Q_nin Q_{n + 1}sta 00 ali 11, preprosto izvedemo operacijo aritmetičnega premika v desno (ashr) na delni produkt AC. In bitov Qn in Q_{n + 1}se poveča za 1 bit.
   2. Če so deli Q_nin Q_{n + 1}je prikazano na 01, bodo multiplikandi (M) dodani v AC (akumulatorski register). Po tem izvedemo operacijo desnega premika na bite AC in QR za 1.
   3. Če so deli Q_nin Q_{n + 1}je prikazano na 10, bodo multiplikandi (M) odšteti od AC (akumulatorskega registra). Po tem izvedemo operacijo desnega premika na bite AC in QR za 1.
6. Operacija deluje neprekinjeno, dokler ne dosežemo n - 1 bit v algoritmu kabine.
7. Rezultati binarnih bitov množenja bodo shranjeni v registrih AC in QR.

V Boothovem algoritmu se uporabljata dve metodi:

aritmetično logična enota

1. RSC (okrožni desni premik)

Premakne skrajni desni bit binarnega števila, nato pa se doda na začetek binarnih bitov.

2. RSA (aritmetika desnega premika)

Sešteje dva binarna bita in nato premakne rezultat v desno za 1-bitni položaj.

blokiraj youtube oglase android

Primer : 0100 + 0110 => 1010, po dodajanju binarnega števila premaknite vsak bit za 1 v desno in postavite prvi bit rezultante na začetek novega bita.

Primer: pomnožite dve števili 7 in 3 z uporabo Boothovega algoritma množenja.

leta . Tukaj imamo dve števili, 7 in 3. Najprej moramo 7 in 3 pretvoriti v dvojiški števili, kot sta 7 = (0111) in 3 = (0011). Zdaj nastavite 7 (v binarnem 0111) kot množitelj (M) in 3 (v binarnem 0011) kot množitelja (Q). In SC (število zaporedij) predstavlja število bitov in tukaj imamo 4 bite, zato nastavite SC = 4. Prav tako prikazuje število ponovitvenih ciklov algoritmov kabine in nato se cikli izvajajo SC = SC - 1-krat.

Numerični primer Boothovega algoritma množenja je 7 x 3 = 21 in binarna predstavitev 21 je 10101. Tukaj dobimo rezultanto v dvojiški obliki 00010101. Zdaj jo pretvorimo v decimalno, kot (000010101)₁₀= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

kaj je desktop ini

Primer: pomnožite dve števili 23 in -9 z uporabo Boothovega algoritma množenja.

Tukaj je M = 23 = (010111) in Q = -9 = (110111)

Q_{n + 1} = 1, pomeni, da je rezultat negativen.

Zato je 23 * -9 = komplement 2 od 111100110001 => (00001100111)