Ist-Stand-Multiplikation Algorithmus zur Multiplikation 2 positive zahlen?

Ist booth-Algorithmus für die Multiplikation nur für die Multiplikation 2 negative zahlen (-3 * -4) oder eine positive und eine negative Zahl (-3 * 4) ? Immer wenn ich multiplizieren mit 2 positiven zahlen mit Stand-Algorithmus erhalte ich ein Falsches Ergebnis.

Beispiel : 5 * 4

A = 101 000 0 //binary of 5 is 101

S = 011 000 0 //2's complement of 5 is 011

P = 000 100 0 //binary of 4 is 100

x = 3 number of bits in m

y = 3 number of bits in r

m = 5

-m = 2-Komplement von m

r = 4

Nach rechts Verschiebung von P um 1 bit 0 000 100
Nach rechts Verschiebung von P um 1 bit 0 000 010
P+S = 011 001 0

Nach rechts-shift um 1 bit 0 011 001
Verwerfen des LSB 001100

Aber das kommt auf das Programm des 12 . Es sollte 20(010100)

UPDATE nach @ ruakh Antwort

5 * 4 = 20

m = 0101 is 5

r = 0100 is 4

A = 0101 0000 0

S = 1010 0000 0

P = 0000 0100 0

shift P nach rechts um 1 bit : 0 0000 0100
shift P nach rechts um 1 bit : 0 0000 0010
P+S = 10100010
Die Verlagerung rightby 1 bit : 1101 0001
P+A = 1 0010 0001 here 1 is the carry generated
verschieben nach rechts um 1 bit : 110010000

Verlassen des LSB : 11001000 (nicht gleich 20)

InformationsquelleAutor saplingPro | 2011-11-19

5

Bist du nicht geben genug Platz für Ihre Zeichen-handling. 5 ist nicht 101, aber 0101: es beginnt mit einem 0, da die Werte, beginnend mit 1 negativ sind. 101 ist tatsächlich -3: es ist das Zweierkomplement von 011 3. Ähnlich 4 ist nicht 100, aber 0100; 100 ist -4. Also, wenn Sie multiplizieren 101 durch 100, bist du eigentlich die Multiplikation von -3 -4; das ist, warum Sie bekommen 12.
- sehen Sie bitte das update. Ich verstehe immer noch nicht das Ergebnis . Was ist falsch ?
- Jetzt ist Ihre S falsch ist: Sie invertiert die bits, aber vergaß hinzuzufügen, 1. 🙂
- ja ich habe einen Fehler gemacht.Nach der Korrektur der it-und DV - P+A im 4. Schritt, es ist ein carry in MSB von P+A . Wenn ich es weglassen, bekomme ich die richtige Antwort. Aber warum haben wir es weglassen. Wie im 4. Schritt : P+A = 110110001 + 010100000 = 1 001010001 finden Sie die carry (1) in der MSB . Wenn ich es weglassen werde ich die richtige Antwort im nächsten Schritt, wo ich weglassen müssen LSB der Zahl.
- Re: "warum haben wir es zu unterlassen": Naja, weil das ist, was der Algorithmus zu tun, sagt. (Der Wikipedia-Artikel, die Sie verlinkt sagt "Ignorieren Sie jegliches überlaufen.") Wenn Sie möchten, einen tieferen Grund, denken Sie daran, dass 1011 bedeutet das gleiche wie ...11111011, nicht ...00001011. Also, wenn Sie durchgeführt sign extension, dieser trug 1 würde tatsächlich auch weiter nach Links auf unbestimmte Zeit, verändert sich die ganze 1s zu 0s auf dem Weg.
- ruakh, ich bin immer ein Falsches Ergebnis, wenn ich multiplizieren 11*13 mit Stand algo. Ich bekomme 0010001111 aber ich sollte 10001111 . Zwei Nullen in der MSB ' s fehlen. Wird es einen Unterschied machen
- ist richtig. 10001111 wäre falsch, da in zweier-Komplement-notation, bezeichnet eine negative Zahl (-113).
InformationsquelleAutor ruakh

Booth-Algorithmus ist für Ganzzahlen mit Vorzeichen, d.h. jeder kann entweder positiv oder negativ oder null ist.

Hier ein Beispiel für ein C-Programm, das zeigt sowohl eine Umsetzung und die Zwischenergebnisse der Multiplikation zweier 8-bit signed (2-Komplement) ganze zahlen und bekommen einen 16-bit signed Produkt:

#include <stdio.h>
#include <limits.h>
#include <string.h>

typedef signed char int8;
typedef short int16;

char* Num2BaseStr(unsigned long long num, unsigned base, int maxDigits)
{
  static char s[sizeof(num) * CHAR_BIT + 1];
  char* p = &s[sizeof(s) - 1];

  memset(s, 0, sizeof(s));

  do
  {
    *--p = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[num % base];
    num /= base;
  } while ((num != 0) || (p > s));

  //Keep at most maxDigits digits if requested
  if ((maxDigits >= 0) && (&s[sizeof(s) - 1] - p > maxDigits))
  {
    p = &s[sizeof(s) - 1] - maxDigits;
  }
  //Skip leading zeroes otherwise
  else
  {
    while (*p == '0') p++;
  }

  return p;
}

int16 BoothMul(int8 a, int8 b)
{
  int16 result = 0;
  int16 bb = b;
  int f0 = 0, f1;
  int i = 8;

  printf("a = %sb (%d)\n", Num2BaseStr(a, 2, 8), a);
  printf("b = %sb (%d)\n", Num2BaseStr(b, 2, 8), b);
  printf("\n");

  while (i--)
  {
    f1 = a & 1;
    a >>= 1;

    printf("        %sb\n", Num2BaseStr(result, 2, 16));
    printf("(%d%d)  ", f1, f0);
    if (!f1 && f0)
    {
      printf("+ %sb\n", Num2BaseStr(bb, 2, 16));
      result += bb;
    }
    else if (f1 && !f0)
    {
      printf("- %sb\n", Num2BaseStr(bb, 2, 16));
      result -= bb;
    }
    else
    {
      printf("no +/-\n");
    }
    printf("\n");

    bb <<= 1;

    f0 = f1;
  }

  printf("a * b = %sb (%d)\n", Num2BaseStr(result, 2, 16), result);

  return result;
}

int main(void)
{
  const int8 testData[][2] =
  {
    {  4,  5 },
    {  4, -5 },
    { -4,  5 },
    { -4, -5 },
    {  5,  4 },
    {  5, -4 },
    { -5,  4 },
    { -5, -4 },
  };
  int i;

  for (i = 0; i < sizeof(testData)/sizeof(testData[0]); i++)
    printf("%d * %d = %d\n\n",
           testData[i][0],
           testData[i][1],
           BoothMul(testData[i][0], testData[i][1]));

  return 0;
}

Ausgabe:

a = 00000100b (4)
b = 00000101b (5)

        0000000000000000b
(00)  no +/-

        0000000000000000b
(00)  no +/-

        0000000000000000b
(10)  - 0000000000010100b

        1111111111101100b
(01)  + 0000000000101000b

        0000000000010100b
(00)  no +/-

        0000000000010100b
(00)  no +/-

        0000000000010100b
(00)  no +/-

        0000000000010100b
(00)  no +/-

a * b = 0000000000010100b (20)
4 * 5 = 20

a = 00000100b (4)
b = 11111011b (-5)

        0000000000000000b
(00)  no +/-

        0000000000000000b
(00)  no +/-

        0000000000000000b
(10)  - 1111111111101100b

        0000000000010100b
(01)  + 1111111111011000b

        1111111111101100b
(00)  no +/-

        1111111111101100b
(00)  no +/-

        1111111111101100b
(00)  no +/-

        1111111111101100b
(00)  no +/-

a * b = 1111111111101100b (-20)
4 * -5 = -20

a = 11111100b (-4)
b = 00000101b (5)

        0000000000000000b
(00)  no +/-

        0000000000000000b
(00)  no +/-

        0000000000000000b
(10)  - 0000000000010100b

        1111111111101100b
(11)  no +/-

        1111111111101100b
(11)  no +/-

        1111111111101100b
(11)  no +/-

        1111111111101100b
(11)  no +/-

        1111111111101100b
(11)  no +/-

a * b = 1111111111101100b (-20)
-4 * 5 = -20

a = 11111100b (-4)
b = 11111011b (-5)

        0000000000000000b
(00)  no +/-

        0000000000000000b
(00)  no +/-

        0000000000000000b
(10)  - 1111111111101100b

        0000000000010100b
(11)  no +/-

        0000000000010100b
(11)  no +/-

        0000000000010100b
(11)  no +/-

        0000000000010100b
(11)  no +/-

        0000000000010100b
(11)  no +/-

a * b = 0000000000010100b (20)
-4 * -5 = 20

a = 00000101b (5)
b = 00000100b (4)

        0000000000000000b
(10)  - 0000000000000100b

        1111111111111100b
(01)  + 0000000000001000b

        0000000000000100b
(10)  - 0000000000010000b

        1111111111110100b
(01)  + 0000000000100000b

        0000000000010100b
(00)  no +/-

        0000000000010100b
(00)  no +/-

        0000000000010100b
(00)  no +/-

        0000000000010100b
(00)  no +/-

a * b = 0000000000010100b (20)
5 * 4 = 20

a = 00000101b (5)
b = 11111100b (-4)

        0000000000000000b
(10)  - 1111111111111100b

        0000000000000100b
(01)  + 1111111111111000b

        1111111111111100b
(10)  - 1111111111110000b

        0000000000001100b
(01)  + 1111111111100000b

        1111111111101100b
(00)  no +/-

        1111111111101100b
(00)  no +/-

        1111111111101100b
(00)  no +/-

        1111111111101100b
(00)  no +/-

a * b = 1111111111101100b (-20)
5 * -4 = -20

a = 11111011b (-5)
b = 00000100b (4)

        0000000000000000b
(10)  - 0000000000000100b

        1111111111111100b
(11)  no +/-

        1111111111111100b
(01)  + 0000000000010000b

        0000000000001100b
(10)  - 0000000000100000b

        1111111111101100b
(11)  no +/-

        1111111111101100b
(11)  no +/-

        1111111111101100b
(11)  no +/-

        1111111111101100b
(11)  no +/-

a * b = 1111111111101100b (-20)
-5 * 4 = -20

a = 11111011b (-5)
b = 11111100b (-4)

        0000000000000000b
(10)  - 1111111111111100b

        0000000000000100b
(11)  no +/-

        0000000000000100b
(01)  + 1111111111110000b

        1111111111110100b
(10)  - 1111111111100000b

        0000000000010100b
(11)  no +/-

        0000000000010100b
(11)  no +/-

        0000000000010100b
(11)  no +/-

        0000000000010100b
(11)  no +/-

a * b = 0000000000010100b (20)
-5 * -4 = 20

InformationsquelleAutor Alexey Frunze

5*4 =20

m=5,r=4,x=y=4

m=0101 , r=0100 , -m=1011 ,x=y=4

A=0101 0000 0
S=1011 0000 0
P=0000 0100 0

1.  P=0000 0100 0       //last two bits are 00 so simply shift P

    P=0000 0010 0

2.  P=0000 0010 0      //last two bits are 00 so simply shift P

    P=0000 0001 0

3.  P=0000 0001 0      //last two bits are 10 so perform  P = P+S

    P=1011 0001 0

    P=1101 1000 1     //after shifting P

4.  P=1101 1000 1     //last two bits are 01 so perform P = P+A

    P=0010 1000 1

    P=0001 0100 0       //after shifting P


5. now remove LSB 

   the product is P=00010100(20)

InformationsquelleAutor tausy

0

Ich denke x sollte 2 statt 3 -- da 3 ist 11 nur zwei bits lang ist.

InformationsquelleAutor sarnold

Unten, eine Implementierung von Booth ' s Algorithmus entsprechend seiner Flussdiagramm, dargestellt in Kapitel 9, in dem so genannten Buch "Computer-Organisation und Architektur, achte Auflage - William-aufschübe.
Dieses Programm multipliziert zwei zahlen in 4 bits.
Wenn VERBOSE == 1, das Programm zeigt die verschiedenen Schritte des Algorithmus.
PS: Das Programm manipuliert die zahlen als strings.

Glück!

#include <stdio.h>
#define WORD 4
#define VERBOSE 1 //0

/*
 * CSC 2304 - Al Akhawayn University
 * Implementation of the Booth's Algorithm.
 */

void twosComplementAddition(char[], char[]);
void rightShift(char[], char);
void addition(char[], char[]);

char* twosComplementMultiplication(char M[], char Q[]) {
    char C;
    char *A = (char*) malloc(sizeof(char)*(2 * WORD + 1));
    char processedQ[WORD+ 1];
    char Q0, Q_1 = '0';
    int i, j;
    strcpy(A, "0000");
    if (VERBOSE) {
        printf("\n  A   |   Q   |   M   |");
        printf("\n  %s  |   %s  |   %s  |   Initial", A, Q, M);
        printf("\n-------------------------------------------------------------");
    }
    for (i = 0, j = 1; i < WORD; i++, j++) {
        Q0 = Q[WORD - 1];
        if (VERBOSE) {
            printf("\n  %s  |   %s  |   %s  |   Cycle %d", A, Q, M, j);
        }
        if (Q0 == '0' && Q_1 == '1') {
            addition(A, M);
            if (VERBOSE) {
                printf("\n  %s  |   %s  |   %s  |   Addition", A, Q, M);
            }
        } else {
            if (Q0 == '1' && Q_1 == '0') {
                twosComplementAddition(A, M);
                if (VERBOSE) {
                    printf("\n  %s  |   %s  |   %s  |   Two's Complement", A, Q, M);
                }
            }
        }
        Q_1 = Q[WORD - 1];
        rightShift(Q, A[WORD - 1]);
        rightShift(A, A[0]);
        if (VERBOSE) {
            printf("\n  %s  |   %s  |   %s  |   Right Shift", A, Q, M);
            getch();
        }
        printf("\n-------------------------------------------------------------");
    }
    strcat(A, Q);
    return A;
}
void rightShift(char reg[], char bit) {
    int i;
    for (i = WORD - 1; i > 0; i--) {
        reg[i] = reg[i - 1];
    }
    reg[0] = bit;
}

void addition(char A[], char M[]) {
    int i;
    char c = '0';
    for (i = WORD - 1; i >= 0; i--) {
        if (A[i] == '0' && M[i] == '0') {
            A[i] = c;
            c = '0';
        } else {
            if ((A[i] == '1' && M[i] == '0') || (A[i] == '0' && M[i] == '1')) {
                if (c == '0') {
                    A[i] = '1';
                } else {
                    A[i] = '0';
                }
            } else {
                if (A[i] == '1' && M[i] == '1') {
                    A[i] = c;
                    c = '1';
                }
            }
        }
    }
}
void twosComplementAddition(char A[], char M[]) {
    int i;
    char temp[WORD + 1];
    for (i = 0; i < WORD; i++) {
        if (M[i] == '0') {
            temp[i] = '1';
        } else {
            temp[i] = '0';
        }
    }
    temp[WORD] = '\0';
    addition(temp, "0001");
    addition(A, temp);
}

int main() {
    char QQ[WORD + 1];
    char M[WORD + 1];
    char Q[WORD + 1];
    char *result;

    printf("\nBooth's Algorithm");
    printf("\n*****************");
    printf("\nEnter M: ");
    scanf("%s", M);
    printf("\nEnter Q: ");
    scanf("%s", Q);
    strcpy(QQ, Q);
    result = twosComplementMultiplication(M, Q);
    printf("\n%s * %s = %s", M, QQ, result);

    printf("\n");
    return 0;

}

InformationsquelleAutor Mohamed Ennahdi El Idrissi

0

Ist es immer empfohlen, um X+1 bits für eine X-bit Anzahl Multiplikation mit Booth-Algorithmus. Extra ein bit wird verwendet, um das Vorzeichen Werte. Das ist ein problem mit deinem Ansatz. Ohne, dass eine Zahl wie 101 (dezimal:5) wirkt als negative 1.

InformationsquelleAutor Rubal
0

Dem Booth-Algorithmus wird verwendet für die Multiplikation negativer zahlen, entweder eine von Ihnen unterzeichnet werden soll, oder beide von Ihnen unterzeichnet.
wir können nicht für den Booth-Algorithmus für zwei zahlen ohne Vorzeichen.

InformationsquelleAutor deepak kumar
0

Dem Booth-Algorithmus wird verwendet für die Multiplikation negativer zahlen, entweder eine von Ihnen unterzeichnet werden soll, oder beide von Ihnen unterzeichnet.
wir können auch den Booth-Algorithmus für zwei zahlen ohne Vorzeichen, aber wir müssen überprüfen, ob die zahlen in einem bestimmten Bereich.
Zum Beispiel, wenn wir an den 4-bit-zahlen wie 2*3 ist möglich .Wenn wir 9*4 oder 9*-4 * oder * -9*-4 ist nicht möglich, da 9 oder -9 ist nicht im Bereich von 4-bit-zahlen, so booth-Algorithmus der Multiplikation ist nicht möglich.

InformationsquelleAutor Madhu

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.