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. $ x_{sampling}(t)=\sum_{n=0}^{\infty} x(n)\delta(t-nT) \tag{1}$ Fourier transforming this discrete signal $ x_ {sampling} (t) $

\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 $ \sum_{n=0}^{\infty}x(n) e^{-j\frac{2\pi}{NT}knT} $ It will be. Considering that the sample value $ x (n) $ consists of $ N $ points, $ \sum_{n=0}^{N-1}x(n) e^{-j\frac{2\pi}{NT}knT} = \sum_{n=0}^{N-1}x(n) e^{-j2\pi k\frac{n}{N}} \tag{3} $ It will be. For the sake of simplicity, let's say $ W = e ^ {-j \ frac {2 \ pi} {N}} $ $ X(k) = \sum_{n=0}^{N-1}x(n)W^{kn} \tag{4} $ Therefore, we were able to derive the discrete Fourier transform equation.

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, $X(k+mN)=X(k) \tag{5}$ Is established. This means that in the frequency spectrum, the same spectrum appears for each sampling frequency.

-** 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, $X(N-k) = X(k)^{*} \tag{6}$ Is established.

-** 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

Properties of the discrete Fourier transform
Fourier transform of raw data
Let's compare the Fourier transform of the synthesized sound source and the composition of the Fourier transform.
The meaning of self
the zen of Python
The story of sys.path.append ()
How to confirm the Persival theorem using the Fourier transform (FFT) of matplotlib and scipy
Qiskit: Quantum Fourier Transform
The latest version of Pillow 7.0.0 will kill the pytorch transform.
Revenge of the Types: Revenge of types
Align the version of chromedriver_binary
Scraping the result of "Schedule-kun"
10. Counting the number of lines
Towards the retirement of Python2
Get the number of digits
Explain the code of Tensorflow_in_ROS
Reuse the results of clustering
Discrete cosine transform using chainer.links.Linear
GoPiGo3 of the old man
Calculate the number of changes
Change the theme of Jupyter
The popularity of programming languages
Change the style of matplotlib
Visualize the orbit of Hayabusa2
About the components of Luigi
Connected components of the graph
Filter the output of tracemalloc
About the features of Python
Simulation of the contents of the wallet
The Power of Pandas: Python