What's the meaning of butterflies on FFT algorithm?

[ChepRidwan]

Meaning of butterfly on FFT algorithm?
Why on FFT algorithm, N point sample input divided to even and odd number?

I want to know the flowchart for programing FFT? ... I don't using Mathlab...

 

[mehtesham]

Re: Programing FFT

this books may help you on algorithms

 

[mro83]

Re: Programing FFT

The pix are from DSP by Oppenheim and Schafer.
for more details refer to chapter 9 of the book. (the book is available in EDAboard).
regards

 

[shameem]

Re: Programing FFT

hi,
when you draw the flowchart of the FFT, you will see that the structure of the algorithm is like cascaded butterflies.
we divide the computation into even and odd indexs so that we can use the periodicity property in the computation of the FFT.
you can get better idea in the book "DISCRETE-TIME SIGNAL PROCESSING" by Alan V. Oppenheim, Ronald W. Schafer.