I got confused in the FFT butterfly diagram. Can someone please help me understand it?
If I have the vector $x = (-3, -2, -1, 0, 1, 2, 3, 4)$, and I want to apply FFT to it using the Butterfly diagram, how is the procedure exactly done? I've found these diagrams on the internet, but I don't know how to read them.
It is in my understanding that at first step we take $x(0) = -3$ and $x(2) = -1$, but then what do we do with them? Add them and multiply by something? Please explain.
I have a sample 4-point diagram where $x(0)=0$ and $x(2)=2$ get transformed to $1$, and $x(1) = 1$ and $x(3) = 1$ get transformed into $0$. But I don't know how exactly that happens. Would appreciate a good clarification. It seems very vague to me so far.