JPH08211110A - Two stage fast fourier transform - Google Patents

Abstract

(57) [Abstract] [Purpose] Even when the size of the fine FFT is small, the increase in the folding level is suppressed without increasing the processing time. [Configuration] An extra phase rotation of π is applied to the output time series of the coarse FFT 4 by the phase compensation amount calculation means 20 and the multiplier 5, and the fine FFT 6 is performed on it. As a result, the analysis frequency of the fine FFT 6 is shifted by ½ of the analysis width, and the bin division at the end of the fine FFT 6 matches the bin division of the coarse FFT 4. Therefore, even when the size of the fine FFT 6 is small, the folding level does not increase.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a two-stage fast Fourier transform method (for example, a narrow band signal frequency detecting device for detecting the center frequency of a narrow band signal containing noise) of a signal ( Two-step Fast Fourier Transform;
Hereinafter, it will be referred to as a two-stage FFT).

[0002]

2. Description of the Related Art Conventionally, techniques in such a field include:
For example, some documents were described in the following documents. Reference; AD Report 785 850, (1974) Na
val Underwater Systems Center (US) Albert H. Nutt
all “An Approximate Fast Fourier Transform Techniq
The ue for Vernier Spectral Analysys "two-stage FFT is known as an approximation method of a relatively large size Fast Fourier Transform (FFT) as described in the above-mentioned document. This two-stage FFT is applied to an input signal. On the other hand, after performing a Fourier transform to obtain an analysis result that is wider than the finally required analysis width called a spectral delay function, the Vernier frequency analysis is performed on the time series of each frequency bin of the output. The Fourier transform is called FFT.
The former is called a coarse FFT and the latter is called a fine FFT.
First, the principle of the conventional two-stage FFT will be described, and then the configuration example of the narrowband signal frequency detection device using the conventional two-stage FFT technique will be described. The principle of the two-step FFT is as follows. First, the input signal x sampled at the sampling interval T
For (t), the discrete Fourier transform and spectrum delay function defined by the following equation (1) are calculated for each frequency.

[0003]

[Equation 1] Expression (1) is repeatedly executed at time intervals S, and k is incremented for each cycle. That is, the delay of the time window function w with respect to x increases by S per cycle. For example, if S = NT / 2, it can be seen that the samples calculated in the next cycle have 50% overlap. By the way, the time window function w (nT)

[Equation 2] Then, the equation (1) can be transformed into the following equations (2) to (4).

[0004]

(Equation 3) From this, the actual calculation of equation (4) is w (mT) x
This can be realized by multiplying the time series of (mT + kS) by N-point FFT and multiplying by the phase compensation term exp (-j2π (p / N) (kS / T)). This FFT is called a coarse FFT.
Further, this phase compensation term is (−1) ^pk when S = NT / 2 (50% overlap) and (−j) ^pk when S = NT / 4 (75% overlap), which facilitates calculation. For,
Generally, such a value of S is selected. Then (4)
Vernier frequency analysis is performed using the time series of the calculation results of the formula. If the vernier frequency analysis width is 1 / MS, the vernier spectrum Y to be obtained is obtained by the following equation (5) using the result X of the equation (4) by using time series M points for each frequency p / NT. .

[Equation 4] The actual calculation of the equation (5) is realized by multiplying the time series of d (kS) X (p / NT) by the M point FFT. This FFT is called a fine FFT. According to the above principle, the same result as the normal FFT can be obtained by performing the FFT twice. FIG. 2 shows the above two-stage FFT.
FIG. 11 is a block diagram showing a configuration example of a conventional narrowband signal frequency detection device using the principle of FIG. This narrow band signal frequency detecting device uses a sensor 1 for detecting a signal transmitted from a narrow band signal source.
It is a device for estimating the frequency of a narrow band signal received by the signal source and emitted by the signal source. Note that, in FIG. 2, in order to simplify the explanation, the coarse FFT is realized by an 8-point FFT, and the fine FFT is realized by a 16-point FFT, and the overlap rate of the coarse FFT is 50%.
And The narrow band signal frequency detection device has a sensor 1 that receives a signal transmitted from a narrow band signal source, and the sensor 1 includes an analog / digital converter (hereinafter, referred to as an A / D converter) 2 and A frequency analyzer 4 that performs coarse FFT is connected via the multiplier 3. A power calculator 7 is connected to the output side of the frequency analyzer 4 via four multipliers 5 and four frequency analyzers 6 that perform precise FFT, and further, an integrator 8 is connected to the output side thereof. And a peak frequency detector 9 are connected. A switch for selecting a phase compensation matrix VI ₀ or VI ₁ (where V represents a matrix; hereinafter, similarly, a V is added to the beginning to represent a matrix code) on the input side of the multiplier 5. 10 are provided. On the output side of the switch 10, the phase compensation matrix VI ₀ or V
A multiplier 11 for multiplying I ₁ by a time window function VD is connected, and an output side of the multiplier 11 is connected to an input side of the multiplier 5.

Next, the operation will be described. The signal x (t) received by the sensor 1 is input to the A / D converter 2 where it is quantized and sampled at a sampling period T, and a sampled value sequence x
(NT) (n = 0, 1, ...) Is output. As the output of the A / D converter 2, eight samples are selected at time intervals S and 50% overlap, and are input to the multiplier 3. Assuming that one cycle is x = (x ₀ , x ₁ , ..., X ₇ ) ... (6), in the multiplier 3, the time window function w ^T = (w ₀ , w ₁ , ..., W ₇₎ ^T ··· ₍₇₎ However, T; transpose and x is _{^{multiplied, w T x = (w 0}} x 0, ..., w 7 x 7) T ··· (8) is output. The frequency analyzer 4 performs an 8-point FFT on the output of the multiplier 3 and outputs a positive frequency spectrum from the result.

(Equation 5) Is output to the multiplier 5. Where (p / 8T) is the coarse FF
It is a representative frequency of the T output and is the center frequency of each frequency bin. On the other hand, the switch 10 alternately selects the phase compensation matrix VI ₀ or VI ₁ of the following equations (10) and (11) for each cycle and inputs them to the multiplier 11.

[0006]

(Equation 6) The multiplier 11 multiplies the output VI ₀ or VI ₁ of the switch 10 by the time window function VD of the following equation (12), and outputs the product to the multiplier 5.

[0007]

(Equation 7) In the multiplier 5, the output of the frequency analyzer 4

(Equation 8) On the other hand, the output of the multiplier 11 is multiplied from the right. That is, VX
Let {VX ₀ , VX ₁ , VX ₂ , ...} be the time series of the output of the multiplier 5 is {VX ₀ · VD · VI ₀ , VX ₁ · VD · V
I ₁ , VX ₂ , VD, VI ₀ , ...}. The time series of the output of the multiplier 5 is input to the frequency analyzer 6 for 16 cycles for each coarse FFT frequency bin. In the frequency analyzer 6, 16-point FFT is performed for each coarse FFT frequency bin.

[Equation 9] Is sent to the power calculator 7. The power calculator 7 calculates the instantaneous power for each fine FFT frequency bin of the output of the frequency analyzer 6, and sends it to the integrator 8. The integrator 8 obtains the long-term integrated power of each fine FFT frequency bin by integrating the instantaneous power, and outputs it to the peak frequency detector 9.
The peak frequency detector 9 selects one or a plurality of maximum signal-to-noise ratios (S / N ratios) in the long-term integrated power and outputs the selected frequency as the frequency of the estimated narrow band signal. .

[0008]

Generally, in FFT, out-of-band leakage occurs due to truncation in the time domain, so that sampling results inevitably suffer from aliasing.
The effect of aliasing within one bin of the FFT output can be reduced by applying an appropriate window function to suppress leakage. However, the conventional two-stage FFT has the following problems and it is difficult to solve them. FIG. 3 is a 1-bin pass characteristic diagram of the coarse FFT output for explaining the problems of the conventional technique. As shown in FIG. 3, the bandwidth used as a result of the fine FFT is 1 / (2M
S) (i.e., 1/2 of the analysis width of the fine FFT), and the level of folding is increased in the fine FFT frequency bin at the shifted end. In particular,
When the size of the fine FFT is small, the increase in folding level due to this band shift has a non-negligible effect on the result. By increasing the overlap rate and shortening the output interval of the coarse FFT (that is, the input interval of the fine FFT), the influence of aliasing can be reduced, but the processing time greatly increases and it is not realistic. The present invention has solved the problem that the above-described conventional art has, that it is difficult to reduce the influence of folding back without increasing the processing time.
It provides a staged FFT.

[0009]

In order to solve the above-mentioned problems, the present invention obtains, for an input signal, an analysis result called a spectrum delay function, which is wider than the finally required analysis width. After performing the coarse FFT, the two-stage FFT for performing the frequency analysis of the input signal by performing the fine FFT called Vernier frequency analysis on the time series of each frequency bin of the coarse FFT output is performed by the following means. I am taking it. That is, the phase compensation amount that gives an extra rotation of π in the time series of the coarse FFT output is calculated. Then, the phase compensation amount is multiplied by the time series of the coarse FFT output, and the fine FFT is performed on the multiplication result.

[0010]

According to the present invention, since the two-stage FFT is constructed as described above, when the phase compensation amount is calculated and multiplied by the output time series of the coarse FFT (that is, the input time series block of the fine FFT). , An extra phase rotation is given to the output time series of the coarse FFT by π, the analysis frequency of the fine FFT (that is, the bin position of the fine FFT) is shifted by ½ of the analysis width, and The edge bin breaks now match the coarse FFT bin breaks. As a result, the fine FF
Even if the size of T is small, the increase in the turnback level is suppressed. Therefore, the above problem can be solved.

[0011]

EXAMPLE First, the principle of this example will be described with reference to FIG. FIG. 4 is a diagram showing the relationship between each data in one block, that is, the input data of the fine FFT, and the phase shift amount. In this embodiment, in the two-stage FFT, the fine FFT
In order to shift the analysis frequency of (1) by 1/2 of the analysis width, an extra phase rotation of π is given to the input time series block of the fine FFT (that is, the output time series of the coarse FFT). As a principle of this, if the discrete Fourier transform of y (kT) is Y (p / NT), this Y (p / N)
To shift T) to 1 / 2NT higher frequency,
From the following equations (14) and (15), the phase shift of rotating the entire data of one book by π, that is, exp (-j
It is understood that the multiplication of π (k / N) should be performed.

[0012]

[Equation 10] Next, FIG. 1 is a block diagram showing an example of the configuration of a narrowband signal frequency detection device using the principle of such a two-step FFT. It should be noted that elements common to the elements in the related art in FIG. 2 are denoted by common reference numerals. This narrowband signal frequency detection device is a device that receives a signal transmitted from a narrowband signal source by the sensor 1 and estimates the frequency of the narrowband signal emitted from the signal source, as in the conventional case. The size of the coarse FFT, the size of the fine FFT, and the overlap ratio can be applied with appropriate arbitrary values, but in this embodiment, the coarse FFT is an 8-point FFT and the fine FFT is 16 points FF
It is realized by T and the overlap rate of the coarse FFT is set to 50%. The narrow-band signal frequency detection device of the present embodiment is similar to the conventional one, in which the acoustic sensor 1, the A / D converter 2, the multiplier 3, the frequency analyzer 4 for performing the coarse FFT, the four multipliers 5, and the fine FF.
It has four frequency analyzers 6 for performing T, a power calculator 7, an integrator 8, and a peak frequency detector 9. The present embodiment is different from the conventional device in that the phase compensation amount calculation means 20 is provided on the input side of the multiplier 5 instead of the conventional switch 10 and multiplier 11 shown in FIG. is there.

FIG. 5 shows the phase compensation amount calculating means 20 in FIG.
FIG. This phase compensation amount calculation means 20 uses the coarse F
When the analysis width of the FT and the size of the coarse FFT are designated, the phase compensation amount is calculated, and the calculation result is given to the multiplier 5, and -jπ is given to each element of (0, 1, 2, 3). And a divider 22 for dividing the output of the multiplier 21 by the size of the coarse FFT (= 8). The output side of the divider 22 is connected to an exponential function calculating means 23 for calculating the value of the exponential function of each element of the output of the divider 22, and the multiplier 2 is connected to the output side of the exponential function calculating means 23.
4 are connected. Further, a switch 25 for selecting either the phase compensation matrix VI ₀ or VI ₁ is provided, and a multiplier 26 is connected to the output side of the switch 25. The multiplier 26 outputs the time window function VD to the output of the switch 25.
And the multiplication result is given to the multiplier 24.

Next, the operation of the narrow band signal frequency detecting device of FIGS. 1 and 5 will be described. First, as in the conventional case, the signal x (t) received by the acoustic sensor 1 is input to the A / D converter 2 to be quantized and sampled at the sampling period T, and the sampled value sequence x (NT) (n = 0, 1, ...) Is output. As the output of the A / D converter 2, eight samples are selected at time intervals S and 50% overlap, and are input to the multiplier 3. Assuming that one cycle is x = (x ₀ , x ₁ , ..., X ₇ ) ... (16), the time window function w ^T = (w ₀ , w ₁ , ..., W in the multiplier 3 ₇₎ ^T ··· (17) and x is _{^{multiplied, w T x = (w 0}} x 0, ..., w 7 x 7) T ··· (18) is output. The frequency analyzer 4 performs an 8-point FFT on the output of the multiplier 3 and outputs a positive frequency spectrum among the results.

[Equation 11] Is output to the multiplier 5. Where (p / 8T) is the coarse FF
It is a representative frequency of the T output and is the center frequency of each frequency bin. On the other hand, in the phase compensation amount calculation means 20, first, the multiplier 21 calculates (0, 1, ..., (Coarse FFT size)).
/ 2-1), that is, each element of (0, 1, 2, 3) is multiplied by -jπ and input to the divider 22. The divider 22 outputs the output (0, -jπ, -2jπ, -3jπ) of the multiplier 21 to the coarse F.
It divides by the size of FT (= 8) and outputs the division result to the exponential function calculating means 23. The exponential function calculating means 23 outputs the output of the divider 22 (0, −jπ / 8, −2jπ / 8, −3).
jπ / 8), the value of the exponential function of each element is calculated, and the multiplier 2
Send to 4. In the switching device 25, the phase compensation matrix VI ₀ or VI ₁ of the following equations (20) and (21) is alternated every cycle.
Is input to the multiplier 26.

[0015]

(Equation 12) The multiplier 26 multiplies the output VI ₀ or VI ₁ of the switch 25 by the time window function VD of the following equation (22), and the multiplier 24
Output to.

[0016]

(Equation 13) In the multiplier 24, the output of the exponential function calculating means 23 is rearranged into a diagonal matrix like the following equation (23), and the multiplier 2 is added to this.
The output of 6 is multiplied and output to the multiplier 5.

[0017]

[Equation 14] The multiplier 5 multiplies the output of the frequency analyzer 4 by the output of the phase compensation amount calculation means 20 from the left and outputs the result to the frequency analyzer 6. That is, the time series of the frequency analyzer 4 is changed to {VX ₀ , VX ₁ ,
VX ₂ , ...}, the output of the multiplier 5 is {VX ₀ · VE
・ VD ・ VI ₀ , VX ₁・ VE ・ VD ・ VI ₁ , VX ₂・ V
E · VD · VI ₀ , ...}. The time series output from the multiplier 5 is input to the frequency analyzer 6 for 16 cycles for each coarse FFT frequency bin. In the frequency analyzer 6, 16-point FFT is performed for each coarse FFT frequency bin.

(Equation 15) Is sent to the power calculator 7. The power calculator 7 calculates the instantaneous power for each fine FFT frequency bin of the output of the frequency analyzer 6, and sends it to the integrator 8. The integrator 8 obtains the long-term integrated power of each fine FFT frequency bin by integrating the instantaneous power, and outputs it to the peak frequency detector 9.
The peak frequency detector 9 detects the S
One or a plurality of maximum N / N ratios are selected and the frequency is output as the frequency of the estimated narrow band signal.

As described above, in this embodiment, the output of the frequency analyzer 4 is phase-shifted by rotating by π by the phase compensation amount calculating means 20 and the multiplier 5, so that the conventional two-stage Even when the size of the fine FFT is particularly smaller than that of the FFT, the folding level does not increase due to the deviation between the demarcation of the coarse FFT and the used band of the fine FFT. The present invention is not limited to the above-mentioned embodiment, and for example,
The phase compensation amount calculation means 20 may be configured using a processor or the like other than that shown in FIG. 5, or the two-stage FFT of the above embodiment.
Is applicable to various devices other than the narrow band signal frequency detecting device of FIG.

[0019]

As described above in detail, according to the present invention, the phase compensation amount is calculated, the phase compensation amount is multiplied by the time series of the coarse Fourier transform output, and the fine Fourier transform is performed on the multiplication result. Since the conversion is performed, the analysis frequency of the fine FFT is shifted by ½ of the analysis width, and the bin boundaries at the ends of the fine FFT match the bin boundaries of the coarse FFT. Therefore, compared to the conventional two-stage FFT, even when the size of the fine FFT is particularly small, the folding level does not increase due to the deviation between the demarcation of the coarse FFT and the used band of the fine FFT.

[Brief description of drawings]

FIG. 1 is a configuration block diagram of a narrow band signal frequency detection device using a two-stage FFT according to an embodiment of the present invention.

FIG. 2 is a configuration block diagram of a narrowband signal frequency detection device using a conventional two-stage FFT.

FIG. 3 is a diagram illustrating a problem of the conventional technique.

FIG. 4 is a diagram showing a relationship between input data of a fine FFT and a phase shift amount according to the embodiment of the present invention.

FIG. 5 is a configuration diagram of a phase compensation amount calculation means in FIG.

[Explanation of symbols]

1 sensor 2 A / D converter 3, 5, 21, 24, 26 multiplier 4 frequency analyzer (coarse FF
T) 6 frequency analyzer (fine FF
T) 7 power calculator 8 integrator 9 peak frequency detector 20 phase compensation amount calculation means 22 divider 23 exponential function calculation means 25 switcher

Continued Front Page (72) Inventor Teruhiko Uki 1-7-12 Toranomon, Minato-ku, Tokyo Oki Electric Industry Co., Ltd. (72) Inventor Shinji 1-7-12 Toranomon, Minato-ku, Tokyo Oki Electric Industry Co., Ltd. In the company

Claims (1)

[Claims] 1. An input signal is subjected to a coarse Fourier transform to obtain an analysis result having a width wider than a finally required analysis width, and then a time series of each frequency bin of the coarse Fourier transform output is obtained. On the other hand, in the two-step fast Fourier transform method of performing the fine Fourier transform to analyze the frequency of the input signal, a phase compensation amount that gives an extra rotation of π to the time series of the rough Fourier transform is calculated, A two-step fast Fourier transform method, characterized in that a time series of the coarse Fourier transform output is multiplied by an amount, and the fine Fourier transform is performed on the multiplication result.