# Magic of twiddle factor in DFT

In DFT calculation following formula is used $$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j2\pi\frac{kn}{N}}$$ where the Twiddle factor is known as complex root of unity, that is a complex number $W_N$ such that $(W_N)^N = 1$. There are $N$, $N$-th roots of unity. $$\big( W_N \big)^{k} = e^{j2\pi\frac{k}{N}} = (\omega_N)^k$$

Suppose I am doing 8 point DFT. Then I am able to get the 8 frequency bins output of this DFT formula : $X[0], \ldots, X[7]$.

Please suggest what magic this twiddle factor does that when each twiddle factor is multiplied with samples & summation is done then we get the respective frequency bin?

• Twiddle factors occur in the implementation of the DFT via certain FFT algorithms. Just looking at the formulas for the DFT will not reveal twiddle factors at all; there are none. – Dilip Sarwate Jun 1 '17 at 16:13
• You can understand that magic if you learn about correlation and orthogonality. – QMC Jun 1 '17 at 23:38
• @DilipSarwate Dilip i believe that is incorrect: the twiddle factors are indeed in the DFT as referred to in Tuley and Cookey's original paper and used to derive the FFT algorithm. The DFT formula specifically is written with the twiddle factors (W_n^N) as a simple substitution for the exponential representation of the same. – Dan Boschen Jun 2 '17 at 11:48

Please see Different way to separate a particular frequency from a signal where I explain the difference and similarity between homodyning the signal and homodyning the coefficients. The DFT is an example of homodyning the coefficients, such that multiplying the coefficients of what would otherwise be a moving average low pass filter by $e^{j2\pi f_c t}$ creates a bandpass response around frequency $f_c$. Twiddle factors are simply the discrete samples of $e^{j2\pi f_c t}$!

Observe specifically in the DFT matrix that the second row steps through all the samples in the roots of unity, so goes around the unit circle once (representing the normalized frequency of one sample per cycle). The third row steps through every other sample in the roots of unity and in the process goes around the unit circle twice, the fourth row goes around the unit circle three times, etc. (The first row is all ones representing no rotation, DC, or the base moving average filter). Note that going past $f_s/2$, where $f_s$ is the sampling rate, that the higher positive rotations alias to negative rotations. For example in the 4 point DFT as illustrated below, the normalized frequencies of 0, 1, 2 and 3 are also 0, 1, -2, -1; rotating twice around the unit circle counter-clockwise is the same as rotating twice around the unit circle clockwise when the twiddle factors are just 0, j, -1 and -j: (0, -1, 0, -1). Rotating three times counter-clockwise is the same as rotating once clockwise: (0, -j, -1, j).

The DFT as a filter bank is much clearer if you consider the case of a "streaming DFT" where we shift through a much longer sequence and compute the DFT once after each shift. In this case every point of the DFT would be identical to the output of a FIR filter with the coefficients as given by the DFT row associates with that output.

• Homodyning is the process of translating one frequency to another by multiplying the signals; multiplying a signal by $e^{j \omega t}$ will translate the signal in frequency by $\omega$. See the shifting or translation property of the Fourier Transform. Homodyne receivers utilize this property by multiplying the received signal at carrier $f_c$ with a local oscillator such as $cos(2\pi f_c t)$ to translate the carrier to D.C. Expand cosine using Euler's identity and you will see the same thing is happening as I describe with exponentials. – Dan Boschen Jun 2 '17 at 13:20
• Yes - but more simply observe what happens when you multiply by $e^{j\omega t}$:The basis vectors are just sampled versions of $e^{j\omega t}$, note that $e^{j \omega_1 t}e^{j\omega_2 t}= e^{j(\omega_1+\omega_2)t}$, demonstrating how frequency translation (homodyning) occurs. – Dan Boschen Jun 2 '17 at 14:25