FFT speed and Size

[ogden]

No, that is going to work really poorly in the presence of any noise. I avoided that thread because it was already flooded with too many incorrect commentary about signals and systems in general.
You can extract exact frequency from a FFT result by looking at at most 3 adjacent frequency bins and looking at the relative phase

Only in case when 3 adjacent frequency bins are free from "any noise" you mentioned as counter-argument against other methods.

[mrflibble]

No, that is going to work really poorly in the presence of any noise. I avoided that thread because it was already flooded with too many incorrect commentary about signals and systems in general.

You say that as if it's a bad thing. Just read it, and it was hilarious! 

Anyways, the fast detection of a single frequency under noise can be done with the sparse FFT. If I understand the OP correctly it would boil down to k-sparse, where k=1, and non-ideal because noise. So it should come as no surprise to anyone who has not been living under a rock the past, oh I dunno, 15 years or so, that we can do significantly better than Ye Olde FFT.

Couple of resources:

• https://arxiv.org/abs/1201.2501v1
• https://groups.csail.mit.edu/netmit/sFFT/fouriermeasurements.pdf
• https://arxiv.org/abs/1909.11123
• https://groups.csail.mit.edu/netmit/sFFT/code.html
• http://spiral.net/software/sfft.html
• https://github.com/davidediger/sfft

[OwO]

Yes, compressive sensing approaches could let you narrow in on the exact frequencies of a few peaks quickly, but you need to be careful - k-sparse does not mean "extract the highest k frequency components" - it means "assume the input signal has *only* k frequency components and then do the minimum work to find them".  For example, a 1-sparse DFT might only look at 3 input samples. It's really just taking 3 points and then curve fitting a sine to it. When you want to make the best possible estimate of the highest peak frequency component in the presence of noise and interferers, the traditional FFT is optimal (it will give you the maximum likelihood answer).

[ali_asadzadeh]

Guys thanks for the feedback, I have used this filtering algorithm with a 31 tap FIR filter and then use Zero crossing to estimate the frequency, it has very good accuracy, around 0.05Hz, but it has a delay,I need around two cycles of the sin wave to get this accuracy,so that was why I asked the question is there any better, faster alternative way? I still do not understand how the Pure FFT method with limited samples works? since I'm now planing to get FFT on each arriving sample, I think there must be a better way than my current work.

[OwO]

Have you tried this on real hardware or did you just do some simulations? Frequency accuracy is a function of SNR, so if you just did simulations it means nothing. 0.05Hz is 0.1% of 50Hz, or a period error of 0.1%. The slope of a sine (with amplitude 1) at the zero crossing is 1, which means period perturbation is roughly equal to amplitude perturbation. 0.1% amplitude error at the zero crossing means 60dB SNR. If the noise is gaussian add another 20dB of margin for 80dB SNR. That SNR also must be achieved within a wide bandwidth, in your case ~100Hz.

[ali_asadzadeh]

Have you tried this on real hardware or did you just do some simulations?

I have tested it on a Cortex M4 on a real hardware and a real signal.

[nctnico]

the traditional FFT is optimal (it will give you the maximum likelihood answer).

I'd still look at more optimised solutions. If you are interested in a narrow frequency band then FFT gives you a lot of extra data you don't need.

[SiliconWizard]

Guys thanks for the feedback, I have used this filtering algorithm with a 31 tap FIR filter and then use Zero crossing to estimate the frequency, it has very good accuracy, around 0.05Hz, but it has a delay,I need around two cycles of the sin wave to get this accuracy,so that was why I asked the question is there any better, faster alternative way? I still do not understand how the Pure FFT method with limited samples works? since I'm now planing to get FFT on each arriving sample, I think there must be a better way than my current work.

I think what you're looking for is close to physically impossible. Basically you want to be able to accurately estimate the frequency of a signal with just one cycle of it? Taking all errors across the acquisition chain into account. Good luck.

What's the intended purpose?

[ali_asadzadeh]

I have this idea, Calculate FFT on every incoming sample, then Add the 3 first Bin complex numbers and then calculate the phase for the sum, then compare it to the previous calculation, and see the phase difference, in this way we can estimate the Frequency,as fast as possible!? is it correct?

[nctnico]

I have this idea, Calculate FFT on every incoming sample, then Add the 3 first Bin complex numbers and then calculate the phase for the sum, then compare it to the previous calculation, and see the phase difference, in this way we can estimate the Frequency,as fast as possible!? is it correct?

It depends on how long the FFT is. My guess is that FFT will need to span several cycles at least for windowing so you'll be slower compared to other methods. Also if you FFT spans multiple cycles then you'll get (some sort of) average value over those cycles.

If you want really fast detection then curve fitting through the last 3 to 5 samples (at a relatively low samplerate like 300 to 500 samples/second) is the fastest. To reduce the effect of noise and disturbances you can use the result of past measurements to determine the maximum / minimum valid frequency. After all there has to be some limit to the maximum frequency jump you can expect. If a new measurement falls outside that limit, it is invalid. You also need to account for phase delays due to filtering (both in the analog and digital domain). You might want to sample with the ADC at a higher speed, filter in the digital domain (elliptic IIR) and then decimate to a lower samplerate to feed the curve fitting algorithm.

[SiliconWizard]

Agreed, and most points have actually already been discussed in the other thread, this just all looks like the same all over again.
Curve fitting can obviously not be used in presence of noise, as it would assume a specific waveform to begin with, and estimation errors on curve fitting get big real quick.

We still don't quite know what the purpose is. If you think about it, estimating the frequency of a signal over just one cycle of it (or less even maybe, why not?) is just non-sense strictly speaking. Even over just one period, the definition of frequency (or period) itself doesn't make much sense, as it's supposed to define a function (signal) that is periodic. Is a signal with just one period periodic? You have fundamental signal processing questions to deal with first.

[mrflibble]

Yes, compressive sensing approaches could let you narrow in on the exact frequencies of a few peaks quickly, but you need to be careful - k-sparse does not mean "extract the highest k frequency components" - it means "assume the input signal has *only* k frequency components and then do the minimum work to find them".

That is one flavor of k-sparse recovery, yes. What you're talking about there is the exactly sparse sfft. But there's also the approximately sparse flavor. The tradeoff there being that the complexity is not as low as the exactly sparse case, but still lower than for the general fft. See for example this comparison list of complexities:
https://groups.csail.mit.edu/netmit/sFFT/algorithm.html

If you check out the code linked to earlier you'll see that sfft v3 only handles exactly sparse, which behaves as you say. The v1 and v2 sfft however also operate correctly with noise present. And as a consequence these take more ops than the v3 version. Anyways, not arguing for sFFT to be the best solution here, because it probably isn't. Something along the lines of a dpll is probably easier. I recall it was already mentioned, or was that in the other thread?

Agreed, and most points have actually already been discussed in the other thread, this just all looks like the same all over again.
Curve fitting can obviously not be used in presence of noise, as it would assume a specific waveform to begin with, and estimation errors on curve fitting get big real quick.

Curve fitting can obviously be used in the presence of noise. People are doing it all the time, and it even works. As a real quick idea, transform the problem to having to fit the phase or phase increment versus time, that way the problem can be reduced to a linear fit. Then you can do a least squares fit if you want to keep it old school and get an adequate result. Or use an l1-minimizer to get a better result, especially when there is noise present. The biggest task when using l1-minimizers is always to linearize the problem.

PS: Oh and thank you very much for mentioning problem #672, that cost me a nice chunk of time the other day.   

[mrflibble]

We still don't quite know what the purpose is. If you think about it, estimating the frequency of a signal over just one cycle of it (or less even maybe, why not?) is just non-sense strictly speaking. Even over just one period, the definition of frequency (or period) itself doesn't make much sense, as it's supposed to define a function (signal) that is periodic. Is a signal with just one period periodic? You have fundamental signal processing questions to deal with first.

Quite true. Not to mention that the uncertainty principle was already mentioned waaay back at the start. So clearly the OP has already been taken into consideration. Right? Right?!?  If not, then he has some catching up to do, because 3blue1brown has some pretty good math videos on his channel.

[SiliconWizard]

Curve fitting can obviously be used in the presence of noise. People are doing it all the time, and it even works. As a real quick idea, transform the problem to having to fit the phase or phase increment versus time, that way the problem can be reduced to a linear fit. Then you can do a least squares fit if you want to keep it old school and get an adequate result. Or use an l1-minimizer to get a better result, especially when there is noise present. The biggest task when using l1-minimizers is always to linearize the problem.

Just keep that in the context of the application here, with the above quote in mind "if you want really fast detection then curve fitting through the last 3 to 5 samples".
What are you going to fit exactly? A pure sine wave? What does it give you if it has even just a small amount of additional noise?

But please have at it. Implement that in Matlab or your favorite tool and see what you get. If you're feeling like it, even try to derive theoretical error on frequency/period estimation as a function of your parameters, included any additional noise.

In the end, you're not going to get anything better than simple filtering + zero crossing, but with a lot more effort IMO. Estimating frequency from just a few points on a curve, sure. Go ahead and come back with some results.

[ogden]

I avoided that thread because it was already flooded with too many incorrect commentary about signals and systems in general.

No offense, but this thread where people suggest FFT for freq measurement of few sine periods is no better than that thread.

[SiliconWizard]

I avoided that thread because it was already flooded with too many incorrect commentary about signals and systems in general.

No offense, but this thread where people suggest FFT for freq measurement of few sine periods is no better than that thread.

Yep. And in the other thread AFAIR, most of the relevants points, that also apply here, were made. I don't see what more has been brought, or could be actually.

[mrflibble]

Curve fitting can obviously be used in the presence of noise. People are doing it all the time, and it even works. As a real quick idea, transform the problem to having to fit the phase or phase increment versus time, that way the problem can be reduced to a linear fit. Then you can do a least squares fit if you want to keep it old school and get an adequate result. Or use an l1-minimizer to get a better result, especially when there is noise present. The biggest task when using l1-minimizers is always to linearize the problem.

Just keep that in the context of the application here, with the above quote in mind "if you want really fast detection then curve fitting through the last 3 to 5 samples".
What are you going to fit exactly? A pure sine wave? What does it give you if it has even just a small amount of additional noise?

I was keeping that in the context of the application. That application however does not include such specifics as "if you want really fast detection then curve fitting through the last 3 to 5 samples". For me, "the application" is more along the lines of "have signal, contains something periodic, may contain harmonics, may contain dc, probably noisy who knowns. Need frequency estimate upto 24876324 digits in 1E-349634 sec, kthxbai! ". The given example of 3 to 5 samples would probably be adequate to do rough binning as a first order approach, and then use that quick & cheap rough estimate as initial condition for whatever method follows. And even that assumption is easily invalidated if there is enough noise present.

The information available about the signal in question is not all that much, so all we would be doing is base stuff on random assumptions. Case in point, the curve fitting being discussed. I can think of a scenario of the "too easy" type, and another of the "nearly" impossible type. Too easy would be: signal is mainly the fundamental, hardly any harmonics, and hardly any noise. Say the fundamental is 200 dB above all the unwanted crap. Lets furthermore cheat by saying that we already have a rough frequency estimate from the "whatever" assumption collection. That scenario would probably be "too easy". Then again, the fundamental could be swamped by random noise. Think "GPS receiver" level garbage. Then we probably need a wee bit more than just 2 cycles to get anything meaningful, and a whole lot of prior knowledge about the signal to be retrieved. As it stands, both the "too easy" and the "gps receiver (without almanc for extra bonus points)" are both valid problem descriptions fully consistent with the info given by the OP. For the pedantic, just subsample gps signal to make it compliant with given frequency range. Even that is totally legit given the constraints, because we know fuck all about the sampling process either.

So I look at this more as an opportunity the exchange thoughts about possible ways to solve problems that look roughly like the problem as given. Because finding a solution in the engineering sense in this case would be non-sense. The most sensible solution in the engineering sense would be to have an extended phone call with the customer to get some actual information. And then, time permitting, have a few talks with the people in engineering to get some actual context.

But please have at it. Implement that in Matlab or your favorite tool and see what you get. If you're feeling like it, even try to derive theoretical error on frequency/period estimation as a function of your parameters, included any additional noise.

Heh, I wouldn't even know how to model the signal, because ... If the OP would give us signal traces for lets say 5 different yet representative scenarios, with each trace at least 10 (fundamental) cycles long, then sure. That would be a fun excercise to see what can and cannot be done with the various processing techniques.

In the end, you're not going to get anything better than simple filtering + zero crossing, but with a lot more effort IMO. Estimating frequency from just a few points on a curve, sure. Go ahead and come back with some results.

That is highly debatable, because it depends a lot on the problem parameters. I do agree however that it will be significantly more effort than filtering (aka throwing away information AND conditioning the signal such that numerically cheap algorithms can do a good enough job) and zero crossing. That's always the tradeoff. Want better result? Needs more resources, be that engineering resources or computational.

Incidentally, did you find a nice solution for problem #672? Because I sure didn't... Wait, I'll post it in the other thread.

[nctnico]

But please have at it. Implement that in Matlab or your favorite tool and see what you get. If you're feeling like it, even try to derive theoretical error on frequency/period estimation as a function of your parameters, included any additional noise.

In the end, you're not going to get anything better than simple filtering + zero crossing, but with a lot more effort IMO. Estimating frequency from just a few points on a curve, sure. Go ahead and come back with some results.

In the end math only gets you so far. You can't catch the real world in a math equation which can handle all the criteria. In many cases you'll have to add extra logic (or even AI) to determine whether the math came up with the right number or not. And if not, what the right number should be.

[OwO]

If the SNR is low within the capture bandwidth, say 0dB @ 1kHz bandwidth while you need to capture a tone that can range from 1 to 10kHz, then FFT *is* the optimal way, and anything you can think of in the time domain will give you trash because the signal waveform looks just like noise. Filtering can not help when you need to capture a wide frequency range. I asked the OP multiple times what the SNR is and never got an answer, so as I'm a communications engineer I will assume low SNR and suggest solutions that are optimal in the presence of noise.

[OwO]

Even if you have only one or two periods of input and reasonable SNR, I can show that using FFT is optimal in terms of MAP (maximum aposterior probability) rule, and to maintain that optimality you can not do much better in terms of computational complexity. Any attempts to reduce computation (time domain approaches, sparse approaches, etc) will make the solution non-optimal in terms of MAP.

First of all, when distinguishing between several possible waveforms in the presence of noise, the MAP rule reduces to minimum distance rule, or in other words the symbol with the lowest distance to the input waveform is the most likely one. Distance here is represented by dot product, or the integral of the product of two waveforms. Higher dot product => less distance.

In this case we have a chunk of input waveform and know that it contains a portion of a sine plus some noise. Our symbol dictionary is simply the set of all sinusoids with amplitude 1.

The problem can then be defined as: find the most likely sinusoid that the input waveform chunk is believed to contain.

If we simply took the dot product between the input waveform chunk and every possible sinusoid, then picked the one with the highest dot product, then we have satisfied the MAP rule. The fourier transform is exactly that, it's a dot product between the input waveform and all possible sinusoids.

However, the FFT as computed is not a FT (fourier transform). It's a special case of it which is properly named the discrete fourier series (DFS). Recall that a signal that is periodic in the time domain is discrete in the frequency domain, and that a signal that is discrete in the time domain is periodic in the frequency domain. The DFS is a fourier transform of a signal that is both discrete and periodic, both in time and frequency domains.

Suppose our input waveform chunk looks like this:



If we compute a FFT on it, we are actually computing the FT of this, which is the input chunk repeated:



(which is repeated and goes on to infinity).
However that's not what we want, we want the FT of just the input chunk, with zeros everywhere else. So to do that we (conceptually) multiply the input with a rect, which is equivalent to convolving with a sinc in the frequency domain or interpolating it.

The FFT output might look like this:



The black lines are the discrete output points, while the red line is the interpolated waveform.
Every point on the red waveform is mathematically equivalent to the dot product between a particular sinusoid and the input waveform chunk.
The peak pointed to by the blue arrow is the maximum point. This peak can be extracted without actually interpolating the FFT output, by deriving the formula of the sinc convolution and then finding local maxima.

Regardless of what you do, to actually make full use of the input data you must look at all points, so your minimum computational complexity is O(n). The FFT + peak finding has a complexity of n log n, which is very close to O(n) and I would say is pretty much as good as you can get. Any approaches that are sublinear such as sparse FFT variants will not give you the MAP result, and thus are not optimal in terms of extracting maximum information out of the input waveform.

Please, before you comment that new and shiny approaches do far better than FFT, go and review your first year signals and systems theory and fourier identities, and try deriving exactly what you are actually computing. There is a time and place for sparse approaches, but when you have evenly spaced input data and you want a best possible estimate of frequency and phase, you actually can not do better than a fourier based approach.

[ali_asadzadeh]

If the SNR is low within the capture bandwidth, say 0dB @ 1kHz bandwidth while you need to capture a tone that can range from 1 to 10kHz, then FFT *is* the optimal way, and anything you can think of in the time domain will give you trash because the signal waveform looks just like noise. Filtering can not help when you need to capture a wide frequency range. I asked the OP multiple times what the SNR is and never got an answer, so as I'm a communications engineer I will assume low SNR and suggest solutions that are optimal in the presence of noise.

Thanks for the detailed answers, I think the SNR is better than 40dB. Suppose that I'm capturing the mains with a 24bit ADC and I have some harmonics and DC too, as the mains have these with them already!

[ogden]

If the SNR is low within the capture bandwidth, say 0dB @ 1kHz bandwidth while you need to capture a tone that can range from 1 to 10kHz, then FFT *is* the optimal way

Thing is that there is no 1KHz BW. Kind reminder to stick within specs of OP project (quotes from multiple posts):

The frequency of interest(the fundamental) is in the range of 40Hz to 70Hz,it may have harmonics and DC as well. And I should detect it as fast as possible with a 0.01Hz to 0.02Hz resolution and accuracy.

The Data comes from two 8 channel 24 bit ADCs, the sample rate of ADC is about 62uS.

I have used this filtering algorithm with a 31 tap FIR filter and then use Zero crossing to estimate the frequency, it has very good accuracy, around 0.05Hz, but it has a delay,I need around two cycles of the sin wave to get this accuracy,so that was why I asked the question is there any better, faster alternative way?

[OwO]

40 to 70Hz is almost one octave of bandwidth, and the requirements are very tight (lowest possible latency but high frequency accuracy), so I would say using a MAP-optimal solution is called for, rather than a computationally cheap one.

[OwO]

Something like this: before digitizing, use an analog filter with corner frequency 300Hz. Sample at 5ksps. Take ~128 samples of the input (or roughly one cycle at 40Hz), zero pad it to 1024, and compute FFT. The zero padding will make it easier to interpolate. Find the peak frequency bin, then interpolate around it to find the exact location of the peak.

[ali_asadzadeh]

Something like this: before digitizing, use an analog filter with corner frequency 300Hz. Sample at 5ksps. Take ~128 samples of the input (or roughly one cycle at 40Hz), zero pad it to 1024, and compute FFT. The zero padding will make it easier to interpolate. Find the peak frequency bin, then interpolate around it to find the exact location of the peak.

That's a good plan, how to extract the frequency after I did find the bin with the peak?