Het booth-algoritme is een vermenigvuldigingsalgoritme waarmee we de twee binaire gehele getallen met teken respectievelijk in 2-complement kunnen vermenigvuldigen. Het wordt ook gebruikt om de uitvoering van het vermenigvuldigingsproces te versnellen. Het is ook heel efficiënt. Het werkt op de stringbits 0's in de vermenigvuldiger, waarvoor geen extra bit nodig is. Verschuif alleen de meest rechtse stringbits en een string van 1's in een vermenigvuldigerbitgewicht 2^knaar gewicht 2^Mdat kan worden beschouwd als 2^k+1- 2^M .

Hieronder volgt de grafische weergave van het algoritme van Booth:

In het bovenstaande stroomschema is aanvankelijk AC En Q_n+1 bits zijn ingesteld op 0, en de SC is een reeksteller die het totaal aantal ingestelde bits vertegenwoordigt N, wat gelijk is aan het aantal bits in de vermenigvuldiger. Er zijn BR die vertegenwoordigen de vermenigvuldigende bits, en QR vertegenwoordigt de vermenigvuldiger bits . Daarna kwamen we twee bits van de vermenigvuldiger tegen als Q_Nen Q_n+1, waarbij Qn het laatste stukje QR vertegenwoordigt, en Q_n+1vertegenwoordigt het opgehoogde bit van Qn met 1. Stel dat twee bits van de vermenigvuldiger gelijk zijn aan 10; het betekent dat we de vermenigvuldiger moeten aftrekken van het deelproduct in de accumulator AC en vervolgens de rekenkundige verschuivingsoperatie (ashr) moeten uitvoeren. Als de twee vermenigvuldigers gelijk zijn aan 01, betekent dit dat we de optelling van de vermenigvuldiger aan het deelproduct in accumulator AC moeten uitvoeren en vervolgens de rekenkundige verschuivingsbewerking moeten uitvoeren ( Ashr ), inbegrepen Q_n+1 . De rekenkundige verschuivingsbewerking wordt in het algoritme van Booth gebruikt om AC- en QR-bits één stap naar rechts te verschuiven, waarbij de tekenbit in AC ongewijzigd blijft. En de reeksteller wordt continu verlaagd totdat de rekenlus wordt herhaald, gelijk aan het aantal bits (n).

Werken aan het Booth-algoritme

1. Stel de binaire bits Multiplicand en Multiplier in als respectievelijk M en Q.
2. In eerste instantie hebben we de AC en Q ingesteld_n+1registreert de waarde op 0.
3. SC vertegenwoordigt het aantal vermenigvuldigerbits (Q), en het is een reeksteller die continu wordt verlaagd tot gelijk aan het aantal bits (n) of tot 0 wordt bereikt.
4. Een Qn vertegenwoordigt het laatste bit van de Q, en de Q_n+1toont het opgehoogde bit van Qn met 1.
5. Bij elke cyclus van het cabine-algoritme wordt Q_Nen Q_n+1bits worden als volgt gecontroleerd op de volgende parameters:
   1. Wanneer twee bits Q_Nen Q_n+100 of 11 zijn, voeren we eenvoudigweg de rekenkundige verschuiving naar rechts (ashr) uit op het deelproduct AC. En de stukjes Qn en Q_n+1wordt met 1 bit verhoogd.
   2. Als de bits van Q_Nen Q_n+1Als 01 wordt weergegeven, worden de vermenigvuldigingsbits (M) toegevoegd aan het AC (accumulatorregister). Daarna voeren we de juiste verschuivingsbewerking uit op de AC- en QR-bits met 1.
   3. Als de bits van Q_Nen Q_n+1Als dit 10 is, worden de vermenigvuldigingsbits (M) afgetrokken van het AC (accumulatorregister). Daarna voeren we de juiste verschuivingsbewerking uit op de AC- en QR-bits met 1.
6. De bewerking werkt continu totdat we n - 1 bit hebben bereikt in het booth-algoritme.
7. Resultaten van de binaire bits voor vermenigvuldiging worden opgeslagen in de AC- en QR-registers.

Er worden twee methoden gebruikt in het algoritme van Booth:

regressietesten bij het testen van software

1. RSC (rechts-shiftcirculaire)

Het verschuift het meest rechtse bit van het binaire getal en wordt vervolgens toegevoegd aan het begin van de binaire bits.

2. RSA (Rechter Shift-rekenkunde)

Het telt de twee binaire bits op en verschuift vervolgens het resultaat met 1 bit naar rechts.

Java-programmalus

Voorbeeld : 0100 + 0110 => 1010, na het toevoegen van het binaire getal, schuif elk bit met 1 naar rechts en plaats het eerste bit van de resultante aan het begin van het nieuwe bit.

Voorbeeld: Vermenigvuldig de twee getallen 7 en 3 met behulp van het vermenigvuldigingsalgoritme van Booth.

Jaren . Hier hebben we twee getallen, 7 en 3. Allereerst moeten we 7 en 3 omzetten in binaire getallen zoals 7 = (0111) en 3 = (0011). Stel nu 7 (in binair getal 0111) in als vermenigvuldiger (M) en 3 (in binair getal 0011) als vermenigvuldiger (Q). En SC (Sequence Count) vertegenwoordigt het aantal bits, en hier hebben we 4 bits, dus stel de SC = 4 in. Het toont ook het aantal iteratiecycli van de algoritmen van de cabine en vervolgens worden de cycli SC = SC - 1 keer uitgevoerd.

Het numerieke voorbeeld van het Booth-vermenigvuldigingsalgoritme is 7 x 3 = 21 en de binaire representatie van 21 is 10101. Hier krijgen we de resultante in binair getal 00010101. Nu zetten we deze om in decimaal, als (000010101)₁₀= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

ls commando's linux

Voorbeeld: Vermenigvuldig de twee getallen 23 en -9 met behulp van het vermenigvuldigingsalgoritme van Booth.

Hier is M = 23 = (010111) en Q = -9 = (110111)

Q_n+1 = 1, dit betekent dat de uitvoer negatief is.

Dus 23 * -9 = 2's complement van 111100110001 => (00001100111)