M.A. College of Engineering
FFT Processor 1
Guided by Done by
Prof. K.Radhakrishnan Ray Ranjan Varghese
ELECTRICAL & ELECTRONICS DEPT.
Chanjal .G.Tharayil
M.A. COLLEGE OF ENGINEERING
M
MM
Ma
aa
ar
r r
r A
AA
At
tt
th
hh
ha
aa
an
nn
na
aa
as
ss
si
ii
iu
uu
us
s s
s C
CC
Co
oo
oll
llll
lle
ee
eg
gg
ge
e e
e o
oo
of
f f
f E
EE
En
nn
ng
gg
gi
ii
in
nn
nee
eeee
eer
rr
ri
ii
in
nn
ng
gg
g
.
..
.2
22
27
77
7+
++
+$0
$0$0
$0$
$$
$1*
1*1*
1*$
$$
$/$
/$/$
/$0
00
0
MAHATMA GANDHI UNIVERSITY, KOTTAYAM,
KERALA 2001
M.A. College of Engineering
FFT Processor 2
TABLE OF CONTENTS
LIST OF FIGURES……………………………………………………
Chapter 1-Introduction to VHDL
1.1 Introduction 1
1.2 Advantages of VHDL over other Hardware…
Description Languages……………………………………….. 1
1.3 VHDL : The Language…………………………………… 2
1.3.1 Entity Declaration……………………………….. 3
1.3.2 Architecture Body……………………………….. 3
1.3.3 Configuration Declaration……………………….. 7
1.3.4 Package…………………………………………… 8
1.3.5 Testbench………………………………………… 9
Chapter 2-High Level Design Flow…………………………………. 10
2.1 HDL Capture……………………………………………… 10
2.2 RTL Simulation…………………………………………… 10
2.3 VHDL Synthesis………………………………………….. 12
2.4 Functional Gate Level Verification………………………. 13
2.5 Place and Route…………………………………………... 13
2.6 Post Layout Timing Simulation………………………….. 15
Chapter 3-Illustration of VHDL…………………………………….. 16
3.1 The IEEE floating-point standard………………………… 16
3.2 The Addition Process…………………………………….. 17
3.3 Hardware Implementation of Floating-Point Adder……… 19
3.3.1 Block Diagram of the Adder…………………….. 19
3.3.2 The Subtractor Unit……………………………… 20
3.3.3 The Swap Unit…………………………………… 21
3.3.4 The Shifter Unit………………………………….. 22
3.3.5 The Summer Unit………………………………… 23
3.3.6 The Normalize Unit………………………………. 23
3.3.7 The Control Unit…………………………………. 24
3.3.8 The Testbench for the adder……………………… 28
Chapter 4- The Fourier Transform…………………………………… 30
4.1 The Discrete Fourier Transform…………………………... 30
4.1.1 An Illustration…………………………………….. 30
4.1.2 Types of Fourier Transforms……………………... 31
4.1.3 Notation and Format of the Real DFT……………. 33
4.1.4 DFT Basis Functions……………………………… 34
4.1.5 Analysis, Calculating the DFT……………………. 37
4.2 The Fast Fourier Transform………………………………. 37
4.2.1 Comparison of Real DFT and Complex DFT……. 38
4.2.2 How the FFT works……………………………… 39
4.3 Synthesis, Calculating the Inverse DFT………………….. 42
4.4 Illustration of the DFT and IDFT in Matlab……………… 44
Chapter 5-Architectural Design of the FFT Processor……………… 46
5.1 Block Diagram of the FFT Processor…………………….. 46
M.A. College of Engineering
FFT Processor 3
5.2 Butterfly Processing Element…………………………….. 48
5.3 Address Generation Unit…………………………………. 50
5.3.1 Butterfly Generator……………………………… 52
5.3.2 Stage Generator………………………………….. 52
5.3.3 Stage Done_IO Done Block……………………... 52
5.3.4 IO-Address Generator…………………………… 53
5.3.5 Base Index Generator……………………………. 53
5.3.6 The Shifters……………………………………… 54
5.3.7 ROM Address Generator………………………... 54
5.4 Controller…………………………………………………. 55
5.5 RAM and ROM…………………………………………... 55
Chapter 6-RTL Simulation of the FFT Processor…………………... 56
Chapter 7-Synthesis of the FFT Processor………………………….59
Chapter 8-Conclusion………………………………………………. 60
APPENDIX A-Code Listing……………………………………….. 61
APPENDIX B-Synthesis Results…………………………………... 101
References ………………………………………………………….112
M.A. College of Engineering
FFT Processor 4
LIST OF FIGURES
Figure 1.1 – Half Adder…………………………………………… 3
Figure 2.1 – High Level Design Flow…………………………….. 11
Figure 3.1 – IEEE Format of Floating Point Numbers……………. 16
Figure 3.2 – Block Diagram of the Floating Point Adder Unit…… 20
Figure 3.3 – Structure of a Finite State Machine…………………. 25
Figure 4.1 – Sampled Values of signal being decomposed………. 29
Figure 4.2 – Sine and Cosine Waves after Fourier Decomposition. 30
Figure 4.3 – Types of Fourier Transforms………………………... 32
Figure 4.4 – DFT Terminology…………………………………… 33
Figure 4.5 – DFT Basis Functions………………………………… 36
Figure 4.6 – Comparison of Real and Complex DFT…………….. 38
Figure 4.7 – Signal Flow Graph for 8-point DIT-FFT with
Input Scrambling…………………………………………………. 40
Figure 4.8 – Signal Flow Graph for 8-point modified DIT-FFT
With Output Scrambling………………………………………….. 41
Figure 4.9 – The Bandwidth of Frequency Domain Signals……... 44
Figure 5.1 – FFT Computation Process…………………………... 46
Figure 5.2 – Block Diagram of FFT Processor…………………... 47
Figure 5.3 – Butterfly Processing Unit…………………………... 48
Figure 5.4 – Waveform of the Cycles used in the FFT Processor.. 49
Figure 5.5 – Address Generation Unit…………………………… 51
M.A. College of Engineering
FFT Processor 5
CHAPTER 1
INTRODUCTION TO VHDL
1.1 Introduction
VHDL is an acronym for VHSIC Hardware Description language
(VHSIC stands for Very High Speed Integrated Circuits ). It is a
hardware description language that can be used to model a digital
system at many levels of abstraction ranging from the algorithmic level
to the gate level. The complexity of the digital system being modeled
could vary from that of a simple gate to a complete digital electronic
system, or anything in between.
VHDL can be regarded as an integrated amalgamation of the
following languages : sequential + concurrent + netlist + timing
specification + waveform generation language.
Therefore the language has constructs that enable to express the
concurrent or sequential behavior of a digital system with or without
timing. It also allows modeling the system as an interconnection of
components. Test waveforms can also be generated using the same
constructs. All the above constructs can be combined to provide a
comprehensive description of the system in a single model.
1.2 Advantages of VHDL over other hardware description
languages.
1. The language con be used as a communication medium
between different CAD and CAE tools.
2. The language supports hierarchy; that is, a digital system can
be modeled as a set of interconnected components each
component in turn can be modeled as a set of interconnected
subcomponents.
