Fourier analysis is a method for expressing a function as a sum of periodic components and recovering the signal from those components. By using this method, we can transform a time domain signal into the frequency domain one and vice versa. A Fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). The DFT is obtained by decomposing a sequence of values into components of different frequencies but computing it naively or directly from the definition is often too slow to be practical. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors. As a result, it reduces the complexity of computing the DFT from O(N2) to O(NlogN) where N is the data size or points to be computed. It may be very complicated for someone to write an FFT algorithm directly but SciPy offers the fftpack module, which lets the user compute fast Fourier transforms very easily. FFT can be multidimensional but here we will learn about one-dimensional FFT.
One-dimensional discrete Fourier Transformation
These transforms can be calculated by means of FFT and IFFT, respectively as shown in the following example.
Python3
# IMPORTING REQUIRED MODULES from scipy.fftpack import fft, ifft import numpy as np # DEFINING INPUT POINTS x = np.array([2.0, 1.0, 4.0, -1.0, -1.5]) # CALCULATING FFT FOR POINTS IN X y = fft(x) # CALCULATING IFFT FOR POINTS IN Y yinv = ifft(y) # CONVERTING RESULT IN LIST AND ROUNDING UPTO TWO DECIMAL PLACE y = [complex(round(elem.real, 2), round(elem.imag, 2)) for elem in y] yinv = [complex(round(elem.real, 2), round(elem.imag, 2)) for elem in yinv] # PRINTING RESULT print("x =", list(x)) print("y =", list(y)) print("yinv =", list(yinv)) |
Output:
x = [2.0, 1.0, 4.0, -1.0, -1.5] y = [(4.5-0j), (-0.58-5.32j), (3.33+3.29j), (3.33-3.29j), (-0.58+5.32j)] yinv = [(2+0j), (1+0j), (4+0j), (-1+0j), (-1.5+0j)]
Discrete Cosine Transform:
A Discrete Cosine Transform expresses a finite sequence of data points in terms of a sum of cosine functions that are oscillating at different frequencies. It is also a widely used transformation technique in signal processing and data compression.
SciPy provides a DCT with the function scipy.fft.dct() and a corresponding IDCT with the function idct. In actuality, there are 8 types of DCT on the basis of different formulas and equations and types of given input but only the first 4 types are implemented in SciPy.
Type 1 DCT is equivalent to the FFT for real, even-symmetrical inputs. The output is also real and even symmetrical. Half of the FFT input is used to generate half of the FFT output using DCT:
Python3
# IMPORTING FILES import numpy as np from scipy.fftpack import fft, dct # INPUT POINTS x = np.array([1., 5., 7., 10., 5., 3.]) # COMPUTED FFT POINTS yfft = fft(x).real x = np.array([1., 5., 7., 10.]) # COMPUTED DCT POINTS ydct = dct(x, 1) print("yfft =", yfft) print("ydct =", ydct) |
Output:
yfft= [ 29. -12. 2. -3. 2. -12.] ydct= [ 35. -11. -1. -5.]
