Frequency Analysis from the Basics (8) "Discrete Fourier Transform (DFT)"

This time, building on what we've discussed so far (Fourier series, Fourier transform, sampling, etc.), we'll talk about the Discrete Fourier Transform (DFT), a fundamental operation in digital signal processing.

Figures 1-1 and 1-2 are explanatory diagrams for deriving the discrete Fourier transform, including the relationship between the time domain and the frequency domain discussed so far. Similar to Figure 3 in the previous installment of this series (Measurement Column emm136), in Figure 1-1, the left-hand figure of the Fourier transform pair represents the time domain and the right-hand figure represents the frequency domain, while in Figure 1-2, the upper figure of the Fourier transform pair represents the time domain and the lower figure represents the frequency domain.

First, the time signal x (t The Fourier transformed frequency spectrum of (Figure 1-1 (a)) X (f) (Figure 1-1 (b)) is the maximum frequency f _m Let's assume that bandwidth is limited. X (t) is sampled with a sampling period τ (sampling frequency 1/τ) to obtain discrete signals. x_τ (t If we assume (Figure 1-1 (c)), then the Fourier transform is X_τ (f The result is a spectrum that repeats at a frequency of 1/τ, as shown in (d) of Figure 1-1.

Next, if the time signal x (t) is a signal of finite length T, or if we cut an infinite signal through a time window T to obtain a signal of finite length (this operation corresponds to a time window in an FFT analyzer), and consider it as a time signal that repeats infinitely with period T (Figure 1-2 (e)), then a Fourier series expansion can be applied, and its spectrum will be discretely arranged on the frequency axis at intervals of 1/ T (Figure 1-2 (f)).

To summarize, if we consider a finite-length, continuous time signal as a periodic function, the corresponding function in the frequency domain will be a discrete spectrum. Conversely, if we consider a band-limited, continuous frequency function as a periodic function, the corresponding time signal will be a discrete signal (a sampled time signal).

Figures 1-2 (g) and (h) show the Fourier transform of a time signal with a finite time window length T, sampled at a sampling frequency of 1/τ, based on these results. In other words, if we consider a discrete time signal with a finite time window length T as a periodic function, then the corresponding frequency function is also a discrete and finite periodic function.

From this, a sampled finite-time signal can be Fourier transformed, and the result is a finite discrete frequency spectrum, which finally makes the DFT (Digital Fourier Transform) possible using digital signal processing.

Next, we derive the formula for calculating the DFT.

When the time waveform x (t) is sampled with a sampling period τ, the time series is:

x(τ)、x(2τ)、x(3τ)、・・・・、x(nτ)、・・・

This is how it works. This time-series signal can be expressed using the delta function;

.................................（1）

It can be expressed as follows: If we let the Fourier transform of equation (1) be:

.................................（2）

This is how it works. Now, we make the time signal finite. If we let the finite time window length be T, then the sampling period is τ, so there are only N (= T/τ) time data points and we set the rest to 0.

.................................（3）

From now on;

.................................（4）

This is a time signal with periodicity. T If we consider it as a periodic signal, the fundamental frequency is 1/ T Since it is discretized, the fundamental frequency is f₀ (= 1/ T If we let ), then equation (4) ultimately becomes:

.................................（5）

It can be transformed as follows. Equation (5) is called the Discrete Fourier Transform (DFT) of the sampled time signal. From a discrete and finite (and periodic) time signal with N points, the DFT operation yields a discrete and finite (and periodic) frequency function with N points.

Next, to find the inverse operation of the DFT, we multiply both sides of equation (5) and integrate with respect to the discrete frequency k.

...........................（6）

Here, due to the orthogonality of the complex exponential function;

Therefore, we only need to consider the case where m = n, and the right-hand side of equation (6) ends up being:

from now;

.................................（7）

Equation (7) is the definition of the Inverse Discrete Fourier Transform (IDFT).

Here, for the sake of brevity, equations (5) and (7) are:

.................................（8）

.................................（9）

This can be expressed as follows: Equation (8) is the Discrete Fourier Transform (DFT), and Equation (9) is the Inverse Discrete Fourier Transform (IDFT). Both equations are a pair of Discrete Fourier Transforms.
It is important to note here that both the time function xn and the frequency function Xk are periodic functions with N points representing one period. Also, although no special mathematical approximations are used to derive the Discrete Fourier Transform from the standard Fourier Transform, significant constraints are assumed in order to utilize the DFT. These constraints are the discretization and finiteization of the time function.
Regarding the first discretization, as explained previously, in order to correctly determine the frequency function of the sampled time signal, the frequency components must be band-limited. For this reason, FFT analyzers are equipped with anti-aliasing filters, and the frequency function is inevitably finite.

Regarding the second finiteization, while it's true that numerical calculations often require handling only finite data, discretizing frequency domain functions also requires cutting even infinite time functions into finite segments and treating those finite data as repeating periodic functions (this cutting is omitted in Figure 1-2). In FFT analyzers, this operation of cutting the time signal into finite segments is called applying a time window. The error caused by this finiteization operation is one of the most important things to pay attention to when using an FFT analyzer. The error and usage of this time window will be discussed later.

By taking these points into consideration when using it, the Discrete Fourier Transform (DFT) can produce results that are almost identical to those of the Continuous Fourier Transform, making it a very practical and powerful computational method in the field of digital signal processing.

Finally, here's a summary.

1. A continuous time function without periodicity can be transformed into a continuous frequency function (Fourier transform).
2. The Fourier transform of a discretized time function is a periodic continuous frequency function (discrete-time Fourier transform).
3. The Fourier transform of a periodic, continuous time function is a discrete frequency function (Fourier series expansion).
4. The Fourier transform of a discretized and periodic (finite) time function is similarly discretized and periodic (finite) frequency function on the frequency axis (Discrete Fourier Transform).
5. The Discrete Fourier Transform (DFT) of N-point digital time data also results in N-point frequency data on the frequency axis, and both are periodic functions that repeat with period N.

【keyword】
Fourier series, Fourier transform, sampling, discrete Fourier transform, DFT, frequency spectrum, sampling period, sampling frequency, inverse discrete Fourier transform, IDFT, discrete Fourier transform pair, anti-aliasing filter, time window

------------------------------------------

[Reference materials]

1. "The Fast Fourier Transform" by E. Oran Brigham, published by Science and Technology Press.
2. "Digital Fourier Analysis (I) - Fundamentals" by Kenichi Kido, published by Corona Publishing Co.
3. "Signal Processing" by Iwao Morishita and Hidefumi Obata, published by Asakura Shoten.

(Excerpt from the email newsletter issued on March 22, 2013)