A fülkealgoritmus egy szorzóalgoritmus, amely lehetővé teszi, hogy a két előjeles bináris egész számot a 2-es komplementerben megszorozzuk. A szorzási folyamat teljesítményének felgyorsítására is szolgál. Nagyon hatékony is. A szorzóban a 0-s karakterlánc-biteken működik, amely nem igényel további bitet, csak a jobb szélső karakterláncbiteket és egy 1-es karakterláncot tolja el a szorzóbit súlyában 2^ksúlyra 2^maminek tekinthető 2^k+1- 2^m .

Az alábbiakban a Booth-algoritmus képi ábrázolása látható:

A fenti folyamatábrán először AC és K_{n + 1} bitek 0-ra vannak állítva, és a SC egy sorozatszámláló, amely az összes bitkészletet reprezentálja n, amely megegyezik a szorzóban lévő bitek számával. Vannak BR amelyek képviselik a szorzó bitek, a QR pedig a szorzó bitek . Ezt követően a szorzó két bitjével találkoztunk Q-ként_nés Q_{n + 1}, ahol Qn a QR utolsó bitje, a Q pedig_{n + 1}Qn 1-gyel megnövelt bitjét jelenti. Tegyük fel, hogy a szorzó két bitje egyenlő 10-zel; ez azt jelenti, hogy az AC akkumulátorban lévő részszorzatból ki kell vonnunk a szorzót, majd végre kell hajtanunk az aritmetikai eltolási műveletet (ashr). Ha a szorzók két értéke 01, az azt jelenti, hogy el kell végeznünk a szorzószám hozzáadását az AC akkumulátor részleges szorzatához, majd végre kell hajtanunk az aritmetikai eltolási műveletet ( Ashr ), beleértve K_{n + 1} . Az aritmetikai eltolási műveletet Booth algoritmusa használja az AC és QR bitek eggyel jobbra tolására, és az előjelbit változatlan marad AC-ban. És a sorozatszámláló folyamatosan csökken, amíg a számítási ciklus meg nem ismétlődik, egyenlő a bitek számával (n).

Munka a Booth algoritmuson

1. Állítsa be a Szorzó és Szorzó bináris biteket M-re, illetve Q-ra.
2. Kezdetben beállítottuk az AC-t és a Q-t_{n + 1}0-ra regisztrálja az értéket.
3. Az SC a szorzóbitek számát (Q) jelenti, és ez egy sorozatszámláló, amely folyamatosan csökken, amíg el nem éri a bitek számát (n), vagy el nem éri a 0-t.
4. A Qn a Q és a Q utolsó bitje_n+1Qn 1-gyel megnövelt bitjét mutatja.
5. A fülke algoritmus minden ciklusában Q_nés Q_{n + 1}A bitek ellenőrzése a következő paraméterek alapján történik:
   1. Amikor két bit Q_nés Q_{n + 1}00 vagy 11, egyszerűen végrehajtjuk az aritmetikai eltolás jobbra műveletét (ashr) az AC részszorzathoz. És a Qn és Q bitjei_{n + 1}1 bittel növekszik.
   2. Ha a Q bitjei_nés Q_{n + 1}Ha értéke 01, akkor a szorzóbitek (M) hozzáadódnak az AC-hoz (Akkumulátorregiszter). Ezt követően 1-gyel végrehajtjuk a jobb eltolási műveletet az AC és a QR bitekre.
   3. Ha a Q bitjei_nés Q_{n + 1}Ha értéke 10, akkor a szorzóbitek (M) kivonásra kerülnek az AC-ból (Akkumulátorregiszter). Ezt követően 1-gyel végrehajtjuk a jobb eltolási műveletet az AC és a QR bitekre.
6. A művelet folyamatosan működik, amíg el nem érjük az n - 1 bitet a fülke algoritmusban.
7. A szorzási bináris bitek eredményeit az AC és a QR regiszterek tárolják.

A Booth-algoritmusban két módszert használnak:

mennyi a 25 a 100-ból

1. RSC (jobb váltókör)

Eltolja a bináris szám jobb szélső bitjét, majd hozzáadja a bináris bitek elejéhez.

2. RSA (jobb eltolásos aritmetika)

Összeadja a két bináris bitet, majd az eredményt 1 bites pozícióval jobbra tolja.

leértékelés áthúzása

Példa : 0100 + 0110 => 1010, a bináris szám hozzáadása után tolja el az egyes biteket 1-gyel jobbra, és helyezze az eredő első bitjét az új bit elejére.

Példa: Szorozzuk meg a két számot, 7-et és 3-at a Booth-féle szorzóalgoritmus segítségével.

Évek . Itt két szám van, a 7 és a 3. Először is át kell alakítanunk a 7-et és a 3-at bináris számokká, például 7 = (0111) és 3 = (0011). Most állítsa be a 7-et (bináris 0111-ben) szorzóként (M) és 3-at (binárisan 0011) szorzóként (Q). Az SC (Sequence Count) pedig a bitek számát jelenti, és itt 4 bitünk van, tehát állítsa be az SC = 4 értéket. Ezenkívül megmutatja a fülke algoritmusainak iterációs ciklusainak számát, majd a ciklusok SC = SC - 1 alkalommal futnak le.

A Booth-féle szorzási algoritmus numerikus példája: 7 x 3 = 21, a 21 bináris reprezentációja pedig 10101. Itt a 00010101 bináris eredményt kapjuk. Most decimálisra konvertáljuk, mint (000010101)₁₀= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

java virtuális gép

Példa: Szorozzuk meg a két 23-as és -9-es számot a Booth-féle szorzóalgoritmus segítségével.

Itt M = 23 = (010111) és Q = -9 = (110111)

K_{n + 1} = 1, ez azt jelenti, hogy a kimenet negatív.

Ezért 23 * -9 = 2 komplementere 111100110001 => (00001100111)