Forum: GNU Radio Question on fir filter implementation(gr_fir_ccf_generic)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
isulsz (Guest)
on 2009-06-03 01:53
(Received via mailing list)
I have two questions regarding to the FIR filter implementation.
I understand that the output of a FIR filter is the sum of the
multiplications of filter taps and previous (and current) inputs, or
simply
speaking, a convolution, y[n] = \sum_{k from 0 to L-1}  h[k]  *  x[n-k].

Take gr_fir_ccf_generic for example, the code introduce a parameter
N_UNROLL(= 2 or 4) and seems to break the summation into N_UNROLL parts:
acc0,acc1,acc2,acc3 (if U_UNROLL == 4). and then sum them together. What
is
the reason for doing this?

Another confusion is that, the summation is like this:
acc0 += d_taps[i+0] * input[i+0];
acc1 += d_taps[i+1] * input[i+1];
acc2 += d_taps[i+2] * input[i+2];
acc3 += d_taps[i+3] * input[i+3];

Why here is input[i PLUS SOMETHING]? I think these are FUTURE(but not
PREVIOUS) values of the current input (the current input is input[0] if
I
understand the code correctly).

Thank you very much!
--
View this message in context:
http://www.nabble.com/Question-on-fir-filter-imple...
Sent from the GnuRadio mailing list archive at Nabble.com.
Eric B. (Guest)
on 2009-06-03 02:16
(Received via mailing list)
On Tue, Jun 02, 2009 at 02:49:58PM -0700, isulsz wrote:
>
> I have two questions regarding to the FIR filter implementation.
> I understand that the output of a FIR filter is the sum of the
> multiplications of filter taps and previous (and current) inputs, or simply
> speaking, a convolution, y[n] = \sum_{k from 0 to L-1}  h[k]  *  x[n-k].
>
> Take gr_fir_ccf_generic for example, the code introduce a parameter
> N_UNROLL(= 2 or 4) and seems to break the summation into N_UNROLL parts:
> acc0,acc1,acc2,acc3 (if U_UNROLL == 4). and then sum them together. What is
> the reason for doing this?

Manual loop unrolling like this allows some compilers to generate
better code.  The dependency chain is shorter.

> Another confusion is that, the summation is like this:
> acc0 += d_taps[i+0] * input[i+0];
> acc1 += d_taps[i+1] * input[i+1];
> acc2 += d_taps[i+2] * input[i+2];
> acc3 += d_taps[i+3] * input[i+3];
>
> Why here is input[i PLUS SOMETHING]? I think these are FUTURE(but not
> PREVIOUS) values of the current input (the current input is input[0] if I
> understand the code correctly).

The delay line is implicitly contained in the input.

See the .h file:

  /*!
   * \brief compute a single output value.
   *
   * \p input must have ntaps() valid entries.
   * input[0] .. input[ntaps() - 1] are referenced to compute the output
value.
   *
   * \returns the filtered input value.
   */
  virtual gr_complex filter (const gr_complex input[]);


FWIW, the code you're looking at is the guts of the generic C++
implementation of the filter.  The GNU Radio block that corresponds is
gr_fir_filter_ccf.{h,cc}


Eric
Shizheng Li (Guest)
on 2009-06-05 07:10
(Received via mailing list)
Thanks! But sorry, I am not completely sure I understand it. According
to my
understanding, when input[0] ... input[ntaps()-1] is put into the filter
function, the filter output is the output when input[ntaps()-1] just go
into
the filter. input[0] should multiply with the tap gain corresponding to
the
most delayed tap ( z^{-ntaps()-1} , the last one in the delay line). And
this is the reason why in the set_tap() function and the constructor,
you
need a gr_reverse(taps).  More specifically, the filter taps given to
the
filter is in an order where the first one is the tap gain for no delay,
the
second one is the tap gain for one delay z^{-1}, ..., we need to reverse
the
order because we hope input[ntaps-1()] multiply with the tap gain of no
delay.

Am I correct?


Thanks!
Eric B. (Guest)
on 2009-06-07 08:53
(Received via mailing list)
On Thu, Jun 04, 2009 at 10:07:32PM -0500, Shizheng Li wrote:
> delay.
>
> Am I correct?
> Thanks!

One more bit of information that may help you understand:

The input is "prestuffed" with ntaps - 1 zeros before the real samples.
This is handled by the "history" method of the calling GNU Raduio
block.

You are correct that we reverse the taps so that we can process both
the taps and the input in the same order.  That is, as a straight dot
product.

Looking at the QA code (e.g., qa_float_dotprod*.cc) might help you
understand what's going on.

Eric
This topic is locked and can not be replied to.