More topics in Digital Signal Processing

# 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 squared). 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.