<< Chapter < Page Chapter >> Page >

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 [link] . That gives some indication of the age of research on the topic, and the fact that a1995 compiled bibliography [link] on efficient algorithms contains over 3400 entries indicates its volume. Three IEEE Pressreprint books contain papers on the FFT [link] , [link] , [link] . An excellent general purpose FFT program has been described in [link] , [link] and is used in Matlab and available over the internet.

In addition to this book there are several others [link] , [link] , [link] , [link] , [link] , [link] , [link] , [link] , [link] that give a good modern theoretical background for the FFT, one book [link] that gives the basic theory plus both FORTRAN and TMS 320 assembly language programs, and other books [link] , [link] , [link] that contain chapters on advanced FFT topics. A good up-to-date, on-line reference with both theory and programming techniques is in [link] . The history of the FFT isoutlined in [link] , [link] and excellent survey articles can be found in [link] , [link] . The foundation of much of the modern work on efficient algorithms was done by S. Winograd. These results can be found in [link] , [link] , [link] . An outline and discussion of his theorems can be found in [link] as well as [link] , [link] , [link] , [link] .

Efficient FFT algorithms for length- 2 M were described by Gauss and discovered in modern times by Cooley and Tukey [link] . These have been highly developed and good examples of FORTRAN programs canbe found in [link] . Several new algorithms have been published that require the least known amount of total arithmetic [link] , [link] , [link] , [link] , [link] , [link] . Of these, the split-radix FFT [link] , [link] , [link] , [link] seems to have the best structure for programming, and an efficient program has beenwritten [link] to implement it. A mixture of decimation-in-time and decimation-in-frequency with very goodefficiency is given in [link] , [link] and one called the Sine-Cosine FT [link] . Recently a modification to the split-radix algorithm has been described [link] that has a slightly better total arithmetic count. Theoretical bounds on the number ofmultiplications required for the FFT based on Winograd's theories are given in [link] , [link] . Schemes for calculating an in-place, in-order radix-2 FFT are given in [link] , [link] , [link] , [link] . Discussion of various forms of unscramblers is given in [link] , [link] , [link] , [link] , [link] , [link] , [link] , [link] , [link] . A discussion of the relation of the computer architecture, algorithmand compiler can be found in [link] , [link] . A modification to allow lengths of N = q 2 m for q odd is given in [link] .

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 PFAwas derived in [link] and further developed and an efficient in-order and in-place program given in [link] , [link] . More results on the PFA are given in [link] , [link] , [link] , [link] , [link] . A method has been developed to use dynamic programming to design optimal FFT programsthat minimize the number of additions and data transfers as well as multiplications [link] . This new approach designs custom algorithms for a particular computer architecture. An efficient andpractical development of Winograd's ideas has given a design method that does not require the rather difficult Chinese remainder theorem [link] , [link] for short prime length FFT's. These ideas have been used to design modules of length 11, 13, 17, 19, and 25 [link] . Other methods for designing short DFT's can be found in [link] , [link] . A use of these ideas with distributed arithmetic and table look-up rather than multiplication is given in [link] . A program that implements the nested Winograd Fourier transform algorithm (WFTA) is given in [link] but it has not proven as fast or as versatile as the PFA [link] . An interesting use of the PFA was announced [link] 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 thediscrete Hartley transform [link] , [link] and the discrete cosine transform [link] , [link] , [link] .

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-designedreal-data FFT [link] is always as good as or better than a well-designed Hartley transform [link] , [link] , [link] , [link] , [link] . The Bruun algorithm [link] , [link] also looks promising for real data applications as does the Rader-Brenner algorithm [link] , [link] , [link] . A novel approach to calculating the inverse DFT is given in [link] .

General length algorithms include [link] , [link] , [link] . For lengths that are not highly composite or prime, the chirp z-transform in agood candidate [link] , [link] for longer lengths and an efficient order- N 2 algorithm called the QFT [link] , [link] , [link] for shorter lengths. A method which automatically generates near-optimal prime lengthWinograd based programs has been given in [link] , [link] , [link] , [link] , [link] . This gives the same efficiency for shorter lengths (i.e. N 19 ) and new algorithms for much longer lengths and with well-structuredalgorithms. Another approach is given in [link] . Special methods are available for very long lengths [link] , [link] . A very interesting general length FFT systemcalled the FFTW has been developed by Frigo and Johnson at MIT. It uses a library of efficient “codelets" which are composed for a very efficientcalculation of the DFT on a wide variety of computers [link] , [link] , [link] . 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 [link] would seem to be more efficient, use of the FFT or PFA is still probably the fastest method on a general purpose computer or DSPchip [link] , [link] , [link] , [link] . On special purpose hardware or special architectures, the use of distributedarithmetic [link] or number theoretic transforms [link] may be even faster. Special algorithms for use with the short-time Fourier transform [link] and for the calculation of a few DFT values [link] , [link] , [link] and for recursive implementation [link] , [link] have also been developed. An excellent analysis of efficient programming the FFT on DSP microprocessors is given in [link] , [link] . Formulations of the DFT in terms of tensor or Kronecker products lookpromising for developing algorithms for parallel and vector computer architectures [link] , [link] , [link] , [link] , [link] , [link] , [link] .

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

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

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

Questions & Answers

How we are making nano material?
what is a peer
What is meant by 'nano scale'?
What is STMs full form?
scanning tunneling microscope
what is Nano technology ?
Bob Reply
write examples of Nano molecule?
The nanotechnology is as new science, to scale nanometric
nanotechnology is the study, desing, synthesis, manipulation and application of materials and functional systems through control of matter at nanoscale
Is there any normative that regulates the use of silver nanoparticles?
Damian Reply
what king of growth are you checking .?
What fields keep nano created devices from performing or assimulating ? Magnetic fields ? Are do they assimilate ?
Stoney Reply
why we need to study biomolecules, molecular biology in nanotechnology?
Adin Reply
yes I'm doing my masters in nanotechnology, we are being studying all these domains as well..
what school?
biomolecules are e building blocks of every organics and inorganic materials.
anyone know any internet site where one can find nanotechnology papers?
Damian Reply
sciencedirect big data base
Introduction about quantum dots in nanotechnology
Praveena Reply
what does nano mean?
Anassong Reply
nano basically means 10^(-9). nanometer is a unit to measure length.
do you think it's worthwhile in the long term to study the effects and possibilities of nanotechnology on viral treatment?
Damian Reply
absolutely yes
how to know photocatalytic properties of tio2 nanoparticles...what to do now
Akash Reply
it is a goid question and i want to know the answer as well
characteristics of micro business
for teaching engĺish at school how nano technology help us
How can I make nanorobot?
Do somebody tell me a best nano engineering book for beginners?
s. Reply
there is no specific books for beginners but there is book called principle of nanotechnology
how can I make nanorobot?
what is fullerene does it is used to make bukky balls
Devang Reply
are you nano engineer ?
fullerene is a bucky ball aka Carbon 60 molecule. It was name by the architect Fuller. He design the geodesic dome. it resembles a soccer ball.
what is the actual application of fullerenes nowadays?
That is a great question Damian. best way to answer that question is to Google it. there are hundreds of applications for buck minister fullerenes, from medical to aerospace. you can also find plenty of research papers that will give you great detail on the potential applications of fullerenes.
what is the Synthesis, properties,and applications of carbon nano chemistry
Abhijith Reply
Mostly, they use nano carbon for electronics and for materials to be strengthened.
is Bucky paper clear?
carbon nanotubes has various application in fuel cells membrane, current research on cancer drug,and in electronics MEMS and NEMS etc
how did you get the value of 2000N.What calculations are needed to arrive at it
Smarajit Reply
Privacy Information Security Software Version 1.1a
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

Get the best Algebra and trigonometry course in your pocket!

Source:  OpenStax, Fast fourier transforms. OpenStax CNX. Nov 18, 2012 Download for free at http://cnx.org/content/col10550/1.22
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Fast fourier transforms' conversation and receive update notifications?