Fast Fourier Transform (FFT) Cheatsheet

Cheatsheet Content

FFT: Kya Hai aur Kyu Zaroori Hai? (What is FFT and Why is it Important?) Basic Idea: FFT ek super-fast algorithm hai for computing Discrete Fourier Transform (DFT). DFT kisi bhi signal (time domain data) ko uske constituent frequencies mein break karta hai. Simple terms mein, yeh batata hai ki ek given signal mein kaun-kaun si frequency components kitni strength (amplitude) ke saath maujood hain. Kyu Zaroori: Real-world signals (audio, images, network data) time domain mein hote hain. Unki analysis frequency domain mein karna often easier aur more insightful hota hai. Example: Agar aap noise remove karna chahte hain, toh frequency domain mein particular noise frequency ko target karna aasan hai. Application: Signal Processing, Image Processing, Data Compression (e.g., MP3, JPEG), Medical Imaging (MRI), Telecommunications. DFT (Discrete Fourier Transform): The Core Idea Formula: Given a discrete signal $x[n]$ of length $N$, its DFT $X[k]$ is defined as: $$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j 2\pi k n / N}$$ where $k = 0, 1, \dots, N-1$. Aur Inverse DFT (IDFT) time domain signal wapas laane ke liye: $$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j 2\pi k n / N}$$ Interpretation: $x[n]$: Time domain samples. $X[k]$: Frequency domain components (amplitude aur phase information). $k$: Frequency index. $k=0$ DC component (average value), $k=1$ fundamental frequency, etc. $e^{-j \theta} = \cos(\theta) - j \sin(\theta)$ (Euler's Identity). Complexity: Directly DFT calculate karne mein $O(N^2)$ operations lagte hain. $N$ jitna bada hoga, utna zyada time lagega. FFT (Fast Fourier Transform): The Speedup FFT: Yeh koi alag transform nahi hai, bas DFT ko calculate karne ka ek optimized algorithm hai. Yeh $O(N^2)$ se $O(N \log N)$ complexity par le aata hai. Jab $N$ bada hota hai (e.g., 1024, 4096), toh yeh huge speedup deta hai! Example: Agar $N=1024$, toh $N^2 \approx 10^6$ operations, jabki $N \log_2 N = 1024 \times 10 \approx 10^4$ operations. Kitna farak hai! How it works (Divide and Conquer): FFT ka main idea hai "Divide and Conquer". Yeh $N$-point DFT ko smaller DFTs mein split karta hai (e.g., two $N/2$-point DFTs), fir unke results ko combine karta hai. Most common FFT algorithms mein $N$ power of 2 hota hai (e.g., $N=2, 4, 8, \dots$). Radix-2 DIT FFT (Decimation-In-Time) Yeh sabse common FFT algorithm hai. Isme time domain signal ko even aur odd parts mein divide karte hain. Signal $x[n]$ (length $N$) ko do parts mein split karo: Even samples: $x_e[n] = x[2n]$ Odd samples: $x_o[n] = x[2n+1]$ Dono ki length $N/2$ hogi. Ab $X[k]$ ko aise likh sakte hain: $$X[k] = \sum_{n=0}^{N/2-1} x[2n] e^{-j 2\pi k (2n) / N} + \sum_{n=0}^{N/2-1} x[2n+1] e^{-j 2\pi k (2n+1) / N}$$ $$X[k] = \sum_{n=0}^{N/2-1} x_e[n] e^{-j 2\pi k n / (N/2)} + e^{-j 2\pi k / N} \sum_{n=0}^{N/2-1} x_o[n] e^{-j 2\pi k n / (N/2)}$$ Let $X_e[k]$ be the DFT of $x_e[n]$ and $X_o[k]$ be the DFT of $x_o[n]$. Then, $X[k] = X_e[k] + W_N^k X_o[k]$ where $W_N^k = e^{-j 2\pi k / N}$ is called the Twiddle Factor . Symmetry: Notice that $W_N^{k+N/2} = -W_N^k$. Is property ka use karke calculations reduce hoti hain. For $k = 0, \dots, N/2-1$: $X[k] = X_e[k] + W_N^k X_o[k]$ $X[k+N/2] = X_e[k] - W_N^k X_o[k]$ Butterfly Diagram (N=4 Example) FFT calculations ko visualize karne ke liye "Butterfly Diagram" use kiya jata hai. Yeh dikhata hai kaise inputs combine hokar outputs bante hain. Steps for N=4 DIT FFT: Bit Reversal: Input samples ko bit-reversed order mein arrange karo. Original Index (Binary) -> Bit-Reversed Index (Binary) 00 ($x_0$) -> 00 ($x_0$) 01 ($x_1$) -> 10 ($x_2$) 10 ($x_2$) -> 01 ($x_1$) 11 ($x_3$) -> 11 ($x_3$) So, input order becomes: $x_0, x_2, x_1, x_3$. Stages: $N$ samples ke liye $\log_2 N$ stages honge. N=4 ke liye $\log_2 4 = 2$ stages. Diagram Explanation: Stage 1 $-1$ $W_2^0$ $-1$ $W_2^0$ Stage 2 $-1$ $W_4^0$ $-1$ $W_4^1$ $-1$ $W_4^2$ $-1$ $W_4^3$ $x_0$ $x_2$ $x_1$ $x_3$ $X_0$ $X_1$ $X_2$ $X_3$ Note: Yeh diagram ek simplified representation hai. Actual butterfly mein inputs cross-connect hote hain aur twiddle factors apply hote hain. Above diagram is a conceptual representation of inputs to outputs. Ek standard butterfly operation (jisme do inputs combine hote hain) yeh hai: A ---+---> A + B * W^k | @ W^k (Twiddle Factor) | B ---X---> A - B * W^k Jahan 'X' multiplication by -1 dikhata hai. Twiddle Factors ($W_N^k$) $W_N^k = e^{-j 2\pi k / N} = \cos(2\pi k / N) - j \sin(2\pi k / N)$ Yeh complex exponential terms hain jo signals ko rotate karte hain complex plane mein. $W_N^0 = 1$ $W_N^{N/2} = e^{-j \pi} = -1$ $W_N^{k+N} = W_N^k$ (Periodic property) FFT vs. DFT: Performance Difference Feature DFT FFT Complexity $O(N^2)$ $O(N \log_2 N)$ Speed for large N Very Slow Very Fast Algorithm Direct sum calculation Divide and Conquer Memory Use $O(N)$ $O(N)$ (often in-place) Important Considerations Input Length (N): FFT algorithms most efficient hote hain jab $N$ 2 ki power ho ($2, 4, 8, 16, \dots$). Agar input signal ki length power of 2 nahi hai, toh zero-padding use karte hain (signal ke end mein zeros add karte hain) usko next power of 2 tak extend karne ke liye. Nyquist-Shannon Sampling Theorem: Time domain signal ko properly reconstruct karne ke liye, sampling frequency ($f_s$) signal ki highest frequency component ($f_{max}$) se kam se kam twice honi chahiye ($f_s \ge 2 f_{max}$). FFT output mein frequencies $0$ se $f_s/2$ tak hoti hain (positive frequencies) aur $f_s/2$ se $f_s$ tak negative frequencies (jo $0$ se $-f_s/2$ tak correspond karti hain). Amplitude Spectrum: FFT output $X[k]$ complex numbers hote hain. Iska magnitude $|X[k]|$ frequency component ki strength batata hai aur phase $\arg(X[k])$ uski phase information. Aksar hum $|X[k]|$ ka plot dekhte hain, jise amplitude spectrum kehte hain. Example: Simple Sine Wave Agar aap ek pure sine wave ($x[t] = A \sin(2\pi f_0 t)$) ka FFT loge, toh aapko frequency domain mein $f_0$ par ek sharp peak dikhega. import numpy as np import matplotlib.pyplot as plt # Parameters Fs = 1000 # Sampling frequency (Hz) T = 1/Fs # Sampling period L = 1000 # Length of signal t = np.arange(0, L) * T # Time vector # Create a sine wave f1 = 50 # Frequency of sine wave (Hz) A1 = 0.7 # Amplitude S = A1 * np.sin(2 * np.pi * f1 * t) # Compute FFT Y = np.fft.fft(S) # Get the frequency axis P2 = np.abs(Y/L) # Two-sided spectrum P1 = P2[0:L//2+1] # Single-sided spectrum P1[1:-1] = 2*P1[1:-1] # Adjust for single-sided f = Fs * np.arange(0, L//2+1) / L # Frequency vector # Plotting (conceptual) # plt.figure() # plt.plot(t, S) # plt.title('Time Domain Signal') # plt.xlabel('Time (s)') # plt.ylabel('Amplitude') # plt.figure() # plt.plot(f, P1) # plt.title('Frequency Domain (FFT Result)') # plt.xlabel('Frequency (Hz)') # plt.ylabel('|Y(f)|') # plt.show() Output graph mein aapko 50 Hz par ek bada peak dikhega, jo confirm karega ki signal mein 50 Hz ki frequency hai.