Re: FFT and time domain amplitude after FFT convolution


Fred Marshall wrote:
"Michel Rouzic" <Michel0528@xxxxxxxx> wrote in message
news:1142556392.986353.61230@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Fred Marshall wrote:
"Michel Rouzic" <Michel0528@xxxxxxxx> wrote in message
news:1142536511.114291.297400@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
I got a little problem when performing a FFT convolution. I try to have
the output to have the same amplitude as it would with a time-domain
convolution.

To do so, I set the sum of the values of the samples of my kernel to
1.0, and after I FFT the kernel and the signal to convolve, I divide
the values of both signals by the square root of the number of samples
(which is the same since they are both zero-padded so their length
equals both of their original length added together minus 1), I perform
the complex multiplication, IFFT the result and then divide the values
by the quare root of the number of samples again.

However, the result is much quieter than what i expected, I'm pretty
sure I got something wrong, so what's the right way to get to the right
amplitudes? (btw, i'm looking forward being as computationally
efficient as possible, so if the solution could consist of a minimal
number of multiplications, that would be cool)


Michael,

I usually do it empirically with a couple of "sanity checks":

Take a simple kernel like a unit sample in time.
You know that the result of convolution should be and set the IFFT
scaling
accordingly.
The array lengths should be what you're using/doing.

But wait, does it mean that you gotta try convolving a unique sample
with signals of different length, then compare their length and their
amplitude and deduce how you should manage that? I thought about doing
that, but I thought i'd ask people who already know, rather tha trying
with signals of different sizes, kernels of different sizes (like a 1.0
sample and N zeroes) and different buffer size (i'm using what I think
is called overlap-add). Isn't there a general solution?

Your scaling with sqrt(1/N) is that of a physicist and implies 2x the
multiplies of a "normal" DSP scaling approach. Most DSP approaches,
subject
to numeric scaling needs perhaps, use no scaling on FFT and 1/N on IFFT.
If
you change the length of the arrays in frequency, then that makes a
difference.
It's easy to experiment - as above.

Well yeah, actually I did that too, no scaling on both FFT's, and after
the IFFT, division by the number of samples. But that gives a result
that's too loud, a few times too loud, but I thought that it would work
no matter what, so why doesn't it just work? why am I even supposed to
experiment since everybody goes through this when trying to implement
FFT convolution? I'm a bit confused, it works good with a kernel made
of only one sample which value is 1.0 and the rest are zeroes, but
whenever it's something different, although the sum of all it's samples
equal one, it doesn't work (i mean its way to loud)

OK - I'll try to use some numbers then:

I should probably refer you to any number of discussions on comp.dsp that
deal with how processes might be scaled. This is different, if related, to
how the FFT/IFFT processes might be scaled.
For example:
I have a sum of sinusoids at different frequencies all with peak amplitude
1.0 and I want to look at the spectral content after passing the signal
through a lowpass filter.
The lowpass filter has gain 1.0 in the passband - so all the low frequency
sinusoids should pass relatively unaltered in magnitude.
Now we'll take an FFT of the filtered signal.
- some will want each sinusoid to have peaks in frequency with amplitude
0.5.
- some will want each sinusoid to have peaks in frequency with amplitude
1.0.
(I am not going to talk about scalloping losses so each frequency is dead on
a frequency sample point, OK?)
- some will want each sinusoid to have peaks in frequency with amplitude N/2
because that's what an unscaled FFT will generate. If N=100, the peaks will
be 50. This is mentioned below.

Now let's talk about the filter:
You said: the sum of the coefficients of the filter is set to 1.0.
I sure hope it's a lowpass filter or the filter is going to have a lot of
gain!
Why? Because the sum of the coefficients of the filter is the gain at f=0
and if it's a bandpass filter then the in-band gain will be the reciprocal
of the intended gain at f=0.
If the intended gain at f=0 is 0.001 then the passband gain will be scaled
by 1/0.001 = 1000 and, yes the output will be "loud".

oh, i got it. hadn't fully thought about what I was doing by
calculating the sum of samples of my kernel. it's calculating the DC
component, and since it's not necessarly a lowpass FIR (it's more like
a speaker's impulse response)

So, maybe that normalization isn't the best idea except in the case of a
lowpass.
A better normalization will make the filter response 1.0 in the passband.
That's generally what the filter design programs do in the first place.
Presumably what one normally wants to do is to not change the input/output
energy in the passband ("loudness"). That's your objective, right?

Yeah that's pretty much it. The kernel has about all frequencies well
represented (with differences from the max magnitude to the min of
about 30 or 40 dB) and the goal is to have the output sound sounding as
loud as the input.

Now, if you zero pad the filter unit sample response, the passband response
doesn't change. That should be obvious for a lowpass filter because the sum
has to be 1.0 at f=0 no matter how many zeros are added at the end. Zero
padding in time doesn't scale it only interpolates in frequency. Why?
Because zero padding the filter doesn't do anything to the filter whatsoever
and the interpolation is only a higher resolution version of a frequency
response plot of the filter's (atually continuous) frequency response.

Now, take that sinusoid above and double its length. The FFT output will
have peaks of amplitude N/2 as before except now N->2N. If there are 200
samples then the peaks are 100. Why? Because the signal is twice as long
and has twice the energy compared to the case above.
If the sinusoid from the case above were to be zero padded by a factor of 2
then the amplitude peaks in frequency would remain at 50 because the energy
doesn't change.

Summary:
For an enduring signal like a sinusoid, the window duration for the FFT will
affect the energy being processed. And, it will also affect the number of
samples. Accordingly, the frequency peaks will remain at K*N/2 no matter
the width of the window (where K is the amplitude of the signal).
For a time-limited "signal" like the unit sample response of a filter, or a
fixed-length but zero padded version of an enduring signal like a sinusoid,
the number of zeros added will have no affect on the frequency domain peak
amplitudes.

If you're doing filtering by frequency domain multiplication, there should
be no scaling problem.
You can zero pad the filter as much as you need to with no scaling impact.
You can zero pad the signal as much as you need with no scaling impact -
*except* the result will be the same, or nearly the same, as if you had not
zero padded ... from a scaling point of view.

The most straightforward and most often used method I believe is to do this:
- Decide on the time duration N of the signal chunks to be filtered.
- Design the (FIR) filter of length L.

Here is the problem. I got my kernel, but the big question is, to what
do I amplify it. Because as I understand it, my problem is not in what
I do in the process of FFT convolution, but rather how I "amplify" my
kernel (since so far I was basing myself on having the sum of it's
values set to 1.0, which isn't a good idea in my case when the DC
element must be about 30 dB under the peak in the frequency domain)

So, how do I set my kernel to the right amplitude? By setting the sum
of the magnitude bins in the frequency domain to some value based on
its length? The way I see it, if I set the sum of the magnitude bins to
be equal to the sum of the magnitude bins of a delta function of the
exact same length, I should get it right, right? (btw, I have no idea
on how to calculate the one value the magnitude bins for a delta
function based on its length)

- Zero pad it out by (not "to") the length of the signal time duration less
one;
N-1 zeros getting N+L-1
- FFT the zero-padded filter with *no* scaling and save it.
- Grab each chunk of the signal of length N or, alternately and probably
more commonly, N+L-1
- If length N, zero pad out to length N+L-1.
- FFT the signal array with *no* scaling.
- Multiply the N+L-1 length filter and signal arrays in frequency.
- IFFT the product scaling by 1/(N+L-1)

No problem about that. I'm thinking by the way that since I'll
calculate my kernel only once and use it indefinitly (it's about
real-time convolution, so once i have calculated everything for my
kernel I just gotta save it and use it forever if I want), I'm better
of doing the 1/(N+L-1) scaling directly on the kernel (so I wouldn't
have to do it everytime on each buffer)

.

Relevant Pages

  • Re: [Announce] Non Invasive Kernel Monitor for threads/processes
    ... I have attached the description and patch about the non-invasive kernel ... >CGL shall support methods to non-intrusively monitor processes at the kernel level. ... The events which match the filter ... >In the case when we have multiple monitor processes, signals are sent to each monitor ...
    (Linux-Kernel)
  • Re: How can I subtract one frequency from another ???
    ... this being the difference of the 2 input frequencies. ... >It was previously mentioned that this mixer IC would give me the sum and the ... >filter such as a butterworth filter. ... But note that if the inputs are complex signals, ...
    (sci.electronics.basics)
  • Re: Neural netss (was Re: death of the mind.)
    ... its 30+ visual areas and 1100+ feedforward and feedback pathways, ... This whole thing makes sense, regards the cortex, if you think about ... feedback signals from the other 29 areas, ... they filter and perform the basic ...
    (sci.cognitive)
  • Re: Superhet receiver and image frequency
    ... Here I'd like to know why the RF circuit cannot filter the ssignal ... using bandwidth of BT, instead of delegate this task to IF circuit. ... so if you want to use one in a tunable radio it has to go in the ... These two signals will be passed from RF to Mixer because I'm supposing ...
    (comp.dsp)
  • Re: Spectrum analyzer blind spots
    ... trouble looking at the signals in detail. ... and narrow filter to scan a whole range of frequencies... ... analyze on a swept-frequency analyzer. ... spread spectrum energy should make it through the bandpass filter. ...
    (sci.electronics.design)