There are a lot of information about FFT but I don't know any book that
says how the butterfly algorithm computes the spectrum intuitively by using
vector images.
FFT (Fast Fourier Transform) is very efficient algorithm to compute DFT
(Discrete Fourier Transform). Fig.1 is the block diagram of eightpoints
FFT. Please note that adding, subtracting and multiplying are complex number
arithmetics.

Fig.1 Computes according to this regulation (CooleyTukey) 
w[n] is "twiddle factors" shown in Fig.2. a[n] is "timedomain
data" shown in Fig.3. In this case, w[n] is complex value, whereas
a[n] is real value.


Fig.2 Uses these twiddle factors. 
Fig.3 Inputs timedomain data. 
The following are explanation of FFT by using vector image. Please take
a look!!
How was my idea of explanation?? Please tell me your impression, question
or any suggestion.
email : 
iwata@digitalfilter.com 

