Algoritmus kabiny je násobící algoritmus, který nám umožňuje vynásobit dvě binární celá čísla se znaménkem v doplňku 2, resp. Používá se také ke zrychlení výkonu procesu násobení. Je také velmi efektivní. Funguje na řetězcových bitech 0 v násobiči, který nevyžaduje žádný další bit, pouze posouvá bity řetězce nejvíce vpravo a řetězec 1 v bitové váze násobiče 2^kna váhu 2^mkteré lze považovat za 2^{k+ 1}- 2^m .

Následuje obrázkové znázornění Boothova algoritmu:

Ve výše uvedeném vývojovém diagramu zpočátku AC a Q_{n + 1} bity jsou nastaveny na 0 a SC je sekvenční čítač, který představuje celkovou sadu bitů n, který se rovná počtu bitů v násobiči. Existují BR které představují multiplikandové bity, a QR představuje multiplikační bity . Poté jsme narazili na dva bity násobiče jako Q_na Q_{n + 1}, kde Qn představuje poslední bit QR a Q_{n + 1}představuje inkrementovaný bit Qn o 1. Předpokládejme, že dva bity násobiče jsou rovny 10; to znamená, že musíme odečíst násobitel od dílčího součinu v akumulátoru AC a poté provést aritmetický posun (ashr). Pokud se dva z multiplikátorů rovnají 01, znamená to, že musíme provést přidání násobiče k dílčímu součinu v akumulátoru AC a poté provést operaci aritmetického posunu ( Ashr ), počítaje v to Q_{n + 1} . Operace aritmetického posunu se používá v Boothově algoritmu k posunutí bitů AC a QR doprava o jedničku a znaménkový bit v AC zůstává nezměněn. A sekvenční čítač se nepřetržitě snižuje, dokud se výpočetní smyčka neopakuje, rovnající se počtu bitů (n).

Práce na algoritmu Booth

1. Nastavte binární bity násobiče a násobiče na M a Q.
2. Nejprve nastavíme AC a Q_{n + 1}registruje hodnotu na 0.
3. SC představuje počet bitů multiplikátoru (Q) a je to sekvenční čítač, který se průběžně snižuje, dokud se nerovná počtu bitů (n) nebo je dosažen na 0.
4. Qn představuje poslední bit Q a Q_n+1ukazuje inkrementovaný bit Qn o 1.
5. V každém cyklu budkového algoritmu, Q_na Q_{n + 1}bity budou kontrolovány na následujících parametrech takto:
   1. Když dva bity Q_na Q_{n + 1}jsou 00 nebo 11, jednoduše provedeme aritmetický posun doprava (ashr) na dílčí součin AC. A bity Qn a Q_{n + 1}se zvýší o 1 bit.
   2. Pokud bity Q_na Q_{n + 1}je zobrazen na 01, multiplikandové bity (M) budou přidány do AC (Accumulator registru). Poté provedeme operaci posunutí doprava na AC a QR bity o 1.
   3. Pokud bity Q_na Q_{n + 1}je zobrazen na 10, multiplikandové bity (M) budou odečteny od AC (registr akumulátoru). Poté provedeme operaci posunutí doprava na AC a QR bity o 1.
6. Operace nepřetržitě funguje, dokud nedosáhneme n - 1 bitu v algoritmu kabiny.
7. Výsledky násobení binárních bitů budou uloženy v registrech AC a QR.

V Boothově algoritmu se používají dvě metody:

herec saira banu

1. RSC (Right Shift Circular)

Posune bit nejvíce vpravo binárního čísla a pak se přidá na začátek binárních bitů.

2. RSA (pravá aritmetika)

Přidá dva binární bity a poté posune výsledek doprava o 1 bitovou pozici.

npm cache vymazat

Příklad : 0100 + 0110 => 1010, po sečtení binárního čísla posuňte každý bit o 1 doprava a první bit výslednice umístěte na začátek nového bitu.

Příklad: Vynásobte dvě čísla 7 a 3 pomocí Boothova násobícího algoritmu.

let . Zde máme dvě čísla, 7 a 3. Nejprve musíme převést 7 a 3 na binární čísla jako 7 = (0111) a 3 = (0011). Nyní nastavte 7 (v binárním kódu 0111) jako multiplikand (M) a 3 (v binárním kódu 0011) jako multiplikátor (Q). A SC (Sequence Count) představuje počet bitů, a zde máme 4 bity, takže nastavte SC = 4. Také ukazuje počet iteračních cyklů algoritmů kabiny a pak cykly proběhnou SC = SC - 1 krát.

Numerický příklad Boothova násobícího algoritmu je 7 x 3 = 21 a binární reprezentace 21 je 10101. Zde dostaneme výslednici v binární 00010101. Nyní ji převedeme na desítkovou soustavu, jako (000010101)₁₀= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

příklad binárního vyhledávacího stromu

Příklad: Vynásobte dvě čísla 23 a -9 pomocí Boothova násobícího algoritmu.

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

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

Proto 23 * -9 = 2 doplněk 111100110001 => (00001100111)