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
FFT (Fast Fourier Transform) is very efficient algorithm to compute DFT
(Discrete Fourier Transform). Fig.1 is the block diagram of eight-points
FFT. Please note that adding, subtracting and multiplying are complex number
Fig.1 Computes according to this regulation (Cooley-Tukey)
w[n] is "twiddle factors" shown in Fig.2. a[n] is "time-domain
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 time-domain data.
The following are explanation of FFT by using vector image. Please take