Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-04-07
2001-05-29
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06240438
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a multiplier circuit, an adder circuit constituting part of the multiplier circuit, a partial product bit compression method for the multiplier circuit, and a large-scale semiconductor integrated circuit using the multiplier circuit, and more particularly, to a multiplier circuit which is reduced in size by reducing the number of necessary elements without sacrificing its high speed capability.
2. Description of the Related Art
In recent years, with rapid advances in manufacturing and design technologies of large-scale semiconductor integrated circuits, exemplified by microprocessors and digital signal processors, a demand for high-speed, large-scale arithmetic circuits has been increasing. In particular, for multiplier circuits that require long calculation times and a larger number of circuits, high-speed circuits with reduced number of elements are needed.
The prior arts and their associated problems will be described in detail later with reference to the accompanying drawings.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a multiplier circuit which is reduced in size by reducing the number of necessary elements without sacrificing its high speed capability. More specifically, a first object of the invention is to provide a partial product bit generating circuit (multiplier circuit) that can reduce the number of necessary elements by half, and an encoder (Booth encoder) suitable for implementing the partial product bit generating circuit. A second object of the invention is to provide an adder circuit (4-2 compression circuit: multiplier circuit), specifically a carry-save adder circuit with four inputs for each digit place (4-2 compression circuit), that can be constructed with 50 or less elements as compared with prior art implementations requiring more than 50 elements. A third object of the invention is to provide a partial product bit compression method for reducing the number of partial product bits for each digit place, that can shorten the critical path in partial bit compression processing without increasing the number of necessary elements compared with the prior art.
According to the present invention, there is provided an adder circuit which takes, for each digit place, four input signals and one intermediate carry-in signal, and generates one intermediate carry-out signal along with a sum signal and a carry signal for output, wherein an OR or NOR signal and an exclusive-OR signal of a first input signal and a second input signal from the same digit place are formed, and when the exclusive-OR signal is a first value, a third input signal from the same digit place is output as the intermediate carry-out signal, while when the exclusive-OR signal is a second value, the OR or NOR signal is output as the intermediate carry-out signal.
Further, according to the present invention, there provided an adder circuit which takes, for each digit place, four input signals and one intermediate carry-in signal, and generates one intermediate carry-out signal along with a sum signal and a carry signal for output, wherein an AND or NAND signal and an exclusive-OR signal of a first input signal and a second input signal from the same digit place are formed, and when the exclusive-OR signal is a first value, a third input signal from the same digit place is output as the intermediate carry-out signal, while when the exclusive-OR signal is a second value, the AND or NAND signal is output as the intermediate carry-out signal.
A circuit for generating the sum signal by exclusive-ORing the five input signals may comprise a first exclusive-OR circuit, constructed from a single-transfer-gate circuit, for exclusive-ORing the exclusive-OR signal of the first and second input signals with the exclusive-OR signal of the third and fourth signals from the same digit place; and a plurality of second exclusive-OR circuits, each constructed from a drive gate circuit or a complementary-transfer-gate circuit, for exclusive-ORing the other signals. The first exclusive-OR circuit may comprise six transistors.
In addition, according to the present invention, there is provided an adder circuit which takes, for each digit place, four input signals and one intermediate carry-in signal, and generates one intermediate carry-out signal along with a sum signal and a carry signal for output, wherein a circuit for generating the sum signal by exclusive-ORing the five input signals comprises a first exclusive-OR circuit, constructed from a single-transfer-gate circuit, for exclusive-ORing the exclusive-OR signal of the first and second input signals with the exclusive-OR signal of the third and fourth signals from the same digit place; and a plurality of second exclusive-OR circuits, each constructed from a drive gate circuit or a complementary-transfer-gate circuit, for exclusive-ORing the other signals.
The adder circuit may be included in a digital multiplier circuit.
According to the present invention, there is also provided a multiplier circuit comprising an encoder for receiving a multiplier bit signal and for outputting a plurality of encode signals; and a partial product bit generating circuit for receiving the encode signals along with a multiplicand bit signal from each digit place and for generating a partial product bit for each digit place, the partial product bit generating circuit including a first selection circuit for selecting a logically true signal from among the encode signals in accordance with a value of the multiplicand bit signal.
The multiplicand bit signal and its inverted signal may be supplied to the partial product bit generating circuit. The encoder may be a Booth encoder. The encode signals to be selected by the first selection circuit may be signals identifying whether a necessary signal as an encoded result is the multiplicand bit signal itself or its inverted signal.
The partial product bit generating circuit may be loaded with multiplicand bit signals from a plurality of digit places; and the partial product bit generating circuit may further include a second selection circuit for selecting, from among the plurality of signals selected based on each multiplicand bit signal, a signal that matches the result of encoding in accordance with an encode signal different from the selected signals.
Each of the first and second selection circuits may be constructed from two AND circuits and one NOR circuit. Each of the first and second selection circuits may be constructed from transfer gates. Each of the first and second selection circuits may be constructed from two transfer gates.
The multiplicand bit signal lines for transferring complementary multiplicand bit signals corresponding to multiplicand digits may be arranged in parallel to each other extending in a first direction in a two-dimensional plane, and sets of encode signal lines corresponding to multiplier digits may be arranged extending in a second direction that intersects the first direction, while the partial product bit generating circuit is repeatedly arranged in order to contain a plurality of predetermined adjacent intersections of the multiplicand bit signal lines and the encode signal lines.
Further, according to the present invention, there is provided a multiplier circuit utilizing a Booth algorithm, comprising a circuit which, instead of a partial product bit signal in accordance with the Booth algorithm, generates for each digit place a bit signal corresponding to a sum of a correction value for twos complement of a most significant partial product and a binary number represented by a bit in a sign digit of a least significant partial product and bits from a least significant digit of the most significant partial product to a digit one position lower than the sign digit of the least significant partial product.
Further, according to the present invention, there is also provided a multiplier circuit utilizing a method for avoiding sign extension by correction processing, comprising a circuit which
Arent Fox Kintner & Plotkin & Kahn, PLLC
Fujitsu Limited
Mai Tan V.
LandOfFree
Multiplier circuit for reducing the number of necessary... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiplier circuit for reducing the number of necessary..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiplier circuit for reducing the number of necessary... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2504083