# dogan memisoglu bilgehan aktepe .pdf

### File information

Original filename: dogan_memisoglu__bilgehan_aktepe.pdf

This PDF 1.5 document has been generated by MicrosoftÂ® Word 2016, and has been sent on pdf-archive.com on 12/05/2017 at 17:47, from IP address 60.49.x.x. The current document download page has been viewed 412 times.
File size: 561 KB (17 pages).
Privacy: public file

dogan_memisoglu__bilgehan_aktepe.pdf (PDF, 561 KB)

### Document preview

DEVELOPING FAST FOURIER TRANSFORM
ALGORITHM ON FPGA BOARD WITH
OPTIMUM PERFORMANCE

Design Report
www.digilentdesigncontest.com

DEVELOPING FAST FOURIER TRANSFORM ALGORITHM ON
FPGA BOARD WITH OPTIMUM PERFORMANCE
BILGEHAN AKTEPE

c1117002@student.cankaya.edu.tr
DOGAN MEMİŞOĞLU

c1214038@student.cankaya.edu.tr
Submitted for the 2017 Digilent Design Contest Europe
May 2017

Cankaya University
Ankara, TURKEY

page 1 of 17

Developing Fast Fourier Transform Algorithm On FPGA Board With
Optimum Performance Design Report

PRODUCT MARKETING SHEET

page 2 of 17

Developing Fast Fourier Transform Algorithm On FPGA Board With
Optimum Performance Design Report

Introduction
Abstract
Fast Fourier Transform had entered the most of the communication standards [1-10] and it is used
most of the practical systems. In the future , surely that the Fast Fourier Transform will be used for
most of the communication systems.
In this Project, the description of the Fast Fourier Transform, the usage areas will be examined in
more detail. The Fast Fourier Transform was provided to understand easily by applying on MATLAB.
As the next step, the Fast Fourier Transform algorithm was done on digital FPGA devices. The Fast
Fourier Transform algorithm includes many multiplication and summation processes in complex area.
Also, the algorithm includes many of exponential functions.
In sum, the Fast Fourier Transform algorithm was done on FPGA environment optimally and for that,
the operational speed gain was calculated by using suggested methods.
Objectives
There are two motivations of the project. One of them is implementing FFT Algorithm with less
iteration index. As a result of that, the FFT Algorithm will need less time to implementation and it will
be expected reducing delays in digital communication, efficient filter design and efficient signal
processing. In the point of view ,Cordic Algorithm was selected for FFT Algorithm with a reason of
being most commonly used algorithm in daily life such as calculators, trigonometric functions
approximation and hyperbolic function calculations. While using Cordic Algorithm, owning less opensource VHDL examples were considered as an objective.
.
Project Summary

The aim of the project is making the Fast Fourier algorithm on FPGA Digital devices with optimum
operational speed. For that, suggested methods are as follows. According to the Fast Fourier Transform
equations had written in last parts, in the formula includes
terms. These exponential terms can be
written in terms of the complex summation of sine and cosine functions. For calculating sine and
cosine functions on FPGA environment, polynomial approach method will be used. For increasing
algorithm speed, entire of this exponential functions will be prepared by calculating in the same time
interval in parallel at the beginning of the algorithm. By this method, system will gain speed while the
running of the algorithm.
On the other hand, according to written equations, a lot of complex multiplication process can be
shown. Making the complex multiplication process affects entire of the algorithm speed. The methods
in literature are thought to use for increasing multiplication process speed in the algorithm. One of
these methods is Cordic algorithm .By this method, multiplication is done by less iteration. Cordic
Algorithm was done by VHDL and multiplication process in Fast Fourier Transform algorithm will be
page 3 of 17

Developing Fast Fourier Transform Algorithm On FPGA Board With
Optimum Performance Design Report

done by this method. Another acceleration method is calculating Fast Fourier Transform coefficients in
same time. Because of independency, coefficients can be calculated separately. That could be done in
FPGA environmental in parallel.
Digilent Products Required

Artix 7 BASYS 3
Pmod DA1 KIT

Tools Required

MATLAB
ISE

Pmod DA1 KIT
Artix 7 BASYS 3

Design Status
For now, the Cordic Algorithm was implemented on FPGA Board and robust results were collapsed.

Background
Why This Project?

Normally Cordic Algorithm is in IP-Core which means there is no access permit for main
codes.This problem was solved .Now everybody can easily access and work on Cordic
Algorithm.
There are less examples about FFT on FPGA Board.It is a big problem for
developers.Problem will be solved after this project finished.
In FFT examples are insufficient due to speed and efficiency . This must be improved.

Reference Material
We worked on VHDL programming.
http://ece477.cankaya.edu.tr/course.php?page=Lecture%20Notes
https://reference.digilentinc.com/_media/basys3:basys3_rm.pdf
page 4 of 17

Developing Fast Fourier Transform Algorithm On FPGA Board With
Optimum Performance Design Report

We studied FFT algorithm on our advisors lecture notes.

Swain, S.R., Patnaik, S.K.: " Design And Implementation Of CORDIC Algorithm
Using VHDL". International Journal of Emerging Trends in Electrical and Electronics, 2015
Manjunath.C.R.: " FPGA Implementation of Sine and Cosine Value Generators using CORDIC Design
for Fixed Angle Rotation". International Journal of Computer Applications (0975 – 8887), 2014

Design
Features and Specifications
In the project, the working logic for FFT Algorithm was listed.
- 2^n based discrete input array is given from user.
-Even and odd functions will be seperated from input.
- The FFT calculation given in below schematic starts to calculate FFT.

-For calculating complex exponential terms, the Cordic Algorithm will calculate cosine and sine
values.
-Due to Euler's Formula, the cosine values represents the real values of complex exponential term
and sine values represents the imaginary values of complex exponential terms.
-In order to calculate FFT, the DFT formula is given below can be used for calculating FFT.

page 5 of 17

Developing Fast Fourier Transform Algorithm On FPGA Board With
Optimum Performance Design Report

Design Overview
In the figure below , the block diagram of the FFT Algorithm was given.

Detailed Design Description
Cordic Algorithm

This algorithm was specially developed for real time digital computers where the majority of the
computation involves trigonometric relationships. This CORDIC algorithm can be implemented using
special arithmetic units such as shift registers, adders, subtractors and special interconnect. This
algorithm is derived from general rotation transform as given below:
X' = Xcos(Ø) - Ysin(Ø)
Y' = Ycos(Ø) + Xsin(Ø)

(1)
(2)

Taking cos(Ø) out, “(1)” and “(2)” can be rewritten as:
X' = cos(Ø)[X - Y * tan(Ø)]
Y' = cos(Ø)[Y + X * tan(Ø)]

(3)
(4)

By replacing tan(Ø) by ±
the multiplications in “(3)” and “(4)” can be replaced simple by shift operations.
The value of tan(Ø) is given in Table I.

page 6 of 17

Developing Fast Fourier Transform Algorithm On FPGA Board With
Optimum Performance Design Report

With this modification, “(3)” and “(4)” can be rewritten as:

where

Removing the scaling factor, iteration is simple shift-add equation. The value of Ki approaches to
0.607 as the iteration count approaches infinity , . The direction in which way the vector should
rotate is expressed as:

where

To understand the iterative operation of this rotational CORDIC algorithm, consider an example: angle
Z˳ = 30.0º . Through iterative method the known angles i.e. tan
in order to reach near the given angle. Once this is achieved, the sine and cosine of the given angle can
be obtained. Fig.1 pictorially shows the iteration process.

page 7 of 17

Developing Fast Fourier Transform Algorithm On FPGA Board With
Optimum Performance Design Report

Fig.1: Iteration process of the CORDIC algorithm

The iteration process is as given below, Let us start with the initial angle of 45.0 º

After eight iterations, the angle which is obtained is 30.0 º as given below,

Through this process, the sine and cosine of the 30.0 º can be obtained. This process is also applicable
for any angle from 0 º to 90 º. The design steps used for CORDIC processor are given below:
Step1: Read the angle Z˳ whose sine and cosine functions are to be determined

page 8 of 17

Developing Fast Fourier Transform Algorithm On FPGA Board With
Optimum Performance Design Report

As is evident from the above design steps, the design of CORDIC processor needs basically three
operations: addition, subtraction and shifting, therefore, require very less hardware to implement it in
FPGA. This also makes the coding complexity comparatively simple , . The flow chart
representation of this CORDIC algorithm is given in Fig. 2. In this flow chart, it is clearly shown, how
adder/subtractor and shifting operations are used to obtain the sine and cosine of a given angle.

Fig.2: Flow chart for the CORDIC algorithm
page 9 of 17

#### HTML Code

Copy the following HTML code to share your document on a Website or Blog

#### QR Code ### Related keywords 