3
$\begingroup$

The term "butterfly " is often used in association with fft texts But what exactly is a butterfly ?a matrix/group of i/o's is known as butterfly? Such as 2 input 2 output butterflies in stage 1 of attached photo

How we can differentiate between butterflies of stage 1 and stage 2?other than number of i/o's? enter image description here

$\endgroup$
6
$\begingroup$

A FFT "butterfly" is the name for an algorithmic structure inside the FFT. It

  • has two complex inputs
  • two complex outputs
  • one complex multiply
  • sum and difference of two complex numbers

There are two basic types. The decimation-in-time butterfly does the multiply first $$y_0 = x_0 + x_1 \cdot W$$ $$ y_1 = x_0 - x_1 \cdot W $$

Decimation-in-Frequency computes the sum/difference operation first $$ y_0 = (x_0 + x_1) $$ $$ y_1 = (x_0 - x_1) \cdot W $$

It's useful to write this in matrix notation. Decimation-in-time: $$ \begin{pmatrix} y_0 \\ y_1 \end{pmatrix} = \begin{pmatrix} 1 & W \\ 1 & -W \end{pmatrix} \cdot \begin{pmatrix} x_0 \\ x_1 \end{pmatrix} $$

and decimation-in-frequency:

$$\begin{pmatrix} y_0 \\ y_1 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ W & -W \end{pmatrix} \cdot \begin{pmatrix} x_0 \\ x_1 \end{pmatrix} $$

So the matrices are transposed of each other.

Update:

The twiddle factor $W$ is a function of which stage you are in and which butterfly inside the stage. For decimation-in-time, $W$ simply alternates between $+1$ and $-1$, i.e. $W = [+1,-1,+1,-1 ...]$ so there is no need for an actual multiplication. Similarly for the second stage we have $W=[1, -j, -1, j, 1, -j, ...]$ which also doesn't require multiplication. This property can be used to further optimize the implementation and so in many Implementation these stages are hand-coded

$\endgroup$
6
  • $\begingroup$ Very nice explanation $\endgroup$ – Man Jun 23 '20 at 1:26
  • 1
    $\begingroup$ But it will be much better if you elaborate on differences between butterflies of stage 1 and stage 2 $\endgroup$ – Man Jun 23 '20 at 1:27
  • $\begingroup$ Your bullet number 4, sum and difference or two complex numbers $\endgroup$ – Man Jun 23 '20 at 1:29
  • $\begingroup$ Isn't there any J term in W matrix for stage 1? $\endgroup$ – engr Jun 24 '20 at 12:36
  • $\begingroup$ You have mentioned about W values of 2nd stage ,nice, but please explain number of io's . As apparently io's are double $\endgroup$ – Man Jun 24 '20 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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