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!

cancel
Showing results for
Did you mean:
Observer
30,122 Views
Registered: ‎03-09-2008

## 8 point FFT in verilog

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.

Thank you.

Shamanth.

1 Solution

Accepted Solutions
Observer
35,486 Views
Registered: ‎04-16-2009

## Re: 8 point FFT in verilog

//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
Observer
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.

Observer
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.

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.

Shamanth.

Observer
35,487 Views
Registered: ‎04-16-2009

## Re: 8 point FFT in verilog

//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:?) .

Observer
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

Newbie
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
Newbie
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...

Newbie
27,911 Views
Registered: ‎11-08-2009

## Re: 8 point FFT in verilog

do anyone know how to use floating point values in vhdl...
Newbie
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

Visitor
22,074 Views
Registered: ‎10-04-2011

## Re: 8 point FFT in verilog

i am currently working on a project to implement fft in spartan 3an.i tried a lot but doesn't know how to calculate the twiddle factor.so can plz mail me ur code.it will be very useful to me.my id is balaji1707@gmail.com.thanks in advance............

Xilinx Employee
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:

i am currently working on a project to implement fft in spartan 3an.i tried a lot but doesn't know how to calculate the twiddle factor.so can plz mail me ur code.it will be very useful to me.my id is balaji1707@gmail.com.thanks in advance............

Cheers,
Jim
Visitor
9,631 Views
Registered: ‎10-04-2011

## Re: 8 point FFT in verilog

thank u sir. i tried a lot of searching in google but can't able to find the solution. the problem is i don't know how to use the value like 0.707 in verilog or tell me how to calculate the twiddle factors.

Xilinx Employee
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:

thank u sir. i tried a lot of searching in google but can't able to find the solution. the problem is i don't know how to use the value like 0.707 in verilog or tell me how to calculate the twiddle factors.

Cheers,
Jim
Newbie
9,462 Views
Registered: ‎03-12-2012

## Re: 8 point FFT in verilog

i need fft vhdl code for my project ...its urgent..i tried opencores codes but they are full of errors..can any body suggest any links for codes...thanks in advance

Highlighted
Observer
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.

Tags (1)
Visitor
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;

//#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

Newbie
5,402 Views
Registered: ‎06-07-2015