[hpsdr] FIR filtering and HPSDR

[Erik Anderson]

I do appreciate your thoughts and analysis on the paper.  Let's see if I
can spent a bit more bandwidth and push this farther with some additional
trains of thought.  Apologies if this is a little too long-winded.

First of all, it does appear as though the author is discussing FIR filters
with >1e5 taps to them, but he is not suggesting use of
"Sample_rate*(N-1)/2 where N is the number of taps".  Instead he appears to
be picking N to be "the size at which block convolution becomes more
efficient than direct form filtering; for a typical DSP this might be 32 or
64 samples" and interrupting the algorithm at that point.  The truncated
direct-convolution filter appears to be getting summed with the results of
later-computed FFT operations in order to return the complete filter.
 Unless I am missing something this would permit a zero-latency filter
without incurring the normal delay of a direct-convolution filter.

Processing a filter sample-by-sample may make sense for audio applications,
but I'm getting a strong message that it makes no sense for HPSDR, which is
just too darn fast.  It's impossible for PC applications to receive data
sample-by-sample anyhow, the current protocol returns ethernet packets
containing between 38 samples (@ 4 receivers) and 126 samples (@ 1
receiver).  Any implementation of this approach on PC for HPSDR should not
use direct-convolution.  The highest curve I would be looking at on Fig 6
would be the one labeled "1.5 ms delay", which is absent any
direct-convolution.

The smallest FFT block size he is calculating is one of size 32 or 64, and
he is then scheduling a tree of block sizes of powers of two until he gets
up to the size required to satisfy the filter.  The choice of starting with
such a small number is because of his parallel use of a direct-convolution
algorithm.  As we would not be using direct convolution we are then free to
choose the starting FFT block size to be an arbitrary amount balancing the
amount of latency vs additional complexity and performance.

One possible use for this is in overlapped FFT calculations.  Assuming the
overlap is a (likely small) power of two, and assuming that all windows are
applied _after_ the FFT calculations are done (via replacement with an
equivalent filter), then this approach could be used to _decrease_ the
number of calculations necessary, by setting FFTs first at the GCD of the
overlapped frames and reusing the calculations.

At this point my focus is on Eq 24 (picture version) or Eq 22 (non-picture
version), which seems to be the "magic" in tying two FFT operations
together.  I can't use any further derivations past this point as the
author is assuming real inputs, so I need to pour over the definition of
FFT again to see what this equation represents.

73 and thx as always,
Erik KM2G

On Tue, Sep 9, 2014 at 1:39 PM, Warren C. Pratt <warren at wpratt.com> wrote:

> Hi Eric,
>
> I thought this approach was creative; so, I read part of the paper.  As he
> notes, it's somewhat difficult to implement; however, I'm sure we could
> overcome that.  The real problem with using this algorithm with what we're
> doing on the Jetson board appears to be the amount of computation it
> requires.  If you look at Figure 6, and then project those lines out to,
> for example, 1,000,000, you can see that there's a huge difference in the
> amount of computation required versus the "large block" approach.
>
> By the way, I also disagree with his position the
> direct-time-domain-convolution FIR and his approach are "zero delay."  The
> delay of a linear-phase direct-convolution filter is Sample_rate*(N-1)/2
> where N is the number of taps.  His filter approach will be the same.
>
> Window functions are sometimes used in the generation of the filter
> coefficients.  I think he just didn't really discuss that process.
>
> 73,
> Warren  NR0V
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openhpsdr.org/pipermail/hpsdr-openhpsdr.org/attachments/20140911/be40c081/attachment-0003.htm>