[PYTHON] Properties of the discrete Fourier transform
table of contents
1.First of all --Derivation of discrete Fourier transform --The nature of the discrete Fourier transform --References --Appendix: Program of Discrete Fourier Transform by Python
1.First of all
The purpose of this article is to understand the properties of the discrete Fourier transform, such as spectral symmetry and periodicity.
2. Derivation of discrete Fourier transform
The discrete signal $ x_ {sampling} (t) $ obtained by sampling the continuous-time signal $ x (t) $ at the interval $ T $ is expressed as follows.
\begin{eqnarray}
\mathcal{F}[x_{sampling}(t)] &=& \int_{-\infty}^{\infty}x_{sampling}(t)e^{-j\omega t}dt \\
&=& \int_{-\infty}^{\infty} \, \sum_{n=0}^{\infty}x(n)\delta(t-nT) \, e^{-j\omega t}dt \\
&=& \sum_{n=0}^{\infty}x(n)\int_{-\infty}^{\infty}\delta(t-nT) \, e^{-j\omega t}dt \\
&=& \sum_{n=0}^{\infty}x(n) e^{-j\omega nT} \tag{2}
\end{eqnarray}
It will be.
Now suppose the sample value $ x (n) $ consists of $ N $ points. Also, as shown in the figure below, the sample value $ x (n) $ consisting of $ N $ points is regarded as one cycle of the signal. The angular frequency at this time is expressed as $ 2 \ pi / NT $ and is called the basic angular frequency.
The angular frequency, which is an integral multiple of the basic angular frequency, is represented by $ \ omega = \ frac {2 \ pi} {NT} k ; ; (k = 0,1,2, ..., N-1) $. Represents higher frequency components. Substituting this $ \ omega = \ frac {2 \ pi} {NT} k $ into the $ (2) $ expression
The discrete Fourier transform of the $ (4) $ equation means that it calculates the similarity between the sample value $ x (n) $ and the complex variable $ W ^ {kn} $. As shown in the figure below, the frequency component of the sample value $ x (n) $ is obtained by taking the inner product of the sample value $ x (n) $ and the complex variable $ W ^ {kn} $ with different frequencies. I can. However, due to the nature of the discrete Fourier transform, frequency components may appear in places other than the original frequency components of the sample value $ x (n) $. (Described in 3. Properties of Discrete Fourier Transform)
3. Properties of the discrete Fourier transform
-** Spectrum periodicity **
Let m be an arbitrary integer
\begin{eqnarray}
X(k+mN) &=&\sum_{n=0}^{N-1}x(n)W^{(k+mN)n} \\
&=&\sum_{n=0}^{N-1}x(n)W^{kn}W^{mNn} \\
&=&\sum_{n=0}^{N-1}x(n)W^{kn}
= X(k)
\end{eqnarray}
Next,
-** Spectrum symmetry **
\begin{eqnarray}
X(N-k) &=& \sum_{n=0}^{N-1}x(n)W^{(N-k)n} \\
&=& \sum_{n=0}^{N-1}x(n)W^{Nn}W^{-kn} \\
&=& \sum_{n=0}^{N-1}x(n)W^{-kn} \\
&=& [\,\sum_{n=0}^{N-1}x(n)W^{kn}\,]^{*} = X(k)^{*}
\end{eqnarray}
Next,
-** Frequency spectrum obtained by discrete Fourier transform **
Now, in order to deepen our understanding of the properties of the discrete Fourier transform, let's observe the spectrum obtained by the actual discrete Fourier transform. Perform the discrete Fourier transform using the program shown in the appendix. The continuous-time signal $ x (t) = cos (2 \ pi ft) $ shown in the figure below is sampled. The frequency $ f $ of the continuous-time signal $ x (t) $ is $ 1000 [Hz] $.
First, the following figure shows the signal $ x (n) $ sampled under the sampling frequency $ f_ {sampling} = 4000 [Hz] $ and the number of samples $ N = 32 $ for the continuous-time signal $ x (t) $. It is shown in.
Next, the frequency spectrum obtained by the discrete Fourier transform of the sample value $ x (n) $ is shown in the figure below. From the figure, you can see that the component of $ 1000 [Hz] $, which is the frequency of the continuous-time signal $ x (t) $, appears. However, due to the spectrum symmetry shown in the $ (6) $ equation, a line-symmetric spectrum is generated around $ 2000 [Hz] $, which is half the sampling frequency. This means that less than half the sampling frequency can be represented correctly. The sampling theorem states that the original signal can be demodulated by sampling at least twice the maximum frequency of the continuous-time signal $ x (t) $. The "more than double the frequency" of the sampling theorem is due to the symmetry of the discrete Fourier transform.
4. References
--Morikita Publishing "Digital Signal Processing" by Masafumi Hagiwara --Kodansha "Introduction to Shannon's Information Theory" Author: Eiko Takaoka -[NumPy] Calculate amplitude spectrum by Fast Fourier Transform (FFT)
Appendix: Program of Discrete Fourier Transform by Python
DFT.py
import numpy as np
import cmath
import matplotlib.pyplot as plt
f_xn = 1000 #Input signal x(n)Frequency of
f_sampling = 4000 #Sampling frequency
T = 1.0 / f_sampling #Sampling interval
N = 32 #The number of samples
t = np.arange(0, N*T, T) #Time axis
width = 3 #Frequency axis display width(How many times the sampling frequency is displayed)
freq = np.linspace(0,f_sampling*width, N*width, endpoint=False).reshape([-1,1]) #Frequency axis
n = np.arange(N) #Sum index
k = np.arange(N*width).reshape([-1,1]) #index of k
x_n = np.cos(2*np.pi*f_xn*t) #Sample value x(n)
W_kn = np.exp(-1j*2*np.pi*n/N *k) #Complex variable W_kn
X_k = np.sum(x_n*W_kn, axis=1) #Sum
amp = np.abs(X_k) #Amplitude component
#graph display
plt.figure()
plt.rcParams['font.family'] = 'Arial'
plt.rcParams['font.size'] = 17
plt.subplot(2,1,1)
plt.plot(t, x_n, marker='o', color='r')
plt.xlabel("time[s]", fontsize=20)
plt.ylabel("x(n)", fontsize=20)
plt.grid()
plt.subplot(2,1,2)
plt.plot(freq, amp, marker='o',color='b')
plt.xlabel('frequency[Hz]', fontsize=20)
plt.ylabel('amplitude', fontsize=20)
plt.grid()
plt.subplots_adjust(wspace=0.4, hspace=0.4)
plt.show()
Recommended Posts