<< Chapter < Page Chapter >> Page >

Efficient computation of the fast Fourier transform (FFT) requires an understanding of the computation at every level of abstraction, from the high-levelalgorithmic view down to the low-level details of the target machine (or failing that, a lot of time to code all known FFT algorithms andexhaustively search the configuration space). This chapter provides an overview of FFT from the mathematical perspective.

Fast Fourier transform algorithms are derived from the discrete Fourier transform (DFT), which is formally defined as  [link] :

X k = n = 0 N - 1 ω N n k x n

where k = 0 , , N - 1 and ω N is the primitive root-of-unity, defined as e - 2 π - 1 / N (often referred to as a “twiddle factor” in the context of fast Fourier transforms). X k and x n are sequences of complex numbers, X k being the outputs in the frequency domain, and x n being the inputs in the time or space domain.

A source of mild confusion in the FFT literature is the sign of the twiddle factor  [link] ; the definition in [link] is considered to be the engineers view of the discrete Fourier transform, where the goal is tocompute the coefficients of a discrete Fourier series. Mathematicians, on the other hand, typically view the DFT as a method of evaluating a polynomial atthe powers of a primitive root of unity, and thus consider [link] to be an inverse DFT  [link] . Cooley and Tukey  [link] , Fiduccia  [link] and Bernstein  [link] are notable examples of those who adopt the mathematicians convention. This work adopts the engineer's view of a DFT, and thus the inverse discrete Fourier transform (IDFT) is defined by the following equation:

x n = 1 N k = 0 N - 1 ω N - n k X k

where n = 0 , , N - 1 . It should be noted that in some implementations, such as FFTW and the implementation presented in this thesis, the IDFT is actually non-normalised for reasons of efficiency; i.e., I F F T ( F F T ( x ) ) = N x , thus avoiding division of each of the samples in time by N  [link] .

Cooley-tukey

In 1965 James Cooley and John Tukey published a description of an economical algorithm for computing the DFT that becameknown as the Cooley-Tukey FFT, or simply the FFT due to its overwhelming popularity  [link] . A later investigation by Heideman, Johnson and Burrus  [link] revealed that the algorithm had actually been discovered several times in various forms prior to Cooley andTukey, most notably by Gauss sometime around 1805  [link] .

The algorithm recursively divides a transform of size N = N 1 N 2 into smaller DFTs of size N 1 and N 2 (where N is highly composite), reducing the time complexity from O( n 2 ) to O( n log n ) by exploiting common factors.

As the algorithm recursively divides a DFT, either N 1 or N 2 is typically a small factor, and is known as the radix. Small N 1 characterizes the algorithm as being decimation-in-time (DIT), otherwisethe algorithm is decimation-in-frequency (DIF). If the radix changes between stages, then the algorithm is referred to as `mixed-radix'.

For example, a radix-2 decimation-in-time algorithm decomposes [link] into a sum over the even indices ( n = 2 n 2 ) and a sum over the odd indices ( n = 2 n 2 + 1 ):

X k = n 2 = 0 N / 2 - 1 ω N ( 2 n 2 ) k x 2 n 2 + n 2 = 0 N / 2 - 1 ω N ( 2 n 2 + 1 ) k x 2 n 2 + 1

The trigonometric coefficient in the second sum can be expanded to ω N 2 n 2 k ω N k , and the term now common to both sums is simplified using the identity ω N m n k = ω N / m n k . Because one of the trigonometric coefficients in the second sum is constant with respect to the index variable, it may be factored out toobtain:

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Computing the fast fourier transform on simd microprocessors. OpenStax CNX. Jul 15, 2012 Download for free at http://cnx.org/content/col11438/1.2
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Computing the fast fourier transform on simd microprocessors' conversation and receive update notifications?

Ask