Forum: GNU Radio FIR filters and set_history()

Ac73d95c8ccddff9ecae369bcb80a923?d=identicon&s=25 George Nychis (Guest)
on 2008-02-06 08:10
(Received via mailing list)
Hi all,

Sorry that this e-mail is long, but I'm trying to be as detailed as
possible for those reading it to understand, otherwise it will take a
couple e-mail exchanges.

I'm attempting to build a filter using the fir filter class, but have
some questions.  Let's assume for a second that set_history() does not
exist.

What I would do is use forecast() to state that the number of input
items needed to produce noutput_items is: fir->ntaps()+noutput_items

What general_work() would do is use the first ntaps() samples as
"history" and start producing output at in+ntaps().  I would then
consume ninput_items-ntaps() to then keep those last ntaps() samples in
the input queue as the "history" for the next series of input.

I'm sorry if my logic is slightly or completely off.  But then I look at
most of the FIR filters, and see the use of set_history(), great!  This
sounds like it is exactly what I want.  Furthermore, looking at the
documentation it states that it is what I want:
http://gnuradio.org/trac/browser/gnuradio/trunk/gn...

This seems to be a workaround for the consume() and forecast approach.
So, I use it:
http://gnuradio.org/trac/browser/gnuradio/branches...

I monitor the actual input to the block by writing to the disk the
complex input samples from the pointer 'in' to 'in+noutput_items.'  I've
noticed that the first time the block is called, there are history()
worth of 0 valued samples pre-pended in my input stream.  Great, I'm
assuming the architecture is placing my "history" in my input stream for
the FIR filter to work correctly, which on first call is "nothing."

What I'm assuming here is that there is actually history()+noutput_items
in the input buffer.  I'm also assuming that a call to filterN(out, in,
noutput_items) would actually skip history() worth of samples in the
input buffer first, and then compute noutput_items.  Yes/no?  If not, it
would make no sense to me that with noutput_items, I would actually only
call filterN(out,in,noutput_items-history()).  Furthermore, I see no
blocks do this.

OK, so, I go ahead and give it a run.  Logically, with set_history() it
should all work to me.  My first call to work(), noutput_items==2064,
and my history is always set to 224.  If set_history() works as I
expect, I would assume my first 2064 items to be correct.  However, only
2064-224=1840 are correct, verified hacking up the matched filter in C
(thanks Brian).

http://cyprus.cmcl.cs.cmu.edu/matched_filter/graph...

That graph is taking the difference of the true value to the observed
value using the matched filter block.  At 1840, the output values start
going haywire, which I'm assuming is due to the fact that there is not
really noutput_items+history() in the input buffer, but noutput_items.
Once the matched filter skips history() worth of data, and tries to
compute noutput_items, it starts venturing in to no mans land.

Is this really how it is supposed to work?  Or, is there a bug?  The
next time work() is called, the input stream is pre-pended again with
what I actually expect to be the "history" of samples to be.  But again
the last ntaps() output items are incorrect, which is why I'm assuming
it's going in to no mans land again.

If this is how it's supposed to work, then I fear gr_fir_filter_XXX is
incorrect when the decimation is set to 1:
http://gnuradio.org/trac/browser/gnuradio/trunk/gn...

Thanks!
George
3dfb724cefc1eddbade1e8bd1ee6131f?d=identicon&s=25 Dan Halperin (Guest)
on 2008-02-06 10:21
(Received via mailing list)
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

George Nychis wrote:
> What general_work() would do is use the first ntaps() samples as
> "history" and start producing output at in+ntaps().  I would then
> consume ninput_items-ntaps() to then keep those last ntaps() samples in
> the input queue as the "history" for the next series of input.
>
> I'm sorry if my logic is slightly or completely off.  But then I look at
> most of the FIR filters, and see the use of set_history(), great!  This
> sounds like it is exactly what I want.  Furthermore, looking at the
> documentation it states that it is what I want:
> 
http://gnuradio.org/trac/browser/gnuradio/trunk/gn...

What set_history actually does is prepend that many zero samples. But it
still adds forecast(noutput_items) samples to the input buffer before
calling work... So when work() is called with noutput_items,
history+forecast(noutput_items) samples are ready in the input buffer,
starting from index 0.

If you look at the implementation of filterN, it reads at samples
0..ntaps-1. So when you call filterN with noutput_items as the length
parameter it will eventually read items 0..noutput_items+ntaps-1. Here
you've set ntaps = history.

In the normal code in the trunk, this works just as expected. But when
you make your custom vectors, you only pull noutput_items out of the
input buffer, not noutput_items+history.

Also, my understanding of a normal matched filter is that it does the
normal complex multiplication (by the conjugate, but I'm assuming you've
done that already before building the taps), not the real-wise and
complex-wise ... inner product, I guess? ... as you've defined it.

- -Dan
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFHqXwCy9GYuuMoUJ4RApVoAKDC3Xrm7spiGzCZZNaS5tvYuPXzzwCfbQzN
pjjttuBVpMgY4vPo6l5/KLc=
=QVtD
-----END PGP SIGNATURE-----
745d8202ef5a58c1058d0e5395a78f9c?d=identicon&s=25 Eric Blossom (Guest)
on 2008-02-06 16:45
(Received via mailing list)
On Wed, Feb 06, 2008 at 02:11:00AM -0500, George Nychis wrote:
> Hi all,
>
> Sorry that this e-mail is long, but I'm trying to be as detailed as
> possible for those reading it to understand, otherwise it will take a
> couple e-mail exchanges.
>
> I'm attempting to build a filter using the fir filter class, but have some
> questions.  Let's assume for a second that set_history() does not exist.
>

Hi George, the gr_fir_XXX* routines assume that the delay line is
"in-line".  This is, the delay line is implicit and that the calling
code (all the GNU Radio framework) does the right thing to ensure that
this is the case.

The history mechanism does work as it was designed to do.  For a
history setting of N, it effectively preloads the first buffer with
N-1 zeros.

If you've got a question about how it behaves, there's lots of QA code
for it. Take a look at filter/qa_gr_fir_fff.cc or _ccc.cc

Eric
79723aa1b24981dcec2dbf7fd59403c1?d=identicon&s=25 Brian Padalino (Guest)
on 2008-02-06 17:47
(Received via mailing list)
On Feb 6, 2008 10:42 AM, Eric Blossom <eb@comsec.com> wrote:
> The history mechanism does work as it was designed to do.  For a
> history setting of N, it effectively preloads the first buffer with
> N-1 zeros.

So just to be clear, if we have 2 calls to work() where we set the
history to 5 taps for a FIR filter.  The first input:

    [ 0 0 0 0 1 2 3 4 5 ]

Will have 5 input items and produce 5 output items.  If we then call
work() again with 5 more input items, are we looking at:

    [ 2 3 4 5 6 7 8 9 10 ]

  - or -

    [ 0 0 0 0 6 7 8 9 10 ]

In essence, who's job is it to maintain state in the filter?

Brian
Ac73d95c8ccddff9ecae369bcb80a923?d=identicon&s=25 George Nychis (Guest)
on 2008-02-06 18:43
(Received via mailing list)
Dan Halperin wrote:

> In the normal code in the trunk, this works just as expected. But when
> you make your custom vectors, you only pull noutput_items out of the
> input buffer, not noutput_items+history.
>


You're exactly right with this, I'm forgetting that I'm creating new
input buffers but only extracting noutput_items from the original input
buffer.  I tested this and get the exact output I'm looking for now.

One line diff:
-  split_complex(in, noutput_items, in_real, in_imag);
+  split_complex(in, noutput_items+history(), in_real, in_imag);

I needed to pull history() additional items from the input queue, which
makes sense.

> Also, my understanding of a normal matched filter is that it does the
> normal complex multiplication (by the conjugate, but I'm assuming you've
> done that already before building the taps), not the real-wise and
> complex-wise ... inner product, I guess? ... as you've defined it.

I had thought I could use gr_fir_filter_ccc, setting my taps to be the
time reversed version of the input signal, but found that it wasn't
correlating.  I think what I was missing is the fact you are suggesting
that the taps be the complex conjugate of the input signal?

- George
D0072e69d706bb3ca211d33a1b536e2c?d=identicon&s=25 Johnathan Corgan (Guest)
on 2008-02-06 18:46
(Received via mailing list)
On 2/6/08, Brian Padalino <bpadalino@gmail.com> wrote:

>     [ 2 3 4 5 6 7 8 9 10 ]

This one.  The zeroes are prepended at the start of the flowgraph
execution.  After that, the input just "slides" along at the same rate
as the input items are consumed.

--
Johnathan Corgan
Corgan Enterprises LLC
http://corganenterprises.com/
Ac73d95c8ccddff9ecae369bcb80a923?d=identicon&s=25 George Nychis (Guest)
on 2008-02-06 18:55
(Received via mailing list)
George Nychis wrote:
> I had thought I could use gr_fir_filter_ccc, setting my taps to be the
> time reversed version of the input signal, but found that it wasn't
> correlating.  I think what I was missing is the fact you are suggesting
> that the taps be the complex conjugate of the input signal?
>

You are apparently correct :)

Using the FIR with time reversed complex conjugate of the desired input
signal:
http://cyprus.cmcl.cs.cmu.edu/matched_filter/graph...

Using the "matched filter block" that uses the complex/real-wise inner
product:
http://cyprus.cmcl.cs.cmu.edu/matched_filter/graph...

The FIR filter method seems to have much better properties, creating a
much larger magnitude in the output.

- George
Ac73d95c8ccddff9ecae369bcb80a923?d=identicon&s=25 George Nychis (Guest)
on 2008-02-06 19:02
(Received via mailing list)
George Nychis wrote:
>
This is probably a much better comparison:
http://cyprus.cmcl.cs.cmu.edu/matched_filter/graph...

The difference between what I would consider the maximum noise level of
the inner product method and the correlation peak is: 160-45=115

For the FIR filter, 225-75=150.

Just approximations.

- George
745d8202ef5a58c1058d0e5395a78f9c?d=identicon&s=25 Eric Blossom (Guest)
on 2008-02-06 19:08
(Received via mailing list)
On Wed, Feb 06, 2008 at 11:46:18AM -0500, Brian Padalino wrote:
> Will have 5 input items and produce 5 output items.  If we then call
> work() again with 5 more input items, are we looking at:
>
>     [ 2 3 4 5 6 7 8 9 10 ]   <-- This


>   - or -
>
>     [ 0 0 0 0 6 7 8 9 10 ]
>
> In essence, who's job is it to maintain state in the filter?
>
> Brian


The way we've implemented the FIR, the state is all implicit in the
input. When using history == ntaps, the standard housekeeping handles
it for you.  forecast ensures that you've got enough valid input for
the given number of output samples.  Outside of a bit of magic that
preloads the zeros before the first time call, the rest of it is
handled in forecast.

Eric
80814b9c47da06f90a295d3a1deb9c6c?d=identicon&s=25 Nico Doronzo (nicodoro)
on 2014-04-19 14:32
Brian Padalino wrote in post #628978:
> On Feb 6, 2008 10:42 AM, Eric Blossom <eb@comsec.com> wrote:
>> The history mechanism does work as it was designed to do.  For a
>> history setting of N, it effectively preloads the first buffer with
>> N-1 zeros.
>
> So just to be clear, if we have 2 calls to work() where we set the
> history to 5 taps for a FIR filter.  The first input:
>
>     [ 0 0 0 0 1 2 3 4 5 ]
>
> Will have 5 input items and produce 5 output items.  If we then call
> work() again with 5 more input items, are we looking at:
>
>     [ 2 3 4 5 6 7 8 9 10 ]
>
>   - or -
>
>     [ 0 0 0 0 6 7 8 9 10 ]
>
> In essence, who's job is it to maintain state in the filter?
>
> Brian

Hi Brian,

I didn't get the point. When you call work() the second time, which is
the input buffer you are looking at

[ 2 3 4 5 6 7 8 9 10 ]  or [ 0 0 0 0 6 7 8 9 10 ]?

Niko
Please log in before posting. Registration is free and takes only a minute.
Existing account

NEW: Do you have a Google/GoogleMail, Yahoo or Facebook account? No registration required!
Log in with Google account | Log in with Yahoo account | Log in with Facebook account
No account? Register here.