**UPGRADE YOUR BROWSER**

We have detected your current browser version is not the latest one. Xilinx.com uses the latest web technologies to bring you the best online experience possible. Please upgrade to a Xilinx.com supported browser:Chrome, Firefox, Internet Explorer 11, Safari. Thank you!

Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Community Forums
- :
- Forums
- :
- Intellectual Property
- :
- DSP IP and Tools
- :
- Re: 8 point FFT in verilog

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

shamanth

Observer

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

05-03-2009 11:02 AM

30,122 Views

Registered:
03-09-2008

Hi everyone,

For an academic project I want to implement an 8 point FFT (for 8-bit signed input data) in verilog. I have the verilog source code of a radix 2 butterfly processor from the book DSP with FPGA by Uwe Meyer-Baese. It is for decimation in frequency. I have implemented the 8 point FFT by instantiating this source code 12 times following the structure of 8 pt FFT.

I am not sure how the numbers are represented on the bit level in this code as in if the inputs are direct decimal values of their binary representation or if it is scaled for 7/8 bits.

Also the code "scales" the output to prevent overflow by right shifting the outputs by one bit.

So if I use this code as is for 8 point, it effectively divides my input data by 8 as it moves through 3 stages for the part which is not multiplied with the twiddle factor.

Also the twiddle factor multiplier used in it provides a similarly scaled output.

So I am pretty confused as to how should the data be represented so I could compare my results with matlab correctly.

Can anyone please help me in this regard?

Thank you.

Shamanth.

1 Solution

Accepted Solutions

sudarshano

Observer

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

05-18-2009 06:45 AM

35,486 Views

Registered:
04-16-2009

See my answers inline

//The complex multiplier used in the code for the twiddle factor multiplication takes in cos(8bit), cos+sin(9bit), and cos-sin(9-bit) factors for the //computation and provides the product by picking the bits 15:8 from the actual output of 16:0. This I suppose is the rounding/truncation. But this //seems to scale the product down by a factor of 2(in addition to the scaling down by 2 due to the bfproc module before it enters the multiplier).

There are some misinterpretations in your above post.

1. Truncation/Rounding is never done at MSBs .

2. if you select 15:8 from 16:0 it is eqvivalent to left shift i.e., scale up by 2 and not scale down.

Now , lets move to point of 15:8 from 16:0 . This done to remove extra sign bit . In your bfly , i assume, cos+sin(9bit) and sample is 8 bit so multiplication will result into 17 bit . The resulting 17 bits has 2 sign bits and 15 fractional bits. So i think this left shift is done to remove the sign bit. Thats what i understand for your post. Please check this against your implementation.

// So do I need to compensate for this scaling by left shifting the bits at every stage or at the last stage or should I simply connect the radix2 //butterfly without any logic between them and just use the scale down the matlab output by 8 for comparison?

Well if my answer to previous question is correct then you need not scale.

//Also how should i represent/scale the complex multiplier factors? since cos is 8 bits while cos+sin and cos-sin are 9 bits to prevent overflow. I //am assuming the first 2 MSB s of the 9bit cps and cms will both be sign bits? i.e. 9th bit will be sign extended? So what would these factors be //if my twiddle factor is say -0.7-j0.7 which gives me

//cos= -.07,

//cos+sin= -1.4

//and cos - sin = 0.

cos+sin is 9 bits and 2MSBs need not be sign bits. when |result| is > 1 then 1 is sign bit and next is integer bit .

Only when |result| is < 1 then sign extension takes place.

cos+sin will be -1.4*2^7 = 10.1001100

Hope i was able to clear some your doubts, (or did i increase :smileyhappy:?) .

16 Replies

sudarshano

Observer

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

05-06-2009 04:18 AM

30,073 Views

Registered:
04-16-2009

Re: 8 point FFT in verilog

Since you have chosen 8bit as wordlength you can choose 1.7 fixed point format. 1.7 means 1 sign bit and 7 fractional bits. So range will from -1 to .99 in steps of 2^-7 . Make sure all i/p samples are in this range.

First you need to convert the 8 i/p samples to be fed into FFT block into 1.7 format , just multply decimal value by 2^7 you will get 8 bit signed number. Then start FFT . Once outputs are available scale up by 8, this result you can compare with MatLab results.

shamanth

Observer

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

05-06-2009 10:14 AM

30,065 Views

Registered:
03-09-2008

Re: 8 point FFT in verilog

Thank you sudarshano. This seems to make a lot of sense now.

I had one more question.

The complex multiplier used in the code for the twiddle factor multiplication takes in cos(8bit), cos+sin(9bit), and cos-sin(9-bit) factors for the computation and provides the product by picking the bits 15:8 from the actual output of 16:0. This I suppose is the rounding/truncation. But this seems to scale the product down by a factor of 2(in addition to the scaling down by 2 due to the bfproc module before it enters the multiplier).

So do I need to compensate for this scaling by left shifting the bits at every stage or at the last stage or should I simply connect the radix2 butterfly without any logic between them and just use the scale down the matlab output by 8 for comparison?

Also how should i represent/scale the complex multiplier factors? since cos is 8 bits while cos+sin and cos-sin are 9 bits to prevent overflow. I am assuming the first 2 MSB s of the 9bit cps and cms will both be sign bits? i.e. 9th bit will be sign extended? So what would these factors be if my twiddle factor is say -0.7-j0.7 which gives me

cos= -.07,

cos+sin= -1.4

and cos - sin = 0.

Sorry for being too specific. But any help would be greatly appreciated.

Thank you for your time.

Shamanth.

sudarshano

Observer

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

05-18-2009 06:45 AM

35,487 Views

Registered:
04-16-2009

See my answers inline

//The complex multiplier used in the code for the twiddle factor multiplication takes in cos(8bit), cos+sin(9bit), and cos-sin(9-bit) factors for the //computation and provides the product by picking the bits 15:8 from the actual output of 16:0. This I suppose is the rounding/truncation. But this //seems to scale the product down by a factor of 2(in addition to the scaling down by 2 due to the bfproc module before it enters the multiplier).

There are some misinterpretations in your above post.

1. Truncation/Rounding is never done at MSBs .

2. if you select 15:8 from 16:0 it is eqvivalent to left shift i.e., scale up by 2 and not scale down.

Now , lets move to point of 15:8 from 16:0 . This done to remove extra sign bit . In your bfly , i assume, cos+sin(9bit) and sample is 8 bit so multiplication will result into 17 bit . The resulting 17 bits has 2 sign bits and 15 fractional bits. So i think this left shift is done to remove the sign bit. Thats what i understand for your post. Please check this against your implementation.

// So do I need to compensate for this scaling by left shifting the bits at every stage or at the last stage or should I simply connect the radix2 //butterfly without any logic between them and just use the scale down the matlab output by 8 for comparison?

Well if my answer to previous question is correct then you need not scale.

//Also how should i represent/scale the complex multiplier factors? since cos is 8 bits while cos+sin and cos-sin are 9 bits to prevent overflow. I //am assuming the first 2 MSB s of the 9bit cps and cms will both be sign bits? i.e. 9th bit will be sign extended? So what would these factors be //if my twiddle factor is say -0.7-j0.7 which gives me

//cos= -.07,

//cos+sin= -1.4

//and cos - sin = 0.

cos+sin is 9 bits and 2MSBs need not be sign bits. when |result| is > 1 then 1 is sign bit and next is integer bit .

Only when |result| is < 1 then sign extension takes place.

cos+sin will be -1.4*2^7 = 10.1001100

Hope i was able to clear some your doubts, (or did i increase :smileyhappy:?) .

shamanth

Observer

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

05-18-2009 01:39 PM

29,889 Views

Registered:
03-09-2008

Re: 8 point FFT in verilog

@ sudarshano -

Your response seems to have cleared many of my doubts now :) I will try to implement the FFT with this information now and will see if it makes any difference. And will post more ifI have anymore questions.

Thank you for time and effort.

Sincerely,

Shamanth S. Huddar

rinheart

Newbie

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

09-24-2009 01:06 AM

28,337 Views

Registered:
09-24-2009

Re: 8 point FFT in verilog

Hi shamanth,

I'm also currently implementing the FFT into fpga in verilog and was wondering if you could guide me in instantiating the 12 butterflies?

I have the source code from uwe's book too and i was hoping if you could give me a step by step guide to perform this instantiation.

I've been stuck here for some time and i hope to get on with this so i can continue on with the ifft part.

Hope to hear from you as soon as possible as time is not on my side.

Rin

san51

Newbie

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

11-08-2009 03:50 AM

27,912 Views

Registered:
11-08-2009

Re: 8 point FFT in verilog

can anyone send me the code for 8 point fft....

i'm new 2 vhdl..... need it urgently for my project...

san51

Newbie

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

11-08-2009 03:52 AM

27,911 Views

Registered:
11-08-2009

Re: 8 point FFT in verilog

do anyone know how to use floating point values in vhdl...

maniftm

Newbie

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

09-25-2010 03:53 AM

25,154 Views

Registered:
09-25-2010

Re: 8 point FFT in verilog

Hello boss....

now i am doing the project in FFT-verilog..Can you able to send the coding for FFT - verilog... I am waiting for your reply.....Please send to given mail id: mani10287@gmail.com

balajitiger

Visitor

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-04-2011 06:04 AM

22,074 Views

Registered:
10-04-2011

Re: 8 point FFT in verilog

ywu

Xilinx Employee

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-04-2011 09:16 PM

9,635 Views

Registered:
11-28-2007

Re: 8 point FFT in verilog

Consult any DSP book or google it and you will find the formula for calculating the twiddle factor.

@balajitiger wrote:

Cheers,

Jim

Jim

balajitiger

Visitor

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-05-2011 10:18 AM

9,631 Views

Registered:
10-04-2011

Re: 8 point FFT in verilog

ywu

Xilinx Employee

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-05-2011 09:37 PM

9,627 Views

Registered:
11-28-2007

Re: 8 point FFT in verilog

Fixed point numbers are generally used for DSP applications targetting FPGA. Take a look at the page below to see how fixed point numbers work.

http://en.wikipedia.org/wiki/Fixed-point_arithmetic

@balajitiger wrote:

Cheers,

Jim

Jim

ajaykumar2689

Newbie

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-12-2012 06:02 AM

9,462 Views

Registered:
03-12-2012

Re: 8 point FFT in verilog

Highlighted
##

Jump to solution

davidzhangca

Observer

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-08-2013 08:11 AM

8,783 Views

Registered:
12-11-2007

Re: 8 point FFT in verilog

hi there,

I am new to DSP.

Sudarshano wrote:

*Since you have chosen 8bit as wordlength you can choose 1.7 fixed point format. 1.7 means 1 sign bit and 7 fractional bits. So range will from -1 to .99 in steps of 2^-7 . Make sure all i/p samples are in this range.*

*First you need to convert the 8 i/p samples to be fed into FFT block into 1.7 format , just multply decimal value by 2^7 you will get 8 bit signed number. Then start FFT . Once outputs are available scale up by 8, this result you can compare with MatLab results.*

* *

my question is: why the output need to be scaled up by 8 when compares with matlab result?

David Z.

sharmi703@gmail.com

Visitor

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-26-2015 03:01 AM

5,996 Views

Registered:
03-24-2015

Re: 8 point FFT in verilog

Hi,

I have created 8 point fft v7.1 logicore 12.3..

simulation has happened.. but all my outputs are zero... its taking my input which ever im giving..i ll put my code n output waveform... can anyone pls help???

**Test bench code**

module tb;

always

begin

clk =1;

#10;

clk =0;

#10;

end

// Inputs

reg clk;

reg start;

reg [31:0] xn_re;

reg [31:0] xn_im;

reg fwd_inv;

reg fwd_inv_we;

// Outputs

wire rfd;

wire [2:0] xn_index;

wire busy;

wire edone;

wire done;

wire dv;

wire [2:0] xk_index;

wire [31:0] xk_re;

wire [31:0] xk_im;

// Instantiate the Unit Under Test (UUT)

fft1 uut (

.clk(clk),

.start(start),

.xn_re(xn_re),

.xn_im(xn_im),

.fwd_inv(fwd_inv),

.fwd_inv_we(fwd_inv_we),

.rfd(rfd),

.xn_index(xn_index),

.busy(busy),

.edone(edone),

.done(done),

.dv(dv),

.xk_index(xk_index),

.xk_re(xk_re),

.xk_im(xk_im)

);

initial begin

// Initialize Inputs

clk = 0;

start = 0;

xn_re = 0;

xn_im = 0;

fwd_inv = 0;

fwd_inv_we = 0;

// Wait 100 ns for global reset to finish

#100;

start = 1;

fwd_inv = 1;

fwd_inv_we = 0;

// Add stimulus here

//#20;

xn_re = 32'b01000000000000000000000000000000; // 2

xn_im = 0;

#20;

xn_re = 32'b01000000100000000000000000000000; //------ 4

xn_im = 0;

#20;

xn_re = 32'b01000000111000000000000000000000; //------ 7

xn_im = 0;

#20;

xn_re = 32'b01000001000100000000000000000000; //------9

xn_im = 0;

//#20;

//xn_re = 32'b01000000010000000000000000000000; //------ 3

//xn_im = 0;

//#20;

//xn_re = 32'b01000001001000000000000000000000; //------ 10

//xn_im = 0;

//#20;

//xn_re = 32'b01000001010000000000000000000000; //------ 12

//xn_im = 0;

// #20;

//xn_re = 32'b01000001011100000000000000000000; //------ 15

//xn_im = 0;

end

endmodule

**Main module**

module fft1(clk,start,xn_re,xn_im,fwd_inv,fwd_inv_we,rfd,xn_index,busy,edone,done,dv,xk_index,xk_re,xk_im);

input [31:0] xn_re,xn_im;

input clk,start,fwd_inv,fwd_inv_we;

output [31:0] xk_re,xk_im;

output [2:0] xn_index,xk_index;

output rfd,busy,done,edone,dv;

reg ce=1,sclr=0;

wire [31:0] xk_re,xk_im;

fft1_ip a1(

.clk(clk),

.start(start),

.ce(ce),

.sclr(sclr),

.xn_re(xn_re),

.xn_im(xn_im),

.fwd_inv(fwd_inv),

.fwd_inv_we(fwd_inv_we),

.rfd(rfd),

.xn_index(xn_index),

.busy(busy),

.edone(edone),

.done(done),

.dv(dv),

.xk_index(xk_index),

.xk_re(xk_re),

.xk_im(xk_im)

);

endmodule

fadi_7878

Newbie

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

06-07-2015 04:55 AM

5,402 Views

Registered:
06-07-2015

Re: 8 point FFT in verilog