Hungchihchiu

FFT

• Many ways to decompose an FFT • Simplest is radix‐2 • Computation made up of radix‐2 butterflies

A B

X = A + BW Y = A – BW

B. Baas, © 2012, EEC 281

14

FFT Dataflow Diagram

• Dataflow diagram

– N = 64 – radix‐2 – 6 stages of  computation

0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 63

Memory Locations

Input

B. Baas, © 2012, EEC 281

Output

15

Radix 2, 8-point FFT

B. Baas, © 2012, EEC 281

16

Radix 2, 8-point FFT

Radix 2, 16-point FFT

B. Baas, © 2012, EEC 281

17

Radix 2, 8-point FFT

Radix 2, 32-point FFT

B. Baas, © 2012, EEC 281

18

Radix 2, 8-point FFT

Radix 2, 64-point FFT

B. Baas, © 2012, EEC 281

19

Radix 2, 256-point FFT

Radix 2, 256-point FFT

B. Baas, © 2012, EEC 281

20

Radix 4, 16-point FFT

B. Baas, © 2012, EEC 281

21

Radix 4, 64-point FFT

B. Baas, © 2012, EEC 281

22

Radix 4, 256-point FFT

B. Baas, © 2012, EEC 281

23

Radix 2, Decimation-In-Time (DIT)

• Input order “decimated”—needs bit reversal • Output in order Critical path: • Butterfly:

B A B X = A + BW x Y = A – BW A car-sav add +

B. Baas, © 2012, EEC 281

24

W

Radix 2, Decimation In Frequency (DIF)

• Input in order • Output “decimated”—needs  bit reversal • Butterfly:

– Two CPAs – Wider multiplier A B X=A+B Y = (A – B) W Critical path: A B

+ (–)

W

x +

25

B. Baas, © 2012, EEC 281

Radix 4, DIT Butterfly

• Decimation in Time (DIT) or Decimation in  Frequency (DIF)

A B C D

V W X Y

B. Baas, © 2012, EEC 281

26

Bit-Reversed Addressing

• Normally:

– DIT: bit‐reverse inputs before processing

BIT REVERSAL

– DIF: bit‐reverse outputs after processing

• Reverse addressing bits for read/write of data

– – – – – – – – 000 (0)   001 (1)   010 (2)   011 (3)   100 (4)   101 (5)   110 (6)   111 (7)   000 (0)     # Word 0 does not move location 100 (4)     # Original word 1 goes to location 4 010 (2)     # Word 2 does not move location...