Author Topic: Impact of new Inverse FFT algorithm  (Read 313 times)

quad4

Impact of new Inverse FFT algorithm
« on: October 12, 2019, 03:10:42 PM »
How will the availability of a cheaper inverse FFT implementation help improve digital domain effects/models? Is what we use today good enough or will this be game changer?

Does a filter or convolutional model become better, cheaper, faster? I assume these use FFT to go to frequency domain and then the inverse transform to get back to the time domain?

https://techxplore.com/news/2019-10-year-old-puzzle.amp

Will it make new types of processing practical, improve quality, reduce dsp/cpu usage, or improve the low or high end of the market?

Rob Strand

Re: Impact of new Inverse FFT algorithm
« Reply #1 on: October 12, 2019, 05:21:16 PM »
Thanks for heads up.

When you have new tools like this it takes a while before people catch on.  You will find people *find* devious and clever ways to solve old problems with the new tool.

My understanding of the motivation for the chirp-Z algorithm is when you want a higher resolution of points over a narrow frequency band.   With the FFT, if you wanted 1024 points between 10kHz and 11kHz you would need to compute an FFT with many more points.   The chirp-Z lets you focus on the smaller region.

IIRC if you try to solve equal problems the chirp-Z is slower than the FFT.

For most audio stuff we use all the points and so we want to compute full FFT's for convolution.  So maybe the FFTs wins for audio. For de-noising of speech, in some parts of the algorithm we don't need a high resolution of points at high frequencies to *analyse* the waveform.  However the algorithm as a whole needs the full FFT to process the signal.

So the way I see it the FFT will hold-up for some time until some of the more clever and indirect uses of the new algorithm are found.
« Last Edit: October 12, 2019, 06:06:18 PM by Rob Strand »
The mind often distorts without gain.

ElectricDruid

Re: Impact of new Inverse FFT algorithm
« Reply #2 on: October 12, 2019, 06:29:38 PM »
+1 agree with Rob. It's not a huge game changer, but sooner or later someone will figure out a way to take advantage of the potential speed-up it offers and get more out of less.

T.


PS: Your assumption about digital filters is wrong - most never go to the frequency domain. Digital time domain filtering techniques are well developed and extensive. No FFT/IFFT required.

potul

Re: Impact of new Inverse FFT algorithm
« Reply #3 on: October 14, 2019, 10:28:10 AM »
Interesting.... is there a relationship between Chip-z and a Constant-Q ? Could this be used to compute an inverse Contant-Q?

I see the value of a FFT/IFFT-like transform that accomodates the way musical notes are spread in the spectrum

Mat

ElectricDruid

Re: Impact of new Inverse FFT algorithm
« Reply #4 on: October 14, 2019, 04:27:10 PM »
I see the value of a FFT/IFFT-like transform that accomodates the way musical notes are spread in the spectrum

There are some cunning tricks using different sampling rates for that sort of thing - it's not what you're after (which I agree would be nice), but it can get you closer. For higher frequencies, a higher sample rate is obviously required. But if you come down an octave, you can also drop the sample rate by an octave and still maintain the same quality. This can be very handy for stuff like a vocoder where you've got multiple bands to process, but each band is only a limited group of frequencies.

It's the only example I can think of where "octaves" really come into play, but I don't do a lot of serious DSP, so others will know better. The PICs I use are not the ideal platform for that!

Rob Strand

Re: Impact of new Inverse FFT algorithm
« Reply #5 on: October 14, 2019, 05:42:54 PM »
Quote
Interesting.... is there a relationship between Chip-z and a Constant-Q ? Could this be used to compute an inverse Contant-Q?

It's not obvious to me but I don't have a deep knowledge of the Chirp-z transform.  And it's quite possible someone might find some tricky way to use the Chirp-z transform for that job in the future.

What did occur to me after this thread is the possibility of processing specific frequency bands with the Chirp-Z.    For example if we only want EQ 4kHz to 8kHz, (for the sake of the argument approximating a constant Q equalizer).   A real filter or equalizer will affect the spectrum outside of the 4kHz to 8kHz region, so you would expect some "non ideal" behaviours by chopping the spectrum.  If we added some guard bands to allow a transition say 3kHz to 9kHz it might help.  However if we need to add guard bands 2kHz to 16kHz then we are already stretching the window to cover most of the spectrum and the whole idea of focusing on a smaller region is lost.

Quote
I see the value of a FFT/IFFT-like transform that accomodates the way musical notes are spread in the spectrum
There's already a constant Q algorithm.  It's quite slow but people have invented fast versions.    It's used for *analysing* signals.    (AFIK) The problem is there's no inverse like a true transform-pair but people have worked on approximate inverses.   The other avenue is filter banks covering unequal spans.

One of the problems with FFT processing is messing with the signal in the frequency domain in a way which is non-minimum phase.  For example if we make an equalizer and just change the magnitudes the results can be quite unnatural. 

Another problem is we are making modifications to *points*  what happens between the points can be vastly different to the points.    If you look at this curve fit (not and FFT) you can see oscillations between the points, which can get large in some instances.  Changing relatively far way points can cause large changes to the shape,



A good example of such bad behaviours is the Equalizers built into sound cards.  You can decrease bands above 3kHz and the treble increases!
The mind often distorts without gain.