Radix-2 Fast Fourier Transform (FFT) Step-by-Step Execution

Theoretical Foundation & Mathematical Derivation

The Discrete Fourier Transform (DFT) transforms a sequence of $N$ complex numbers $x_0, x_1, \dots, x_{N-1}$ into another sequence of frequency spectrum components $X_0, X_1, \dots, X_{N-1}$ defined by:

$$ X_k = \sum_{n=0}^{N-1} x_n \cdot W_N^{kn} \quad \text{for } k = 0, 1, \dots, N-1 $$ Where $W_N$ is the primitive $N$-th root of unity, known as the twiddle factor: $$ W_N = e^{-i \frac{2\pi}{N}} = \cos\left(\frac{2\pi}{N}\right) – i \sin\left(\frac{2\pi}{N}\right) $$

Evaluating this summation directly for all $N$ frequencies requires $N^2$ complex multiplications and additions, yielding a runtime complexity of $\mathcal{O}(N^2)$.

1. The Cooley-Tukey Decimation-in-Time (DIT) Split

When $N$ is a power of 2 ($N = 2^M$), the Cooley-Tukey Radix-2 algorithm divides the computation by splitting the sum into even-indexed samples ($n = 2m$) and odd-indexed samples ($n = 2m + 1$), where $m = 0, 1, \dots, \frac{N}{2}-1$:

$$ X_k = \sum_{m=0}^{\frac{N}{2}-1} x_{2m} \cdot W_N^{k(2m)} + \sum_{m=0}^{\frac{N}{2}-1} x_{2m+1} \cdot W_N^{k(2m+1)} $$ Factoring out the phase shift term $W_N^k$ from the odd summation yields: $$ X_k = \sum_{m=0}^{\frac{N}{2}-1} x_{2m} \cdot W_N^{2mk} + W_N^k \sum_{m=0}^{\frac{N}{2}-1} x_{2m+1} \cdot W_N^{2mk} $$

2. Twiddle Factor Halving Lemma

Using the exponent identity of complex exponentials, observe how the twiddle factor simplifies when raised to an even power:

$$ W_N^{2mk} = \left(e^{-i \frac{2\pi}{N}}\right)^{2mk} = e^{-i \frac{2\pi}{\frac{N}{2}} mk} = W_{N/2}^{mk} $$ Substituting $W_{N/2}^{mk}$ back into our split equation reveals that the two summations are exactly $\frac{N}{2}$-point DFTs: $$ X_k = \underbrace{\sum_{m=0}^{\frac{N}{2}-1} x_{2m} \cdot W_{N/2}^{mk}}{E_k \text{ (DFT of Even Samples)}} + W_N^k \underbrace{\sum{m=0}^{\frac{N}{2}-1} x_{2m+1} \cdot W_{N/2}^{mk}}_{O_k \text{ (DFT of Odd Samples)}} $$ $$ X_k = E_k + W_N^k \cdot O_k $$

3. Exploiting Symmetry & Periodicity for the Second Half

Since $E_k$ and $O_k$ are $\frac{N}{2}$-point DFTs, they are periodic with period $\frac{N}{2}$: $$ E_{k + \frac{N}{2}} = E_k \quad \text{and} \quad O_{k + \frac{N}{2}} = O_k $$ Furthermore, the twiddle factor exhibits half-period anti-symmetry: $$ W_N^{k + \frac{N}{2}} = W_N^k \cdot W_N^{\frac{N}{2}} = W_N^k \cdot e^{-i \pi} = -W_N^k $$ Evaluating the formula for the upper half of frequencies ($k + \frac{N}{2}$) gives: $$ X_{k + \frac{N}{2}} = E_{k + \frac{N}{2}} + W_N^{k + \frac{N}{2}} \cdot O_{k + \frac{N}{2}} = E_k – W_N^k \cdot O_k $$

4. The Butterfly Operation & Complexity Reduction

For every pair of frequencies $(k, k + \frac{N}{2})$, we compute the famous Butterfly Operation:

$$ \begin{cases} X_k = E_k + W_N^k \cdot O_k \ X_{k + \frac{N}{2}} = E_k – W_N^k \cdot O_k \end{cases} \quad \text{for } k = 0, 1, \dots, \frac{N}{2}-1 $$ By computing the product $W_N^k \cdot O_k$ only once and using it for both addition and subtraction, we cut the required multiplications in half at each recursive level. Applying this divide-and-conquer strategy recursively across $\log_2(N)$ stages reduces the total arithmetic complexity from $\mathcal{O}(N^2)$ down to: $$ \mathcal{O}(N \log_2 N) $$

---

Initial Input Signal $x_n$

$$ \big[ 1.00, 2.00, 3.00, 4.00, 5.00, 6.00, 7.00, 8.00 \big] $$

---

Step 1: Bit-Reversal Permutation (Theory $\rightarrow$ Practice Mapping)

[!NOTE] To perform the FFT iteratively (bottom-up without recursion), we must reorder the input array according to the bit-reversed binary representation of their indices. This places adjacent even and odd leaf elements right next to each other.

How to Remember This Order:

Method 1: The “Mirror” Trick Write the original index in binary (e.g., index 1 is 001), mirror the bits backwards (100), and convert it back to a decimal number (4). Thus, index 1 becomes index 4.

Method 2: The “Evens & Odds” Split (Decimation-in-Time) Continuously split the sequence into even-indexed and odd-indexed samples:

• Pass 1: Original 0, 1, 2, 3, 4, 5, 6, 7 splits into Evens [0, 2, 4, 6] and Odds [1, 3, 5, 7].
• Pass 2: Split those halves again. 0, 2, 4, 6 becomes [0, 4] and [2, 6]. 1, 3, 5, 7 becomes [1, 5] and [3, 7].
• Result: 0, 4, 2, 6, 1, 5, 3, 7

Original Index $n$	Binary	Bit-Reversed Index	Reordered Binary	Value $x_n$
0	000	0	000	1.00
1	001	4	100	2.00
2	010	2	010	3.00
3	011	6	110	4.00
4	100	1	001	5.00
5	101	5	101	6.00
6	110	3	011	7.00
7	111	7	111	8.00

Array State After Bit-Reversal Reordering

$$ \big[ 1.00, 5.00, 3.00, 7.00, 2.00, 6.00, 4.00, 8.00 \big] $$

---

Step 2: Butterfly Stage 1 (Sub-problem DFT Size $N_{\text{sub}} = 2$)

In this stage, we combine adjacent pairs of size-1 DFTs into size-2 DFTs.

• Base Twiddle Factor: $W_{2} = e^{-i \frac{2\pi}{2}}$

The Gap Rule

The distance between the two elements in a butterfly pair is always exactly half the size of the sub-problem. Since $N_{\text{sub}} = 2$, you pair elements that are 1 step(s) apart.

The “Add & Subtract” Trick: Because the gap is 1 and the twiddle factor used here is exactly 1.00, this entire stage simplifies. You do not need to memorize complex formulas; just chunk the array into pairs and calculate $A + B$ for the first spot and $A – B$ for the second spot.

Combining Sub-block [0..0] (Evens $E_k$) with [1..1] (Odds $O_k$)

Butterfly Pair $j = 0$ (Indices 0 & 1)

• Twiddle Factor: $W_{2}^{0} = 1 = 1.00$
• Theory Mapping: $E_{0} = X_{0} = 1.00$ and $O_{0} = X_{1} = 5.00$
• Twiddle Multiplication: $W_{2}^{0} \cdot O_{0} = 1.00 \cdot 5.00 = 5.00$
• Output Calculation: $$ X_{0} = E_{0} + (W_{2}^{0} \cdot O_{0}) = 1.00 + 5.00 = \mathbf{6.00} $$ $$ X_{1} = E_{0} – (W_{2}^{0} \cdot O_{0}) = 1.00 – 5.00 = \mathbf{-4.00} $$

Combining Sub-block [2..2] (Evens $E_k$) with [3..3] (Odds $O_k$)

Butterfly Pair $j = 0$ (Indices 2 & 3)

• Twiddle Factor: $W_{2}^{0} = 1 = 1.00$
• Theory Mapping: $E_{0} = X_{2} = 3.00$ and $O_{0} = X_{3} = 7.00$
• Twiddle Multiplication: $W_{2}^{0} \cdot O_{0} = 1.00 \cdot 7.00 = 7.00$
• Output Calculation: $$ X_{2} = E_{0} + (W_{2}^{0} \cdot O_{0}) = 3.00 + 7.00 = \mathbf{10.00} $$ $$ X_{3} = E_{0} – (W_{2}^{0} \cdot O_{0}) = 3.00 – 7.00 = \mathbf{-4.00} $$

Combining Sub-block [4..4] (Evens $E_k$) with [5..5] (Odds $O_k$)

Butterfly Pair $j = 0$ (Indices 4 & 5)

• Twiddle Factor: $W_{2}^{0} = 1 = 1.00$
• Theory Mapping: $E_{0} = X_{4} = 2.00$ and $O_{0} = X_{5} = 6.00$
• Twiddle Multiplication: $W_{2}^{0} \cdot O_{0} = 1.00 \cdot 6.00 = 6.00$
• Output Calculation: $$ X_{4} = E_{0} + (W_{2}^{0} \cdot O_{0}) = 2.00 + 6.00 = \mathbf{8.00} $$ $$ X_{5} = E_{0} – (W_{2}^{0} \cdot O_{0}) = 2.00 – 6.00 = \mathbf{-4.00} $$

Combining Sub-block [6..6] (Evens $E_k$) with [7..7] (Odds $O_k$)

Butterfly Pair $j = 0$ (Indices 6 & 7)

• Twiddle Factor: $W_{2}^{0} = 1 = 1.00$
• Theory Mapping: $E_{0} = X_{6} = 4.00$ and $O_{0} = X_{7} = 8.00$
• Twiddle Multiplication: $W_{2}^{0} \cdot O_{0} = 1.00 \cdot 8.00 = 8.00$
• Output Calculation: $$ X_{6} = E_{0} + (W_{2}^{0} \cdot O_{0}) = 4.00 + 8.00 = \mathbf{12.00} $$ $$ X_{7} = E_{0} – (W_{2}^{0} \cdot O_{0}) = 4.00 – 8.00 = \mathbf{-4.00} $$

Array State After Stage 1: $$ \big[ 6.00, -4.00, 10.00, -4.00, 8.00, -4.00, 12.00, -4.00 \big] $$

---

Step 3: Butterfly Stage 2 (Sub-problem DFT Size $N_{\text{sub}} = 4$)

In this stage, we combine adjacent pairs of size-2 DFTs into size-4 DFTs.

• Base Twiddle Factor: $W_{4} = e^{-i \frac{2\pi}{4}}$

The Gap Rule

The distance between the two elements in a butterfly pair is always exactly half the size of the sub-problem. Since $N_{\text{sub}} = 4$, you pair elements that are 2 step(s) apart.

Combining Sub-block [0..1] (Evens $E_k$) with [2..3] (Odds $O_k$)

Butterfly Pair $j = 0$ (Indices 0 & 2)

• Twiddle Factor: $W_{4}^{0} = 1 = 1.00$
• Theory Mapping: $E_{0} = X_{0} = 6.00$ and $O_{0} = X_{2} = 10.00$
• Twiddle Multiplication: $W_{4}^{0} \cdot O_{0} = 1.00 \cdot 10.00 = 10.00$
• Output Calculation: $$ X_{0} = E_{0} + (W_{4}^{0} \cdot O_{0}) = 6.00 + 10.00 = \mathbf{16.00} $$ $$ X_{2} = E_{0} – (W_{4}^{0} \cdot O_{0}) = 6.00 – 10.00 = \mathbf{-4.00} $$

Butterfly Pair $j = 1$ (Indices 1 & 3)

• Twiddle Factor: $W_{4}^{1} = e^{-i \frac{2\pi}{4}} = -1.00i$
• Theory Mapping: $E_{1} = X_{1} = -4.00$ and $O_{1} = X_{3} = -4.00$
• Twiddle Multiplication: $W_{4}^{1} \cdot O_{1} = -1.00i \cdot -4.00 = 4.00i$
• Output Calculation: $$ X_{1} = E_{1} + (W_{4}^{1} \cdot O_{1}) = -4.00 + 4.00i = \mathbf{(-4.00 + 4.00i)} $$ $$ X_{3} = E_{1} – (W_{4}^{1} \cdot O_{1}) = -4.00 – 4.00i = \mathbf{(-4.00 – 4.00i)} $$

Combining Sub-block [4..5] (Evens $E_k$) with [6..7] (Odds $O_k$)

Butterfly Pair $j = 0$ (Indices 4 & 6)

• Twiddle Factor: $W_{4}^{0} = 1 = 1.00$
• Theory Mapping: $E_{0} = X_{4} = 8.00$ and $O_{0} = X_{6} = 12.00$
• Twiddle Multiplication: $W_{4}^{0} \cdot O_{0} = 1.00 \cdot 12.00 = 12.00$
• Output Calculation: $$ X_{4} = E_{0} + (W_{4}^{0} \cdot O_{0}) = 8.00 + 12.00 = \mathbf{20.00} $$ $$ X_{6} = E_{0} – (W_{4}^{0} \cdot O_{0}) = 8.00 – 12.00 = \mathbf{-4.00} $$

Butterfly Pair $j = 1$ (Indices 5 & 7)

• Twiddle Factor: $W_{4}^{1} = e^{-i \frac{2\pi}{4}} = -1.00i$
• Theory Mapping: $E_{1} = X_{5} = -4.00$ and $O_{1} = X_{7} = -4.00$
• Twiddle Multiplication: $W_{4}^{1} \cdot O_{1} = -1.00i \cdot -4.00 = 4.00i$
• Output Calculation: $$ X_{5} = E_{1} + (W_{4}^{1} \cdot O_{1}) = -4.00 + 4.00i = \mathbf{(-4.00 + 4.00i)} $$ $$ X_{7} = E_{1} – (W_{4}^{1} \cdot O_{1}) = -4.00 – 4.00i = \mathbf{(-4.00 – 4.00i)} $$

Array State After Stage 2: $$ \big[ 16.00, (-4.00 + 4.00i), -4.00, (-4.00 – 4.00i), 20.00, (-4.00 + 4.00i), -4.00, (-4.00 – 4.00i) \big] $$

---

Step 4: Butterfly Stage 3 (Sub-problem DFT Size $N_{\text{sub}} = 8$)

In this stage, we combine adjacent pairs of size-4 DFTs into size-8 DFTs.

• Base Twiddle Factor: $W_{8} = e^{-i \frac{2\pi}{8}}$

The Gap Rule

The distance between the two elements in a butterfly pair is always exactly half the size of the sub-problem. Since $N_{\text{sub}} = 8$, you pair elements that are 4 step(s) apart.

Combining Sub-block [0..3] (Evens $E_k$) with [4..7] (Odds $O_k$)

Butterfly Pair $j = 0$ (Indices 0 & 4)

• Twiddle Factor: $W_{8}^{0} = 1 = 1.00$
• Theory Mapping: $E_{0} = X_{0} = 16.00$ and $O_{0} = X_{4} = 20.00$
• Twiddle Multiplication: $W_{8}^{0} \cdot O_{0} = 1.00 \cdot 20.00 = 20.00$
• Output Calculation: $$ X_{0} = E_{0} + (W_{8}^{0} \cdot O_{0}) = 16.00 + 20.00 = \mathbf{36.00} $$ $$ X_{4} = E_{0} – (W_{8}^{0} \cdot O_{0}) = 16.00 – 20.00 = \mathbf{-4.00} $$

Butterfly Pair $j = 1$ (Indices 1 & 5)

• Twiddle Factor: $W_{8}^{1} = e^{-i \frac{2\pi}{8}} = (0.71 – 0.71i)$
• Theory Mapping: $E_{1} = X_{1} = (-4.00 + 4.00i)$ and $O_{1} = X_{5} = (-4.00 + 4.00i)$
• Twiddle Multiplication: $W_{8}^{1} \cdot O_{1} = (0.71 – 0.71i) \cdot (-4.00 + 4.00i) = 5.66i$
• Output Calculation: $$ X_{1} = E_{1} + (W_{8}^{1} \cdot O_{1}) = (-4.00 + 4.00i) + 5.66i = \mathbf{(-4.00 + 9.66i)} $$ $$ X_{5} = E_{1} – (W_{8}^{1} \cdot O_{1}) = (-4.00 + 4.00i) – 5.66i = \mathbf{(-4.00 – 1.66i)} $$

Butterfly Pair $j = 2$ (Indices 2 & 6)

• Twiddle Factor: $W_{8}^{2} = e^{-i \frac{4\pi}{8}} = -1.00i$
• Theory Mapping: $E_{2} = X_{2} = -4.00$ and $O_{2} = X_{6} = -4.00$
• Twiddle Multiplication: $W_{8}^{2} \cdot O_{2} = -1.00i \cdot -4.00 = 4.00i$
• Output Calculation: $$ X_{2} = E_{2} + (W_{8}^{2} \cdot O_{2}) = -4.00 + 4.00i = \mathbf{(-4.00 + 4.00i)} $$ $$ X_{6} = E_{2} – (W_{8}^{2} \cdot O_{2}) = -4.00 – 4.00i = \mathbf{(-4.00 – 4.00i)} $$

Butterfly Pair $j = 3$ (Indices 3 & 7)

• Twiddle Factor: $W_{8}^{3} = e^{-i \frac{6\pi}{8}} = (-0.71 – 0.71i)$
• Theory Mapping: $E_{3} = X_{3} = (-4.00 – 4.00i)$ and $O_{3} = X_{7} = (-4.00 – 4.00i)$
• Twiddle Multiplication: $W_{8}^{3} \cdot O_{3} = (-0.71 – 0.71i) \cdot (-4.00 – 4.00i) = 5.66i$
• Output Calculation: $$ X_{3} = E_{3} + (W_{8}^{3} \cdot O_{3}) = (-4.00 – 4.00i) + 5.66i = \mathbf{(-4.00 + 1.66i)} $$ $$ X_{7} = E_{3} – (W_{8}^{3} \cdot O_{3}) = (-4.00 – 4.00i) – 5.66i = \mathbf{(-4.00 – 9.66i)} $$

Array State After Stage 3: $$ \big[ 36.00, (-4.00 + 9.66i), (-4.00 + 4.00i), (-4.00 + 1.66i), -4.00, (-4.00 – 1.66i), (-4.00 – 4.00i), (-4.00 – 9.66i) \big] $$

---

Final FFT Output $X_k$ (Frequency Domain)

Each element $X_k$ represents the amplitude and phase of the frequency component $k$ in the signal:

$$ \big[ 36.00, (-4.00 + 9.66i), (-4.00 + 4.00i), (-4.00 + 1.66i), -4.00, (-4.00 – 1.66i), (-4.00 – 4.00i), (-4.00 – 9.66i) \big] $$