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.

on 2009-06-02 23:53

on 2009-06-03 00:16

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

on 2009-06-05 05:10

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!

on 2009-06-07 06:53

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