Fast-convolution filtering on real signal

On Wednesday, November 21, 2012 2:06:47 PM UTC-8, gongdori wrote:
> ...

> 
> Thanks all for your reply.
> I considered shifting it to baseband and using some efficient filter such
> as cic, and shift it back up, but I need to compensate for sinx/x roll off.
> Thus, I decided to go for fast convolution filter.

To implement this efficiently, you use a multi-stage lowpass/desampling architecture, perform the sinc, etc. correction at a much reduced frequency, and then upsample back to the original Fs. Filter structures for the desampling portion have been recently discussed here.

> ...
> I couldn't find the paper, DESIGN AND EFFICIENT IMPLEMENTATION OF SINGLE
> FILTER FREQUENCY-RESPONSE MASKING FIR FILTERS, but Thanks!

If you go to the referenced site, click on the file icon (rectangle with folded down corner) that says "PDF" on it, press it to download. It is in the upper right of the page.

> I am about to code up to test what b-j mentioned, but it would be great if
> I can see how it works mathematically. If you have any reference on this,
> could you let me know please? 
> Thanks so much!!!

If you consider the FFT/filter/IFFT approach, it is simply a method of performing multiple, equally spaced instantiations of the translate/lowpass filter/translate when one DFT output has adequate bandwidth. The transforms also do the de- and up- sampling. And you still have to do the sinc (or transform of whatever other window you choose) correction. The one window class that avoids this correction is the flattop window family, but you may need bandpass filtering of the bin data anyway in your narrow band doesn't exactly match a DFT bin.

Good luck!

Dale B. Dalrymple
 

On 11/21/12 5:06 PM, gongdori wrote:
> I am about to code up to test what b-j mentioned, but it would be great if
> I can see how it works mathematically.

it actually is quite simple.  all you need is linearity and the 
knowledge that you don't get imaginary values out of a real convolution:

                                L-1
     y[n]  =  h[n] (*) x[n]  =  SUM{ h[i] x[n-i] }
                                i=0

if h[n] and x[n] are both real, then y[n] must also be real.

(*) means discrete-time convolution.

so consider (with real h[n], x1[n], x2[n]):

   h[n] (*) (x1[n] +  j x2[n]) = h[n](*)x1[n]  + j( h[n](*)x2[n] )

so the imaginary part of the result is exactly what you would get with 
x2[n] alone (and real).  this is true if and only if Im{ h[n] } = 0.


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

There are quite many tricks you can play, but it requires knowing more
about the problem.

You can use intentional aliasing: decimate and allow the wanted signal to
alias somewhere in a lower bandwidth. The trick is: make sure that nothing
else can alias to the same frequency range. This ends up with a filter
design problem where most of the bandwidth is covered with "don't-care"
areas, allowing simple filtering (or, none at all) at the "expensive" high
sample rate. Whatever filtering is then done at the lower rate is
considerably cheaper.

----------------------------------

If you want to try frequency-masking filters, I've got a design script
here
http://www.dsprelated.com/showarticle/180.php
But: I'd expect it to save maybe 70 % of the computational load, where the
above method might save 99.9 % and seems more straightforward to design.

On Thursday, November 22, 2012 1:21:57 PM UTC-8, mnentwig wrote:
> There are quite many tricks you can play, but it requires knowing more
> about the problem.

A common situation on comp.dsp.

> ...
> If you want to try frequency-masking filters, I've got a design script
> here
> http://www.dsprelated.com/showarticle/180.php
> But: I'd expect it to save maybe 70 % of the computational load, where the
> above method might save 99.9 % and seems more straightforward to design.

Your single stage 70% solution isn't very efficient, but it doesn't seem very narrowband either. Could you provide the design script for your 99.9% solution so that we can see how narrowband it is so we can evaluate the validity of your comparison?

Dale B. Dalrymple

Hello,

the design script is for a generic frequency masking lowpass, and it
achieves similar performance as reported in a reference paper (discussion
in the blog entry).

>> Could you provide the design script for your 99.9% solution 
I'd first have to invent an artificial problem that allows a 99.9 %
improvement. For example, use a 192k audio converter to track fluctuations
in the 50 Hz AC line frequency. 

The solutions I had in mind are all textbook-level multi-rate DSP. The
difficulty is IMO not to design the filter, but to understand the
requirements well enough in order to decide how to do the job best.

For example, simply adding n samples can act as a fairly efficient
alias-reject filter if the wanted signal happens to be close enough to 0
Hz:
http://www.dsprelated.com/showcode/262.php
Or then, design an appropriate CIC filter and select the parameters looking
at all possible alias responses, and the input power that is present at
each (i.e. if there is no input signal at a frequency that aliases over the
wanted signal after decimation, I can disregard it completely). 

"mnentwig" <24789@dsprelated> writes:
> [...]
> For example, simply adding n samples can act as a fairly efficient
> alias-reject filter if the wanted signal happens to be close enough to 0
> Hz:
> http://www.dsprelated.com/showcode/262.php

and

> Or then, design an appropriate CIC filter [...]

They are the same thing, apart from possibly a scale factor. That is, a
CIC filter is identical to a moving average filter.
-- 
Randy Yates
Digital Signal Labs
http://www.digitalsignallabs.com

>They are the same thing, apart from possibly a scale factor. That is, a
>CIC filter is identical to a moving average filter.
it's a special case, yes, but an intuitive one.

On Saturday, November 24, 2012 7:01:47 AM UTC-8, mnentwig wrote:
> Hello,
> 
> the design script is for a generic frequency masking lowpass, and it
> achieves similar performance as reported in a reference paper (discussion
> in the blog entry).

So neither relates to a narrowband process.

>
> >> Could you provide the design script for your 99.9% solution 
> I'd first have to invent an artificial problem that allows a 99.9 %
> improvement. For example, use a 192k audio converter to track fluctuations
> in the 50 Hz AC line frequency. 
> ...

So neither of the numbers you compare relates to the op's question? (This is comp.dsp so I won't suggest that this is really something that can be expected. :) ) You have compared efficiency of a single stage wideband lowpass to a potentially multi-pass narrowband process. It's nice to find a place to hawk the results of your work, but I think the comparison of two narrowband implementations would be less of a grapes to grapefruit comparison.

Dale B. Dalrymple

>> It's nice to find a place to hawk the results of your work, but I think
the comparison of two narrowband implementations would be less of a grapes
to grapefruit comparison.

Hello,

please allow me to summarize my earlier posts in a few, simple words:

- From a frequency masking filter I'd expect 70 % savings over plain ol'
FIR
- But usually, one can save a lot more with run-of-the-mill textbook
methods.
- both statements are "educated guesses", based on general past experience
and knowing very little about the specific problem. Your mileage -will-
vary. 

----------------------------------------------------------

More simple words: "Keep it simple and stupid". As far as the problem
allows. 
If the original task is like "design a lawn mover", proposing a
frequency-masking filter seems to me about as practical as starting the
project with a turbine engine. 

----------------------------------------------------------

Then, the "narrowband" topic: 
If anybody still wants to try the turbine-powered racing lawn mover
variant, my "frequency masking" design script can be changed to bandpass
response by editing the following line

    mask = (abs(omega) <= 0.3);

into something like 
    mask = (abs(omega) >= 0.2) .* (abs(omega) <= 0.3);

And then the engineering work starts for real. I'm not "hawking" this as a
turnkey solution - find a consultant. Instead, please consider it an
opportunity to reuse large parts of existing code that took quite a while
to write. 
For a real-world design, expect that you'll have to dig a lot deeper than
this trivial change.

-Markus

>> lawn mover
but let's spell it with a "w" :-)