Scribd
Upload
36 views4 pages

Booth Algorithm and Bit-Pair Recoding

The document explains the Booth Algorithm for both signed and unsigned multiplication, providing examples of multiplying -5 by -3 and 11 by 13. It details the conversion of numbers to 2's complement and the Booth format, along with the Bit-Pair Recoding method. The document emphasizes the bit-length of the results for each multiplication operation.

Uploaded by

anson
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
36 views4 pages

Booth Algorithm and Bit-Pair Recoding

The document explains the Booth Algorithm for both signed and unsigned multiplication, providing examples of multiplying -5 by -3 and 11 by 13. It details the conversion of numbers to 2's complement and the Booth format, along with the Bit-Pair Recoding method. The document emphasizes the bit-length of the results for each multiplication operation.

Uploaded by

anson
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Booth Algorithm (Signed Multiplication)

(-5) × (-3) = 15

0101 (5) ➔ 1011 (-5, 2’s complement)


0011 (3) ➔ 1101 (-5, 2’s complement)

Bit i Bit i – 1 Booth format


0 0 0
0 1 +1
1 0 -1
1 1 0

The Booth format of 1101 (-3) is

1 1 0 1 0
   
0 -1 1 -1

It is a 4-bit multiplication, and the answer should be 8 bits.

1 1 1 1 1 0 1 1
× 0 -1 1 -1
0 0 0 0 0 1 0 1
1 1 1 1 0 1 1
0 0 0 1 0 1
0 0 0 0 1 1 1 1
Booth Algorithm (Unsigned Multiplication)

11 × 13 = 143

01011 (11)
01101 (13)

Bit i Bit i – 1 Booth format


0 0 0
0 1 +1
1 0 -1
1 1 0

The Booth format of 01101 (13) is

0 1 1 0 1 0
    
1 0 -1 1 -1

It is a 5-bit multiplication, and the answer should be 10 bits.

0 0 0 0 0 0 1 0 1 1
× 1 0 -1 1 -1
1 1 1 1 1 1 0 1 0 1
0 0 0 0 0 1 0 1 1
1 1 1 1 0 1 0 1
0 0 1 0 1 1
0 0 1 0 0 0 1 1 1 1
Bit-Pair Recoding (Signed Multiplication)

(-5) × (-3) = 15

0101 (5) ➔ 1011 (-5, 2’s complement)


0011 (3) ➔ 1101 (-5, 2’s complement)

Booth Format Booth Format Bit-Pair Recoding Bit-Pair Recoding


Bit i Bit i – 1 Bit i Bit i – 1
1 -1 0 1
-1 1 0 -1
1 0 0 2
-1 0 0 -2
0 -1 0 -1
0 1 0 1
0 0 0 0
0 / 0 /
1 / 1 /

The values of Booth Format in the last five rows are the same as Bit-Pair Recoding.

The Bit-Pair Recoding values of 1101 (-3) are

1 1 0 1 0
   
0 -1 1 -1 Booth Format

0 -1 0 1 Bit-Pair Recoding

It is a 4-bit multiplication, and the answer should be 8 bits.

1 1 1 1 1 0 1 1
× 0 -1 0 1
1 1 1 1 1 0 1 1
0 0 0 1 0 1
0 0 0 0 1 1 1 1
Bit-Pair Recoding (Unsigned Multiplication)

11 × 13 = 143

01011 (11)
01101 (13)

Booth Format Booth Format Bit-Pair Recoding Bit-Pair Recoding


Bit i Bit i – 1 Bit i Bit i – 1
1 -1 0 1
-1 1 0 -1
1 0 0 2
-1 0 0 -2
0 -1 0 -1
0 1 0 1
0 0 0 0
0 / 0 /
1 / 1 /

The Bit-Pair Recoding values of 01101 (13) are

0 1 1 0 1 0
    
1 0 -1 1 -1 Booth Format

1 0 -1 0 1 Bit-Pair Recoding

It is a 5-bit multiplication, and the answer should be 10 bits.

0 0 0 0 0 0 1 0 1 1
× 1 0 -1 0 1
0 0 0 0 0 0 1 0 1 1
1 1 1 1 0 1 0 1
0 0 1 0 1 1
0 0 1 0 0 0 1 1 1 1
Lawrence Cheung
October 2021

You might also like