Insight to FFT

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 eight-points FFT. Please note that adding, subtracting and multiplying are complex number arithmetics. 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 a look!! How is FFT computed in the butterflies I wrote some PDF documents to explain how the computation progresses on eight-points FFT. Why is FFT constructed like butterflies I wrote some PDFs to see the FFT taking the patterns of angle into account. How was my idea of explanation?? Please tell me your impression, question or any suggestion. e-mail : iwata@digitalfilter.com

FFT Laboratory

Top Page