FFT speed and Size

[ali_asadzadeh]

Hi,
I have to implement a 16 channel FFT core on either a spartan 6 XC6SLX16 or on a GOWIN GW2AR-18 family.
my Data input is 24bit and I want to do a 256 point FFT, So the question in here is this,
AS I have only 62us total time to do all the FFT calculations on all 16 channels and there are lot of other stuff beside that, so In best case I have about 50% of resources available to me, so this Idea came to me to make a single or dual channel FFT core and share the 16 channels with them, But in core generator for spartan 6 in ISE the best thing I can get for low resources and speed is the Radix2 burst IO which take about 7.1us to calculate a single channel and it would use about 12 DSP blocks, so in this way I can not reach my desired timing. Also Since I only need to extract about 16 harmonics from the input signal and also extract signal phase from the first harmonic, how much does I lose precision to use a lower size FFT, for example 128 point or 64 point one? in this way I can certainly meet my goals for timing and resources,But what happens to the precision for amplitude and phase info? I need to achive at least 0.1 degree phase info for the first harmonic.(and I should implement an arctan block to calculate that too in the same FGPA with other calcs as well)

If I lower the FFT size, the output would scale in the power of 2, what about phase info? how much do I lose?

Is there a better open-source solution to this?

[OwO]

Also Since I only need to extract about 16 harmonics from the input signal and also extract signal phase from the first harmonic, how much does I lose precision to use a lower size FFT, for example 128 point or 64 point one?

If you know the fundamental frequency ahead of time and can set the sample rate to exactly (fundamental * 32), then a 32-FFT will give you exactly the first 31 harmonics. If you average each output over many periods, you can get processing gain in the same way that a larger FFT will, but the frequency error must be small.

Does the data come in in bursts or is it streamed in steadily?
I design FFT cores that beat Xilinx's ones in resource usage and Fmax, but currently I don't have burst IO solutions.

[OwO]

Do you have hard latency requirements or does it simply need to handle a certain data throughput?
A 256-point chunk every 62us * 16 channels means 67MS/s total throughput, which is easy to handle with a single FFT core and input/output interleavers (to get 16 interleaved channels).
Unfortunately this will still use 24 multipliers on Xilinx (if you want 24b data and 24b twiddle).

However it's possible to use a custom multiplier module that runs the DSP units at a higher clock, and you can use 1/4 of the total multipliers if you run them at 67*4 = 268MHz.

[ali_asadzadeh]

The Data comes from two 8 channel 24 bit ADCs, the sample rate of ADC is about 62uS and I want to calculate FFT Before the next sample time of ADC when new data is ready.Is your FFT core open-source?

[OwO]

If you are doing a full FFT at every ADC sample, that means you are doing overlapped FFTs. I recommend using a streaming FFT core and writing your own HDL to do the overlap buffering and channel mux.
https://github.com/owocomm-0/fpga-fft
It's LGPL licensed.

If you want to use less DSP units you need to replace the multiplier implementation that runs the DSP at a higher clock.

[ali_asadzadeh]

Big thumbs up
Thanks for the update, what sort of DSP and logic usage and Fmax should I expect on spartan 6 and Gowin parts? is your code a streaming FFT core?

[OwO]

Spartan 6 is untested - you'll need 4 multipliers per real multiply to get 24 bits data and twiddle, and the timings will suck (DSP48A1 doesn't allow proper cascading without wasting a bunch of fabric registers). Gowin DSP slice is a bit better, but it's still 18x18 and it won't be easy to get it to fit. Either go with 18 bits twiddle and data, or use an FPGA with 25x18 multiplies.

A 256-FFT requires 3 complex multipliers. A complex multiply requires 4 real multipliers. 3*4*4 = 48. My experience is spartan 6/gowin will not run at 268MHz with this core, at least not without a lot of work and whackamole with timing.

[ali_asadzadeh]

Thanks for the info, what's the cheapest FPGA I should Use? I need it to be around 5-10USD

[OwO]

Well depending on the application you might be able to optimize and save a LOT of unnecessary computation; for example do you actually need a new FFT done at every input clock cycle? You have what is effectively an overlap factor of 256, which means a lot of redundant output. Can you set the sample rate as you wish (i.e. the freq*32 suggestion I mentioned)?

[SiliconWizard]

Yeah, not sure why you'd want to compute a whole FFT at every sample, that's a huge overlapping factor that I'm not sure makes sense at all if you consider windowing. If you don't apply any window before FFT, are you sure you know what you're going to get?

[ali_asadzadeh]

Well depending on the application you might be able to optimize and save a LOT of unnecessary computation; for example do you actually need a new FFT done at every input clock cycle? You have what is effectively an overlap factor of 256, which means a lot of redundant output. Can you set the sample rate as you wish (i.e. the freq*32 suggestion I mentioned)?

Actually I can do it, By using Zero crossing algorithm and calculating the input wave frequency, But this algorithm is not that accurate and uses a lot of resources, Do you have something in mind?

[OwO]

So you need to detect a tone with arbitrary frequency and its harmonics? What is the frequency range of the fundamental signal? The solution can range from digital PLL to long, infrequent FFTs to small FFTs.

[ali_asadzadeh]

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.

[colorado.rob]

This video may help you:  The more general uncertainty principle -

The .01Hz resolution places a lower bound on the number of samples required to measure the signal to obtain that level of precision with reasonable  confidence.  And you will need a large FFT to get that level of precision.

[ogden]

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.

You definitely would want to read this thread: https://www.eevblog.com/forum/projects/signal-processing-getting-exact-frequency-from-short-adc-sample/

[nctnico]

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 FFT is not the way to go due to the frequency resolution. I'd go an entirely different route and use a fast microcontroller (70MHz Arm). Sample 16 channels at 500 Hz or so (while making sure to filter anything below10Hz and over 200Hz in the analog domain). Then use a simple frequency counting algorithm with increased resolution by interpolating the zero crossings. I think this question has come up a while ago and someone presented a paper which also showed that this method has very good results with very little downsides. I see Ogden already linked to that thread.

[OwO]

The FFT is not the way to go due to the frequency resolution. I'd go an entirely different route and use a fast microcontroller (70MHz Arm). Sample 16 channels at 500 Hz or so (while making sure to filter anything below10Hz and over 200Hz in the analog domain). Then use a simple frequency counting algorithm with increased resolution by interpolating the zero crossings. I think this question has come up a while ago and someone presented a paper which also showed that this method has very good results with very little downsides. I see Ogden already linked to that thread.

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 (mathematically equivalent to interpolating with a sinc and finding the peak). Doing this embeds the assumption that within these 3 bins there are no interferers, whereas the time domain approach embeds the assumption that there are no interferers across the entire band, so you can estimate processing gain which is going to be directly proportional to FFT size.

However there is absolutely no need to use an overlap factor of 256; actually unless you need to squeeze latency to a minimum I don't see a need to do any overlapping, so that cuts down processing power to 1/256th. Then if you reduce sample rate to 500Sps as suggested you will be able to get away with using a fast MCU. The GD32F303 in LQFP64 package has 16 ADC channels.

[ali_asadzadeh]

You can extract exact frequency from a FFT result by looking at at most 3 adjacent frequency bins and looking at the relative phase (mathematically equivalent to interpolating with a sinc and finding the peak). Doing this embeds the assumption that within these 3 bins there are no interferers, whereas the time domain approach embeds the assumption that there are no interferers across the entire band, so you can estimate processing gain which is going to be directly proportional to FFT size.

Thanks for the info, I do not get it fully how to implement that,would you explain more or show some code snipet?

However there is absolutely no need to use an overlap factor of 256; actually unless you need to squeeze latency to a minimum

Also I need FFT to capture the phase at minimum delay, so I used overlapping, because the thing should do some real time decision as fast as possible based on the input phases.

[OwO]

Also I need FFT to capture the phase at minimum delay, so I used overlapping, because the thing should do some real time decision as fast as possible based on the input phases.

Then a digital PLL is the way to go. How often and how fast does input frequency/phase change? What is the SNR? If SNR is high (>= 40dB), a simple phase/frequency detector can be used for the initial lock. Once lock is obtained a coherent detector (multiply input by complex NCO) + integrate and dump will give you best possible phase and magnitude accuracy.

The only time FFT might be used in a digital PLL is for locking onto a very weak signal with a wide frequency range (e.g. you need 10kHz locking range, but the SNR is only 10dB @ 10Hz bandwidth).

[scatha]

Thanks for the info, I do not get it fully how to implement that,would you explain more or show some code snipet?

The term you're looking for is 'DFT single-tone estimation' - there's a bunch of biased and unbiased, windowed and non-windowed parameter (frequency/phase/amplitude) estimating algorithms out there. Check out Lyon's 'Streamlining Digital Signal Processing' for a comparison.

[nctnico]

The FFT is not the way to go due to the frequency resolution. I'd go an entirely different route and use a fast microcontroller (70MHz Arm). Sample 16 channels at 500 Hz or so (while making sure to filter anything below10Hz and over 200Hz in the analog domain). Then use a simple frequency counting algorithm with increased resolution by interpolating the zero crossings. I think this question has come up a while ago and someone presented a paper which also showed that this method has very good results with very little downsides. I see Ogden already linked to that thread.

No, that is going to work really poorly in the presence of any noise.

Orcourse it will need some averaging over a couple of periods. But by band-filtering the input signal (which can be further improved in the digital domain with relatively little processing power) the out of band noise (and harmonics) will be rejected.

You can extract exact frequency from a FFT result by looking at at most 3 adjacent frequency bins and looking at the relative phase (mathematically equivalent to interpolating with a sinc and finding the peak). Doing this embeds the assumption that within these 3 bins there are no interferers, whereas the time domain approach embeds the assumption that there are no interferers across the entire band, so you can estimate processing gain which is going to be directly proportional to FFT size.

But in the end it comes down to the same while FFT takes a lot of processing power. You'll need to take a long enough piece of signal to allow for windowing and from there FFT will have the same effect as averaging. Your assumption that the time based approach is susceptible to out-of-band frequencies isn't entirely true; it should go without saying that the out-of-band frequencies are filtered away before feeding the signal into the frequency counter algorithm. If push comes to shove the frequency band can be split further for the zero crossing approach. In the end both FFT and zero crossing are equally susceptible to in-band noise / disturbances. Just think about how phase noise will affect the phase information of FFT. However you can add logic to a zero crossing algorithm which just throws away measurements which are out of bounds. For example calculate the standard deviation of the last 10 measurements and use that as a threshold to throw bad measurements out. Given the frequency band the purpose is likely mains so there may be switching spikes and other disruptive signals.

Edit: it seems multiple papers where referenced in the other thread. I was refering to this paper which tested various methods:
https://www.researchgate.net/publication/321255243_Power_System_Frequency_Measurement_for_Frequency_Relaying

[SiliconWizard]

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.

Given that new piece of information... the frequency range of interest is pretty narrow. Why not aggressively filter the signal first (with eg. a band-pass filter)? Since the upper frequency is lower than the lowest harmonic (lowest freq = 40Hz, thus lowest harmonic = 80Hz), then you could just use some simple zero-crossing to estimate the frequency. If the filter is decent, neither average DC nor harmonics should have a high enough level that it would hinder the zero-crossing approach...)

Of course the filter itself will introduce some delay. But as it's always been discussed many times, and in the other thread, you can't have it all anyway. Frequency and time are dual.
A proper band-pass filter would probably be less expensive than even a 256-pt FFT.

[OwO]

Of course the filter itself will introduce some delay. But as it's always been discussed many times, and in the other thread, you can't have it all anyway. Frequency and time are dual.
A proper band-pass filter would probably be less expensive than even a 256-pt FFT.

I think it's pretty similar if you go by the number of multiplications; a 8-tap FIR will require 8 real multiplications per output sample; a radix-4 256-FFT requires 3 complex multiplies which is 3*4 = 12 real multiplications per output sample. The FFT will use more memory, but it does give you much more processing gain. I don't think a 8-tap FIR will do much though, but you can definitely save huge amounts of resources using an IIR filter instead.

[nctnico]

In the decades that I have been doing DSP I have never used a FIR filter because it is too slow and resource hungry. Always IIR and in most cases elliptic filters.

[SiliconWizard]

In the decades that I have been doing DSP I have never used a FIR filter because it is too slow and resource hungry. Always IIR and in most cases elliptic filters.

Really depends on the use case... FIR filters can be made linear phase easily, which can be a plus, or even a requirement. But in this application I don't think it would have any benefit... so yeah, IIR would do it IMO.

[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?

[nctnico]

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.

Sorry but sampling a signal with the highest frequency of interest at 70Hz at 5ksps is insane. A sampling rate of 500Hz leaves more than enough headroom for an analog filter. With a more cleverly choosen samplerate you can go much lower; just make sure to push the aliasing artefacts out of the frequency band of interest.  And then padding to get a decent FFT length just adds to the necessary computation power. As others have pointed out: for this application FFT is not the right choice. You need to use a more optimised algorithm which (unlike plain FFT) doesn't compute results you don't need. For sure these algorithms use the same base as FFT but that doesn't mean that they serve no purpose.

Edit: I'm also not convinced that multiplying the input signal with a rectangle will actually work. Either by stitching multiple chunks together or padding with zeroes there is a chance you introduce frequencies which aren't there which do fall inside the frequency band of interest. Think about partial periods and the sampling won't be aligned with the input waveform.