JPH0227703B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a block floating point arithmetic fast Fourier transform processor in which a plurality of stages each having a butterfly arithmetic circuit and two data input/output memories are connected in cascade, and is particularly applicable to an automatic scaling circuit. Involved.

In general arithmetic devices, including fast Fourier transform processors, the word length of arithmetic operations is determined by the hardware configuration thereof. When the dynamic range of the data to be operated on is wide, the word length becomes longer than the operation word length determined by the operation, and so-called overflow may occur. Conventionally, when such an overflow occurs, the calculation target data is incremented and the calculation is performed again to prevent the overflow. When an overflow occurs in such a calculation, the calculation is performed again after carrying down, which has the disadvantage that the calculation time becomes longer.

An object of the present invention is to perform high-speed calculations by cascading a plurality of stages each having a butterfly calculation circuit and two data input/output memories in a fast Fourier transform processor. The purpose is to reduce the computation time by predicting overflow and not requiring redoing the computation.

According to this invention, in a fast Fourier transform processor in which a plurality of stages each having a butterfly operation circuit and two data input/output memories are connected in cascade, the upper two bits of the input data are input to each stage. A scaling circuit including a maximum value detection circuit and an addition circuit are respectively provided, and these addition circuits are connected in series, and the maximum value detection circuit detects the maximum value of data within one frame at each stage input. predicts the overflow of the butterfly operation at that stage, outputs a scaling signal for preventing overflow from that scaling circuit to that stage, increases the content of the adder circuit of that stage by 1, and increases the output of the adder circuit. is input as a scale factor to the addition circuit of the next stage, and the exponent part of the spectrum output data in the fast Fourier transform processor is obtained as the final output result of the scale factor.

Also, if the number of bits of input data to the fast Fourier transform processor is i, then i
A bit conversion circuit selects j bits (j<i) from among the bits, and converts the selected j bits into
It is input to the first stage of the FFT, and the bit selection signal from the bit conversion circuit is input to the first stage adder of the automatic scaling device and used as the initial value of the scale factor. To select the j bit, look at the state of the upper multiple bits of the i-bit data, for example 4 bits, and select an appropriate part of the j bit in the i-bit so that overflow does not occur in calculations within the FFT processor. .

As described above, the fast Fourier transform processor according to the present invention has a relatively short calculation word length, and therefore can perform high-speed processing of input signals whose input data values, that is, amplitudes, fluctuate greatly, without significantly increasing the scale of the hardware. It is possible to perform Fourier transform in real time. As described above, the dynamic range of the input signal amplitude is large and high-speed Fourier transform is required in a short time. There is an example of an application in which abnormalities in materials or equipment are detected by monitoring emitted acoustic emissions (hereinafter referred to as AE).

Hereinafter, a case where the present invention is applied to a device that detects microscopic destruction of an object by capturing an AE signal will be described with reference to the drawings.

In FIG. 1, an AE signal generated by microscopic destruction of an object to be detected 11 is captured by a pickup 12 as an electrical signal. The output of this pickup 12 is amplified by an amplifier 13 and inputted to an AD converter 15 from a terminal 14. The output of the amplifier 13 is also input to the comparator 16 and compared with the reference signal of the reference signal source 17. If the absolute value of the input is larger than the reference signal, it is determined that the AE signal has been input, and the output is sent to the AD converter 15 and thereafter. At the same time, the time signal generator 18 is activated so that the elapsed time can be known.

The AD converter 15 samples the input AE signal at regular intervals and converts each sample value into a multi-bit digital signal. The digital signal is written into a buffer memory 19 and transferred from there to a fast Fourier transform (hereinafter referred to as FFT) processor 21, and the complex frequency spectrum output from the FFT processor 21 is converted into a power spectrum by a power spectrum calculator 22 and accumulated. If input to the calculator 23 and one AE signal is defined as one event, a power spectrum accumulated for one event is calculated and transferred to the data compressor 24. The automatic scaling circuit 25 calculates a scale factor while controlling the block floating point operation performed by the FFT processor 21. This scale factor 26 is used to normalize the spectral intensity during accumulation in the accumulator 23.

For the radix-2 fast Fourier transform algorithm, 2 ⁿ
data is defined as one frame, and FFT calculation is performed for each frame. For example, if n=10, 1024
A data group forms one frame. Also, according to the sampling theorem, sampling must be performed at a sampling frequency that is at least twice the highest frequency included in the signal under test.
The spectrum obtained by FFT is not determined. AE signal
If it has a frequency component of 1MHz, the sampling frequency ( _s ) will be 2MHz. Therefore, the time (T) required to capture one frame of data can be obtained from the following equation (1).

T=2 ⁿ / _s =1024/2×10 ⁶ =0.512 msec (1) Figure 2 shows a schematic diagram of the AE signal and frame division. As shown in this figure, there are two FFT methods for AE signals that have a connection time longer than one frame T. Assuming n=13, one frame has 8192 points.
There is a method of performing FFT, and a method of calculating the spectrum by performing FFT on each of 8 frames and accumulating the obtained spectral components. The example shown in Figure 1 has the following advantages: the amount of hardware is small, the resolution is not so important for AE signals, and the averaging operation by accumulation suppresses the minute oscillations in the spectrum that are characteristic of FFT. For some reason, we have chosen the latter. However, the former method may also be used.

As shown in FIG. 3, the FFT processor according to the present invention is composed of an n-stage butterfly operation stage 33 and a stage 32 that performs window processing provided in the preceding stage, where 2 ⁿ points constitute one frame. In the case of 1024 points, stages 32 and 33 are combined to form a cascaded stage configuration of 11 stages. FIG. 4 shows a block diagram of the buffer memory 19 in FIGS. 1 and 3, and FIG. 5 shows a block diagram of the stage 33. The buffer memory 19 and each stage 32, 33 are all two-sided input/output memories M ₁ , M ₂
When one is in a writing state of output data from the AD converter 15 or the previous stage, the other is in a reading state in which previously written data is transferred to the next stage after calculation. When the transfer of 1024 points of data is completed, the states of memories _M1 and _M2 are exchanged, and the memory that was in the read state changes to the write state, and the memory that was in the write state changes to the read state. , the data flow is performed in a pipeline manner. At this time, the address for memory access is supplied from the address register unit 37.

The butterfly calculation unit 41 in each stage 33 is also controlled by microinstructions given by the control section 38, and performs butterfly calculation by pipeline calculation. Each stage 33 is provided with a memory 44 in which twiddle factors are stored. If we abbreviate the input data at each stage as A _k , B _k , the output data as A′ _k , B′ _k , and the twiddle factor as W ^k , the butterfly operation at each stage is a repetition of the following equation (2). .

A' _k = A _k + W ^k B _k B' _k = A _k −W ^k B _k ...(2) At this time, the instruction state of the microinstruction is given as shown in Figure 6, and this instruction is decoded. In particular, as shown in FIG. 6, D ₁ to D ₆ , S ₁ to S ₄ ,
Further, a SUB control signal is generated and an instruction as shown in FIG. 7 is executed. As a result, the input A _k in the data read from the memories M ₁ and M ₂ using such an instruction is stored in the register 42 via the bus buffer 43 as shown in FIG. 5, and the input data B _k is Via the bus buffer 43, the twiddle factor ^Wk is stored from the twiddle factor ROM (memory) 44 into the multiplier 45, and multiplication is performed. An address 46 is applied to the ROM 44, and this address 46 is selected by a multiplexer 47 and selectively applied to the memories M ₁ and M ₂ . The multiplication result of the multiplier 45 is sent to the multiplexer 47
and is stored in the register 48 or 49 via the adder 51. The multiplication result W ^k B _k passes through a multiplexer 52 , an exclusive OR circuit 53 , and further passes through a multiplexer 54 to be applied to an adder 51 . At this time, one input of the exclusive OR circuit 53 is set to all "0" or all "1", and in the case of the former, the output and the contents of the register 42 are added.
A′ _k is obtained, and in the latter case, when adding with the contents of the register 42, “1” is further added to obtain the complement of W ^k B _k to obtain B′ _k as the addition result. These input data and control each part so that the butterfly operation of equation (2) is executed in a pipeline manner. The calculation result is sent to the next stage through the overflow prevention circuit 55. Note that when writing to the memories M ₁ and M ₂ , the data 56 is given to the memories M ₁ and M ₂ via the bus buffer 57 and the address 58 is
is selected by the multiplexer 47 and the memory M ₁ ,
_M2 is given and done.

This pipeline configuration enables high-speed calculations with a Nyquist frequency of 1.4MHz in real-time calculations, and achieves real-time fast Fourier transform of AE signals.

One of the characteristics of the AE signal is that the intensity of each event varies greatly, and the range is
It is over 40dB. Furthermore, the AE signal waveform itself is a damped vibration waveform, and the data size for each frame within one event is different, so when frame division is performed, the data included in the last frame of the event will have a small amplitude. Become something. Therefore, when performing digital operations with a finite word length,
In order to obtain sufficient calculation accuracy without loss of digits even for small amplitude signals, the word length of the AD converter 15 is made large, and an appropriate bit is selected from among them according to the input signal strength, and automatic scaling is used. It is preferable to prevent overflow and underflow during calculation by means.

FIG. 3 shows a block diagram of an FFT processor equipped with an automatic scaling circuit 25 according to the present invention. For example, if the word length of AD converter 15 is 10 bits,
The FFT data word length is 8 bits. Regarding the buffer memory 19, in FIG. 4, when one frame of 10-bit data (D ₉ to D ₀ ) is written from the AD converter 15 to one memory, the maximum value in the frame is detected by the maximum value detector. 61 (Figure 3)
The detection output is set in the flip-flop 67 for each frame, the set contents are decoded by the decoder 62, and the output of the decoder 62 is controlled as follows. Since the maximum value that can be expressed with 10 bits is 1023, if the maximum value detected by the detector 61 is less than 1023/4=255, the bit select signal 63 output from the decoder 62 is
The bit selector (bit conversion circuit) 60 in the buffer memory 19 selects the bus buffer 64 in FIG.
If it is within the range, bus buffer 65 is selected, and if it is 512 or more, bus buffer 66 is selected.
The data is transferred to the FFT processor 21 as 8-bit data. The output of the flip-flop circuit 67 also passes through a gate circuit 68, becomes the initial value of the scale factor 26, and is preset in the counter 73. In this way, the dynamic range for AE input signals with large amplitude changes can be expanded without unnecessarily increasing the data word length of the FFT processor 21, that is, the amount of hardware, and the 8-bit word length can be used effectively. be able to.

Similarly, for each stage 33 in FIG. 3, block floating point operations can be controlled using means for detecting the maximum value within one frame.
Therefore, for each stage 33, a scaling circuit 70 including a maximum value detection circuit 71 and an addition circuit 73 are provided.
These adder circuits 73 are connected in series in the order of the stage 33. The butterfly operation is as shown in equation (2), where |W ^k
Since |≦1, there is a possibility of overflow when data A _k or B _k exceeds half of the maximum value expressed in 8 bits. In the FFT processor 21, the range of values that data A _k and B _k can take is -128≦A _k , B _k ≦127 ... (3), so A _k , B _k < -64 or A _k , B _k ＞63 ……(4) Only when A _k ′=A _k ′/2 B′ _k =B′ _k /2 ……(5) is sufficient. This method is called block floating point arithmetic, and it is possible to perform butterfly arithmetic while making full use of the 8-bit word length. Here, to control whether to divide by 2 or not, the upper 2 bits of the input data of the stage 33 are input to the maximum value detection circuit 71, the condition of equation (4) is detected, and the output is sent to the flip-flop circuit 67.
The scaling circuit 70 outputs a block floating point arithmetic signal (scaling signal) 72 by latching it at
This is done by applying the signal to the overflow prevention circuit 55 (FIG. 5) of the corresponding stage. At the same time, using the output of the scaling circuit 70, only when the output data of the stage is divided by 2, the contents of the counter 73 as an adder circuit of the stage 33, that is, the scale factor, is incremented by one step. This scale factor is propagated through the counters 73 of each stage in synchronization with the data flow. Therefore, the scale factor 26 that is finally output is FFT
This indicates the number of times divided by 2 during calculation, so
This becomes an exponential display amount with base 2 and forms the exponential part of the frequency spectrum. Therefore, during accumulation, the spectrum of the mantissa part is normalized by this scale factor and then accumulated.

A specific example of the scale ring circuit 70 is shown in FIG. In other words, the top two of the calculation results from the previous stage
The bits, that is, the sixth and seventh bits D ₆ and D ₇ are input to an exclusive OR circuit (EXNOR) 75, the output of which is supplied to a D-type flip-flop 77 through a NOR circuit 76, and is clocked by a clock 78 for each data. Read. That flipflop 7
The output of 7 is fed back through a NOR circuit 76.
Therefore, when the data A _k and B _k are outside the range of -64<A _k , B _k <63, the output of the circuit 75 becomes "1", the output of the flip-flop 77 becomes "1", and this state is maintained. . When the value becomes "1", the counter 73 is incremented by one step. Every time data for one frame (1024 samples in this example) is taken in, the contents of the counter 73 in the previous stage are latched in the counter 73 by the clock 79, and the output of the flip-flop 77 is latched in the flip-flop 67. The Q output of the flip-flop 67 is output as a block floating point arithmetic control signal 72. The inverted signal of clock 79 presets flip-flop 77 to zero.

From buffer memory 19 to FFT processor 21
Creation of the scale factor when inputting it to is performed as shown in FIG. 9, for example. That is, AD converter 1
The upper 4 bits D ₈ , D ₉ and D ₇ , D ₉ of the 10 bits D ₀ to D ₉ (D ₉ is the most significant bit) from 5 are supplied to exclusive OR circuits 83 and 84, respectively, and these circuits The outputs of circuits 83 and 84 are supplied to an AND circuit 85, and the outputs of circuits 83 and 85 are supplied to NOR circuits 86 and 87 through inverters, respectively.
The outputs of the NOR circuits 86 and 87 are sent to the flip-flops 88 and 88 for each data by the clock 78, respectively.
89, this flip-flop 88,8
The respective outputs of 9 are fed back to NOR circuits 86 and 87, respectively. Therefore, if the input data is 512 or more, the output of the flip-flop 88 becomes "1", and if the input data is 255 or more, the output of the flip-flop 89 becomes "1". These flip-flops 88 and 89 are input into flip-flops 91 and 92 by the clock 79 for each frame, and the outputs of the flip-flops 91 and 92 are decoded by the decoder 62, and the outputs of the three output lines 63 are input according to the three states. becomes “1”. The outputs of the flip-flops 91 and 92 are also supplied to an exclusive OR circuit 93 and a NOR circuit 94. When the input data is 512 or more, the output of the circuit 93 is "1", the output of the circuit 94 is "0", and the input data is 255 ~511, the output of the circuit 93 is "0", the output of the circuit 94 is "1", and when the input data is 254 or less, the output of the circuit 93,
94 are each "0". These circuits 93,
The output of 94 is preset in the counter 73 for each frame with the latter as the least significant bit, that is, either decimal 2, 1, or 0 is preset depending on the state of each input data. This buffer memory 1
The counter (addition circuit) 73 for each stage 33 is connected as the first stage of the cascade connection of counters (addition circuits) for each stage 33.

In FIG. 3, a register can be interposed between each counter 73 as necessary to prevent the contents of the initial stage counter from racing all at once to the final stage counter.

FIG. 10 shows a time chart in a specific example of FFT processing for the AE signal. In the figure, data of the first frame #1 of the AE signal in FIG. 10A, for example, is written to the buffer memory 19 in section 1 of the time scale (FIG.
After window calculation is performed at the window calculation stage 32 as shown in FIG. Since this spectrum is a folded spectrum peculiar to FFT calculation, only the first half of the spectrum is converted as a power spectrum in section 13 (FIG. 10D). Then accumulator 23 (Fig. 1)
The accumulation is repeated, and the accumulated power spectrum is output in section 17 where all calculations for one event have been completed (FIG. 10E).

Figure 11 shows an example of the spectrum of an AE signal when this invention is applied and when it is not applied.
is the spectrum of the AE signal obtained by frame division and automatic scaling, Figure B is the spectrum obtained when 8192-point FFT is performed without frame division, and Figure C is the spectrum obtained without automatic scaling. This is a spectrum obtained by 14-bit fixed-point arithmetic FFT. From the above example, it was understood that the features of the AE signal spectrum are not lost even with the frame division method, and the minute vibrations seen in Figure B are also suppressed, making it easier to distinguish the features. .

As described above, according to the present invention, the 8-bit data word length can be easily expressed in the characteristics of the input signal spectrum, and by adding the automatic scaling circuit 25.
FFT is comparable to 14-bit fixed-point arithmetic FFT,
Although the hardware scale is relatively small, it is possible to operate on data with a long data word length. In addition, in this invention, each stage generates a scaling signal when it is predicted from the input data that an overflow will occur in the calculation at that stage. In comparison, calculations can be performed at high speed. Therefore, as in the embodiment described above, it is possible to perform real-time frequency analysis of a wideband AE signal in which the amplitude and duration vary greatly for each event, and the frequency components are up to 1 MHz.

As shown in FIG. 1, the envelope of the frequency spectrum of the AE signal analyzed in this manner was compared with a standard pattern previously stored in the standard memory 34 by a comparator 35, and micro-fractures were detected. or if it is greater than or equal to a predetermined value, the alarm 36
display or issue a warning. When the output of the accumulator 23 is stored in the memory 24, the time signal of the time signal generator 18 is also stored in the memory 24 so that the elapsed time of the generated spectral power can be seen. If the comparator 16 is used to store the AE signal only when it is obtained, the memory 24 can be effectively used by the output of the comparator 16. The automatic scaling circuit 25 of the present invention can be applied not only to frequency analysis of AE signals but also to general FFT.

[Brief explanation of drawings]

Fig. 1 is a block diagram showing a configuration example of a microscopic fracture detection device to which the present invention is applied, Fig. 2 is a schematic diagram of dividing an AE signal into frames, and Fig. 3 is an example of a fast Fourier transform processor according to the invention. 4 is a block diagram showing an example of the buffer memory 19, FIG. 5 is a block diagram showing an example of the FFT stage 33, and FIG. 7 is a diagram showing an example of the contents of the instruction shown in FIG. 6, FIG. 8 is a logic circuit diagram showing a specific example of the scaling circuit 70 in the calculation stage, and FIG. 9 is a scaling circuit at the input of the buffer memory. 10 is an operation time chart of the entire device shown in FIG. 1. FIG. 11A is a diagram showing an example of the spectrum of the AE signal obtained by the example. Figure B shows an example of a spectrum when FFT is performed at 8192 points without frame division, and Figure 11C shows an example of a spectrum when FFT is performed with a word length of 14 bits using fixed-point arithmetic without the automatic scaling circuit 25. FIG. 3 is a diagram showing an example of a spectrum when 19: Buffer memory, 21: FFT processor, 24: Output memory, 25: Automatic scaling circuit, 26: Exponent output, 32: Wind calculation stage, 33: Butterfly calculation stage, 41:
Butterfly operation unit, 44: twiddle factor memory, 60: bit conversion circuit, 70: scaling circuit, 71: maximum value detection circuit, 72: scaling signal, 73: addition circuit.

Claims (1)

[Claims] 1. In a block floating point arithmetic fast Fourier transform processor in which a plurality of stages each having a butterfly arithmetic circuit and two data input/output memories are connected in series, the upper two bits of the input data are sent to each stage. A scaling circuit and an addition circuit each having a maximum value detection circuit 71 as an input are provided, and these addition circuits are connected in series, and the maximum value of data within one frame at each stage input is detected by the maximum value detection circuit 71. detects the overflow of the butterfly operation in that stage, outputs a scaling signal to prevent the overflow from the scaling circuit to that stage, increases the content of the adder circuit in that stage by 1, and A fast Fourier transform processor that has an automatic scaling device that inputs the output of the adder circuit as a scale factor to the adder circuit in the next stage and obtains the exponent part of the spectral output data in the fast Fourier transform processor as the final output result of the scale factor. .