Computer Arithmetic - Fundamentals of Computer Organization and Architecture - page 71

Example Consider the multiplication of the two positive numbers M ¼ 0111 (7)

and Q ¼ 0011 (3) and assuming that n ¼ 4. The steps needed are tabulated below.

M A Q Q( 2 1)

0111 0000 0011 0 Initial value
0111 1001 0011 0 A ¼ A 2 M
0111 1100 1001 1 ASR End cycle #1
---------------------------------------------------------------------
0111 1110 0100 1 ASR End cycle #2
---------------------------------------------------------------------
0111 0101 0100 1 A ¼ A þ M
0111 0010 1010 0 ASR End cycle #3
---------------------------------------------------------------------
0111 0001 0101 1 ASR End cycle #4

| {z }
þ 21 (correct result)

Example Consider the multiplication of the two numbers M ¼ 0111 (7) and

Q ¼ 1101 ( 3) and assuming that n ¼ 4. The steps needed are tabulated below.

2

M A Q Q( 2 1)

0111 0000 1101 0 Initial value
0111 1001 1101 0 A ¼ A 2 M
0111 1100 1110 1 ASR End cycle #1
---------------------------------------------------------------------
0111 0011 1110 1 A ¼ A þ M
0111 0001 1111 0 ASR End cycle #2
---------------------------------------------------------------------
0111 1010 1111 0 A ¼ A 2 M
0111 1101 0111 1 ASR End cycle #3
---------------------------------------------------------------------
0111

1110 1011 1 ASR End cycle #4

| {z }
2 21 (correct result)

The hardware structure shown in Figure 4.9 can be used to perform the operations
required by the Booth's algorithm. It consists of an ALU that can perform the add

/

sub operation depending on the two bits Q(0)Q( 1). A control circuitry is also

required to perform the ASR (AQ) and to issue the appropriate signals needed to
control the number of cycles.
The main drawbacks of the Booth's algorithm are the variability in the number of
add

2

sub operations and the inefficiency of the algorithm when the bit pattern in Q

/