Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1997-08-22
2001-04-24
Mai, Tan V. (Department: 2787)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06223197
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a constant multiplier for multiplying a constant by a signal set to an optional value, a method and a device for automatically providing such a constant multiplier and a storage medium storing a program used for automatically providing such a constant multiplier.
2. Description of the Related Art
Generally, a large scale application specific integrated circuit (ASIC) having functions of a moving picture expert group (MPEG), and so on, needs a number of multipliers each as an arithmetic circuit for performing image processing or the like. Most of these multipliers multiply constants (already known fixed numbers) by signals having unknown optional values.
For example, multiplication of a constant by a signal is often used for discrete cosine/color space transformation. Specifically, in a RGB code/YUV code conversion expression like that described below, U and V are signals having unknown optional values and parameters (coefficients) multiplied by these signals U and V are constants.
R=Y+
1.367
×V
G=Y−
0.703125
×U−
0.34375
×V
B=Y+
1.7345
×U
Conventionally, multipliers for multiplying constants by signals like those described above have been designed not as special multipliers for the constants but as multipliers for multiplying unknown optional values by each other. In other words, multiplication of a constant by a signal is performed by a multiplier operated based on the same algorithm as that for performing multiplication of a signal by another signal.
It can thus be understood that conventionally, for designing of a large scale integrated circuit, even if a value for one of signals to be multiplied by each other is fixed and known beforehand, the signal (constant) has been treated as a signal having an unknown value and no optimization has been carried out for a circuit as a constituting element for the multiplier.
Consequently, in the large scale integrated circuit (e.g., LSI for MPEG) having a number of useless circuit portions and a number of multipliers for multiplying constants by signals, if a multiplier like that described above is formed, not only an area for the circuit is increased but also operational delay is caused to occur.
For example, a multiplier designed by using a shift multiplier method treats a multiplier B which is a constant as a signal and produces a partial product from a product with a multiplicand A for each figure (bit), and the partial products thus obtained for respective bits are shifted each by 1 bit and added together. Specifically, with A=“1101” and B=“1011”, calculation is performed in a manner described below.
1101
Multiplicand
(A: signal)
× 1011
Multiplier
(B: constant)
1101
Partial product{circle around (1)} (A)
1101
Partial product{circle around (2)} (2A)
0000
Partial product{circle around (3)} (0)
+ 1101
Partial product{circle around (4)} (8A)
10001111
Multiplication result
In the above example, since the partial product {circle around (3)} is 0, this product need not be added in actuality. However, if a multiplier for multiplying a signal by another signal is used, the partial product {circle around (3)} is also added and accordingly an unnecessary circuit (adder) is provided.
Next, the circuitry example of the multiplier designed by producing partial products with the shift multiplier method will be described by referring to
FIGS. 11 and 12
.
Referring first to
FIG. 11
, there are shown a multiplication processing procedure and a constitutional example of a multiplier. It is assumed that as a multiplier, for instance a constant “59 [=(111011)
2
; 6 bits ]” is given and a multiplicand is a signal A. In this case, if partial products are to be produced by using the above-noted shift multiplier method, six partial products {circle around (6)} 32A, {circle around (5)} 16A, {circle around (4)} 8A, {circle around (3)} 0A, {circle around (2)} 2A and {circle around (1)} A are obtained. A partial product adding circuit, in other words a multiplier 100, for calculating a multiplication result “59A” with the signal A by adding these products together to output it, is then provided.
The multiplier
100
shown in
FIG. 11
is constructed in a manner that five carry save adders (abbreviated to CSA, hereinafter)
101
to
105
are connected together and a carry look-ahead adder (abbreviated to CLA, hereinafter)
106
which is a typical high-speed type carry propagate adder (abbreviated to CPA, hereinafter) is connected to a stage next to the CSA
105
as a last stage. For an adder used in the last stage, any type may be used as long as it belongs to CPA. For example, a carry select adder or a ripple carry adder other than CLA can be used.
In the multiplier constructed in the above-noted manner, multiplication processing is performed as follows. The partial products {circle around (6)}, {circle around (5)}, {circle around (4)}, {circle around (3)}, {circle around (2)} and {circle around (1)} are regularly added together in sequence by the five CSAs
101
to
105
, carried values are propagated at a high speed and added together by the CLA
106
in the last stage and then a multiplication result “59A” is outputted. In the multiplier
100
shown in
FIG. 11
, the number of adding stages excluding the last stage is “5”.
However, since the multiplier
100
is designed without making any determination as to whether the partial product is “0” or not, the CSA
103
for adding the partial product {circle around (3)} which is “0” must be provided. Consequently, a circuit area is increased and operational delay is caused to occur.
Referring next to
FIG. 12
, there is shown a procedure for designing a constant multiplier and a constitutional example thereof. A multiplier
200
shown in
FIG. 12
produces six partial products {circle around (1)} to {circle around (6)} by using the same shift multiplier method as that shown in
FIG. 11
, adds these six partial products {circle around (6)}, {circle around (5)}, {circle around (4)}, {circle around (3)}, {circle around (2)} and {circle around (1)} together and thereby calculates a multiplication result “59A”. In this case, the multiplier
200
comprises four CSAs
201
to
204
interconnected in a tree form so as to reduce the number of adding stages and a CPA
205
connected to a stage next to the CSA
204
as a last stage. In other words, the constant multiplier
200
having adding stages amounting in number to “3” is provided/designed by the four CSAs
201
to
204
. This tree-formed adder construction is called “Wallace tree”. For the CPA
205
, a CLA or a carry select adder can be used.
With the multiplier
200
provided/designed in the above-noted manner, since the number of adding stages can be reduced compared with the case of the multiplier
100
shown in FIG.
11
and the number of CSAs to be used can also be reduced, the problems of an increased circuit area and operational delay may be solved to a certain extent. However, the number of adding stages and the number of used adders should preferably be reduced much more.
Referring further to
FIG. 13
, there is shown another constitutional example of a multiplier. A multiplier
300
shown in
FIG. 13
comprises a partial product generation circuit, which includes a booth decoder
301
and a booth selector
302
. By using this partial product generation circuit, the number of partial products can be reduced by half. Accordingly, when a constant “59” is to be multiplied by a signal A as described above, the number of partial products is reduced from six to three, the three partial products {circle around (1)} to {circle around (3)} are added together by an adding circuit (by “Wallace tree” or CSA)
303
and a CLA
304
in the last stage and then a multiplication result “59A” is calculated.
With the multiplier
300
constructed in the above-noted manner, since the booth decoder
301
and the booth
Fujitsu Limited
Mai Tan V.
Staas & Halsey
LandOfFree
Constant multiplier, method and device for automatically... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Constant multiplier, method and device for automatically..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constant multiplier, method and device for automatically... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2553943