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

**What is FFT?**

- FFT stands for Fast Fourier Transform.
- It is an algorithm that is used to calculate the discrete Fourier transform of a sequence.
- It is more efficient and reduces the computational time significantly.
- It converts time domain to frequency domain.

**What is IFFT?**

- IFFT stands for Inverse Fast Fourier Transform.
- It undoes the working of the Discrete Fourier Transform.
- It is an algorithm that performed inverse or backward Fourier transform.
- 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[2], 1); x_c, x_d = two_point(x[1], x[3], 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[0], x[2], 1, True)

x_b, x_d = two_point(x[ 1], x[3], 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:**

- Radar.
- Spectrum Analysis.
- Background noise reduction for mobile telephony.
- Speech processing communications.

## 0 Comments

Please Do Not Enter Any Spam Links or Any Spam Text/Images.