← 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 to a continuous, -periodic function of frequency } [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 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 of length (defined over ) 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._