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 2kna váhu 2mktoré možno považovať za 2k+ 1- 2m .
Nasleduje obrazové znázornenie Boothovho algoritmu:
Vo vyššie uvedenom vývojovom diagrame na začiatku AC a Qn + 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 Qna Qn + 1, kde Qn predstavuje posledný bit QR a Qn + 1predstavuje 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 Qn + 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
- Nastavte binárne bity násobiteľa a násobiteľa na M a Q.
- Najprv sme nastavili AC a Qn + 1registruje hodnotu na 0.
- 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.
- Qn predstavuje posledný bit Q a Qn+1ukazuje zvýšený bit Qn o 1.
- V každom cykle algoritmu kabíny, Qna Qn + 1bity budú kontrolované na nasledujúcich parametroch takto:
- Keď dva bity Qna Qn + 1sú 00 alebo 11, jednoducho vykonáme aritmetický posun doprava (ashr) na čiastkový súčin AC. A bity Qn a Qn + 1sa zvýši o 1 bit.
- Ak kúsky Qna Qn + 1je 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.
- Ak kúsky Qna Qn + 1je 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.
- Operácia nepretržite funguje, kým sme v algoritme kabíny nedosiahli n - 1 bit.
- 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.
| Qn | Qn + 1 | M = (0111) M' + 1 = (1001) & operácia | AC | Q | Qn + 1 | SC |
|---|---|---|---|---|---|---|
| 1 | 0 | Počiatočné | 0000 | 0011 | 0 | 4 |
| Odčítať (M' + 1) | 1001 | |||||
| 1001 | ||||||
| Vykonávať aritmetické operácie pravého posunu (ashr) | 1100 | 1001 | 1 | 3 | ||
| 1 | 1 | Vykonávať aritmetické operácie pravého posunu (ashr) | 1110 | 0100 | 1 | 2 |
| 0 | 1 | Pridanie (A + M) | 0111 | |||
| 0101 | 0100 | |||||
| Vykonajte aritmetickú operáciu s posunom doprava | 0010 | 1010 | 0 | 1 | ||
| 0 | 0 | Vykonajte aritmetickú operáciu s posunom doprava | 0001 | 0101 | 0 | 0 |
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)10= 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)
| QnQn + 1 | M = 0 1 0 1 1 1 M' + 1 = 1 0 1 0 0 1 | AC | Q | Qn + 1SC |
|---|---|---|---|---|
| Na začiatku | 000 000 | 110111 | 0 6 | |
| 10 | Odčítať M | 101001 | ||
| 101001 | ||||
| Vykonajte aritmetický posun vpravo | 110100 | 111011 | pätnásť | |
| jedenásť | Vykonajte aritmetický posun vpravo | 111010 | 011101 | 1 4 |
| jedenásť | Vykonajte aritmetický posun vpravo | 111101 | 001110 | 1 3 |
| 0 1 | Pridanie (A + M) | 010111 | ||
| 010100 | ||||
| Vykonajte aritmetický posun vpravo | 001010 | 000111 | 0 2 | |
| 10 | Odčítať M | 101001 | ||
| 110011 | ||||
| Vykonajte aritmetický posun vpravo | 111001 | 100011 | jedenásť | |
| jedenásť | Vykonajte aritmetický posun vpravo | 111100 | 110001 | 1 0 |
Qn + 1 = 1, znamená to, že výstup je záporný.
Preto 23 * -9 = dvojkový doplnok 111100110001 => (00001100111)