Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It only takes a minute to sign up.
Sign up to join this community
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
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
