Forums

Goertzel Algorithm

Started by lars...@gmail.com May 5, 2005
I have recently read about the Goertzel algorithm and I am looking to
use it in a FPGA/DSP.  The problem is I am interested in using the
algorithm to compute about 1000 frequency bins during a microsecond
period, so I am very interested in its performance in hardware to help
me select a device.  Does anyone know where I can find some info on the
performance of the Goertzel algorithm in an FPGA.  Thanks in advance.

larsonbr@gmail.com wrote:
> I have recently read about the Goertzel algorithm and I am looking to > use it in a FPGA/DSP. The problem is I am interested in using the > algorithm to compute about 1000 frequency bins during a microsecond > period, so I am very interested in its performance in hardware to help > me select a device. Does anyone know where I can find some info on the > performance of the Goertzel algorithm in an FPGA. Thanks in advance. >
Are the bins evenly spaced? If they are then you will probably be better off doing an FFT rather than implementing 1000 Goertzel filters. Certainly if you are collecting 1000-2000 points and want to bin them up then an FFT makes more sense. Come to think of it, even an FFT will be a challenge in that amount of time -- what the _heck_ are you trying to do? By the way, you can find information about the performance of the FPGA-implemented Goertzel algorithm in your nearest brain: implement it and look at how much FPGA resources it takes up. Then multiply that by 1000 and start looking for big chips. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
<larsonbr@gmail.com> wrote in message 
news:1115303015.154487.303250@g14g2000cwa.googlegroups.com...
>I have recently read about the Goertzel algorithm and I am looking to > use it in a FPGA/DSP. The problem is I am interested in using the > algorithm to compute about 1000 frequency bins during a microsecond > period, so I am very interested in its performance in hardware to help > me select a device. Does anyone know where I can find some info on the > performance of the Goertzel algorithm in an FPGA. Thanks in advance. >
Perhaps someone else will give you some insight into implementation in an FPGA. However, your application suggests some basis issues in phyics: It would be helpful to know the absolute numbers regarding frequency and bandwidth / bin width. if the data is coming in real time, then "1000 frequency bins during a microsecond" implies that the bin width will be 1/1^-6 = 1MHz. There is no getting around that. If the bin widths are 1MHz and you're using the Goertzel algorithm to get 1000 bins, that implies a bandwidth of at least many GHz. i.e. beyond the 1GHz across the 1000 bins. Of course, if you're processing stored data and just want to do it very fast, then the numbers might be very different. What are we missing? Fred
Hello,  I geuss I should clear things up a bit.  I am trying to
calculate an N-point DFT  using the Goertzel algorithm.  I will be
receiving a 24 bit complex number every 1 microsecond.  I am still
fairly new to the Goertzel algorithm, but as far as I understand it
should only take a multiplication and a couple of additions for one
frequency bin every microsecond.  Granted I need 1000 frequency bins I
should be able to do this in an FPGA by breaking it up into several
modules and doing this operation every 1000/(number of modules)
microseconds.  As far as just implementing it in an FPGA, there a
several ways of doing it only limited by my imagination.  I am looking
at using an Altera Stratix II using the DSP cores, but I am also
looking into some Intellectual Properties for implementing it as well.
I am just wondering if someone has already done something similar in an
FPGA and what they learned a long the way.  Thanks for the input.

larsonbr@gmail.com wrote:
> Hello, I geuss I should clear things up a bit. I am trying to > calculate an N-point DFT using the Goertzel algorithm.
Ahh. Somehow I was interpreting your original post to mean that you wanted to do all of the processing all at once in one microsecond, not one step each microsecond. That certainly simplifies things.
> I will be > receiving a 24 bit complex number every 1 microsecond. I am still > fairly new to the Goertzel algorithm, but as far as I understand it > should only take a multiplication and a couple of additions for one > frequency bin every microsecond.
Two multiplies if it's complex data, four if you want to filter out both positive and negative frequencies (which you may, if you're starting from complex data).
> Granted I need 1000 frequency bins I > should be able to do this in an FPGA by breaking it up into several > modules and doing this operation every 1000/(number of modules) > microseconds.
Yes. 1000 operations per microsecond, and this should be much more doable than the 1000000 I quoted in the other post, having mistaken your intent.
> As far as just implementing it in an FPGA, there a > several ways of doing it only limited by my imagination. I am looking > at using an Altera Stratix II using the DSP cores, but I am also > looking into some Intellectual Properties for implementing it as well. > I am just wondering if someone has already done something similar in an > FPGA and what they learned a long the way. Thanks for the input. >
This seems like the kind of thing that's specialized enough that you're better off rolling your own -- but if you can find somebody's IP that does the job then more power to you! No matter how you slice it, however, if you are going to use evenly spaced frequency bins you can do it with less processing by using an FFT, as long as you can stand the delay. You _will_ have an issue with latency, and with having to store the samples, but that Stratix part should include block RAM as well. I'd make it a point to seriously consider both approaches. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Tim Wescott wrote:
> larsonbr@gmail.com wrote: > >> Hello, I geuss I should clear things up a bit. I am trying to >> calculate an N-point DFT using the Goertzel algorithm. > > > Ahh. Somehow I was interpreting your original post to mean that you > wanted to do all of the processing all at once in one microsecond, not > one step each microsecond. That certainly simplifies things. > >> I will be >> receiving a 24 bit complex number every 1 microsecond. I am still >> fairly new to the Goertzel algorithm, but as far as I understand it >> should only take a multiplication and a couple of additions for one >> frequency bin every microsecond. > > > Two multiplies if it's complex data, four if you want to filter out both > positive and negative frequencies (which you may, if you're starting > from complex data). > >> Granted I need 1000 frequency bins I >> should be able to do this in an FPGA by breaking it up into several >> modules and doing this operation every 1000/(number of modules) >> microseconds. > > > Yes. 1000 operations per microsecond, and this should be much more > doable than the 1000000 I quoted in the other post, having mistaken your > intent. > >> As far as just implementing it in an FPGA, there a >> several ways of doing it only limited by my imagination. I am looking >> at using an Altera Stratix II using the DSP cores, but I am also >> looking into some Intellectual Properties for implementing it as well. >> I am just wondering if someone has already done something similar in an >> FPGA and what they learned a long the way. Thanks for the input. >> > This seems like the kind of thing that's specialized enough that you're > better off rolling your own -- but if you can find somebody's IP that > does the job then more power to you! > > No matter how you slice it, however, if you are going to use evenly > spaced frequency bins you can do it with less processing by using an > FFT, as long as you can stand the delay. You _will_ have an issue with > latency, and with having to store the samples, but that Stratix part > should include block RAM as well. I'd make it a point to seriously > consider both approaches.
Sounds like a chore for a sliding FFT. http://www.pscc02.org/papers/s28p04.pdf http://www.hunteng.co.uk/bench/fft-bench.htm Jerry -- Engineering is the art of making what you want from things you can get. &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
On 5 May 2005 07:23:35 -0700, "larsonbr@gmail.com"
<larsonbr@gmail.com> wrote:

>I have recently read about the Goertzel algorithm and I am looking to >use it in a FPGA/DSP. The problem is I am interested in using the >algorithm to compute about 1000 frequency bins during a microsecond >period, so I am very interested in its performance in hardware to help >me select a device. Does anyone know where I can find some info on the >performance of the Goertzel algorithm in an FPGA. Thanks in advance.
Hello Larson, after reading your post I also (like some of the other guys here) thought that maybe the FFT would be better for you. However, not knowing all the details of what you're trying to achieve, I think you might want to take a look at the "Sliding DFT algorithm". If your spectral results need to be updated (a sort of "real time idea") periodically, then you should definitely consider the Sliding DFT. I cover that SDFT algorithm in my book, but you can find essentially the same information at: "The Sliding DFT", IEEE Signal Processing Magazine, DSP Tips & Tricks column, Vol. 20, No. 2, March 2003. "The Sliding DFT, an Update", IEEE Signal Processing Magazine, DSP Tips & Tricks column, Vol. 21, No. 1, Jan. 2004. Good Luck, [-Rick-]
Hello,

Why not prototyping it using one of the latest C2H (C to Hardware)
compilers ? It will be a matter of days instead of weeks.

There is an interesting example here :
http://www.elektor.com/magazines/2008/march/from-c-to-hardware.372572.lynkx

All you need is to write the algo in C and you'll get it translated into a
coprocessor, or, as you said, an array of coprocessors within the FPGA. The
rest of the FPGA would be configured as a general-purpose 16-bit or 32-bit
microcontroller possibly with DMA in and DMA out. You don't need power in
the &micro;C as the power is in the dedicated co-processor and DMA can assist
you doing the I/O.

I am not sure you'll get a gigahertz throughput, but you'll get something
between 100 MHz and 300 Mhz. After less than one week work. 

Maybe use 4 or 8 FPGAs, then later on with silicon advances, you'll be
able to pack all this in one FPGA running close to 1GHz and outputting on
FireWire.

Then, you'll be selling a device about 10K dollars each, with a BOM cost
of less than 100 dollars with almost no development cost. 

Steph