Browse Prior Art Database

Statistical Approach To Booth's Algorithm

IP.com Disclosure Number: IPCOM000110912D
Original Publication Date: 1994-Jan-01
Included in the Prior Art Database: 2005-Mar-26

Publishing Venue

IBM

Related People

Dieffenderfer, JN: AUTHOR [+2]

Abstract

This article describes an alternate approach to Booth's algorithm that allows for a faster cycle time and a statistically faster binary integer multiply. (Note the comparisons made in this paper do not apply to Wallace tree-type adders used in multiplication.)

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Statistical Approach To Booth's Algorithm

      This article describes an alternate approach to Booth's
algorithm that allows for a faster cycle time and a statistically
faster binary integer multiply.  (Note the comparisons made in this
paper do not apply to Wallace tree-type adders used in
multiplication.)

      Three new bits at a time means shifting right three bits each
cycle.  It is three bits and more which becomes interesting.  The
derivation:

      The problem with three new bits at a time (and greater than 3
new bits at a time) is how to handle the 3N terms.  Multiples of
2(sub)x xN where x=0,1,2,3...., can be simply wired into a
multiplexer (mux).  Terms like 3N cannot be directly wired.  A direct
implementation uses a second adder/subtracter unit, as shown in Fig.
3.

      Two different pairs of muxes are shown at the top of the first
Direct Booth implementation of Fig. 1.  Either of these mux pairs can
be used to generate all the possible combinations of N including 0xN.
The output mux for both configurations has straight F for the
unsigned multiplier case and 1/8 F for shifting three bits at a time.
The 1/4 F is needed because 8 bits is not evenly divisible by 3.  The
first two shifts are 3 bits wide, and the last shift is 2 bits wide.
The 2-bit shift adheres to the 2 new bits at a time rules listed in
Table 2.

      An alternate approach to the Direct Booth implementation and
the subject of this disclosure is what we call Statistical Booth.
Those entries in Table 3 which require +3N or -3N are treated as 2
new bits at a time and only shifted right 2 bits.  Table 4 shows the
rules for the Statistical Booth approach.

      With the Statistical Booth method the need for a second adder/
subtracter is eliminated, as shown in Fig. 4.

      Eliminating the need to add +3N to the partial product requires
the addition of the 1/2 F term on the output mux to incorporate a
one-bit shift right.  Eight bit positions need to be shifted right
for the product to be correctly oriented in the PP MR registers.
Three possible shift patterns require a final single bit shift; 3221,
2321, and 2231.  Fig. 5 shows the state machine for Statistical
Booth's implementation.

      States A through H of Fig. 3 represent the number of shifts
left to complete the multiply.  A = 8 bit positions left to shift, C
= 6 bit positions left, D = 5 bit positions left, E = 4 bit positions
left, F = 3 bit positions left, G = 2 bit positions left, and H = 1
bit position left.  There is no state B since there is not a shift
combina- tion to yield 7 bits left.  State I advances to state J if
the multiplier is unsigned and the most significant bit is a one.

      Table 3 shows each path through t...