ADSP Lec 10 - Advanced FFt,DFT PDF

Preview

Summary

Advanced FFt,DFT...

Description

12/27/2011

Advan Advanced ced Dig Digital ital Signal Proc Processing essing DTFT, DFS, DFT, FFT

Dr Dr.. Ta Tahir hir Za Zaidi idi

DTFT to DFT

1

12/27/2011

Sampling the Fourier Transform  Consider an aperiodic sequence with a Fourier transform

 

 x[n] DTFT  X ej  Assume that a sequence is obtained by sampling the DTFT

 

~ Xk  X e j

2  / Nk



j 2 / N k  Xe 



 Since the DTFT is periodic resulting sequence is also periodic  We can also write it in terms of the z-transform



~ Xk   X z z e  2 /Nk  X e j 2 / N k



 The sampling points are shown in figure ~  Xk could be the DFS of a sequence  Write the corresponding sequence N1 ~  1 ~  j 2  / N kn x[n] Xk e N k 0

DFT Analysis and Synthesis

2

12/27/2011

DFT

DFT is Periodic with period N

3

12/27/2011

Example 1

Example 1 (cont.) N=5

4

12/27/2011

Example 1 (cont.) N>M

DFT from DFS

5

12/27/2011

Symmetry Properties

DFT Properties

6

12/27/2011

Example: Circular Shift

Example: Circular Shift

7

12/27/2011

Example: Circular Shift

Duality

8

12/27/2011

Circular Flip

Properties: Circular Convolution

9

12/27/2011

Example: Circular Convolution

Example: Circular Convolution

10

12/27/2011

Example (continued) illustration of the circular convolution process

Illustration of circular convolution for N = 8:

11

12/27/2011

•Example:

•Example (continued)

12

12/27/2011

•Proof of circular convolution property:

•Multiplication:

13

12/27/2011

INT INTRODUCTION RODUCTION TO THE FAST FOU FOURI RI RIER ER TRA RANSFORM NSFORM ALGOR ALGORITHM ITHM

14

12/27/2011

15

12/27/2011

16

12/27/2011

17

12/27/2011

Introduction Fast Fourier Transforms have revolutionized digital signal processing Wh What at is the FFT FFT??  A collection of “tricks” that exploit the symmetry of the DFT calculation to make its execution much faster  Speedup increases with DFT size

18

12/27/2011

Com puta tional Co st of Dis cre te -Ti me Fil teri ng Computa putational Cost Discre crete te-Ti -Time Filteri tering Computational Cost of Discrete-Time Filtering Con Convolution volution of an N-p -point oint inp nput ut wi with th an M -p -point oint uni nitt sam sample ple re resp sp sponse onse …. Di Direct rect co conv nv nvolution: olution:

y[n] 



 x[k]h[n  k] k

 Number of multiplies ≈ MN

Computational Cost of Discrete-Time Filtering Computational Cost of Discrete-Time Filtering Con Convolution volution of an N-p -point oint inp nput ut wi with th an M -p -point oint uni unitt sa sampl mpl mple e res esponse ponse …. Us Usin in ing g tra transform nsform nsforms s dir direct ect ectly: ly: X[k] 

N 1

 x[n]e  j2kn / N

n0 2  Computation of N -point DFTs requires N multiplys  Each convolution requires three DFTs of length N+M1 plus an additional N+M-1 complex multiplys or

3( N  M  1)2  (N  M  1)  For N  M

2 , for example, the computation is O(N )

19

12/27/2011

The Cooley -T ukey de cim ation-in-time alg ori thm Cooley-T -Tukey decim cima algori orithm The Cooley-Tukey decimation-in-time algorithm • Consider the DFT algorithm for an integer power of 2, N1



X[k] 

k 0

x[n]WN nk 

N1



k 0

x[n]e  j 2nk / N ; WN  e  j2 / N

• Create separate sums for even and odd values of n:

 x[n]WN 2k   x[n]WN 2k

X[k] 

n even

n odd

n  2r 1 for n odd, we obtain

• Letting n  2r for n even and X[k] 

 N / 21

 N / 2 1

r 0

r 0



x[2r]WN 2rk 



x[2r  1]WN 2r1 k

Cooley-T -Tukey decim cima time algorithm The Cooley -T ukey de cim ation in tim e algor ithm Sp Spli li litting tting in indi di dices ces in tim time, e, we hav have e ob obtai tai tained ned X[k] 

N / 2 1

N / 2 1

r 0

r0



x[2r]WN 2rk 



x[2r  1]WN 2r1 k

But WN2  e  j 22 / N  e  j 2 /( N / 2)  WN / 2and WN2rk WNk  WNk WNrk/ 2 So … X[k] 

(N/ 2)1

( N/ 2)1

n0

n0



k x[2r ]WNrk/ 2  WN

N/2-point DFT of x[2r]



rk x[2 r  1]WN /2

N/2-point DFT of x[2r+1]

20

12/27/2011

Savings so…far … Savings so far We have sp spli li litt th the e DFT comp computation utation in into to two hal halves: ves: X[k]  

N 1



x[n]WN nk

k 0 ( N/ 2)1

( N/ 2)1

n0

n0



k x[2r ]WNrk/ 2  WN



x[2 r  1]WNrk/ 2

Have we gain gained ed an anyt yt ything? hing? C Cons ons onsider ider th the e nomi ominal nal nu numbe mbe mberr of mul multi ti tiplications plications forN  8 Original ginal form prod produces uces 8 2  64 mu mult lt ltiplications iplications  Ori  New f orm produ produces ces 2(4 2 )  8  40 mu mult lt ltiplication iplication iplications s So we’re a lr a hea …. Let’ k eep g oin lready eady head d …... Let’s s oing!! g!! 

Sign al flow graph rep res entatio n of 8 -p oi nt DFT Signal lowgraph repres resentatio entation 8-p -poi oint Signal flowgraph representation of 8-point DFT Rec Recall all tha thatt the DFT is now of the form The DFT in (partial) fl flowgraph owgraph no notation tation tation:

21

12/27/2011

The complete decomposition into 2-point DFTs

The complete decomposition into 2-point DFTs

22

12/27/2011

Now let’s take a closer look at the 2-point DFT The exp xpressio ressio ression n for the 2-p 2-point oint DFT is: X[k] 

1



x[n]W2nk 

n0

Eval Evaluating uating fo forr k  0,1

1



 x[n]e  j 2 nk / 2

n0

we obt obtain ain

X[0]  x[0]  x[1] X[1]  x[0]  e  j 2 1/ 2 x[1]  x[0]  x[1]

whi which ch in sign signal al flowg flowgraph raph not notati ati ation on look looks s like ... This topology is referred to as the basic butterfly

The complete 8-point decimation-in-time FFT

23

12/27/2011

Number of multiplys for N-point FFTs

 • )Let N  2 where   log 2 (N • (log2(N) columns)(N/2 butterflys/column)(2 mults/butterfly) N log2 (N) or ~ multiplys

Computational complexity

24

12/27/2011

Additional timesavers: reducing multiplications in the basic butterf As we deri derive ve ved d it it,, the basi basic c but utterf terf terfly ly i s of the form

WNr

S ince W N / 2  1 N r prem premultiplying ultiplying by WN

WNr N / 2 we can reduc reduce e co compu mpu mputation tation by 2 by

1

WNr

1

Bit reversal of the input Re Reca ca call ll th the e firs firstt st stag ag ages es of the 88-po po point int FFT: Consider the binary representation of the indices of the input:

0 000 4 100 If these binary indices are 2 010 time reversed, we get the 6 110 binary sequence representing 0,1,2,3,4,5,6,7 1 001 5 101 Hence the indices of the FFT 3 011 inputs are said to be in bit-reversed order 7 111

25

12/27/2011

Some comments on bit reversal In the imple implementation mentation of the FFT that we discussed discussed,, the in input put is bi bitt rev reversed ersed an and d the outpu outputt is de developed veloped in natur natural al ord orde er Some othe otherr imp implementati lementati lementations ons of the FFT have the inp input ut in nat natur ur ural al ord order er and the output bit rev reversed ersed In some situa situations tions it is conve convenient nient to impl implement ement fi filtering ltering app pplicati licati lications ons by  Use FFTs with input in natural order, output in bitreversed order  Multiply frequency coefficients together (in bit-reversed order)  Use inverse FFTs with input in bit-reversed order, output in natural order

Comp Computing uting in this fashi fashion on me means ans we neve neverr hav have e to comp compute ute bi bitt rever reversal sal ex expl pl plicitly icitly

Decimation in Freq FFT

26

12/27/2011

Alternate FFT structures

We developed the basic decimationin-time (DIT) FFT structure, but other forms are possible simply by rearranging the branches of the signal flowgraph Consider the rearranged signal flow diagrams on the following panels …..

Alternate DIT FFT structures (continued)

 DIT structure with input bit-reversed, output natural (OSB 9.10):

27

12/27/2011

Alternate DIT FFT structures (continued)

 DIT structure with input natural, output bit-reversed (OSB 9.14):

Alternate DIT FFT structures (continued)

 DIT structure with both input and output natural (OSB 9.15):

28

12/27/2011

Alternate DIT FFT structures (continued)

 DIT structure with same structure for each stage (OSB 9.16):

Comments on alternate FFT structures

A method to avoid bit-reversal in filtering operations is:

 Compute forward transform using natural input, bit-reversed output (as in OSB 9.10)  Multiply DFT coefficients of input and filter response (both in bit-reversed order)  Compute inverse transform of product using bit-reversed input and natural output (as in OSB 9/14)

Latter two topologies (as in OSB 9.15 and 9.16) are now rarely used

29

12/27/2011

forabout inverseforward DFTs DFTs in  We’ve alwaysUsing beenFFTs talking our discussion about FFTs …. what about the inverse FFT? 1 x[n]  N

N 1



k 0

kn X[k]WN ; X[k] 

N 1



n0

kn x[n]WN

 One way to modify FFT algorithm for the inverse DFT computation is: k k  Replace WN by WN wherever it appears  Multiply final output by 1/ N

 This method has the disadvantage that it requires modifying the internal code in the FFT subroutine

A better way to modify FFT code for inverse DFTs Tak Taking ing the com compl pl plex ex con conju ju jugate gate of both sid sides es of the ID IDFT FT eq equati uati uation on and mul ultiplying tiplying by N: Nx *[n]  N1

N1 * kn  kn 1   X *[k ]WN ; or x[n]  N  X *[ k ]WN  k0  k0

N 1

Thi This s sugg uggests ests tha thatt we can modify the FFT alg algori ori orithm thm for th the e inve inverse rse DF DFT T compu computation tation by the foll ollowing: owing:  Complex conjugate the input DFT coefficients  Compute the forward FFT  Complex conjugate the output of the FFT and multiply by 1/N

Thi This s method has the adv advantage antage th that at the inte internal rnal FF FFT T cod code e is undi undisturbed; sturbed; it is wide widely ly us used. ed.

30...