# Difficulty regarding grasping concept of fft butterfly?

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?

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

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