← 11.03 Radix-2 Decimation-In-Time FFT Algorithm (DIT-FFT) | Chapter 11 Map | Chapter 12 Map →

11.04 Radix-2 Decimation-In-Frequency FFT Algorithm (DIF-FFT)

Alright — let’s tackle the final transform-domain topic under Instructor 1: The Radix-2 Decimation-In-Frequency FFT Algorithm (DIF-FFT)!

In the previous note, we mastered the Decimation-In-Time (DIT) algorithm, which recursively divided our input sequence $x[n]$ in the time domain into even and odd samples {even indices first, odd indices second} [11.03, 174]. Now, we are going to look at its mathematical dual: Decimation-In-Frequency (DIF) [11.04, 176]. Instead of slicing the time-domain input, the DIF algorithm recursively splits the output frequency spectrum $X[k]$ into even-numbered bins and odd-numbered bins [11.04, 176].

Let’s derive the algebraic equations, analyze the butterfly flow paths, and solve the major 15-mark past year exam classics step-by-step!

---

1. Mathematical Derivation of Radix-2 DIF

We begin with the standard $N$-point Discrete Fourier Transform (DFT) equation [11.01]: $X[k]={\sum }_{n=0}^{N-1}x[n]W_N^{nk}extfork=0,1,\dots ,N-1$

Under the Radix-2 assumption, $N$ is a power of 2 ($N=2^L$). Instead of splitting the indices of the sequence into even and odd, let’s split the summation range itself into the first half ($n\in [0,N/2-1]$) and the second half ($n\in [N/2,N-1]$):

$X[k]={\sum }_{n=0}^{N/2-1}x[n]W_N^{nk}+{\sum }_{n=N/2}^{N-1}x[n]W_N^{nk}$

Now, let’s apply an index shift to the second summation by letting $m=n-N/2$ {which shifts the boundaries to match the first half exactly}:

ight] W_N^{\left(n + rac{N}{2} ight)k}$$ Since $W_N^{\left(n + N/2 ight)k} = W_N^{nk} \cdot W_N^{rac{N}{2}k}$, we can factor out $W_N^{nk}$: $$X[k] = \sum_{n=0}^{N/2-1} \left( x[n] + x\left[n + rac{N}{2} ight] W_N^{rac{N}{2}k} ight) W_N^{nk}$$ Let's simplify the complex term $W_N^{rac{N}{2}k}$: $$W_N^{rac{N}{2}k} = \left( e^{-jrac{2\pi}{N}} ight)^{rac{N}{2}k} = e^{-j\pi k} = (-1)^k$$ Substituting this back yields the core partition equation: $$X[k] = \sum_{n=0}^{N/2-1} \left( x[n] + (-1)^k x\left[n + rac{N}{2} ight] ight) W_N^{nk}$$ --- ### 1.1 Decimating the Output Frequency Bins To eliminate the $(-1)^k$ dependency, we split the output bins $X[k]$ into even frequency channels ($k = 2r$) and odd frequency channels ($k = 2r+1$) for $r = 0, 1, \dots, N/2-1$ [11.04]: #### Case 1: Even Frequency Bins ($k = 2r$) Substitute $k = 2r$ into our partition equation {note that $(-1)^{2r} = +1$}: $$X[2r] = \sum_{n=0}^{N/2-1} \left( x[n] + x\left[n + rac{N}{2} ight] ight) W_N^{n(2r)}$$ Since $W_N^{2nr} = \left(e^{-jrac{2\pi}{N}} ight)^{2nr} = e^{-jrac{2\pi}{N/2}nr} = W_{N/2}^{nr}$, we obtain: $$X[2r] = \sum_{n=0}^{N/2-1} \left( x[n] + x\left[n + rac{N}{2} ight] ight) W_{N/2}^{nr}$$ If we define a new auxiliary sequence $g[n] = x[n] + x[n+N/2]$, this is simply an $N/2$-point DFT: $$X[2r] = \sum_{n=0}^{N/2-1} g[n] W_{N/2}^{nr} = ext{DFT}_{N/2}\{g[n]\}$$ #### Case 2: Odd Frequency Bins ($k = 2r+1$) Substitute $k = 2r+1$ into the partition equation {note that $(-1)^{2r+1} = -1$}: $$X[2r+1] = \sum_{n=0}^{N/2-1} \left( x[n] - x\left[n + rac{N}{2} ight] ight) W_N^{n(2r+1)}$$ Distribute the twiddle factor $W_N^{n(2r+1)} = W_N^{2nr} \cdot W_N^n = W_{N/2}^{nr} \cdot W_N^n$: $$X[2r+1] = \sum_{n=0}^{N/2-1} \left[ \left( x[n] - x\left[n + rac{N}{2} ight] ight) W_N^n ight] W_{N/2}^{nr}$$ If we define another auxiliary sequence $h[n] = \left( x[n] - x[n+N/2] ight) W_N^n$, this becomes: $$X[2r+1] = \sum_{n=0}^{N/2-1} h[n] W_{N/2}^{nr} = ext{DFT}_{N/2}\{h[n]\}$$ > [!TIP] > > **The Algebraic Symmetry of DIF Decomposition:** > * The first half of our auxiliary array represents a simple pairwise addition: $g[n] = x[n] + x[n + N/2]$ [11.04]. > * The second half represents a pairwise subtraction weighted by a twiddle multiplier: $h[n] = \left(x[n] - x[n + N/2] ight) W_N^n$ [11.04]. --- ## 2. DIF Butterfly Flow Paths vs. DIT Let's look at the basic Radix-2 DIF butterfly module: ``` a (Top Input) ───────o───────────────> A = a + b \ / \ / \ / X / / / b (Bottom Input) ────o───────[ -1 ]───( x W_N^r )───> B = (a - b) * W_N^r ``` ### 2.1 The Critical Structural Differences You must be able to contrast the DIT and DIF butterfly structures in your exam: | Feature | Decimation-In-Time (DIT-FFT) [11.03] | Decimation-In-Frequency (DIF-FFT) [11.04] | | :--- | :--- | :--- | | **Input Ordering** | **Bit-Reversed order** required {requires initial shuffle} | **Natural order** ($x[0], x[1], \dots, x[7]$) | | **Output Ordering** | **Natural order** ($X[0], X[1], \dots, X[7]$) | **Bit-Reversed order** {requires final unscramble} | | **Twiddle Placement** | Multiplied **before** the butterfly addition/subtraction block | Multiplied **after** the butterfly subtraction path | | **Complex Multipliers**| $A = a + W_N^r b$ and $B = a - W_N^r b$ | $A = a + b$ and $B = (a - b)W_N^r$ | --- ## 3. The 8-Point Radix-2 DIF Signal-Flow Graph For $N = 8$, the DIF-FFT algorithm consists of $L = \log_2(8) = 3$ stages. Because the inputs are in natural order, the signals flow through three descending widths of division: * **Stage 1:** One 8-point butterfly division {span = 4 samples, twiddles $W_8^0, W_8^1, W_8^2, W_8^3$}. * **Stage 2:** Two 4-point butterfly divisions {span = 2 samples, twiddles $W_4^0, W_4^1$ (which map to $W_8^0, W_8^2$)}. * **Stage 3:** Four 2-point butterfly divisions {span = 1 sample, twiddle $W_2^0 = 1$ (which maps to $W_8^0$)}. ``` [DIAGRAM: Complete 8-point Radix-2 DIF-FFT butterfly signal-flow graph showing normally ordered inputs, subtraction stages, twiddle multipliers, and bit-reversed outputs] x[0] ────o──────────────o─── Stage 1 ───o──────────────o─── Stage 2 ───o─── Stage 3 ───o───> X[0] (s3[0]) x[1] ────│────o─────────│────o──────────│────o─────────│────o──────────│────o──────────│───> X[4] (s3[1]) x[2] ────│────│────o────│────│────o─────│────│────o────│────│────o─────│────│────o─────│───> X[2] (s3[2]) x[3] ────│────│────│────o────│────│─────o────│────│────o────│────│─────o────│────│─────o───> X[6] (s3[3]) x[4] ────o────│────│────│────o*W_8^0 ────────o────│────│────o*W_8^0 ────────o────│────│───> X[1] (s3[4]) x[5] ─────────o────│────│────o*W_8^1 ─────────────o────│────o*W_8^2 ─────────────o────│───> X[5] (s3[5]) x[6] ──────────────o────│────o*W_8^2 ──────────────────o────o*W_8^0 ──────────────────o───> X[3] (s3[6]) x[7] ───────────────────o────o*W_8^3 ───────────────────────o*W_8^2 ──────────────────────> X[7] (s3[7]) ``` --- ## 4. High-Yield Solved "Exam Killers" Let's solve the two most highly-weighted past year questions in complete, marks-saving numerical detail! ### 4.1 The 15-Mark 2025 Exam Classic: $x[n] = n^2$ > [!question] **2025 Exam Section B Q. 8c** > > Given $x[n] = n^2$ and $N = 8$. Find $X[k]$ using the Radix-2 DIF-FFT algorithm. (15 Marks) #### Step 1: Write down the Input Vector For $n = 0, 1, \dots, 7$, evaluate $x[n] = n^2$: $$x[n] = \{0, 1, 4, 9, 16, 25, 36, 49\}$$ --- #### Step 2: Stage 1 Calculations (8-Point Butterfly) The first stage splits the array into a top half and bottom half with a span of $N/2 = 4$: * **Addition Path (Top Half):** $s_1[n] = x[n] + x[n+4]$ * **Subtraction Path (Bottom Half):** $s_1[n+4] = (x[n] - x[n+4]) \cdot W_8^n$ Using the twiddle factor values: $$W_8^0 = 1, \quad W_8^1 = rac{1}{\sqrt{2}} - jrac{1}{\sqrt{2}} = 0.7071 - j0.7071$$ $$W_8^2 = -j, \quad W_8^3 = -rac{1}{\sqrt{2}} - jrac{1}{\sqrt{2}} = -0.7071 - j0.7071$$ $$egin{aligned} s_1[0] &= x[0] + x[4] = 0 + 16 = \mathbf{16} \ s_1[1] &= x[1] + x[5] = 1 + 25 = \mathbf{26} \ s_1[2] &= x[2] + x[6] = 4 + 36 = \mathbf{40} \ s_1[3] &= x[3] + x[7] = 9 + 49 = \mathbf{58} \ s_1[4] &= (x[0] - x[4]) \cdot W_8^0 = (0 - 16) \cdot 1 = \mathbf{-16} \ s_1[5] &= (x[1] - x[5]) \cdot W_8^1 = (1 - 25) \cdot (0.7071 - j0.7071) = -24 \cdot (0.7071 - j0.7071) = \mathbf{-16.9706 + j16.9706} \ s_1[6] &= (x[2] - x[6]) \cdot W_8^2 = (4 - 36) \cdot (-j) = -32 \cdot (-j) = \mathbf{j32} \ s_1[7] &= (x[3] - x[7]) \cdot W_8^3 = (9 - 49) \cdot (-0.7071 - j0.7071) = -40 \cdot (-0.7071 - j0.7071) = \mathbf{28.2843 + j28.2843} \end{aligned}$$ --- #### Step 3: Stage 2 Calculations (Two 4-Point Butterflies) Stage 2 operates on two independent 4-point groups: $\{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]\}$ with a span of $N/4 = 2$. The twiddle factors are $W_4^0 = W_8^0 = 1$ and $W_4^1 = W_8^2 = -j$. ##### Group 1 (Top Half): $$egin{aligned} s_2[0] &= s_1[0] + s_1[2] = 16 + 40 = \mathbf{56} \ s_2[1] &= s_1[1] + s_1[3] = 26 + 58 = \mathbf{84} \ s_2[2] &= (s_1[0] - s_1[2]) \cdot W_8^0 = (16 - 40) \cdot 1 = \mathbf{-24} \ s_2[3] &= (s_1[1] - s_1[3]) \cdot W_8^2 = (26 - 58) \cdot (-j) = -32 \cdot (-j) = \mathbf{j32} \end{aligned}$$ ##### Group 2 (Bottom Half): $$egin{aligned} s_2[4] &= s_1[4] + s_1[6] = -16 + j32 = \mathbf{-16 + j32} \ s_2[5] &= s_1[5] + s_1[7] = (-16.9706 + j16.9706) + (28.2843 + j28.2843) = \mathbf{11.3137 + j45.2548} \ s_2[6] &= (s_1[4] - s_1[6]) \cdot W_8^0 = (-16 - j32) \cdot 1 = \mathbf{-16 - j32} \ s_2[7] &= (s_1[5] - s_1[7]) \cdot W_8^2 = \left[ (-16.9706 + j16.9706) - (28.2843 + j28.2843) ight] \cdot (-j) \ &= (-45.2548 - j11.3137) \cdot (-j) = j45.2548 - 11.3137 = \mathbf{-11.3137 + j45.2548} \end{aligned}$$ --- #### Step 4: Stage 3 Calculations (Four 2-Point Butterflies) Stage 3 uses a span of 1. Twiddles are all $W_2^0 = W_8^0 = 1$. ##### Pair 1: $$s_3[0] = s_2[0] + s_2[1] = 56 + 84 = \mathbf{140}$$ $$s_3[1] = s_2[0] - s_2[1] = 56 - 84 = \mathbf{-28}$$ ##### Pair 2: $$s_3[2] = s_2[2] + s_2[3] = \mathbf{-24 + j32}$$ $$s_3[3] = s_2[2] - s_2[3] = \mathbf{-24 - j32}$$ ##### Pair 3: $$s_3[4] = s_2[4] + s_2[5] = (-16 + j32) + (11.3137 + j45.2548) = \mathbf{-4.6863 + j77.2548}$$ $$s_3[5] = s_2[4] - s_2[5] = (-16 + j32) - (11.3137 + j45.2548) = \mathbf{-27.3137 - j13.2548}$$ ##### Pair 4: $$s_3[6] = s_2[6] + s_2[7] = (-16 - j32) + (-11.3137 + j45.2548) = \mathbf{-27.3137 + j13.2548}$$ $$s_3[7] = s_2[6] - s_2[7] = (-16 - j32) - (-11.3137 + j45.2548) = \mathbf{-4.6863 - j77.2548}$$ --- #### Step 5: Unscramble the Bit-Reversed Output In the DIF algorithm, the final stage outputs ($s_3[i]$) correspond to the frequency bins ($X[k]$) in **bit-reversed order**: $$egin{aligned} X[0] &= s_3[0] = \mathbf{140} \ X[4] &= s_3[1] = \mathbf{-28} \ X[2] &= s_3[2] = \mathbf{-24 + j32} \ X[6] &= s_3[3] = \mathbf{-24 - j32} \ X[1] &= s_3[4] = \mathbf{-4.6863 + j77.2548} \ X[5] &= s_3[5] = \mathbf{-27.3137 - j13.2548} \ X[3] &= s_3[6] = \mathbf{-27.3137 + j13.2548} \ X[7] &= s_3[7] = \mathbf{-4.6863 - j77.2548} \end{aligned}$$ #### Step 6: Final Sorted Array & Verification Let's assemble our final sorted DFT output vector: $$\mathbf{X[k] = \left\{ 140, \; -4.6863 + j77.2548, \; -24 + j32, \; -27.3137 + j13.2548, \; -28, \; -27.3137 - j13.2548, \; -24 - j32, \; -4.6863 - j77.2548 ight\}}$$ > [!SUCCESS] > > **Conjugate Symmetry Verification Check:** > Let's check if the real sequence satisfies $X[k] = X^*[N-k]$: > * $X[1] = -4.6863 + j77.2548$ and $X[7] = -4.6863 - j77.2548$ [Verified!] > * $X[2] = -24 + j32$ and $X[6] = -24 - j32$ [Verified!] > * $X[3] = -27.3137 + j13.2548$ and $X[5] = -27.3137 - j13.2548$ [Verified!] > > The calculations are 100% accurate! --- ### 4.2 The 15-Mark 2023 Exam Classic: $x[n] = n + 1$ > [!question] **2023 Exam Section B Q. 8c** > > Given $x[n] = n + 1$ and $N = 8$. Find $X[k]$ using the Radix-2 DIF-FFT algorithm. (15 Marks) #### Step 1: Write down the Input Vector $$x[n] = \{1, 2, 3, 4, 5, 6, 7, 8\}$$ #### Step 2: Stage 1 Calculations (8-Point Butterfly) $$egin{aligned} s_1[0] &= 1 + 5 = \mathbf{6} \ s_1[1] &= 2 + 6 = \mathbf{8} \ s_1[2] &= 3 + 7 = \mathbf{10} \ s_1[3] &= 4 + 8 = \mathbf{12} \ s_1[4] &= (1 - 5) \cdot 1 = \mathbf{-4} \ s_1[5] &= (2 - 6) \cdot (0.7071 - j0.7071) = -4 \cdot (0.7071 - j0.7071) = \mathbf{-2.8284 + j2.8284} \ s_1[6] &= (3 - 7) \cdot (-j) = -4 \cdot (-j) = \mathbf{j4} \ s_1[7] &= (4 - 8) \cdot (-0.7071 - j0.7071) = -4 \cdot (-0.7071 - j0.7071) = \mathbf{2.8284 + j2.8284} \end{aligned}$$ #### Step 3: Stage 2 Calculations (Two 4-Point Butterflies) ##### Group 1 (Top Half): $$egin{aligned} s_2[0] &= s_1[0] + s_1[2] = 6 + 10 = \mathbf{16} \ s_2[1] &= s_1[1] + s_1[3] = 8 + 12 = \mathbf{20} \ s_2[2] &= (s_1[0] - s_1[2]) \cdot 1 = (6 - 10) \cdot 1 = \mathbf{-4} \ s_2[3] &= (s_1[1] - s_1[3]) \cdot (-j) = (8 - 12) \cdot (-j) = \mathbf{j4} \end{aligned}$$ ##### Group 2 (Bottom Half): $$egin{aligned} s_2[4] &= s_1[4] + s_1[6] = \mathbf{-4 + j4} \ s_2[5] &= s_1[5] + s_1[7] = (-2.8284 + j2.8284) + (2.8284 + j2.8284) = \mathbf{j5.6569} \ s_2[6] &= (s_1[4] - s_1[6]) \cdot 1 = \mathbf{-4 - j4} \ s_2[7] &= (s_1[5] - s_1[7]) \cdot (-j) = \left[ (-2.8284 + j2.8284) - (2.8284 + j2.8284) ight] \cdot (-j) \ &= -5.6569 \cdot (-j) = \mathbf{j5.6569} \end{aligned}$$ #### Step 4: Stage 3 Calculations (Four 2-Point Butterflies) ##### Pair 1: $$s_3[0] = s_2[0] + s_2[1] = 16 + 20 = \mathbf{36}$$ $$s_3[1] = s_2[0] - s_2[1] = 16 - 20 = \mathbf{-4}$$ ##### Pair 2: $$s_3[2] = s_2[2] + s_2[3] = \mathbf{-4 + j4}$$ $$s_3[3] = s_2[2] - s_2[3] = \mathbf{-4 - j4}$$ ##### Pair 3: $$s_3[4] = s_2[4] + s_2[5] = (-4 + j4) + j5.6569 = \mathbf{-4 + j9.6569} \quad \{j(4 + 4\sqrt{2})\}$$ $$s_3[5] = s_2[4] - s_2[5] = (-4 + j4) - j5.6569 = \mathbf{-4 - j1.6569} \quad \{j(4 - 4\sqrt{2})\}$$ ##### Pair 4: $$s_3[6] = s_2[6] + s_2[7] = (-4 - j4) + j5.6569 = \mathbf{-4 + j1.6569}$$ $$s_3[7] = s_2[6] - s_2[7] = (-4 - j4) - j5.6569 = \mathbf{-4 - j9.6569}$$ #### Step 5: Unscramble the Bit-Reversed Output Mapping $s_3[i]$ directly to $X[k]$: $$egin{aligned} X[0] &= s_3[0] = \mathbf{36} \ X[4] &= s_3[1] = \mathbf{-4} \ X[2] &= s_3[2] = \mathbf{-4 + j4} \ X[6] &= s_3[3] = \mathbf{-4 - j4} \ X[1] &= s_3[4] = \mathbf{-4 + j9.6569} \ X[5] &= s_3[5] = \mathbf{-4 - j1.6569} \ X[3] &= s_3[6] = \mathbf{-4 + j1.6569} \ X[7] &= s_3[7] = \mathbf{-4 - j9.6569} \end{aligned}$$ #### Step 6: Assemble the Final DFT Array $$\mathbf{X[k] = \left\{ 36, \; -4 + j9.6569, \; -4 + j4, \; -4 + j1.6569, \; -4, \; -4 - j1.6569, \; -4 - j4, \; -4 - j9.6569 ight\}}$$ --- ## 5. Common Mistakes That Cost Marks > [!WARNING] **Key Exam Checkpoints** > > 1. **Bit-Reversal Sorting Stage Mismatch:** Shuffling the input sequence instead of the output bins in the DIF algorithm. Remember: DIT has bit-reversed inputs and natural outputs, whereas DIF has natural inputs and bit-reversed outputs. > 2. **Twiddle Exponent Arithmetic Slip:** Using the wrong twiddle factor values at intermediate stages. In Stage 2 of an 8-point DIF, the bottom branches of each 4-point group are scaled by $W_8^0 = 1$ and $W_8^2 = -j$. > 3. **The Conjugate Symmetry Self-Test:** Forgetting to run $X[k] = X^*[N-k]$ at the end of the calculation. This 10-second check will immediately catch any basic sign mistakes in your stage-by-stage arithmetic before handing in your paper! --- ## 6. PYQ Bank — Verbatim Questions & Answer Plans ### Q1: The Decimation-in-Frequency Framework * **Question:** What is the DIF-FFT algorithm? Discuss its butterfly features. (05 Marks) * **Answer Plan:** 1. Define DIF as the recursive frequency bin decimation process [11.04, 325]. 2. Draw the single Radix-2 DIF butterfly, showing that the subtraction and multiplication blocks occur at the tail-end. 3. Draw the structural comparison table (contrast DIT vs. DIF input/output and twiddle placement). ### Q2: 8-Point $n^2$ Sequence Evaluation * **Question:** Given $x[n] = n^2$ and $N = 8$. Find $X(k)$ using the DIF-FFT algorithm. (15 Marks) * **Answer Plan:** Use the complete derivation from **Section 4.1**. Detail each stage's variables ($s_1, s_2, s_3$) explicitly, write out the bit-reversal mapping steps, and finish with the conjugate symmetry verification. ### Q3: 8-Point Linear Sequence Evaluation * **Question:** Given $x[n] = n+1$ and $N = 8$. Find $X(k)$ using the DIF-FFT algorithm. (15 Marks) * **Answer Plan:** Follow the steps in **Section 4.2**. Show the stage-by-stage math clearly, plot the final $X[k]$ values, and highlight the conjugate symmetry results to secure full marks. --- ## 7. Self-Check Before Moving On - [ ] Can you derive the Radix-2 DIF-FFT algebraic equations for even ($k=2r$) and odd ($k=2r+1$) output bins from the baseline DFT summation [11.04]? - [ ] Can you sketch a complete, labeled 8-point DIF-FFT signal-flow graph, showing natural-order inputs and bit-reversed outputs? - [ ] Do you know how to perform Stage 1, 2, and 3 complex computations for $N=8$ without mixing up twiddle factor indices? --- *Source: Shah Muhammad Azmat Ullah lecture notes (05 DFT FFT.pdf), K. Deergha Rao signals and systems (8.10.2 Bilinear Transformation).*