Zero Padding for Non-Causal Filters
in [DSP]
|
Prev: DSK 6713
Next: alternatives to correlation
From: Scott T. on 22 Mar 2010 15:44 I am implementing a non-causal filter in the frequency domain. The filter frequency response is defined by an analytic function. To ensure that the result corresponds to linear convolution, I must zero pad the input and impulse response to L+P-1 samples. This is easy enough for the input signal. However, I don't have the impulse response of the filter, so I "indirectly" zero pad by sampling more finely in the frequency domain. However, I don't think the conventional method of zero padding after the input signal works for non-causal filters. According to Stanford CCRMA, "if the FIR filter is noncausal, then zero-padding is needed before the input signal in order not to ``cut off'' the ``pre-ring'' of the filter." (https://ccrma.stanford.edu/~jos/fp/General_LTI_Filter_Matrix.html) I don't understand the reason for zero-padding before the input rather than after. Does anyone know how to zero-pad correctly in this situation?
From: robert bristow-johnson on 22 Mar 2010 23:35 On Mar 22, 3:44 pm, "Scott T." <scott_t7339(a)n_o_s_p_a_m.yahoo.com> wrote: > I am implementing a non-causal filter in the frequency domain. The filter > frequency response is defined by an analytic function. To ensure that the > result corresponds to linear convolution, I must zero pad the input and > impulse response to L+P-1 samples. i might have a better idea of what this means if L and P are defined. is L the FIR length and P-1 the number of padded zeros? > This is easy enough for the input > signal. However, I don't have the impulse response of the filter, so I > "indirectly" zero pad by sampling more finely in the frequency domain. > > However, I don't think the conventional method of zero padding after the > input signal works for non-causal filters. According to Stanford CCRMA, > "if the FIR filter is noncausal, then zero-padding is needed before the > input signal in order not to ``cut off'' the ``pre-ring'' of the filter." > (https://ccrma.stanford.edu/~jos/fp/General_LTI_Filter_Matrix.html) > > I don't understand the reason for zero-padding before the input rather than > after. Does anyone know how to zero-pad correctly in this situation? first of all, non-causal FIR filters only make sense when you are convolving your non-causal impulse response with a file of data not in real-time (heck, it can be faster than real-time, but any real-time process has to be causal). zero padding is not an issue if your convolution summation is the simple FIR summation (with a negative bottom limits to the summation). the zero-padding only is an issue of you're doing "fast convolution", using an FFT, multiplication in the frequency domain, inverse FFT and either overlap-add or overlap-save. if the FFT or DFT length is N, you need to pad the FIR with N-L zeros before it gets DFT and stored as frequency-domain data for the fast convolution. in that case, you can always just adjust (delay) the FIR to be causal and account for that delay by advancing the output by the same amount. then the padding issue is identical to what it is for a causal FIR. the hop length between frames is N-L+1 (one more than the number of padded zeros). given an FIR length, L, there is an optimal power of two, N, that the computational cost per processed sample is minimized. see http://groups.google.com/group/comp.dsp/browse_frm/thread/6c9c1195d9226b55/5af3612b9f0fa5e9 .. but i don't get what the issue is regarding non-causal FIR. for real- time you ain't doing non-causal. for non-real-time it really doesn't make any difference; delay the impulse response to make it causal, deal with it like any other causal impulse response, and do the bookkeeping or accounting at the output. r b-j
From: HardySpicer on 23 Mar 2010 03:11 On Mar 23, 8:44 am, "Scott T." <scott_t7339(a)n_o_s_p_a_m.yahoo.com> wrote: > I am implementing a non-causal filter in the frequency domain. The filter > frequency response is defined by an analytic function. To ensure that the > result corresponds to linear convolution, I must zero pad the input and > impulse response to L+P-1 samples. This is easy enough for the input > signal. However, I don't have the impulse response of the filter, so I > "indirectly" zero pad by sampling more finely in the frequency domain. > > However, I don't think the conventional method of zero padding after the > input signal works for non-causal filters. According to Stanford CCRMA, > "if the FIR filter is noncausal, then zero-padding is needed before the > input signal in order not to ``cut off'' the ``pre-ring'' of the filter." > (https://ccrma.stanford.edu/~jos/fp/General_LTI_Filter_Matrix.html) > > I don't understand the reason for zero-padding before the input rather than > after. Does anyone know how to zero-pad correctly in this situation? Can I buy your non-causal filter when it is ready - last week.
From: jim on 23 Mar 2010 11:48 "Scott T." wrote: > > I am implementing a non-causal filter in the frequency domain. The filter > frequency response is defined by an analytic function. To ensure that the > result corresponds to linear convolution, I must zero pad the input and > impulse response to L+P-1 samples. This statement is not valid. If you do linear convolution using your impulse response (no matter how you happened to arrive at that IR) - It will still be linear convolution. And how you decide to doctor the data being convolved won't change that. If you add zeroes before or after or add some other sequence of data to before or after the data sequence it will still be linear convolution. If you are not concerned with causality the concept of "before" and "after" is itself a completely arbitrary naming convention. > This is easy enough for the input > signal. However, I don't have the impulse response of the filter, so I > "indirectly" zero pad by sampling more finely in the frequency domain. > > However, I don't think the conventional method of zero padding after the > input signal works for non-causal filters. According to Stanford CCRMA, > "if the FIR filter is noncausal, then zero-padding is needed before the > input signal in order not to ``cut off'' the ``pre-ring'' of the filter." > (https://ccrma.stanford.edu/~jos/fp/General_LTI_Filter_Matrix.html) > > I don't understand the reason for zero-padding before the input rather than > after. Does anyone know how to zero-pad correctly in this situation? Asking how to do something "correctly" makes little sense since you haven't supplied any context by which anyone else could judge what might be more or less correct. There may be valid reasons for adding zeroes to the beginning of your finite data sequence or there may be no good reason for doing that. For instance if you are applying this filter to one line in a digital video image you may want to pad that sequence in such a way so that you can produce a new sequence that is the same length and has the same zero phase registration as the original sequence. Using a linear phase impulse response of odd length N and padding the data sequence with (N-1)/2 points would be one way of achieving that. Making the padded points zero may or may not be the best choice depending on the effect you wish to achieve. -jim
From: Scott T. on 23 Mar 2010 18:16
Thank you for your replies. I guess I should have made it more clear that I am doing the filtering in the frequency domain by multiplying FFTs. This corresponds to a circular convolution unless you zero pad both the input and impulse response to L+P-1 before taking the DFT. I don't have an explicit version of the impulse response, so it is difficult to just delay the response to make it causal. Although I suppose I could multiply the frequency response function by a complex exponential to create a delay. My real question is where the zeros padding needs to be in a non-causal filter for the output to be identical to linear convolution, not circular convolution. In this case, I figured out that traditional zero padding actually gives me a circularly shifted version of a linear convolution. Knowing where to take the samples from solves the problem. |