bart wrote:

>I need 1000 frequency "bins", where each bin is a descrete frequency.
>As Thomas Womack pointed out above, it is beter defined as a N-point
>DFT with 1000 frequency bins, where N = 1024.  For each sample, every
>microsecond, there is 24-bits of data lets call that x(n).  During that
>microsecond there must be 1000 MACS in parallel to calculate the N=1024
>DFT.  This would happen for 1024 samples to calculate the N-point DFT.
>I hope that is a better description.  Thanks for the  input.
>
>  
>
Bart, as others have pointed out, it sounds like you are doing a brute 
force DFT.  The FFT reduces the computations by exploiting symmetry 
present in the evenly spaced bins.  Most FFTs are done with a variation 
of the Cooley-Tukey algorithm which factors DFTs with a power of 2 
number of points by successively breaking the DFT into half sized DFTs 
and combining the results with a phase rotation.  Your post seems to 
indicate that you are looking instead for a 1000 point transform.  You 
can either use a 1024 point FFT by padding the input data to fill out 
the size and accepting the slightly smaller bin size, or if you need the 
1000 point DFT, you can use some of the other FFT algorithms to arrive 
at a 1000 point transform.  Either way, you'll greatly reduce the number 
of multiplies by using a Fast Fourier Transform instead of the DFT.  The 
Smith and Smith book ( 
http://www.amazon.com/exec/obidos/ASIN/0780310918/andraka/102-8981403-3626538 
) provides a pretty good coverage of the various FFT algorithms that 
you'd need for either approach.  It is presented more from a software 
perspective than from hardware, but nevertheless it provides a 
comprehensive background to permit you to build a hardware 
implementation that is far more efficient than what you are proposing.

The other point I should make is that you can use a process clock that 
is faster than your sample clock, which I think you said is only 1 MHz.  
Our FFT cores will run at over 300 MS/sec in current FPGA devices, and 
they don't use anywhere near the 1000 multiplies you are looking at.

-- 
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930     Fax 401/884-7950
email ray@andraka.com  
http://www.andraka.com  

 "They that give up essential liberty to obtain a little 
  temporary safety deserve neither liberty nor safety."
                                          -Benjamin Franklin, 1759

Maybe I misspoke. I meant to say that a cicuit that runs at a fraction
of its speed capabilty can be miade to do multiple jobs sequentially.
That obviously only applies when the designer runs the circuitry at
half or quarter speed or less. Only then can you seriously think about
time-sharing or time multiplexing.

it's good to have friends who watch over me  :-)
Peter Alfke

On 4 May 2005 10:28:15 -0700, "Peter Alfke" <peter@xilinx.com> wrote:

>Remember, any circuit that does not work close to its speed limit
>represents waste.
>Peter Alfke

Designing close to the limit is a nice idea.  But unless the part has
been completely and correctly characterized by the vendor, designing
too close to its speed limit can be fatal.  Having been burnt by speed
files that changed for the worse after I'd completed a design, I now
try to keep a healthy margin between my design requirements and the
speed limit du jour.

Bob Perlman
Cambrian Design Works

Peter Alfke wrote:

>Remember, any circuit that does not work close to its speed limit
>represents waste.
>Peter Alfke
>
>  
>
Peter, while this is true from a device utilization standpoint, there is 
also development time, life cycle costs etc to consider.  For someone 
that is not well versed in the nuances, this sometimes significant cost 
can weigh in favor of a larger design clocked at a relatively slow clock.

-- 
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930     Fax 401/884-7950
email ray@andraka.com  
http://www.andraka.com  

 "They that give up essential liberty to obtain a little 
  temporary safety deserve neither liberty nor safety."
                                          -Benjamin Franklin, 1759

Hi Peter,

> that's the problem with glaring generalizations: there always are
> exceptions.

Us in apps do tend to mostly see the corner cases - extreme speed, extreme
size, trying to shoehorn that last MHz out of the silicon while trying to
shoehorn a few hundred extra lines of code into the silicon etc. I'm
getting the feeling that we tend to see the exceptions, more than the rule.

In the last two years I have seen, with the introduction of Cyclone and
(slightly less so) Spartan 3, the performance bar at the lower end of the
spectrum has been raised considerably. The amount of performance and
capacity that is available for under $10 nowadays is just amazing compared
to three years ago.

It's a fun field we're working in.

Best regards,


Ben

Ben,
that's the problem with glaring generalizations: there always are
exceptions.
Peter Alfke

Hi Peter,

> Remember, any circuit that does not work close to its speed limit
> represents waste.

Well, I've seen a fair share of 15-25ns CPLD designs, filled 60% and running
at 4 or 8MHz. Sometimes applications can simply be slow. And developed,
debugged and programmed in under an hour and a half. And, especially
nowadays, without a smaller or slower part that is any cheaper.

But, that's good, isn't it? It would be horrible if the lower end of the
market couldn't take advantage of modern technology.

Best regards,


Ben

Bart,
consider time / frequency as a third dimension. You have a certain job
to do in a given time. Then look at the perforamnce of your multiplier,
registers, etc, and you find that they will work at multiple 100 MHz.
Then get creative and do certain things sequentially, and other things
in parallel. You have an enormous amount of creative freedom, and
pipelining is essentially free in an FPGA.
Remember, any circuit that does not work close to its speed limit
represents waste.
Peter Alfke

I need 1000 frequency "bins", where each bin is a descrete frequency.
As Thomas Womack pointed out above, it is beter defined as a N-point
DFT with 1000 frequency bins, where N = 1024.  For each sample, every
microsecond, there is 24-bits of data lets call that x(n).  During that
microsecond there must be 1000 MACS in parallel to calculate the N=1024
DFT.  This would happen for 1024 samples to calculate the N-point DFT.
I hope that is a better description.  Thanks for the  input.