Skip to content Skip to navigation

OpenStax-CNX

You are here: Home » Content » Comments: Fast Fourier Transforms

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Rice Digital Scholarship

    This module is included in aLens by: Digital Scholarship at Rice UniversityAs a part of collections: "Fast Fourier Transforms", "Fast Fourier Transforms (6x9 Version)"

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

  • NSF Partnership display tagshide tags

    This module is included inLens: NSF Partnership in Signal Processing
    By: Sidney BurrusAs a part of collection: "Fast Fourier Transforms"

    Click the "NSF Partnership" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Featured Content display tagshide tags

    This module is included inLens: Connexions Featured Content
    By: ConnexionsAs a part of collection: "Fast Fourier Transforms"

    Comments:

    "The Fast Fourier Transform (FFT) is a landmark algorithm used in fields ranging from signal processing to high-performance computing. First popularized by two American scientists in 1965, the […]"

    Click the "Featured Content" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

Also in these lenses

  • UniqU content

    This module is included inLens: UniqU's lens
    By: UniqU, LLCAs a part of collection: "Fast Fourier Transforms"

    Click the "UniqU content" link to see all content selected in this lens.

  • Lens for Engineering

    This module is included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Comments: Fast Fourier Transforms

Module by: C. Sidney Burrus. E-mail the author

Other work and Results

This section comes from a note describing results on efficient algorithms to calculate the discrete Fourier transform (DFT) that were collected over years. Perhaps the most interesting is the discovery that the Cooley-Tukey FFT was described by Gauss in 1805 [46]. That gives some indication of the age of research on the topic, and the fact that a 1995 compiled bibliography [88] on efficient algorithms contains over 3400 entries indicates its volume. Three IEEE Press reprint books contain papers on the FFT [74], [24], [25]. An excellent general purpose FFT program has been described in [34], [35] and is used in Matlab and available over the internet.

In addition to this book there are several others [60], [65], [10], [44], [102], [64], [11], [9], [97] that give a good modern theoretical background for the FFT, one book [12] that gives the basic theory plus both FORTRAN and TMS 320 assembly language programs, and other books [57], [84], [15] that contain chapters on advanced FFT topics. A good up-to-date, on-line reference with both theory and programming techniques is in [3]. The history of the FFT is outlined in [21], [46] and excellent survey articles can be found in [30], [20]. The foundation of much of the modern work on efficient algorithms was done by S. Winograd. These results can be found in [115], [116], [117]. An outline and discussion of his theorems can be found in [57] as well as [60], [65], [10], [44].

Efficient FFT algorithms for length-2M2M were described by Gauss and discovered in modern times by Cooley and Tukey [22]. These have been highly developed and good examples of FORTRAN programs can be found in [12]. Several new algorithms have been published that require the least known amount of total arithmetic [119], [26], [28], [58], [112], [17]. Of these, the split-radix FFT [26], [28], [111], [100] seems to have the best structure for programming, and an efficient program has been written [90] to implement it. A mixture of decimation-in-time and decimation-in-frequency with very good efficiency is given in [77], [78] and one called the Sine-Cosine FT [17]. Recently a modification to the split-radix algorithm has been described [52] that has a slightly better total arithmetic count. Theoretical bounds on the number of multiplications required for the FFT based on Winograd's theories are given in [44], [43]. Schemes for calculating an in-place, in-order radix-2 FFT are given in [7], [6], [50], [107]. Discussion of various forms of unscramblers is given in [16], [69], [54], [31], [73], [114], [120], [79], [71]. A discussion of the relation of the computer architecture, algorithm and compiler can be found in [59], [62]. A modification to allow lengths of N=q2mN=q2m for qq odd is given in [4].

The “other” FFT is the prime factor algorithm (PFA) which uses an index map originally developed by Thomas and by Good. The theory of the PFA was derived in [55] and further developed and an efficient in-order and in-place program given in [5], [12]. More results on the PFA are given in [105], [106], [107], [108], [98]. A method has been developed to use dynamic programming to design optimal FFT programs that minimize the number of additions and data transfers as well as multiplications [49]. This new approach designs custom algorithms for a particular computer architecture. An efficient and practical development of Winograd's ideas has given a design method that does not require the rather difficult Chinese remainder theorem [57], [51] for short prime length FFT's. These ideas have been used to design modules of length 11, 13, 17, 19, and 25 [48]. Other methods for designing short DFT's can be found in [104], [56]. A use of these ideas with distributed arithmetic and table look-up rather than multiplication is given in [18]. A program that implements the nested Winograd Fourier transform algorithm (WFTA) is given in [60] but it has not proven as fast or as versatile as the PFA [5]. An interesting use of the PFA was announced [19] in searching for large prime numbers.

These efficient algorithms can not only be used on DFT's but on other transforms with a similar structure. They have been applied to the discrete Hartley transform [93], [13] and the discrete cosine transform [112], [118], [76].

The fast Hartley transform has been proposed as a superior method for real data analysis but that has been shown not to be the case. A well-designed real-data FFT [94] is always as good as or better than a well-designed Hartley transform [93], [29], [68], [109], [80]. The Bruun algorithm [14], [101] also looks promising for real data applications as does the Rader-Brenner algorithm [70], [23], [109]. A novel approach to calculating the inverse DFT is given in [27].

General length algorithms include [91], [40], [32]. For lengths that are not highly composite or prime, the chirp z-transform in a good candidate [12], [75] for longer lengths and an efficient order-N2N2 algorithm called the QFT [92], [41], [42] for shorter lengths. A method which automatically generates near-optimal prime length Winograd based programs has been given in [51], [82], [85], [86], [87]. This gives the same efficiency for shorter lengths (i.e. N19N19) and new algorithms for much longer lengths and with well-structured algorithms. Another approach is given in [67]. Special methods are available for very long lengths [47], [99]. A very interesting general length FFT system called the FFTW has been developed by Frigo and Johnson at MIT. It uses a library of efficient “codelets" which are composed for a very efficient calculation of the DFT on a wide variety of computers [34], [35], [33]. For most lengths and on most computers, this is the fastest FFT today. Surprisingly, it uses a recursive program structure. The FFTW won the 1999 Wilkinson Prize for Numerical Software.

The use of the FFT to calculate discrete convolution was one of its earliest uses. Although the more direct rectangular transform [2] would seem to be more efficient, use of the FFT or PFA is still probably the fastest method on a general purpose computer or DSP chip [66], [94], [29], [61]. On special purpose hardware or special architectures, the use of distributed arithmetic [18] or number theoretic transforms [1] may be even faster. Special algorithms for use with the short-time Fourier transform [81] and for the calculation of a few DFT values [89], [72], [83] and for recursive implementation [113], [35] have also been developed. An excellent analysis of efficient programming the FFT on DSP microprocessors is given in [63], [62]. Formulations of the DFT in terms of tensor or Kronecker products look promising for developing algorithms for parallel and vector computer architectures [95], [102], [53], [110], [103], [39], [38].

Various approaches to calculating approximate DFTs have been based on cordic methods, short word lengths, or some form of pruning. A new method that uses the characteristics of the signals being transformed has combined the discrete wavelet transform (DWT) combined with the DFT to give an approximate FFT with O(N)O(N) multiplications [36], [37], [8] for certain signal classes. A similar approach has been developed using filter banks [96], [45].

The study of efficient algorithms not only has a long history and large bibliography, it is still an exciting research field where new results are used in practical applications.

More information can be found on the Rice DSP Group's web page

References

  1. Agarwal, R. C. and Burrus, C. S. (1975, April). Number Theoretic Transforms to Implement Fast Digital Convolution. [also in IEEE Press DSP Reprints II, 1979]. Proceedings of the IEEE, 63(4), 550–560.
  2. Agarwal, R. C. and Cooley, J. W. (1977, October). New Algorithms for Digital Convolution. IEEE Trans. on ASSP, 25(2), 392–410.
  3. Arndt, Jörg. (2008). Algorithms for Programmers: Ideas and Source Code. [FFT book available on-line, 1000 pages, continually updated]. Bayreuth, Germany: http://www.jjj.de/fxt/.
  4. Bi, Guoan and Chen, Yan Qiu. (1998, June). Fast DFT Algorithms for Length. IEEE Transactions on Circuits and Systems – II, 45(6), 685–690.
  5. Burrus, C. S. and Eschenbacher, P. W. (1981, August). An In–Place, In–Order Prime Factor FFT Algorithm. [Reprinted in it DSP Software, by L.R. Morris, 1983]. IEEE Transactions on Acoustics, Speech, and Signal Processing, 29(4), 806–817.
  6. Beard, James K. (2003). The FFT in the 21st Century: Eigenspace Processing. Boston: Kluwer.
  7. Beard, James K. (1978, April). An In-Place, Self-Reordering FFT. In Proceedings of the ICASSP-78. (pp. 632-633). Tulsa
  8. Burrus, C. Sidney and Gopinath, Ramesh A. and Guo, Haitao. (1998). Introduction to Wavelets and the Wavelet Transform. Upper Saddle River, NJ: Prentice Hall.
  9. Briggs, William L. and Henson, Van Emden. (1995). The DFT: An Owner's Manual for the Discrete Fourier Transform. Philadelphia: SIAM.
  10. Blahut, R. E. (1984). Fast Algorithms for Digital Signal Processing. Reading, MA: Addison-Wesley, Inc.
  11. Blahut, Richard E. (1992). Algebraic Methods for Signal Processing and Communications Coding. New York: Springer-Verlag.
  12. Burrus, C. S. and Parks, T. W. (1985). DFT/FFT and Convolution Algorithms. New York: John Wiley & Sons.
  13. Bracewell, R. N. (1986). The Hartley Transform. Oxford Press.
  14. Bruun, G. (1978, February). z-Transform DFT Filters and FFTs. IEEE Transactions on ASSP, 26(1), 56–63.
  15. Burrus, C. Sidney and Selesnick, Ivan W. (1998). Fast Convolution and Filtering. In Madisetti, V. K. and Williams, D. B. (Eds.), The Digital Signal Processing Handbook. Boca Raton: CRC Press.
  16. Burrus, C. S. (1988, July). Unscrambling for Fast DFT Algorithms. IEEE Transactions on Acoustics, Speech, and Signal Processing, 36(7), 1086–1087.
  17. Byam, Iain R. (1999, June). A New Fast Fourier Transform Algorithm. [A short version is in Technical Report PG-99001, ECE Dept., Univ. of the West Indies, Aug. 1999]. Technical report. University of the West Indies (UWI), St. Augustine, Trinidad.
  18. Chu, Shuni and Burrus, C. S. (1982, April). A Prime Factor FFT Algorithm using Distributed Arithmetic. IEEE Transactions on Acoustics, Speech, and Signal Processing, 30(2), 217–227.
  19. Chen, K. T. (1990, February). A New Record: The Largest Known Prime Number. IEEE Spectrum, 27(2), 47.
  20. Cooley, James W. (1990, April). The Structure of FFT Algorithms. [Notes for a Tutorial at IEEE ICASSP-90].
  21. Cooley, J. W. (1992, January). How the FFT Gained Acceptance. [Also presented at the ACM Conference on the History of Scientific and Numerical Computation, Princeton, NJ, May 1987 and published in: A History of Scientific Computing, edited by S. G. Nash, Addison-Wesley, 1990, pp. 133-140.]. IEEE Signal Processing Magazine, 9(1), 10–13.
  22. Cooley, J. W. and Tukey, J. W. (1965). An Algorithm for the Machine Calculation of Complex Fourier Series. Math. Computat., 19, 297–301.
  23. Cho, K. M. and Temes, G. C. (1978, April). Real-factor FFT Algorithms. In Proceedings of IEEE ICASSP-78. (pp. 634-637). Tulsa, OK
  24. DSP Committee, (Ed.). (1979). Digital Signal Processing II, selected reprints. New York: IEEE Press.
  25. DSP Committee, (Ed.). (1979). Programs for Digital Signal Processing. New York: IEEE Press.
  26. Duhamel, P. and Hollmann, H. (1984, January 5). Split Radix FFT Algorithm. Electronic Letters, 20(1), 14–16.
  27. Duhamel, P. and Piron, B. and Etcheto, J. M. (1978, February). On Computing the Inverse DFT. IEEE Transactions on ASSP, 36(2), 285–286.
  28. Duhamel, P. (1986, April). Implementation of `Split-Radix' FFT Algorithms for Complex, Real, and Real-Symmetric Data. [A shorter version appeared in the ICASSP-85 Proceedings, p. 20.6, March 1985]. IEEE Trans. on ASSP, 34, 285–295.
  29. Duhamel, P. and Vetterli, M. (1987, June). Improved Fourier and Hartley Transfrom Algorithms, Application to Cyclic Convolution of Real Data. IEEE Trans. on ASSP, 35(6), 818–824.
  30. Duhamel, P. and Vetterli, M. (1990, April). Fast Fourier Transforms: A Tutorial Review and a State of the Art. Signal Processing, 19(4), 259–299.
  31. Evans, D. M. W. (1989, August). A Second Improved Digit–Reversal Permutation Algorithm for Fast Transforms. IEEE Transactions on Acoustics, Speech, and Signal Processing, 37(8), 1288–1291.
  32. Ferguson, Jr., W. E. (1982). A Simple Derivation of Glassman General-N Fast Fourier Transform. [Also, in Report AD-A083811, NTIS, Dec. 1979]. Comput. and Math. with Appls., 8(6), 401–411.
  33. Frigo, Matteo and Johnson, Steven G. (2005, February). The Design and Implementtion of FFTW. Proceedings of the IEEE, 93(2), 216–231.
  34. Frigo, Matteo and Johnson, Steven G. (1998, May 12–15). FFTW: An Adaptive Software Architecture for the FFT. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. (Vol. III, p. 1381–1384). ICASSP-98, Seattle
  35. Frigo, Matteo. (1999, May). A Fast Fourier Transform Compiler. In Proceedings of the 1999 ACM SIGPLAN Conference on Programming Language Design and Implentation. PLDI-99, Atlanta
  36. Guo, Haitao and Burrus, C. Sidney. (1996, August 6–9). Approximate FFT via the Discrete Wavelet Transform. In Proceedings of SPIE Conference 2825. Denver
  37. Guo, Haitao and Burrus, C. Sidney. (1997, April 21–24). Wavelet Transform Based Fast Approximate Fourier Transform. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. (Vol. 3, p. III:1973–1976). IEEE ICASSP-97, Munich
  38. Granata, John and Conner, Michael and Tolimieri, Richard. (1992, December). Recursive Fast Algorithms and the Role of the Tensor Product. IEEE Transactions on Signal Processing, 40(12), 2921–2930.
  39. Granata, John and Conner, Michael and Tolimieri, Richard. (1992, January). The Tensor Product: A Mathematical Programming Language for FFTs. IEEE Signal Processing Magazine, 9(1), 40–48.
  40. Glassman, J. A. (1970, Feburary). A Generalization of the Fast Fourier Transform. IEEE Transactions on Computers, C-19(2), 105–116.
  41. Guo, H. and Sitton, G. A. and Burrus, C. S. (1994, April 19–22). The Quick Discrete Fourier Transform. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. (p. III:445–448). IEEE ICASSP-94, Adelaide, Australia
  42. Guo, H. and Sitton, G. A. and Burrus, C. S. (1998, February). The Quick Fourier Transform: an FFT based on Symmetries. IEEE Transactions on Signal Processing, 46(2), 335–341.
  43. Heideman, M. T. and Burrus, C. S. (1986, February). On the Number of Multiplications Necessary to Compute a Length- DFT. IEEE Transactions on Acoustics, Speech, and Signal Processing, 34(1), 91–95.
  44. Heideman, M. T. (1988). Multiplicative Complexity, Convolution, and the DFT. Springer–Verlag.
  45. Hossen, A. N. and Heute, U. and Shentov, O. V. and Mitra, S. K. (1995). Subband DFT – Part II: Accuracy, Complexity, and Applications. Signal Processing, 41, 279–295.
  46. Heideman, M. T. and Johnson, D. H. and Burrus, C. S. (1984, October). Gauss and the History of the FFT. [also in Archive for History of Exact Sciences, 1985]. IEEE Acoustics, Speech, and Signal Processing Magazine, 1(4), 14–21.
  47. Hocking, W. K. (1989, January). Performing Fourier Transforms on Extremely Long Data Streams. Computers in Physics, 3(1), 59–65.
  48. Johnson, H. W. and Burrus, C. S. (1981). Large DFT Modules: N = 11, 13, 17, 19, and 25. (8105). Technical report. Department of Electrical Engineering, Rice University, Houston, TX 77251–1892.
  49. Johnson, H. W. and Burrus, C. S. (1983, April). The Design of Optimal DFT Algorithms Using Dynamic Programming. IEEE Transactions on Acoustics, Speech, and Signal Processing, 31(2), 378–387.
  50. Johnson, H. W. and Burrus, C. S. (1984, March). An In-Place, In-Order Radix-2 FFT. In ICASSP-84 Proceedings. (p. 28A.2).
  51. Johnson, Howard W. and Burrus, C. S. (1985, February). On the Structure of Efficient DFT Algorithms. IEEE Transactions on Acoustics, Speech, and Signal Processing, 33(1), 248–254.
  52. Johnson, Steven G. and Frigo, Matteo. (2007, January). A Modified Split-Radix FFT with Fewer Arithmetic Operations. IEEE Transactions on Signal Processing, 55(1), 111–119.
  53. Johnson, J. and Johnson, R. W. and Rodriguez, D. and Tolimieri, R. (1990). A Methodology for Designing, Modifying, and Implementing Fourier Transform Algorithms on Various Architectures. Circuits, Systems and Signal Processing, 9(4), 449–500.
  54. Jeong, Jechang and Williams, William J. (1990, April). A Fast Recursive Bit-Reversal Algorithm. In Proceedings of the ICASSP-90. (p. 1511–1514). Albuquerque, NM
  55. Kolba, D. P. and Parks, T. W. (1977, August). A Prime Factor FFT Algorithm Using High Speed Convolution. [also in]. IEEE Trans. on ASSP, 25, 281–294.
  56. Lu, Chao and Cooley, James W. and Tolimieri, Richard. (1993, February). FFT Algorithms for Prime Transform Sizes and their Implementations on VAX, IBM3090VF, and IBM RS/6000. IEEE Transactions on Signal Processing, 41(2), 638–648.
  57. Lim, Jae S. and Oppenheim, A. V. (1988). 4. Advanced Topics in Signal Processing. Prentice-Hall.
  58. Martens, J. B. (1984, August). Recursive Cyclotomic Factorization – A New Algorithm for Calculating the Discrete Fourier Transform. IEEE Trans. on ASSP, 32(4), 750–762.
  59. Morris, L. R. (1982, 1983). Digital Signal Processing Software. Toronto, Canada: DSPSW, Inc.
  60. McClellan, J. H. and Rader, C. M. (1979). Number Theory in Digital Signal Processing. Englewood Cliffs, NJ: Prentice-Hall, Inc.
  61. Meyer, R. and Reng, R. and Schwarz, K. (1991, May). Convolution Algorithms on DSP Processors. In Proceedings of the ICASSP-91. (p. 2193–2196). Toronto, Canada
  62. Meyer, R. and Schwarz, K. (1990, Sept. 18). FFT Implementation on DSP-Chips. [preprint].
  63. Meyer, R. and Schwarz, K. and Schuessler, H. W. (1990, April). FFT Implementation on DSP-Chips — Theory and Practice. In Proceedings of the ICASSP-90. (p. 1503–1506). Albuquerque, NM
  64. Myers, Douglas G. (1990). Digital Signal Processing, Efficient Convolution and Fourier Transform Techniques. Sydney, Australia: Prentice-Hall.
  65. Nussbaumer, H. J. (1981, 1982). Fast Fourier Transform and Convolution Algorithms. (Second). Heidelberg, Germany: Springer-Verlag.
  66. Pitas, I. and Burrus, C. S. (1983, March). Time and Error Analysis of Digital Convolution by Rectangular Transforms. Signal Processing, 5(2), 153–162.
  67. Perez, F. and Takaoka, T. (1987, August). A Prime Factor FFT Algorithm Implementation Using a Program Generation Technique. IEEE Transactions on Acoustics, Speech and Signal Processing, 35, 1221–1223.
  68. Popović, Miodrag and Šević, Dragutin. (1994, August). A New Look at the comparison of the Fast Hartley and Fourier Transforms. IEEE Transactions on Signal Processing, 42(8), 2178–2182.
  69. Rösel, Petr. (1989, December). Timing of Some Bit Reversal Algorithms. Signal Processing, 18(4), 425–433.
  70. Rader, C. M. and Brenner, N. M. (1976, June). A New Principle for Fast Fourier Transformation. IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-24(3), 264-266.
  71. Rius, J. M. and De Porrata-Dòria, R. (1995, April). New FFT Bit-Reversal Algorithm. IEEE Transactions on Signal Processing, 43(4), 991–994.
  72. Roche, Christian. (1992, May). A Split–Radix Partial Input/Output Fast Fourier Transform Algorithm. IEEE Transactions on Signal Processing, 40(5), 1273–1276.
  73. Rodríguez, J. J. (1989, August). An Improved FFT Digit–Reversal Algorithm. IEEE Transactions on Acoustics, Speech, and Signal Processing, 37(8), 1298–1300.
  74. Rabiner, L. R. and Rader, C. M. (Eds.). (1972). Digital Signal Processing, selected reprints. New York: IEEE Press.
  75. Rabiner, L.R. and Schafer, R.W. and Rader, C.M. (1969, June). The Chirp Z-Transform Algorithm. IEEE Transactions on Audio Electroacoustics, AU-17, 86–92.
  76. Rao, K. R. and Yip, P. (1990). Discrete Cosine Transform: Algorithms, Advantages, Applications. San Diego, CA: Academic Press.
  77. Saidi, Ali. (1994, April 19–22). Decimation-in-Time-Frequency FFT Algorithm. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. (Vol. 3, p. III:453–456). IEEE ICASSP-94, Adelaide, Australia
  78. Saidi, Ali. (1996). Decimation-in-Time-Frequency FFT Algorithm. [manuscript].
  79. Sundararajan, D. and Ahamad, M. O. and Swamy, M. N. S. (1994, October). A Fast FFT Bit-Reversal Algorithm. IEEE Transactions on Circuits and Systems, II, 41(10), 701–703.
  80. Sundararajan, D. and Ahmad, M. O. and Swamy, M. N. S. (1997, August). Fast Computations of the Discrete Fourier Transform of Real Data. IEEE Transactions on Signal Processing, 45(8), 2010–2022.
  81. Sorensen, H. V. and Burrus, C. S. (1988, April). Efficient Computation of the Short-Time FFT. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. (pp. 1894-1897). New York
  82. Selesnick, I. W. and Burrus, C. S. (1992, May). Automating the Design of Prime Length FFT Programs. In Proceedings of the IEEE International Symposium on Circuits and Systems. (Vol. 1, p. 133–136). ISCAS-92, San Diego, CA
  83. Sorensen, H. V. and Burrus, C. S. (1993, March). Efficient Computation of the DFT with Only a Subset of Input or Output Points. IEEE Transactions on Signal Processing, 41(3), 1184–1200.
  84. Sorensen, H. V. and Burrus, C. S. (1993). Fast DFT and Convolution Algorithms. In Mitra, Sanjit K. and Kaiser, James F. (Eds.), Handbook for Digital Signal Processing. New York: John Wiley & Sons.
  85. Selesnick, I. W. and Burrus, C. S. (1993, April). Multidimensional Mapping Techniques for Convolution. In Proceedings of the IEEE International Conference on Signal Processing. (Vol. III, pp. III-288–291). IEEE ICASSP-93, Minneapolis
  86. Selesnick, I. W. and Burrus, C. S. (1994, June 30). Extending Winograd's Small Convolution Algorithm to Longer Lengths. In Proceedings of the IEEE International Symposium on Circuits and Systems. (Vol. 2, p. 2.449–452). IEEE ISCAS-94, London
  87. Selesnick, Ivan W. and Burrus, C. Sidney. (1996, January). Automatic Generation of Prime Length FFT Programs. IEEE Transactions on Signal Processing, 44(1), 14–24.
  88. Sorensen, Henrik V. and Burrus, C. Sidney and Heideman, Michael T. (1995). Fast Fourier Transform Database. Boston: PWS Publishing.
  89. Sorensen, H. V. and Burrus, C. S. and Jones, D. L. (1988, June). A New Efficient Algorithm for Computing a Few DFT Points. In Proceedings of the IEEE International Symposium on Circuits and Systems. (p. 1915–1918). Espoo, Finland
  90. Sorensen, H. V. and Heideman, M. T. and Burrus, C. S. (1986, February). On Computing the Split–Radix FFT. IEEE Transactions on Acoustics, Speech, and Signal Processing, 34(1), 152–156.
  91. Singleton, R.C. (1969, June). An Algorithm for Computing the Mixed Radix Fast Fourier Transform. IEEE Transactions on Audio and Electroacoustics, AU-17, 93-103.
  92. Sitton, G. A. (1985). The QFT Algorithm.
  93. Sorensen, H. V. and Jones, D. L. and Burrus, C. S. and Heideman, M. T. (1985, October). On Computing the Discrete Hartley Transform. IEEE Transactions on Acoustics, Speech, and Signal Processing, 33(5), 1231–1238.
  94. Sorensen, H. V. and Jones, D. L. and Heideman, M. T. and Burrus, C. S. (1987, June). Real Valued Fast Fourier Transform Algorithms. IEEE Transactions on Acoustics, Speech, and Signal Processing, 35(6), 849–863.
  95. Sorensen, H. V. and Katz, C. A. and Burrus, C. S. (1990, April). Efficient FFT Algorithms for DSP Processors Using Tensor Product Decomposition. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. (p. 1507–1510). Albuquerque, NM
  96. Shentov, O. V. and Mitra, S. K. and Heute, U. and Hossen, A. N. (1995). Subband DFT – Part I: Definition, Interpretation and Extensions. Signal Processing, 41, 261–278.
  97. Smith, Winthrop W. and Smith, Joanne M. (1995). Handbook of Real-Time Fast Fourier Transforms. New York: IEEE Press.
  98. Stasiński, R. (1987). Prime Factor DFT Algorithms for New Small-N DFT Modules. IEE Proceedings, Part G, 134(3), 117–126.
  99. Stasiński, R. (1990). Extending Sizes of Effective Convolution Algorithms. Electronics Letters, 26(19), 1602–1604.
  100. Stasiński, Ryszard. (1991, May). The Techniques of the Generalized Fast Fourier Transform Algorithm. IEEE Transactions on Signal Processing, 39(5), 1058–1069.
  101. Storn, R. (1992). On the Bruun Algorithm and its Inverse. [a German journal]. Frequenz, 46, 110–116.
  102. Tolimieri, Richard and An, Myoung and Lu, Chao. (1989, 1997). Algorithms for Discrete Fourier Transform and Convolution. (second). New York: Springer-Verlag.
  103. Tolimieri, Richard and An, Myoung and Lu, Chao. (1993, 1997). Mathematics of Multidimensional Fourier Transform Algorithms. (second). New York: Springer-Verlag.
  104. Temperton, Clive. (1988). A New Set of Minimum-Add Small-N Rotated DFT Modules. Journal of Computational Physics, 75, 190–198.
  105. Temperton, Clive. (1988). A Self-Sorting In-Place Prime Factor Real/Half-Complex FFT Algorithm. Journal of Computational Physics, 75, 199–216.
  106. Temperton, Clive. (1989, June). Nesting Strategies for Prime Factor FFT Algorithms. Journal of Computational Physics, 82(2), 247–268.
  107. Temperton, Clive. (1991). Self-Sorting In-Place Fast Fourier Transforms. SIAM Journal of Sci. Statist. Comput., 12(4), 808–823.
  108. Temperton, Clive. (1992, May). A Generalized Prime Factor FFT Algorithm for any. SIAM Journal of Scientific and Statistical Computing, 13, 676–686.
  109. Uniyal, P. R. (1994, November). Transforming Real-Valued Sequences: Fast Fourier versus Fast Hartley Transform Algorithms. IEEE Transactions on Signal Processing, 42(11), 3249–3254.
  110. Van Loan, Charles. (1992). Matrix Frameworks for the Fast Fourier Transform. Philadelphia, PA: SIAM.
  111. Vetterli, Martin and Duhamel, P. (1989, January). Split-Radix Algorithms for Length -   DFT's. [Also, ICASSP-88 Proceedings, pp. 1415–1418, April 1988]. IEEE Trans. on ASSP, 37(1), 57–64.
  112. Vetterli, Martin and Nussbaumer, H. J. (1984, August). Simple FFT and DCT Algorithms with Reduced Number of Operations. Signal Processing, 6(4), 267–278.
  113. Várkonyi-Kóczy, A. R. (1995, September). A Recursive Fast Fourier Transformation Algorithm. IEEE Transactions on Circuits and Systems, II, 42(9), 614–616.
  114. Walker, J. S. (1990, August). A New Bit Reversal Algorithm. IEEE Transactions on Acoustics, Speech, and Signal Processing, 38(8), 1472–1473.
  115. Winograd, S. (1978, January). On Computing the Discrete Fourier Transform. Mathematics of Computation, 32, 175–199.
  116. Winograd, S. (1979, May). On the Multiplicative Complexity of the Discrete Fourier Transform. [also in]. Advances in Mathematics, 32(2), 83–117.
  117. Winograd, S. (1980). SIAM CBMS-NSF Series, No. 33: Arithmetic Complexity of Computation. Philadelphia: SIAM.
  118. Wang, Fang Ming and Yip, P. (1989). Fast Prime Factor Decomposition Algorithms for a Family of Discrete Trigonometric Transforms. Circuits, Systems, and Signal Processing, 8(4), 401–419.
  119. Yavne, R. (1968). An Economical Method for Calculating the Discrete Fourier Transform. In Fall Joint Computer Conference, AFIPS Conference Proceedings. (Vol. 33 part 1, p. 115–125).
  120. Yong, Angelo A. (1991, October). A Better FFT Bit-Reversal Algorithm without Tables. IEEE Transactions on Signal Processing, 39(10), 2365–2367.

Content actions

Download module as:

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks