11.02 Properties of the DFT and Twiddle Factors

← 11.01 The Discrete Fourier Transform (DFT) | Chapter 11 Map | 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.

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[\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.

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[\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.

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[\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(⟨n-m{⟩}_N\right)=x[(n-m)(\mathrm{mod}N)]$

3.1 The Circular Shifting Property

The DFT of a circularly shifted sequence is: $\text{DFT}\left\{x\left(⟨n-m{⟩}_N\right)\right\}=W_N^{km}X[k]$

Circular Shifting Proof

Prove that $\text{DFT}\{x\left(⟨n-m{⟩}_N\right)\}=W_N^{km}X[k]$.

Proof: By the definition of the DFT: $Y[k]={\sum }_{n=0}^{N-1}x\left(⟨n-m{⟩}_N\right)W_N^{nk}$

Let’s perform a change of variable by setting $p=(n-m)(\mathrm{mod}N)$, which implies $n=(p+m)(\mathrm{mod}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][\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(⟨n-m{⟩}_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].

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)(\mathrm{mod}N)$: $\frac{1}{N}{\sum }_{k=0}^{N-1}{X}_2[k]W_N^{-(n-m)k}=x_2\left(⟨n-m{⟩}_N\right)$

Substituting this back yields the final circular convolution sum: $y[n]={\sum }_{m=0}^{N-1}{x}_1[m]x_2\left(⟨n-m{⟩}_N\right)=x_1[n]\otimes x_2[n][\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

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=0$
• $y_L[1]=0+1=1$
• $y_L[2]=0+1+2=3$
• $y_L[3]=0+2+2+3=7$
• $y_L[4]=2+4+3=9$
• $y_L[5]=4+6=10$
• $y_L[6]=6=6$

Thus, the linear convolution sequence is: ${\mathbf{y}}_{\mathbf{L}}[\mathbf{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: $\left[\begin{array}{c}{y}_C[0]\\ y_C[1]\\ y_C[2]\\ y_C[3]\end{array}\right]=\left[\begin{array}{cccc}{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{array}\right]\left[\begin{array}{c}{x}_1[0]\\ x_1[1]\\ x_1[2]\\ x_1[3]\end{array}\right]$

Substitute the values $x_1=[0,1,2,3{]}^T$ and $x_2=[1,1,2,2{]}^T$: $\left[\begin{array}{c}{y}_C[0]\\ y_C[1]\\ y_C[2]\\ y_C[3]\end{array}\right]=\left[\begin{array}{cccc}1& 2& 2& 1\\ 1& 1& 2& 2\\ 2& 1& 1& 2\\ 2& 2& 1& 1\end{array}\right]\left[\begin{array}{c}0\\ 1\\ 2\\ 3\end{array}\right]$

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=9$
• $y_C[1]=(1\cdot 0)+(1\cdot 1)+(2\cdot 2)+(2\cdot 3)=0+1+4+6=11$
• $y_C[2]=(2\cdot 0)+(1\cdot 1)+(1\cdot 2)+(2\cdot 3)=0+1+2+6=9$
• $y_C[3]=(2\cdot 0)+(2\cdot 1)+(1\cdot 2)+(1\cdot 3)=0+2+2+3=7$

Thus, the $4$-point circular convolution sequence is: ${\mathbf{y}}_{\mathbf{C}}[\mathbf{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]\ne 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=9[\text{Verified!}]$
• $y_C[1]=y_L[1]+y_L[5]=1+10=11[\text{Verified!}]$
• $y_C[2]=y_L[2]+y_L[6]=3+6=9[\text{Verified!}]$
• $y_C[3]=y_L[3]=7[\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

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]=2$
• $y_L[1]=1+4=5$
• $y_L[2]=1+2+4=7$
• $y_L[3]=2+2+2+2=8$
• $y_L[4]=4+2+1=7$
• $y_L[5]=4+1=5$
• $y_L[6]=2$

Thus, the linear convolution is: ${\mathbf{y}}_{\mathbf{L}}[\mathbf{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: $\left[\begin{array}{c}{y}_C[0]\\ y_C[1]\\ y_C[2]\\ y_C[3]\end{array}\right]=\left[\begin{array}{cccc}2& 2& 1& 1\\ 1& 2& 2& 1\\ 1& 1& 2& 2\\ 2& 1& 1& 2\end{array}\right]\left[\begin{array}{c}1\\ 2\\ 2\\ 1\end{array}\right]$

Calculate terms:

• $y_C[0]=(2\cdot 1)+(2\cdot 2)+(1\cdot 2)+(1\cdot 1)=2+4+2+1=9$
• $y_C[1]=(1\cdot 1)+(2\cdot 2)+(2\cdot 2)+(1\cdot 1)=1+4+4+1=10$
• $y_C[2]=(1\cdot 1)+(1\cdot 2)+(2\cdot 2)+(2\cdot 1)=1+2+4+2=9$
• $y_C[3]=(2\cdot 1)+(1\cdot 2)+(1\cdot 2)+(2\cdot 1)=2+2+2+2=8$

Thus, the periodic convolution sequence is: ${\mathbf{y}}_{\mathbf{C}}[\mathbf{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

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)