Skip to content Skip to navigation

Connexions

You are here: Home » Content » Fast fourier transform (FFT)

Navigation

Content Actions
  • Download module PDF
  • Add to ...
    Add the module to:
    • My Favorites
    • A lens
    • An external social bookmarking service
    • My Favorites (What is 'My Favorites'?)
      'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.
    • A lens (What is a lens?)

      Definition of a lens

      Lenses

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

      What is in a lens?

      Lens makers point to Connexions 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 Connexions member, a community, or a respected organization.

    • External bookmarks
  • E-mail the author

Recently Viewed

This feature requires Javascript to be enabled.

Fast fourier transform (FFT)

Module by: Richard Baraniuk

The fast fourier transform is an efficient computational algorithm for the DFT. The DFT can be expensive to compute,

∀k,0≤k≤N-1:Xk=∑n=0N-1Xkⅇⅈ2πNkn k 0 k N 1 X k n 0 N 1 X k 2 N k n (1)
For each kk, we must execute: NN complex multiplications and N-1 N 1 complex additions. There are NN kk values, which means that the total cost of direct computations of a DFT is N2 N 2 complex multiplications and N2-N N 2 N complex adds.

Exercise 1

How many multiplies and adds are there for reals numbers?

This O( N2 N 2 ) computation readily gets out of hand as NN gets large. This is illustrated by Figure 1 and Table 1:

Figure 1
Figure 1 (FFT1.png)
N N N2 N 2
1 1
10 100
100 10000
1000 106 10 6
106 10 6 1012 10 12
The FFT is an efficient algorithm for computing the DFT. Efficient? We will see that it requires only O( NlogN N N ) coputations to compute NN DFT samples. This is illustrated in Figure 2 and Table 2:
Figure 2
Figure 2 (FFT2.png)
N N N2 N 2 Nlog10N N 10 N
10 100 1
100 10000 200
1000 106 10 6 3000
106 10 6 1012 10 12 6×106 6 10 6

Exercise 2

How long is 1012 10 12 μsecμsec? 6×106 6 10 6 μsecμsec?

The FFT and digital computer were almost completely responsible for the 'Golden Age of DSP' (1960-1980). The FFT exploits the symmetries of the twiddle factors W N =ⅇⅈ2πN W N 2 N .

Symmetry 1: Complex conjugate symmetry: W N k ( N - n ) = W N - k n = W N kn ¯ W N k ( N - n ) W N - k n W N kn ⅇ-ⅈ2πNkN-n=ⅇ-ⅈ2πNkn=ⅇⅈ2πNkn¯ 2 N k N n 2 N k n 2 N k n

Symmetry 2: Periodicity in nn and kk: W N kn = W N k ( n - N ) = W N ( k + N ) n W N kn W N k ( n - N ) W N ( k + N ) n ⅇ-ⅈ2πNkn=ⅇ-ⅈ2πNkn+N=ⅇ-ⅈ2πNk+Nn 2 N k n 2 N k n N 2 N k N n

Decimation in time FFT

Decimation is just one of many different FFT schemes. The idea is to build a DFT out of smaller and smaller DFTs by decompsing xn x n into smaller and smaller sequences. A condition for this scheme is that we must assume that N=2V N 2 V (it is a power of 2).

Derivation

NN is even, so we can compute Xk X k by separating xn x n into two subsequences each of length N2 N 2 .

Xk=∑n=0N-1xn W N kn =∑n=evenxn W N kn +∑n=oddxn W N kn X k n 0 N 1 x n W N kn n even x n W N kn n odd x n W N kn (2)
For 0≤r≤N2-1 0 r N 2 1 , let n=even=2r n even 2 r and n=odd=2r+1 n odd 2 r 1 :
Xk=∑r=0N2-1x2r W N 2 k r +∑r=0N2-1x2r+1 W N ( 2 r + 1 ) k =∑r=0N2-1x2r W N 2 kr + W N k ∑r=0N2-1x2r+1 W N 2 kr X k r 0 N 2 1 x 2 r W N 2 k r r 0 N 2 1 x 2 r 1 W N ( 2 r + 1 ) k r 0 N 2 1 x 2 r W N 2 kr W N k r 0 N 2 1 x 2 r 1 W N 2 kr (3)
But since W N 2 =ⅇ-ⅈ2πN2=ⅇ-ⅈ2πN2= W N / 2 W N 2 2 N 2 2 N 2 W N / 2 , then for 0≤k≤N-1 0 k N 1 :
Xk=∑r=0N2-1x2r W N / 2 kr + W N k ∑r=0N2-1x2r+1 W N / 2 kr =Gk+ W N k Hk X k r 0 N 2 1 x 2 r W N / 2 kr W N k r 0 N 2 1 x 2 r 1 W N / 2 kr G k W N k H k (4)

Example 1

Figure 3: N=8 N 8
Figure 3 (FFT3-4.png)
A → a B ⇒B=aA A → a B B a A

X0=G0+ W 8 0 H0 X 0 G 0 W 8 0 H 0

X1=G1+ W 8 1 H1 X 1 G 1 W 8 1 H 1

X2=G2+ W 8 2 H2 X 2 G 2 W 8 2 H 2

X3=G3+ W 8 3 H3 X 3 G 3 W 8 3 H 3

X4=G4+ W 8 4 H4=G0+ W 8 4 H0 X 4 G 4 W 8 4 H 4 G 0 W 8 4 H 0

X5= X 5

X6= X 6

X7= X 7

Problem 1

Why is X4=G4+ W 8 4 H4=G0+ W 8 4 H0 X 4 G 4 W 8 4 H 4 G 0 W 8 4 H 0 true?

Why would we want to do this? Because its more efficient. Recall that the cost to compute an N-ponit DFT is approximately N2 N 2 complex multiplications and additions. But decomposition into 2 N-point DFTS and combination requires only N22+N22+N=N22+N N 2 2 N 2 2 N N 2 2 N complex multiplications and additions. For N>2 N 2 , N22+N<N2 N 2 2 N N 2 (less computations).

So why stop heer? Break each of the N2 N 2 point DFTs into two N4 N 4 point DFTs, etc...

Example 2

For N=8 N 8 , if we start with Figure 4,

Figure 4
Figure 4 (FFT3-4.png)
then that becomes Figure 5,
Figure 5
Figure 5 (FFT5.png)
which becomes Figure 6.
Figure 6
Figure 6 (FFT6.png)

But what is an N4=2 N 4 2 point DFT?

Yk=∑m=01ymⅇ-ⅈ2π2km=y01+y1-1=y0 W N 0 +y1 W N 4 Y k m 0 1 y m 2 2 k m y 0 1 y 1 -1 y 0 W N 0 y 1 W N 4 (5)
For example, in Figure 7, we have: y0=x0 y 0 x 0 , y1=x4 y 1 x 4 .
Figure 7: What is a good name for this structure?
Figure 7 (FFT7.png)
For large NN, we keep dividing up by factors of 2. After splitting pp times, we need approximately N22p+pN N 2 2 p p N complex multiplies and adds to compute the NN point DFT.

Exercise 3

How far can this go on? p=? p ?

Then what is the total number of complex multiplies and adds in this FFT?

The total number can be reduced even further using other tricks, but for N=2 N 2 , it is always O( NlogN N N ).

The final picture

N=8 N 8

Figure 8: Weird signal ordering
Figure 8 (FFT8.png)

Notes

  1. There are logN N stages. Why?
  2. Total number of multiplies and adds is... Recall that replacing an NN point DFT with two N2 N 2 point DFTs reduced the cost from N2 N 2 to 2N22+N 2 N 2 2 N so, replacing each N2 N 2 point DFT with two N4 N 4 point DFTs will reduce cost to 22N42+N2+N=4N42+2N 2 2 N 4 2 N 2 N 4 N 4 2 2 N .
More advanced FFT topics (look in your textbooks) include:
  • Other algorithms - eg: Decimation in frequency.
  • Other structures - Note the weird ordering of xn x n on pg.C54.
  • N≠2V N 2 V - Prime factor algorithms (Chinese remainder theorem).
  • Chirp z-transform - For zooming in on DTFT.

Note:

CSBurrus wrote the book (literally!) on FFTs.

Comments, questions, feedback, criticisms?

Send feedback