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 421 times.

File size: 574.09 KB (17 pages).

Privacy: public file

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

Advisor: ASSOC. PROF. ORHAN GAZI

Cankaya University

Ankara, TURKEY

page 1 of 17

Copyright Digilent, Inc. All rights reserved. Other product and company names mentioned may be trademarks of their respective owners.

Developing Fast Fourier Transform Algorithm On FPGA Board With

Optimum Performance Design Report

PRODUCT MARKETING SHEET

page 2 of 17

Copyright Digilent, Inc. All rights reserved. Other product and company names mentioned may be trademarks of their respective owners.

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[1], 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 [12].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

Copyright Digilent, Inc. All rights reserved. Other product and company names mentioned may be trademarks of their respective owners.

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 AD2

Pmod DA1 KIT

Tools Required

•

•

•

•

•

•

MATLAB

ISE

VIVADO

Pmod DA1 KIT

Pmod AD2

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

We made a research about BASYS 3.

https://reference.digilentinc.com/_media/basys3:basys3_rm.pdf

page 4 of 17

Copyright Digilent, Inc. All rights reserved. Other product and company names mentioned may be trademarks of their respective owners.

Developing Fast Fourier Transform Algorithm On FPGA Board With

Optimum Performance Design Report

We studied FFT algorithm on our advisors lecture notes.

http://ece310.cankaya.edu.tr/uploads/files/ece310Lec8%282%29.pdf

We made a research about Cordic Algorithm.

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

Copyright Digilent, Inc. All rights reserved. Other product and company names mentioned may be trademarks of their respective owners.

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

Copyright Digilent, Inc. All rights reserved. Other product and company names mentioned may be trademarks of their respective owners.

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 [1], [3]. 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º [4]. Through iterative method the known angles i.e. tan

are either added or subtracted

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

Copyright Digilent, Inc. All rights reserved. Other product and company names mentioned may be trademarks of their respective owners.

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

Copyright Digilent, Inc. All rights reserved. Other product and company names mentioned may be trademarks of their respective owners.

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 [4], [5]. 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

Copyright Digilent, Inc. All rights reserved. Other product and company names mentioned may be trademarks of their respective owners.

dogan_memisoglu__bilgehan_aktepe.pdf (PDF, 574.09 KB)

Download PDF

Use the permanent link to the download page to share your document on Facebook, Twitter, LinkedIn, or directly with a contact by e-Mail, Messenger, Whatsapp, Line..

Use the short link to share your document on Twitter or by text message (SMS)

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

This file has been shared publicly by a user of

Document ID: 0000596144.