Overlap-Add Question

staufman@gmail.com wrote:
> Ok, I understand what you mean about this not being overlap-add but
> shouldn't my algorithm work nonetheless? In my case, I don't want to
> run a filter over my signal. Instead, in the frequency domain, I
> seriously just need to zero out certain frequency bins and change the
> magnitude of others. Does zero'ing certain bins cause the problem I am
> seeing? Is there anyway around this?

Consider a signal where your frequency is changing.  The 
magnitude and phase of two successive blocks at that 
frequency will not be the same.  Zeroing that frequency 
sample in the FFT for each block effectively subtracts a 
sinusoid from each time domain block with the magnitude and 
phase those frequency samples actually had.  If that is 
different for the two blocks, a discontinuity will be 
created between them.  This comes from modifying something 
on a block basis that is actully changing continuously.

That a block operation has an inverse does not imply an 
intuitive reconstruction if the coeficients are modified 
willy-nilly before taking the inverse.  That's why we do our 
modifications with convolutions, i.e. filters which actually 
do perform overlap-add.


Bob
-- 

"Things should be described as simply as possible, but no 
simpler."

                                              A. Einstein

Jerry wrote:
>> In my case, I don't want to
>> run a filter over my signal. Instead, in the frequency domain, I
>> seriously just need to zero out certain frequency bins
>
> That never works. Infinitely sharp filters in the frequency domain
> introduce unacceptable artifacts into the frequency domain.

I disagree. The zero-phase frequency response of a linear-phase FIR is
just a trigonometric polynomial. Setting bins to zero specifies the
zeros of the polynomial and does not in any way imply infinitely sharp
transition bandwidths. The only drawback of the naive approach is as
O&S put it: "If we evaluate the frequency response corresponding to
such a filter [designed by zeroing bins in frequency domain], we obtain
the rather disappointing curve shown in ...". The stop band attenuation
of such filters is usually lousy because of the wiggly frequency
response in between the specified zeros. But that is another topic.

I pointed out to Salil a thread where we discussed how to implement a
frequency domain FIR with arbitrary modulation of the frequency domain
vector (including setting arbitrary bins to zero) using overlap-save
(which is simpler to implement and more effiicient than overlap-add).
The only way to do that is by shifting the FFT frame by one sample and
using one sample of each output frame to splice the output signal
together.

My advice to Salil is: read about FIR design and time-domain
convolution first before you try frequency-domain convolution. That way
you understand why what you are doing now is not going to work. You'll
find most of what you need in that online book again.

Regards,
Andor

Andor wrote:
> Jerry wrote:
> 
>>>In my case, I don't want to
>>>run a filter over my signal. Instead, in the frequency domain, I
>>>seriously just need to zero out certain frequency bins
>>
>>That never works. Infinitely sharp filters in the frequency domain
>>introduce unacceptable artifacts into the frequency domain.
> 
> 
> I disagree. The zero-phase frequency response of a linear-phase FIR is
> just a trigonometric polynomial. Setting bins to zero specifies the
> zeros of the polynomial and does not in any way imply infinitely sharp
> transition bandwidths. The only drawback of the naive approach is as
> O&S put it: "If we evaluate the frequency response corresponding to
> such a filter [designed by zeroing bins in frequency domain], we obtain
> the rather disappointing curve shown in ...". The stop band attenuation
> of such filters is usually lousy because of the wiggly frequency
> response in between the specified zeros. But that is another topic.
> 
> I pointed out to Salil a thread where we discussed how to implement a
> frequency domain FIR with arbitrary modulation of the frequency domain
> vector (including setting arbitrary bins to zero) using overlap-save
> (which is simpler to implement and more effiicient than overlap-add).
> The only way to do that is by shifting the FFT frame by one sample and
> using one sample of each output frame to splice the output signal
> together.
> 
> My advice to Salil is: read about FIR design and time-domain
> convolution first before you try frequency-domain convolution. That way
> you understand why what you are doing now is not going to work. You'll
> find most of what you need in that online book again.

If you repeat what you wrote at Salil's level of understanding, I think 
you will come close to "That never works." Maybe instead of "infinitely 
sharp" I should have written "apparently (to the naive) infinitely 
sharp". That is more detail than I think the level of the discussion 
warranted. I think we agree on the facts. We differ on the best way to 
help Salil. Your judgment may be better than mine there.

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

Bob Cain wrote:

   ...

> Consider a signal where your frequency is changing.  The magnitude and 
> phase of two successive blocks at that frequency will not be the same.  
> Zeroing that frequency sample in the FFT for each block effectively 
> subtracts a sinusoid from each time domain block with the magnitude and 
> phase those frequency samples actually had.  If that is different for 
> the two blocks, a discontinuity will be created between them.  This 
> comes from modifying something on a block basis that is actully changing 
> continuously.

   ...

A beautiful accounting. One of those insights I wish had occurred to me!

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

Jerry Avins schrieb:
> Bob Cain wrote:
>
>    ...
>
> > Consider a signal where your frequency is changing.  The magnitude and
> > phase of two successive blocks at that frequency will not be the same.
> > Zeroing that frequency sample in the FFT for each block effectively
> > subtracts a sinusoid from each time domain block with the magnitude and
> > phase those frequency samples actually had.  If that is different for
> > the two blocks, a discontinuity will be created between them.  This
> > comes from modifying something on a block basis that is actully changing
> > continuously.
>
>    ...
>
> A beautiful accounting. One of those insights I wish had occurred to me!

Indeed - one is tempted to say that Bob describes things as simple as
possible, but no simpler.

:-)

Regards,
Andor

Andor wrote:
> Jerry Avins schrieb:
>>
>>A beautiful accounting. One of those insights I wish had occurred to me!
> 
> 
> Indeed - one is tempted to say that Bob describes things as simple as
> possible, but no simpler.

<blush>  :-)


Bob
-- 

"Things should be described as simply as possible, but no 
simpler."

                                              A. Einstein