REGISTER  |  SIGN IN
United States Patent5600569
Nishiyama , ; et al.February 4, 1997
Title
Method, system, and apparatus for automatically designing logic circuit, and multiplier
Abstract
With respect to each bit of a multiplier factor, it is judged whether or not the multiplier factor is a variable or a constant. If the multiplier factor is a constant, it is judged whether or not a bit of concern in the multiplier factor has the value of 1. Only if the bit of concern in the multiplier factor is 1, there is generated a circuit for outputting, as a partial product, a signal indicating a multiplicand. The signal indicating the multiplicand is then shifted by one bit so that the resulting signal is newly set as the signal indicating the multiplicand. By repeatedly executing the foregoing process with respect to all the bits of the multiplier factor, a circuit for calculating a partial product with respect to each bit of the multiplier factor is generated.
Inventors:Nishiyama; Tamotsu (Osaka, JP), Tsubata; Shintaro  (Osaka, JP)
Assignee:Matsushita Electric Industrial Co., Ltd. (Kadoma, JP)
Appl. No.:300802
Filed:September 2, 1994
Foreign Application Priority Data
Sep 02, 1993 [JP] 5-218780
Current U.S. Class:716/1 716/17 708/625 708/627 
Field of Search:364/488,489,490,736,754,757
U.S. Patent Documents
4792909December 1988Serlet
5043914August 1991Nishiyama et al.
5146583September 1992Matsunaka et al.
5200907April 1993Tran
5313414May 1994Yang et al.
5412591May 1995Bapst
Foreign Patent Documents
0309292Mar., 1989EP
0447244Mar., 1991EP
0605885Jul., 1994EP
3-15984Jan., 1991JP
3-17737Jan., 1991JP
51-64844Jun., 1976JP
Other References
NIKKEI Electronics, May 29, 1978, pp. 76-89. .
Patent Abstracts of Japan, vol. 18, No. 606 (P-1827) (Aug. 12, 1994). .
Patent Abstracts of Japan, vol. 18, No. 631 (P-1836) (Sep. 2, 1994). .
Patent Abstracts of Japan, vol. 15, No. 136 (P-1187) (Jan. 24 1991). .
Patent Abstracts of Japan, vol. 15, No. 140 (P-1188) (Jan. 25, 1991)..~
Primary Examiner: Trans; Vincent N.
Attorney, Agent or Firm:McDermott, Will & Emery
Claims

We claim:
1. A method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and a multiplicand, comprising the steps of:
with respect to each bit of the multiplier factor,
(a) judging whether the multiplier factor is a variable or a constant;
(b) if the multiplier factor is a variable, generating information on a circuit for selecting, based on the value of a bit of concern in the multiplier factor, either of a signal indicating the multiplicand and a signal indicating 0 and outputting the selected signal as a partial product;
(c) if the multiplier factor is a constant, judging whether or not the value of said bit in the multiplier factor is 1;
(d) if the value of said bit in the multiplier factor is 1, generating information on a circuit for outputting the signal indicating the multiplicand as a partial product; and
(e) after executing the steps (a) to (d), generating information on a shift circuit for shifting the signal indicating the multiplicand by one bit and newly setting the output signal from said shift circuit as a signal indicating the multiplicand to be used in the steps (a) to (d),
the steps (a) to (e) being repeatedly executed for all the bits of the multiplier factor.

2. A method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and a multiplicand, comprising the steps of:
with respect to each group consisting of n partial products obtained by evenly dividing a plurality of partial products which are the products of the individual bits of the multiplier factor and the multiplicand,
(a) generating information on an adding circuit for receiving the n partial products in a group of concern and outputting the sum of the n partial products in said group as m (<n) partial products; and
with respect to all said plurality of partial products,
(b) after repeatedly executing the step (a), newly setting all the partial products that are the outputs of the adding circuit generated in the step (a) and those partial products of said plurality of partial products which were not received by the adding circuit generated in the step (a) as the plurality of partial products to be processed in the step (a),
the steps (a) and (b) being repeatedly executed.

3. A method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and a multiplicand, comprising the steps of:
with respect to each group consisting of three partial products obtained by evenly dividing a plurality of partial products which are the products of the individual bits of the multiplier factor and the multiplicand,
(a) generating information on a carry-save adder for receiving the three partial products in a group of concern and outputting the sum of said three partial products as two partial products; and
with respect to all said partial products,
(b) after executing the step (a), newly setting all the partial products that are the outputs of the carry-save adder generated in the step (a) and those partial products of said plurality of partial products which were not received by the carry-save adder generated in the step (a) as the plurality of partial products to be processed in the step (a),
the steps (a) and (b) being repeatedly executed until the number of the new partial products newly set in the step (b) becomes two.

4. A method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and a multiplicand, comprising the steps of:
(a) detecting the number of partial products as the products of the individual bits of the multiplier factor and the multiplicand;
(b) if the number of the partial products is n or more, with respect to each group consisting of n partial products obtained by evenly dividing a plurality of partial products,
(b-1) generating information on an adding circuit for receiving the n partial products in a group of concern and outputting the sum of said n partial products as m (<n) partial products and
with respect to all said plurality of partial products,
(b-2) after repeatedly executing the step (b-1), newly setting all the partial products that are the outputs of the adding circuit generated in the step (b-1) and those partial products of said plurality of partial products which were not received by the adding circuit generated in the step (b-1) as the plurality of partial products to be processed in the step (b-1),
the steps (b-1) and (b-2) being repeatedly executed until the number of the partial products newly set in the step (b-2) becomes m; and
(c) if the number of the partial products is m or less and 2 or more, generating information on a final sum circuit for receiving said number or partial products and calculating the product of the multiplier factor and the multiplicand by adding up said partial products.

5. A method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and a multiplicand, comprising the steps of:
(a) with respect to each bit of the multiplier factor,
(a-1) judging whether the multiplier factor is a variable or a constant,
(a-2) if the multiplier factor is a variable, generating information on a circuit for selecting, based on the value of a bit of concern in the multiplier factor, either of a signal indicating the multiplicand and a signal indicating 0 and outputting the selected signal as a partial product,
(a-3) if the multiplier factor is a constant, judging whether or not the value of said bit in the multiplier factor is 1,
(a-4) if the value of said bit in the multiplier factor is 1, generating information on a circuit for outputting the signal indicating the multiplicand as a partial product;
(a-5) after executing the steps (a-1) to (a-4), generating information on a shift circuit for shifting the signal indicating the multiplicand by one bit and newly setting the output signal from said shift circuit as a signal indicating the multiplicand to be used in the steps (a-1) to (a-4),
with respect to all the bits of the multiplier factor, the steps (a-1) to (a-5) being repeatedly executed so as to generate partial products as the products of the individual bits of the multiplier factor and the multiplicand;
(b) detecting the number of said partial products;
(c) if the number of the partial products is n or more, with respect to each group consisting of n partial products obtained by evenly dividing a plurality of partial products,
(c-1) generating information on an adding circuit for receiving the n partial products in a group of concern and outputting the sum of said n partial products as m (<n) partial products and
with respect to all said plurality of partial products,
(c-2) after repeatedly executing the step (c-1), newly setting all the partial products that are the outputs of the adding circuit generated in the step (c-1) and those partial products of said plurality of partial products which were not received by the adding circuit generated in the step (c-1) as the plurality of partial products to be processed in the step (c-1),
the steps (c-1) and (c-2) being repeatedly executed until the number of the partial products newly set in the step (c-2) becomes m; and
(d) if the number of the partial products is m or less and 2 or more, generating information on a final sum circuit for receiving said number of partial products and calculating the product of the multiplier factor and the multiplicand by adding up said partial products.

6. A method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and a multiplicand, comprising the steps of:
(a) determining two constants A1 and A2 so that the difference (A1-A2) between the constants A1 and A2 equals the constant multiplier factor A;
(b) generating information on a first partial-product generating circuit for receiving the constant A1 and the multiplicand X and outputting their partial products;
(c) generating information on a second partial-product generating circuit for receiving the constant A2 and the multlplicand X and outputting their partial products;
(d) generating information on a logic NOT circuit for receiving the output signals from said second partial-product generating circuit and outputting the logic NOT signals thereof; and
(e) generating information on a circuit for receiving the output signals from said first partial-product generating circuit, the output signals from said logic NOT circuit, and a correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

7. A method of automatically designing a logic circuit according to claim 6, wherein the step (e) has the steps of:
(e-1) generating information on a partial-product adding circuit for receiving the output signals from said first partial-product generating circuit and the output signals from said logic NOT circuit and outputting the addition results as a specified number of partial products; and
(e-2) generating information on a final sum circuit for receiving the output signals from said partial-product adding circuit and the correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

8. A method of automatically designing a logic circuit according to claim 6, wherein the step (e) has the steps of:
(e-1) with respect to each group consisting of n partial products obtained by evenly dividing a plurality of partial products,
(e-1-1) generating information on an adding circuit for receiving the n partial products in a group of concern and outputting the sum of said n partial products as m (<n) partial products and
with respect to all said plurality of partial products,
(e-1-2) after repeatedly executing the step (e-1-1), newly setting all the partial products that are the outputs of the adding circuit generated in the step (e-1-1) and those partial products of said plurality of partial products which were not received by the adding circuit generated in the step (e-1-1) as the plurality of partial products to be processed in the step (e-1-1),
the steps (e-1-1) and (e-1-2) being repeatedly executed so as to generate information on a partial-product adding circuit for outputting m partial products; and
(e-2) generating information on a final sum circuit for receiving the output signals from said partial-product adding circuit and the correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

9. A method of automatically designing a logic circuit according to claim 6, wherein the step (e) has the steps of:
(e-1) judging whether the sum of the number of the bits having the value of 1 in the constant A1 and the number of the bits having the value of 1 in the constant A2 is equal to or larger than a specified number;
(e-2) if the sum of the number of the bits having the value of 1 in the constant A1 and the number of the bits having the value of 1 in the constant A2 is equal to said specified number, generating information on a final sum circuit for receiving the output signals from said first partial-product generating circuit, the output signals from said logic NOT circuit, and the correction signal, calculating the sum thereof. and outputting the sum as the product of the multiplier factor A and the multiplicand X; and
(e-3) if the sum of the number of the bits having the value of 1 in the constant A1 and the number of the bits having the value of 1 in the constant A2 is larger than said specified number,
(e-3-1) generating information on a partial-product adding circuit for receiving the output signals from said first partial -product generating circuit and the output signals from said logic NOT circuit and outputting the addition results as said specified number of partial products and
(e-3-2) generating information on a final sum circuit for receiving the output signals from said partial-product adding circuit and the correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

10. A method of automatically designing a logic circuit according to claim 6, wherein the step (e) has the steps of:
(e-1) judging whether the sum of the number of the bits having the value of 1 in the constant A1 and the number of the bits having the value of 1 in the constant A2 is 1, 2, or larger than 2;
(e-2) if the sum of the number of the bits having the value of 1 in the constant A1 and the number of the bits having the value of 1 in the constant A2 is 1, generating information on a circuit for outputting the output signals from said first partial-product generating circuit as the product of the multiplier factor A and the multiplicand X;
(e-3) if the sum of the number of the bits having the value of 1 in the constant A1 and the number of the bits having the value of 1 in the constant A2 is 2, generating information on a final sum circuit for receiving the output signals from said first partial-product generating circuit, the output signals from said logic NOT circuit, and the correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X; and
(e-4) if the sum of the number of the bits having the value of 1 in the constant A1 and the number of the bits having the value of 1 in the constant A2 is larger than 2,
(e-4-1) generating information on a partial-product adding circuit, composed of carry-save adders arranged in a tree structure, for receiving the output signals from said first partial-product generating circuit and the output signals from said logic NOT circuit and outputting the addition results as two partial products, and
(e-4-2) generating information on a final sum circuit for receiving the output signals from said partial-product adding circuit and the correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

11. A method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and a multiplicand, comprising the steps of:
(a) determining two constants A1 and A2 so that the difference (A1-A2) between the constants A1 and A2 equals the constant multiplier factor A and that the sum of the number of the bits having the value of 1 in the constant A1 and the number of the bits having the value of 1 in the constant A2 is minimized;
(b) generating information on a first partial-product generating circuit for receiving the constant A1 and the multiplicand X and outputting their partial products;
(c) generating information on a second partial-product generating circuit for receiving the constant A2 and the multiplicand X and outputting their partial products;
(d) generating information on a logic NOT circuit for receiving the output signals from said second partial-product generating circuit and outputting the logic NOT signals thereof; and
(e) generating information on a partial-product-sum circuit for receiving the output signals from said first partial-product generating circuit, the output signals from the logic NOT circuit, and a correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

12. A method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and a multiplicand, comprising the steps of:
(a) determining two constants A1 and A2 so that the difference between the constants A1 and A2 equals the constant multiplier factor A;
(b) with respect to each bit of the constant A1,
(b-1) judging whether or not the value of a bit of concern in the constant A1 is 1,
(b-2) if the value of said bit in the constant A1 is 1, generating information on a circuit for outputting a signal indicating the multiplicand X as a partial product, and
(b-3) after executing the steps (b-1) and (b-2), generating information on a first shift circuit for shifting the signal indicating the multiplicand X by one bit and newly setting the output signal from said first shift circuit as the signal indicating the multiplicand X to be used in the steps (b-1) and (b-2),
the steps (b-1) to (b-3) being repeatedly executed with respect to all the bits of the constant A1 so as to generate a first partial-product generating circuit;
(c) with respect to each bit of the constant A2,
(c-1) judging whether or not the value of a bit of concern in the constant A2 is 1,
(c-2) if the value of said bit in the constant A2 is 1, generating information on a circuit for outputting the signal indicating the multiplicand X as a partial product, and
(c-3) after executing the steps (c-1) and (c-2), generating information on a second shift circuit for shifting the signal indicating the multiplicand X by one bit and newly setting the output signal from said second shift circuit as the signal indicating the multiplicand X to be used in the steps (c-1) and (c-2),
the steps (c-1) to (c-3) being repeatedly executed with respect to all the bits of the constant A2 so as to generate a second partial-product generating circuit;
(d) generating information on a logic NOT circuit for receiving the output signals from said second partial-product generating circuit and outputting the logic NOT signals thereof; and
(e) generating information on a circuit for receiving the output signals from said first partial-product generating circuit, and the output signals from said logic NOT circuit, and a correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand.

13. A method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and a multiplicand, comprising the steps of:
(a) producing the logic NOT signal of the constant multiplier factor A from the multiplier factor A;
(b) with respect to each bit of the logic NOT signal of said multiplier factor A,
(b-1) judging whether or not the value of a bit of concern in the logic NOT signal of said multiplier factor A is 1,
(b-2) if the value of said bit in the logic NOT signal of said multiplier factor A is 1, generating information on a circuit for outputting a signal indicating the multiplicand X as a partial product, and
(b-3) after executing the steps (b-1) and (b-2), generating information on a shift circuit for shifting the signal indicating the multiplicand X by one bit and newly setting the output signal from said shift circuit as the multiplicand X to be used in the steps (b-1) and (b-2),
the steps (b-1) to (b-3) being repeatedly executed with respect to all the bits of the logic NOT signal of said multiplier factor A so as to generate information on a partial-product generating circuit;
(c) generating information on a partial-product adding circuit for receiving all the output signals from said partial-product generating circuit and the signal indicating the multiplicand X and outputting the addition results as a specified number of partial products;
(d) generating information on a logic NOT circuit for receiving the output signals from said partial-product adding circuit and outputting the logic NOT signals thereof;
(e) generating a correction signal from the multiplicand X; and
(f) generating information on a final sum circuit for receiving said correction signal and the output signals from said logic NOT circuit, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

14. A method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and a multiplicand, comprising the steps of:
(a) producing the logic NOT signal of the constant multiplier factor A from the multiplier factor A;
(b) with respect to each bit of the logic NOT signal of said multiplier factor A,
(b-1) judging whether or not the value of a bit of concern in the logic NOT signal of said multiplier factor A is 1,
(b-2) if the value of said bit in the logic NOT signal of said multiplier factor is 1, generating information on a circuit for outputting a signal indicating the multiplicand X as a partial product, and
(b-3) after executing the steps (b-1) and (b-2), generating information on a shift circuit for shifting the signal indicating the multiplicand X by one bit and newly setting the output signal from said shift circuit as the multiplicand X to be used in the steps (b-1) and (b-2),
the steps (b-1) to (b-3) being repeatedly executed with respect to all the bits of the logic NOT signal of said multiplier factor A so as to generate information on a partial-product generating circuit;
(c) with respect to each group consisting of n input signals obtained by evenly dividing a plurality of input signals composed of all the output signals from said partial-product generating circuit and the signal indicating the multiplicand X,
(c-1) generating information on an adding circuit for receiving the n input signals in a group of concern and outputting the sum of said n input signals as m (<n) signals and
with respect to all said input signals,
(c-2) after repeatedly executing the step (c-1), newly setting all the output signals from the adding circuit generated in the step (c-1) and those input signals of said plurality of input signals which were not received by the adding circuit generated in the step (c-1) as the plurality of input signals to be processed in the step (c-1),
the steps (c-1) and (c-2) being repeatedly executed so as to generate information on a partial-product adding circuit;
(d) generating information on a logic NOT circuit for receiving the output signals from said partial-product adding circuit and outputting the logic NOT signals thereof;
(e) producing a correction signal from the multiplicand X; and
(f) generating a final sum circuit for receiving said correction signal and the output signals from said logic NOT circuit, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

15. A method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and a multiplicand, comprising the steps of:
(a) determining two constants A1 and A2 so that the difference (A1-A2) between the constants A1 and A2 equals the constant multiplier factor A;
(b) judging whether or not the constant A2 is 0;
(c) if the constant A2 is 0,
(c-1) generating information on a first partial-product generating circuit for receiving the multiplier factor A1 and the multiplicand X and outputting their partial products and
(c-2) generating information on a first partial-product-sum circuit for receiving all the output signals from said first partial-product generating circuit, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X; and
(d) if the constant A2 is not 0,
(d-1) generating information on a second partial-product generating circuit for receiving the constant A1 and the multiplicand X and outputting their partial products,
(d-2) generating information on a third partial-product generating circuit for receiving the constant A2 and the multiplicand X and outputting their partial products,
(d-3) generating information on a logic NOT circuit for receiving the output signals from said third partial-product generating circuit and outputting the logic NOT signals thereof, and
(d-4) generating information on a second partial-product-sum circuit for receiving the output signals from said second partial-product generating circuit, the output signals from said logic NOT circuit, and a correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

16. A method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and the multiplicand, comprising the steps of:
(a) determining three constants A1, A2, and A3 so that the difference A1-(A2+A3) between the constant A1 and the sum of the constants A2 and A3 equals the constant multiplier factor A;
(b) judging whether or not the constant A1 is equal to the multiplier factor A and whether or not each of the constants A2 and A3 is 0;
(c) if the constant A1 is equal to the multiplier factor A,
(c-1) generating information on a first partial-product generating circuit for receiving the multiplier factor A1 and the multiplicand X and outputting their partial products and
(c-2) generating information on a first partial-product-sum circuit for receiving all the output signals from said first partial-product generating circuit, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X; and
(d) if the constant A1 is not equal to the multiplier factor A and at least either one of the constants A2 and A3 is not 0,
(d-1) generating information on a second partial-product generating circuit for receiving the constant A1 and the multiplicand X and outputting their partial products,
(d-2) generating information on a third partial-product generating circuit for receiving the constant A2 and A3 and the multiplicand X and outputting their partial products,
(d-3) generating information on a first logic NOT circuit for receiving the output signals from said third partial-product generating circuit and outputting the logic NOT signals thereof, and
(d-4) generating information on a second partial-product-sum circuit for receiving the output signals from said second partial-product generating circuit, the output signals from said first logic NOT circuit, and a first correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

17. A method of automatically designing a logic circuit according to claim 16, wherein
with respect to each bit of the constant A1, the step (c-1) has the steps of:
(c-1-1) judging whether or not the value of a bit of concern in the constant A1 is 1;
(c-1-2) if the value of said bit in the constant A1 is 1, generating information on a circuit for outputting a signal indicating the multiplicand X as a partial product; and
(c-1-3) after executing the steps (c-1-1) and (c-1-2), generating information on a first shift circuit for shifting the signal indicating the multlplicand X by one bit and newly setting the output signal from said first shift circuit as the signal indicating the multiplicand X to be used in the steps (c-1-1) and (c-1-2),
with respect to all the bits of the constant A1, the steps (c-1-1) to (c-1-3) being repeatedly executed so as to generate the first partial-product generating circuit,
with respect to each bit of the constant A1, the step (d-1) has the steps of:
(d-1-1) judging whether or not the value of the bit of concern of the constant A1 is 1;
(d-1-2) if the value of said bit in the constant A1 is 1, generating information on a circuit for outputting the signal indicating the multiplicand X as a partial product; and
(d-1-3) after executing the steps (d-1-1) and (d-1-2), generating information on a second shift circuit for shifting the signal indicating the multiplicand X by one bit and newly setting the output signal from said second shift circuit as the signal indicating the multiplicand X to be used in the steps (d-1-1) and (d-1-2),
with respect to all the bits of the constant A1, the steps (d-1-1) to (d-1-3) being repeatedly executed so as to generate the second partial-product generating circuit, and
with respect to each bit of the constants A2 and A3, the step (d-2) has the steps of:
(d-2-1) judging whether or not the value of a bit of concern in the constants A2 and A3 is 1;
(d-2-2) if the value of said bit in the constants A2 and A3 is 1, generating information on a circuit for outputting the signal indicating the multiplicand X as a partial product; and
(d-2-3) after executing the steps (d-2-1) and (d-2-2), generating information on a third shift circuit for shifting the signal indicating the multiplicand X by one bit and newly setting the output signal from said third shift circuit as the signal indicating the multiplicand X to be used in the steps (d-2-1) and (d-2-2),
with respect to all the bits of the constants A2 and A3, the steps (d-2-1) to (d-2-3) being repeatedly executed so as to generate the third partial-product generating circuit.

18. A method of automatically designing a logic circuit according to claim 16, wherein
with respect to each group consisting of n partial products which was obtained by evenly dividing a plurality of first partial products composed of the output signals from said first partial-product generating circuit, the step (c-2) has the steps of:
(c-2-1) generating information on an adding circuit for receiving the n partial products in a group of concern and outputting the sum of said n partial products as m (<n) partial products; and
with respect to all said plurality of first partial products,
(c-2-2) after repeatedly executing the step (c-2-1), newly setting all the partial products that are the outputs of the adding circuit generated in the step (c-2-1) and those partial products of said plurality of first partial products which were not received by the adding circuit generated in the step (c-2-1) as the plurality of first partial products to be processed in the step (c-2-1),
the steps (c-2-1) and (c-2-2) being repeatedly executed so as to generate information on the first partial-product-sum circuit and
with respect to each group consisting of n partial products which was obtained by evenly dividing a plurality of second partial products composed of the output signals from said second partial-product generating circuit, the output signals from said first logic NOT circuit, and the first correction signal, the step (d-4) has the steps of:
(d-4-1) generating information on an adding circuit for receiving the n partial products in a group of concern and outputting the sum of said n partial products as m (<n) partial products; and
with respect to all said plurality of second partial products,
(d-4-2) after repeatedly executing the step (d-4-1), newly setting all the partial products that are the outputs of the adding circuit generated in the step (d-4-1) and those partial products of said plurality of second partial products which were not received by the adding circuit generated in the step (d-4-1) as the plurality of second partial products to be processed in the step (d-4-1),
the steps (d-4-1) and (d-4-2) being repeatedly executed so as to generate information on the second partial-product-sum circuit.

19. A method of automatically designing a logic circuit according to claim 16, further comprising the steps of:
(e) judging whether or not the constant A2 is equal to the logic NOT of the multiplier factor A and the constant A3 is 1; and
(f) if the constant A2 is equal to the logic NOT of the multiplier A and the constant A3 is 1,
(f-1) generating information on a fourth partial-product generating circuit for receiving the constant A2 and the multiplicand X and outputting their partial products,
(f-2) generating information on a partial-product adding circuit for receiving all the output signals from said fourth partial-product generating circuit and a signal indicating the multiplicand X and outputting the addition results as partial products,
(f-3) generating information on a second logic NOT circuit for receiving the output signals from said partial-product adding circuit and outputting the logic NOT signals thereof,
(f-4) producing a second correction signal from the multiplicand X, and
(f-5) generating information on a final sum circuit for receiving said second correction signal and the output signals from said second logic NOT circuit, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

20. A method of automatically designing a logic circuit according to claim 19, wherein
with respect to each bit of the constant A1, the step (c-1) has the steps of:
(c-1-1) judging whether or not the value of a bit of concern in the constant A1 is 1;
(c-1-2) if the value of said bit in the constant A1 is 1, generating information on a circuit for outputting the signal indicating the multiplicand X as a partial product; and
(c-1-3) after executing the steps (c-1-1) and (c-1-2), generating information on a first shift circuit for shifting the signal indicating the multlplicand X by one bit and newly setting the output signal from said first shift circuit as the signal indicating the multiplicand X to be used in the steps (c-1-1) and (c-1-2),
with respect to all the bits of the constant A1, the steps (c-1-1) to (c-1-3) being repeatedly executed so as to generate the first partial-product generating circuit,
with respect to each bit of the constant A1, the step (d-1) has the steps of:
(d-1-1) judging whether or not the value of a bit of concern in the constant A1 is 1;
(d-1-2) if the value of said bit in the constant A1 is 1, generating information on a circuit for outputting the signal indicating the multiplicand X as a partial product; and
(d-1-3) after executing the steps (d-1-1) and (d-1-2), generating information on a second shift circuit for shifting the signal indicating the multiplicand X by one bit and newly setting the output signal from said second shift circuit as the signal indicating the multlplicand X to be used in the steps (d-1-1) and (d-1-2),
with respect to all the bits of the constant A1, the steps (d-1-1) to (d-1-3) being repeatedly executed so as to generate the second partial-product generating circuit, and
with respect to each bit of the constants A2 and A3, the step (d-2) has the steps of:
(d-2-1) judging whether or not the value of a bit of concern in the constants A2 and A3 is 1;
(d-2-2) if the value of said bit in the constants A2 and A3 is 1, generating information on a circuit for outputting the signal indicating the multiplicand X as a partial product;
(d-2-3) after executing the steps (d-2-1) and (d-2-2), generating information on a third shift circuit for shifting the signal indicating the multiplicand X by one bit and newly setting the output of said third shift circuit as the signal indicating the multiplicand X to be used in the steps (d-2-1) and (d-2-2),
with respect to all the bits of the constants A2 and A3, the steps (d-2-1) to (d-2-3) being repeatedly executed so as to generate the third partial-product generating circuit; and
with respect to each bit of the constant A2, the step (f-1) has the steps of:
(f-1-1) judging whether or not the value of a bit of concern in the constant A2 is 1;
(f-1-2) if the value of said bit in the constant A2 is 1, generating information on a circuit for outputting the signal indicating the multiplicand X as a partial product; and
(f-1-3) after executing the steps (f-1-1) and (f-1-2), generating information on a fourth shift circuit for shifting the signal indicating the multiplicand X by one bit and newly setting the output of said fourth shift circuit as the signal indicating the multiplicand X to be used in the steps (f-1-1) and (f-1-2),
with respect to all the bits of the constant A2, the steps (f-1-1) to (f-1-3) being repeatedly executed so as to generate the fourth partial-product generating circuit.

21. A method of automatically designing a logic circuit according to claim 19, wherein
with respect to each group consisting of n partial products which was obtained by evenly dividing a plurality of first partial products composed of the output signals from said first partial-product generating circuit, the step (c-2) has the steps of:
(c-2-1) generating information on an adding circuit for receiving the n partial products in a group of concern and outputting the sum of said n partial products as m (<n) partial products; and
with respect to all said plurality of first partial products,
(c-2-2) after repeatedly executing the step (c-2-1), newly setting all the partial products that are the outputs of the adding circuit generated in the step (c-2-1) and those partial products of said plurality of first partial products which were not received by the adding circuit generated in the step (c-2-1) as the plurality of first partial products to be processed in the step (c-2-1),
the steps (c-2-1) and (c-2-2) being repeatedly executed so as to generate information on the first partial-product-sum circuit,
with respect to each group consisting of n partial products which was obtained by evenly dividing a plurality of second partial products composed of the output signals from said second partial-product generating circuit, the output signals from said first logic NOT circuit, and the first correction signal, the step (d-4) has the steps of:
(d-4-1) generating information on an adding circuit for receiving the n partial products in a group of concern and outputting the sum of said n partial products as m (<n) partial products; and
with respect to all said plurality of second partial products,
(d-4-2) after repeatedly executing the step (d-4-1), newly setting all the partial products that are the outputs of the adding circuit generated in the step (d-4-1) and those partial products of said plurality of second partial products which were not received by the adding circuit generated in the step (d-4-1) as the plurality of second partial products to be processed in the step (d-4-1),
the steps (d-4-1) and (d-4-2) being repeatedly executed so as to generate information on the second partial-product-sum circuit, and
with respect to each group consisting of n partial products which was obtained by evenly dividing a plurality of third partial products composed of the output signals from said fourth partial-product generating circuit and the signal indicating the multiplicand X, the step (f-2) has the steps of:
(f-2-1) generating information on an adding circuit for receiving the n partial products in a group of concern and outputting the sum of said n partial products as m (<n) partial products; and
with respect to all said plurality of third partial products,
(f-2-2) after repeatedly executing the step (f-2-1), newly setting all the partial products that are the outputs of the adding circuit generated in the step (f-2-1) and those partial products of said plurality of third partial products which were not received by the adding circuit generated in the step (f-2-1) as the plurality of third partial products to be processed in the step (f-2-1),
the steps (f-2-1) and (f-2-2) being repeatedly executed so as to generate information on the partial-product adding circuit.

22. A method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplicand and a multiplier, comprising the steps of:
(a) determining three constants A1, A2, and A3 so that the difference A1-(A2+A3) between the constant A1 and the sum of the constants A2 and A3 equals the constant multiplier factor A and that the sum of the number of the bits having the value of
1 in the constant A1, the number of the bits having the value of 1 in the constant A2, and the number of the bits having the value of 1 in the constant A3 is minimized;
(b) judging whether or not the constant A1 is equal to the multiplier factor A and whether or not each of the constants A2 and A3 is 0;
(c) if the constant A1 is equal to the multiplier factor A,
(c-1) generating information on a first partial-product generating circuit for receiving the multiplier factor A1 and the multiplicand X and outputting their partial products and
(c-2) generating information on a first partial-product-sum circuit for receiving all the output signals from said first partial-product generating circuit, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X;
(d) if the constant A1 is not equal to the multiplier factor A and at least either one of the constants A2 and A3 is not 0,
(d-1) generating information on a second partial-product generating circuit for receiving the constant A1 and the multiplicand X and outputting their partial products,
(d-2) generating information on a third partial-product generating circuit for receiving the constants A2 and A3 and the multiplicand X and outputting their partial products,
(d-3) generating information on a first logic NOT circuit for receiving the output signals from said third partial-product generating circuit and outputting the logic NOT signals thereof, and
(d-4) generating information on a second partial-product-sum circuit for receiving the output signals from said second partial-product generating circuit, the output signals from said first logic NOT circuit, and a first correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

23. A method of automatically designing a logic circuit according to claim 22, wherein
with respect to each bit of the constant A1, the step (c-1) has the steps of:
(c-1-1) judging whether or not the value of a bit of concern in the constant A1 is 1;
(c-1-2) if the value of said bit in the constant A1 is 1, generating information on a circuit for outputting a signal indicating the multiplicand X as a partial product; and
(c-1-3) after executing the steps (c-1-1) and (c-1-2), generating information on a first shift circuit for shifting the signal indicating the multiplicand X by one bit and newly setting the output signal from said first shift circuit as the multiplicand X to be used in the steps (c-1-1) and (c-1-2),
with respect to all the bits of the constant A1, the steps (c-1-1) to (c-1-3) being repeatedly executed so as to generate the first partial-product generating circuit, and
with respect to each bit of the constant A1, the step (d-1) has the steps of:
(d-1-1) judging whether or not the value of a bit of concern in the constant A1 is 1;
(d-1-2) if the value of said bit in the constant A1 is 1, generating information on a circuit for outputting the signal indicating the multiplicand X as a partial product; and
(d-1-3) after executing the steps (d-1-1) and (d-1-2), generating information on a second shift circuit for shifting the signal indicating the multiplicand X by one bit and newly setting the output signal from said second shift circuit as the multiplicand X to be used in the steps (d-1-1) and (d-1-2),
with respect to all the bits of the constant A1, the steps (d-1-1) to (d-1-3) being repeatedly executed so as to generate the second partial-product generating circuit, and
with respect to each bit of the constants A2 and A3, the step (d-2) has the steps of:
(d-2-1) judging whether or not the value of a bit of concern in the constants A2 and A3 is 1;
(d-2-2) if the value of said bit in the constants A2 and A3 is 1, generating information on a circuit for outputting the signal indicating the multiplicand X as a partial product;
(d-2-3) after executing the steps (d-2-1) and (d-2-2), generating information on a third shift circuit for shifting the signal indicating the multiplicand X by one bit and newly setting the output signal from said third shift circuit as the multiplicand X to be used in the steps (d-2-1) and (d-2-2),
with respect to all the bits of the constants A2 and A3, the steps (d-2-1) to (d-2-3) being repeatedly executed so as to generate the third partial-product generating circuit.

24. A method of automatically designing a logic circuit according to claim 22, wherein
with respect to each group consisting of n partial products which was obtained by evenly dividing a plurality of first partial products composed of the output signals from said-first partial-product generating circuit, the step (c-2) has the steps of:
(c-2-1) generating information on an adding circuit for receiving the n partial products in a group of concern and outputting the sum of said n partial products as m (<n) partial products; and
with respect to all said plurality of first partial products,
(c-2-2) after repeatedly executing the step (c-2-1), newly setting all the partial products that are the outputs of the adding circuit generated in the step (c-2-1) and those partial products of said plurality of first partial products which were not received by the adding circuit generated in the step (c-2-1) as the plurality of first partial products to be processed in the step (c-2-1),
the steps (c-2-1) and (c-2-2) being repeatedly executed so as to generate information on the first partial-product-sum circuit, and
with respect to each group consisting of n partial products which was obtained by evenly dividing a plurality of second partial products composed of the output signals from said second partial-product generating circuit, the output signals from said first logic NOT circuit, and the first correction signal, the step (d-4) has the steps of:
(d-4-1) generating information on an adding circuit for receiving the n partial products in a group of concern and outputting the sum of said n partial products as m (<n) partial products; and
with respect to all said plurality of second partial products,
(d-4-2) after repeatedly executing the step (d-4-1), newly setting all the partial products that are the outputs of the adding circuit generated in the step (d-4-1) and those partial products of said plurality of second partial products which were not received by the adding circuit generated in the step (d-4-1) as the plurality of second partial products to be processed in the step (d-4-1),
the steps (d-4-1) and (d-4-2) being repeatedly executed so as to generate information on the second partial-product-sum circuit.

25. A method of automatically designing a logic circuit according to claim 22, further comprising the steps of:
(e) judging whether or not the constant A2 is equal to the logic NOT of the multiplier factor A and the constant A3 is 1; and
(f) if the constant A2 is equal to the logic NOT of the multiplier factor A and the constant A3 is 1,
(f-1) generating information on a fourth partial-product generating circuit for receiving the constant A2 and the multiplicand X and outputting their partial products,
(f-2) generating information on a partial-product adding circuit for receiving all the output signals from said fourth partial-product generating circuit and a signal indicating the multiplicand X and outputting the addition results as partial products,
(f-3) generating information on a second logic NOT circuit for receiving the output signals from said partial-product adding circuit and outputting the logic NOT signals thereof;
(f-4) producing a second correction signal from the multiplicand X, and
(f-5) receiving said second correction signal and the output signals from said second logic NOT circuit, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

26. A method of automatically designing a logic circuit according to claim 25, wherein
with respect to each bit of the constant A1, the step (c-1) has the steps of:
(c-1-1) judging whether or not the value of a bit of concern in the constant A1 is 1;
(c-1-2) if the value of said bit in the constant A1 is 1, generating information on a circuit for outputting a signal indicating the multiplicand X as a partial product; and
(c-1-3) after executing the steps (c-1-1) and (c-1-2), generating information on a first shift circuit for shifting the signal indicating the multlplicand X by one bit and newly setting the output of said first shift circuit as the multiplicand X to be used in the steps (c-1-1) and (c-1-2),
with respect to all the bits of the constant A1, the steps (c-1-1) to (c-1-3) being repeatedly executed so as to generate the first partial-product generating circuit,
with respect to each bit of the constant A1, the step (d-1) has the steps of:
(d-1-1) judging whether or not the value of a bit of concern in the constant A1 is 1;
(d-1-2) if the value of said bit in the constant A1 is 1, generating information on a circuit for outputting the signal indicating the multiplicand X as a partial product; and
(d-1-3) after executing the steps (d-1-1) and (d-1-2), generating information on a second shift circuit for shifting the signal indicating the multiplicand X by one bit and newly setting the output of said second shift circuit as the multiplicand X to be used in the steps (d-1-1) and (d-1-2),
with respect to all the bits of the constant A1, the steps (d-1-1) to (d-1-3) being repeatedly executed so as to generate the second partial-product generating circuit, and
with respect to each bit of the constants A2 and A3, the step (d-2) has the steps of:
(d-2-1) judging whether or not the value of a bit of concern in the constants A2 and A3 is 1;
(d-2-2) if the value of said bit in the constants A2 and A3 is 1, generating information on a circuit for outputting the signal indicating the multiplicand X as a partial product;
(d-2-3) after executing the steps (d-2-1) and (d-2-2), generating information on a third shift circuit for shifting the signal indicating the multiplicand X by one bit and newly setting the output signals from said third shift circuit as the multiplicand X to be used in the steps (d-2-1) and (d-2-2),
with respect to all the bits of the constants A2 and A3, the steps (d-2-1) to (d-2-3) being repeatedly executed so as to generate the third partial-product generating circuit; and
with respect to each bit of the constant A2, the step (f-1) has the steps of:
(f-1-1) judging whether or not the value of a bit of concern in the constant A2 is 1;
(f-1-2) if the value of a bit of concern in the constant A2 is 1, generating information on a circuit for outputting the signal indicating the multiplicand X as a partial product; and
(f-1-3) after executing the steps (f-1-1) and (f-1-2), generating information on a fourth shift circuit for shifting the signal indicating the multiplicand X by one bit and newly setting the output signal from said fourth shift circuit as the multiplicand X to be used in the steps (f-1-1) and (f-1-2),
with respect to all the bits of the constant A2, the steps (f-1-1) to (f-1-3) being repeatedly executed so as to generate the fourth partial-product generating circuit.

27. A method of automatically designing a logic circuit according to claim 25, wherein
with respect to each group consisting of n partial products which was obtained by evenly dividing a plurality of first partial products composed of the output signals from said first partial-product generating circuit, the step (c-2) has the steps of:
(c-2-1) generating information on an adding circuit for receiving the n partial products in a group of concern and outputting the sum of said n partial products as m (<n) partial products; and
with respect to all said plurality of first partial products,
(c-2-2) after repeatedly executing the step (c-2-1), newly setting all the partial products that are the outputs of the adding circuit generated in the step (c-2-1) and those partial products of said plurality of first partial products which were not received by the adding circuit generated in the step (c-2-1) as the plurality of first partial products to be processed in the step (c-2-1),
the steps (c-2-1) and (c-2-2) being repeatedly executed so as to generate information on the first partial-product-sum circuit,
with respect to each group consisting of n partial products which was obtained by evenly dividing a plurality of second partial products composed of the output signals from said second partial-product generating circuit, the output signals from said first logic NOT circuit, and the first correction signal, the step (d-4) has the steps of:
(d-4-1) generating information on an adding circuit for receiving the n partial products in a group of concern and outputting the sum of said n partial products as m (<n) partial products; and
with respect to all said plurality of second partial products,
(d-4-2) after repeatedly executing the step (d-4-1), newly setting all the partial products that are the outputs of the adding circuit generated in the step (d-4-1) and those partial products of said plurality of second partial products which were not received by the adding circuit generated in the step (d-4-1) as the plurality of second partial products to be processed in the step (d-4-1),
the steps (d-4-1) and (d-4-2) being repeatedly executed so as to generate information on the second partial-product-sum circuit, and
with respect to each group consisting of n partial products which was obtained by evenly dividing a plurality of third partial products composed of the output signals from said fourth partial-product generating circuit and the signal indicating the multiplicand X, the step (f-2) has the steps of:
(f-2-1) generating information on an adding circuit for receiving the n partial products in a group of concern and outputting the sum of said n partial products as m (<n) partial products; and
with respect to all said plurality of third partial products,
(f-2-2) after repeatedly executing the step (f-2-1), newly setting all the partial products that are the outputs of the adding circuit generated in the step (f-2-1) and those partial products of said plurality of third partial products which were not received by the adding circuit generated in the step (f-2-1) as the plurality of third partial products to be processed in the step (f-2-1),
the steps (f-2-1) and (f-2-2) being repeatedly executed so as to generate information on the partial-product adding circuit.

28. A method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and a multiplicand, comprising the steps of:
(a) determining two constants A1 and A2 so that the difference (A1-A2) between the constants A1 and A2 equals the constant multiplier factor A;
(b) judging which is the smaller of the number of the bits having the value of 1 in the multiplier factor A and the sum of the numbers of the bits having the value of 1 in the constants A1 and A2;
(c) if the number of the bits having the value of 1 in the multiplier factor A is the smaller,
(c-1) generating information on a first partial-product generating circuit for receiving the multiplier factor A and the multiplicand X and outputting the products of the individual bits in the multiplier factor A and the multiplicand X as partial products, and
(c-2) generating information on a first partial-product-sum circuit for receiving all the output signals from said first partial-product generating circuit, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X; and
(d) if the sum of the numbers of the bits having the value of 1 in the constants A1 and A2 is the smaller,
(d-1) generating information on a second partial-product generating circuit for receiving the constant A1 and the multiplicand X and outputting their partial products,
(d-2) generating information on a third partial-product generating circuit for receiving the constant A2 and the multiplicand X and outputting their partial products,
(d-3) generating information on a logic NOT circuit for receiving the output signals from said third partial-product generating circuit and outputting the logic NOT signals thereof, and
(d-4) generating information on a second partial-product-sum circuit for receiving the output signals from said second partial-product generating circuit, the output signals from said logic NOT circuit, and a correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

29. A system for automatically designing a logic circuit, comprising:
an input means for receiving various information;
a storage means for storing the various information being processed;
a processing means for producing information on the logic circuit for calculating the product of a multiplier factor and the multiplicand inputted from said input means; and
an output means for outputting the information on the logic circuit produced by said processing means, wherein
said processing means executes the steps of:
(a) determining two constants A1 and A2 so that the difference (A1-A2) between the constants A1 and A2 equals the constant multiplier factor A;
(b) judging which is the smaller of the number of the bits having the value of 1 in the multiplier factor A and the sum of the numbers of the bits having the value of 1 in the constants A1 and A2;
(c) if the number of the bits having the value of 1 is the smaller,
(c-1) generating information on a first partial-product generating circuit for receiving the multiplier factor A and the multiplicand X and outputting the products of the individual bits in the multiplier factor A and the multiplicand X as partial products, and
(c-2) generating information on a first partial-product-sum circuit for receiving all the output signals from said first partial-product generating circuit, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X; and
(d) if the sum of the numbers of the bits having the value of 1 in the constants A1 and A2 is the smaller,
(d-1) generating information on a second partial-product generating circuit for receiving the constant A1 and the multiplicand X and outputting their partial products,
(d-2) generating information on a third partial-product generating circuit for receiving the constant A2 and the multiplicand X and outputting their partial products,
(d-3) generating information on a logic NOT circuit for receiving the output signals from said third partial-product generating circuit and outputting the logic NOT signals thereof, and
(d-4) generating information on a second partial-product-sum circuit for receiving the output signals from said second partial-product generating circuit, the output signals from said logic NOT circuit, and a correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

30. A system for automatically designing a logic circuit according to claim 29, wherein
the first partial-product generating circuit generated in the step (c-2) to be executed by said processing means has:
a first partial-product adding circuit for adding up inputted signals and outputting the addition results as partial products; and
a first final-sum circuit for receiving at least the output signals from said first partial-product adding circuit, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X and
the second partial-product generating circuit generated in the step (d-2) to be executed by said processing means has:
a second partial-product adding circuit for adding up inputted signals and outputting the addition results as partial products; and
a second final-sum circuit for receiving at least the output signals from said second partial-product adding circuit, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

31. A system for automatically designing a logic circuit, comprising:
an input means for receiving various information;
a storage means for storing the various information being processed;
a processing means for producing information on the logic circuit for calculating the product of a multiplier factor and multiplicand inputted from said input means; and
an output means for outputting the information on the logic circuit produced by said processing means, wherein
said processing means executes the steps of:
(a) determining two constants A1 and A2 so that the difference (A1-A2) between the constants A1 and A2 equals the constant multiplier factor A;
(b) judging which is the smallest of the number of the bits having the value of 1 in the multiplier factor A, the sum of the numbers of the bits having the value of 1 in the constants A1 and A2, and the sum of the number of the bits having the value of 0 in the multiplier factor A and 2;
(c) if the number of the bits having the value of 1 in the multiplier factor A is the smallest,
(c-1) generating information on a first partial-product generating circuit for receiving the multiplier factor A and the multiplicand X and outputting the products of the individual bits in the multiplier factor A and the multiplicand X as partial products, and
(c-2) generating information on a first partial-product-sum circuit for receiving all the output signals from said first partial-product generating circuit, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X;
(d) if the sum of the numbers of the bits having the value of 1 in the constants A1 and A2 is the smallest,
(d-1) generating information on a second partial-product generating circuit for receiving the constant A1 and the multiplicand X and outputting their partial products,
(d-2) generating information on a third partial-product generating circuit for receiving the constant A2 and the multiplicand X and outputting their partial products,
(d-3) generating information on a first logic NOT circuit for receiving the output signals from said third partial-product generating circuit and outputting the logic NOT signals thereof, and
(d-4) generating information on a second partial-product-sum circuit for receiving the output signals from said second partial-product generating circuit, the output signals from said first logic NOT circuit, and a first correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X; and
(e) if the sum of the number of the bits having the value of 0 in the multiplier factor A and 2 is the smallest,
(e-1) generating, from the multiplier factor A, the logic NOT signal thereof,
(e-2) generating information on a fourth partial-product generating circuit for receiving said logic NOT signal of the multiplier factor A and the multlplicand X and outputting the products of the individual bits in said logic NOT signal of the multiplier factor A and the multiplicand X as partial products;
(e-3) generating information on a partial-product adding circuit for receiving all the output signals from said fourth partial-product generating circuit and a signal indicating the multiplicand X and outputting the addition results as partial products;
(e-4) generating information on a second logic NOT circuit for receiving the output signals from said partial-product adding circuit and outputting the logic NOT signals thereof;
(e-5) producing a second correction signal from the multiplicand X, and
(e-6) generating information on a final sum circuit for receiving said second correction signal and the output signals from said second logic NOT circuit, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

32. An apparatus for automatically designing a logic circuit having the multiplying function for calculating the product of a multiplier factor and a multiplicand, comprising:
a first means for receiving, from the outside, various information including information on the multiplier factor A, information on the multiplicand X, and information on the product P;
a second means for receiving the information on the multiplier factor A and determining information on a number A1 and information on a constant A2 so that the difference (A1-A2) between the number A1 and constant A2 equals the multiplier factor A;
a third means for receiving the information on the number A1 and the information on the multiplicand X and generating information on a first partial-product generating circuit which receives the number A1 and the multiplicand X and outputs, as partial products, the products of the individual bits the value of which is not 0 in the multiplier factor A and the multiplicand X;
a fourth means for receiving the information on the constant A2 and the information on the multiplicand X and generating information on a second partial-product generating circuit which receives the constant A2 and the multiplicand X and outputs, as partial products, the products of the individual bits the value of which is not 0 in the constant A2 and the multiplicand X;
a fifth means for receiving information on the output signals from said second partial-product generating circuit and generating information on a logic NOT circuit which receives the output signals from said second partial-product generating circuit and outputs the logic NOT signals thereof;
a sixth means for detecting the total number of the output signals from said first partial-product generating circuit and from the logic NOT circuit;
a seventh means for receiving information on the output signals from said first partial-product generating circuit and information on the output signals from the logic NOT circuit and generating information on a partial-product adding circuit which receives all the output signals from said first partial-product generating circuit and from the logic NOT circuit and outputs the addition results as partial products;
an eighth means for receiving either the information on the output signals from said logic NOT circuit or the information on the output signals from the second partial-product generating circuit and generating a correction signal based on the number of the output signals indicated by said received information; and
a ninth means for receiving information on the output signals from said partial-product adding circuit, information on said correction signal, and the information on the product P and generating information on a partial-product-sum generating circuit which calculates the sum of the output signals from said partial-product adding circuit and said correction signal, sets said sum to the product P as the product of the multiplier factor A and the multiplicand X, and outputs said product P.

33. An apparatus for automatically designing a logic circuit according to claim 32, wherein said seventh means generates information on a partial-product adding circuit consisting of adders arranged in a tree structure.

34. An apparatus for automatically designing a logic circuit having the multiplying function for calculating the product of a multiplier factor and a multiplicand, comprising:
a first means for receiving, from the outside, various information including information on the multiplier factor A, information on the multiplicand X, and information on the product P;
a second means for receiving the information on the multiplier factor A and determining information on a number A1 and information on a constant A2 so that the difference (A1-A2) between the number A1 and constant A2 equals the multiplier factor A;
a third means for receiving the information on the number A1 and the information on the multiplicand X and generating information on a first partial-product generating circuit which receives the number A1 and the multiplicand X and outputs, as partial products, the products of the individual bits the value of which is not 0 in the number A1 and the multiplicand X;
a fourth means for receiving the information on the constant A2 and the information on the multiplicand X and generating information on a second partial-product generating circuit which receives the constant A2 and the multiplicand X and outputs, as partial products, the products of the individual bits the value of which is not 0 in the constant A2 and the multiplicand X;
a fifth means for receiving information on the output signals from said second partial-product generating circuit and generating information on a logic NOT circuit which receives the output signals from said second partial-product generating circuit and outputs the logic NOT signals thereof;
a sixth means for detecting the total number of the output signals from said first partial-product generating circuit and from the logic NOT circuit;
a seventh means for receiving either information on the output signals from said logic NOT circuit or information on the output signals from the second partial-product generating circuit and generating a correction signal based on the number of the output signals indicated by said received information; and
an eighth means for receiving the information on the output signals from said first partial-product generating circuit, the information on the output signals from the logic NOT circuit, and information on said correction signal and generating information on a partial-product adding circuit which receives all the output signals from said first partial-product generating circuit and from the logic NOT circuit and said correction signal and outputs the addition results as partial products; and
a ninth means for receiving information on the output signals from said partial-product adding circuit and the information on the product P and generating information on a partial-product-sum generating circuit which calculates the sum of the output signals from said partial-product adding circuit, sets said sum to the product P as the product of the multiplier factor A and the multiplicand X, and outputs said product P.

35. An apparatus for automatically designing a logic circuit according to claim 34, wherein said eighth means generates information on a partial-product adding circuit consisting of adders arranged in a tree structure.

36. An apparatus for automatically designing a logic circuit having the multiplying function for calculating the product of a multiplier factor and a multiplicand, comprising:
a first means for receiving, from the outside, various information including information on the multiplier factor A, information on the multiplicand X, and information on the product P;
a second means for receiving the information on the multiplier factor A and producing the logic NOT signal of the multiplier factor A;
a third means for receiving information on said logic NOT signal of the multiplier factor A and the information on the multiplicand X and generating information on a partial-product generating circuit which receives said logic NOT signal of the multiplier factor A and the multiplicand X and outputs, as partial products, the products of the individual bits the value of which is not 0 in said logic NOT signal of the multiplier factor A and the multiplicand X;
a fourth means for receiving information on the partial products outputted from said partial-product generating circuit and the information on the multiplicand X and generating information on a partial-product adding circuit which receives all the partial products outputted from said partial-product generating circuit and the multiplicand X and outputs the addition results as partial products;
a fifth means for receiving information on the output signals from said partial-product adding circuit and generating information on a logic NOT circuit which receives the output signals from said partial-product adding circuit and outputs the logic NOT signals thereof;
a sixth means for receiving the information on the multiplicand X and generating a correction signal from the multiplicand X; and
a seventh means for receiving information on said correction signal, the information on the output signals from said partial-product adding circuit, and the information on the product P and generating information on a partial-product-sum circuit which calculates the sum of said correction signal and the output signals from said partial-product adding circuit, sets said sum to the product P as the product of the multiplier factor A and the multiplicand X, and outputs said product P.

37. An apparatus for automatically designing a logic circuit according to claim 36, wherein said fourth means generates information on a partial-product adding circuit consisting of adders arranged in a tree structure.

38. An apparatus for automatically designing a logic circuit having the multiplying function for calculating the product of a multiplier factor and a multiplicand, comprising:
a first means for receiving from the outside various information including information on the multiplier factor A, information on the multiplicand X, and information on the product P;
a second means for receiving the information on the multiplier factor A and the information on the multiplicand X and generating information on a partial-product generating circuit which receives the multiplier factor A and the multiplicand X and outputs, as partial products, the products of the individual bits the value of which is not 0 in the multiplier factor A and the multiplicand X;
a third means for detecting the number of the output signals from said partial-product generating circuit;
a fourth means for receiving information on the output signals from said partial-product generating circuit and generating information on a partial-product adding circuit which receives all the output signals from said partial-product generating circuit and outputs the addition results as partial products; and
a fifth means for receiving information on the output signals from said partial-product adding circuit and the information on the product P and generating information on a partial-product-sum circuit which receives all the output signals from said partial-product adding circuit, calculates the sum thereof, sets said sum to the product P as the product of the multiplier factor A and the multiplicand X, and outputs said product P.

39. An apparatus for automatically designing a logic circuit according to claim 38, wherein said fourth means generates information on a partial-product adding circuit consisting of adders arranged in a tree structure.

40. A multiplier for outputting the product of a multiplier factor A, which satisfies A=A1-A2 with respect the constants A1 and A2, and a multiplicand X, comprising:
a first partial-product generating means for receiving the constant A1 and the multiplicand X and outputting partial products only with respect to the bits having the value of 1 in the constant A1;
a second partial-product generating means for receiving the constant A2 and the multiplicand X and outputting partial products only with respect to the bits having the value of 1 in the constant A2;
a logic NOT means for receiving the output signals from said second partial-product generating means and outputting the logic NOT signals thereof; and
a partial-product-sum means for receiving the output signals from said first partial-product generating means, the output signals from said logic NOT means, and a correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

41. A multiplier according to claim 40, wherein said partial-product-sum means has:
a partial-product adding means for receiving the output signals from said first partial-product generating means and the output signals from said logic NOT means, adding up the output signals from said first partial-product generating means and the output signals from said logic NOT means by using a single-stage or multi-stage adding means, and outputting the addition results as partial products; and
a final sum means for receiving the output signals from said partial-product adding means and the correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

42. A multiplier according to claim 41, wherein said adding means includes a carry-save adder.

43. A multiplier for outputting the product of a multiplier factor A and a multiplicand X, comprising:
a partial-product generating means for receiving the logic NOT signal of the multiplier factor A and the multiplicand X and outputting partial products only with respect to the bits having the value of 1 in the logic NOT signal of said multiplier factor A;
a partial-product adding means for receiving the output signals from said partial-product generating means and the multiplicand X, adding up the output signals from said partial-product generating means and the multiplicand X by using a single-stage or multi-stage adding means, and outputting the addition results as partial products;
a logic NOT means for receiving the output signals from said partial-product adding means and outputting the logic NOT signals thereof; and
a partial-product-sum means for receiving the output signals from said logic NOT means and a correction signal which can be generated from the multiplicand X, calculating the sum of the output signals from said logic NOT means and said correction signal, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

44. A multiplier according to claim 43, wherein said adding means includes a carry-save adder.
Description
BACKGROUND OF THE INVENTION

The present invention relates to a method, system, and apparatus for automatically designing a logic circuit, particularly a multiplier or a logic circuit including a multiplier, and to a multiplier.

Conventional multipliers for performing multiplication with digital information are often used not only as single, independent LSIs but also as elements to be mounted in such LSIs as DSP (digital signal processor). However, as the bit width is increased in multiplication and their applications are more diversified, multipliers of this type are required to have reduced circuit size and chip area as well as to operate at higher speed. To meet the requirements, circuit systems using various multiplication methods have been proposed.

For example, a multiplication method using the Booth's 2-bit recode system, which is one of the highest-speed multiplication methods, is disclosed in "Nikkei Electronics" (May 29, pp.76-89(1978)). The multiplication method uses the following algorithm in order to increase the speed of multiplication.

If an n-bit multiplicand X is to be multiplied by an m-bit multiplier factor Y, e.g., the multiplier factor Y is represented by two's complements as follows: ##EQU1## where ym=ys, q=m/2 if m is an even number or q=(m-1)/2 if m is an odd number, and y0=0 (y is a value given for convenience).

Hence, the product P of X and Y becomes ##EQU2##

Here, since the values of y.sub.2i, y.sub.2i+1, and y.sub.2i+2 are 0 or 1, (y.sub.2i +y.sub.2i+1 -2y.sub.2i+2) becomes 0, .+-.1, or .+-.2, so that each of their partial products becomes a value obtained by multiplying 0, .+-.X, or .+-.2X by
2.sup.2i.

TABLE 1 ______________________________________ y.sub.2i+2 y.sub.2i+1 y.sub.2i (y.sub.2i + y.sub.2i+1 - 2y.sub.2i+2) ______________________________________ 0 0 0 0 0 0 1 +1 0 1 0 +1 0 1 1 +2 1 0 0 -2 1 0 1 -1 1 1 0 -1 1 1 1 0 ______________________________________

Here, a circuit for generating the partial products can be composed of a shifter primarily for shifting the multiplicand .+-.X by one bit till it is doubled and a shifter for shifting a mantissa (0, .+-.X or .+-.2X) by two bits till it is raised to the power of 2.sup.2i (weighing).

As for the number of logic stages in a circuit for calculating the total sum of the partial products, since the number of the partial products becomes q=m/2 (m is an even number) or q=(m-1)/2 (m is an odd number), it becomes approximately log.sub.2 m-1 (m is an even number) or log.sub.2 (m-1)-1 (m is an odd number) when a 2-input adder is connected so as to form a binary tree.

As an example of high-speed multipliers not using the Booth's 2-bit recode system, Japanese Patent Publication no. 03-017737 discloses a multiplier using redundant binary code.

With the multiplier mentioned above, when the multiplier factor is composed of 24 bits, the number of its partial products becomes 12 and the number of its logic stages becomes 4.

On the other hand, the increase in multiplication speed and the decrease in circuit size have been pursued not only by improving the performance of such a multiplication algorithm as mentioned above, but also by optimizing the circuit on the level of logic elements.

In recent years, multipliers and logic circuits containing multipliers are mostly designed by using automatic designing systems. Such a system is intended to eliminate a redundant portion of the circuit or to perform other operations by replacing a part of the circuit with an equivalent circuit having a smaller number of logic elements and logic stages in the case of, e.g., expanding circuit information on the level of logic elements to circuit information on the level of mounted elements, which are actually mounted in a chip.

If functional description information, which represents a function requested on the circuit in a hardware description language or the like, is inputted to such an automatic designing system, the system converts it to functional circuit information in an internal representation form, which represents a circuit composed of virtual functional elements whose functions are primarily and solely defined. Then, the resulting functional circuit information is further converted to logic circuit information which represents a circuit composed of real logic circuits, followed by the generation of mounted circuit information which represents a circuit to which real elements, mounted by specified technology, are allotted.

In the case where the function represented by the above functional description information includes multiplication, if a versatile multiplier having a specified bit width (e.g., 4, 8, 17, or 32 bits) has previously been in a library as a hardware macro and hence is available, for example, the versatile multiplier is allotted to the logic circuit. If a multiplier which is not in the library is required, a logic circuit constituting a shift-and-add multiplier or the like is newly generated. If either of the multiplier factor or multiplicand is a constant and the value thereof is a certain power-of-2 number, a circuit using a shifter is normally generated.

If the multiplier factor is a constant the value of which is not a power-of-2 number, however, the values of all the bits of a partial product that corresponds to a bit having the value of 0 in the multiplier factor become 0, so that signals from a circuit for generating or adding up such partial products disadvantageously remain in the same state.

To solve the problem, conventional automatic designing apparatus have adopted a method in which a multiplying circuit using variables as its multiplier factor and multiplicand and a circuit for generating a constant are generated before the circuit is optimized on the level of logic elements as mentioned above, thereby accomplishing the deletion of logic elements which generate signals remaining in the same state.

With the conventional automatic designing systems, however, the optimization of the circuit on the level of logic elements is localized, for the replacement by an equivalent circuit having a smaller number of logic elements and logic stages is limited to portions of the circuit that coincide with specific patterns which were preliminarily set. If such optimization is performed in the case where the multiplier factor or multiplicand is a constant, a circuit having the minimum number of logic elements and the like cannot necessarily be obtained. In particular, when carry-save adders are connected in a tree structure so as to add up partial products, the resulting tree is normally ill-balanced if the portion associated with a circuit for adding up the partial products in which the values of all the bits are 0 is omitted. Therefore, it is difficult to minimize the number of logic elements and the number of logic stages by partially replacing the circuit. Moreover, the conventional automatic designing apparatus were designed without any consideration of increasing the number of particular products in which the values of all the bits are 0.

SUMMARY OF THE INVENTION

The present invention has been achieved in view of the foregoing. It is therefore an object of the present invention to provide, in the case of generating a multiplier for performing multiplication by using a constant as its multiplier factor or multiplicand and a logic circuit including such a multiplier, a method, system, and apparatus for automatically designing a logic circuit whereby a circuit having a smaller number of logic elements and logic stages can be generated and to provide a high-speed multiplier which performs multiplication by using a constant as its multiplier factor or multiplicand and which has a smaller number of logic elements and logic stages, appropriately for large-scale integration.

To attain the above object, a method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and a multiplicand comprises the steps of: with respect to each bit of the multiplier factor, (a) judging whether the multiplier factor is a variable or a constant; (b) if the multiplier factor is a variable, generating information on a circuit for selecting, based on the value of a bit of concern in the multiplier factor, either of a signal indicating the multiplicand and a signal indicating 0 and outputting the selected signal as a partial product; (c) if the multiplier factor is a constant, judging whether or not the value of the bit in the multiplier factor is
1; (d) if the value of the bit in the multiplier factor is 1, generating information on a circuit for outputting the signal indicating the multiplicand as a partial product; and (e) after executing the steps (a) to (d), generating information on a shift circuit for shifting the signal indicating the multiplicand by one bit and newly setting the output signal from the shift circuit as a signal indicating the multiplicand to be used in the steps (a) to (d), the steps (a) to (e) being repeatedly executed for all the bits of the multiplier factor.

With the above structure, if the multiplier factor is a constant in the stage of designing a logic circuit with the multiplying function, the circuit for calculating, as a partial product, the product of a bit having the value of 1 in the multiplier factor and the multiplicand is solely generated, while the circuit for calculating a partial product with respect to a bit having the value of 0 in the multiplier factor is not generated. As a result, the number of the circuits for calculating partial products in the logic circuit to be generated can be reduced, while the area of the circuits for adding up partial products can be reduced. Consequently, the area of the logic circuit can be reduced and higher-speed calculation can easily be performed.

To attain the above object, a method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and a multiplicand comprises the steps of: with respect to each group consisting of n partial products obtained by evenly dividing a plurality of partial products which are the products of the individual bits of the multiplier factor and the multiplicand, (a) generating information on an adding circuit for receiving the n partial products in a group of concern and outputting the sum of the n partial products in the above group as m (<n) partial products; and with respect to all the plurality of partial products, (b) after repeatedly executing the step (a), newly setting all the partial products that are the outputs of the adding circuit generated in the step (a) and those partial products of the plurality of partial products which were not received by the adding circuit generated in the step (a) as the plurality of partial products to be processed in the step (a), the steps (a) and (b) being repeatedly executed.

With the above structure, the circuit for adding up partial products can be generated by arranging adders with less carry propagation in a tree structure in the stage of designing a logic circuit with the multiplying function. Consequently, in the resulting logic circuit, the number of stages for adding up products can be reduced and carry is not propagated in individual addition, thereby implementing multiplication at a higher speed.

To attain the above object, a method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and a multiplicand comprises the steps of: (a) determining two constants A1 and A2 so that the difference (A1-A2) between the constants A1 and A2 equals the constant multiplier factor A; (b) generating information on a first partial-product generating circuit for receiving the constant A1 and the multiplicand X and outputting their partial products; (c) generating information on a second partial-product generating circuit for receiving the constant A2 and the multlplicand X and outputting their partial products; (d) generating information on a logic NOT circuit for receiving the output signals from the second partial-product generating circuit and outputting the logic NOT signals thereof; and (e) generating information on a circuit for receiving the output signals from the first partial-product generating circuit, the output signals from the logic NOT circuit, and a correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

A method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and the multiplicand comprises the steps of: (a) determining three constants A1, A2, and A3 so that the difference A1-(A2+A3) between the constant A1 and the sum of the constants A2 and A3 equals the constant multiplier factor A; (b) Judging whether or not the constant A1 is equal to the multiplier factor A and whether or not each of the constants A2 and A3 is 0; (c) if the constant A1 is equal to the multiplier factor A, (c-1) generating information on a first partial-product generating circuit for receiving the multiplier factor A1 and the multiplicand X and outputting their partial products and (c-2) generating information on a first partial-product-sum circuit for receiving all the output signals from the first partial-product generating circuit, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X; and (d) if the constant A1 is not equal to the multiplier factor A and at least either one of the constants A2 and A3 is not 0, (d-1) generating information on a second partial-product generating circuit for receiving the constant A1
and the multiplicand X and outputting their partial products, (d-2) generating information on a third partial-product generating circuit for receiving the constant A2 and A3 and the multiplicand X and outputting their partial products, (d-3) generating information on a first logic NOT circuit for receiving the output signals from the third partial-product generating circuit and outputting the logic NOT signals thereof, and (d-4) generating information on a second partial-product-sum circuit for receiving the output signals from the second partial-product generating circuit, the output signals from the first logic NOT circuit, and a first correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

With the above structure, in the case where the multiplier factor A has a large number of bits the value of which is 1 in the stage of designing a logic circuit with the multiplying function, the multiplier factor A is divided into the constants A1 and A2 which satisfy A=A1-A2 (or the multiplier factor A is divided into the constants A1, A2, and A3 which satisfy A=A1-(A2+A3)), so that it becomes possible to keep the total number of the bits having the value of 1 in the constants A1 and A2 (or in the constants A1, A2, and A3) smaller than the number of the bits having the value of 1 in the multiplier factor A. Therefore, the number of partial products in the above logic circuit can be reduced.

To attain the above object, a method of automatically designing a logic circuit for generating information on the logic circuit for calculating the product of a multiplier factor and a multiplicand comprises the steps of: (a) producing the logic NOT signal of the constant multiplier factor A from the multiplier factor A; (b) with respect to each bit of the logic NOT signal of the multiplier factor A, (b-1) judging whether or not the value of a bit of concern in the logic NOT signal of the multiplier factor A is 1, (b-2) if the value of the bit in the logic NOT signal of the multiplier factor A is 1, generating information on a circuit for outputting a signal indicating the multiplicand X as a partial product, and (b-3) after executing the steps (b-1) and (b-2), generating information on a shift circuit for shifting the signal indicating the multiplicand X by one bit and newly setting the output signal from the shift circuit as the multiplicand X to be used in the steps (b-1) and (b-2), the steps (b-1) to (b-3) being repeatedly executed with respect to all the bits of the logic NOT signal of the multiplier factor A so as to generate information on a partial-product generating circuit; (c) generating information on a partial-product adding circuit for receiving all the output signals from the partial-product generating circuit and the signal indicating the multiplicand X and outputting the addition results as a specified number of partial products; (d) generating information on a logic NOT circuit for receiving the output signals from the partial-product adding circuit and outputting the logic NOT signals thereof; (e) generating a correction signal from the multiplicand X; and (f) generating information on a final sum circuit for receiving the correction signal and the output signals from the logic NOT circuit, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

With the above structure, in the case where the number of the bits having the value of 1 in the constant multiplier factor A is large in the stage of designing a logic circuit with the multiplying function, the logic NOT signal of the multiplier factor A is produced, so that there can be generated the circuit for calculating partial products only with respect to the bits having the value of 1 in the logic NOT signal of the multiplier factor A. Consequently, it becomes possible to keep the number of the circuits for calculating partial products in the above logic circuit equal to or smaller than half the number of all the bits in the multiplier factor A.

To attain the above object, a system for automatically designing a logic circuit comprises: an input means for receiving various information; a storage means for storing the various information being processed; a processing means for producing information on the logic circuit for calculating the product of a multiplier factor and the multiplicand inputted from the input means; and an output means for outputting the information on the logic circuit produced by the processing means, wherein the processing means executes the steps of: (a) determining two constants A1 and A2 so that the difference (A1-A2) between the constants A1 and A2 equals the constant multiplier factor A; (b) judging which is the smaller of the number of the bits having the value of 1 in the multiplier factor A and the sum of the numbers of the bits having the value of 1 in the constants A1 and A2; (c) if the number of the bits having the value of 1 is the smaller, (c-1) generating information on a first partial-product generating circuit for receiving the multiplier factor A and the multiplicand X and outputting the products of the individual bits in the multiplier factor A and the multiplicand X as partial products, and (c-2) generating information on a first partial-product-sum circuit for receiving all the output signals from the first partial-product generating circuit, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X; and (d) if the sum of the numbers of the bits having the value of 1 in the constants A1 and A2 is the smaller, (d-1) generating information on a second partial-product generating circuit for receiving the constant A1 and the multiplicand X and outputting their partial products, (d-2) generating information on a third partial-product generating circuit for receiving the constant A2 and the multiplicand X and outputting their partial products, (d-3) generating information on a logic NOT circuit for receiving the output signals from the third partial-product generating circuit and outputting the logic NOT signals thereof, and (d-4) generating information on a second partial- product-sum circuit for receiving the output signals from the second partial-product generating circuit, the output signals from the logic NOT circuit, and a correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

An apparatus for automatically designing a logic circuit having the multiplying function for calculating the product of a multiplier factor and a multiplicand comprises: a means for receiving, from the outside, various information including information on the multiplier factor A, information on the multiplicand X, and information on the product P; a means for receiving the information on the multiplier factor A and determining information on a number A1 and information on a constant A2 so that the difference (A1-A2) between the number A1 and constant A2 equals the multiplier factor A; a means for receiving the information on the number A1 and the information on the multiplicand X and generating information on a first partial-product generating circuit which receives the number A1 and the multiplicand X and outputs, as partial products, the products of the individual bits the value of which is not 0 in the multiplier factor A and the multiplicand X; a means for receiving the information on the constant A2 and the information on the multiplicand X and generating information on a second partial-product generating circuit which receives the constant A2 and the multiplicand X and outputs, as partial products, the products of the individual bits the value of which is not 0 in the constant A2 and the multiplicand X; a means for receiving information on the output signals from the second partial-product generating circuit and generating information on a logic NOT circuit which receives the output signals from the second partial-product generating circuit and outputs the logic NOT signals thereof; a means for detecting the total number of the output signals from the first partial-product generating circuit and from the logic NOT circuit; a means for receiving information on the output signals from the first partial-product generating circuit and information on the output signals from the logic NOT circuit and generating information on a partial-product adding circuit which receives all the output signals from the first partial-product generating circuit and from the logic NOT circuit and outputs the addition results as partial products; a means for receiving either the information on the output signals from the logic NOT circuit or the information on the output signals from the second partial-product generating circuit and generating a correction signal based on the number of the output signals indicated by the received information; and a means for receiving information on the output signals from the partial-product adding circuit, information on the correction signal, and the information on the product P and generating information on a partial-product-sum generating circuit which calculates the sum of the output signals from the partial-product adding circuit and the correction signal, sets the sum to the product P as the product of the multiplier factor A and the multiplicand X, and outputs the product P.

With the above structure, if the processing means of the automatic designing system executes the sequence of processes or if the individual means of the automatic designing apparatus execute their respective processes, a logic circuit having a reduced number of partial products and a reduced number of logic stages can easily be generated.

To attain the above object, a multiplier for outputting the product of a multiplier factor A, which satisfies A=A1-A2 with respect to the constants A1 and A2, and a multiplicand X comprises: a first partial-product generating means for receiving the constant A1 and the multiplicand X and outputting partial products only with respect to the bits having the value of 1 in the constant A1; a second partial-product generating means for receiving the constant A2 and the multiplicand X and outputting partial products only with respect to the bits having the value of 1 in the constant A2; a logic NOT means for receiving the output signals from the second partial-product generating means and outputting the logic NOT signals thereof; and a partial-product-sum means for receiving the output signals from the first partial-product generating means, the output signals from the logic NOT means, and a correction signal, calculating the sum thereof, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

A multiplier for outputting the product of a multiplier factor A and a multiplicand X comprises: a partial-product generating means for receiving the logic NOT signal of the multiplier factor A and the multiplicand X and outputting partial products only with respect to the bits having the value of 1 in the logic NOT signal of the multiplier factor A; a partial-product adding means for receiving the output signals from the partial-product generating means and the multiplicand X, adding up the output signals from the partial-product generating means and the multiplicand X by using a single-stage or multi-stage adding means, and outputting the addition results as partial products; a logic NOT means for receiving the output signals from the partial-product adding means and outputting the logic NOT signals thereof; and a partial-product-sum means for receiving the output signals from the logic NOT means and a correction signal which can be generated from the multiplicand X, calculating the sum of the output signals from the logic NOT means and the correction signal, and outputting the sum as the product of the multiplier factor A and the multiplicand X.

With the above structure, each partial-product generating means outputs a partial product only with respect to a bit having the value of 1 in the logic NOT signal of the multiplier factor A or in the constants A1 and A2 which satisfy A=A1-A2, so that the number of partial products can be reduced. In addition, the resulting partial products are added up by the addition tree consisting of carry-save adders, which serves as the partial-product adding means. Consequently, there can be provided a high-speed multiplier which has a reduced number of logic elements and a reduced number of logic stages, appropriately for large-scale integration.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram showing the structure of an automatic logic-circuit designing system according to a first embodiment of the present invention;

FIG. 2 is a view showing the structure of a storage device of the above automatic designing system;

FIG. 3 is a flow chart showing a designing process according to the above automatic designing system;

FIG. 4 is a flow chart showing in detail a process of converting a functional element in Step 43 of FIG. 3;

FIG. 5 is a flow chart showing in detail a process of generating a multiplier in Step 85 of FIG. 4;

FIG. 6 is a flow chart showing in detail the process of converting a functional element in Step 1012 of FIG. 5;

FIG. 7 is a flow chart showing in detail the process of generating a multiplier in Step 1013 of FIG. 5;

FIG. 8 is a flow chart showing in detail a process of generating a multiplier using an addition tree in Step 142 of FIG. 7;

FIG. 9 is a flow chart showing in detail a process of generating a partial-product generating circuit in Step 151 of FIG. 8;

FIG. 10 is a flow chart showing in detail a process of generating a partial-product addition tree in Step 153 of FIG. 8;

FIG. 11 is a flow chart showing in detail a process of generating a multiplier by sign inversion in Step 146 of FIG. 7;

FIG. 12 is a flow chart showing in detail a process of generating a multiplier by division in Step 148 of FIG. 7;

FIG. 13 is a flow chart showing in detail a process of dividing a multiplier factor in Step 143 of FIG. 7;

FIG. 14 is a flow chart showing a process of generating a multiplier by an automatic logic-circuit designing system according to a second embodiment of the present invention;

FIG. 15 is a block diagram showing the structure of an automatic logic-circuit designing system according to a third embodiment of the present invention;

FIGS. 16(a) to 16(c) show an example of circuit data to be stored in the storage device of the automatic designing system according to the above first embodiment: FIG. 16(a) is a view diagrammatically showing a circuit, FIG. 16(b) is a view showing functional description information, and FIG. 16(c) is a view showing functional circuit information;

FIGS. 17(a) to 17(c) show another example of the circuit data to be stored in the storage device of the automatic designing system according to the above first embodiment: FIG. 17(a) is a view diagrammatically showing a circuit, FIG. 17(b) is a view showing functional description information, and FIG. 17(c) is a view showing functional circuit information;

FIGS. 18(a) to 18(d) are views diagrammatically showing a multiplier as a functional element in the designing process using the automatic designing system according to the above first embodiment;

FIGS. 19(a) to 19(d) are circuit diagrams showing a circuit generated in the process of generating a multiplier of FIG. 5;

FIGS. 20(a) and (b) are a view diagrammatically showing a conversion rule 1;

FIG. 20(c) is a view showing an actual representation form of the conversion rule 1;

FIG. 21 is a view diagrammatically showing a conversion rule 2;

FIG. 22 is a view diagrammatically showing a conversion rule 3;

FIG. 23 is a view diagrammatically showing a conversion rule 4;

FIG. 24 is a view diagrammatically showing a conversion rule 5;

FIG. 25 is a view diagrammatically showing a conversion rule 6;

FIG. 26 is a view diagrammatically showing a conversion rule 7; and

FIG. 27 is a view diagrammatically showing a conversion rule 8.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

(First Embodiment)

Referring now to the drawings, an automatic logic-circuit designing system according to a first embodiment of the present invention will be described below.

A description will be given first to the hardware structure of the automatic designing system according to the first embodiment with reference to FIGS. 1 and 2.

FIG. 1 is a block diagram showing an example of the hardware structure of an automatic logic-circuit designing system. In the drawing, an input device 11 is for inputting functional description information on a circuit to be designed by the automatic designing system. The input device 11 can be composed of a keyboard, mouse, light pen, card reader, or schematic entry system. Aside from the foregoing devices that receive the inputting of information through a direct operation by an operator, it can also be composed of a magnetic disk device, which stores information preliminarily inputted through the foregoing devices as a file, or of an network device which receives information sent from another device.

A CPU 12 is for performing circuit-designing processes such as logical synthesis or circuit optimization by executing a variety of processes, which will be described below.

An output device 13 is for outputting circuit information which is the result of the designing process by the CPU 12 or a variety of information on processing. The output device 13 can be composed of a graphic display, character display, printer, or plotter. The output device 13 can also be composed of the magnetic disk device or network device, similarly to the input device 11.

A storage device 14 consists of, for example, a design process storage unit 21, element library storage unit 22, and circuit data storage unit 23, as shown in FIG. 2, so that it can store information inputted through the input device 11 and programs or data on circuit-designing processes.

Specifically, the design process storage unit 21 stores a variety of programs whereby the foregoing CPU 12 executes design processes and conversion rule information to be applied in the course of these processes.

The element library storage unit 22 stores information on the functions of functional elements, logic elements, and mounted elements and on their area, delay time, and driving forces, so as to provide an element library.

The circuit data storage unit 23 stores functional description information which is inputted through the input device 11 and functional circuit information, logic circuit information, and mounted circuit information, each of which is generated by the circuit-designing processes.

The foregoing functional description information is mainly on a function required on a circuit, and is represented in a hardware description language. The functional circuit information is mainly on a circuit that is composed of virtual functional elements, the functions of which are only defined, and is represented in an internal representation form. The logic circuit information shows a circuit composed of real logic elements, which are on a logic level seldom dependent on the fabrication process or design methods. On the other hand, the mounted circuit information is greatly dependent on the fabrication process and design methods and shows a circuit to which are allotted elements actually mounted by a specified technology (e.g., a standard cell composed of a CMOS transistor, a cell in the library of a gate array, or TTL, ECL, and the like which are dependent on the fabrication process).

Examples of the foregoing functional elements are shown in Table 2. For example, a multiple-bit adder represents a functional element for adding two multiple-bit numbers. A comparator represents a functional element for comparing two multiple-bit numbers. A multiple-bit AND represents a functional element for calculating bit-by-bit logic products of two multiple-bit signals. A multiple-bit INV represents a logical element for calculating bit-by-bit logic Nots in a multiple-bit signal.

A ripper and mixer are functional elements for conveniently dividing a multiple-bit signal and processing the multiple-bit signal as a whole, respectively, during the course of conversion process. The ripper and mixer are eventually converted to a circuit composed of mounted elements and eliminated when all signals are processed in 1-bit signals.

In general, there exists no circuit that is composed of mounted elements directly corresponding to these functional elements. The functional elements are expanded to a circuit composed of real logic elements which realize their functions, and then replaced by a circuit composed of mounted elements.

TABLE 2 ______________________________________ MULTIPLE-BIT ADDER MULTIPLE-BI