JPH0319583B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION Technical Field of the Invention The present invention relates to a product-sum calculation circuit suitable for cases where the number of digits is large.

Prior Art and Problems When performing fast Fourier transform, discrete Fourier transform, etc., a sum-of-products operation of the form _N 〓 ⁱ⁼¹ AiBi appears. The number of digits in the arithmetic circuit can be easily determined for a sum or product operation alone; for example, for the sum of two 8-bit binary numbers, a 9-bit arithmetic circuit, and for a product, a 16-bit arithmetic circuit. On the other hand, in the product-sum operation, the number of digits required increases as N increases, and if the number of digits in the arithmetic circuit is insufficient, overflow will occur. If you use the floating-point method, which separates the accumulation operation into the mantissa and exponent parts, overflow is less likely to occur, although some loss of digits may occur, but if you use the fixed-point method, you do not pay enough attention to the number of digits. This will cause an overflow.

This problem can be resolved by designing the arithmetic circuit with a sufficient margin for the number of digits beyond the decimal point, or by limiting the data to be operated on within the number of digits of the arithmetic circuit so that overflow will never occur. This can be avoided by normalizing with the maximum value of , shifting the digits to prevent overflow, or correcting to take the maximum positive/negative value when overflow occurs, but in either case, the circuit size It is not easy to carry out because of the increase in the number of errors and the increase in errors.
Conventional examples of product-sum calculation circuits are shown in FIGS. 1 and 2.

In FIG. 1, 10 and 12 are arithmetic registers, 14 is a multiplication circuit, and 16 is an accumulation (addition) circuit. Data A and B to be multiplied and summed (this is a set of two series of digital binary information Ai and Bi (i=1, 2, . . . N)) are set in registers 10 and 12, and multiplied by a multiplier circuit 14. The product A.times.B is obtained, and the sum of the result and the previous addition result is obtained in the accumulation circuit 16, and the above is repeated to perform the product-sum operation _N 〓 ⁱ⁼¹ AiBi. For the sake of explanation, assuming that data A and B are both 8 bits, the output result of the multiplier circuit 14 may be 16 bits. However, in the accumulation circuit 16, the number of required bits increases in accordance with N if results are to be obtained without errors. To be exact, the required number of bits depends on the cumulative result and is therefore undefined, and here it is assumed to be (16+L) bits. If L is not large enough, overflow will occur. For example, the maximum positive value of the output of the 16-bit multiplier circuit 14 is 011...1 (1 is 15
, the first 0 is a plus sign), expressed in hexadecimal as 7FFF
If the least significant bit of the previous calculation result of the accumulation circuit 16 is 1, the current calculation result will be 8000,
If L=0, an overflow will occur and the calculation result will be negative. Here, in an accumulation circuit that performs the above-mentioned overflow correction, add 1 to 7FFF,
If we consider the case where we then add -1 and then -2, the correct result is 7FFF-2, which is 7FFD, but this will not happen because an overflow will occur at the first +1 stage and will be corrected. Therefore, it is necessary to make L sufficiently large, but increasing bits with an adder is quite troublesome, unlike increasing bits with a register.

FIG. 2 shows an example of normalization and shifting so that overflow is less likely to occur. The maximum value detection circuit 18 detects the larger value of data A and B set in the registers 10 and 12 to be the sum of products, and the normalization correction circuit 2 so that the larger value becomes 1.
It is normalized to 0.22. Now, if A>B, the output of the circuit 22 is 1, and the output of the circuit 20 is smaller than 1. Although these products are less than 1, we expect 1 to be the maximum possible value, and the accumulator 16 has a decimal point of 4.
If the design is such that it is in the digit (in terms of L, L=3), there is a risk that overflow will occur after eight accumulations. Therefore, in this circuit, normalization is performed to make the maximum value of data A and B less than 1, for example, 0.5 (after normalization, the data is shifted to the right by 1 bit. This is called normalization correction). In this way, the product of such normalized data A and B will be 0.25 at most, or
2 ^-2 , which uses 3 bits above the decimal point (the first 1 bit is a sign), which means that it can be accumulated 32 times before it reaches 8 or more and overflows. The output correction circuit 24 is 1/2 in circuits 2 and 22,
Since we have processed to reduce the total to 1/4, we will compensate for this by multiplying by 4. Since the circuit shown in FIG. 2 performs normalization and correction in this way, it is possible to perform a large number of accumulation operations using the accumulation circuit 16, which does not have a large number of bits. However, during the above correction, that is, right shift, there is a risk that bits on the LSB side may be missing, causing errors due to missing digits. Furthermore, the circuit configuration including maximum value detection, normalization, and correction is complicated.

OBJECTS OF THE INVENTION The present invention aims to provide a circuit that can accurately perform a product-sum operation many times without significantly increasing the circuit scale or causing overflow during the operation.

Structure of the Invention The present invention includes a multiplication circuit and an accumulation circuit, and includes two series of digital binary information Ai, Bi (i=1, 2,...N).
In the product-sum operation circuit that calculates _N 〓 ⁱ⁼¹ AiBi by adding the products, the product-sum operation _N1 〓 ⁱ⁼¹ AiBi is _N1 〓 ⁱ⁼¹ AiBi+ _N2 〓 ^i=N1+1 AiBi+...+ _N 〓 ⁱ⁼ a storage device for storing the calculation results of the individual terms, which are n blocks of ^Nn-1+1 AiBi, and the number of additions of each block is the number of times that the accumulation circuit does not overflow; Each time the number of cumulative operations in the accumulation circuit reaches the scheduled number of cumulative operations for each term, the operation result is saved in the storage device, the accumulation circuit is cleared, and the accumulation operation is started again, and the operation for each term is completed. The present invention is characterized by comprising a cumulative number counter device for accumulating the values of each term stored in the storage device in an accumulating circuit when the above-described values are stored in the storage device. .

Embodiment of the invention FIG. 3 shows an embodiment of the invention, and FIG.
The same parts as in the figure are given the same reference numerals. As is clear from comparing these, this circuit is provided with a temporary storage device 26 for saving the accumulated results, and a counter 28 for counting the number of accumulations. Expressing the cumulative operation as S= _N 〓 ⁱ⁼¹ AiBi ……(1), from the linearity of this equation, (1) becomes S= _N1 〓 ⁱ⁼¹ AiBi+ _N2 〓 ^i=N1+1 AiBi+…+ _N 〓 ^i=Nn-1+1 AiBi
...(2) The number of times N1, N2 - N1, ... of each product-sum is such that overflow does not occur in the relevant product-sum interval, for example, the multiplication result is within the range of ±1.0, and the cumulative calculation circuit is within ±8.0. If you want to cover this range, do it within 8 times. The circuit of FIG. 3 executes the calculation of equation (2), that is, the sum of N products is subdivided into the number of times such that no overflow occurs. The cumulative number counter 28 checks whether the sum of each subdivided product has reached the scheduled cumulative number of times.
The temporary storage device 26 temporarily stores the individual product-sum results, that is, the value of each term in equation (2).

That is, the data A and B of the registers 10 and 12 are input to the multiplication circuit 14, and the product A×B is obtained.
These Ai·Bi (i=1, 2, . . . N) are input to the accumulation circuit 16 through the selector 30, and ΣAi·Bi is calculated. The counter 28 counts the clocks generated from the accumulation circuit 16 each time the accumulation process is performed (one clock per process), and when i=N1, the accumulation result of the accumulation circuit 16 is taken into the storage device 26, and the accumulation circuit 16 and Clear your own counter. This means that the first term on the right side of equation (2) has been calculated and the result has been stored. The product-sum counter 28 calculates the cumulative number of times N1, N2 of each term on the right side of equation (2) above.
-N1, . . . , the total cumulative number N, the number of terms on the right side, etc. are set in advance, and it is possible to count these and notify the completion of counting. Next, the accumulation circuit 16 starts accumulating the output data of the multiplication circuit 14 from the beginning, and the counter 28 counts the number of accumulations, and when it reaches (N2 - N1), the accumulation result of the circuit 16 is stored in the storage device 26, and the accumulation result is stored in the storage device 26. The circuit 16 and its own counter are cleared. This means calculating the second term on the right side of equation (2) and storing the result.
The same holds true for the following operations, including the calculation of the final term on the right side of equation (2) and the storage of the result.

When the calculation up to the final term is completed, the counter 28 switches the selector 30 so that the read output of the temporary storage device 26 is input to the accumulation circuit 16. This corresponds to the operation of adding each term on the right side of equation (2) above,
After (n-1) additions, the calculation of equation (2) is completed, and the sum-of-products output S can be taken out through the output register 32. Signals S _W and S _R from the cumulative number counter 28
is a write/read instruction signal for the temporary storage device 26, S _S is a switching instruction signal for the selector 30,
So is a signal for instructing the output register 32 to take in the output of the accumulation circuit 16 and for outputting the same.

In the accumulation of each term in equation (2) above, if each term is a positive number, the accumulation result will gradually increase, so the accumulation circuit should have a margin of L bits as shown in Figure 2. However, depending on the degree of increase, an overflow may occur in the accumulator circuit. However, when correlating audio signals, data A and B are B = A _i-2
In other words, B is two sampling times before A, and since the audio signal is alternating current and changes from positive to negative, each term of the sum of products changes from positive to negative depending on how it is divided. Therefore, it is effective to avoid overflow of the accumulation circuit 16 by alternately taking out each term on the right side of the equation (2) stored in the temporary storage device 26, for example, positive and negative. A right shift is also effective. For example, if you check the value of each term in the above equation (2) stored in the temporary storage device 26 and calculate it as it is, if an overflow is likely to occur, shift both of the two data to be accumulated to the right by the required number of bits. However, if you undo the process after the subtraction has been performed and the problem no longer occurs, or at the output stage, overflow can be avoided, although there is a risk of loss of digits. Regarding the loss of digits, in the present invention, there is a possibility that this may occur if the accumulation of each term in equation (2) is
Since this is a case where a right shift is added and executed, and there is no risk of this occurring when taking the sum of individual products as in the method shown in Figure 2, the magnitude of the error is much greater with the present invention. You can expect it to be small.

Effects of the Invention As explained above, according to the present invention, the product-sum operation can be performed without increasing the number of bits of the arithmetic circuit, overflow is prevented, and loss of precision is avoided as much as possible, and a large amount of data can be processed. Product-sum operations can be executed accurately.

[Brief explanation of drawings]

1 and 2 are block diagrams showing a conventional product-sum calculation circuit, and FIG. 3 is a block diagram showing an embodiment of the present invention. In the drawing, 14 is a multiplication circuit, 16 is an accumulation circuit, and 26
28 is a storage device and a cumulative number counter device.

Claims (1)

[Claims] 1. A multiplication circuit and an accumulation circuit are provided, and two series of digital binary information Ai, Bi (i= _1,2, . . . _N ) are multiplied and summed to obtain _N 〓 ⁱ⁼¹
In the product-sum calculation circuit that calculates AiBi, the product-sum calculation _N 〓 ⁱ⁼¹ AiBi is _N1 〓 ⁱ⁼¹ AiBi＋ _N2 〓 ^i=N1+1 +... ＋ _N 〓 ^i=Nn-1+1. The number of additions for each block is the number of times that the accumulation circuit does not overflow.The memory device stores the operation results of each term divided into the n blocks, and the number of additions for each block is the number of times that the accumulation circuit does not overflow. Every time the scheduled number of cumulative calculations is reached, the calculation results are saved in the storage device, the accumulation circuit is cleared and the cumulative calculation is started again, and when the calculation of each term is completed, the calculation results stored in the storage device are saved. 1. A product-sum calculation circuit comprising: a cumulative number counter device for accumulating the value of each term in an accumulating circuit.