Choosing FFT convolution lengths

Quick (and dumb) question, but just wanted to make sure I understand.
Supposed I have an input vector x of length N=500. And I also have a filter
vector h of length M=3000. If peforming convolution filtering via FFT, what
should I set the FFT sizes to be? I want the output signal to be the same
size as the input signal (N)

I assume it would need to be greater than N+M-1 to not cause circular
convolution. i.e.
X=fft(x,N+M);
H=fft(h,N+M);
Y=X.*H;
y=ifft(Y,N+M);

.. then would I just cut out the ramp-up/down regions of the filter to get
y to be the same length of x?

Thanks!

On Sat, 19 Feb 2011 15:17:17 -0600, plarser48 wrote:

> Quick (and dumb) question, but just wanted to make sure I understand.
> Supposed I have an input vector x of length N=500. And I also have a
> filter vector h of length M=3000. If peforming convolution filtering via
> FFT, what should I set the FFT sizes to be? I want the output signal to
> be the same size as the input signal (N)
> 
> I assume it would need to be greater than N+M-1 to not cause circular
> convolution. i.e.
> X=fft(x,N+M);
> H=fft(h,N+M);
> Y=X.*H;
> y=ifft(Y,N+M);
> 
> .. then would I just cut out the ramp-up/down regions of the filter to
> get y to be the same length of x?

Well you have the mechanics sorted.  The question you really have to ask 
yourself is why you only want N result samples, and if you do, what sort 
of window you are going to use to throw away the others.

It is possible that your N-in/N-out scenario is part of an on-going 
processing chain, where you want to do this over and over again?  In that 
case you need to re-think your structure to include some memory of 
previous inputs, because "correct" output in that kind of on-going block 
based model has the N samples of output, with M samples of FIR filter 
taps needs at least M samples of input available.

Cheers,

-- 
Andrew

If I understand the proposed system, nothing will work. With an FIR filter length of 3000 stages, the first 3000 outputs are part of the transient. (With late coefficients being small, the transient is largely faded before it is gone completely.

Jerry
-- 
Engineering is the art of making what you want from things you can get.

> The question you really have to ask yourself is why you only want N
result samples

I'll give hypothetical context that came to my head. Suppose I have a
transmission device or medium (perhaps a speaker or a wireless channel)
that through measurement and instrumentation I acquired a high fidelity
spectral profile for. 

As a simple example, I collect samples on the medium for a long time with
no input to gather noise statistics (assume white, stationary). And I also
run a very slow long chirp through to see the frequency response. From
there, I determine frequency response that includes MANY bins. Say it has
thousands of frequency bins (or M=3000 in this case). This is effectively
the "filter" for below.

Now I want to model (not real-time) how a short-burst transmission of N=500
samples of some waveform. I'd like to know the effect of the transmission
medium on the waveform. Or in other words, what is the expected output (as
the same # of samples as input) after it passes through this medium.

In this case, do I do length > M+N-1 FFT sizes? Or do I decimate the
transmission medium "filter" to be of the same size as the input waveform
instead? Or some other technique?

Thanks again!

On 2/19/2011 9:35 PM, plarser48 wrote:
>> The question you really have to ask yourself is why you only want N
> result samples
>
> I'll give hypothetical context that came to my head. Suppose I have a
> transmission device or medium (perhaps a speaker or a wireless channel)
> that through measurement and instrumentation I acquired a high fidelity
> spectral profile for.
>
> As a simple example, I collect samples on the medium for a long time with
> no input to gather noise statistics (assume white, stationary). And I also
> run a very slow long chirp through to see the frequency response. From
> there, I determine frequency response that includes MANY bins. Say it has
> thousands of frequency bins (or M=3000 in this case). This is effectively
> the "filter" for below.
>
> Now I want to model (not real-time) how a short-burst transmission of N=500
> samples of some waveform. I'd like to know the effect of the transmission
> medium on the waveform. Or in other words, what is the expected output (as
> the same # of samples as input) after it passes through this medium.
>
> In this case, do I do length>  M+N-1 FFT sizes? Or do I decimate the
> transmission medium "filter" to be of the same size as the input waveform
> instead? Or some other technique?
>
> Thanks again!

I think you're confusing system frequency response with system modeling. 
  Frequency response, by definition, is *steady state* - that is, 
infinite time.  That doesn't imply an infinite impulse or unit sample 
response of the system at all.  What it implies is an infinite *signal* 
duration at each frequency of which there may be an infinite number as well.

Frequency response doesn't have "bins".  You can binnize a frequency 
response but that's just a choice you make with no particular physical 
meaning.

Samples don't run bare through a medium either... Well, I suppose that 
someone could concoct such a situation but I believe it's not the most 
useful model.

But, indeed, it's likely that the channel will have *some* memory and, 
thus, will elongate the input.  The answer to your question is really 
about just how much memory the channel has.  For example, if the channel 
is the ocean with a submarine in it and represents the round trip for an 
active sonar pulse then the echo returned will be elongated more because 
of the length of the submarine and less due to the environment unless 
there are widely separated multipaths - which is somewhat rare.

Normally the channel model is pretty simple and the output is not much 
longer than the input - well unless you excite a reverberation chamber!!

Fred

On Sat, 19 Feb 2011 23:35:15 -0600, plarser48 wrote:

> Now I want to model (not real-time) how a short-burst transmission of
> N=500 samples of some waveform. I'd like to know the effect of the
> transmission medium on the waveform. Or in other words, what is the
> expected output (as the same # of samples as input) after it passes
> through this medium.

So, your input is some pulse of length <500 samples, and you know a-
priori that it is zero extended on either end.  In that case, you'll need 
to compute the full M+N-1 samples of the convolution of your input pulse 
with your filter impulse response so that you can look at the whole 
thing.  If your system response (h) is largely minimum phase with no 
gross group delay (i.e., compact in lag) then your result will be 
somewhere near the beginning of the convolution result and you can 
perhaps get away with truncating the tail.  If the system has significant 
delay in any frequency range then your result will be significantly 
smeared in time, occupying much more than the N (500) initial samples, 
and it will be up to you which end (or both) you decide you can truncate.

> In this case, do I do length > M+N-1 FFT sizes? Or do I decimate the
> transmission medium "filter" to be of the same size as the input
> waveform instead? Or some other technique?

Convolution of a (compact) signal with a finite-impulse response (an FIR 
filter) of length M (non-zero coefficients) produces M-1 more non-zero 
result values than there were non-zero input values in your input 
sequence.  That's just the way it is.  How you fit that truth to the 
problem you're trying to solve is perhaps up to you.  Decimating the 
transmission impulse response doesn't sound particularly helpful, though.

Cheers,

-- 
Andrew

On Feb 19, 10:17=A0pm, "plarser48" <plarser48@n_o_s_p_a_m.gmail.com>
wrote:
> Quick (and dumb) question, but just wanted to make sure I understand.
> Supposed I have an input vector x of length N=3D500. And I also have a fi=
lter
> vector h of length M=3D3000. If peforming convolution filtering via FFT, =
what
> should I set the FFT sizes to be? I want the output signal to be the same
> size as the input signal (N)
>
> I assume it would need to be greater than N+M-1 to not cause circular
> convolution. i.e.
> X=3Dfft(x,N+M);
> H=3Dfft(h,N+M);
> Y=3DX.*H;
> y=3Difft(Y,N+M);
>
> .. then would I just cut out the ramp-up/down regions of the filter to ge=
t
> y to be the same length of x?

A couple of comments:

1) It seems you have the general mechanics about zero-padding ringt.

2) The filter length M is far greater than the signal length N,
   which is unusual. Why? There is a real chance that you
   *think* you isolate features of the signal when in fact
   you isolate features of the filter.

3) A filtered signal *does* have a longer duration than the
   input signal. If you only want to keep a portion of the
   filtered signal, you will have to justify why.

Rune

Fred Marshall <fmarshallxremove_the_x@acm.org> wrote:

(snip)
> Frequency response doesn't have "bins".  You can binnize a frequency 
> response but that's just a choice you make with no particular physical 
> meaning.
 
> Samples don't run bare through a medium either... Well, I suppose that 
> someone could concoct such a situation but I believe it's not the most 
> useful model.
 
> But, indeed, it's likely that the channel will have *some* memory and, 
> thus, will elongate the input.  The answer to your question is really 
> about just how much memory the channel has.  For example, if the channel 
> is the ocean with a submarine in it and represents the round trip for an 
> active sonar pulse then the echo returned will be elongated more because 
> of the length of the submarine and less due to the environment unless 
> there are widely separated multipaths - which is somewhat rare.

Well, in the case of dispersive media, the returned pulse would
also be elongated.  
 
> Normally the channel model is pretty simple and the output is not much 
> longer than the input - well unless you excite a reverberation chamber!!

Still, for convolution one would expect the output to be at least
as long as max(length input1,length input2).  

-- glen

Thank you all for the very informative and welcoming replies!

I understand that a wireless channel usually a low number of time-domain
filter tap coefficients to model the multipath and/or propagation effects.
But there were some concepts that I wasn't sure how you get around not
having a long-length filter. 

(1) I was reading a section in Rappaport's Wireless Communications (2nd ed)
book labeled "Frequency Domain Channel Sounding", whereby one sweeps across
frequencies, and measuring the response across a channel at varying
frequency ranges. From there an inverse DFT of the S-parameter (Y/X) is
determined to create a time-domain representation of the channel. I think I
am confused. If I were to sweep across hundreds of frequencies, wouldn't I
end up with a very long-length filter resembling the channel from this
sounding technique? 

(2) Or in another application, consider an audio speaker without any
wireless channel effects. A spec sheet may provide the frequency response
of that speaker. Would it be possible to invert that frequency response
such that if a chirp was passed through it, there'd be a flat response?
i.e. if at 15 kHz there is a -3dB drop in power caused by the speaker, have
a pre-filter that boosts 15kHz by 3dB to offset the effect? If so, then
would a long-length filter be needed to catch the full dynamics of the
frequency response of that speaker, or is there another method?

Thanks again!

Hi all,

(I can't speak to the radio question...)

On Sun, 20 Feb 2011 12:32:20 -0600, plarser48 wrote:

> (2) Or in another application, consider an audio speaker without any
> wireless channel effects. A spec sheet may provide the frequency
> response of that speaker. Would it be possible to invert that frequency
> response such that if a chirp was passed through it, there'd be a flat
> response? i.e. if at 15 kHz there is a -3dB drop in power caused by the
> speaker, have a pre-filter that boosts 15kHz by 3dB to offset the
> effect? If so, then would a long-length filter be needed to catch the
> full dynamics of the frequency response of that speaker, or is there
> another method?

Speaker inversion/EQ filters are often indeed quite long.  Not least 
because the four or so octaves that they have to operate across and the 
notchiness typical.  The point to understand is that this is not a 
problem.  There is almost never a suggestion that the signal is time-
limited, and never a requirement that the response be limited to the same 
time.  (Because it isn't.)

Cheers,

-- 
Andrew