Here’s the beef from that paper:
(The reader should realize that an appropriate change must be made to the analysis-i.e., padding the windowed in- put signal with a sufficient number of zero valued samples-to prevent time aliasing when implementing the analysis and syn- thesis operations with FFT's, which have length L . If a modification P(eJWk) has a time response which is effectively No points long, the analysis length L must be at least N +No - 1 where the window length is N.) That’s more or less describing the limits of that approach by using the identity of spectral multiplication and time-domain convolution. For a convolution of N input samples with M filter samples, the result is L= N+M-1. So, if you use an FFT with size L, you can use M-1-L input samples. So you need to zero-pad to avoid artefacts. Best, Steffan > On 24.06.2020|KW26, at 16:10, Corey K <corey...@gmail.com> wrote: > > I think you're mistaken, unfortunately. Block FFT convolution has been around > for 30+ years. In 1977 (43 years ago now), Jont Allen showed in his paper "A > Unified Approach to Short-Time Fourier Analysis" how you can perform FIR > filtering perfectly with the FFT, of COLA windows are used. See equation > 5.2.5 in that paper, and the analysis that precedes it. > > > > > > On Wed, Jun 24, 2020 at 11:16 AM Zhiguang Eric Zhang <zez...@nyu.edu > <mailto:zez...@nyu.edu>> wrote: > that's not true. with FFT/COLA you will necessarily have the Gibbs > phenomenon / ringing / ripple artifacts. certain window types will minimize > this but you will get this phenomenon nonetheless. > > On Wed, Jun 24, 2020 at 9:44 AM Corey K <corey...@gmail.com > <mailto:corey...@gmail.com>> wrote: > I see what you're getting at, I suppose. However, in the context of FIR > filtering I wouldn't refer to this as an artifact. Let's say you gave me an > FIR filter with N-taps and asked me to write a program to implement that > filter. I could implement this using a direct form structure (in the > time-domain), or with the FFT using OLA. Both would give the exact same > results down to numerical precision, with no "artifacts". That's why it > intrigued me when you said "of course it won't have the ripple artifacts > associated with FFT overlap windowing" when referring to software that does > filtering. > > > On Wed, Jun 24, 2020 at 10:59 AM Zhiguang Eric Zhang <zez...@nyu.edu > <mailto:zez...@nyu.edu>> wrote: > ripple is just a known artifactual component of a windowing operation. it's > also known as the Gibbs phenomenon > > http://matlab.izmiran.ru/help/toolbox/signal/filterd8.html > <https://urldefense.proofpoint.com/v2/url?u=http-3A__matlab.izmiran.ru_help_toolbox_signal_filterd8.html&d=DwMFaQ&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=LVW8eOM2POVbM1MauwqppWYiBwmnAs5_i7qiMOEK0-o&s=XefFmTg_gx0qQrZnZTOJDTlaqMl3xt5WBzqxYAkoMKA&e=> > > i'm not referring to any equivalency between time/freq domain filtering > > > On Wed, Jun 24, 2020 at 9:21 AM Corey K <corey...@gmail.com > <mailto:corey...@gmail.com>> wrote: > Not totally understanding you, unfortunately. But if what you are describing > is part of the normal filter response/ringing I guess I wouldn't refer to it > as "artifacts"? FIR filtering can be performed equivalently in the time or > frequency domain. Do you disagree with that statement? > > On Wed, Jun 24, 2020 at 10:02 AM Zhiguang Eric Zhang <zez...@nyu.edu > <mailto:zez...@nyu.edu>> wrote: > yes but any windowing operation is akin to taking a dirac delta function on X > number of samples and thus you will get ringing/ripple artifacts as a > necessary part of the filter response > > On Wed, Jun 24, 2020 at 6:30 AM Corey K <corey...@gmail.com > <mailto:corey...@gmail.com>> wrote: > > of course it won't have the ripple artifacts associated with FFT overlap > windowing > > What is the ripple artifact you are talking about? When using constant > overlap add (COLA) windows the STFT is a perfect reconstruction filterbank. > Likewise block FFT convolution can be used to implement any FIR filtering > operation. > > > > > > > cheers, > -ez > > On Mon, Apr 13, 2020 at 4:55 PM Andreas Gustafsson <g...@waxingwave.com > <mailto:g...@waxingwave.com>> wrote: > Hello Spencer, > > You wrote: > > A while ago I read through some the literature [1] on implementing > > an invertible CQT as a special case of the Nonstationary Gabor > > Transform. It's implemented by the essentia library [2] among other > > places probably. > > > > The main idea is that you take the FFT of your whole signal, then > > apply the filter bank in the frequency domain (just > > multiplication). Then you IFFT each filtered signal, which gives you > > the time-domain samples for each band of the filter bank. Each > > frequency-domain filter has a different bandwidth, so your IFFT is a > > different length for each one, which gives you the different sample > > rates for each one. > > That's the basic idea, but the Gaborator rounds up each of the > per-band sample rates to the original sample rate divided by some > power of two. This means all the FFT sizes can be powers of two, > which tend to be faster than arbitrary sizes. It also results in a > nicely regular time-frequency sampling grid where many of the samples > coincide in time, as shown in the second plot on this page: > > > https://urldefense.proofpoint.com/v2/url?u=https-3A__www.gaborator.com_gaborator-2D1.4_doc_overview.html&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=4rIFY1X4fS1G8-882xM72jF9DvsY6-Z2ckeHxjPPfTY&s=FG-ZGfFa09T-Y7nLajB8evbCy9WIADFrUqPwjz-LHow&e= > > <https://urldefense.proofpoint.com/v2/url?u=https-3A__www.gaborator.com_gaborator-2D1.4_doc_overview.html&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=4rIFY1X4fS1G8-882xM72jF9DvsY6-Z2ckeHxjPPfTY&s=FG-ZGfFa09T-Y7nLajB8evbCy9WIADFrUqPwjz-LHow&e=> > > > Also, the Gaborator makes use of multirate processing where the signal > is repeatedly decimated by 2 and the calculations for the lower > octaves run at successively lower sample rates. These optimizations > help the Gaborator achieve a performance of millions of samples per > second per CPU core. > > > They also give an "online" version where you do > > the processing in chunks, but really for this to work I think you'd > > need large-ish chunks so the latency would be pretty bad. > > The Gaborator also works in chunks. A typical chunk size might be > 8192 samples, but thanks to the multirate processing, in the lowest > frequency bands, each of those 8192 samples may represent the > low-frequency content of something like 1024 samples of the original > signal. This gives an effective chunk size of some 8 million samples > without actually having to perform any FFTs that large. > > Latency is certainly high, but I would not say it is a consequence of > the chunk size as such. Rather, both the high latency and the need > for a large (effective) chunk size are consequences of the lengths of > the band filter impulse responses, which get exponentially larger as > the constant-Q bands get narrower towards lower frequencies. > > Latency in the Gaborator is discussed in more detail here: > > > https://urldefense.proofpoint.com/v2/url?u=https-3A__www.gaborator.com_gaborator-2D1.4_doc_realtime.html&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=4rIFY1X4fS1G8-882xM72jF9DvsY6-Z2ckeHxjPPfTY&s=uuRzi0taGcXI9Sq63G_xTTrCjaz9cu3ewu8jfzIUcVc&e= > > <https://urldefense.proofpoint.com/v2/url?u=https-3A__www.gaborator.com_gaborator-2D1.4_doc_realtime.html&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=4rIFY1X4fS1G8-882xM72jF9DvsY6-Z2ckeHxjPPfTY&s=uuRzi0taGcXI9Sq63G_xTTrCjaz9cu3ewu8jfzIUcVc&e=> > > > > The whole process is in some ways dual to the usual STFT process, > > where we first window and then FFT. in the NSGT you first FFT and > > then window, and then IFFT each band to get a Time-Frequency > > representation. > > Yes. > > > For resynthesis you end up with a similar window overlap constraint > > as in STFT, except now the windows are in the frequency domain. It's > > a little more complicated because the window centers aren't > > evenly-spaced, so creating COLA windows is complicated. There are > > some fancier approaches to designing a set of synthesis windows that > > are complementary (inverse) of the analysis windows, which is what > > the frame-theory folks like that Austrian group seem to like to use. > > The Gaborator was inspired by the papers from that Austrian group and > uses complementary resynthesis windows, or "duals" as frame theorists > like to call them. The analysis windows are Gaussian, and the dual > windows used for resynthesis end up being slightly distorted > Gaussians. > > > One of the nice things about the NSGT is it lets you be really > > flexible in your filterbank design while still giving you > > invertibility. > > Agreed. > > In a later message, you wrote: > > Whoops, just clicked through to the documentation and it looks like > > this is the track you're on also. I'm curious if you have any > > insight into the window-selection for the analysis and synthesis > > process. It seems like the NSGT framework forces you to be a bit > > smarter with windows than just sticking to COLA, but the dual frame > > techniques should apply for regular STFT processing, right? > > I'm actually not that familiar with traditional STFTs and COLA, but as > far as I can tell, the STFT is a special case of the NSGT and the same > dual frame techniques should apply. > -- > Andreas Gustafsson, g...@waxingwave.com <mailto:g...@waxingwave.com> > _______________________________________________ > dupswapdrop: music-dsp mailing list > music-dsp@music.columbia.edu <mailto:music-dsp@music.columbia.edu> > https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=4rIFY1X4fS1G8-882xM72jF9DvsY6-Z2ckeHxjPPfTY&s=br6gIADk3PB9_kF8YoA7aZdcf5McFvCCOlyYso5D2BI&e= > > <https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=4rIFY1X4fS1G8-882xM72jF9DvsY6-Z2ckeHxjPPfTY&s=br6gIADk3PB9_kF8YoA7aZdcf5McFvCCOlyYso5D2BI&e=> > > _______________________________________________ > dupswapdrop: music-dsp mailing list > music-dsp@music.columbia.edu <mailto:music-dsp@music.columbia.edu> > https://lists.columbia.edu/mailman/listinfo/music-dsp > <https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwMFaQ&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=0Zfr9NX2z_qbqorZ4mvWlKWdhvCOnws4tZKFE3J0lxI&s=_0-DUAEnNzJ0nyrUgGHozY0ob4n_-0OWpipEf-p2Bps&e=>_______________________________________________ > dupswapdrop: music-dsp mailing list > music-dsp@music.columbia.edu <mailto:music-dsp@music.columbia.edu> > https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=0Zfr9NX2z_qbqorZ4mvWlKWdhvCOnws4tZKFE3J0lxI&s=_0-DUAEnNzJ0nyrUgGHozY0ob4n_-0OWpipEf-p2Bps&e= > > <https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=0Zfr9NX2z_qbqorZ4mvWlKWdhvCOnws4tZKFE3J0lxI&s=_0-DUAEnNzJ0nyrUgGHozY0ob4n_-0OWpipEf-p2Bps&e=>_______________________________________________ > dupswapdrop: music-dsp mailing list > music-dsp@music.columbia.edu <mailto:music-dsp@music.columbia.edu> > https://lists.columbia.edu/mailman/listinfo/music-dsp > <https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwMFaQ&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=ggIGGD37NXAIrRak00WIRysmpvCxdGGCHkoma2TGgxc&s=2aCxaadCSRm8GtUxELE7DhnWmqkKUkkAymUl19tD-v4&e=>_______________________________________________ > dupswapdrop: music-dsp mailing list > music-dsp@music.columbia.edu <mailto:music-dsp@music.columbia.edu> > https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=ggIGGD37NXAIrRak00WIRysmpvCxdGGCHkoma2TGgxc&s=2aCxaadCSRm8GtUxELE7DhnWmqkKUkkAymUl19tD-v4&e= > > <https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=ggIGGD37NXAIrRak00WIRysmpvCxdGGCHkoma2TGgxc&s=2aCxaadCSRm8GtUxELE7DhnWmqkKUkkAymUl19tD-v4&e=>_______________________________________________ > dupswapdrop: music-dsp mailing list > music-dsp@music.columbia.edu <mailto:music-dsp@music.columbia.edu> > https://lists.columbia.edu/mailman/listinfo/music-dsp > <https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwMFaQ&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=LVW8eOM2POVbM1MauwqppWYiBwmnAs5_i7qiMOEK0-o&s=Wiyf_pAPkjR4_Ox3pi0vTvCNZDjINUsf0bfxVKpiGW8&e=>_______________________________________________ > dupswapdrop: music-dsp mailing list > music-dsp@music.columbia.edu <mailto:music-dsp@music.columbia.edu> > https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=LVW8eOM2POVbM1MauwqppWYiBwmnAs5_i7qiMOEK0-o&s=Wiyf_pAPkjR4_Ox3pi0vTvCNZDjINUsf0bfxVKpiGW8&e= > > <https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=LVW8eOM2POVbM1MauwqppWYiBwmnAs5_i7qiMOEK0-o&s=Wiyf_pAPkjR4_Ox3pi0vTvCNZDjINUsf0bfxVKpiGW8&e=>_______________________________________________ > dupswapdrop: music-dsp mailing list > music-dsp@music.columbia.edu <mailto:music-dsp@music.columbia.edu> > https://lists.columbia.edu/mailman/listinfo/music-dsp > <https://lists.columbia.edu/mailman/listinfo/music-dsp>
_______________________________________________ dupswapdrop: music-dsp mailing list music-dsp@music.columbia.edu https://lists.columbia.edu/mailman/listinfo/music-dsp
