downsampling -> FFT -> upsampling

Fred Marshall wrote:
> 
> "Erik de Castro Lopo" <nospam@mega-nerd.com> wrote in message
> news:42524DB2.396F6AB2@mega-nerd.com...
> > "Fred T. Weiler" wrote:
> >>
> >> Hi!
> >>
> >> I'm experimenting with FFT and inverse FFT, doing some filtering in
> >> real-time.
> >> It sounds good but it's a bit too CPU heavy
> >
> > So why not filter in the time domain which in most cases is much less
> > CPU intensive.
> 
> Erik,
> 
> If the filter is FIR and of any appreciable length then the longer the
> filter the more time is saved by the FFT/*/IFFT method.  But you knew that
> didn't you? 

Yes :-).

However, FIR filters are mostly used where linear phase or
absolute guaranteed stabiltiy is required.

Outside of the above two requirements, IIR filters beat the
pants off frequency domain methods. (I am also aware that 
IIR filters can be applied in the frequency domain :-)).

Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo  nospam@mega-nerd.com (Yes it's valid)
+-----------------------------------------------------------+
"The beauty of religious mania is that it has the power to
explain everything. Once God (or Satan) is accepted as the first
cause of everything which happens in the mortal world, nothing
is left to chance...logic can be happily tossed out the window."
- Stephen King

"Fred T. Weiler" <nospam@nospam.com> wrote in message 
news:7nu4e.134088$dP1.471149@newsc.telia.net...
> >
>> Exactly what do you do? I believe there is a post filter involved after 
>> the
>> upsample stage. If you leave that out, you'd get all sorts of artifacts
>> in the data.
>>
>> Rune
>>
>
> Hi Rune,
>
> I take a buffer of size bufsize and:
>
> 1. Throw away every second sample to obtain a buffer of size bufsize/2.
>
> 2. Perform an FFT on that stream (size: bufsize/2).
>
> 3. Adjust the bins and perform the inverse FFT.
>
> 4. Add one (linear) interpolated sample making the buffer twice as big 
> again (= bufsize),
> which is the original size.
>
> Shouldn't it work? It doesn't.
> NOTE: It works fine if I do just (2) and (3). But if I add (1) and (4) 
> then it sounds *very* strange.
> Hard to describe in words, a bit like a comb filter with a metallic touch 
> and I can hear a
> tendency of echoes.

Fred,

Well, I've read all the posts so far and it sounds like "there's nothing 
wrong here or there but somewhere".  Time to reevaluate.  So my remarks are 
intended to suggest areas to investigate.

> I take a buffer of size bufsize and:
>
> 1. Throw away every second sample to obtain a buffer of size bufsize/2.

As others have said, you shouldn't do this without filtering first.  It's 
easy enough to apply a halfband filter just to see what happens.  But, read 
on.  There is likely a better way that will save a bunch of compute time.

>
> 2. Perform an FFT on that stream (size: bufsize/2).

This could be the problem.  The array size needs to be =>L+M-1 where L is 
the length of the filter and M is the length of the data sequence.  You need 
to zero pad to get this on both the filter and the data.
>
> 3. Adjust the bins and perform the inverse FFT.

It's still unclear to me what this operation called "adjust" really is.  The 
proper operation is to multiply with a reasonable filter FFT.
>
> 4. Add one (linear) interpolated sample making the buffer twice as big 
> again (= bufsize),
> which is the original size.
>

Now, for interpolation you don't need to add interpolated samples in time if 
you're already working in the frequency domain.  Here's how:
In principle, you can replicate the spectrum to double the sample rate. 
Doing this alone will introduce unwanted frequencies as you can imagine. 
So, you want to replicate the spectrum (which is almost a no-op because you 
don't have to actually *do it*).  Then you apply a half-band filter before 
the IFFT.  This is much more efficient than interpolation in the time 
domain.

If you do replicate the spectrum, I might suggest at the risk of being 
hammered by purists that IF the spectrum is low around fs/4 and 3fs/4 then 
you can *assume* that the samples in frequency between these two are zero 
and don't bother to multiply away the nonzero terms around fs/2.  In other 
words multiply by a "perfect" halfband filter that is 1.0 in the passband 
and 0.00 in the stopband.  Of course, then you don't multiply at all!

Note well: the longer an FFT, the more efficient it is.  So, instead of 
decimating in time at all, just do an FFT that's 2x as long.  Then filter 
accordingly by multiplying.  Then IFFT.  Don't interpolate in time.  This is 
well known to be more efficient by a huge amount if the array is of any 
appreciable size.  Mind the overlap stuff.

Fred

> Fred,
>
> Well, I've read all the posts so far and it sounds like "there's nothing
> wrong here or there but somewhere".  Time to reevaluate.  So my remarks are
> intended to suggest areas to investigate.

Sure. Thanks. I appreciate all input.

> > 1. Throw away every second sample to obtain a buffer of size bufsize/2.
>
> As others have said, you shouldn't do this without filtering first.  It's
> easy enough to apply a halfband filter just to see what happens.  But, read
> on.  There is likely a better way that will save a bunch of compute time.

OK. Then I should lowpass filter at Fs/4 (= 11.025 kHz), right?
But do I gain anything else than reducing a slight distortion in the upper
frequency regions? The problem is that the resulting audio sounds like
it has flams/delays in it plus some nasty comb filtering.

> > 2. Perform an FFT on that stream (size: bufsize/2).
>
> This could be the problem.  The array size needs to be =>L+M-1 where L is
> the length of the filter and M is the length of the data sequence.  You need
> to zero pad to get this on both the filter and the data.

Yup.

> > 3. Adjust the bins and perform the inverse FFT.
>
> It's still unclear to me what this operation called "adjust" really is.  The
> proper operation is to multiply with a reasonable filter FFT.

Sorry. More precise: I do a complex multiplication on each element in the filter
FFT and the input signal.

> Now, for interpolation you don't need to add interpolated samples in time if
> you're already working in the frequency domain.  Here's how:
> In principle, you can replicate the spectrum to double the sample rate.
> Doing this alone will introduce unwanted frequencies as you can imagine.
> So, you want to replicate the spectrum (which is almost a no-op because you
> don't have to actually *do it*).  Then you apply a half-band filter before
> the IFFT.  This is much more efficient than interpolation in the time
> domain.

Hmmm, is it really? Applying the half-band filter will require some computation
on the whole array. And the array size is equal to the size of the output samples.
Sounds like it'd take at least around the same time.

> If you do replicate the spectrum, I might suggest at the risk of being
> hammered by purists that IF the spectrum is low around fs/4 and 3fs/4 then
> you can *assume* that the samples in frequency between these two are zero
> and don't bother to multiply away the nonzero terms around fs/2.  In other
> words multiply by a "perfect" halfband filter that is 1.0 in the passband
> and 0.00 in the stopband.  Of course, then you don't multiply at all!

I'm not sure if I understood it. You mean that if the buffer size is [0 - top], then
I'd double the array size and zero the items at [top+1 - top*2] ?
Won't I get phase problems then?

> Note well: the longer an FFT, the more efficient it is.  So, instead of
> decimating in time at all, just do an FFT that's 2x as long.  Then filter
> accordingly by multiplying.  Then IFFT.  Don't interpolate in time.  This is
> well known to be more efficient by a huge amount if the array is of any
> appreciable size.  Mind the overlap stuff.

Yeah, well I've experimented with different sizes on the original sample rate.
But no matter how much I optimize it could still be optimized even more
by downsampling.

Fred

Fred T. Weiler wrote:

>> > 1. Throw away every second sample to obtain a buffer of size bufsize/2.
>>
>> As others have said, you shouldn't do this without filtering first.  It's
>> easy enough to apply a halfband filter just to see what happens.  But,
>> read
>> on.  There is likely a better way that will save a bunch of compute time.
> 
> OK. Then I should lowpass filter at Fs/4 (= 11.025 kHz), right?

yes.

> But do I gain anything else than reducing a slight distortion in the upper
> frequency regions?

Aliasing is NOT a slight distortion in the upper frequency regions.
The upper half of the original spectrum is folded back into the new
downsampled spectrum, so the whole new spectrum is affected.

bye
Andreas
-- 
Andreas H�nnebeck | email: ah@despammed.com
----- privat ---- | www  : http://www.huennebeck-online.de
Fax/Anrufbeantworter: 0721/151-284301
GPG-Key: http://www.huennebeck-online.de/public_keys/andreas.asc

> Aliasing is NOT a slight distortion in the upper frequency regions.
> The upper half of the original spectrum is folded back into the new
> downsampled spectrum, so the whole new spectrum is affected.
>
> bye
> Andreas

Guys,

Given a signal obtained at sampling frequency F. Assume that the signal
would have been sampled at the rate of F/2 instead of F. Then it would look
exactly the same as if we traverse the signal sampled at rate F and throw
away every second sample.

It's a completely different story if you start throwing away, say, every third
sample or keep 4 samples and throw away every fifth. That's an error.

But I'm talking about obtaining the signal as it would look if it would have
been sampled at F/2. Then it's indeed possible to throw away every
second sample. It's equivalent to as how the signal would have looked
if it had been sampled at F/2 instead of F.

Fred

I found the error.
When I downsample, then the window length became much longer in time and
the  overlaps got much more easy to identify/hear. I used 4 overlapping windows
which were separated 90 degrees and since the actual FFT got much longer
after downsampling, then there was a noticable stutter (or delay).

However, I eliminated two of the overlapping windows and kept only two
separated 180 degrees and picked another window function (triangle).
Then it worked. However, it's not 100% perfect (I'm a perfectionist).
I've tried different overlap windows. I'm using a 50% overlap now, but I
find it hard to find a function which one cannot hear. I've thought about
using just a short overlap only over the actual seams rather than using
two windows which are crossfaded across the whole window.
Do you have any recommendations?

Fred

Fred T. Weiler wrote:
> I found the error.
> When I downsample, then the window length became much longer in time
and
> the  overlaps got much more easy to identify/hear. I used 4
overlapping windows
> which were separated 90 degrees and since the actual FFT got much
longer
> after downsampling, then there was a noticable stutter (or delay).
>
> However, I eliminated two of the overlapping windows and kept only
two
> separated 180 degrees and picked another window function (triangle).
> Then it worked. However, it's not 100% perfect (I'm a perfectionist).
> I've tried different overlap windows. I'm using a 50% overlap now,
but I
> find it hard to find a function which one cannot hear. I've thought
about
> using just a short overlap only over the actual seams rather than
using
> two windows which are crossfaded across the whole window.
> Do you have any recommendations?
>
> Fred

Leaving aside the downsampling, if you are splitting your input into
consecutive  blocks of N samples, and assuming that the impulse
response of your filter is less than N samples long, then zero pad both
blocks of input samples and the filter impulse response to length 2N
before applying a 2N point FFT, multiplying and then applying a 2N
point IFFT to give 2N sample output blocks which should be overlapped
50%. The only window functions necessary are rectangular, i.e. implied
by taking blocks.
I think that will work. Hope it helps.

Donald

> Leaving aside the downsampling, if you are splitting your input into
> consecutive  blocks of N samples, and assuming that the impulse
> response of your filter is less than N samples long, then zero pad both
> blocks of input samples and the filter impulse response to length 2N
> before applying a 2N point FFT, multiplying and then applying a 2N
> point IFFT to give 2N sample output blocks which should be overlapped
> 50%. The only window functions necessary are rectangular, i.e. implied
> by taking blocks.
> I think that will work. Hope it helps.
>
> Donald
>

Uh? You'll need some sort of window function to get rid of the glitches at
the edges of each block. I tried a Hamming window and it works fine.
Haven't tried Hanning yet.

Fred

Fred T. Weiler wrote:
>>Aliasing is NOT a slight distortion in the upper frequency regions.
>>The upper half of the original spectrum is folded back into the new
>>downsampled spectrum, so the whole new spectrum is affected.
>>
>>bye
>>Andreas
> 
> 
> Guys,
> 
> Given a signal obtained at sampling frequency F. Assume that the signal
> would have been sampled at the rate of F/2 instead of F. Then it would look
> exactly the same as if we traverse the signal sampled at rate F and throw
> away every second sample.

You're correct - it would look the same. However, if the signal contains 
frequency components higher than F/2 - then when you throw away half 
your samples you've just aliased your acquired signal. Just because "it 
looks the same" doesn't mean it is correct.

Another example, say your signal is just a sinuisoid higher than F/2. If 
I sample at F it will still look like a sinusoid but it has the wrong 
frequency - it looks (and is treated) like has a lower frequency than it 
really does.

> 
> It's a completely different story if you start throwing away, say, every third
> sample or keep 4 samples and throw away every fifth. That's an error.

Nope. It's the same thing. What's so special about the factor 2. Why is 
it an error for 3 but not for 2??

> 
> But I'm talking about obtaining the signal as it would look if it would have
> been sampled at F/2. Then it's indeed possible to throw away every
> second sample. It's equivalent to as how the signal would have looked
> if it had been sampled at F/2 instead of F.

> 
> Fred
> 
> 

Cheers,
David

Fred T. Weiler wrote:
> Given a signal obtained at sampling frequency F. Assume that the signal
> would have been sampled at the rate of F/2 instead of F. Then it would look
> exactly the same as if we traverse the signal sampled at rate F and throw
> away every second sample.
> 

If you sample at F, you generally have an analog filter that knocks out 
everything above F/2.  If you sample at F/2, you need an analog filter 
to knock out everything above F/4.

If you do NOT have an analog filter that cuts off at F/4, you cannot 
sample at F, throw away every other sample and get the same sequence you 
would have gotten had you sampled at F/2.

If your signal has components in the F/4 to F/2 band, they will alias 
into the F/4 to 0 band when you decimate by 2.  You have to get rid of 
them first by some method, be it analog or digital.

Said another way - When you decimate by 2, the components you have 
between F/4 and F/2 WILL appear unattenuated between F/4 and 0.  If 
those components are zero, this will not be a problem.  If they are near 
zero, it will only be a small problem.  If they are large, it will be a 
big problem.

-- 
Jim Thomas            Principal Applications Engineer  Bittware, Inc
jthomas@bittware.com  http://www.bittware.com    (603) 226-0404 x536
Hope springs occasionally.