Butterfly Diagram in FFT: What It Is and How It Works

A butterfly diagram in FFT is a visual representation of the basic computation step that combines pairs of data points using addition and subtraction with complex multiplications. It shows how the FFT algorithm breaks down a signal into smaller parts to efficiently compute the frequency spectrum.

How It Works

The butterfly diagram is like a simple machine inside the FFT that mixes pairs of numbers to get new results. Imagine you have two numbers, and you want to combine them in a way that helps find frequencies in a signal. The butterfly step adds and subtracts these numbers, then multiplies one result by a special complex number called a twiddle factor.

This process repeats many times, breaking the big problem into smaller ones, just like folding a paper multiple times to reach a tiny size. The diagram looks like a butterfly because the lines connecting the pairs cross over, resembling butterfly wings.

Example

This example shows one butterfly step combining two complex numbers with a twiddle factor.

python

import numpy as np

# Two input complex numbers
x0 = 1 + 1j
x1 = 2 - 1j

# Twiddle factor for this stage (usually e^{-2j * pi * k / N})
W = np.exp(-2j * np.pi * 1 / 4)  # example for N=4, k=1

# Butterfly computations
Y0 = x0 + W * x1
Y1 = x0 - W * x1

print(f"Y0 = {Y0}")
print(f"Y1 = {Y1}")

Output

Y0 = (2.414213562373095+0.41421356237309515j)
Y1 = (-0.4142135623730949+1.414213562373095j)

When to Use

Use the butterfly diagram concept when implementing or understanding the FFT algorithm, which is essential for fast frequency analysis of signals. It is widely used in audio processing, image compression, wireless communications, and any field that needs quick transformation from time to frequency domain.

Understanding the butterfly helps optimize FFT code and debug signal processing tasks by visualizing how data points combine step-by-step.

Key Points

• The butterfly diagram shows the core addition, subtraction, and multiplication steps in FFT.
• It visually represents how FFT breaks down a big problem into smaller parts.
• Twiddle factors are complex multipliers used in butterfly steps.
• Butterfly steps repeat in stages to compute the full FFT efficiently.

Key Takeaways

The butterfly diagram is the fundamental step in FFT combining pairs of data points.

It uses addition, subtraction, and complex multiplication with twiddle factors.

Butterfly steps repeat to break down signals for fast frequency analysis.

Understanding butterflies helps optimize and debug FFT implementations.