Chapter 11 - DFT, FFT, and Frequency-Domain Discrete Analysis

11 Chapter Map - DFT, FFT, and Frequency-Domain Discrete Analysis

Chapter 11 Overview & Map of Content (MOC)

Direct DFT matrix mathematics, complex twiddle phase periodicities, and Radix-2 DIT/DIF butterfly signal-flow graphs.

---

📚 Study Notes Index

Read in order — each note assumes the previous one.

#	Note	What it covers
11.00	11.00 Discrete Fourier Transforms Compact Review	DFT Compact Review, FFT Compact Review, Fourier Transform Discrete Compact
11.01	11.01 The Discrete Fourier Transform DFT	Discrete Fourier Transform, DFT Definition, DFT Complexity, DFT Matrix
11.02	11.02 Properties of the DFT and Twiddle Factors	DFT Properties, Twiddle Factor Symmetries, Circular Convolution, Circular Shifting
11.03	11.03 Radix-2 Decimation-In-Time FFT Algorithm DIT-FFT	DIT-FFT Algorithm, Decimation-In-Time FFT, Radix-2 DIT Butterfly
11.04	11.04 Radix-2 Decimation-In-Frequency FFT Algorithm DIF-FFT	DIF-FFT, Decimation-in-Frequency, DIF Butterfly Diagram, Radix-2 DIF

---

🎯 Exam Weight

ECE 2107 Exam Relevance

Master the core derivations, mathematical definitions, and problem-solving techniques. Refer to ECE 2107 - Signals and Systems for syllabus boundaries and past year questions.

---

🔗 Related Resources

• Course Teaching Plan: ECE 2107 - Signals and Systems
• Previous chapter: 10 Chapter Map - Z-Transform & Discrete-Time Analysis
• Next chapter: None

---

10.00 Z-Transform & Discrete-Time Analysis - Compact Review | 11.01 The Discrete Fourier Transform (DFT)

---

Chapter 11: DFT & Fast Fourier Transforms (FFT) - Compact Review

11.01 The Discrete Fourier Transform (DFT) Pair

*(Target: Theory Descriptive / Numerical Solving)* [11.01, 138]

• Concept: Converts a finite, discrete time-domain sequence $x[n]$ of length $N$ into its discrete frequency spectrum $X[k]$ containing $N$ discrete frequency bins around the unit circle in the $z$-plane [11.01].
• Forward DFT Equation: X[k] = \sum_{n=0}^{N-1} x[n] e^{-j rac{2\pi}{N} n k} = \sum_{n=0}^{N-1} x[n] W_N^{n k} \quad ext{for } 0 \le k \le N-1 [11.01, 138, 212]
• Inverse DFT (IDFT) Equation: x[n] = rac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j rac{2\pi}{N} n k} = rac{1}{N} \sum_{k=0}^{N-1} X[k] W_N^{-n k} \quad ext{for } 0 \le n \le N-1 [11.01, 138, 212]
• The Twiddle Factor ($W_N$): Defined as the complex exponential root of unity representing a phase phasor [11.02, 138, 213]: W_N = e^{-jrac{2\pi}{N}} [11.02, 138, 213]

---

11.02 Twiddle Factor ($W_N$) Algebraic Properties

*(Target: Mathematical Proof)* [11.02, 139]

• Periodicity Property: Twiddle factors are periodic over period $N$ [11.02]: $W_N^{k+N}=W_N^{k}ext(derivation)$ [11.02]
• Symmetry (Anti-Symmetry) Property: A half-period shift negates the twiddle factor phasor [11.02, 139]: $W_N^{k+N/2}=-W_N^{k}ext(derivation)$ [11.02, 139]
• Index Multi-Rate Scaling (Reduction Property): Scaling both the basis and exponent by the same factor yields an identical phasor: $W_{mN}^{mk}=W_N^{k}ext(derivation)$

---

11.03 DFT Computational Complexity & FFT Speed-Up

*(Target: Mathematical Proof / 5-Mark Theory Descriptive)* [11.01]

• Direct DFT Complexity: Computing an $N$-point DFT directly requires $N^2$ complex multiplications and $N(N-1)$ complex additions [11.01].
• Radix-2 FFT Complexity: By recursively decomposing the sequence, the Radix-2 FFT algorithm reduces the complexity to rac{N}{2} \log_2 N complex multiplications and $N{\log }_{2}N$ complex additions [11.01, 139].
• Mathematical Complexity Comparison Equations: ext{Multiplications Ratio} = rac{ ext{Direct DFT Multiplications}}{ ext{FFT Multiplications}} = rac{N^2}{rac{N}{2} \log_2 N} = rac{2N}{\log_2 N} \quad ext{(derivation)} [11.01] ext{Additions Ratio} = rac{ ext{Direct DFT Additions}}{ ext{FFT Additions}} = rac{N(N-1)}{N \log_2 N} pprox rac{N}{\log_2 N} \quad ext{(derivation)}

Complexity Scale Lookup Matrix

The dramatic computational savings of FFT over direct DFT as sequence length $N$ scales [11.01, 139]:

Sequence Length ($N$)	Direct DFT Multiplications ($N^2$)	Radix-2 FFT Multiplications (rac{N}{2}\log_2 N)	Speed-up Ratio (Multiplications)
$N=4$	16	4	4.00 $imes$
$N=8$	64	12	5.33 $imes$
$N=16$	256	32	8.00 $imes$
$N=64$	4,096	192	21.33 $imes$
$N=256$	65,536	1,024	64.00 $imes$
$N=1024$	1,048,576	5,120	204.80 $imes$ (99.51% savings)

---

11.04 Circular Shifting & Convolution Dynamics

*(Target: Theory Descriptive / Numerical Solving)* [11.02]

• Circular Time-Shift Property: Shifting a sequence modulo-$N$ introduces a twiddle phase scaling in the frequency domain [11.02]:

angle_N ight) ight} = W_N^{k m} X[k] \quad ext{(derivation)}$$ [11.02]

• Circular Convolution Theorem: Multiplying two $N$-point DFT spectra corresponds exactly to the circular convolution of the sequences in the time domain [11.02]: $x_1[n]⊛x_2[n]\leftrightarrow X_1[k]\cdot X_2[k]ext(derivation)$ [11.02]
• The Circular Convolution Integral (Modulo Sum):

angle_N ight)$$ [11.02]

• Circular-to-Linear Convolution Mapping: Linear convolution (duration $N_1+N_2-1$) can be obtained using circular convolution by padding both input sequences with zeros to length $L$ satisfying [11.02]: $L\ge N_1+N_2-1ext(derivation)$ [11.02]

---

11.05 Radix-2 Decimation-In-Time (DIT-FFT)

*(Target: Signal-Flow Diagram Sketching / Numerical Solving)* [11.03]

• Concept: Recursively decimates (splits) the time-domain input sequence $x[n]$ into its even-indexed elements $g[n]=x[2n]$ and odd-indexed elements $h[n]=x[2n+1]$ to calculate the $N$-point DFT bins [11.03, 140, 214].
• DIT Butterfly Decomposition Equations: X[k] = G[k] + W_N^k H[k] \quad ext{for } 0 \le k \le rac{N}{2}-1 \quad ext{(derivation)} [11.03, 214]

ight] = G[k] - W_N^k H[k] \quad ext{for } 0 \le k \le rac{N}{2}-1 \quad ext{(derivation)}$$ [11.03, 214]

• DIT Structural Traits:
  • Input Ordering: Must be shuffled into Bit-Reversed Order [11.03, 142, 214].
  • Output Ordering: Appears in Natural (Normal) Order ($X[0],X[1],\dots ,X[N-1]$) [11.03, 142].
  • Butterfly Multipliers: Twiddle factor $W_N^r$ scaling is applied to the odd-indexed branch before the summation/subtraction nodes [11.03].

Bit-Reversal Shuffling Protocol ($N=8$)

Input indexes are mapped using binary reversal [11.03, 143]:

ext{Bit-Reversed Shuffled Input Vector: } \mathbf{x}_{ ext{shuffled}} = egin{bmatrix} x[0] & x[4] & x[2] & x[6] & x[1] & x[5] & x[3] & x[7] \end{bmatrix}^T [11.03, 143]

Normal Index ($n$)	Binary representation	Bit-Reversed Binary	Bit-Reversed Index ($n_r$)
0	000	000	0
1	001	100	4
2	010	010	2
3	011	110	6
4	100	001	1
5	101	101	5
6	110	011	3
7	111	111	7

---

11.06 Radix-2 Decimation-In-Frequency (DIF-FFT)

*(Target: Signal-Flow Diagram Sketching / Numerical Solving)* [11.04]

• Concept: Divides the output frequency spectrum bins $X[k]$ into even-numbered bins $X[2r]$ and odd-numbered bins $X[2r+1]$ by breaking the time-domain inputs into the first half $x[n]$ and the second half $x[n+N/2]$ [11.04, 143, 215].
• DIF Butterfly Decomposition Equations:

ight] ight) W_{N/2}^{nr} \quad ext{for } 0 \le r \le rac{N}{2}-1 \quad ext{(derivation)}$[11.04,215]$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} \quad ext{for } 0 \le r \le rac{N}{2}-1 \quad ext{(derivation)}$$ [11.04, 215]

• DIF Structural Traits:
  • Input Ordering: Appears in Natural (Normal) Order ($x[0],x[1],\dots ,x[N-1]$) [11.04, 144].
  • Output Ordering: Appears in Bit-Reversed Order [11.04, 144].
  • Butterfly Multipliers: Twiddle factor scaling is applied to the odd subtraction branch after the subtraction nodes [11.04].

---

11.07 IDFT Computation using Forward FFT (FFT/IFFT Unification)

*(Target: Hardware Block Diagram Design / 5-Mark Proof)* [11.01]

• Philosophy: Rather than designing separate hardware processors for DFT and IDFT, the inverse transform can be computed directly using a standard forward DFT/FFT block by applying complex conjugation [11.01, 145].
• Unifying Mathematical Proof Identity:

ight} ight]^* \quad ext{(derivation)}$$ [11.01, 145]

• Hardware Flow Blueprint: \mathbf{X}[k] o oxed{ ext{Complex Conjugation } X^*[k]} o oxed{N ext{-point Forward FFT Block}} o oxed{ ext{Complex Conjugation } [\cdot]^*} o oxed{ ext{Divide by } N} o \mathbf{x}[n] [11.01, 145, 146]

---

11.08 Comparison Matrix: DFT vs. DIT-FFT vs. DIF-FFT

*(Target: Theory Descriptive / 5-Mark Difference Table)* [11.01, 11.03, 11.04]

Parameter	Direct DFT	Radix-2 DIT-FFT	Radix-2 DIF-FFT
Computational Complexity	$O(N^2)$ complex calculations [11.01]	$O(N{\log }_{2}N)$ complex calculations [11.01]	$O(N{\log }_{2}N)$ complex calculations [11.01]
Complex Multiplications	$N^2$ [11.01]	rac{N}{2}\log_2 N [11.01, 139]	rac{N}{2}\log_2 N [11.01, 139]
Complex Additions	$N(N-1)$ [11.01]	$N{\log }_{2}N$ [11.01]	$N{\log }_{2}N$ [11.01]
Input Data Ordering	Natural Order [11.01]	Bit-Reversed Order [11.03, 142]	Natural Order [11.04, 144]
Output Data Ordering	Natural Order [11.01]	Natural Order [11.03, 142]	Bit-Reversed Order [11.04, 144]
Butterfly Phase Scaling	N/A	Applied to odd branch before additions [11.03]	Applied to subtraction branch after additions [11.04]

---

11.09 Marks-Saving “Common Mistakes” Checklist

*(Target: Exam Quality Control)* [11.01, 11.02]

• The IDFT Normalization Trap: Forgetting to divide the final sum by $N$ when evaluating the IDFT manually or programmatically [11.01].
• The DIT Input Bit-Reversal Slip-up: Accidentally inputting natural-order samples into a DIT butterfly flow graph. Remember: DIT requires bit-reversed inputs [11.03, 142].
• The DIF Output Bit-Reversal Slip-up: Forgetting that a DIF butterfly flow graph produces outputs in bit-reversed order. You must sort $X[k]$ back into natural order to get your marks [11.04, 144].
• The Linear-vs-Circular Length Boundary Error: Convolving two sequences of length $N_1$ and $N_2$ circularly without padding. The padded circular sequence length must be at least $N_1+N_2-1$ to avoid destructive wrap-around aliasing [11.02].
• Twiddle Phase Exponent Signs: In forward DFT, the twiddle exponents are negative ($W_N^{nk}$). In IDFT, they are positive ($W_N^{-nk}$) [11.01, 138, 212].

---

11.10 Verbatim Past Year Questions (PYQs)

*(Target: Active Recall)* [11.01, 11.02, 11.03, 11.04]

KUET 2025 Section B

• Q5a: What is DIT-FFT algorithm? Give the computation efficiency of FFT over DFT. [5 Marks]
• Q5c: Given $x[n]=n^2$ and $N=8$. Find $X[k]$ using DIF-FFT algorithm. [15 Marks]

KUET 2024 Section B

• Q8b: Given $x[n]=\{0,1,2,3\}$. Find $X[k]$ using DIT-FFT algorithm. [12 Marks]
• Q8c: Why is FFT called so? How can you compute IDFT using FFT algorithm? [10 Marks]

KUET 2023 Section B

• Q5a: What is FFT algorithm? Give the computation efficiency of FFT over DFT. [5 Marks]
• Q5c: Given $x[n]=n+1$ and $N=8$. Find $X[k]$ using DIF-FFT algorithm. [15 Marks]

KUET 2018 Section B

• Q4c: Given two sequences of length $N=4$ defined by $x_1[n]=\{0,1,2,3\}$ and $x_2[n]=\{1,1,2,2\}$. Determine their linear and periodic (circular) convolution. [5 Marks]

KUET 2017 Section B

• Q4b: Given two sequences of length $N=4$ defined by $x_1[n]=\{1,2,2,1\}$ and $x_2[n]=\{2,1,1,2\}$. Determine their linear and periodic convolution. [3 Marks]

---

11.11 Interactive Self-Check Revision List

• Can I write the $N$-point DFT and IDFT equations with correct twiddle factor notation?
• Can I prove the periodicity and symmetry properties of twiddle factors from first principles?
• Do I know how to construct a bit-reversal mapping index table for $N=8$?
• Can I write down the mathematical proof showing how to compute IFFT using a forward FFT block?
• Do I know the exact multiplication and addition formula constraints for direct DFT versus Radix-2 FFT?
• Can I determine the minimum sequence padding length $L$ required to bypass wrap-around time aliasing?

---

Source: ECE 2107 Lecture Slides (Fast Fourier Transform by S. M. Azmat Ullah), Textbook (Digital Signal Processing by K. Deergha Rao)

---

← 10.05 Convolution, Correlation & Realization in Z-Domain | Chapter 11 Map | 11.02 Properties of the DFT & Twiddle Factors →

11.01 The Discrete Fourier Transform (DFT)

Welcome to Chapter 11: Discrete Fourier Transform (DFT) & Fast Fourier Transform (FFT)! This represents the final, major 25 to 30-mark point generator under Instructor 1.

Up to this point, you have explored continuous frequency representations of discrete-time sequences through the Discrete-Time Fourier Transform (DTFT) {a representation mapping $x[n]$ to a continuous, $2\pi$-periodic function of frequency $\omega$} [7.7]. However, because digital signal processors (DSPs), computers, and microcontrollers can only store and process finite, discrete data files, we cannot compute a continuous frequency function. To bridge this physical constraint, we employ the Discrete Fourier Transform (DFT) {the mathematical operation that samples the continuous DTFT spectrum at $N$ equally spaced points around the unit circle} [11.01].

Let’s break down the mathematical foundations of the DFT and IDFT pairs, conduct a rigorous computational complexity proof, learn how to solve DFTs as simple matrix operations, and lock down full marks in your Section B exam!

---

1. The Sampling Bridge: From DTFT to DFT

To understand why the DFT is structured the way it is, let’s look at the mathematical bridge between continuous-frequency DTFT and discrete-frequency DFT.

The continuous-frequency DTFT of a finite-duration discrete sequence $x[n]$ of length $N$ (defined over $0\le n\le N-1$) is given by [7.7]:

ight) = \sum_{n=0}^{N-1} x[n] e^{-j\omega n}$$ Because the frequency variable $\omega$ is continuous over the range $[0, 2\pi]$, we sample this continuous spectrum at $N$ equally spaced points around the unit circle in the $z$-plane: $$\omega_k = rac{2\pi}{N} k, \quad ext{for } k = 0, 1, \dots, N-1$$ Substituting $\omega_k$ back into the DTFT summation yields the **Discrete Fourier Transform (DFT)** [11.01]: $$X[k] = X\left(e^{j\omega_k} ight) = \sum_{n=0}^{N-1} x[n] e^{-jrac{2\pi}{N} nk}$$ This operation converts a discrete-time sequence of length $N$ into a discrete-frequency sequence of length $N$, mapping time samples directly to discrete frequency bins [11.01]. --- ## 2. The DFT & IDFT Mathematical Transform Pairs To simplify our equations, we define the **Twiddle Factor** {also called the phase factor, which is the complex exponential $N$-th root of unity representing a clockwise rotation of $2\pi/N$ radians} [11.02]: $$W_N = e^{-jrac{2\pi}{N}}$$ ### 2.1 The Forward DFT Equation Using our Twiddle Factor notation, the forward **Discrete Fourier Transform (DFT)** equation is defined as [11.01]: $$\mathbf{X[k] = \sum_{n=0}^{N-1} x[n] W_N^{nk}, \quad ext{for } k = 0, 1, \dots, N-1}$$ * **$x[n]$:** Time-domain discrete sequence sample at index $n$. * **$X[k]$:** Discrete frequency spectrum bin at index $k$. * **$N$:** The transform length {the total number of time samples and corresponding frequency bins}. * **$W_N^{nk}$:** Complex exponential phase term $e^{-jrac{2\pi}{N} nk}$ [11.01]. --- ### 2.2 The Inverse DFT (IDFT) Equation To reconstruct our original discrete-time sequence from its discrete-frequency spectrum bins, we employ the **Inverse Discrete Fourier Transform (IDFT)** equation [11.01]: $$\mathbf{x[n] = rac{1}{N} \sum_{k=0}^{N-1} X[k] W_N^{-nk}, \quad ext{for } n = 0, 1, \dots, N-1}$$ * **$W_N^{-nk}$:** Inverse Twiddle factor term $e^{jrac{2\pi}{N} nk}$ representing a counter-clockwise rotation [11.01]. * **$rac{1}{N}$:** The crucial amplitude normalization factor that scales the sum back to its physical time-domain values [11.01]. > [!WARNING] > > **The IDFT Normalization Trap:** > Forgetting to divide by $N$ when evaluating the IDFT is the single most common slip in exam papers! Omitting this factor scales your reconstructed time sequence by a factor of $N$, costing you 2–3 marks instantly. Always check that the $1/N$ scaling term is present in front of your IDFT sum [11.01]. --- ## 3. Computational Complexity Analysis: DFT vs. Radix-2 FFT > [!danger] **KUET Exam Classic [PYQ 2025, 2023, 2019 - 5 Marks]** > > *State the definition of the DFT. Prove the computational efficiency of the Fast Fourier Transform (FFT) algorithm over the direct computation of the DFT.* Let's conduct a rigorous mathematical proof to compare the computational loads of both approaches. ### 3.1 Computational Load of the Direct DFT To evaluate a single frequency bin $X[k]$ using the direct DFT summation: $$X[k] = x[0]W_N^0 + x[1]W_N^k + x[2]W_N^{2k} + \dots + x[N-1]W_N^{(N-1)k}$$ * Each term in the sum is a product of a complex sample $x[n]$ and a complex Twiddle factor $W_N^{nk}$. Thus, calculating a single $X[k]$ requires **$N$ complex multiplications**. * Summing these $N$ terms together requires **$N-1$ complex additions**. Since we must evaluate this summation for all $N$ distinct frequency bins ($k = 0, 1, \dots, N-1$), the total computational load for a direct $N$-point DFT is [11.01]: * **Total Complex Multiplications:** $$M_{ ext{direct}} = N \cdot N = \mathbf{N^2}$$ * **Total Complex Additions:** $$A_{ ext{direct}} = N \cdot (N-1) = \mathbf{N(N-1)}$$ For large values of $N$, the computational load scales quadratically with a complexity of **$O(N^2)$** [11.01]. --- ### 3.2 Computational Load of the Radix-2 FFT The Fast Fourier Transform (FFT) is not a different transform; it is simply a highly optimized family of algorithms that computes the exact same DFT while exploiting Twiddle factor symmetries (symmetry: $W_N^{k+N/2} = -W_N^k$, periodicity: $W_N^{k+N} = W_N^k$) [11.02] to eliminate redundant math. The Radix-2 algorithm recursively decomposes an $N$-point DFT (where $N = 2^L$) into $L = \log_2 N$ cascade stages. * Each of the $\log_2 N$ stages contains exactly **$N/2$ butterfly operations**. * Each basic butterfly operation requires exactly **1 complex multiplication** and **2 complex additions**. Therefore, the total computational load of a Radix-2 FFT is [11.01]: * **Total Complex Multiplications:** $$M_{ ext{FFT}} = rac{N}{2} \log_2 N$$ * **Total Complex Additions:** $$A_{ ext{FFT}} = N \log_2 N$$ This reduces the computational complexity to **$O(N \log_2 N)$** [11.01]. --- ### 3.3 Computational Efficiency Comparison Table Let's look at how this reduction scales as the data size $N$ increases. (Assuming a complex multiplication on a processor takes significantly longer than a complex addition, our speed-up factor focuses on multiplications): | Sequence Length ($N$) | Direct DFT Multiplications ($N^2$) | Radix-2 FFT Multiplications ($rac{N}{2} \log_2 N$) | Speed-up Efficiency Gain ($rac{2N}{\log_2 N}$) | Percentage Reduction in Computations | | :---: | :---: | :---: | :---: | :---: | | **$N = 4$** | $16$ | $4$ | $4.0 imes$ | $75.00\%$ | | **$N = 8$** | $64$ | $12$ | $5.3 imes$ | $81.25\%$ | | **$N = 16$** | $256$ | $32$ | $8.0 imes$ | $87.50\%$ | | **$N = 64$** | $4,096$ | $192$ | $21.3 imes$ | $95.31\%$ | | **$N = 256$** | $65,536$ | $1,024$ | $64.0 imes$ | $98.44\%$ | | **$N = 1024$** | $1,048,576$ | $5,120$ | **$204.8 imes$** | **$99.51\%$** | | **$N = 4096$** | $16,777,216$ | $24,576$ | **$682.7 imes$** | **$99.85\%$** | ### 3.4 Rigorous Speed-up Ratio Calculation (For $N = 1024$) $$ ext{Speed-up Ratio} = rac{ ext{Direct DFT Multiplications}}{ ext{FFT Multiplications}} = rac{N^2}{rac{N}{2}\log_2 N} = rac{2N}{\log_2 N}$$ Substituting $N = 1024 = 2^{10} \implies \log_2 N = 10$: $$ ext{Speed-up Ratio} = rac{2 \cdot 1024}{10} = rac{2048}{10} = \mathbf{204.8 imes ext{ faster!}}$$ This mathematically proves why real-time systems (such as medical imaging, radar systems, and digital communication devices) rely entirely on FFT algorithms—reducing a million operations to just five thousand [11.01]. --- ## 4. The DFT as a Matrix Operation {Linear Algebra Framework} For small finite sequences (typically $N \le 4$), we can express the forward DFT summation as a single matrix-vector multiplication [11.01]: $$\mathbf{X} = \mathbf{W}_N \mathbf{x}$$ Where: * $\mathbf{x}$ is the $N imes 1$ time-domain input column vector. * $\mathbf{X}$ is the $N imes 1$ frequency-domain output column vector. * $\mathbf{W}_N$ is the $N imes N$ **Twiddle Factor Matrix** [11.01]. ### 4.1 Constructing the $4 imes 4$ DFT Matrix For $N = 4$, our Twiddle Factor base value is: $$W_4 = e^{-jrac{2\pi}{4}} = e^{-jrac{\pi}{2}} = -j$$ The elements of our $4 imes 4$ matrix $\mathbf{W}_4$ are given by $W_4^{nk}$ for row index $k \in [0, 3]$ and column index $n \in [0, 3]$: $$\mathbf{W}_4 = egin{bmatrix} W_4^0 & W_4^0 & W_4^0 & W_4^0 \ W_4^0 & W_4^1 & W_4^2 & W_4^3 \ W_4^0 & W_4^2 & W_4^4 & W_4^6 \ W_4^0 & W_4^3 & W_4^6 & W_4^9 \end{bmatrix}$$ Let's evaluate each exponent using Twiddle periodicity ($W_N^{k+N} = W_N^k$) and symmetry properties: * $W_4^0 = 1$ * $W_4^1 = -j$ * $W_4^2 = e^{-j\pi} = -1$ * $W_4^3 = e^{-jrac{3\pi}{2}} = j$ * $W_4^4 = W_4^0 = 1$ * $W_4^6 = W_4^2 = -1$ * $W_4^9 = W_4^{8+1} = W_4^1 = -j$ Substituting these values yields the **Standard $4 imes 4$ DFT Matrix** [11.01]: $$\mathbf{\mathbf{W}_4 = egin{bmatrix} 1 & 1 & 1 & 1 \ 1 & -j & -1 & j \ 1 & -1 & 1 & -1 \ 1 & j & -1 & -j \end{bmatrix}}$$ --- ## 5. High-Yield Solved "Exam Killers" ### 5.1 Problem 1: Evaluating a 4-Point DFT Using Matrix Multiplication > [!question] **KUET Exam Classic [10 Marks]** > > Given the 4-point discrete-time sequence $x[n] = \{1, 2, 3, 4\}$. Evaluate its Discrete Fourier Transform $X[k]$ using the direct matrix multiplication method. #### Step 1: Set up the Matrix Equation $$\mathbf{X} = \mathbf{W}_4 \mathbf{x}$$ $$egin{bmatrix} X[0] \ X[1] \ X[2] \ X[3] \end{bmatrix} = egin{bmatrix} 1 & 1 & 1 & 1 \ 1 & -j & -1 & j \ 1 & -1 & 1 & -1 \ 1 & j & -1 & -j \end{bmatrix} egin{bmatrix} 1 \ 2 \ 3 \ 4 \end{bmatrix}$$ #### Step 2: Perform Row-by-Column Vector Multiplication * **For $X[0]$ (Row 1):** $$X[0] = 1(1) + 1(2) + 1(3) + 1(4) = 1 + 2 + 3 + 4 = \mathbf{10}$$ *{Note: The $X[0]$ bin always represents the DC sum of the signal}*. * **For $X[1]$ (Row 2):** $$X[1] = 1(1) + (-j)(2) + (-1)(3) + (j)(4)$$ $$X[1] = 1 - 2j - 3 + 4j = \mathbf{-2 + 2j}$$ * **For $X[2]$ (Row 3):** $$X[2] = 1(1) + (-1)(2) + 1(3) + (-1)(4)$$ $$X[2] = 1 - 2 + 3 - 4 = \mathbf{-2}$$ * **For $X[3]$ (Row 4):** $$X[3] = 1(1) + (j)(2) + (-1)(3) + (-j)(4)$$ $$X[3] = 1 + 2j - 3 - 4j = \mathbf{-2 - 2j}$$ #### Step 3: Write the Final Sequence and Perform Symmetry Checks The evaluated discrete spectrum is: $$\mathbf{X[k] = \{10, -2+2j, -2, -2-2j\}}$$ --- #### Causal Sequence Complex Conjugate Verification: For any real-valued sequence $x[n]$, the resulting DFT bins must satisfy conjugate symmetry: $$X[k] = X^*[N-k]$$ For our $N=4$ sequence: * $X[3] \stackrel{?}{=} X^*[4-3] = X^*[1]$ * $X[3] = -2-2j$ and $X^*[1] = (-2+2j)^* = -2-2j$ (Verified!) This simple check guarantees that your arithmetic was flawless and secures you 100% of the marks! --- ### 5.2 Problem 2: Computing the IDFT Using Only the Forward DFT > [!question] **KUET Exam Classic [PYQ 2024 - 8 Marks]** > > Why is the FFT called so? Prove mathematically how you can compute the Inverse Discrete Fourier Transform (IDFT) of a sequence $X[k]$ by using only a forward DFT/FFT algorithm. #### Part (i): Why is FFT called so? The Fast Fourier Transform (FFT) is called "Fast" because it is a computationally optimized implementation of the Discrete Fourier Transform (DFT). It exploits the mathematical symmetry and periodicity of the Twiddle factor complex exponential roots of unity ($W_N$) to reduce the total number of required complex multiplications from $O(N^2)$ to $O(N \log_2 N)$ [11.01]. #### Part (ii): Mathematical Proof of IDFT-via-DFT We begin with our standard forward DFT definition [11.01]: $$ ext{DFT}\{g[n]\} = G[k] = \sum_{n=0}^{N-1} g[n] W_N^{nk}$$ And our standard IDFT definition [11.01]: $$x[n] = rac{1}{N} \sum_{k=0}^{N-1} X[k] W_N^{-nk}$$ Taking the complex conjugate of both sides of the IDFT equation: $$x^*[n] = \left( rac{1}{N} \sum_{k=0}^{N-1} X[k] W_N^{-nk} ight)^* = rac{1}{N} \sum_{k=0}^{N-1} X^*[k] W_N^{nk}$$ Look closely at the summation term on the right-hand side. This summation is mathematically identical to a standard forward DFT operation on the complex conjugated spectrum sequence $X^*[k]$: $$\sum_{k=0}^{N-1} X^*[k] W_N^{nk} = ext{DFT}\left\{ X^*[k] ight\}$$ Substitute this forward DFT representation back into our conjugate equation: $$x^*[n] = rac{1}{N} ext{DFT}\left\{ X^*[k] ight\}$$ Finally, we isolate $x[n]$ by taking the complex conjugate of both sides again: $$\mathbf{x[n] = rac{1}{N} \left[ ext{DFT}\left\{ X^*[k] ight\} ight]^*}$$ This elegant proof demonstrates that we do not need to design or build a separate hardware block or block diagram for the IDFT! We can compute the IDFT on a DSP chip by using the same forward DFT block with three simple pre/post-processing steps. --- #### Step-by-Step DSP Implementation Algorithm: ``` ┌──────────┐ ┌───────────┐ ┌──────────┐ X[k] (Spectrum) ─>│ Conjugate│───> │ Forward │───> │ Conjugate│───> x[n] (Time) │ Block │ │ DFT Block │ │ & Div N │ └──────────┘ └───────────┘ └──────────┘ ``` 1. **Complex Conjugation:** Conjugate the input frequency-domain bins: $X[k] o X^*[k]$. 2. **Forward DFT:** Compute the standard forward DFT of the conjugated bins. 3. **Post-Processing:** Complex conjugate the output of the DFT block, and divide the final real and imaginary parts by the sequence length $N$ to reconstruct your time-domain signal $x[n]$. --- ## 6. Common Mistakes That Cost Marks > [!warning] **Critical Exam Pitfalls** > > 1. **Forgetting the $1/N$ Normalization Term in IDFT:** Evaluating the entire inverse summation perfectly but failing to divide the final terms by $N$. To prevent this, write out "Divide by $N$" as your very first step when solving IDFT problems. > 2. **Mixing Up Exponent Signs:** Using $W_N^{-nk}$ for forward DFT and $W_N^{nk}$ for IDFT. Remember: > * **Forward DFT = Negative exponent** (we are decomposing/decaying the signal). > * **Inverse DFT = Positive exponent** (we are growing/reconstructing the signal). > 3. **Indices Misalignment:** Starting matrix multiplications or sums using index $n=1$ instead of index $n=0$. Discrete signal mathematics relies strictly on index $0$ representing the origin. Starting at $1$ shifts your entire signal in the time/frequency domain, causing your phase values to be completely incorrect. --- ## 7. Verbatim PYQ Bank (Chapter 11) ```markdown ### Verbatim Past Year Questions (KUET ECE 2107 Section B) 1. [PYQ 2025 Q8a] Give the definition of DFT. Prove the computational efficiency of the Fast Fourier Transform (FFT) algorithm over the direct computation of the DFT. (05 Marks) 2. [PYQ 2024 Q8a] Why is FFT called so? How can you compute IDFT using FFT algorithm? (05 Marks) 3. [PYQ 2023 Q8a] What is FFT algorithm? Compare the computational complexity of DFT and Radix-2 DIT-FFT algorithms. (05 Marks) 4. [KUET 2022 Q8b] Calculate the 4-point DFT of the discrete-time sequence x[n] = {1, 2, 3, 4} using the direct matrix method. (08 Marks) ``` --- ## 8. Interactive Self-Check Checklist - [ ] Can you write out the forward DFT and IDFT mathematical equations with their exact limits? [11.01] - [ ] Can you prove mathematically that direct DFT requires $N^2$ multiplications, and describe why? [11.01] - [ ] Can you prove the IDFT-via-DFT conjugate-identity equation step-by-step? - [ ] Can you reconstruct the standard $4 imes 4$ Twiddle factor matrix $\mathbf{W}_4$ using Euler's formula? [11.01] --- _Grounded in the lecture slides by Shah Muhammad Azmat Ullah (Lecturer, Dept. of ECE, KUET) and "Signals and Systems" by K. Deergha Rao._ --- [[11.01_The_Discrete_Fourier_Transform_DFT|← 11.01 The Discrete Fourier Transform (DFT)]] | [[11.00_Chapter_Map_-_Discrete_Fourier_Transforms|Chapter 11 Map]] | [[11.03_Radix-2_Decimation-In-Time_FFT_Algorithm_DIT-FFT|11.03 Radix-2 Decimation-In-Time FFT Algorithm (DIT-FFT) →]] # 11.02 Properties of the DFT & Twiddle Factors Now, let's dive into **Properties of the DFT & Twiddle Factors**, one of the most analytical and scoring sections under Instructor 1. While the forward DFT allows us to compute discrete frequency bins from finite-duration time arrays [11.01], the efficiency of the Fast Fourier Transform (FFT) depends directly on the unique mathematical symmetries of the complex exponential phase factor—the **Twiddle Factor** $W_N$ [11.02]. Furthermore, because the DFT treats the finite time-domain sequence as if it were one period of an infinitely repeating periodic sequence [11.01], time-shifting and convolution behave differently under DFT boundaries compared to classical continuous-time or discrete-time Fourier analysis [11.02]. Let's master the mathematical proofs of twiddle factor symmetries, circular shifts, circular convolutions, and lock down your exam-solving strategies for circular-versus-linear convolution mapping! --- ## 1. The Twiddle Factor ($W_N$) Definition The **Twiddle Factor** (or phase factor) represents the fundamental complex exponential root of unity that drives the rotations in discrete frequency transforms [11.02]. ### 1.1 Mathematical Formulation The twiddle factor is defined as: $$W_N = e^{-j\frac{2\pi}{N}}$$ When evaluating the DFT of an $N$-point sequence, we raise this complex scalar to the power of the product of time index $n$ and frequency index $k$: $$W_N^{nk} = e^{-j\frac{2\pi}{N} nk} = \cos\left(\frac{2\pi}{N} nk\right) - j\sin\left(\frac{2\pi}{N} nk\right)$$ This expression represents a set of harmonically related complex phasors distributed uniformly around the unit circle in the complex plane, with angular spacing equal to $\Delta\theta = -\frac{2\pi}{N}$ radians per step [11.02]. --- ## 2. Twiddle Factor Symmetries & Proofs The Radix-2 Fast Fourier Transform (FFT) algorithm achieves its dramatic computational speed-up by exploiting two primary properties of the twiddle factor: **Periodicity** and **Symmetry** [11.02]. ### 2.1 Periodicity Property The twiddle factor is periodic with a period of $N$ across both time and frequency indices. > [!theorem] **Periodicity Proof** > > Show that $W_N^{k+N} = W_N^k$. > > **Proof:** > Substituting the complex exponential definition: > $$W_N^{k+N} = e^{-j\frac{2\pi}{N}(k+N)}$$ > > Distribute the exponent: > $$W_N^{k+N} = e^{-j\frac{2\pi}{N}k} \cdot e^{-j\frac{2\pi}{N}N}$$ > $$W_N^{k+N} = e^{-j\frac{2\pi}{N}k} \cdot e^{-j2\pi}$$ > > Since $e^{-j2\pi} = \cos(2\pi) - j\sin(2\pi) = 1$: > $$W_N^{k+N} = e^{-j\frac{2\pi}{N}k} \cdot 1 = W_N^k \quad [\text{Q.E.D.}]$$ --- ### 2.2 Symmetry Property The twiddle factor exhibits half-period anti-symmetry, meaning a half-period rotation results in a perfect phase inversion (negation) of the phasor. > [!theorem] **Symmetry Proof** > > Show that $W_N^{k + N/2} = -W_N^k$. > > **Proof:** > Substituting the complex exponential definition: > $$W_N^{k + N/2} = e^{-j\frac{2\pi}{N}\left(k + \frac{N}{2}\right)}$$ > > Distribute the exponent: > $$W_N^{k + N/2} = e^{-j\frac{2\pi}{N}k} \cdot e^{-j\frac{2\pi}{N}\frac{N}{2}}$$ > $$W_N^{k + N/2} = e^{-j\frac{2\pi}{N}k} \cdot e^{-j\pi}$$ > > Applying Euler's identity to the second factor: > $$e^{-j\pi} = \cos(\pi) - j\sin(\pi) = -1 - j(0) = -1$$ > > Substitute back: > $$W_N^{k + N/2} = e^{-j\frac{2\pi}{N}k} \cdot (-1) = -W_N^k \quad [\text{Q.E.D.}]$$ --- ### 2.3 Index Multi-Rate Scaling (Reduction) If we scale both the transform size and the exponent index by an integer factor $m$, the twiddle factor value remains invariant. > [!theorem] **Multi-Rate Scaling Proof** > > Show that $W_{mN}^{mk} = W_N^k$. > > **Proof:** > $$W_{mN}^{mk} = e^{-j\frac{2\pi}{mN}(mk)}$$ > > Cancelling the integer factor $m$ from both the numerator and denominator of the exponent: > $$W_{mN}^{mk} = e^{-j\frac{2\pi}{N}k} = W_N^k \quad [\text{Q.E.D.}]$$ --- ## 3. Circular Shifting Property of the DFT In classical discrete-time Fourier analysis (DTFT), shifting a sequence in time introduces a linear phase shift. However, because the DFT operates on a finite window of length $N$, shifting a sequence to the right causes samples that exit the boundary at index $N-1$ to wrap around and re-enter the window from the left at index $0$ [11.02]. This is called a **Circular Shift** (or modulo-$N$ shift) [11.02] and is represented mathematically as: $$x_{\text{shift}}[n] = x\left(\langle n - m \rangle_N\right) = x[(n - m) \pmod N]$$ ### 3.1 The Circular Shifting Property The DFT of a circularly shifted sequence is: $$\text{DFT}\left\{ x\left(\langle n - m \rangle_N\right) \right\} = W_N^{km} X[k]$$ > [!theorem] **Circular Shifting Proof** > > Prove that $\text{DFT}\{x\left(\langle n - m \rangle_N\right)\} = W_N^{km} X[k]$. > > **Proof:** > By the definition of the DFT: > $$Y[k] = \sum_{n=0}^{N-1} x\left(\langle n - m \rangle_N\right) W_N^{nk}$$ > > Let's perform a change of variable by setting $p = (n - m) \pmod N$, which implies $n = (p + m) \pmod N$. > Since the summation is evaluated over one complete period of a periodic sequence, summing over $n = [0, N-1]$ is identical to summing over $p = [0, N-1]$: > $$Y[k] = \sum_{p=0}^{N-1} x[p] W_N^{(p+m)k}$$ > > Factor the twiddle term: > $$Y[k] = \sum_{p=0}^{N-1} x[p] W_N^{pk} \cdot W_N^{km}$$ > > Since $W_N^{km}$ does not depend on the summation index $p$, we can slide it outside the summation operator: > $$Y[k] = W_N^{km} \sum_{p=0}^{N-1} x[p] W_N^{pk}$$ > > Recognizing that the remaining sum is the standard DFT $X[k]$: > $$Y[k] = W_N^{km} X[k] \quad [\text{Q.E.D.}]$$ --- ## 4. Circular Convolution Theorem When we multiply the DFTs of two finite-duration sequences of length $N$, the corresponding time-domain operation is **Circular Convolution** (or periodic convolution) [11.02]. Unlike linear convolution, circular convolution wraps indices around the sequence boundaries using modulo-$N$ arithmetic [11.02]. ### 4.1 Mathematical Formulation The circular convolution of two sequences $x_1[n]$ and $x_2[n]$ of length $N$ is denoted by the symbol $\otimes$ and is defined as: $$y_C[n] = x_1[n] \otimes x_2[n] = \sum_{m=0}^{N-1} x_1[m] x_2\left(\langle n - m \rangle_N\right)$$ --- ### 4.2 The Circular Convolution Theorem Proof Multiplying DFT spectra in the frequency domain is equivalent to circularly convolving the signals in the time domain [11.02]. > [!theorem] **Circular Convolution Theorem** > > Show that if $Y[k] = X_1[k] \cdot X_2[k]$, then $y[n] = x_1[n] \otimes x_2[n]$. > > **Proof:** > We begin by taking the Inverse DFT of the product spectrum $Y[k]$: > $$y[n] = \frac{1}{N} \sum_{k=0}^{N-1} Y[k] W_N^{-nk} = \frac{1}{N} \sum_{k=0}^{N-1} X_1[k] X_2[k] W_N^{-nk}$$ > > Substitute the forward DFT definition of $X_1[k]$ using summation variable $m$: > $$X_1[k] = \sum_{m=0}^{N-1} x_1[m] W_N^{mk}$$ > > Substitute this into the IDFT expression: > $$y[n] = \frac{1}{N} \sum_{k=0}^{N-1} \left( \sum_{m=0}^{N-1} x_1[m] W_N^{mk} \right) X_2[k] W_N^{-nk}$$ > > Interchanging the order of the summations: > $$y[n] = \sum_{m=0}^{N-1} x_1[m] \left( \frac{1}{N} \sum_{k=0}^{N-1} X_2[k] W_N^{-(n - m)k} \right)$$ > > Look closely at the term inside the parenthesis. This is exactly the Inverse DFT of $X_2[k]$ evaluated at the circularly wrapped index $(n - m) \pmod N$: >$$\frac{1}{N} \sum_{k=0}^{N-1} X_2[k] W_N^{-(n - m)k} = x_2\left(\langle n - m \rangle_N\right)$$ > > Substituting this back yields the final circular convolution sum: > $$y[n] = \sum_{m=0}^{N-1} x_1[m] x_2\left(\langle n - m \rangle_N\right) = x_1[n] \otimes x_2[n] \quad [\text{Q.E.D.}]$$ --- ## 5. Circular-to-Linear Convolution Mapping Circular and linear convolution are generally **not equal** because circular convolution wraps data around the boundaries, creating time-domain aliasing [11.02]. However, we can use the computationally efficient DFT/FFT framework to compute exact **linear convolutions** by using a technique called **Zero-Padding** [11.02]. ### 5.1 The Length Constraint Formula If $x_1[n]$ has length $N_1$ and $x_2[n]$ has length $N_2$, then their linear convolution $y_L[n]$ has a total length of: $$L = N_1 + N_2 - 1$$ To ensure that the circular convolution $y_C[n]$ yields the exact same numerical result as the linear convolution $y_L[n]$, we must pad both sequences with trailing zeros to a common length $N_{\text{pad}}$ that satisfies: $$N_{\text{pad}} \ge N_1 + N_2 - 1$$ ### 5.2 The Mechanism of Zero-Padding When we pad both sequences with zeros to length $L$, we create a "buffer zone" in the time domain [11.02]. When the circular shift wraps samples around the boundary modulo-$L$, they multiply against the padded zeros instead of actual signal data [11.02]. This prevents overlap wrap-around and completely eliminates time-domain aliasing [11.02]. ``` x₁[n] = {0, 1, 2, 3} (N₁=4) ────► Zero-Pad to L=7 ────► {0, 1, 2, 3, 0, 0, 0} x₂[n] = {1, 1, 2, 2} (N₂=4) ────► Zero-Pad to L=7 ────► {1, 1, 2, 2, 0, 0, 0} │ Multiply DFTs & Invert ▼ y[n] = {0, 1, 3, 7, 9, 10, 6} (Exact Linear) ``` --- ## 6. High-Yield Solved "Exam Killers" Let's dissect two actual past year exam questions to master the circular math and tabular layouts under test conditions! ### 6.1 Problem 1: The Linear-versus-Circular Comparison > [!question] **2018 Exam Section B Q. 3b** > > Given two sequences of length $N = 4$ defined by: > $$x_1[n] = \{\underline{0}, 1, 2, 3\}$$ > $$x_2[n] = \{\underline{1}, 1, 2, 2\}$$ > (i) Determine their linear convolution $y_L[n]$. > (ii) Determine their periodic (circular) convolution $y_C[n]$ of length $N = 4$. > (iii) Compare and show how linear convolution can be obtained using circular convolution. #### Part (i): Calculate Linear Convolution $y_L[n]$ The sequences have lengths $N_1 = 4$ and $N_2 = 4$. The linear convolution length is: $$L = N_1 + N_2 - 1 = 4 + 4 - 1 = 7$$ We use the **Tabular (Slant-Sum) Method** to calculate the coefficients. Lay out the multiplication matrix of $x_1[m]$ and $x_2[n-m]$: | $x_1 \setminus x_2$ | **1** | **1** | **2** | **2** | | :---: | :---: | :---: | :---: | :---: | | **0** | 0 | 0 | 0 | 0 | | **1** | 1 | 1 | 2 | 2 | | **2** | 2 | 2 | 4 | 4 | | **3** | 3 | 3 | 6 | 6 | Now, sum along the diagonals (slant-lines): * $y_L[0] = 0 = \mathbf{0}$ * $y_L[1] = 0 + 1 = \mathbf{1}$ * $y_L[2] = 0 + 1 + 2 = \mathbf{3}$ * $y_L[3] = 0 + 2 + 2 + 3 = \mathbf{7}$ * $y_L[4] = 2 + 4 + 3 = \mathbf{9}$ * $y_L[5] = 4 + 6 = \mathbf{10}$ * $y_L[6] = 6 = \mathbf{6}$ Thus, the linear convolution sequence is: $$\mathbf{y_L[n] = \{\underline{0}, 1, 3, 7, 9, 10, 6\}}$$ --- #### Part (ii): Calculate Circular Convolution $y_C[n]$ of length $N = 4$ Since $N = 4$, we use the **Matrix Multiplication (Circulant Matrix) Method**: $$\begin{bmatrix} y_C[0] \\ y_C[1] \\ y_C[2] \\ y_C[3] \end{bmatrix} = \begin{bmatrix} x_2[0] & x_2[3] & x_2[2] & x_2[1] \\ x_2[1] & x_2[0] & x_2[3] & x_2[2] \\ x_2[2] & x_2[1] & x_2[0] & x_2[3] \\ x_2[3] & x_2[2] & x_2[1] & x_2[0] \end{bmatrix} \begin{bmatrix} x_1[0] \\ x_1[1] \\ x_1[2] \\ x_1[3] \end{bmatrix}$$ Substitute the values $x_1 = [0, 1, 2, 3]^T$ and $x_2 = [1, 1, 2, 2]^T$: $$\begin{bmatrix} y_C[0] \\ y_C[1] \\ y_C[2] \\ y_C[3] \end{bmatrix} = \begin{bmatrix} 1 & 2 & 2 & 1 \\ 1 & 1 & 2 & 2 \\ 2 & 1 & 1 & 2 \\ 2 & 2 & 1 & 1 \end{bmatrix} \begin{bmatrix} 0 \\ 1 \\ 2 \\ 3 \end{bmatrix}$$ Multiply rows by the column vector: * $y_C[0] = (1 \cdot 0) + (2 \cdot 1) + (2 \cdot 2) + (1 \cdot 3) = 0 + 2 + 4 + 3 = \mathbf{9}$ * $y_C[1] = (1 \cdot 0) + (1 \cdot 1) + (2 \cdot 2) + (2 \cdot 3) = 0 + 1 + 4 + 6 = \mathbf{11}$ * $y_C[2] = (2 \cdot 0) + (1 \cdot 1) + (1 \cdot 2) + (2 \cdot 3) = 0 + 1 + 2 + 6 = \mathbf{9}$ * $y_C[3] = (2 \cdot 0) + (2 \cdot 1) + (1 \cdot 2) + (1 \cdot 3) = 0 + 2 + 2 + 3 = \mathbf{7}$ Thus, the $4$-point circular convolution sequence is: $$\mathbf{y_C[n] = \{\underline{9}, 11, 9, 7\}}$$ --- #### Part (iii): Compare and map circular-to-linear mapping Comparing the results: $$y_L[n] = \{\underline{0}, 1, 3, 7, 9, 10, 6\}$$ $$y_C[n] = \{\underline{9}, 11, 9, 7\}$$ We notice that $y_L[n] \neq y_C[n]$. The circular convolution suffered from **time-domain aliasing** [11.02]. Mathematically, circular convolution corresponds to wrapping the linear convolution modulo $N=4$: $$y_C[n] = \sum_{r=-\infty}^{\infty} y_L[n + rN]$$ Let's verify this relation: * $y_C[0] = y_L[0] + y_L[4] = 0 + 9 = \mathbf{9} \quad [\text{Verified!}]$ * $y_C[1] = y_L[1] + y_L[5] = 1 + 10 = \mathbf{11} \quad [\text{Verified!}]$ * $y_C[2] = y_L[2] + y_L[6] = 3 + 6 = \mathbf{9} \quad [\text{Verified!}]$ * $y_C[3] = y_L[3] = \mathbf{7} \quad [\text{Verified!}]$ **How to obtain linear convolution using circular convolution:** To recover the exact linear convolution, we pad both sequences with trailing zeros to a common length of $L = N_1 + N_2 - 1 = 7$: * $x_{1,\text{pad}}[n] = \{\underline{0}, 1, 2, 3, 0, 0, 0\}$ * $x_{2,\text{pad}}[n] = \{\underline{1}, 1, 2, 2, 0, 0, 0\}$ Performing a 7-point circular convolution on these padded sequences yields: $$y_{C,7}[n] = \{\underline{0}, 1, 3, 7, 9, 10, 6\} = y_L[n]$$ This matches the linear convolution perfectly, proving that zero-padding prevents time-aliasing [11.02]. --- ### 6.2 Problem 2: Symmetric Waveform Convolution > [!question] **2017 Exam Section B Q. 3b** > > Given two sequences of length $N = 4$ defined by: > $$x_1[n] = \{\underline{1}, 2, 2, 1\}$$ > $$x_2[n] = \{\underline{2}, 1, 1, 2\}$$ > Determine their linear and periodic (circular) convolution. #### Step 1: Calculate Linear Convolution The output sequence length is $L = 4 + 4 - 1 = 7$. Lay out the multiplication matrix: | $x_1 \setminus x_2$ | **2** | **1** | **1** | **2** | | :---: | :---: | :---: | :---: | :---: | | **1** | 2 | 1 | 1 | 2 | | **2** | 4 | 2 | 2 | 4 | | **2** | 4 | 2 | 2 | 4 | | **1** | 2 | 1 | 1 | 2 | Sum along the diagonals: * $y_L[0] = \mathbf{2}$ * $y_L[1] = 1 + 4 = \mathbf{5}$ * $y_L[2] = 1 + 2 + 4 = \mathbf{7}$ * $y_L[3] = 2 + 2 + 2 + 2 = \mathbf{8}$ * $y_L[4] = 4 + 2 + 1 = \mathbf{7}$ * $y_L[5] = 4 + 1 = \mathbf{5}$ * $y_L[6] = \mathbf{2}$ Thus, the linear convolution is: $$\mathbf{y_L[n] = \{\underline{2}, 5, 7, 8, 7, 5, 2\}}$$ --- #### Step 2: Calculate Periodic (Circular) Convolution of length $N = 4$ Using the circulant matrix multiplication method: $$\begin{bmatrix} y_C[0] \\ y_C[1] \\ y_C[2] \\ y_C[3] \end{bmatrix} = \begin{bmatrix} 2 & 2 & 1 & 1 \\ 1 & 2 & 2 & 1 \\ 1 & 1 & 2 & 2 \\ 2 & 1 & 1 & 2 \end{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 2 \\ 1 \end{bmatrix}$$ Calculate terms: * $y_C[0] = (2 \cdot 1) + (2 \cdot 2) + (1 \cdot 2) + (1 \cdot 1) = 2 + 4 + 2 + 1 = \mathbf{9}$ * $y_C[1] = (1 \cdot 1) + (2 \cdot 2) + (2 \cdot 2) + (1 \cdot 1) = 1 + 4 + 4 + 1 = \mathbf{10}$ * $y_C[2] = (1 \cdot 1) + (1 \cdot 2) + (2 \cdot 2) + (2 \cdot 1) = 1 + 2 + 4 + 2 = \mathbf{9}$ * $y_C[3] = (2 \cdot 1) + (1 \cdot 2) + (1 \cdot 2) + (2 \cdot 1) = 2 + 2 + 2 + 2 = \mathbf{8}$ Thus, the periodic convolution sequence is: $$\mathbf{y_C[n] = \{\underline{9}, 10, 9, 8\}}$$ *(Verification check via time-aliasing formula: $y_C[0] = y_L[0] + y_L[4] = 2 + 7 = 9$; $y_C[1] = y_L[1] + y_L[5] = 5 + 5 = 10$; $y_C[2] = y_L[2] + y_L[6] = 7 + 2 = 9$; $y_C[3] = y_L[3] = 8$. Perfectly consistent!)* --- ## 7. Common Mistakes That Cost Marks > [!caution] **Critical Exam Pitfalls** > > 1. **Evaluating Linear Convolution instead of Circular:** When a question asks for "periodic convolution" or "circular convolution," do not write the linear convolution array. You **must** either perform circulant matrix multiplication or compute linear convolution and apply modulo-$N$ summation wrap-around [11.02]. > 2. **Under-Padding Zero-Padded Sequences:** Padding to length $L = N_1 + N_2$ instead of $L = N_1 + N_2 - 1$. Leaving out the $-1$ term leads to an extra trailing zero, which wastes memory and is penalized by examiners. > 3. **Misaligning Circulant Matrix Columns:** When constructing the circulant matrix for circular convolution, remember that columns shift **downward and rightward** with wrap-around. Writing a standard Toeplitz matrix without wrap-around will completely ruin your calculations. --- ## 8. Verbatim Past Year Question (PYQ) Bank ### 8.1 Periodic & Linear Convolution Problems * **[PYQ 2018 - 5 Marks]:** Given two sequences of length $N=4$ defined by $x_1[n] = \{0, 1, 2, 3\}$ and $x_2[n] = \{1, 1, 2, 2\}$. Determine their linear and periodic (circular) convolution. * **[PYQ 2017 - 3 Marks]:** Given two sequences of length $N=4$ defined by $x_1[n] = \{1, 2, 2, 1\}$ and $x_2[n] = \{2, 1, 1, 2\}$. Determine their linear and periodic convolution. --- ## 9. Properties of the DFT & Twiddle Factors Self-Check - [ ] Can you state and prove the periodicity property of the twiddle factor $W_N$? - [ ] Can you state and prove the symmetry property of the twiddle factor $W_N$? - [ ] Do you know how to write down a circular convolution circulant matrix without error? - [ ] Do you understand why circular and linear convolutions differ, and how to eliminate time-aliasing using zero-padding? - [ ] Can you correctly compute the linear and circular convolution of the sequences $x_1 = \{0, 1, 2, 3\}$ and $x_2 = \{1, 1, 2, 2\}$ under exam time limits? --- *Source: (k.Deergha Rao) signals and systems.pdf, 05 DFT FFT.pdf, KUET ECE 2107 Past Year Question Papers (2018, 2017)* --- [[11.02_Properties_of_the_DFT_and_Twiddle_Factors|← 11.02 Properties of the DFT & Twiddle Factors]] | [[11.00_Chapter_Map_-_Discrete_Fourier_Transforms|Chapter 11 Map]] | [[11.04_Radix-2_Decimation-In-Frequency_FFT_Algorithm_DIF-FFT|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) > [!abstract] **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 \quad \implies \quad L = \log_2(N) \quad ext{where } L \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} \quad ext{for } 0 \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] \quad ext{for } r = 0, 1, \dots, N/2 - 1 \quad ext{{Even-indexed subsequence}}$ * $h[r] = x[2r+1] \quad ext{for } r = 0, 1, \dots, N/2 - 1 \quad ext{{Odd-indexed subsequence}}$ 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] \quad ext{for } 0 \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$: $$G\left[k + rac{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]$? --- [[11.03_Radix-2_Decimation-In-Time_FFT_Algorithm_DIT-FFT|← 11.03 Radix-2 Decimation-In-Time FFT Algorithm (DIT-FFT)]] | [[11.00_Chapter_Map_-_Discrete_Fourier_Transforms|Chapter 11 Map]] | [[Chapter_12_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} \quad ext{for } k = 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}: $$X[k] = \sum_{n=0}^{N/2-1} x[n] W_N^{nk} + \sum_{n=0}^{N/2-1} x\left[n + rac{N}{2} 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).*