3
$\begingroup$

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$$ enter image description here

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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Dilip Sarwate
    Jun 1, 2017 at 16:13
  • $\begingroup$ You can understand that magic if you learn about correlation and orthogonality. $\endgroup$
    – QMC
    Jun 1, 2017 at 23:38
  • 2
    $\begingroup$ @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. $\endgroup$
    – Dan Boschen
    Jun 2, 2017 at 11:48

2 Answers 2

Reset to default
3
$\begingroup$

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: 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).

dft as filter bank

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ 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[1] row right ? for X[1] rotation is once right i.e (pi/2 radians , pi radian, 3*pi/2 radian, then 2pi radian) .. but how X[2] 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 ? $\endgroup$
    – user6363
    Jun 2, 2017 at 12:08
  • 1
    $\begingroup$ Sorry first row is no rotation (DC), and second row rotate once etc let me fix that $\endgroup$
    – Dan Boschen
    Jun 2, 2017 at 12:14
  • $\begingroup$ 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 " $\endgroup$
    – user6363
    Jun 2, 2017 at 13:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – Dan Boschen
    Jun 2, 2017 at 13:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – Dan Boschen
    Jun 2, 2017 at 14:25
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ 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 $\endgroup$
    – Dilip Sarwate
    Jun 2, 2017 at 0:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.