Multipliers with a shorter run time

Details Multipliers with a shorter run time Multipliers with a shorter run time

1996-09-23

1999-09-21

Moise, Emmanuel L.

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

G06F 752

Patent

active

059547910

DESCRIPTION:

BRIEF SUMMARY
BACKGROUND OF THE INVENTION

1. Field of the Invention
The present invention relates to simplified multipliers for binary coded numbers which have shorter run times than known multipliers.
2. Description of the Related Art
Various multiplier structures are known for the purpose of multiplying binary coded numbers. Both serial-operating and parallel-operating multiplier methods are applied. It is possible, for example, to use as a 4-quadrant multiplier a field multiplier whose algorithm is described in the journal `IEEE Transactions on Computers`, Vol. C-22, No. 12, December 1973, pages 1045 to 1047, or a BOOTH multiplier such as is described in Klar, Springer Verlag 1993, pages 228 to 232.
The BOOTH multiplier represented uses carry-ripple logic. In addition to positive numbers, the 4-quadrant multipliers can also process negative numbers in the form of two's complements. If, for example, a BOOTH multiplier is designed using carry-save logic in order to shorten the run time, the sign bit must be supplemented in the individual stages by at least two further bit positions which are fed to inputs of half-adders or full adders of the following adding stage.
For example, by multiplying the multiplicand by, in each case, one bit of the multiplier factor, partial products are formed of which firstly the lowest-order are added. A further partial product in then respectively added to the partial product subtotal formed.
A basic rule in adding numbers in two's complement representations requires that in the case of multipliers (adders) designed using carry-save technology the sign bits (which are the highest-order bits) are supplemented as far as the highest significance of the highest-order summand or partial product. This means, in turn, that each sign bit in the individual adder rows must be led to the inputs of further adders.
In the case of multipliers using carry-ripple technology, too, by multiplying the multiplicand by, in each case one bit of the multiplier factor partial products are formed of which likewise initially the lowest-order are added using carry-ripple technology. A further partial product is then likewise respectively added to the partial product subtotal formed.
The corresponding basic rule for adding numbers in a two's complement representation also requires that the sign bits (which are the highest-order bits) are supplemented up to the highest significance of the expected sum in the case of multipliers (adders) designed using carry-ripple technology. This means that each sign bit must be led to an input of at least one further adder.
The run time is substantially lengthened in all types of multiplier, particularly by the capacitive loading owing to further adder inputs.
A method of simplification in the case of supplementing the sign bits of Booth multipliers, which is designed in accordance with FIG. 4 using full adders, is specified in the publication "Electronics Letters", Sep. 25, 1986, Vol. 22, No. 20, page 1061 to 1062. However, there are no details on further circuit simplification. It is further mentioned that the method is not limited to Booth multipliers. However, its application does not lead to an optimum result in the case of other types of multiplier.


SUMMARY OF THE INVENTION

It is an object of the invention to specify multipliers with a simpler design and reduced run time.
This and other objects and advantages of the invention are achieved by a multiplier having a matrix-shaped circuit arrangement of a plurality of adder rows in which the sign bits of partial products or their subtotals are supplemented by at least one binary digit, by the sign bit to be supplemented being fed inverted to an adder of the next adder row and in addition a one being added in this adder, and in that instead of the sign bit a constant one is added in each case in the higher-order adders of the same adder row, characterized in that the lowest-order full adder of the first adder row, which combines two sign bits of two partial products, is fed the sign bits inverted and in that the highest-order

REFERENCES:
patent: 4748584 (1988-05-01), Noda
patent: 4910701 (1990-03-01), Gibbons et al.
patent: 5262976 (1993-11-01), Young et al.
Henlin et al., "A 16 Bit.times.16 Bit Pipelined Multiplier Macrocell", IEEE Journal of Solid-State Circuits, vol. SC-20, No. 2, Apr. 1985, pp. 542-547.
Klar, "Integrierte Digitale Schaltungen MOS/BICMOS", Springer-Verlag 1993, pp. 228-232.
Baugh et al., member, IEEE, "A Two's Complement Parallel Array Multiplication Algorithm", IEEE Transactions on Computers, vol. C-22, No. 12, Dec. 1973, pp. 1045-1047.
R. Roncella et al., "Application of a Systolic Macrocell-Based VLSI Design Style to the Design of a Single-Chip High-Performance Fir Filter", IEEE Proceedings-G, vol. 138, No. 1, Feb. 1991, pp. 17-21.
Vassiliadis et al., member IEEE, "Hard-Wired Multipliers with Encoded Partial Products", IEEE Transactions on Computers, vol. 40, No. 11, Nov. 1991, pp. 1181-1197.
Sunder, "A Fast Multiplier Based on the Modified Booth Algorithm", Inter. Journal of Electronics, 1993, vol. 75, No. 2, pp. 199-208.
Electronics Letters, Aug. 16th, 1990, vol. 26, No. 17, pp. 1413-1415.
Electronics Letters, Sep. 25th, 1986, vol. 22, No. 20, pp. 1061-1062.

Affiliated with

Also associated with

Rating

Multipliers with a shorter run time does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multipliers with a shorter run time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multipliers with a shorter run time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-75754