# Implementation of Fast Fourier Transform (FFT) and Inverse Fast Fourier Transform (IFFT) in Python: Full Code in Python Implementation of Fast Fourier Transform (FFT) and Inverse Fast Fourier Transform (IFFT) in Python: Full Code in Python

What is FFT?
1. FFT stands for Fast Fourier Transform.
2. It is an algorithm that is used to calculate the discrete Fourier transform of a sequence.
3. It is more efficient and reduces the computational time significantly.
4. It converts time domain to frequency domain.
What is IFFT?
1. IFFT stands for Inverse Fast Fourier Transform.
2. It undoes the working of the Discrete Fourier Transform.
3. It is an algorithm that performed inverse or backward Fourier transform.
4. It transforms the time or space signal to the frequency domain.
Code:
import math

def two_point(x, y, tf, inverse=False):

if not inverse:

X = x + tf*y; Y = x - tf*y

else:

X = x + y; Y = (x - y)*tf

return X, Y

def fft(x):

x_a, x_b = two_point(x[ 0], x, 1); x_c, x_d = two_point(x, x, 1) x0, x2 = two_point(x_a, x_c, 1);

x1, x3 = two_point(x_b, x_d, complex(0, -1))

return x0, x1, x2, x3

def ifft(x):

x  = list(map (lambda y: y/4, x)); x_a, x_c = two_point(x, x, 1, True)

x_b, x_d = two_point(x[ 1], x, complex(0, 1), True)

x0, x2 = two_point(x_a, x_b, 1, True); x1, x3 = two_point(x_c, x_d, 1, True)

return x0, x1, x2, x3 if __name__ == '__main__':

x  = [2, 3, 4, 5]; fft_x = fft(x)

print("Original Signal: ", x); print("FFT: ", fft_x)

ifft_x = ifft(fft_x); print("IFFT of x: ", ifft_x)

Output:
Original Signal: [2, 3, 4, 5]

FFT: (14, (-2+2j), -2, (-2-2j))

IFFT: ((2+0j), (3+0j), (4+0j), (5+0j))

Applications: