Skip to content Skip to navigation

OpenStax_CNX

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

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Fast fourier transform (FFT)

Module by: Richard Baraniuk. E-mail the author

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

k ,0kN1:Xk= n =0N1Xkei2π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 N1 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 N2N 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)
Table 1
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)
Table 2
N N N2 N 2 NlogN 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 =ei2π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 e(i)2πNk(Nn)=e(i)2πNkn=ei2π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 e(i)2πNkn=e(i)2πNk(n+N)=e(i)2πN(k+N)n 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 =0N1xn 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 0rN21 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 =0N21x2r W N 2 k r + r =0N21x2r+1 W N ( 2 r + 1 ) k = r =0N21x2r W N 2 kr + W N k r =0N21x(2r+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 =e(i)2πN2=e(i)2πN2= W N / 2 W N 2 2 N 2 2 N 2 W N / 2 , then for 0kN1 0 k N 1 :
Xk= r =0N21x2r W N / 2 kr + W N k r =0N21x(2r+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 =01yme(i)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 2(2N42+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.
  • N2V 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.

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

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