very simple question on Cos and Sin

[aj]

Dear all,
I am implementing 2048 point FFT on virtex pro using VHDL and to start
with i am trying to implement radix 4 FFT.. I am new to vhdl, and i am
stuck at this simple problem

* Please tell me how will i implement twiiddle factors
like it is
(Wbase N)to power nk)= twidle= e to d power -( 2*pi*n*k/N) =
cos(2*pi*nk/N) -j*sin(2*pi*nk/N)
i am just implementing this but i am getting this error

* Error: C:/Xilinx/Project/RAM/radix 4.vhdl(57): Unknown identifier
'sin'.
** Error: C:/Xilinx/Project/RAM/radix 4.vhdl(57): Unknown identifier
'cos'.
** Error: C:/Xilinx/Project/RAM/radix 4.vhdl(57): Bad expression.
** Error: C:/Xilinx/Project/RAM/radix 4.vhdl(57): Bad expression.
** Error: C:/Xilinx/Project/RAM/radix 4.vhdl(57): Bad expression.
** Error: C:/Xilinx/Project/RAM/radix 4.vhdl(57): Bad right hand side
(infix expression) in signal assign


------------------------------------------------------------------------------------------------------
MY Questions------------------>
------------------------------------------------------------------------------------------------------
Q1. I am also bit confused what value will i give to "j". i know " j" =
square root of -1. so what value shall i put in my program...

Q2. please clear my concepts for this twiddle factor, Please tell me
the easiest way to implement twiddle factors. as i am stuck.... as i
have to implement much bigger like 2048 point FFT

My program is giving me error.... if i use cos and sin functionsl...
for default i have given j as a value of -1

-------------------------------------------------------------------------------------------------------------------------------------------
library ieee;
use ieee.std_logic_1164.all;
USE ieee.std_logic_arith.ALL;
USE ieee.std_logic_unsigned.ALL;
use ieee.numeric_std.all;

entity r4 is
generic(
width : integer :=8);


port
( i : in std_logic_vector(width-1 downto 0);
iout : out std_logic_vector(width+1 downto 0);
clock,reset : in std_logic;
ram_read : in bit;
ram_write : in bit
);
end r4;

architecture arch_r4 of r4 is

type ram_data is array (3 downto 0) of std_logic_vector(7 downto 0);
signal tramA : ram_data;
signal tramB : ram_data;

begin

process(clock,reset,ram_write)

variable ram_mem :std_logic_vector( 7 downto 0 );
begin
if ( clock ='1' and clock'event) then
if (ram_write = '1') then
ram_mem := i(7 downto 0);

end if ;

end if ;
end process;
--------------------------------------------------------------





--tx(0) := ((ta(0) + ta(2)) - ( ta(1) + ta(3)));
--tx(1) := ((ta(0) + ta(2)) - ( ta(1) + ta(3))) * (cos( 2*3.14/3) -j *
sin( 2* 3.14/3));
--tx(2) := ((ta(0) - ta(2)) - ( ta(1) - ta(3))) * (cos( 4*3.14/3) -j *
sin( 4* 3.14/3));
--tx(3) := ((ta(0) - ta(2)) + ( ta(1) - ta(3))) * (cos( 6*3.14/3) -j *
sin( 6* 3.14/3));
--------------------------------------------------------------------------
calculaterocess(clock)
variable j : integer:=- 1;
begin

if ( clock ='1' and clock'event) then

if (ram_read ='1') then

tramB(0)<=(tramA(0) + tramA(2)) + ( tramA(1) + tramA(3));
tramB(1)<=(tramA(0) + tramA(2)) - ( tramA(1) + tramA(3))* (cos(
2*3.14/3) -j * sin( 2*3.14 /3));
tramB(2) <=(tramA(0) - tramA(2)) - ( tramA(1) - tramA(3))*(cos(
4*3.14/3) -j * sin( 4* 3.14/3));
tramB(3) <=(tramA(0) - tramA(2)) + ( tramA(1) - tramA(3))*(cos(
6*3.14/3) -j * sin( 6* 3.14/3));
end if;

end if;
end process calculate;
end arch_r4;

 

[jens]

Xilinx has an FFT core that can already do what you're trying to do,
and it can be optimized for size or speed.

If you really want to do it yourself, starting with a good DSP book is
a good idea, my favorite is Understanding Digital Signal Processing by
Richard Lyons.

 

[Andy Peters]

aj wrote:
-------------------------------------------------------------------------------------------------------------------------------------------

library ieee;
use ieee.std_logic_1164.all;
USE ieee.std_logic_arith.ALL;
USE ieee.std_logic_unsigned.ALL;
use ieee.numeric_std.all;

Why both numeric_std and std_logic_arith?

entity r4 is
generic(
width : integer :=8);

 

[aj]

se ieee.std_logic_1164.all;
--USE ieee.std_logic_arith.ALL;
USE ieee.std_logic_unsigned.ALL;
use ieee.numeric_std.all;

Dear Andy even if i remove arith_all; the problem is still there.
I just wanted to know how to implement these cos and sin functions in
vhdl...
and what about twiddle factors.. what do i need to do?
I would seriously be very much thankfull if you just go into the code
and tell me where ami wrong.. coz i am stuck here... and I have a long
long way to go once this thing gets clear.

and Jens i am totally aware that Xilinx core generators can do the same
thing. but my project leader wants me to do this by my self.
i will seriously try to get hold of that DSP book. but please just
check the code...
what do i need to do for the " J " in the twiddle equation i.e
[cos(2pi*k/N) -j sin(2pi*k/N)] any small help will be appreciated

 

[aj]

library ieee;

USE ieee.std_logic_arith.ALL;
USE ieee.std_logic_unsigned.ALL;
use ieee.numeric_std.all;

 

[Nicolas Matringe]

aj a écrit:

I just wanted to know how to implement these cos and sin functions in
vhdl...

sin and cos are defined in the ieee.math_real package but this package
is NOT synthesizable.
The usual way to generate trigonometric functions is to use a CORDIC
generator (look for Ray Andraka's posts on this topic)

Nicolas

 

[Andy Peters]

aj wrote:

se ieee.std_logic_1164.all;
--USE ieee.std_logic_arith.ALL;
USE ieee.std_logic_unsigned.ALL;
use ieee.numeric_std.all;

Dear Andy even if i remove arith_all; the problem is still there.

You need to get rid of std_logic_unsigned, too. Forget those packages
even exist.

I just wanted to know how to implement these cos and sin functions in
vhdl...

They're in the real math package, which is not synthesizable ...

=-a

 

[jens]

Are you allowed to use any cores? If so, Xilinx has a CORDIC core, and
their DDS core might also suit your needs. Otherwise, make your own
previously mentioned CORDIC or a look-up table (if you have enough
memory or access to external memory). A look-up table would be the
easiest way if you have to do it all yourself. It's been too long
since I've looked at an actual FFT implementation, but the key is to
pre-calculate as much as you can before you do an FFT.

To get the "j", use the square root function of the CORDIC core, and
use -1 as the input.

Just kidding! You'll need to use complex numbers, you can make a
complex record type for ease of use. The Understanding Digital Signal
Processing book has an excellent review of complex number and their
operations.

 

[Arnaud]

If you can't use any cordic core generated by Coregen, the best is to
address tables (ROMs) containing the values of the sines and cosines.

Say if you want to compute sin(2), you'll put the value of sin(2) in
the ROM at the address and then use the address port to generate the
right value. This method is also very commonly used in digital signal
processing to compute the value of arctan(I/Q) when you want to compute
phase errors. The size of the tables will depend on the precision you
want to obtain for your results. This is the problem when switching
from floats to fixed values. You have to define by yourself how to
reframe your numbers and which dynamix you want to keep for addressing
the ROMs.

For the complex values, you'll have to compute both real and imaginary
parts separatly.

For instance if you want to compute (x1 + j*y1) * (x2 + j*y2),

you'll compute (x1 * x2 - y1 * y2) for the real part, and (x1 * y2 + x2
* y1) for the imaginary part. Then you'll know that your result is to
be (x1 * x2 - y1 * y2) + j* (x1 * y2 + x2 * y1).

As Jens says, the key is to pre-calculate as much as you can before you
do the FFT. And particularly for knowing which values to store in the
ROMs and how to address them (how thin your addressing scheme must be)

Hope this helps.

 

As an alternative to pre-calculating trig tables or using general
CORDIC routines, another possibility you should consider is to generate
the trig functions on the fly using an iterative generation scheme.
There, you are exploiting the fact that you need sine and cosine not
for a random set of angles, but for a regular arithmetic sequence. A
good reference comparing many different schemes is:

Manfred Tasche and Hansmartin Zeuner, "Improved roundoff error analysis
for precomputed twiddle factors," J. Computational Analysis and
Applications 4 (1), 1-18 (2002).

The tradeoff here is that such schemes generally sacrifice some
accuracy, but this can be compensated for somewhat by using higher
precision for generating the trig values as compared to the rest of the
computations.

Cordially,
Steven G. Johnson

 

[james]

On 23 Dec 2005 05:10:13 -0800, "aj" <aj.bohra@gmail.com> wrote:

+<se ieee.std_logic_1164.all;
+<--USE ieee.std_logic_arith.ALL;
+<USE ieee.std_logic_unsigned.ALL;
+<use ieee.numeric_std.all;
+
+<Dear Andy even if i remove arith_all; the problem is still there.
+<I just wanted to know how to implement these cos and sin functions in
+<vhdl...
+<and what about twiddle factors.. what do i need to do?
+<I would seriously be very much thankfull if you just go into the code
+<and tell me where ami wrong.. coz i am stuck here... and I have a long
+<long way to go once this thing gets clear.
+
+<and Jens i am totally aware that Xilinx core generators can do the same
+<thing. but my project leader wants me to do this by my self.
+<i will seriously try to get hold of that DSP book. but please just
+<check the code...
+<what do i need to do for the " J " in the twiddle equation i.e
+<[cos(2pi*k/N) -j sin(2pi*k/N)] any small help will be appreciated
*****

Why don't you use a power series instead to compute SIN and COS?


james