JP2864597B2 - Digital arithmetic circuit - Google Patents

Description

Description: BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a digital operation circuit applicable to a product-sum operation such as a digital filter.

[Summary of the Invention]

The invention according to claim (1) is provided for a full adder to which a first input of a binary number, a second input as a carry, and a third input as a sum are supplied, and a second input. A carry connection means for supplying a carry from the lower order to the full adder and passing the carry to the higher order, a means for holding the carry and the sum output from the full adder in synchronization with a clock, and a hold means And a feedback path for feeding the sum output back to the full adder, while supplying the carry from the carrier through the carry connection means.

According to a second aspect of the present invention, there is provided a digital operation circuit comprising at least two first and second multipliers and an adder for adding outputs of the first and second multipliers, wherein the first and second multipliers are provided. The second multiplier is configured to form a partial product of the multiplicand and the data obtained by dividing the multiplier, and accumulate the partial product in a form divided into a carry and a sum.
And a selector for sequentially selecting each of the sum and the carry of the multiplier, and the output signal of the selector is cumulatively added. Thus, a product-sum operation circuit having a small number of gates can be obtained.

[Conventional technology]

An n-tap FIR digital filter converts the input sequence to x _i
When the output sequence is y _i and the impulse response is h ₀ to h _n-1 , The following calculation is performed. In digital filter processing of an audio signal, one multiplier and one accumulator are provided.
A configuration (so-called DSP) in which the above-described calculation is controlled by a program is used. However, in real-time processing of image data having a high sampling frequency, there is not enough time for the multiplier and the accumulator to perform time-division processing. Therefore, as shown in FIG. 5, a configuration in which a circuit is omitted in correspondence with the above-described arithmetic processing is used. FIG. 5 shows that (n =
This is an example of 4). The configuration in FIG. 5 can be expressed as in FIG. That is, the shift register unit 31 and the multiplication unit
32 and an addition tree unit 33.

As a multiplier used in the above digital filter, a parallel multiplier in which partial product addition circuits are arranged in parallel is usually used.
in use. FIG. 7 shows an example of a parallel multiplier using the Booth multiplication algorithm according to the proposal of the present applicant (see Japanese Patent Application Laid-Open No. 64-86270). However, FIG. 7 shows a circuit configuration for one bit,
The configuration is such that five partial products are added assuming a 10-bit multiplier (coefficient).

One bit of the input data extracted from the tap of the shift register section is connected to the selector 3 via the flip-flop 34.
5, 36, 37, 38, 39 and bit connection circuits 40, 41, 42, 43, 4
Supplied to 4 respectively. To the selectors 35 to 39, a coefficient, that is, a 3-bit control signal formed every two bits of the multiplier is supplied from a booth decoder (not shown). This decoder is supplied with a total of three bits, that is, two bits of interest of the coefficient and the lower one bit. Selectors 35 to 39 are 2
Based on the following Booth's algorithm, ± 2 times, ± 1 times and 0 times of 1 bit of the input are selected. The data of ± 2 times the input is realized by selecting the lower bits by the bit connection circuits 40 to 44. That is, 2 bits by one bit shift
A double value is formed.

Reference numerals 45, 46, 47, and 48 denote 1-bit full adders (full adders), to which three inputs are supplied and output two bits of a carry c and a sum s. Carries from the lower order are supplied as carry inputs of the full adders 46, 47 and 48 via the bit connection circuits 49, 50 and 51, respectively. Carry connection circuit 49, 50, 51
Indicates that the carry for the carry is connected to the circuit in the upper bit plane, and that the carry for the carry from the circuit in the lower bit plane is received.

In a normal parallel multiplier, carry is added at the end, but in the configuration of FIG. 7, the form of a 2-bit redundant binary number of carry and sum is assumed on the assumption that carry is added after the addition tree. Output of flip-flop 52 and
Output from 53. In this case,
As shown in FIG. 8, the six inputs passed through the input-side flip-flop 54 are sequentially added by four-stage full adders 55, 56, 57, 58, and the output-side flip-flops 59 and 60 are added. A configuration to output via can be used. FIG. 8 also shows a configuration of only one bit. As is apparent from FIG. 8, the difference from the normal configuration is that all 1-bit data is handled by two carry c and sum s. This FIG.
It is an example of addition of partial products for three taps of an R digital filter.

In the normal configuration, in the case of a 1-bit full adder, as shown in FIG. 9A, the inputs of A and B and the carry input ci from the lower side are supplied, and the addition output s and the carry output co to the upper side are provided. That occurs. On the other hand, the configuration shown in FIG. 8 described above is based on the concept that the arithmetic output is treated as a redundant binary number, and after all the operations are completed, the redundant binary number is converted into a normal binary number. That is, as shown in FIG. 9B, three inputs of the same bit digit of A, B, and C are added, and two outputs s1 and s2 of the same bit digit are output. With this concept, a large number of inputs of the same bit digit can be reduced to two outputs per bit at the end, but not one. Therefore, as shown in FIG. 9C,
It is necessary to connect a number of full adders in series to form one regular binary output per bit.

However, the configuration shown in FIG. 9C is a low-speed arithmetic circuit in which carry propagates in multiple stages. As a method of increasing the speed of such an addition circuit, carry look ahead (carry look ahead) and carry select are known. However, these methods have a disadvantage that the number of gates increases. Therefore, providing such an adder circuit for each multiplier and each adder tree constituting the digital filter in FIG. 5 is an obstacle to speeding up. Therefore, in the prior application, in each multiplier and each adder, two operations per bit are stopped in the middle, the next operation is started, and after all the operations, the speed is increased as shown in FIG. The conversion is from a redundant binary number to a normal binary number.

FIG. 8 shows one bit plane of the multiplying unit. In order to form an n-bit multiplier, it is necessary to overlap the n planes as shown in FIG. In FIG. 10, for simplicity, extension of the word length by the multiplier is not taken into account. FIG. 9 also shows a 1-bit plane of the addition tree unit. In order to have n bits, it is necessary to overlap the n-plane as shown in FIG. In FIG. 10, MP
Y corresponds to the configuration in FIG. 7, and AT corresponds to the configuration in FIG. In FIG. 10, connection lines are shown only for the most significant bit plane for simplicity, but are similarly connected for other bit planes.

[Problems to be solved by the invention]

In the previously proposed configuration, as shown in FIGS. 7 and 8, a large number of gate circuits such as full adders are interposed between flip-flops. In other words, a configuration in which a large number of gate circuits are arranged in series between pipeline registers is sandwiched. Such a configuration can be said to be a circuit with low efficiency because each gate circuit has a short working time and most of the clock cycles are rested. Unless such inefficiency is improved, the scale of a high-speed arithmetic circuit for image signal processing becomes large, and power consumption and cost increase.

In order to solve such inefficiency, it is only necessary to sandwich the gate circuit between pipeline registers in as small a form as possible, and as shown in FIG. 11, the input side and the output side of the full adder 61 are respectively provided. Flip-flops 62 and 63 are provided. However, as shown in FIG. 11, it is not possible to pipeline in units of full adders or in units of booth selectors.
Although the frequency of the clock can be tripled, the number of flip-flops increases and the number of gates increases.

SUMMARY OF THE INVENTION Accordingly, an object of the present invention is to provide an improved digital arithmetic circuit so that the number of gates is small and the gates do not play wastefully.

[Means for solving the problem]

The invention of claim (1) provides a full adder (16) to which a first input of a binary number, a second input of a carry, and a third input of a sum are supplied, And a carry connection means (18) for supplying the carry from the lower order to the full adder (16) and for transferring the carry to the upper order, and a carry and a sum output from the full adder (16). Means (17) for holding in synchronization with the clock; and carry from the hold means (17) is supplied to the higher order via carry connection means (18), and the sum output is fed back to the full adder (16). This is a digital operation circuit consisting of a feedback path and.

The invention according to claim (2) is characterized in that at least two first and second multipliers (8A, 8B) and first and second multipliers (8A, 8B).
A digital operation circuit comprising an adder (9) for adding the output of B), wherein the first and second multipliers (8A, 8B) calculate a partial product of the multiplicand and the data obtained by dividing the multiplier. And sums the partial products in a form divided into carry and sum. The adder (9) sequentially selects the respective sum and carry of the first and second multipliers (8A, 8B). Selector to do (20)
And a digital arithmetic circuit configured to accumulate the output signal of the selector (20).

[Action]

In the invention of claim (1), one full adder 16 and its input and output pipeline flip-flops
With the use of 15 and 17, it is possible to obtain the addition result of the partial products of half the number of bits of the multiplier by the time-division operation.

According to the invention of claim (2), when performing a product-sum operation such as a digital filter, the multiplying units 8A and 8B and the addition tree 9 are used.
Perform processing in the form of two signals, carry and sum. The addition tree 9 sequentially selects four inputs from the multiplication units 8A and 8B by the selector 20 and performs cumulative addition. Therefore,
The number of gates can be reduced, and circuits such as full adders can be prevented from being idle.

〔Example〕

Hereinafter, an embodiment in which the present invention is applied to a 4-tap FIR digital filter will be described with reference to the drawings.
FIG. 1 shows the overall configuration of this embodiment. The input data is a code whose one sample is, for example, 8 bits in parallel and whose 2's complement is used. However, in FIG.
Only the configuration for one bit plane is shown.

In FIG. 1, reference numerals 1, 2, 3 and 4 denote unit delay elements, for example, flip-flops each having a delay time equal to the sampling period of input data. The output data a of the flip-flop 1 (first tap) is supplied to the multiplier 8A. The output data of the flip-flop 2 (second tap) and the output data of the flip-flop 3 (third tap) are supplied to delay circuits 5 and 6 having a delay amount of 2τ (τ: clock cycle), respectively. 6 output data b '
And c 'are supplied to multipliers 8B and 8C, respectively. The output data d of the flip-flop 4 (fourth tap) is supplied to the delay circuit 7 of 4τ, and the output data d ′ of the delay circuit 7 is supplied to the multiplying unit 8D.

The multiplication units 8A to 8D multiply the coefficients by the data of the taps according to the secondary Booth algorithm. That is, when multiplying (X × Y) (X: multiplicand (data), Y: multiplier (coefficient)), (0, + X, -X, + 2X, or -2X ) Is performed to perform multiplication. Therefore,
A booth selector provided in each of the multipliers 8A to 8D is supplied with a control signal formed by supplying three consecutive bits of coefficients to a booth decoder. These 0, ± X, ± 2X are called partial products.

The multiplying units 8A to 8D include flip-flops 1, 2, 3
And 4, a partial product of a number corresponding to 1/2 of the coefficient word length is accumulated for each clock cycle. This partial product must have a 2 bit shift. Therefore, the output of the shift register unit shifts not only to the right every four clock cycles but also to two bits every clock cycle. As a method of this shift, a selector is provided on each input side of the multiplying units 8A to 8D, or a shift register that stores each input of the multiplying units 8A to 8D and can shift in the direction of increasing the bit digit is provided. Can be adopted.

The output e of the multiplier 8A and the output f of the multiplier 8B are the addition tree.
Supplied to 9A. The output g of the multiplier 8C and the output h of the multiplier 8D
Are supplied to the addition tree 9B. The outputs i and j of the summing trees 9A and 9B, respectively, are provided to a summing tree 10, respectively.
These addition trees 9A, 9B, and 10 add two bits of carry and sum to each other.

The output (carry and sum) k of the addition tree 10 is supplied to the flip-flops 11 and 12, and the output 1 is obtained from the flip-flops 11 and 12. Although not shown, this output l
Is a redundant binary number, and one bit is converted into one ordinary binary number by the configuration of the accumulator.

FIG. 2 is a timing chart showing the operation of the circuit shown in FIG. Multiplication units 8A to 8D, addition trees 9A, 9B, 10
Is a frequency four times the sampling frequency of the input data. That is, if the sampling period of the input data is represented by T and the clock period is represented by τ, then (T =
4τ). .. represent one bit of the same digit (MSB, LSB, etc.) of the parallelized input data.

For output data a of flip-flop 1, output data b of flip-flop 2, output data c of flip-flop 3, and output data d of flip-flop 4
T, 2T, 3T are each late. The output data b 'of the delay circuit 5 has a delay of 2τ with respect to b, the output data c' of the delay circuit 6 has a delay of 2τ with respect to c, and the output data d 'of the delay circuit 7 Has a delay of 4τ with respect to d.

In each of the output e of the multiplication unit 8A, the output f of the multiplication unit 8, the output g of the multiplication unit 8C, and the output h of the multiplication unit 8D, tn indicates the timing at which the multiplication result of xn of the input data and the coefficient is obtained. I have. For example, in the output e of the multiplication unit 8A, t4 is a timing at which a result of multiplication of x4 by the coefficient of the first tap is obtained.

In the output i of the addition tree 9A and the output j of the addition tree 9B, tmn indicates the timing at which the sum of the product of the coefficient and xm and the product of the coefficient and xn is obtained. For example, addition tree 9A
T54 is the product of x5 and the coefficient of the first tap (obtained at the timing indicated by t5 in the multiplication output e).
And the timing at which the sum of x4 and the product of the coefficient of the second tap (obtained at the timing indicated by t4 in the multiplication f) is obtained.

Furthermore, at the output k of the summing tree 10, tmop is tm
The timing at which the sum of the sum outputs obtained respectively by n and top is obtained is shown. For example, t4321 is t43 at the output i of the addition tree 9A.
The timing at which the sum of the addition output generated at the timing of (1) and the addition output generated at the timing t21 at the output j of the addition tree 9B is obtained. In the flip-flops 11 and 12, the output of the addition tree 10 is sampled by the clock of the original sampling frequency, and the filter operation output l
Are obtained from the flip-flops 11 and 12.

The above-described multiplication unit 8A has a configuration shown in FIG.
In FIG. 3, reference numeral 13 denotes a Booth selector, and the selector 13 is controlled by a 3-bit control signal obtained by supplying a coefficient for the first tap to the Booth decoder. The selector 13 selectively outputs a signal of 0 times, ± 1 times, ± 2 times of the input data according to a control signal for every two bits of the coefficient. The selector 13 is supplied with two bits of a carry from the lower side via the carry connection circuit 14 and the input data a. When the lower carry from the carry connection circuit 14 is selected, it means that double output is generated. In the case of a code with 2's complement,
The polarity inversion is realized by inverting “0” and “1” and adding “1” to the least significant bit.

The output of the selector 13 is supplied to the full adder 16 via the flip-flop 15. Two bits of the carry c and the sum s of the full adder 16 are output via the flip-flop 17 and are fed back to the input side of the full adder 16. This feedback path constitutes a cumulative adder (accumulator). With the configuration of the accumulator, the addition of the partial products is performed by time division processing. As described above, the selector 13, the flip-flops 15 and 17 and the full adder are clocked by four times the sampling frequency.
16 works.

When one bit, for example, x4 of the input data a is supplied, the selector 13 generates a partial product every two bits of the coefficient (8 bits) of the first tap. A total of four partial products are cumulatively added by the full adder 16 in four clock cycles, and the multiplication unit 8A shown in FIG.
In the output e, a multiplied output of x4 and a coefficient is obtained at the timing indicated by t4. Prior to each accumulation, the flip-flop 17 is cleared, or initialization is performed by inserting an AND gate in the feedback path. The carry generated at the time of the accumulation is supplied to the full adder of the upper digit via the carry connection circuit 18, and the carry of the lower digit is supplied to the full adder 15 via the carry connection circuit 18. .

The above-described multiplication unit 8A performs cumulative addition in such a manner that an input of one bit is represented by two bits of a carry c and a sum s. The multipliers 8B, 8C, and 8D have the same configuration as the multiplier 8A shown in FIG.

The details of the addition tree 9A are shown in FIG. Multipliers 8A and 8B
As described above, since 2-bit outputs e and f of carry and sum are generated as described above, a configuration capable of adding these 2 bits is required.

In FIG. 4, reference numeral 20 denotes an input e from the multipliers 8A and 8B.
And f (total of four inputs). Since the delay circuit 5 is inserted, there is a delay of two clock cycles between the inputs e and f to be added.
For carry of these inputs, the carry connection circuit
21 and 22 have been inserted. Flip-flops 23 and 24 are inserted only with respect to the input of the sum, and the sum is supplied to the selector 20 with a delay of one clock cycle with respect to the carry at the respective inputs e and f. Therefore, the selector
The carry of the input e, the sum of the input e, the carry of the input f, and the sum of the input f are sequentially supplied to the selector 20 at four clock cycles, and the selector 20 selects these one bit in order and outputs the selected one bit. I do.

One input selected by the selector 20 is supplied to the flip-flop 25. Flip-flop 25, full adder 26,
The flip-flop 27 constitutes the same accumulator as the multipliers 8A to 8D. The four inputs through the flip-flop 25 are cumulatively added by the accumulator. Therefore, the output i of the addition tree 9A is obtained from the flip-flop 27 after (4 + 1 + 1 = 6) clock cycles from the timing at which the input e is supplied. For example, a timing t43 six clock cycles after the timing t4 of the input e in FIG. 2 is a timing at which the output i of the addition tree 9A is obtained.

The addition trees 9B and 10 also have the same configuration as in FIG. One addition tree without addition trees A and 9B
The addition process can be performed with only 10. In this case, however, the selector sequentially selects one of the eight inputs, and the number of repetitive additions increases to eight, so that the operation speed of the circuit needs to be twice that of the configuration in FIG.

Further, the number of taps, the word length of the filter, the word length of the accumulator, and the like are not limited to the above-described embodiment. In particular, the word length of the accumulator is 1-bit, which is the fastest,
The word length may be extended to n bits. Further, the present invention
The present invention can be applied not only to digital filters but also to product-sum operations such as FFT and cosine exchange.

〔The invention's effect〕

According to the present invention, since the accumulator including the full adder and the feedback path has a pipeline configuration, the addition or the multiplier can be performed with a small number of gates, and the gates can be prevented from being idle. In addition, when a product-sum operation such as a filter operation is performed, the processing in the multiplication unit and the addition tree can be performed using redundant binary numbers, and it is necessary to add carry carry in each of the multiplication unit and the addition tree. Gone
The calculation speed can be prevented from lowering. Further, in the present invention, since there are many such circuits having the same circuit configuration as a cumulative adder, the present invention is suitable for IC implementation.

[Brief description of the drawings]

FIG. 1 is an overall block diagram of one embodiment of the present invention, and FIG.
FIG. 3 is a timing chart showing the operation of this embodiment, FIG. 3 is a block diagram showing an example of a configuration of a multiplication unit, FIG. 4 is a block diagram showing an example of a configuration of an addition tree, and FIGS. FIG. 7 is a block diagram used to describe an FIR digital filter, FIGS. 7 and 8 are block diagrams respectively showing a multiplier and an addition tree proposed above, and FIG. 9 is a schematic diagram illustrating an addition process. FIG. 10 is a schematic diagram showing a connection relationship between bit planes, and FIG. 11 is a block diagram showing a configuration in which a pipeline is formed for each full adder. Explanation of main symbols in the drawings 8A to 8D: multiplication unit, 9A, 9B, 10: addition tree, 13: booth selector, 16, 26: full adder, 20: selector.

Claims (2)

(57) [Claims] 1. A binary first input and a second carry.
And a third input which is a sum, which is provided for the second input, supplies a carry from the lower order to the full adder, and passes a carry to the upper order. Carrying means for holding the carry and the sum output from the full adder in synchronization with a clock; and supplying the carry from the holding means to a higher order through the carry connecting means. And a feedback path for returning the sum output to the full adder. 2. A digital operation circuit comprising at least two first and second multipliers and an adder for adding outputs of the first and second multipliers, wherein the first and second multipliers are provided. Is configured to form a partial product of the data obtained by dividing the multiplicand and the multiplier, and to cumulatively add the partial product in a form divided into a carry and a sum. A digital arithmetic circuit comprising: a selector for sequentially selecting each sum and carry of the two multipliers; and a configuration for accumulating the output signals of the selector.