Twiddle factors in DSP for calculating DFT, FFT and IDFT

Throughout this Digital Signal Processing course, we are/will be seeing a trend of simplifying mathematical operations. From the various transforms (Laplace, Z, Fourier) to using different forms of number representations, the general objective is to simplify and optimize calculations. The twiddle factor is a major key component in this pursuit of simplicity. In this article, we will understand the twiddle factors’ purpose, definition, and applications.

Contents

What are twiddle factors?

Twiddle factors (represented with the letter W) are a set of values that is used to speed up DFT and IDFT calculations.

For a discrete sequence x(n), we can calculate its Discrete Fourier Transform and Inverse Discrete Fourier Transform using the following equations.

DFT: x(k) = $\sum _{ n=0 }^{ N-1 }{ x(n){ e }^{ \frac { -j2\pi nk }{ N } } }$

IDFT: x(n) = $\frac { 1 }{ N } \sum _{ n=0 }^{ N-1 }{ x(k){ e }^{ \frac { j2\pi nk }{ N } } }$

The computation procedure for the above is quite complex.

Complexity

To be pedantic, the DFT requires NxN complex multiplications and N(N-1) complex additions. Without the twiddle factor, the computational complexity of DFT is O(n²). With twiddle factors, the computational complexity is Nlog2N. Let’s keep this information aside for a moment though.

Twiddle factors are mathematically represented as:

${ W }_{ N }={ e }^{ -j2\pi /N }$

Rewriting the equations for calculating DFT and IDFT using twiddle factors we get:

DFT: $\sum _{ n=0 }^{ N-1 }{ x(n){ { W }_{ N }^{ nk } } }$

IDFT: $\frac { 1 }{ N } \sum _{ n=0 }^{ N-1 }{ x(k){ { W }_{ N }^{ -nk } } }$

Why do we use twiddle factors?

We use the twiddle factor to reduce the computational complexity of calculating DFT and IDFT.

The twiddle factor is a rotating vector quantity. All that means is that for a given N-point DFT or IDFT calculation, it is observed that the values of the twiddle factor repeat at every N cycles. The expectation of a familiar set of values at every (N-1)th step makes the calculations slightly easier. (N-1 because the first sequence is a 0)

Alternatively, we can also say that the twiddle factor has periodicity/a cyclic property. We’ll graphically see this below.

Cyclic property of twiddle factors

For a 4-point DFT

Let’s derive the twiddle factor values for a 4-point DFT using the formula above.

For n=0 and k=0,

${ W }_{ N }^{ nk }$ $={ W }_{ 4 }^{ 0 }={ e }^{ 0 }=1$

(From Euler’s formula: ${ e }^{ i\theta }=Cos\theta +iSin\theta$ )

Similarly calculating for the remaining values we get the series below:

${ W }_{ 4 }^{ 0 }$ = 1

${ W }_{ 4 }^{ 1 }$ = -j

${ W }_{ 4 }^{ 2 }$ = -1

${ W }_{ 4 }^{ 3 }$ = j

${ W }_{ 4 }^{ 4 }$ = 1

As you can see, the value starts repeating at the 4th instant. This periodic property can is shown in the diagram below.

For an 8-point DFT

Let’s derive the twiddle factor values for an 8-point DFT using the formula above.

For n=0 and k=0,

${ W }_{ 8 }^{ 0 }$ = 1

Similarly calculating for the remaining values we get the series below:

${ W }_{ 8 }^{ 0 }$ = 1

${ W }_{ 8 }^{ 1 }$ = 0.707-0.707j

${ W }_{ 8 }^{ 2 }$ = -j

${ W }_{ 8 }^{ 3 }$ = -0.707-0.707j

${ W }_{ 8 }^{ 4 }$ = -1

${ W }_{ 8 }^{ 5 }$ = -0.707+0.707j

${ W }_{ 8 }^{ 6 }$ = j

${ W }_{ 8 }^{ 7 }$ = 0.707+0.707j

${ W }_{ 8 }^{ 8 }$ = 1

As you can see, the value starts repeating at the 8th instant. This periodic property can is shown in the diagram below.

Matrix method of calculating DFT and IDFT with twiddle factors

The above DFT equation using the twiddle factor can also be written in matrix form. The matrix form of calculating a DFT and an IDFT eases up many calculations.

X(k) = ${ W }_{ N }$ x(n)

$\left[ \begin{matrix} X(0) \\ X(1) \\ . \\ . \\ . \\ X(N-1) \end{matrix} \right] = \left[ \begin{matrix} { W }_{ N }^{ 0 } & { W }_{ N }^{ 0 } & . & . & . & { W }_{ N }^{ 0 } \\ { W }_{ N }^{ 0 } & { W }_{ N }^{ 1 } & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & { W }_{ N }^{ { (N-1) }^{ 2 } } \end{matrix} \right] \left[ \begin{matrix} x(0) \\ x(1) \\ . \\ . \\ . \\ x(N-1) \end{matrix} \right]$

Similarly an IDFT can be calculated using a matrix form using the following equation.

x(n) = $\frac { { W }_{ N }^{ * }x }{ N }$

Here, ${ W }_{ N }^{ * }$ is the complex conjugate of the twiddle factor. To get the values of the complex conjugate, just invert the signs of the complex components of the twiddle factor. For example: The complex conjugate of 0.707+0.707j will become 0.707-0.707j.

DFT as linear transform

The matrix of ${ W }_{ N }$ is known as the matrix of linear transformation. Check out the scene of the linear transformation in DFT below.

We have the formula for calculating DFT using a matrix as:

X(k) = ${ W }_{ N }$ x(n)

x(n) = ${ W }_{ N }^{ -1 }$ X(k)

We also have the formula for calculating the IDFT using a matrix as:

x(n) = $\frac { { W }_{ N }^{ * }x }{ N }$

Equating the last two equations:

${ W }_{ N }^{ -1 }$ = $\frac { { W }_{ N }^{ * } }{ N }$

${ W }_{ N }^{ * }{ W }_{ N }\quad =\quad N{ I }_{ N }$

Here, ‘I’ is an identity matrix of order N. This equation represents the fact that the DFT displays linear transformation characteristics.

Now that we understand the twiddle factor, we can also see how it is used practically in the calculation of IDFT using the Decimation in Frequency FFT algorithm.

6 thoughts on “Twiddle factors in DSP for calculating DFT, FFT and IDFT”

Fernando says:

April 29, 2022 at 8:12 PM

The periodic property diagram shows that the value for (W8)^5 as being -0.707-j0.707, but the correct value is -0.707+j0.707.

vivek says:

October 31, 2021 at 4:55 PM

the fifth twiddle factor for 8 point dft on the image

Dave says:

July 9, 2020 at 6:12 AM

You put nk in the exponential but why isn’t it just n ? wouldn’t n*k basically be n^2 since n and k are the indexs and are always the same? The wiki doesn’t state it as n*k …

1. Umair Hussaini says:
  
  July 18, 2020 at 11:47 AM
  
  The Fourier series expansion of x(n) is represented by the function e^(j2(pi)nk/N) where N is the number of expressions and n exists for all values but k is from 0 to N-1. Hence the n and the k are separate. To be more specific, for the DFT equation n exists for all values but k is from 0 to N-1. For the IDFT equation above n exists from 0 to N-1, but k exists for all values. And that’s why we can’t write n^2. I hope that answers your question.
  
  1. Mohammed Adnan says:
    
    September 22, 2020 at 1:04 PM
    
    Bro n represents the time domain in discrete form and k represents frequency domain in discete .your are not giving comfort statements to estimate dft terms .By reading your statements we are getting confused to differentiate betwwen ‘n’ and ‘k’ terms in dft expression
    
    1. Umair Hussaini says:
      
      October 10, 2020 at 9:25 PM
      
      Yes you are absolutely right! Umm I am unable to find the location where I might have written it incorrectly though. Can you please let me know the section of the article that’s creating confusion. I will make the necessary clarification if needed.