8. Fast Fourier Transform (FFT)

What is FFT?

The Fast Fourier Transform (FFT) is a highly efficient algorithm to compute the Discrete Fourier Transform (DFT) of a sequence. The DFT transforms a sequence of complex numbers from the time domain into the frequency domain.

Why FFT?

• Direct DFT calculation takes O(N²) time for a sequence of length N because it involves summing over N points for each of the N outputs.
• FFT reduces this to O(N log N), making it much faster and practical for large data sets.

8.1 Recap: Discrete Fourier Transform (DFT)

Given a sequence x[n] for n = 0, 1, ..., N-1, its DFT is:

X[k] = Σ (n=0 to N-1) x[n] × e^{-j (2π/N) k n}, for k = 0, 1, ..., N-1

• X[k] is the frequency domain output.
• j = √-1 (imaginary unit).
• N is the total number of points.

Computing this directly requires N × N = N² complex multiplications.

8.2 FFT Overview

FFT exploits symmetry and periodicity properties of the exponential factor e^{-j (2π/N) k n} to reduce redundant calculations.

The most common FFT algorithm is the Radix-2 FFT, which works when N is a power of two (e.g., 8, 16, 32, ...).

8.3 Radix-2 FFT Algorithm

Basic idea:

Divide the DFT of size N into two smaller DFTs of size N/2:

• One for the even-indexed samples.
• One for the odd-indexed samples.

Step-by-step:

X[k] = Σ (n=0 to N-1) x[n] × W_N^kn

Where W_N = e^{-j 2π / N} (called the twiddle factor).

Split into even and odd terms:

X[k] = Σ (m=0 to N/2-1) x[2m] × W_N^{k × 2m} + Σ (m=0 to N/2-1) x[2m+1] × W_N^{k × (2m+1)}

Rewrite twiddle factors:

= Σ (m=0 to N/2-1) x[2m] × W_N/2^{k m} + W_N^k × Σ (m=0 to N/2-1) x[2m+1] × W_N/2^{k m}

Define:

• E[k] = DFT of even-indexed samples
• O[k] = DFT of odd-indexed samples

Then,

X[k] = E[k] + W_N^k × O[k]
X[k + N/2] = E[k] - W_N^k × O[k]
for k = 0, 1, ..., N/2 - 1

Intuition:

- Calculate DFT for smaller parts (even and odd).
- Combine the results with twiddle factors W_N^k.
- Recursively apply the same process to smaller DFTs until size 1.

8.4 Bit Reversal

To perform FFT efficiently, input data must be reordered in bit-reversed order before processing.

What is bit reversal?

For N = 8, indices run from 0 to 7. Express each index in binary (3 bits for 8):

The input array elements are reordered to these new indices before FFT processing.

8.5 Decimation-in-Time (DIT) and Decimation-in-Frequency (DIF)

These are two main FFT implementation strategies:

• Decimation-in-Time (DIT):
  • Break input sequence into even and odd time samples.
  • Bit-reversed input ordering.
  • Combines smaller FFT results.
  • Output is in natural order.
• Decimation-in-Frequency (DIF):
  • Process the sequence by dividing the output frequencies.
  • Input is in natural order.
  • Output is bit-reversed.

Both algorithms achieve the same result but differ in order of operations and indexing.

8.6 Example of Radix-2 FFT (N=8)

Let's compute the FFT of:

x = [1, 1, 1, 1, 0, 0, 0, 0]

Step 1: Bit reversal reorder input (indices shown above)

Original indices: 0 1 2 3 4 5 6 7

Bit reversed indices: 0 4 2 6 1 5 3 7

Reordered x:

x_reordered = [1, 0, 1, 0, 1, 0, 1, 0]

Step 2: Apply the recursive radix-2 algorithm

- Divide into even and odd indexed parts recursively.
- Combine using twiddle factors W₈^k = e^{-j 2π k / 8}.

Note: Due to complexity, detailed calculations are often done step-by-step or using software tools.

8.7 Summary

Formulas to Remember

• Twiddle factor:
  W_N = e^{-j 2π / N}
• Recursive FFT formula:
  X[k] = E[k] + W_N^k × O[k]
  X[k + N/2] = E[k] - W_N^k × O[k]

20 Solved Examples on Fast Fourier Transform (FFT) and DFT

These examples cover simple to complex problems to help you fully master FFT concepts. Each step explains the formulas used, symbols, and reasoning.

Example 1: Compute the DFT of x = [1, 0] (N=2)

Problem: Find the DFT X[k] for k=0,1 of the sequence x = [1, 0].

Solution:

Recall DFT formula:

X[k] = Σ_n=0^N-1 x[n] · e^{-j (2π/N) k n}

• N=2 (number of points)
• k=0,1 (frequency index)
• x[n] = input sequence
• j = √-1, imaginary unit

Calculate for k=0:

X[0] = x[0]·e^{-j 2π/2 · 0 · 0} + x[1]·e^{-j 2π/2 · 0 · 1}
X[0] = 1·1 + 0·1 = 1

Calculate for k=1:

X[1] = x[0]·e^{-j 2π/2 · 1 · 0} + x[1]·e^{-j 2π/2 · 1 · 1}
X[1] = 1·1 + 0·e^{-j π} = 1

Answer: X = [1, 1]

Example 2: Compute DFT of x = [1, 1, 1, 1] (N=4) manually

Problem: Compute the DFT of a constant sequence x = [1, 1, 1, 1].

Solution:

Use DFT formula:

X[k] = Σ_n=0³ x[n] · e^{-j (2π/4) k n}

Calculate each X[k]:

• k=0:
  X[0] = 1 + 1 + 1 + 1 = 4
• k=1:
  X[1] = 1 + e^{-j π/2} + e^{-j π} + e^{-j 3π/2}
  = 1 + (-j) + (-1) + j = 0
• k=2:
  X[2] = 1 + e^{-j π} + e^{-j 2π} + e^{-j 3π}
  = 1 - 1 + 1 - 1 = 0
• k=3:
  X[3] = 1 + e^{-j 3π/2} + e^{-j 3π} + e^{-j 9π/2}
  = 1 + j - 1 - j = 0

Answer: X = [4, 0, 0, 0]

Example 3: Compute the FFT of x = [1, 2, 0, 0] (N=4) using Radix-2 FFT

Solution:

Step 1: Split x into even and odd indexed parts:

• Even indices: x[0] = 1, x[2] = 0 → E = [1, 0]
• Odd indices: x[1] = 2, x[3] = 0 → O = [2, 0]

Step 2: Compute DFT of size 2 for E and O:

• E[0] = 1 + 0 = 1
• E[1] = 1 - 0 = 1
• O[0] = 2 + 0 = 2
• O[1] = 2 - 0 = 2

Step 3: Compute twiddle factors W₄^k = e^{-j 2π k/4}:

• W₄⁰ = 1
• W₄¹ = e^{-j π/2} = -j

Step 4: Combine results:

• X[0] = E[0] + W₄⁰ × O[0] = 1 + 1 × 2 = 3
• X[1] = E[1] + W₄¹ × O[1] = 1 + (-j) × 2 = 1 - 2j
• X[2] = E[0] - W₄⁰ × O[0] = 1 - 2 = -1
• X[3] = E[1] - W₄¹ × O[1] = 1 - (-j) × 2 = 1 + 2j

Answer: X = [3, 1 - 2j, -1, 1 + 2j]

Example 4: Explain bit reversal for N=8 and reorder x = [1, 2, 3, 4, 5, 6, 7, 8]

Solution:

Step 1: Write indices in binary and reverse bits:

Step 2: Reorder x according to reversed indices:

Original x = [1, 2, 3, 4, 5, 6, 7, 8]

Reordered x = [x[0], x[4], x[2], x[6], x[1], x[5], x[3], x[7]] = [1, 5, 3, 7, 2, 6, 4, 8]

Example 5: Calculate twiddle factor W₈³

Solution:

Twiddle factor formula:

W_N^k = e^{-j 2π k / N}

For N=8 and k=3:

W₈³ = e^{-j 2π × 3 / 8} = e^{-j 3π/4}

Using Euler's formula: e^jθ = cos θ + j sin θ
So, W₈³ = cos(3π/4) - j sin(3π/4) = -√2/2 - j √2/2

Example 6: Show why FFT reduces complexity from O(N²) to O(N log N)

Solution:

Naive DFT requires N sums, each summing N terms → O(N²) operations.

FFT divides problem into halves recursively:

• At each level, you do N operations.
• Number of levels is log₂(N) because problem size halves each time.

Total operations = N × log₂(N) → O(N log N).

Example 7: Calculate FFT for x = [0, 1, 0, 0] (N=4)

Solution:

Split into even and odd:

• Even: x[0] = 0, x[2] = 0 → E = [0,0]
• Odd: x[1] = 1, x[3] = 0 → O = [1,0]

DFTs of size 2:

• E[0] = 0 + 0 = 0, E[1] = 0 - 0 = 0
• O[0] = 1 + 0 = 1, O[1] = 1 - 0 = 1

Twiddle factors W₄^k = 1, -j

Combine:

• X[0] = 0 + 1 × 1 = 1
• X[1] = 0 + (-j) × 1 = -j
• X[2] = 0 - 1 × 1 = -1
• X[3] = 0 - (-j) × 1 = j

Answer: X = [1, -j, -1, j]

Example 8: Explain why twiddle factor W_N^k is important

Explanation:

Twiddle factor is:

W_N^k = e^{-j 2π k / N}

• It represents the complex rotation needed to combine smaller DFTs into the full DFT.
• Its periodicity and symmetry allow us to reuse calculations.
• It encodes frequency components, rotating the odd part's results to align properly with even parts.

Example 9: Compute the FFT of x = [1, 0, 0, 0] (N=4)

Solution:

This is the delta function δ[n]. Its FFT is a constant:

Using DFT formula:

X[k] = 1 × e^{-j 2π k 0 / 4} + 0 + 0 + 0 = 1 for all k.

Answer: X = [1, 1, 1, 1]

Example 10: Calculate magnitude spectrum of X = [3, 1-2j, -1, 1+2j]

Solution:

Magnitude |X[k]| = sqrt(Re(X[k])² + Im(X[k])²)

• |X[0]| = |3| = 3
• |X[1]| = sqrt(1² + (-2)²) = sqrt(1 + 4) = sqrt(5) ≈ 2.236
• |X[2]| = |-1| = 1
• |X[3]| = sqrt(1² + 2²) = sqrt(1 + 4) = sqrt(5) ≈ 2.236

Example 11: Using FFT, find the frequency components of x = [0, 1, 0, 0, 0, 0, 0, 0] (N=8)

Solution outline:

This is a discrete impulse at n=1, so FFT will have all frequency components with phases:

X[k] = e^{-j 2π k 1 / 8} = e^{-j π k / 4}

• For k=0: 1
• For k=1: cos(π/4) - j sin(π/4) ≈ 0.707 - j0.707
• For k=2: cos(π/2) - j sin(π/2) = 0 - j1
• ... and so on

Example 12: Explain the difference between Decimation-in-Time and Decimation-in-Frequency FFT

Answer:

• Decimation-in-Time (DIT): splits input samples by even/odd indices; input is bit-reversed; output in normal order.
• Decimation-in-Frequency (DIF): splits output frequency bins; input in normal order; output is bit-reversed.

Example 13: Verify Parseval's theorem for x = [1, 2, 3, 4]

Parseval’s theorem states:

Σ|x[n]|² = (1/N) Σ|X[k]|²

Solution:

Calculate time domain sum:

1² + 2² + 3² + 4² = 1 + 4 + 9 + 16 = 30

Calculate FFT X (omitting full detail, assume computed X):

X = [10, -2 + 2j, -2, -2 - 2j]

Calculate frequency domain sum:

(1/4) × (|10|² + |-2+2j|² + |-2|² + |-2-2j|²)

= (1/4) × (100 + 8 + 4 + 8) = (1/4) × 120 = 30

Both sums equal → theorem verified.

Example 14: Compute the inverse FFT of X = [4, 0, 0, 0]

Inverse DFT formula:

x[n] = (1/N) Σ X[k] × e^{j 2π k n / N}

For N=4, only X[0]=4 nonzero:

x[n] = (1/4) × 4 × e^{j 0} = 1 for all n

Answer: x = [1, 1, 1, 1]

Example 15: How many stages are there in Radix-2 FFT for N=16?

Number of stages = log₂(N) = log₂(16) = 4 stages

Example 16: Calculate W₁₆⁵ in rectangular form

W₁₆⁵ = e^{-j 2π 5 / 16} = cos(5π/8) - j sin(5π/8)

cos(5π/8) ≈ -0.383, sin(5π/8) ≈ 0.924

So, W₁₆⁵ ≈ -0.383 - j0.924

Example 17: Explain why N must be a power of two in Radix-2 FFT

Radix-2 FFT splits data into halves recursively until size 1. This requires repeatedly dividing N by 2.

If N is not a power of two, you cannot evenly split the sequence at every stage, breaking the algorithm’s assumptions.

Example 18: Compute FFT of x = [0, 0, 1, 0, 0, 0, 0, 0]

This is an impulse at n=2, so FFT:

X[k] = e^{-j 2π k 2 / 8} = e^{-j π k / 2}

• k=0 → 1
• k=1 → cos(π/2) - j sin(π/2) = 0 - j1 = -j
• k=2 → cos(π) - j sin(π) = -1 - j0 = -1
• k=3 → cos(3π/2) - j sin(3π/2) = 0 + j1 = j
• ... etc.

Example 19: Using DIT FFT, find X[2] of x = [1, 3, 0, 0]

Split:

• Even: [1, 0]
• Odd: [3, 0]

DFT size 2:

• E[0] = 1 + 0 = 1
• E[1] = 1 - 0 = 1
• O[0] = 3 + 0 = 3
• O[1] = 3 - 0 = 3

Twiddle factor W₄² = e^{-j π} = -1

X[2] = E[0] - W₄² × O[0] = 1 - (-1) × 3 = 1 + 3 = 4

Example 20: Show how FFT can be used to multiply polynomials

Multiplying two polynomials of degree n can be done by:

• Take FFT of both coefficient sequences (length ≥ 2n)
• Multiply pointwise the FFT outputs
• Apply inverse FFT to get the coefficients of the product

This reduces polynomial multiplication from O(n²) to O(n log n).

These examples help you build a deep understanding of FFT, its formulas, and how to apply it in practical scenarios.