Algoritmus kabíny je násobiaci algoritmus, ktorý nám umožňuje vynásobiť dve binárne celé čísla so znamienkom v doplnku 2, resp. Používa sa tiež na urýchlenie výkonu procesu násobenia. Je tiež veľmi efektívny. Funguje na reťazcových bitoch 0 v multiplikátore, ktorý nevyžaduje žiadny ďalší bit, iba posunie reťazcové bity úplne vpravo a reťazec 1 v bitovej váhe multiplikátora 2^kna váhu 2^mktoré možno považovať za 2^{k+ 1}- 2^m .

Nasleduje obrazové znázornenie Boothovho algoritmu:

Vo vyššie uvedenom vývojovom diagrame na začiatku AC a Q_{n + 1} bity sú nastavené na 0 a SC je sekvenčné počítadlo, ktoré predstavuje celkovú množinu bitov n, ktorý sa rovná počtu bitov v multiplikátore. Existujú BR ktoré predstavujú multiplikandové bity, a QR predstavuje multiplikačné bity . Potom sme narazili na dva bity multiplikátora ako Q_na Q_{n + 1}, kde Qn predstavuje posledný bit QR a Q_{n + 1}predstavuje inkrementovaný bit Qn o 1. Predpokladajme, že dva bity multiplikátora sa rovnajú 10; to znamená, že od čiastkového súčinu v akumulátore AC musíme odpočítať násobiteľ a potom vykonať aritmetický posun (ashr). Ak sa dva z násobiteľov rovnajú 01, znamená to, že musíme vykonať pridanie násobiteľa k čiastočnému súčinu v akumulátore AC a potom vykonať operáciu aritmetického posunu ( Ashr ), počítajúc do toho Q_{n + 1} . Operácia aritmetického posunu sa používa v Boothovom algoritme na posunutie bitov AC a QR doprava o jeden a zostáva znamienkový bit v AC nezmenený. A sekvenčné počítadlo sa nepretržite znižuje, kým sa výpočtová slučka nezopakuje, rovná počtu bitov (n).

Práca na Boothovom algoritme

1. Nastavte binárne bity násobiteľa a násobiteľa na M a Q.
2. Najprv sme nastavili AC a Q_{n + 1}registruje hodnotu na 0.
3. SC predstavuje počet bitov multiplikátora (Q) a je to sekvenčné počítadlo, ktoré sa nepretržite znižuje, kým sa nerovná počtu bitov (n) alebo sa nedosiahne 0.
4. Qn predstavuje posledný bit Q a Q_n+1ukazuje zvýšený bit Qn o 1.
5. V každom cykle algoritmu kabíny, Q_na Q_{n + 1}bity budú kontrolované na nasledujúcich parametroch takto:
   1. Keď dva bity Q_na Q_{n + 1}sú 00 alebo 11, jednoducho vykonáme aritmetický posun doprava (ashr) na čiastkový súčin AC. A bity Qn a Q_{n + 1}sa zvýši o 1 bit.
   2. Ak kúsky Q_na Q_{n + 1}je zobrazené na 01, multiplikandové bity (M) sa pridajú do AC (Accumulator register). Potom vykonáme operáciu posunu doprava na AC a QR bity o 1.
   3. Ak kúsky Q_na Q_{n + 1}je zobrazené na 10, multiplikandové bity (M) sa odpočítajú od AC (registra akumulátora). Potom vykonáme operáciu posunu doprava na AC a QR bity o 1.
6. Operácia nepretržite funguje, kým sme v algoritme kabíny nedosiahli n - 1 bit.
7. Výsledky násobenia binárnych bitov budú uložené v AC a QR registroch.

V Boothovom algoritme sa používajú dve metódy:

stiahnite si videá z youtube pomocou vlc

1. RSC (Right Shift Circular)

Posúva bit úplne vpravo binárneho čísla a potom sa pridá na začiatok binárnych bitov.

2. RSA (pravá aritmetika)

Pridá dva binárne bity a potom posunie výsledok doprava o 1 bitovú pozíciu.

blokovanie reklám na youtube pre Android

Príklad : 0100 + 0110 => 1010, po pridaní binárneho čísla posuňte každý bit o 1 doprava a prvý bit výslednice umiestnite na začiatok nového bitu.

Príklad: Vynásobte dve čísla 7 a 3 pomocou Boothovho násobiaceho algoritmu.

rokov . Tu máme dve čísla, 7 a 3. Najprv musíme previesť 7 a 3 na binárne čísla ako 7 = (0111) a 3 = (0011). Teraz nastavte 7 (v binárnom 0111) ako násobiteľ (M) a 3 (v binárnom 0011) ako násobiteľ (Q). A SC (Sequence Count) predstavuje počet bitov a tu máme 4 bity, takže nastavte SC = 4. Tiež ukazuje počet iteračných cyklov algoritmov kabíny a potom sa cykly spustia SC = SC - 1 krát.

Numerický príklad Boothovho multiplikačného algoritmu je 7 x 3 = 21 a binárne vyjadrenie 21 je 10101. Tu dostaneme výsledok v binárnom 00010101. Teraz ho prevedieme na desiatkové číslo, ako (000010101)₁₀= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

príklad binárneho vyhľadávacieho stromu

Príklad: Vynásobte dve čísla 23 a -9 pomocou Boothovho násobiaceho algoritmu.

Tu M = 23 = (010111) a Q = -9 = (110111)

Q_{n + 1} = 1, znamená to, že výstup je záporný.

Preto 23 * -9 = dvojkový doplnok 111100110001 => (00001100111)