0
$\begingroup$

So, I'm (I think) aware of how the overlap and add algorithm for linear convolution works, but my question is that, suppose I have a FFT-ed set of sequences that belong to a large sequence.

  1. Can I add the overlapping parts before taking the IFFT of each sequence?

  2. Can I add the overlapping parts and then perform another convolution without taking another set of IFFTs and FFTs?

  3. Let's say that I have a function which multiplies by 3 if the number is 0 in the time domain, but multiplies by 6 if it isn't. I can perform this with only one IFFT as opposed to an IFFT+ a FFT by taking the IFFT and then multiplying in the frequency domain by the required number. Can I do a convolution through overlap and add, apply the aforementioned function through the "one IFFT only technique" and then do another convolution through the overlap and add method without having to do another set of FFTs for the next convolution through the overlap and add?

$\endgroup$
  • $\begingroup$ In 3. What do you want to multiply with 3 or 6? The sample in the time-domain or in the frequency-domain (where it isn't a single sample anymore)? $\endgroup$ – Oscar Jan 23 '17 at 10:43
  • $\begingroup$ In the frequency domain. I understand it isn't a single sample, but if I take the IFFT of each separate sample, then I should be able to multiply in the frequency domain, right? Sorry if this is a stupid question :( $\endgroup$ – user3003467 Jan 23 '17 at 16:17
1
$\begingroup$

your FIR, $h[n]$ can be converted, once and for all, into $H[k]$ the spectrum with which you will multiply in the frequency domain. but for every frame of $x[n]$, you must zero pad and FFT that into $X[k]$, multiply that $X[k]$ by $H[k]$ (which now becomes $Y[k]$) and you must iFFT that back into $y[n]$ and overlap add with the previous frame of $y[n]$.

$\endgroup$
  • $\begingroup$ I was asking if I can do the addition in the frequency domain since additions are identical under linear transforms. $\endgroup$ – user3003467 Jan 23 '17 at 16:12
  • $\begingroup$ your question is pointless. you don't have to do overlap-add or overlap-save at all if you make your FFT large enough. but if your data is billions of samples (because you're running this real-time for over a day) and your impulse response is only a hundred thousand samples long, then you need to figure out how you're going to do this. $\endgroup$ – robert bristow-johnson Jan 23 '17 at 18:33
1
$\begingroup$

1) Can I add the overlapping parts before taking the IFFT of each sequence?

Yes, but you will also end up adding the non-overlapped parts as well. Before the IFFT the non-overlapped and overlapped parts are completely mixed together in the intermediate spectral product, and can't be separated (except by an IFFT or equivalent). So you can't add only the overlapped parts before taking the IFFT, which is likely what you are asking.

And, yes. If you leave out the FFT (and FFT'd data), you can do overlap add convolution without an IFFT. Just use regular linear convolution to compute each block segment, instead of the FFT+IFFT pairs. This is how a very long data streams might actually be filtered given a sufficiently short FIR filter kernel in a system with limited-size buffer or block based input and/or limited working memory.

$\endgroup$
  • $\begingroup$ 1) Could you give me an example pseudocode or a link to a resource of how to do this? I would greatly appreciate this! Thank you for your help by the ways :) 2) I probably stated this badly. Let's say I have a Overlap and Added convolution but I haven't done the iFFT yet, so they're still in the frequency domain. I add them in the frequency domain, and since each piece of data is still in the frequency domain, I convolve each one again with an equal sized kernel. Can I do this? $\endgroup$ – user3003467 Jan 23 '17 at 16:13
  • $\begingroup$ Also, how would this be different with overlap and save? How would I do overlap and save in the frequency domain before the IFFT? $\endgroup$ – user3003467 Jan 23 '17 at 16:18
  • $\begingroup$ my suggestion @user3003467 is to get O&S and really learn how the DFT works regarding convolution (that it performs circular convoluion), that the FFT is an efficient implementation of the DFT, and exactly how overlap-add (OLA) and overlap-save (OLS) using this tool that does circular convolution and gets that tool to perform linear convolution. $\endgroup$ – robert bristow-johnson Jan 23 '17 at 18:31
  • $\begingroup$ Thanks, could you point me to any resources by chance? $\endgroup$ – user3003467 Jan 24 '17 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.