# 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, \ldots, X$.

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

## 2 Answers

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.

• e-sciencecentral.org/upload/etrij/thumb/… if we see in this link at ( 0 radian we have = 1 , then at pi/2 = j, then Pi = -1, and 3*Pi/2 = -j )... you are saying first row rotate around once so here you are taking about X row right ? for X rotation is once right i.e (pi/2 radians , pi radian, 3*pi/2 radian, then 2pi radian) .. but how X is two rotation (pi radian, 2pi radian , pi radian , 2pi radian) do you mean here in each multiplication we are moving around circle by pi radian ? – user6363 Jun 2 '17 at 12:08
• Sorry first row is no rotation (DC), and second row rotate once etc let me fix that – Dan Boschen Jun 2 '17 at 12:14
• What exactly you mean by "homodyning the signal and homodyning the coefficients. " .. a per wiki .. " en.wikipedia.org/wiki/Homodyne_detection Homodyne detection is a method of extracting information encoded as modulation of the phase and/or frequency of an oscillating signal, by comparing that signal with a standard oscillation " – user6363 Jun 2 '17 at 13:01
• 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

The twiddle factors happen to be samples of the basis vectors of the orthogonal transform.

The "magic" is that each DFT basis vector creates a matched filter (one complex or two real matched filters) for an FFT result bin. The twiddle factors can also be thought of as the filter taps.

• I have no idea what is meant by this answer. All the words are known to me, and the sentences parse, but the meaning eludes me. Please expand your answer and explain a little bit more. Thanks – Dilip Sarwate Jun 2 '17 at 0:45