Skip to content

Lab 19: The Butterfly

Time: ~40 minutes | Prerequisites: Lab 18 | Hardware: Pico 2 (no microphone needed)

Four multiplies. That's the whole engine.

Echo waving welcome Everything in an FFT — all 2,304 operations in a 512-point transform — is this one tiny thing repeated. Learn it here and you've learned the FFT's entire arithmetic. It even looks nice on paper.

What You'll Build

The butterfly: a two-in, two-out operation that shares one complex multiplication between both outputs. Then you'll see how butterflies arrange into stages.

Learning Objectives

  • Perform a complex multiplication with four real multiplies
  • Execute a butterfly by hand and in code
  • Explain why both outputs reuse the same product
  • Describe how the pairing distance doubles each stage
  • Count the butterflies in an N-point FFT

Concepts Introduced

ID Concept
384 Butterfly Structure
385 Complex Multiplication
386 Four Multiply Form
387 Butterfly Pair
388 Stage Span
389 Data Flow Graph
390 Butterfly Count
391 Stage Loop
392 Cross Add And Subtract

Background

The shape

1
2
3
4
5
6
7
8
        a ──────────┬─────────► a + W·b
                     ╲       ╱
                      ╲     ╱
                       ╲   ╱
                        ╳
                       ╱   ╲
                      ╱     ╲
        b ──[× W]────┴───────► a − W·b

Two complex inputs, two complex outputs, crossing over in the middle. Hence "butterfly."

The arithmetic

Step 1 — multiply b by the twiddle. Complex multiplication needs four real multiplies:

1
2
tr = wr*br - wi*bi        # real part
ti = wr*bi + wi*br        # imaginary part

Step 2 — cross add and subtract. No more multiplying:

1
2
out1 = a + t
out2 = a - t

Total: 4 real multiplies, 6 real adds, two complex outputs.

The saving is the sharing

Echo thinking Notice that W·b is computed once and used for both outputs. The direct DFT computes those two bins separately, redoing that multiply. Multiply that waste across every bin and every stage and you have the entire 500× gap from Lab 16.

Stages

1
2
3
Stage 1: pairs are 1 apart  (0,1) (2,3) (4,5) (6,7)
Stage 2: pairs are 2 apart  (0,2) (1,3) (4,6) (5,7)
Stage 3: pairs are 4 apart  (0,4) (1,5) (2,6) (3,7)

Stage 1 pairs neighbours. Each stage the reach doubles until the last stage spans half the array. For N = 512 that's nine stages — the log₂(N) from Lab 17, made concrete.

Every stage does exactly N/2 butterflies, so the total is (N/2)·log₂(N).

Procedure

Step 1 — Work one butterfly by hand

Open 19-butterfly.py and run it:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
# Lab 19: The Butterfly
#
# We have the pieces now:
#   Lab 17 -- split into evens and odds, recombine with a twiddle factor
#   Lab 18 -- reorder once by bit reversal, then work in place
#
# The recombination step is where all the arithmetic happens, and it has a
# name. Draw it and it looks like a butterfly's wings:
#
#        a ------+-------> a + W*b
#                 \     /
#                  \   /
#                   \ /
#                    X
#                   / \
#                  /   \
#                 /     \
#        b --[W]--+-------> a - W*b
#
# Two inputs, two outputs, ONE complex multiplication shared between them.
# That sharing is the whole reason the FFT is fast.

import config
import math

# =========================================================================
# PART 1 -- one butterfly, step by step
# =========================================================================
print("=== PART 1: a single butterfly ===")
print()

# Two complex numbers, a and b
ar, ai = 3.0, 1.0
br, bi = 2.0, -1.0
# A twiddle factor: a rotation of -45 degrees
angle = -math.pi / 4
wr, wi = math.cos(angle), math.sin(angle)

print("input a  = %+.3f %+.3fi" % (ar, ai))
print("input b  = %+.3f %+.3fi" % (br, bi))
print("twiddle W= %+.3f %+.3fi   (rotate by %.0f degrees)"
      % (wr, wi, math.degrees(angle)))
print()

# Step 1: multiply b by the twiddle factor.
# Complex multiply: (wr + wi*i)(br + bi*i)
#                 = wr*br - wi*bi  +  (wr*bi + wi*br)i
tr = wr * br - wi * bi
ti = wr * bi + wi * br
print("Step 1 -- W * b  (four real multiplies):")
print("   real = wr*br - wi*bi = %+.3f*%+.3f - %+.3f*%+.3f = %+.4f"
      % (wr, br, wi, bi, tr))
print("   imag = wr*bi + wi*br = %+.3f*%+.3f + %+.3f*%+.3f = %+.4f"
      % (wr, bi, wi, br, ti))
print()

# Step 2: add and subtract. Both outputs reuse the SAME product.
out1r, out1i = ar + tr, ai + ti
out2r, out2i = ar - tr, ai - ti
print("Step 2 -- combine (no more multiplying):")
print("   top    = a + W*b = %+.4f %+.4fi" % (out1r, out1i))
print("   bottom = a - W*b = %+.4f %+.4fi" % (out2r, out2i))
print()
print("Total cost: 4 real multiplies and 6 real adds, for TWO outputs.")

# =========================================================================
# PART 2 -- the butterfly as a function
# =========================================================================
print()
print("=== PART 2: as reusable code ===")


def butterfly(re, im, i1, i2, wr, wi):
    """One butterfly, performed in place on two positions of an array."""
    # W * x[i2]
    tr = wr * re[i2] - wi * im[i2]
    ti = wr * im[i2] + wi * re[i2]
    # cross add and subtract
    ar, ai = re[i1], im[i1]
    re[i1] = ar + tr
    im[i1] = ai + ti
    re[i2] = ar - tr
    im[i2] = ai - ti


re = [3.0, 2.0]
im = [1.0, -1.0]
butterfly(re, im, 0, 1, wr, wi)
print("same numbers through the function:")
print("   x[0] = %+.4f %+.4fi" % (re[0], im[0]))
print("   x[1] = %+.4f %+.4fi" % (re[1], im[1]))

# =========================================================================
# PART 3 -- how butterflies are arranged into stages
# =========================================================================
print()
print("=== PART 3: stages ===")
print()
N = 8
stages = int(math.log(N, 2) + 0.5)
print("For N=%d there are %d stages, each with %d butterflies."
      % (N, stages, N // 2))
print("Total: %d butterflies. Compare to %d operations for the direct DFT."
      % (stages * N // 2, N * N))
print()

half = 1
stage = 1
while half < N:
    span = half * 2
    print("Stage %d: pairs are %d apart, blocks of %d" % (stage, half, span))
    pairs = []
    for k in range(0, N, span):
        for j in range(half):
            pairs.append((k + j, k + j + half))
    print("         ", " ".join("(%d,%d)" % p for p in pairs))
    half *= 2
    stage += 1

print()
print("Stage 1 pairs neighbours. Each stage the reach doubles, until the")
print("last stage pairs elements half the array apart. Nine stages covers")
print("512 samples -- that is the log2(N) in N*log2(N).")

# =========================================================================
# PART 4 -- how many butterflies, really
# =========================================================================
print()
print("=== PART 4: counting the work ===")
print("%8s %8s %14s %16s %10s" % ("N", "stages", "butterflies", "direct DFT ops", "ratio"))
for n in (8, 64, 256, 512, 1024):
    st = int(math.log(n, 2) + 0.5)
    bf = st * n // 2
    print("%8d %8d %14d %16d %9.0fx" % (n, st, bf, n * n, (n * n) / bf))

print()
print("512 samples: 2304 butterflies instead of 262144 operations.")
print("Each butterfly is 4 multiplies -- so about 9216 multiplications")
print("where the DFT needed over half a million.")

Part 1 shows every intermediate value for a single butterfly with a = 3+1i, b = 2−1i, and a 45° twiddle. Follow the arithmetic with a calculator once — it makes the rest concrete.

Step 2 — See it as code

1
2
3
4
5
6
7
8
def butterfly(re, im, i1, i2, wr, wi):
    tr = wr * re[i2] - wi * im[i2]
    ti = wr * im[i2] + wi * re[i2]
    ar, ai = re[i1], im[i1]
    re[i1] = ar + tr
    im[i1] = ai + ti
    re[i2] = ar - tr
    im[i2] = ai - ti

Eight lines. This is the FFT's entire arithmetic. Everything else is loops deciding which indices and which twiddle.

Save a before you overwrite it

Echo warning Notice ar, ai = re[i1], im[i1] happens before any assignment. Write re[i1] first and the old value is gone when you need it for re[i2]. It's a two-character bug that produces a spectrum which looks plausible and is wrong.

Step 3 — Watch the stages spread

Part 3 prints the pairing for every stage of an 8-point FFT. Trace one element — say index 1 — through all three stages and see who it partners with each time.

Step 4 — Count the work

1
2
       N   stages    butterflies   direct DFT ops      ratio
     512        9           2304           262144        114x

2,304 butterflies for a 512-point FFT. At 4 multiplies each that's about 9,216 multiplications, where the DFT needed over half a million.

Step 5 — Predict, then measure

Prediction: how many butterflies in a 1,024-point FFT? How many stages?

Work it out before checking the table.

Expected Output

1
2
3
4
5
6
7
8
Step 1 -- W * b  (four real multiplies):
   real = wr*br - wi*bi = +0.707*+2.000 - -0.707*-1.000 = +0.7071
   imag = wr*bi + wi*br = +0.707*-1.000 + -0.707*+2.000 = -2.1213

Stage 1: pairs are 1 apart, blocks of 2
          (0,1) (2,3) (4,5) (6,7)

     512        9           2304           262144        114x

Troubleshooting

Symptom Likely cause Fix
Outputs wrong but plausible Overwrote a before using it Save ar, ai first
Complex multiply wrong Sign error tr = wr·br − wi·bi; the minus is on the real part
Pairs overlap between blocks Block stride wrong Blocks advance by half*2
Only half the array changes Inner loop bound wrong It runs half times, not n

Challenges

  1. Three multiplies. There's a known trick computing a complex product with 3 multiplies and 5 adds instead of 4 and 2. Look it up, implement it, and decide whether it's worth it here.
  2. Draw the graph. Sketch the full 8-point data-flow diagram, all three stages. You'll see why it's called a butterfly network.
  3. Trace an element. Follow index 3 through all three stages of an 8-point FFT. Which partners does it meet, and which twiddle applies each time?

Check Your Understanding

  1. How many real multiplies does one butterfly need, and for how many outputs?
  2. Why must you save a before writing the outputs?
  3. In stage 3 of a 16-point FFT, how far apart are the paired elements?
  4. How many butterflies are in a 256-point FFT?
  5. In one sentence, where does the FFT's saving actually come from?

You have every piece now

Echo celebrating Split, reorder, look up twiddles, butterfly. Next lab you assemble all four into a working FFT — and find out just how much faster it really is.

Next: Lab 20: A Complete Python FFT | Previous: Lab 18