# Goertzel Algorithm

Started by 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
>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
```