← 11.02 Properties of the DFT & Twiddle Factors | Chapter 11 Map | 11.04 Radix-2 Decimation-In-Frequency FFT Algorithm (DIF-FFT) →

11.03 Radix-2 Decimation-In-Time FFT Algorithm (DIT-FFT)

Alright — let’s tackle one of the most high-yielding and point-generating topics in the entire fast-algorithms curriculum: the Radix-2 Decimation-In-Time FFT (DIT-FFT) Algorithm!

On every university exam, the examiner is guaranteed to ask you to either:

1. State and derive the Radix-2 DIT-FFT decomposition from the first principles of the discrete Fourier transform (typically a 10-mark theory question).
2. Calculate the $N$-point DFT of a given finite-duration sequence (such as $N=4$ or $N=8$) using a step-by-step decimation butterfly workflow and draw the complete signal-flow butterfly graph.

Rather than memorizing abstract flowgraphs, we are going to break down the exact mathematical splitting mechanism, master the binary bit-reversal sorting rules, and solve high-yield past year exam questions with absolute numerical precision. Let’s lock down these marks!

---

1. The Mathematical Splitting Mechanism (Derivation)

Core Concept: Decimation-In-Time

Decimation-In-Time (DIT) means we recursively divide the time-domain input sequence $x[n]$ of length $N$ into smaller and smaller subsequences based on their indices, compute the DFT of those subsequences, and then recombine them using complex Twiddle Factors $W_N^k$ to synthesize the total spectrum $X[k]$.

1.1 The Radix-2 Constraint

To perform a symmetric, binary decimation, the total number of points $N$ must be a power of $2$: $N=2^L⟹L={\log }_2(N)extwhereL\in {\mathbb{Z}}^{+}$ Here, $L$ represents the number of decimation stages required in our butterfly network. If $N$ is not a power of 2, we must zero-pad the sequence to the nearest power of 2 to satisfy the Radix-2 criteria.

---

1.2 Mathematical Derivation of Even vs. Odd Decimation

Let’s start from the standard definition of the $N$-point Discrete Fourier Transform (DFT): $X[k]={\sum }_{n=0}^{N-1}x[n]W_N^{nk}extfor0\le k\le N-1$

We can split this single summation over $n=0,1,\dots ,N-1$ into two separate summations: one over even-indexed samples ($n=2r$) and one over odd-indexed samples ($n=2r+1$): $X[k]={\sum }_{r=0}^{N/2-1}x[2r]W_N^{(2r)k}+{\sum }_{r=0}^{N/2-1}x[2r+1]W_N^{(2r+1)k}$

Now, let’s analyze the twiddle factor exponents. Using the definition of the twiddle factor W_N = e^{-jrac{2\pi}{N}}: W_N^{(2r)k} = e^{-jrac{2\pi}{N}(2rk)} = e^{-jrac{2\pi}{N/2}(rk)} = W_{N/2}^{rk}

Substitute this identity back into our split summation equation: $X[k]={\sum }_{r=0}^{N/2-1}x[2r]W_{N/2}^{rk}+W_N^k{\sum }_{r=0}^{N/2-1}x[2r+1]W_{N/2}^{rk}$

Let’s define two new $(N/2)$-point sequences representing the even-indexed and odd-indexed samples:

• $g[r]=x[2r]extforr=0,1,\dots ,N/2-1extEven-indexedsubsequence$
• $h[r]=x[2r+1]extforr=0,1,\dots ,N/2-1extOdd-indexedsubsequence$

Thus, the corresponding $(N/2)$-point DFTs of these subsequences are: $G[k]={\sum }_{r=0}^{N/2-1}g[r]W_{N/2}^{rk}$ $H[k]={\sum }_{r=0}^{N/2-1}h[r]W_{N/2}^{rk}$

We can now express the total $N$-point DFT $X[k]$ as a simple linear combination of these two $(N/2)$-point DFTs: $X[k]=G[k]+W_N^{k}H[k]extfor0\le k\le N-1$

---

1.3 Exploiting Symmetries: The Half-Range Butterfly Equations

Since $G[k]$ and $H[k]$ are $(N/2)$-point DFTs, they are naturally periodic with period $N/2$:

ight] = G[k]$$ $$H\left[k + rac{N}{2} ight] = H[k]$$ Additionally, we recall the highly high-yield **Symmetry Property** of twiddle factors: $$W_N^{k + N/2} = -W_N^k$$ Let's evaluate $X[k + N/2]$ for the second half of our frequency bins, where $0 \le k \le N/2 - 1$: $$X\left[k + rac{N}{2} ight] = G\left[k + rac{N}{2} ight] + W_N^{k + N/2} H\left[k + rac{N}{2} ight]$$ $$X\left[k + rac{N}{2} ight] = G[k] - W_N^k H[k]$$ This is the ultimate mathematical triumph of the FFT! We can compute the full range of frequency spectrum bins using only the first half calculations of $G[k]$ and $H[k]$: $$egin{aligned} \mathbf{X[k]} &\mathbf{= G[k] + W_N^k H[k]} \quad && ext{for } 0 \le k \le rac{N}{2} - 1 \\ \mathbf{X\left[k + rac{N}{2} ight]} &\mathbf{= G[k] - W_N^k H[k]} \quad && ext{for } 0 \le k \le rac{N}{2} - 1 \end{aligned}$$ --- ## 2. Signal-Flow Butterfly Geometry The equations derived above map directly to a simple, visual signal-flow block called the **Butterfly**. ### 2.1 The Basic DIT Butterfly Unit ``` G[k] o──────────────────────────────> X[k] = G[k] + W_N^k · H[k] \ / \ / \ / \ / \ / \ / \ / \ / \ / X X / \ / \ / \ / \ / \ / \ / W_N^k \ H[k] o──────( × )─────────────────( -1 )──> X[k+N/2] = G[k] - W_N^k · H[k] ``` * **Twiddle Multiplier:** The bottom input $H[k]$ is multiplied by $W_N^k$ *before* entering the cross-addition branches. * **Summing Node (Top Output):** Adds $G[k]$ to $W_N^k H[k]$. * **Subtracting Node (Bottom Output):** Subtracts $W_N^k H[k]$ from $G[k]$ (implemented by multiplying by a branch factor of $-1$ and summing). --- ## 3. Bit-Reversal Input Sorting Because the decimation-in-time algorithm recursively divides indices into even and odd bins at each stage, the input samples $x[n]$ must be shuffled into a unique **bit-reversed order** before they are fed into Stage 1 of the butterfly network. ### 3.1 The Bit-Reversal Algorithm To find the bit-reversed index of a sample index $n$: 1. Write the index $n$ in its **binary representation** using $L = \log_2(N)$ bits. 2. **Reverse** the order of the bits (from right-to-left). 3. Convert the reversed binary string back into a **decimal integer**. ### 3.2 Master Bit-Reversal Mapping Table ($N=8$, $L=3$ bits) | Original Time Index ($n$) | Decimal | Binary ($b_2 b_1 b_0$) | Reversed Binary ($b_0 b_1 b_2$) | Reversed Index | Shuffled DIT Input | | :---: | :---: | :---: | :---: | :---: | :---: | | **$x[0]$** | 0 | `000` | `000` | 0 | **$x[0]$** | | **$x[1]$** | 1 | `001` | `100` | 4 | **$x[4]$** | | **$x[2]$** | 2 | `010` | `010` | 2 | **$x[2]$** | | **$x[3]$** | 3 | `011` | `110` | 6 | **$x[6]$** | | **$x[4]$** | 4 | `100` | `001` | 1 | **$x[1]$** | | **$x[5]$** | 5 | `101` | `101` | 5 | **$x[5]$** | | **$x[6]$** | 6 | `110` | `011` | 3 | **$x[3]$** | | **$x[7]$** | 7 | `111` | `111` | 7 | **$x[7]$** | > [!TIP] > > **DIT Input Shuffling Memory Trick:** > Notice that the shuffled input order splits into two clear halves: > * The first half contains all the **even-indexed** samples, bit-reversed: $\{x[0], x[4], x[2], x[6]\}$. > * The second half contains all the **odd-indexed** samples, bit-reversed: $\{x[1], x[5], x[3], x[7]\}$. > > Remembering this "even first, odd second" structure will save you precious minutes in exams! --- ## 4. High-Yield Solved "Exam Killers" ### 4.1 The Verbatim 10-Mark 8-Point DIT-FFT Classic > [!question] **KUET Exam Problem** > > Find the 8-point DFT of the causal sequence: > $$x[n] = \{0, 1, 2, 3, 0, 0, 0, 0\} \quad ext{for } N=8$$ > using the Radix-2 Decimation-In-Time (DIT) FFT algorithm. Show all intermediate calculations for Stage 1, Stage 2, and Stage 3, and draw the complete butterfly signal-flow diagram. #### Step 1: Pre-calculate the Twiddle Factors ($N=8$) Let's compute the complex twiddle factors $W_8^k = e^{-jrac{2\pi}{8}k} = e^{-jrac{\pi}{4}k}$ for $k = 0, 1, 2, 3$: * $W_8^0 = e^{0} = \mathbf{1}$ * $W_8^1 = e^{-j\pi/4} = \cos(\pi/4) - j\sin(\pi/4) = rac{1}{\sqrt{2}} - jrac{1}{\sqrt{2}} pprox \mathbf{0.707 - j0.707}$ * $W_8^2 = e^{-j\pi/2} = \cos(\pi/2) - j\sin(\pi/2) = \mathbf{-j}$ * $W_8^3 = e^{-j3\pi/4} = -rac{1}{\sqrt{2}} - jrac{1}{\sqrt{2}} pprox \mathbf{-0.707 - j0.707}$ --- #### Step 2: Set Up Stage 0 Shuffled Inputs (Bit-Reversed Order) Rearrange the input sequence $x[n] = \{0, 1, 2, 3, 0, 0, 0, 0\}$ using our bit-reversal mapping: * $s_0[0] = x[0] = 0$ * $s_0[1] = x[4] = 0$ * $s_0[2] = x[2] = 2$ * $s_0[3] = x[6] = 0$ * $s_0[4] = x[1] = 1$ * $s_0[5] = x[5] = 0$ * $s_0[6] = x[3] = 3$ * $s_0[7] = x[7] = 0$ $$ ext{Stage 0 Array: } \mathbf{\{0, 0, 2, 0, 1, 0, 3, 0\}}$$ --- #### Step 3: Compute Stage 1 (2-Point DFTs) In Stage 1, we combine adjacent pairs $(s_0[2r], s_0[2r+1])$ using the 2-point twiddle factor $W_2^0 = 1$: $$egin{aligned} s_1[2r] &= s_0[2r] + W_2^0 \cdot s_0[2r+1] = s_0[2r] + s_0[2r+1] \ s_1[2r+1] &= s_0[2r] - W_2^0 \cdot s_0[2r+1] = s_0[2r] - s_0[2r+1] \end{aligned}$$ * **Pair 1 (Indices 0, 1):** * $s_1[0] = s_0[0] + s_0[1] = 0 + 0 = \mathbf{0}$ * $s_1[1] = s_0[0] - s_0[1] = 0 - 0 = \mathbf{0}$ * **Pair 2 (Indices 2, 3):** * $s_1[2] = s_0[2] + s_0[3] = 2 + 0 = \mathbf{2}$ * $s_1[3] = s_0[2] - s_0[3] = 2 - 0 = \mathbf{2}$ * **Pair 3 (Indices 4, 5):** * $s_1[4] = s_0[4] + s_0[5] = 1 + 0 = \mathbf{1}$ * $s_1[5] = s_0[4] - s_0[5] = 1 - 0 = \mathbf{1}$ * **Pair 4 (Indices 6, 7):** * $s_1[6] = s_0[6] + s_0[7] = 3 + 0 = \mathbf{3}$ * $s_1[7] = s_0[6] - s_0[7] = 3 - 0 = \mathbf{3}$ $$ ext{Stage 1 Output Array: } \mathbf{\{0, 0, 2, 2, 1, 1, 3, 3\}}$$ --- #### Step 4: Compute Stage 2 (4-Point DFTs) In Stage 2, we group the elements into two sets of 4: $\{s_1[0], s_1[1], s_1[2], s_1[3]\}$ and $\{s_1[4], s_1[5], s_1[6], s_1[7]\}$. The butterfly width is now 2. The twiddle factors are $W_4^0 = W_8^0 = 1$ and $W_4^1 = W_8^2 = -j$. $$egin{aligned} s_2[k] &= s_1[k] + W_8^{2k} \cdot s_1[k+2] \ s_2[k+2] &= s_1[k] - W_8^{2k} \cdot s_1[k+2] \quad ext{for } k = 0, 1 ext{ in each block} \end{aligned}$$ * **Block 1 (Even-part combination):** * $s_2[0] = s_1[0] + W_8^0 \cdot s_1[2] = 0 + (1)(2) = \mathbf{2}$ * $s_2[1] = s_1[1] + W_8^2 \cdot s_1[3] = 0 + (-j)(2) = \mathbf{-2j}$ * $s_2[2] = s_1[0] - W_8^0 \cdot s_1[2] = 0 - (1)(2) = \mathbf{-2}$ * $s_2[3] = s_1[1] - W_8^2 \cdot s_1[3] = 0 - (-j)(2) = \mathbf{2j}$ * **Block 2 (Odd-part combination):** * $s_2[4] = s_1[4] + W_8^0 \cdot s_1[6] = 1 + (1)(3) = \mathbf{4}$ * $s_2[5] = s_1[5] + W_8^2 \cdot s_1[7] = 1 + (-j)(3) = \mathbf{1 - 3j}$ * $s_2[6] = s_1[4] - W_8^0 \cdot s_1[6] = 1 - (1)(3) = \mathbf{-2}$ * $s_2[7] = s_1[5] - W_8^2 \cdot s_1[7] = 1 - (-j)(3) = \mathbf{1 + 3j}$ $$ ext{Stage 2 Output Array: } \mathbf{\{2, -2j, -2, 2j, 4, 1-3j, -2, 1+3j\}}$$ --- #### Step 5: Compute Stage 3 (8-Point DFT Combinations) In Stage 3, we combine Block 1 and Block 2. The butterfly width is now 4. We apply twiddle multipliers $W_8^0, W_8^1, W_8^2, W_8^3$: $$egin{aligned} X[k] &= s_2[k] + W_8^k \cdot s_2[k+4] \ X[k+4] &= s_2[k] - W_8^k \cdot s_2[k+4] \quad ext{for } 0 \le k \le 3 \end{aligned}$$ * **Frequency Bin $k=0$ and $k=4$:** * $W_8^0 \cdot s_2[4] = (1)(4) = 4$ * $X[0] = s_2[0] + 4 = 2 + 4 = \mathbf{6}$ * $X[4] = s_2[0] - 4 = 2 - 4 = \mathbf{-2}$ * **Frequency Bin $k=1$ and $k=5$:** * $W_8^1 \cdot s_2[5] = (0.707 - j0.707)(1 - 3j) = [0.707(1) - 0.707(3)] + j[-0.707(1) - 0.707(3)] = -1.414 - j2.828$ * $X[1] = s_2[1] + (-1.414 - j2.828) = -2j - 1.414 - j2.828 = \mathbf{-1.414 - j4.828}$ * $X[5] = s_2[1] - (-1.414 - j2.828) = -2j + 1.414 + j2.828 = \mathbf{1.414 + j0.828}$ * **Frequency Bin $k=2$ and $k=6$:** * $W_8^2 \cdot s_2[6] = (-j)(-2) = 2j$ * $X[2] = s_2[2] + 2j = \mathbf{-2 + 2j}$ * $X[6] = s_2[2] - 2j = \mathbf{-2 - 2j}$ * **Frequency Bin $k=3$ and $k=7$:** * $W_8^3 \cdot s_2[7] = (-0.707 - j0.707)(1 + 3j) = [-0.707(1) + 0.707(3)] + j[-0.707(1) - 0.707(3)] = 1.414 - j2.828$ * $X[3] = s_2[3] + (1.414 - j2.828) = 2j + 1.414 - j2.828 = \mathbf{1.414 - j0.828}$ * $X[7] = s_2[3] - (1.414 - j2.828) = 2j - 1.414 + j2.828 = \mathbf{-1.414 + j4.828}$ --- #### Step 6: Final DFT Output Assembly & Symmetry Check Let's assemble the calculated DFT array: $$\mathbf{X[k] = \left\{6, \; -1.414-j4.828, \; -2+2j, \; 1.414-j0.828, \; -2, \; 1.414+j0.828, \; -2-2j, \; -1.414+j4.828 ight\}}$$ > [!TIP] > > **Real-Signal Conjugate Symmetry Audit:** > Since our original time sequence $x[n]$ is real-valued, its DFT spectrum MUST satisfy conjugate symmetry: > $$X[k] = X^*[N - k]$$ > Let's check our calculations: > * $X[1] = -1.414 - j4.828 \iff X[7] = -1.414 + j4.828 \quad ext{{Conjugates! Verified!}}$ > * $X[2] = -2 + 2j \iff X[6] = -2 - 2j \quad ext{{Conjugates! Verified!}}$ > * $X[3] = 1.414 - j0.828 \iff X[5] = 1.414 + j0.828 \quad ext{{Conjugates! Verified!}}$ > This verification ensures that you will receive full marks with 100% confidence! --- ### Step 7: Signal-Flow Butterfly Graph ($N=8$) ``` Stage 0 (Input) Stage 1 (2-Point) Stage 2 (4-Point) Stage 3 (Output) x[0] = 0 o───────────────( × )───o───────────────( × )───o───────────────( × )───o X[0] = 6 \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / x[4] = 0 o──────\──/─────( -1)───o─────\───/─────( -1)───o─────\───/─────( -1)───o X[4] = -2 X \ / \ \ / / \ X \ X / \ / \ \ / x[2] = 2 o────o─────o────( × )───o─────o───o─────( × )───o───\─/───o─────( × )───o X[2] = -2+2j \ / \ / \ / \ / \ / \ / \/ \ / \ / \ / /\ \ / \ / \ / / \ \ / x[6] = 0 o──────\──/─────( -1)───o─────\───/─────( -1)────o────\───\───/─( -1)───o X[6] = -2-2j \X─────────────────────X───────────────────────\───\X /\ / \ \ / / \ / \ \/ x[1] = 1 o─────o────o────( × )───o───o─────o─────( × )───o────────/\────o─( × )───o X[1] = -1.41-j4.83 \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / X \ / x[5] = 0 o──────\──/─────( -1)───o─────\───/─────( -1)───o───/─\────────\──/─( -1)──o X[5] = 1.41+j0.83 \X─────────────────────X───────────────────/───\────────\/ /\ / \ / \ / / \ / \ / \ / x[3] = 3 o─────o────o────( × )───o───o─────o─────( × )───o─────────\────o─────( × )──o X[3] = 1.41-j0.83 \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / x[7] = 0 o──────\──/─────( -1)───o─────\───/─────( -1)───o─────────\_/───────────( -1)──o X[7] = -1.41+j4.83 ``` --- ### 4.2 The 3-Mark 4-Point DIT-FFT Quick-Solver [PYQ 2024] > [!question] **2024 Exam Section B Q. 8b** > > Given causal sequence $x[n] = \{0, 1, 2, 3\}$. Find the 4-point DFT spectrum $X[k]$ using the Radix-2 DIT-FFT algorithm. #### Step 1: Bit-Reverse the Input Sequence ($N=4$, $L=2$) * $n=0 o `00` o `00` o 0 \implies s_0[0] = x[0] = 0$ * $n=1 o `01` o `10` o 2 \implies s_0[1] = x[2] = 2$ * $n=2 o `10` o `01` o 1 \implies s_0[2] = x[1] = 1$ * $n=3 o `11` o `11` o 3 \implies s_0[3] = x[3] = 3$ $$ ext{Stage 0 Array: } \mathbf{\{0, 2, 1, 3\}}$$ #### Step 2: Compute Stage 1 (2-Point DFTs, Twiddle $W_2^0 = 1$) * **Pair 1 (Indices 0, 1):** * $s_1[0] = s_0[0] + s_0[1] = 0 + 2 = \mathbf{2}$ * $s_1[1] = s_0[0] - s_0[1] = 0 - 2 = \mathbf{-2}$ * **Pair 2 (Indices 2, 3):** * $s_1[2] = s_0[2] + s_0[3] = 1 + 3 = \mathbf{4}$ * $s_1[3] = s_0[2] - s_0[3] = 1 - 3 = \mathbf{-2}$ $$ ext{Stage 1 Output Array: } \mathbf{\{2, -2, 4, -2\}}$$ #### Step 3: Compute Stage 2 (4-Point Combination DFT) The twiddle factors are $W_4^0 = 1$ and $W_4^1 = -j$: * **Bin $k=0$ and $k=2$:** * $X[0] = s_1[0] + W_4^0 \cdot s_1[2] = 2 + (1)(4) = \mathbf{6}$ * $X[2] = s_1[0] - W_4^0 \cdot s_1[2] = 2 - (1)(4) = \mathbf{-2}$ * **Bin $k=1$ and $k=3$:** * $X[1] = s_1[1] + W_4^1 \cdot s_1[3] = -2 + (-j)(-2) = \mathbf{-2 + 2j}$ * $X[3] = s_1[1] - W_4^1 \cdot s_1[3] = -2 - (-j)(-2) = \mathbf{-2 - 2j}$ $$ ext{Final 4-Point DFT Spectrum: } \mathbf{X[k] = \{6, \; -2+2j, \; -2, \; -2-2j\}}$$ --- ## 5. Common Mistakes That Cost Marks > [!warning] **Critical Exam Pitfalls** > > 1. **DIT vs. DIF Sorting Confusion:** Shuffling the inputs of DIT-FFT in bit-reversed order while keeping outputs in natural order, but accidentally doing the same for DIF! Remember: **DIT-FFT has bit-reversed inputs and natural outputs**, while **DIF-FFT has natural inputs and bit-reversed outputs**. Shuffling both ways or swapping them will earn you a solid zero from the examiner. > 2. **Mismapping Twiddle Factors in Stage 2:** In Stage 2 of an 8-point DIT-FFT, students often multiply the bottom branches by $W_8^1$ instead of $W_8^2$ (which is $W_4^1 = -j$). Remember: Stage 2 represents 4-point DFT blocks, so the twiddle exponent steps by $2$ ($W_8^{2k} \implies W_8^0$ and $W_8^2$). > 3. **Twiddle Multiplier Placement Error:** Placing the twiddle multiplier $W_N^k$ on the feedback loop or on the addition node instead of strictly on the bottom input branch before the subtraction node. Make sure your arrow directions and multipliers match the standard flow graph perfectly. --- ## 6. PYQ Bank — Verbatim Questions > [!question] **2025 Exam Section B Q. 8a [10 Marks]** > > What is DIT-FFT algorithm? Give the computation efficiency of FFT over DFT. > * **Answer Plan:** Define Decimation-In-Time as the recursive splitting of $x[n]$ into even and odd indices to compute the DFT. Derive the butterfly equations $X[k] = G[k] + W_N^k H[k]$ and $X[k+N/2] = G[k] - W_N^k H[k]$ from the forward DFT definition. Present the computational efficiency analysis (direct DFT $O(N^2)$ complex multiplications vs. Radix-2 FFT $O(N \log_2 N)$) with a comparison lookup table. > [!question] **2024 Exam Section B Q. 8b [3 Marks]** > > Given causal sequence $x[n] = \{0, 1, 2, 3\}$. Find the 4-point DFT spectrum $X[k]$ using the Radix-2 DIT-FFT algorithm. > * **Answer Plan:** Apply bit-reversal sorting on the input to get $\{0, 2, 1, 3\}$. Compute Stage 1 outputs using 2-point butterflies to get $\{2, -2, 4, -2\}$. Combine in Stage 2 using $W_4^0 = 1$ and $W_4^1 = -j$ to calculate the final spectrum $X[k] = \{6, -2+2j, -2, -2-2j\}$. --- ## 7. My Self-Check Checklist - [ ] Can you derive the half-range butterfly equations $X[k] = G[k] + W_N^k H[k]$ from the forward DFT summation? - [ ] Do you know how to perform bit-reversal sorting on an 8-point sequence without looking at the reference table? - [ ] Did you remember that DIT-FFT has bit-reversed inputs and normally ordered outputs? - [ ] Is every twiddle factor exponent in Stage 1, Stage 2, and Stage 3 labeled correctly on your flow graph? - [ ] Have you verified that your final real-sequence DFT output satisfies conjugate symmetry $X[k] = X^*[N-k]$?