Booth algoritmas yra daugybos algoritmas, leidžiantis padauginti du pasirašytus dvejetainius sveikuosius skaičius 2 komplemente. Jis taip pat naudojamas pagreitinti dauginimo procesą. Tai taip pat labai efektyvu. Jis veikia su daugiklio eilutės bitais 0, kuriems nereikia papildomų bitų, tik perkelia labiausiai dešinėje esančius eilutės bitus ir 1 eilutę daugiklio bitų svoryje 2^kiki svorio 2^mkurį galima laikyti 2^k+1– 2^m .

Toliau pateikiamas vaizdinis Booth algoritmo vaizdas:

Aukščiau pateiktoje schemoje iš pradžių AC ir K_{n + 1} bitai yra nustatyti į 0, o SC yra sekos skaitiklis, rodantis bendrą bitų skaičių n, kuris lygus bitų skaičiui daugiklyje. Yra BR kurie atstovauja daugybos bitai, o QR reiškia daugiklio bitai . Po to mes susidūrėme su dviem daugiklio bitais kaip Q_nir Q_{n + 1}, kur Qn reiškia paskutinį QR bitą, o Q_{n + 1}reiškia Qn padidintą bitą 1. Tarkime, kad du daugiklio bitai yra lygūs 10; tai reiškia, kad turime atimti daugiklį iš dalinės sandaugos akumuliatoriuje AC ir tada atlikti aritmetinę poslinkio operaciją (ashr). Jei du daugikliai lygūs 01, tai reiškia, kad turime atlikti daugiklio pridėjimą prie dalinės sandaugos akumuliatoriuje AC ir tada atlikti aritmetinę poslinkio operaciją ( Ašras ), įskaitant K_{n + 1} . Aritmetinio poslinkio operacija naudojama Bootho algoritme, kad kintamosios srovės ir QR bitai būtų perkeliami į dešinę, o kintamos srovės ženklo bitas išlieka nepakitęs. Ir sekos skaitiklis nuolat mažinamas, kol kartojasi skaičiavimo ciklas, lygus bitų skaičiui (n).

Darbas su Booth algoritmu

1. Dvejetainius bitus Multiplicand ir Multiplier nustatykite kaip M ir Q.
2. Iš pradžių mes nustatėme AC ir Q_{n + 1}registruoja reikšmę į 0.
3. SC reiškia daugiklio bitų skaičių (Q), ir tai yra sekos skaitiklis, kuris nuolat mažinamas, kol bus lygus bitų skaičiui (n) arba pasiekiamas iki 0.
4. Qn reiškia paskutinį Q bitą ir Q_n+1rodo Qn padidintą bitą 1.
5. Kiekviename kabinos algoritmo cikle Q_nir Q_{n + 1}bitai bus tikrinami pagal šiuos parametrus:
   1. Kai du bitai Q_nir Q_{n + 1}yra 00 arba 11, paprasčiausiai atliekame aritmetinę perkėlimo į dešinę operaciją (ashr) į dalinį sandaugą AC. Ir Qn ir Q bitai_{n + 1}padidinamas 1 bitu.
   2. Jei Q bitai_nir Q_{n + 1}rodomas iki 01, daugybos bitai (M) bus įtraukti į AC (akumuliatoriaus registrą). Po to mes atliekame teisingą perjungimo operaciją į AC ir QR bitus 1.
   3. Jei Q bitai_nir Q_{n + 1}rodomas iki 10, daugybos bitai (M) bus atimti iš AC (akumuliatoriaus registro). Po to atliekame teisingą perjungimo operaciją į AC ir QR bitus 1.
6. Operacija veikia nuolat, kol pasiekiame n - 1 bitą kabinos algoritme.
7. Daugybos dvejetainių bitų rezultatai bus saugomi AC ir QR registruose.

Booth algoritme naudojami du metodai:

pirmasis nešiojamas kompiuteris

1. RSC (dešiniojo poslinkio apskritimas)

Jis perkelia labiausiai į dešinę esantį dvejetainio skaičiaus bitą, tada jis pridedamas prie dvejetainių bitų pradžios.

2. RSA (dešiniojo poslinkio aritmetika)

Jis prideda du dvejetainius bitus ir perkelia rezultatą į dešinę 1 bito padėtimi.

išvalyti talpyklą npm

Pavyzdys : 0100 + 0110 => 1010, pridėję dvejetainį skaičių, kiekvieną bitą perkelkite 1 į dešinę ir pirmąjį rezultato bitą įdėkite į naujo bito pradžią.

Pavyzdys: padauginkite du skaičius 7 ir 3 naudodami Booth daugybos algoritmą.

Metai . Čia mes turime du skaičius, 7 ir 3. Pirmiausia turime paversti 7 ir 3 dvejetainiais skaičiais, tokiais kaip 7 = (0111) ir 3 = (0011). Dabar nustatykite 7 (dvejetainėje 0111) kaip daugiklį (M) ir 3 (dvejetainėje 0011) kaip daugiklį (Q). Ir SC (Sequence Count) reiškia bitų skaičių, o čia mes turime 4 bitus, todėl nustatykite SC = 4. Taip pat jis rodo kabinos algoritmų iteracijos ciklų skaičių ir tada ciklai paleidžiami SC = SC - 1 kartą.

Skaitinis Booth daugybos algoritmo pavyzdys yra 7 x 3 = 21, o dvejetainis 21 atvaizdavimas yra 10101. Čia gauname dvejetainį rezultatą 00010101. Dabar konvertuojame jį į dešimtainį skaičių, kaip (000010101)₁₀= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

dvejetainis medis vs bst

Pavyzdys: naudodami Booth daugybos algoritmą, padauginkite du skaičius 23 ir -9.

Čia M = 23 = (010111) ir Q = -9 = (110111)

K_{n + 1} = 1, tai reiškia, kad išvestis yra neigiama.

Taigi, 23 * -9 = 2 papildinys 111100110001 => (00001100111)