### 4. FFT Generator

```Fast Fourier
Transform
Generator
Chia-Wei Chen
1
Overview
DFT
FFT
−1
=

2
−

2
=0
− 2
2
2
Outline
• 1. History of FT/FFT
• 2. FFT Algorithm
• 3. FFT Hardware
• 4. FFT Generator
3
History of FT
• Joseph Fourier 1768-1830
1822
4
5
History of FFT
• Cooley & Tukey
1965
• Gauss 1777-1855
1805
6
History of FFT
1805:Fast Algorithm
1822:FT
DFT
1965:FFT
7
Outline
• 1. History of DFT/FFT
• 2. FFT Algorithm
• 3. FFT Hardware
• 4. FFT Generator
8
−1
=

2
−

−1

=
=0
=0
−1
2 =

−1
2
=
−1

(2)

=0

+

=
2

−1
2
=0

−1
2
=

(2)

+
=0

−1
2
=
(  +   +
=0

=0
(2)

=

=0

−1
2
−1
(2)

(2+1)
2 + 1 =
−1
(2+1)

(+ )(2)
+
2
2

)/2
2
=

(2+1)

=0

−1
2
=
(  −   +
=0

=
2

−1
2
=0

−1
2
(2+1)
+
+
=0

(+ )(2+1)
+
2
2

)/2
/2
2
9
10
11
-j
81
-j
-j
81
12
Comparison
• Complexity
DFT
7
8
=
=0
• Performance
-j
81
-j
-j
81
13
Outline
• 1. History of DFT/FFT
• 2. FFT Algorithm
• 3. FFT Hardware
• 4. FFT Generator
14
Single-Path Delay Feedback (SDF)
BF
BF
BF
15
Single-Path Delay Feedback (SDF)
BF
16
• For the students of GICE
• Course: Digital Signal Processing
• Prof. Pei
• Complexity  Performance
• For the students of GIEE
• Course: Digital Signal Processing in VLSI Design
• Prof. Chien
• Schedule Table  Animations
17
Outline
• 1. History of DFT/FFT
• 2. FFT Algorithm
• 3. FFT Hardware
• 4. FFT Generator
18
FFT Generator
• Matlab
• C++
• Verilog
• FPGA
FFT or IFFT
Length
SQNR
Operation speed
Antenna number
FFT/IFFT
Generator
Verilog file
Test bench
19
Flowchart
20
4096 = 212
21
Target: SQNR=55dB
22
Demonstration
23
Thank You!
24
```