Fft

EE4008 Digital Signal Processing

• Direct Computation of N Point DFT of real data x(n) N −1 X

2πkn x(n) cos XR (k) = N n=0 N −1 X

2πkn x(n) sin XI (k) = − N n=0 • Resulting in:

1. 2N 2 evaluation of trigonometric functions

2. 2N 2 real multiplications 3. 2N (N − 1) real additions

4. indexing and addressing operations FFT.

1

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

Fast Fourier Transform • Collection of algorithms to compute DFT efficiently • Radix r is the smallest DFT performed: – Radix 2, N = 2v – Radix 4, N = 4v • Decimation

– In Time :- input x(n) is decimated by factor r.

– In Frequency :- output X(k) is decimated by a factor r at each stage. FFT.

2

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

Define WN = e

( −j2π ) N

Following Properties: Periodic with period N WNk+N

−j2π(k+N ) ) N

= e

(

= e

−j2πN ( −j2πk ) ( ) N N

= e

( −j2πk ) N

e

= WNk

FFT.

3

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

Odd Function k+ N WN 2

= e = e

−j2π(k+ N 2 )) ( N

( −j2πk ) N

= −e

e

−j2π N ( N 2

)

( −j2πk ) N

= −WNk

FFT.

4

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

Decimation in Time FFT N point DFT Then X(k) =

N −1 X

x(n)WNnk

n=0

=

X

x(n)WNnk

neven

k = 0, 1, . . . , N − 1 +

X

x(n)WNnk

nodd

(N/2)−1

=

X

(N/2)−1

x(2m)WN2mk

m=0

+

X

x(2m +

k(2m+1) 1)WN

m=0

Let f1 (m) = x(2m) even samples, and f2 (m) = x(2m + 1) odd samples. With WN2 = WN/2 FFT.

5

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

(N/2)−1

X(k) =

(N/2)−1 mk f1 (m)WN/2

X

m=0

+

WNk

X

km f2 (m)WN/2

m=0

= F1 (k) + WNk F2 (k)

k = 0, 1, . . . , N − 1

F1 (k) and F2 (k) are periodic with period

N 2

N F1 (k + ) = F1 (k) 2 N F2 (k + ) = F2 (k) 2 and FFT.

k+ N WN 2

= −WNk 6

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

Xlower Xupper

N −1 = X(k) = F1 (k) + k = 0, 1, . . . , 2 N N k −1 = X(k + ) = F1 (k) − WN F2 (k) k = 0, 1, . . . , 2 2 WNk F2 (k)

A N point DFT X(k) of sequence x(0), x(1), . . . , x(N − 1) can be expressed in terms of two N2 point DFTs:

FFT.

• F1 (k) is

N 2

point DFT of even samples x(0), x(2), x(4), . . .

• F2 (k) is

N 2

point DFT of odd samples x(1), x(3), x(5), . . .

7

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

8 Point DFT

N 2

=4

k=0

X(0)

=

X1 (0) + W80 X2 (0)

k=1

X(1)

=

X1 (1) + W81 X2 (1)

k=2

X(2)

=

X1 (2) + W82 X2 (2)

k=3

X(3)

=

X1 (3) + W83 X2 (3)

k=4

X(4)

=

X(0 + N/2) = X1 (0) − W80 X2 (0)

k=5

X(5)

=

X(1 + N/2) = X1 (1) − W81 X2 (1)

k=6

X(6)

=

X(2 + N/2) = X1 (2) − W82 X2 (2)

k=7

X(7)

=

X(3 + N/2) = X1 (3) − W83 X2 (3)

X1 (k) is 4 point DFT of x(0), x(2), x(4), x(6) and X2 (k) is 4 point DFT of x(1), x(3), x(5), x(7).

FFT.

8

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

X1 (0)

x(0) = x1 (0)

X(0) x(2) = x1 (1)

DFT

X1 (1) X(1) X1 (2)

x(4) = x1 (2) N =4

X(2)

X2 (0)

x(1) = x2 (0) DFT

Combining

X1 (3)

x(6) = x1 (3)

X(3) X(4) X(5)

X2 (1)

x(3) = x2 (1)

X(6) X2 (2)

x(5) = x2 (2) N =4 x(7) = x2 (3)

FFT.

X(7) X2 (3)

9

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

Calculation of 4 point DFTs X1 (k) and X2 (k) X1 (0) = X3 (0) + W40 X4 (0) X1 (1) = X3 (1) + W41 X4 (1) X1 (2) = X1 (0 + N/2) = X3 (0) − W40 X4 (0)

X1 (3) = X1 (1 + N/2) = X3 (1) − W41 X4 (1)

Where X3 (k) is 2 point DFT of even terms of sequence x(0), x(2), x(4), x(6) that is 2 point DFT of x(0) and x(4). X4 (k) is 2 point DFT of odd terms of sequence x(0), x(2), x(4), x(6) that is 2 point DFT of x(2) and x(6).

FFT.

10

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

Likewise for X2 (k): X2 (0) = X5 (0) + W40 X6 (0) X2 (1) = X5 (1) + W41 X6 (1) X2 (2) = X2 (0 + N/2) = X5 (0) − W40 X6 (0)

X2 (3) = X2 (1 + N/2) = X5 (1) − W41 X6 (1)

Where X5 (k) is 2 point DFT of even terms of sequence x(1), x(3), x(5), x(7) that is 2 point DFT of x(1) and x(5). X6 (k) is 2 point DFT of odd terms of sequence x(1), x(3), x(5), x(7) that is 2 point DFT of x(3) and x(7).

FFT.

11

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

x(6) = x4 (1)

x(1) = x5 (0) x(5) = x5 (1)

x(3) = x6 (0) x(7) = x6 (1)

FFT.

DFT N =2

DFT N =2

DFT N =2

X1 (0)

X3 (1)

X4 (0)

X(0) X1 (1) X(1) X1 (2) X(2)

X4 (1)

X1 (3)

X5 (0)

X2 (0)

X5 (1)

X2 (1)

X6 (0)

Combining

x(2) = x4 (0)

N =2

X3 (0)

Combining

x(4) = x3 (1)

DFT

X(3) X(4) X(5)

Combining

x(0) = x3 (0)

X(6) X2 (2) X(7) X2 (3)

X6 (1)

12

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

Bit Reversal

FFT.

Input

Binary

Bit Reversed

Position

x(0)

000

000

0

x(1)

001

100

4

x(2)

010

010

2

x(3)

011

110

6

x(4)

100

001

1

x(5)

101

101

5

x(6)

110

011

3

x(7)

111

111

7

13

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

FFT using Matrix Notation • 8 Point DFT • Matrix Vector Multiplication • Define

w=e

( −j2π ) 8

• w(k+8) = wk • w(k+4) = −wk

FFT.

14

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

                    

FFT.

X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7)





1

      1       1       1   =   1         1       1  

1

1

1

1

1

1 w6

1

w

w2

w3

w4

w5

w7

w2

w4

w6

w8

w10 w12 w14

w3

w6

w9

w12 w15 w18 w21

w4

w8

w12 w16 w20 w24 w28

w5 w10 w15 w20 w25 w30 w35 w6 w12 w18 w24 w30 w36 w42

1 w7 w14 w21 w28 w35 w42 w49

15

                    

x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7)

                    

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

                    

FFT.

X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7)





1

      1       1       1   =   1         1       1  

1 w

1

1

1

1

1

1

w2 w3 w4 w5 w6 w7

w2 w4 w6 w3 w6

w

w4

w4

1

1

w2 w4 w6

w4 w7 w2 w5 1

w4

1

w4

w5 w2 w7 w4 w1 w6 w3 w6 w4 w2

1

w6 w4 w2

1 w7 w6 w5 w4 w3 w2

16

w

                    

x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7)

                    

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

                    

FFT.

X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7)





1

      1       1       1   =   1         1       1  

1

1

1

w2 w4 w6 w4

1

1 w

1

1

1

w3 w5 w7

1

w

w7 w5

w4 w4 w4 w4

w2 w4 w6 w5 w7 w4

1

w4 w2 w6 w2 w6

w6 w4 w2 w3 1

1

w

w3

w4 w6 w2 w6 w2

1 w6 w4 w2 w7 w5 w3

17

w

                    

x(0) x(2) x(4) x(6) x(1) x(3) x(5) x(7)

                    

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

                    

FFT.

X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7)





1

      1       1       1   =   1         1       1  

1

1

1

−j −1 −1 j 1

1

j

j

1 w

1

1

1

1

1

w3 w5 w7

−1 w2 w6 w2 w6

−1 −j w3

−j −1 −1

1

w

w7 w5

1

w4 w4 w4 w4

j

w5 w7

w

w3

−1 w6 w2 w6 w2

−1 −j w7 w5 w3

18

w

                    

x(0) x(2) x(4) x(6) x(1) x(3) x(5) x(7)

                    

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

                    

FFT.

X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7)





1

      1       1       1   =   1         1       1  

1

1

1

−j −1 −1 j 1

1

1

j

1

1

1

1

1

j

w

w3

w5

−1

w2

w6

w2

w3

w

w7

1

−1

−1

−1

j

−w

−1 −j

−j −1 −1

1

−w 3 −w5

−1 −w2 −w6 −w2

−1 −j −w 3

19

−w



  7  w    6  w    5  w     −1     −w7     6  −w  

−w7 −w5

x(0) x(2) x(4) x(6) x(1) x(3) x(5) x(7)

Dr Liam Marnane email: [email protected]

                    

EE4008 Digital Signal Processing



 A4 X=

A4



B4  x −B4

where 

1

1

   1 −j A4 =     1 −1 

1

j

1 −1 1



1   j  

 −1   

−1 −j

and B4 = w k A4 FFT.

20

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

Decimation in Time Radix 2, 8pt FFT x(0) x(4)

X(0) 0 w8

X(1) −1

x(2) x(6)

0 w8

0 w8

X(2) −1

2 w8

X(3) −1

−1 x(1) x(5)

X(4) 1 w8

0 w8

−1 x(3) x(7)

0 w8

0 w8

2 w8

−1

2 w8

−1

FFT.

0 w8

−1

21

3 w8

−1 X(5) −1 X(6) −1 X(7) −1

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

³

X(0) = x(0) + w80 × x(4) + w80 x(2) + w80 × x(6) ³

³

´

+w80 x(1) + w80 × x(5) + w80 x(3) + w80 × x(7)

´´

= x(0) + x(1) + x(2) + x(3) + x(4) + x(5) + x(6) + x(7) X(1) = x(0) − +w81

³

w80

× x(4) +

x(1) −

w80

w82

³

x(2) −

× x(5) +

w82

³

w80

× x(6)

x(3) −

w80

´

× x(7)

´´

= x(0) + w81 × x(1) + w82 × x(2) + w81 × w82 × x(3)

−x(4) − w81 × x(5) − w82 × x(6) − w81 × w82 × x(7)

FFT.

22

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

Decimation in Frequency FFT N point DFT Then X(k) =

N −1 X

x(n)WNnk

k = 0, 1, . . . , N − 1

n=0

N 2

X(k) =

x(n)WNnk +

n=0 N 2

X(k) =

N −1 X

−1

X

n= N 2

−1

X

x(n)WNkn

+

N k/2 WN

n=0

FFT.

x(n)WNnk N 2

−1

X

n=0

23

N x(n + )WNkn 2 Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

But

kN WN 2

= (−1)k N 2

X(k) =

−1 X ·

n=0

N k x(n) + (−1) x(n + ) WNkn 2 ¸

Let us split X(k) into even and odd Numbered Samples N 2

X(2p) =

−1 · X

x(n) + x(n +

n=0 N 2

X(2p + 1) =

−1 ½· X

n=0

FFT.

¸

N pn ) WN 2 2

p = 0, 1, . . . ,

¸ ¾ N pn x(n) − x(n + ) WNn W N 2 2

24

N −1 2

N −1 p = 0, 1, . . . , 2

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

Define

N 2

Point Sequence: N n = 0, 1, 2, . . . , − 1 2 N n = 0, 1, 2, . . . , − 1 2

N g1 (n) = x(n) + x(n + ) 2 · ¸ N g2 (n) = x(n) − x(n + ) WNn 2 Then we have the

N 2

point DFTs of g1 (n) and g2 (n)

N 2

X(2p) =

−1

X

pn

g1 (n)W N 2

n=0 N 2

X(2p + 1) =

−1

X

pn

g2 (n)W N 2

n=0

FFT.

25

N p = 0, 1, . . . , − 1 2 N p = 0, 1, . . . , − 1 2 Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

g1 (0)

X(0)

x(0) g1 (1)

DFT

X(2)

x(1) g1 (2) N =4

x(4)

Combining

x(2) x(3)

X(4)

g1 (3)

X(6)

g2 (0)

X(1) DFT

x(5) g2 (1)

X(3)

g2 (2)

X(5)

x(6) N =4

x(7) g2 (3)

FFT.

26

X(7)

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

x(0)

g1 (0)

x(1)

g1 (1)

x(2)

g1 (2)

X(0) DFT

X(2) X(4)

N =4 g1 (3)

X(6)

0 w8

g2 (0)

X(1)

1 w8

g2 (1)

X(3)

2 w8

g2 (2)

X(5)

3 w8

g2 (3)

x(3)

x(4) −1 x(5) −1 x(6) −1 x(7)

DFT

N =4 X(7)

−1

FFT.

27

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

Decimation in Frequency Radix 2, 8pt FFT x(0)

X(0) 0 w8

x(1) 0 w8

x(2) −1 x(3) x(4) −1 x(5) −1 x(6) −1 x(7)

X(2) 0 w8

X(6)

−1 X(1)

1 w8

0 w8

0 w8

2 w8

−1

3 w8

−1

FFT.

−1

2 w8

−1

0 w8

X(4)

−1

28

X(5)

−1 X(3) 0 w8

2 w8

X(7)

−1

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

8 Point DFT Example Data x =

µ

1 1 1 1 0.5 0.5 0.5 0.5

¶

8 Point DFT is:         

FFT.

X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7)





       =         

1

1

1

e 4

−j

1

−j

−1

j

1

−j3π e 4

1

−1

1

j3π e 4

1

j

1

e 4

−jπ

1 e

1

1

−j3π 4

−1

1

1

1

j

e 4

−1

j j3π e 4

j3π

e 4

jπ

1

−j

j

−jπ e 4

−1

jπ e 4

−j

1

−1

1

−1

1

−1

−j

jπ e 4

−1

−jπ e 4

j

−j3π e 4

−1

−j

1

j

−1

−j

jπ

j3π

j

e 4

−1

29

e

−j3π 4

−j

e

−jπ 4





         

x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7)

        

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

8 Point DFT Example         

6 0.5 − 1.270711j 0 0.5 − 0.20711j 0 0.5 + 0.270711j 0 0.5 + 1.270711j



       =         

Note e

FFT.



−jπ 4

1

1

1

1

e 4

−j

1

−j

−1

j

1

−j3π e 4

1

−1

1

j3π e 4

1

j

1

e 4

−jπ

π = cos 4

1

−j3π 4

−1

1

1

1

j

e 4

−1

j j3π e 4

j3π

jπ

e 4

1

−j

j

−jπ e 4

−1

jπ e 4

−j

1

−1

1

−1

1

−1

−j

jπ e 4

−1

−jπ e 4

j

−j3π e 4

−1

−j

1

j

−1

−j

jπ

µ ¶

e

1

j3π

j

e 4

π − j sin 4

µ ¶

30

−1

e

−j3π 4

−j

e

−jπ 4





         

1 1 1 1 0.5 0.5 0.5 0.5

j 1 =√ −√ 2 2

Dr Liam Marnane email: [email protected]

        

EE4008 Digital Signal Processing

Decimation in Time Radix 2, 8pt FFT X(0)

1

0.5

0 =1 w8

X(1) −1 0 =1 w8

1

X(2) −1

0.5

0 w8 =1

2 = −j w8

X(3) −1 0 w8 =1

−1 1

0.5

X(4)

0 w8 =1

X(5) −1

2 w8 = −j

2 w8 = −j

X(6)

−1 1+j 3 w8 =− √

−1

−1

−1

X(7)

2

−1

FFT.

−1

2

−1 0 w8 =1

1

0.5

1−j 1 = √ w8

0 w8 =1

31

Dr Liam Marnane email: [email protected]

EE4008 Digital Signal Processing

Decimation in Time Radix 2, 8pt FFT 1

X(0)

0.5

X(1) −1 X(2)

1 −1 0.5

X(3) −1

−1 1

X(4) −1 X(5)

0.5 −1

−1 1

X(6) −1

−1 X(7)

0.5 −1

FFT.

−1

32

−1

Dr Liam Marnane email: [email protected]