Booth-algoritmi on kertoalgoritmi, jonka avulla voimme kertoa kaksi etumerkillistä binaarilukua 2:n komplementissa, vastaavasti. Sitä käytetään myös nopeuttamaan kertolaskuprosessia. Se on myös erittäin tehokas. Se toimii kertoimen merkkijonobitteillä 0, joka ei vaadi ylimääräistä bittiä, vain siirtää oikeanpuoleisimpia merkkijonobittejä ja 1:n merkkijonoa kertoimen bittipainossa 2 ^k painoon 2 ^m jota voidaan pitää 2 ^k+1 - 2 ^m .

Seuraava on kuvallinen esitys Boothin algoritmista:

Yllä olevassa vuokaaviossa aluksi AC ja K _{n + 1} bitit on asetettu arvoon 0, ja SC on sekvenssilaskuri, joka edustaa asetettujen bittien kokonaismäärää n, joka on yhtä suuri kuin kertoimen bittien lukumäärä. On BR jotka edustavat kertobitit, ja QR edustaa kertoimen bitit . Sen jälkeen kohtasimme kaksi kertojan bittiä Q:na _n ja Q _{n + 1} , jossa Qn edustaa QR:n viimeistä bittiä ja Q _{n + 1} edustaa Qn:n lisättyä bittiä yhdellä. Oletetaan, että kertoimen kaksi bittiä on yhtä suuri kuin 10; se tarkoittaa, että meidän on vähennettävä kerroin akun AC osatuloksesta ja suoritettava sitten aritmeettinen siirtooperaatio (ashr). Jos kaksi kertojaa ovat yhtä suuret kuin 01, se tarkoittaa, että meidän on suoritettava kertolaskujen summa akun AC osittaistuloon ja suoritettava sitten aritmeettinen siirtotoiminto ( Ashr ), mukaan lukien K _{n + 1} . Aritmeettista siirtooperaatiota käytetään Boothin algoritmissa AC- ja QR-bittien siirtämiseksi oikealle yhdellä ja pysyy AC:n etumerkkibittinä muuttumattomana. Ja sekvenssilaskuria pienennetään jatkuvasti, kunnes laskentasilmukka toistetaan, yhtä suuri kuin bittien lukumäärä (n).

Työskentely Booth-algoritmin parissa

1. Aseta Multiplicand- ja Multiplier-binääribitit arvoiksi M ja Q.
2. Aluksi asetimme AC:n ja Q:n _{n + 1} rekisteröi arvon 0:ksi.
3. SC edustaa kertojabittien määrää (Q), ja se on sekvenssilaskuri, jota pienennetään jatkuvasti, kunnes se on yhtä suuri kuin bittien lukumäärä (n) tai saavutetaan nollaan.
4. Qn edustaa Q:n ja Q:n viimeistä bittiä _n+1 näyttää Qn:n lisätyn bitin yhdellä.
5. Jokaisessa kopin algoritmin syklissä Q _n ja Q _{n + 1} bitit tarkistetaan seuraavilla parametreilla seuraavasti:
   1. Kun kaksi bittiä Q _n ja Q _{n + 1} ovat 00 tai 11, suoritamme yksinkertaisesti aritmeettisen siirto oikealle -operaation (ashr) osittaistuloon AC. Ja Qn:n ja Q:n bitit _{n + 1} kasvaa 1 bitillä.
   2. Jos Q:n bitit _n ja Q _{n + 1} on 01, kerroinbitit (M) lisätään AC-rekisteriin (akkurekisteriin). Tämän jälkeen suoritamme oikean siirtotoiminnon AC- ja QR-biteille 1:llä.
   3. Jos Q:n bitit _n ja Q _{n + 1} Jos on 10, kertobitit (M) vähennetään AC:sta (akkurekisteristä). Tämän jälkeen suoritamme oikean siirtotoiminnon AC- ja QR-biteille 1:llä.
6. Toiminto toimii jatkuvasti, kunnes saavutimme n - 1 bitin koppialgoritmissa.
7. Kertomisen binääribittien tulokset tallennetaan AC- ja QR-rekistereihin.

Boothin algoritmissa käytetään kahta menetelmää:

1. RSC (Right Shift Circular)

Se siirtää binääriluvun oikeanpuoleisinta bittiä, ja sitten se lisätään binääribittien alkuun.

2. RSA (Right Shift Aritmetic)

Se lisää kaksi binaaribittiä ja siirtää sitten tulosta oikealle 1 bitin paikan verran.

Esimerkki : 0100 + 0110 => 1010, binääriluvun lisäämisen jälkeen siirrä kutakin bittiä 1:llä oikealle ja laita resultantin ensimmäinen bitti uuden bitin alkuun.

Esimerkki: Kerro kaksi lukua 7 ja 3 käyttämällä Boothin kertolaskualgoritmia.

Vuosia . Tässä on kaksi numeroa, 7 ja 3. Ensinnäkin meidän on muutettava 7 ja 3 binääriluvuiksi, kuten 7 = (0111) ja 3 = (0011). Aseta nyt 7 (binääriarvossa 0111) kertojaksi (M) ja 3 (binääriarvossa 0011) kertoimeksi (Q). Ja SC (Sequence Count) edustaa bittien määrää, ja tässä meillä on 4 bittiä, joten aseta SC = 4. Lisäksi se näyttää kopin algoritmien iteraatiojaksojen lukumäärän ja sitten syklit ajavat SC = SC - 1 kerran.

Boothin kertolaskualgoritmin numeerinen esimerkki on 7 x 3 = 21 ja luvun 21 binääriesitys on 10101. Tässä saadaan resultantti binäärinä 00010101. Muunnamme sen nyt desimaaliluvuksi, kuten (000010101) ₁₀ = 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

Esimerkki: Kerro kaksi lukua 23 ja -9 käyttämällä Boothin kertolaskualgoritmia.

Tässä M = 23 = (010111) ja Q = -9 = (110111)

K _{n + 1} = 1, se tarkoittaa, että tulos on negatiivinen.

Näin ollen 23 * -9 = 2:n komplementti luvusta 111100110001 => (00001100111)