11.00 Discrete Fourier Transforms Compact Review

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)