Fast Fourier Transform (FFT) algorithm in Signal Processing - Step-by-Step Execution

Concept Flow - Fast Fourier Transform (FFT) algorithm

Input: Time-domain signal

↓

Divide signal into halves

↓

Recursively apply FFT on halves

↓

Combine results with twiddle factors

↓

Output: Frequency-domain signal

FFT breaks a signal into smaller parts, solves each, then combines results to get frequency info fast.

Execution Sample

Signal Processing

from math import pi, exp
def fft(x):
    N = len(x)
    if N <= 1: return x
    even = fft(x[0::2])
    odd = fft(x[1::2])
    combined = [even[k] + exp(-2j * pi * k / N) * odd[k] for k in range(N // 2)]
    return combined + [even[k] - exp(-2j * pi * k / N) * odd[k] for k in range(N // 2)]

This code splits the input signal recursively and combines results to compute FFT.

Execution Table

Step	Input x	N	Action	Result
1	[1, 0, 0, 0]	4	Split into even and odd indices	even=[1,0], odd=[0,0]
2	even=[1,0]	2	Split even into [1] and [0]	even_even=[1], even_odd=[0]
3	even_even=[1]	1	Base case reached	[1]
4	even_odd=[0]	1	Base case reached	[0]
5	Combine even halves	2	Calculate combined FFT for even	[1+0, 1-0] = [1,1]
6	odd=[0,0]	2	Split odd into [0] and [0]	odd_even=[0], odd_odd=[0]
7	odd_even=[0]	1	Base case reached	[0]
8	odd_odd=[0]	1	Base case reached	[0]
9	Combine odd halves	2	Calculate combined FFT for odd	[0+0, 0-0] = [0,0]
10	Combine even and odd	4	Calculate full FFT	[1+0, 1+0j, 1-0, 1-0j] = [1,1,1,1]
11	Output	4	FFT complete	[1, 1, 1, 1]

💡 Reached base case when N=1, then combined results up to full FFT.

Variable Tracker

Variable	Start	After 1	After 2	After 5	After 9	Final
x	[1,0,0,0]	[1,0]	[1]	[1,1]	[0,0]	[1,1,1,1]
N	4	2	1	2	2	4
even	N/A	[1,0]	[1]	[1,1]	N/A	N/A
odd	N/A	[0,0]	[0]	[0,0]	[0,0]	N/A
combined	N/A	N/A	N/A	[1,1]	[0,0]	[1,1,1,1]

Key Moments - 3 Insights

Why do we stop splitting when the length N is 1?

Because when N=1, the FFT of a single element is the element itself, so it's the base case (see execution_table rows 3,4,7,8).

How do we combine the results from even and odd parts?

We use twiddle factors (complex exponentials) to combine even and odd FFT results as shown in step 10 of execution_table.

Why do we split the input into even and odd indices?

Splitting into even and odd indices reduces the problem size by half each time, enabling efficient recursion (see step 1 and 2).

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the combined FFT result for the even part?

A [0, 0]

B [1, 0]

C [1, 1]

D [1, -1]

💡 Hint

Check the 'Result' column at step 5 in execution_table.

At which step does the recursion reach the base case for the odd part?

A Step 7

B Step 3

C Step 10

D Step 1

💡 Hint

Look for 'Base case reached' for odd part in execution_table.

If the input length N was 8 instead of 4, how would the number of recursion steps change?

A It would double

B It would increase by one level

C It would stay the same

D It would decrease

💡 Hint

Recall recursion depth depends on log2(N), see variable_tracker for N values.

Concept Snapshot

Fast Fourier Transform (FFT) algorithm:
- Input: time-domain signal array
- Recursively split into even and odd parts
- Base case: length 1 array returns itself
- Combine halves using twiddle factors (complex exponentials)
- Output: frequency-domain representation
- Runs in O(N log N) time, much faster than direct DFT

Full Transcript

The Fast Fourier Transform (FFT) algorithm takes a time-domain signal and breaks it down recursively into smaller parts by splitting the signal into even and odd indexed elements. When the parts reach length one, the recursion stops, as the FFT of a single element is the element itself. Then, the algorithm combines these smaller FFT results using special complex numbers called twiddle factors to build up the full frequency-domain signal. This process is much faster than computing the Discrete Fourier Transform directly. The execution table shows each step of splitting and combining for a simple input of length 4, tracking variables like the input array, its length, and the combined results. Key moments include understanding the base case, the splitting strategy, and how results are combined. The visual quiz tests understanding of these steps and recursion depth. The concept snapshot summarizes the algorithm's main points and efficiency.

Practice

1. What is the main purpose of the Fast Fourier Transform (FFT) algorithm in signal processing?

easy

A. To compress the signal data for storage

B. To convert a signal from time domain to frequency domain

C. To filter out noise from the signal

D. To increase the amplitude of the signal

Solution

1. Step 1: Understand FFT role and compare options

   FFT transforms time-domain signal to frequency domain. A matches exactly; B is compression, C filtering, D amplification.

2. Final Answer:

   To convert a signal from time domain to frequency domain -> Option B

3. Quick Check:

   FFT = Time to Frequency conversion [OK]

Hint: FFT changes signal view from time to frequency fast [OK]

Common Mistakes:

• Confusing FFT with noise filtering
• Thinking FFT compresses data
• Assuming FFT amplifies signals

2. Which of the following is the correct way to import the FFT function from NumPy in Python?

easy

A. from numpy import fft

B. import numpy.fft as fft

C. import fft from numpy

D. from numpy.fft import fft

Solution

1. Step 1: Recall and match Python import syntax

   Correct for specific function: 'from numpy.fft import fft' (C). A imports submodule, B aliases submodule (requires fft.fft()), D invalid.

2. Final Answer:

   from numpy.fft import fft -> Option D

3. Quick Check:

   Correct import syntax = from numpy.fft import fft [OK]

Hint: Use 'from module import function' to import FFT [OK]

Common Mistakes:

• Using 'import fft from numpy' which is invalid syntax
• Importing whole numpy.fft as fft causing confusion
• Trying 'from numpy import fft' which imports the module, not function

3. Given the Python code:

import numpy as np
signal = np.array([1, 0, -1, 0])
fft_result = np.fft.fft(signal)
print(np.round(fft_result, 2))

What is the output?

medium

A. [0.+0.j 0.+2.j 0.+0.j 0.-2.j]

B. [0.+0.j 0.+0.j 0.+0.j 0.+0.j]

C. [0.+0.j 2.+0.j 0.+0.j 2.+0.j]

D. [0.+0.j 1.+0.j 0.+0.j 1.+0.j]

Solution

1. Step 1: Compute and verify FFT output

   np.fft.fft([1,0,-1,0]) corresponds to a sine wave component, resulting in imaginary parts at k=1 and k=3. The output is [0.+0.j 0.+2.j 0.+0.j 0.-2.j], matching [0.+0.j 0.+2.j 0.+0.j 0.-2.j].

2. Final Answer:

   [0.+0.j 0.+2.j 0.+0.j 0.-2.j] -> Option A

3. Quick Check:

   FFT sine wave = imaginary components at k=1,3 [OK]

Hint: Sine-like signals yield imaginary FFT components [OK]

Common Mistakes:

• Confusing cosine signal with sine (imaginary output)
• Confusing zeros with non-zero frequency components
• Rounding incorrectly or not at all

4. Consider this Python code snippet:

import numpy as np
signal = [1, 2, 3, 4]
fft_result = fft(signal)
print(fft_result.real)

It raises an error. What is the most likely cause?

medium

A. signal should be a NumPy array, not a list

B. np.fft.fft does not have a real attribute

C. Missing import statement for fft

D. print statement syntax is incorrect

Solution

1. Step 1: Trace code execution for error

   fft(signal) raises NameError: 'fft' undefined. Import is numpy as np (use np.fft.fft); no direct fft import (e.g., from numpy.fft import fft). A, B, D unrelated.

2. Final Answer:

   Missing import statement for fft -> Option C

3. Quick Check:

   Undefined fft = missing import [OK]

Hint: Import fft properly: from numpy.fft import fft [OK]

Common Mistakes:

• Not importing the fft function when using fft()
• Thinking .real is invalid on FFT output
• Confusing print syntax errors

5. You have a noisy signal sampled at 1000 Hz stored in a NumPy array data. You want to remove frequencies above 100 Hz using FFT. Which approach correctly achieves this?

hard

A. Compute FFT, zero out components with frequency > 100 Hz, then inverse FFT

B. Compute FFT, keep only first 100 components, then inverse FFT

C. Apply FFT and multiply all values by 0.1 to reduce noise

D. Use FFT to find max frequency and subtract it from signal

Solution

1. Step 1: Outline correct FFT low-pass filtering

   FFT to freq domain (use fftfreq for bins), zero coeffs where |freq| > 100 (fs=1000, cutoff index ~100/500=0.2*N), ifft back. Matches B precisely; A ignores freq mapping, C/D ineffective.

2. Final Answer:

   Compute FFT, zero out components with frequency > 100 Hz, then inverse FFT -> Option A

3. Quick Check:

   Zero high freq + ifft = low-pass filter [OK]

Hint: Zero unwanted FFT frequencies, then inverse transform [OK]

Common Mistakes:

• Confusing component count with frequency
• Scaling FFT values instead of zeroing
• Misusing FFT to subtract frequencies directly