cancel
Showing results for 
Show  only  | Search instead for 
Did you mean: 
Visitor
Visitor
790 Views
Registered: ‎03-04-2020

Continuously estimate the frequency with the highest amplitude

Hello,

I would like to continuously estimate the maximum frequency with parallel input paths.

For every clock cycle, I receive a sample frame consisting of 8 samples with a sample width of 10 bit. Thus, I receive 8x10 bit per clock cycle.
I want to do the following steps:

  1. Buffer several frames, e.g., 8 frames (8x8 = 64 samples)
  2. Zero-pad the buffered frames to obtain a better frequency resolution in the frequency domain, e.g., by padding the 64 samples with 512-64 samples
  3. Compute the FFT of the zero-padded samples
  4. Estimate and return the frequency index of the maximum magnitude

In my current System Generator design, I receive a single FFT sample per clock cycle, i.e., it takes 512 clock cycles to obtain the entire frequency spectrum and then I can estimate the maximum.

Is it possible to do all of this in parallel to obtain the maximum frequency continuously?

Tags (3)
0 Kudos
Reply
8 Replies
726 Views
Registered: ‎01-22-2015

@yy 

Frequency is not an instantaneous quantity.  That is, you need a full spectra (ie. a complete FFT) in order to find the frequency of max amplitude.   However, you could use FFT cores in parallel (as you suggest) and send data to each core in a way that gives you a full spectra more often than once every 512 clock cycles.
 
For example, with 4 cores, you could send samples 0-511 to core1, samples 128-639 to core2, samples 256-767 to core3,  samples 384-895 to core4, samples 512-1023 to core1, samples 640-1151 to core2,  etc ......  After latency of the cores has passed, you will have a full spectra from one of the cores every 128 clock cycles.   Thus, you can find the frequency of max amplitude every 128 clock cycles - instead of every 512 clock cycles.
 
Cheers,
Mark
Visitor
Visitor
702 Views
Registered: ‎03-04-2020

markg@prosensing.com 

Thank you for your answer! This is also a great approach. For now, I implemented an 8 input butterfly diagram to perform the FFT fully parallel. As with only 8 samples the frequency resolution is very limited, I would like to buffer more samples.

Is there something which behaves like a FIFO which I can use to buffer the samples and access all buffered samples in parallel?
For example, for 64 samples with a word width of 32 bit, I would like to start with an empty buffer. Then, at every clock cycle, I receive 8 new samples and the oldest samples should be discarded.
I want to access the samples in parallel using a slice block as follows:

  • Sample 0: [0:31]
  • Sample 1: [32:63]
  • ...
  • Sample 63: [2016:2047]

Is there a type of memory I can use for this purpose?

The single port RAM only allows to access a single value at a specific address and the FIFO only allows to access the first element in the queue.

0 Kudos
Reply
672 Views
Registered: ‎01-22-2015

@yy 

Is there something which behaves like a FIFO which I can use to buffer the samples and access all buffered samples in parallel?

Maybe FIFOs in parallel?

For example, if sample count is 8 then use 8 FIFOs and load them as follows:

sample1>FIFO1,  sample2>FIFO2   ...   sample8>FIFO8,  sample9>FIFO1,  sample10>FIFO2 ....

Scholar
Scholar
660 Views
Registered: ‎05-21-2015

@yy,


Is there something which behaves like a FIFO which I can use to buffer the samples and access all buffered samples in parallel?

Yes, but you'd have to write it.

The "FFT" would basically be a complex exponential downconversion followed by a block average for every frequency and every one of your 8-samples.  The result of this operation would then go into your 8-pt butterfly and you'd be there.  You could then take all 8-outputs at once from the core and do whatever you needed to with them.

That said, there's a reason why no one does this.  Specifically, the time/frequency uncertainty principle ... sometimes (erroneously?) called the Heisenberg uncertainty principle.  That is, the more/better you estimate things in frequency, the poorer they'll be estimated in time.  Indeed, I can pretty much mathematically prove that a 50% overlap rate of FFTs contains *all* of the frequency information you would ever get from a continuous sampled FFT output.  The proof isn't all that hard to do.  So, at this point, you have to ask: why am I working so hard to get "extra" information when I can prove that there's no "extra" information present?

There are other approaches as well which can work in this context, but for which there isn't quite the same noise tolerance.  One of them is a PLL.  PLLs will easily track the largest incoming frequency, and they will do it on a sample by sample basis.  The tracking frequency of the PLL will give you the frequency you want.  Another approach would be to take two FFTs of samples x[0:N-1] and x[1:N], and conjugate multiply them together.  The phase found in the strongest bin will be directly related to your frequency of interest.  Both of these techniques work nicely on a sample-by-sample basis, but neither gets the noise tolerance of the FFT.  As a separate benefit, these techniques will give you fractional resolution whereas an FFT will (at best) give you the nearest bin--you will need to run a quadratic interpolator on the FFT peak to actually get the best frequency estimate--if fractional resolution is important to you.  (Which it probably is, since you are asking for bigger and bigger FFTs.)

A third technique to consider, which tends to work nicely in FPGA contexts, is simply counting transitions.  The number of negative to positive transitions over a period of time is a good estimator of frequency.  Like the last two estimates, however, it is quite susceptible to noise.

But if you want to stick with the FFT, perhaps because you have a weak sinusoid or because there's other interfering signals in your band, then beware of whether or not you should use a window function.  Window functions are very useful  when trying to separate two closely spaced sinusoids into separate frequency bins.  Without a window function, the effects you will get if you ever have more than one sinusoid ... won't be what you are expecting.  The problem is that window functions don't fit nicely into sample by sample FFT estimates, and might not fit onto your hardware at all.  (They fit nicely with FFTs that incorporate an N/2 decimation, such as you'd get from a 50% overlap--a minimum overlap which can cover everything.)

So let me come back to the original question, and ask: is there a reason why you need to do this with an FFT, and is there a reason why it needs to be done on a sample by sample basis?

Dan

Visitor
Visitor
646 Views
Registered: ‎03-04-2020

@dgisselq

Thank you for your very detailed answer. I have a couple of questions.


That said, there's a reason why no one does this.  Specifically, the time/frequency uncertainty principle ... sometimes (erroneously?) called the Heisenberg uncertainty principle.  That is, the more/better you estimate things in frequency, the poorer they'll be estimated in time.  Indeed, I can pretty much mathematically prove that a 50% overlap rate of FFTs contains *all* of the frequency information you would ever get from a continuous sampled FFT output.  The proof isn't all that hard to do.  So, at this point, you have to ask: why am I working so hard to get "extra" information when I can prove that there's no "extra" information present?


I'm not completely sure what you mean by this. I know that using only 8 samples for the FFT can be considered as using a short rectangular window in the time domain which is represented by a wide sinc function in the frequency domain. I'm also aware that in the noise-free case with a single frequency, the 8 samples should already be sufficient to recover the frequency accurately by using zero-padding to decrease the spacing between two frequency samples.

As in my case, the signal is not noise-free, I would like to buffer more than 8 samples, so I can perform the FFT on more samples. I do not know how this is related to the proof you mentioned. What do you mean by "extra" information?


There are other approaches as well which can work in this context, but for which there isn't quite the same noise tolerance.  One of them is a PLL.  PLLs will easily track the largest incoming frequency, and they will do it on a sample by sample basis.  The tracking frequency of the PLL will give you the frequency you want.


This approach sounds very promising. I will have a look at this. Is it possible to get the frequency as a value or will I only get a signal with this frequency?


So let me come back to the original question, and ask: is there a reason why you need to do this with an FFT, and is there a reason why it needs to be done on a sample by sample basis?

The FFT was my first idea to estimate the dominant frequency of a time signal as I did not know about the other approaches you mentioned. I can't tell you the SNR of my signal, but I am quite sure that the frequency I want to estimate is always the dominant frequency. There might be attenuated multi-path interference if this is of interest.

The most important factor for me is a very low latency which is why I wanted to use a fully parallel design. On the first glance, your proposed PLL approach could be faster than buffering several samples and performing an FFT. Thanks again for your input. I will also think about the other approaches you mentioned.


0 Kudos
Reply
Scholar
Scholar
635 Views
Registered: ‎05-21-2015

@yy,


Thank you for your very detailed answer. I have a couple of questions.

That said, there's a reason why no one does this.  Specifically, the time/frequency uncertainty principle ... sometimes (erroneously?) called the Heisenberg uncertainty principle.  That is, the more/better you estimate things in frequency, the poorer they'll be estimated in time.  Indeed, I can pretty much mathematically prove that a 50% overlap rate of FFTs contains *all* of the frequency information you would ever get from a continuous sampled FFT output.  The proof isn't all that hard to do.  So, at this point, you have to ask: why am I working so hard to get "extra" information when I can prove that there's no "extra" information present?


I'm not completely sure what you mean by this. I know that using only 8 samples for the FFT can be considered as using a short rectangular window in the time domain which is represented by a wide sinc function in the frequency domain. I'm also aware that in the noise-free case with a single frequency, the 8 samples should already be sufficient to recover the frequency accurately by using zero-padding to decrease the spacing between two frequency samples.

What I'm pointing out here is that by zero padding you aren't adding any new information.  You are only interpolating between the points you already have.  If you compare raster images of FFTs before and after zero padding, you'll find that you are just smearing the information in the FFTs around more and more.  While the interpolator created by zero padding is generally a good one--provided you've windowed your data properly, it can also become more expensive than its worth after a zero pad of 2x.  Other interpolators, such as a simple quadratic interpolator, simply provide better solutions for less logic.


As in my case, the signal is not noise-free, I would like to buffer more than 8 samples, so I can perform the FFT on more samples. I do not know how this is related to the proof you mentioned. What do you mean by "extra" information?

Simply put, you can't create information where none is available.  The fact that you can interpolate and get the same results helps to point out that larger FFTs don't give more information--it's just the same information smeared across more bins.



There are other approaches as well which can work in this context, but for which there isn't quite the same noise tolerance.  One of them is a PLL.  PLLs will easily track the largest incoming frequency, and they will do it on a sample by sample basis.  The tracking frequency of the PLL will give you the frequency you want.


This approach sounds very promising. I will have a look at this. Is it possible to get the frequency as a value or will I only get a signal with this frequency?


The frequency value is contained within the r_step register internal to the core, but nothing keeps you from creating an output with this information.  This value is proportional to the Nyquist frequency, with { 1'b1, {(rest_of_bits){1'b0}} } being equal to the Nyquist frequency.  You may have to do some scaling to this number to get the one you want, but you'd have to do that with the FFT anyway.



So let me come back to the original question, and ask: is there a reason why you need to do this with an FFT, and is there a reason why it needs to be done on a sample by sample basis?

The FFT was my first idea to estimate the dominant frequency of a time signal as I did not know about the other approaches you mentioned. I can't tell you the SNR of my signal, but I am quite sure that the frequency I want to estimate is always the dominant frequency. There might be attenuated multi-path interference if this is of interest.


Be aware that any multipath with Doppler could really throw any frequency estimation off, and that very quickly.  There's not an FFT long enough that could deal with all Doppler eventualities.  Without Doppler, your frequency estimate is likely to be accurate enough, although the multipath might throw off any phase measurements associated with that frequency.






The most important factor for me is a very low latency which is why I wanted to use a fully parallel design.


Be aware that even the fully parallel design you have proposed will still have a latency associated with it as well, as will any PLL.  The only real low-latency method of frequency estimation I know of, arg(x[n] * x[n-1]), is quite susceptible to noise and interference.  Anything else is going to have latency that you'll need to manage.  Further, the better the frequency estimate that you want, the more latency you will need to suffer from.  It's just a natural part of frequency measurement.

You haven't mentioned your application yet, so let me offer that PLL's work great for tracking frequencies in many communications applications.  Where the FFT comes in handy is in early tone frequency estimation in order to bootstrap the PLL--although handoff between the FFT and the PLL while doable can be a challenge.  Once you are tracking the carrier, symbol rate, whatever, the PLL usually works quite well for the task.  You might even consider filtering the signal before using the PLL--but again you'll need to track the latency through any such operations.  Radar is a bit different, since you can often suffer the lag between reception and display without too much of a hassle, whereas a communications receiver can't.

Dan

Visitor
Visitor
477 Views
Registered: ‎03-04-2020

@dgisselq 

Thank you again for your detailed response. I highly appreciate it.

First about the application. I want to estimate the slope of a a linearly chirp signal. Either directly with the chirp signal or by down-converting the chirp signal with a delayed version which yields a constant frequency that can be converted to the chirp slope. The second approach would introduce another delay and requires more resources.

I continued with the FFT-based approach and for now, I created a 16 sample FFT butterfly in System Generator, computed the magnitude and tested the quadratic interpolation as you suggested. Currently, I am doing the quadratic interpolation in an independent MATLAB simulation as I could not find out yet how to access the adjacent samples of the maximum in parallel in a single clock cycle.

Also, I am unsure about the FPGA resources required to do all of this in parallel and therefore I am thinking about the PLL approach again. Is the PLL module you mentioned only capable of tracking (almost) constant frequencies or is it capable of estimating the chirp slope? Also, can the PLL handle frequency hops or does the frequency has to change smoothly?

0 Kudos
Reply
Scholar
Scholar
456 Views
Registered: ‎05-21-2015

@yy,

What answer is appropriate really depends upon 1) the maximum chirp rate, since even an FFT based approach will fail for the wrong FFT size compared to the chirp rate, 2) your latency tolerance, 3) the SNR available to you, and 4) the time and frequency resolution you need.  My guess is that these values are specific to your application, and that I won't be able to help you further on this forum.

The PLL module I quoted will track changing frequencies within some limit, depending upon the bandwidth of the filter you choose.  Changing frequencies will put a "stress" (technical term) on the system.  At some point, the stress will be too much and the PLL will lose lock.

There is another PLL formulation that includes a second integrator in the PLL.  These are known as 3rd order PLL's.  They can track changing frequencies.  They are used often for satellite communications carrier trackers.  Technically, they're not hard to build at all.  Practically, you'll need to figure out and get the coefficients right, and that's not necessarily that trivial.  Feel free to browse my PLL tutorial for (a limited amount of) more information.

If the frequency "hops" (what problem are you solving here?), the PLL will lose lock and need to reacquire.  Indeed, even a chirp of sufficient delta frequency might cause the PLL to lose lock as well.  Given that the PLL can acquire in the first place, this isn't necessarily a total loss--but it's certainly something to consider.  Will the PLL reacquire your signal, and in the time frame you need?  You'll need to know.

Dan

0 Kudos
Reply