1
$\begingroup$

I was reading the answer to this question provided by Phil Karn.

In the answer, it has been said:

Ensure that the impulse response of your lowpass filter is shifted to the front of your time domain buffer AND properly windowed to M samples before you take the forward FFT to get the frequency domain representation of your filter. This keeps the result from wrapping around in the time domain when you take the inverse FFT. (Remember you're actually doing circular convolution when you want linear convolution.)

I know that windowing is important because of spectral leakage but I do not completely understand this paragraph.

I think in this paragraph some important points are mentioned which are worth explaining in more detail.

What does exactly "shifting the impulse response of a filter to the front of the time domain" mean?

It has been said that "This keeps the result from wrapping around in the time domain when you take the inverse FFT". Is this a result of "shifting the impulse response of a filter to the front of the time domain" or a result of "windowing"?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ See time domain aliasing. $\endgroup$
    – mhdadk
    Jun 4 at 13:47
  • $\begingroup$ @mhdadk What a terrible name. Each time it should be said that nothing is aliased in the sense that circular convolution is executed exactly. $\endgroup$
    – OverLordGoldDragon
    Jun 5 at 12:34
  • $\begingroup$ @OverLordGoldDragon how I think about it is this: any time I see “aliasing”, I think “multiplication by a Dirac comb”. Time-domain aliasing occurs because the DTFT is multiplied by a Dirac comb along the unit circle to get the DFT, which is equivalent to convolution with a Dirac comb in the time domain. This is what I think of when I read “circular convolution”. $\endgroup$
    – mhdadk
    Jun 5 at 14:16
  • $\begingroup$ @mhdadk Well what a terrible contriving. All we have is finite sequences and a finite formula, and to understand this concept we must invoke several more concepts as or more complicated than the DFT, with infinities, and even more work to relate the convolution theorems. For over a year I thought it meant FFT conv's just an approximation, since there's "distortions". It's false advertising in a more important way to call it "aliasing", in that it implies a flawed output where a linear convolution would be flawless. The better term is "boundary effects"; zero extension != necessarily correct. $\endgroup$
    – OverLordGoldDragon
    Jun 5 at 14:54
  • $\begingroup$ @OverLordGoldDragon could you please add an answer of your own explaining what you mean? I'm sure other users on dsp.SE would appreciate it. $\endgroup$
    – mhdadk
    Jun 5 at 15:20

1 Answer 1

Reset to default
1
$\begingroup$

Well, as mentioned by the original answer, "I assume you already know the basic rules for fast convolution: the FFT length N is equal to the data blocksize L plus the length of the filter impulse response M minus 1. Each operation uses L samples of new data plus M-1 samples of data from the old block."

The OP was going to do fast convolution i.e. FFT convolution, by taking FFT of the signal and multiplying by the FFT of the lowpass filter. What you quoted and what I just quoted, taken together, is just saying that

  1. when taking FFT of the signal he needs to pad the signal with zeros at the end before FFT'ing.
  2. when taking FFT of the lowpass filter he also needs to pad the signal with zeros at the end before FFT'ing.
  3. Of course, (1) and (2) need to be padded to the same FFT length, for multiplication between them to be possible.
  4. The total FFT length required is L+M-1, where L is the actual data length of (1) and M the actual data length of (2).
  5. Now, if the lowpass filter impulse response were sampled earlier than its first meaningful output sample, M would include leading zeros, those leading zeros would still have to be counted, making M unnecessarily big. If the FFT length is smaller than L+M-1, the multiplication and then iFFT would create a convolution where the tail of the response wraps over to the beginning, per circular convolution. That's why the impulse response should be pushed all the way to the beginning / left / front.
  6. Finally because lowpass filters are typically IIR filters, their impulse response actually nominally go on forever so you need to crop it to M with a windowing function. The quality and length of the window function will determine how much of the low-pass-filtering of the designed LPF actually makes its way through to the FFT multiplication.

Hope that helps...

Improve this answer
$\endgroup$
4
  • $\begingroup$ First in 6 years, neat. +1, but the answer's completed by explaining the role of unpadding relative to padding, which is about how the DFT "sees" inputs per the standard implementation of FFT. 'same' output mode isn't achieved by taking first M or N samples of such (right-padded) FFT convolution, for example. $\endgroup$
    – OverLordGoldDragon
    Jun 5 at 12:55
  • 1
    $\begingroup$ Thanks @OverLordGoldDragon. I read some of you posts and they're far over my head. In fact I don't think I even understand your caveat about "same" or how you would "complete" this answer. And most math formulas about this stuff look like alien inscriptions to me. But I thought I knew enough from my daily tinkering to answer this one :P $\endgroup$
    – user25849
    Jun 5 at 23:33
  • $\begingroup$ "alien inscriptions" is exactly what I called it years ago, and still do for the shenanigans they do at MO! $\endgroup$
    – OverLordGoldDragon
    Jun 6 at 16:29
  • 1
    $\begingroup$ @OverLordGoldDragon that gives me hope! 😆 $\endgroup$
    – user25849
    Jun 7 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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