אלגוריתם ה-FFT של קולי-טוקי
הערות שוליים

↑  Gauss, Carl Friedrich (1876). Theoria Interpolationis Methodo Nova Tractata. Carl Friedrich Gauss Werke. Vol. Band 3. Göttingen: Königliche Gesellschaft der Wissenschaften. pp. 265–327.
1 2 3 4 5  Heideman, M. T., D. H. Johnson, and C. S. Burrus, "Gauss and the history of the fast Fourier transform," IEEE ASSP Magazine, 1, (4), 14–21 (1984)
1 2 3 4 5  Cooley, James W.; Tukey, John W. (1965). "An algorithm for the machine calculation of complex Fourier series". Math. Comput. 19 (90): 297–301. doi:10.2307/2003354. JSTOR 2003354.
↑  Cooley, James W.; Lewis, Peter A. W.; Welch, Peter D. (1967). "Historical notes on the fast Fourier transform" (PDF). IEEE Transactions on Audio and Electroacoustics. 15 (2): 76–79. CiteSeerX 10.1.1.467.7209. doi:10.1109/tau.1967.1161903.
↑  Rockmore, Daniel N., Comput. Sci. Eng. 2 (1), 60 (2000). The FFT — an algorithm the whole family can use Special issue on "top ten algorithms of the century "Barry A. Cipra. "The Best of the 20th Century: Editors Name Top 10 Algorithms" (PDF). SIAM News. 33. אורכב מ-המקור (PDF) ב-2009-04-07. נבדק ב-2009-03-31.
↑  James W. Cooley, Peter A. W. Lewis, and Peter W. Welch, "Historical notes on the fast Fourier transform," Proc. IEEE, vol. 55 (no. 10), p. 1675–1677 (1967).
↑  Danielson, G. C., and C. Lanczos, "Some improvements in practical Fourier analysis and their application to X-ray scattering from liquids," J. Franklin Inst. 233, 365–380 and 435–452 (1942).
1 2  S. G. Johnson and M. Frigo, "Implementing FFTs in practice," in Fast Fourier Transforms (C. S. Burrus, ed.), ch. 11, Rice University, Houston TX: Connexions, September 2008.
↑  Singleton, Richard C. (1967). "On computing the fast Fourier transform". Commun. ACM. 10 (10): 647–654. doi:10.1145/363717.363771.
1 2  Duhamel, P., and M. Vetterli, "Fast Fourier transforms: a tutorial review and a state of the art," Signal Processing 19, 259–299 (1990)
↑  Lundy, T., and J. Van Buskirk, "A new matrix approach to real FFTs and convolutions of length 2k," Computing 80, 23–45 (2007).
↑  Johnson, S. G., and M. Frigo, "A modified split-radix FFT with fewer arithmetic operations," IEEE Trans. Signal Process. 55 (1), 111–119 (2007).
1 2  Frigo, M.; Johnson, S. G. (2005). "The Design and Implementation of FFTW3" (PDF). Proceedings of the IEEE. 93 (2): 216–231. CiteSeerX 10.1.1.66.3097. doi:10.1109/JPROC.2004.840301.
1 2  Gentleman W. M., and G. Sande, "Fast Fourier transforms—for fun and profit," Proc. AFIPS 29, 563–578 (1966).
1 2  Bailey, David H., "FFTs in external or hierarchical memory," J. Supercomputing 4 (1), 23–35 (1990)
1 2  M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS 99), p.285-297. 1999. Extended abstract at IEEE, at Citeseer.
↑  Cooley, J. W., P. Lewis and P. Welch, "The Fast Fourier Transform and its Applications", IEEE Trans on Education 12, 1, 28–34 (1969)
דיאגרמת זרימת נתונים עבור N =8. אלגוריתם ה-FFT מסוג radix-2 מפרק DFT באורך N לשני DFT באורך N/2 ולאחר מכן משלב מספר DFT באורך 2 הנקראים פעולות "פרפר" (מקור השם בצורה של דיאגרמות זרימת הנתונים).
ניתן לראות את הצעד הבסיסי של קולי-טוקי FFT כפירוש מחדש של DFT חד־ממדי כדומה ל-DFT דו־ממדי. מערך הקלט החד־ממדי באורך N=N1N2 מפורש מחדש כמטריצת N1×N2 המאוחסנת בסדר עמודה ראשי. אנו מחשבים DFT קטנים יותר לאורך כיוון N2 (הכיוון הלא רציף), ואז מכפילים בגורמי סיבוב (Twiddle factors), ולבסוף מחשבים DFT לאורך כיוון N1. ניתן לבצע את שלב השחלוף (transposition) באמצע, כמוצג כאן, או בהתחלה או בסוף. התהליך הזה הוא רקורסיבי.
איור של סדר עיקרי בשורה ובעמודה