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.