Browse Prior Art Database

Pseudo Two-Bit Multiplier for Decreased Delay and Circuit Size

IP.com Disclosure Number: IPCOM000118051D
Original Publication Date: 1996-Aug-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 2 page(s) / 32K

Publishing Venue

IBM

Related People

Imming, KC: AUTHOR [+2]

Abstract

Disclosed is a hardware binary multiplier for reduced circuit area and delay that achieves two-bit non-overlapping add-shift performance 75% of the time.

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

Pseudo Two-Bit Multiplier for Decreased Delay and Circuit Size

      Disclosed is a hardware binary multiplier for reduced circuit
area and delay that achieves two-bit non-overlapping add-shift
performance 75% of the time.

      To compute P = X * Y with a two-bit add-shift multiplication
algorithm, a maximum of N/2 cycles are required where N is the number
of bits in the multiplicand.  This is implemented with the following
algorithm:
  P <= 0
  Do unitl Y=0
    IF Y(1:0) = 00    THEN   P<=P+0,  Y <= Y shift right 2
    IF Y(1:0) = 01    THEN   P<=P+X,  Y <= Y shift right 2
    IF Y(1:0) = 10    THEN   P<=P+2X, Y <= Y shift right 2
    IF Y(1:0) = 11    THEN   P<=P+3X, Y <= Y shift right 2
  END

      A carry-save adder is needed for the 3X case, where X and 2X
must both be added to the partial result.  Since only 25% of the
cases use the carry-save adder, the following revised algorithm is
implemented, eliminating the need for the 3X add.
  P <= 0
  Do unitl Y=0
    IF Y(1:0) = 00    THEN   P<=P+0,  Y <= Y shift right 2
    IF Y(1:0) = 01    THEN   P<=P+X,  Y <= Y shift right 2
    IF Y(1:0) = 10    THEN   P<=P+2X, Y <= Y shift right 2
    IF Y(1:0) = 11    THEN   P<=P+X , Y <= Y shift right 1
  END

      This solution eliminates the need for the carry-save adder,
and thus eliminates the logic delay and circuit area it required.
The result is a slightly slower multiplication for...