Datum -
Date
Rev
Nr -
No.
Uppgjord (även faktaansvarig om annan) -
Prepared
(also subject responsible if other)
Dokansv/Godkänd -
Doc respons/Approved
Kontr -
Checked
File
REPORT
/proj/fmd/fft/report02.fm
1(52)
FFT, REALIZATION AND IMPLEMENTATION IN FPGA
Griffith University/Ericsson Microwave System AB 2000/2001
by
Magnus Nilsson
Supervisor, EMW: Rune Olsson
Supervisor, GU: Prof. Kuldip K. Paliwal
Signal Processing Laboratory, School of Microelectronic Engineering, Griffith University
Brisbane/Gothenburg 2000/2001
−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1
−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
cos(2*pi*4.5/16*t)+i*sin(2*pi*4.5/16*t)
EMWMSNN (Magnus Nilsson)
EMW/FX/DC (Anders Wanner) 2001-02-12 A1
FX/D-2001:007
Datum -
Date
Rev
Nr -
No.
Uppgjord (även faktaansvarig om annan) -
Prepared
(also subject responsible if other)
Dokansv/Godkänd -
Doc respons/Approved
Kontr -
Checked
File
2001-02-12 A1
FX/D-2001:007
REPORT
EMW/FX/DC(Anders Wanner)
EMWMSNN(Magnus Nilsson)
2(52)
Abstract
Ericsson Microwave Systems develops radar systems for military and civilian
applications. In military environments high radar resolution and long range
are desired, thus high demands must be met by the generated and
transmitted radar signal.
In this report the design of a parallel Radix-4 Fast Fourier Transform
algorithm is described. A theoretical review regarding Fourier theory and
Fast Fourier Transform (Radix-2 and Radix-4) is done.
A complex parallel Radix-4 algorithm is simulated, implemented and realized
in hardware using VHDL and a Xilinx Virtex-E 1000 FPGA circuit.
The VHDL code was simulated and synthesized in Ease and Synplify
environment. The design was verified and the output was identical with the
Matlab and VHDL simulations, proving speed improvements due to a parallel
approach.
Datum -
Date
Rev
Nr -
No.
Uppgjord (även faktaansvarig om annan) -
Prepared
(also subject responsible if other)
Dokansv/Godkänd -
Doc respons/Approved
Kontr -
Checked
File
2001-02-12 A1
FX/D-2001:007
REPORT
EMW/FX/DC(Anders Wanner)
EMWMSNN(Magnus Nilsson)
3(52)
Preface
This thesis is a part of my education towards a Master degree in Computer
and Information Engineering at Griffith University, Brisbane, Australia.
Project 1,2 and 3. MEE7097,MEE7098 and MEE7099.
The work has been done at Ericsson Microwave System AB in Mölndal
Sweden, at the department FX/D
I would like to thank the following people who has been of great help to me
during my work.
My supervisor Rune Olsson, EMW.
My manager Håkan Olsson/Anders Wanner, EMW.
Prof. Kuldip K. Paliwal, supervisor GU.
Daniel Wallström, EMW, for help with VHDL.
Dennis Eriksson, EMW, for help with Logical Analyser/Pattern generator.
Nils Dagås and Gabriel Gitye, EMW, for help with Matlab.
I would also like to thank the remaining staff at EMW/FX and GU who have
been helpful to me.
Datum -
Date
Rev
Nr -
No.
Uppgjord (även faktaansvarig om annan) -
Prepared
(also subject responsible if other)
Dokansv/Godkänd -
Doc respons/Approved
Kontr -
Checked
File
2001-02-12 A1
FX/D-2001:007
REPORT
EMW/FX/DC(Anders Wanner)
EMWMSNN(Magnus Nilsson)
4(52)
Contents Page
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Task . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Technical function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Jean-Baptiste-Joseph Fourier . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 The Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4 The Discrete Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . 13
5 Development of the Fast Fourier Transform. . . . . . . . . . . . . . . 15
5.1 Theory of the Fast Fourier Transform . . . . . . . . . . . . . . . . . . . 15
5.2 History of the Fast Fourier Transform . . . . . . . . . . . . . . . . . . . 16
6 The Radix - 2 Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Fig.1. : FFT-Butterfly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Fig.2. : Radix-2 DFT structure . . . . . . . . . . . . . . . . . . . . . . . . . 23
Fig.3. : Radix-2 vs. Direct calculation in flops . . . . . . . . . . . . . 23
Fig.4. : Radix-2 algorithm comp. with MATLAB function FFT . 24
7 The Radix-4 Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Fig.5. : Radix-4 Butterfly, also referred to as Dragonfly . . . . . . 26
Fig.6. : Radix-4 FFT algorithm compared with Matlab FFT . . . 29
8 Implementation and Realization in hardware. . . . . . . . . . . . . . 30
8.1 FPGA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Fig.7. : CLB, Configurable logic block. Courtesy of Xilinx Inc.. 30
8.2 Complex FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Fig.8. : Construction configuration. . . . . . . . . . . . . . . . . . . . . . 31
8.3 Bit-length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Fig.9. : Radix-4 FFT, 12-bit length of samples . . . . . . . . . . . . . 32
Fig.10. : Radix-4 FFT, 14-bit length of samples . . . . . . . . . . . . 32
Fig.11. : Radix-4 FFT, 16-bit length of samples . . . . . . . . . . . . 32
8.4 Radix-4 FFT algorithm, N = 64 . . . . . . . . . . . . . . . . . . . . . . . . 33
Fig.12. : Radix-4 FFT, N = 64 . . . . . . . . . . . . . . . . . . . . . . . . . 33
Fig.13. : First FFT construction vs. Matlab FFT. . . . . . . . . . . . 35
Fig.14. : Timing diagram for Radix-4 FFT, shared multiplier . . 37
8.5 Radix-4 FFT algorithm, N = 16 . . . . . . . . . . . . . . . . . . . . . . . . 38
Fig.15. : Input signal X1 and X2. . . . . . . . . . . . . . . . . . . . . . . . 38
Fig.16. : Input signal X3 and X4. . . . . . . . . . . . . . . . . . . . . . . . 38
Fig.17. : Radix-4 N = 16. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Fig.18. : Timing diagram for Radix-4 FFT length 16, 16 bits . . 39
Fig.19. : Absolute value block . . . . . . . . . . . . . . . . . . . . . . . . . 40
Datum -
Date
Rev
Nr -
No.
Uppgjord (även faktaansvarig om annan) -
Prepared
(also subject responsible if other)
Dokansv/Godkänd -
Doc respons/Approved
Kontr -
Checked
File
2001-02-12 A1
FX/D-2001:007
REPORT
EMW/FX/DC(Anders Wanner)
EMWMSNN(Magnus Nilsson)
5(52)
9 Verification and Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42
9.1 Test pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42
9.2 Matlab verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43
Fig.20. : Output graph signal X1, absolute = 1 . . . . . . . . . . . . .43
Fig.21. : Output graph signal X2, absolute = 1 . . . . . . . . . . . . .43
Fig.22. : Output graph signal X3, absolute = 1 . . . . . . . . . . . . .43
Fig.23. : Output graph signal X4, absolute = 1 . . . . . . . . . . . . .43
Fig.24. : Output complex and absolute, signal 1 vs. Matlab . . .44
Fig.25. : Output complex and absolute, signal 2 vs. Matlab . . .44
Fig.26. : Output complex and absolute, signal 3 vs. Matlab . . .45
Fig.27. : Output complex and absolute, signal 4 vs. Matlab . . .45
10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .46
11 Ideas for further studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .46
12 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .47
Appendix A1 . . . . . . . . . . . . . . Ease block structure of Radix-4 FFT, N = 64
Appendix-A2 . . . Ease block structure of Radix-4 FFT, N = 64, shared mult
Appendix A3 . . . . . . . . . . . . . . Ease block structure of Radix-4 FFT, N = 16
Appendix B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Matlab code
Appendix C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Output listing
