Last time, we explained the Fast Fourier Transform (FFT), but since the FFT is simply a method for performing the Discrete Fourier Transform (DFT) at high speed, this time we will continue to discuss various properties of the DFT. Note that in the following explanation, we will assume that DFT calculations are performed using the FFT.
As explained in the previous article (Frequency Analysis from the Basics (8) "Discrete Fourier Transform (DFT)"), by performing a DFT on the time signal xn at N points, we can obtain the frequency function Xk at the same N points. Furthermore, both the time signal and the frequency function are periodic functions with N points as one period (see Figure 1).
-
Figure 1 shows the N-point frequency function Xk obtained by DFT of the N-point time function xn.
The definition of DFT is shown again.
................................（1）
Here, n = 0, 1, ..., N-1, k = 0, 1, ..., 1, N-1
As explained with the complex Fourier series, the Fourier transform reveals both positive and negative frequencies, but in the DFT, as is clear from the figure, the latter half of the points corresponds to negative frequencies. If we write the frequency function X k as X(k):
X(Nk)= X*(k) ................................(2)
Here, * represents the complex conjugate.
The proof of equation (2) is that x and n are real numbers;
That is, the frequency function X k The complex number data sequence is symmetric in its real part with respect to k = N/2, and its imaginary part is symmetric.
The two are point-symmetric, or, with respect to k = N/2, their absolute values are the same, but their phases are opposite in sign only.
(Note that the diagram at the bottom of Figure 1 shows absolute values.)
As can be understood from the sampling theorem in "Sampling of Time Signals" (EMM No. 136),
From the time data of N points, we can obtain complex frequency data for N/2 points.
Figure 2 shows that by performing DFT (FFT) on time data at N = 64 points, the frequency data at N points is obtained.
The result is a complex number, representing a sequence of data with positive and negative frequencies.
-
Figure 2 shows the data sequence in the frequency domain in DFT (FFT) (example with N = 64).
The actual DFT calculation method is as follows: In equation (1), the time function x n It is treated as complex number data.
Since time data is usually a real number, we add zeros to the imaginary part to convert it into complex time data for N points.
The calculation is being performed.
By utilizing these DFT-related functions and properties, we can perform a single DFT (FFT) on 2-channel real-time data.
This section introduces methods for efficiently performing calculations.
For real-time functions x(n) and y(n) of two N points, we define the following complex-time function z(n).
................................（3）
The DFT on the right-hand side of equation (3) is, by its linearity property, as follows:
.................................（4）
The DFT results obtained from actual calculations:
.................................（5）
Therefore, comparing equation (4) and equation (5)
.................................（6）
.................................（7）
It can be seen that this is the case.
Since both the time functions x(n) and y(n) are real numbers, their frequency data satisfy the complex conjugate relationship in equation (2), and from equation (6):
Also, from equation (7):
From this result, the DFT X(k) of the time function x(n) is:
................................（8）
Here, k = 0, 1, ..., N / 2
Furthermore, the DFT Y(k) of the time function y(n) is:
.................................（9）
Here, k = 0, 1, …, N / 2
It will be.
Thus, by performing the operations of equations (8) and (9) at the end after the FFT calculation, when it is 2ch
The DFT of the inter-function can be performed in a single FFT. Furthermore, from this, the complex number time of N points can be calculated.
From the intervening data, it can be understood that effective complex frequency data for N points can also be obtained.
Furthermore, the 1-channel time data of 2N points is decomposed into the first half and the second half (or even and odd value parts).
Considering this as a real part and an imaginary part, we obtain N points of complex time data, and then the 2N points of time data.
Another method is to obtain the DFT using a single N-point FFT.
Next time, we'll use DFT to explain how an FFT analyzer calculates a function on the frequency axis.
Let me explain how to do it.
Finally, here's a summary.
- By performing a DFT on the time signal xn at N points, we obtain the frequency function Xk at the same N points. Both the time signal xn and the frequency function Xk are periodic functions with N points as one period.
- In DFT, the first half of the N frequency data points corresponds to the positive frequency domain, and the second half corresponds to the negative frequency domain.
This will be in the range of several domains. - Frequency function X k The complex number data sequence has a real part that is symmetric with respect to k = N/2, and an imaginary part.
The part is point-symmetric, or, with respect to k = N/2, the absolute values are the same and the phase is only the sign.
The opposite is true. - Using the properties of DFT, there are methods to perform FFT on 2 channels of real-time data in one pass, and 1 channel
Efficient calculations such as obtaining time data for 2N points in a single N-point FFT
Yes, it is possible.
【keyword】
DFT (Discrete Fourier Transform), FFT (Fast Fourier Transform), complex conjugate, sampling theorem
[Reference materials]
- "The Fast Fourier Transform" by E. Oran Brigham, published by Science and Technology Press.
- "Digital Fourier Analysis (I) - Fundamentals" by Kenichi Kido, published by Corona Publishing Co.
(Excerpt from the email newsletter issued on July 19, 2013)
