FIR filters and set_history()

GNU Radio
1

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/gnuradio-core/src/lib/runtime/gr_block.h#L62

This seems to be a workaround for the consume() and forecast approach.
So, I use it:
http://gnuradio.org/trac/browser/gnuradio/branches/developers/gnychis/matched_filter/gnuradio-core/src/lib/filter/gr_matched_filter_ccc.cc#L53

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/graphs/mf_delta_zoom.jpg

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/gnuradio-core/src/lib/filter/gr_fir_filter_XXX.cc.t#L82

Thanks!
George

2

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

George N. 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/gnuradio-core/src/lib/runtime/gr_block.h#L62

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-----

3

On Wed, Feb 06, 2008 at 02:11:00AM -0500, George N. 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

4

On Feb 6, 2008 10:42 AM, Eric B. [email protected] 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

5

On 2/6/08, Brian P. [email protected] 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 C.
Corgan Enterprises LLC
http://corganenterprises.com/

6

George N. 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 :slight_smile:

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

Using the “matched filter block” that uses the complex/real-wise inner
product:
http://cyprus.cmcl.cs.cmu.edu/matched_filter/graphs/mf_block.jpg

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

  • George
7

Dan H. 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
8

On Wed, Feb 06, 2008 at 11:46:18AM -0500, Brian P. 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

9

George N. wrote:

This is probably a much better comparison:
http://cyprus.cmcl.cs.cmu.edu/matched_filter/graphs/mf_compare.jpg

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
10

Brian P. wrote in post #628978:

On Feb 6, 2008 10:42 AM, Eric B. [email protected] 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