Re: [Discuss-gnuradio] sync_interpolator

[Martin Braun (CEL)]

Let's cover some signal processing basics:

Say our block's input signal is x[k] and the output signal is y[k].
Let's assume there's one input to keep things simple.

If a block has a history of N, the output depends on N samples of the
input, or
y[k] = f(x[k], x[k-1], ..., x[k-N-1]).

If the block is linear, then
y[k] = \sum_{l = 0}^{N-1} a_l x[k-l]
Any block like this is equivalent to an FIR filter, regardless of what
it's called.

But say we *are* actually filtering, and have an odd number of taps.
How about making a filter with zero phase? That would ask for:
y[k] = \sum_{l = (N-1)/2}^{(N-1)/2} a_l x[k-l]

Whoops--if we want to keep causality, that won't work. /That's/ a block
that would be looking into the future.[1]

So we relax the requirements, and simply use the next samples we have
available in the input buffer. But what about the delay line?
GNU Radio understands this problem, and offers to take care of the delay
line for you by providing set_history(). So let's think of set_history()
as a signal-processing related setting.

forecast() is an entirely different beast. It tells the scheduler how
man input items a block requires before it can produce any (or a given
amount of) output. In a sync block, we 'trick' the scheduler to give us
more samples to include the delay line (when we consume noutput_items
items, the delay line is still in there).
So if you override forecast(), then yes, obviously, the scheduler will
give you this much input. It's hard-wired to do so.

In a sync block (and related, i.e. sync_interpolator), it is *always*
clear how many input items I need to produce an number of output items.
That's why forecast() needn't be overridden in those cases (probably:
shouldn't); the stock blocks *do* stick to this (with, possibly, some
exceptions but I can't think of any right now).

In a gr::block, things are different. You only choose this type of block
if you don't know the ratio input:output (or there isn't a rational
one). An example of the latter is the fractional resampler (its
forecast() looks very much like that of a sync_interpolator!).
An example of the former would be any gr_tagged_stream_block.

There are other settings that control streaming behaviour, such as
set_output_multiple().

If you have any more questions, do add some specifics of what you're
trying to achieve.

MB

[1] The peak detector does this, and in a sense is looking into the
    future. But it has to look back inside the input buffer, and thus is
    causing latency, even if it doesn't look like it if your time
    reference is sample time.


On Tue, Aug 27, 2013 at 12:43:34PM -0500, Miklos Maroti wrote:
> Hi Martin,
> 
> On Tue, Aug 27, 2013 at 3:07 AM, Martin Braun (CEL)
> <address@hidden> wrote:
> > On Tue, Aug 27, 2013 at 02:43:32AM -0500, Miklos Maroti wrote:
> >> Hi Martin,
> >>
> >> I have checked the tutorials, but they do not give precise details.
> >
> > http://gnuradio.org/redmine/projects/gnuradio/wiki/OutOfTreeModules
> > discusses the whole concept several times.
> >
> >> Here is what I have discovered with a general block:
> >>
> >> 1) set_history(1+m) will simply fill your input buffer with m many
> >> zero items at startup, then your input data will follow.
> >
> > You're missing the point. In *every* work call, you will have 'm' extra
> > samples to calculate your output.
> 
> This is not true, unless you rely on the stock gnuradio blocks, like
> sync_interpolator for which forecast actually requests "noutput_items
> / interpolation() + history() - 1" input items. If what you are saying
> were true, i.e. a general block would always give you 'm' extra input
> after the set_history(1+m), then sync_interpolator would only need to
> request "output_items / interpolation()" items.
> 
> >> 2) If you actually want to see more samples in your work method, then
> >> you have to increase the requested number of inputs in your forecast
> >> method by history() - 1.
> >
> > OK, only mess around with forecast() if you know what you're doing.
> > If you need the precise history inside forecast(), chances are the
> > default behaviour will already do what you want.
> 
> I want to mess around with forecast, I want to understand how these
> things interact. Sure, if you stick with stock blocks, then everything
> will work, but the stock stuff is not good for me.
> 
> >> 3) To see actual history, you have to do both 1) and 2) and do NOT
> >> consume in your work method every sample you have requested in
> >> forecast, only the regular amount so you maintain the proper amount of
> >> past samples in your input buffer.
> >
> > In a sync block, the input buffer is always history()-1 larger than the
> > output buffer. Does this help?
> 
> It is, because in forecast it asked for that many input items more.
> 
> >> 4) You can do 2) alone without 1), but then you are going to work with
> >> "future" samples. So you can always request more input but you are not
> >> going to consume it, so you will see the future.
> >
> > If I understand you correctly: No!
> 
> I think you are wrong. You can set_history(1), and request
> noutput_items + 10 in your forecast, then you will always have 10 more
> extra samples in your general work, so you will see the future. Of
> course you should consume noutput_items to maintain it that way.
> 
> >> 5) Many blocks (sync, sync_interpolator, sync_decimator, general) will
> >> actually implement some default behaviour for your forecast method,
> >> and there they take history() into account. However, if you
> >> reimplement forecast() and forget to include your history, then in
> >> your work method you are going to read garbage outside of your input
> >> buffer (which will be hard to debug).
> >
> > You will always read garbage *outside* of your input buffer.
> 
> The question is how large the input buffer is. What I am claiming that
> the size of the input buffer is always as large (or larger) as what
> you have requested in your forecast method. If you ask for 10 input
> samples in your forecast, then you get 10 samples no matter what the
> history is!!!
> 
> >> 6) The amount of input items in your work method is exactly the amount
> >> (or more) you have requested in your forecast, so magically you will
> >> not have more input data because of set_history() is called.
> >
> > Let me put it this way: GNU Radio has many ways to configure the
> > scheduling behaviour. You're not supposed to use *all* of them at once.
> 
> Why? Stock blocks use all of them!
> 
> > Think about what your block is doing. Do you really need to both change
> > forecast() *and* fiddle with history()? Perhaps you do, but it does seem
> > unlikely.
> 
> I know what I am doing, and I need that behavior, which cannot be
> achieves with stock blocks. So the question remains: can you disprove
> the above 6 claims?
> 
> Best,
> Miklos
> 
> >
> > MB
> >
> >>
> >> Are these statements correct? Best,
> >> Miklos
> >>
> >>
> >> On Tue, Aug 27, 2013 at 2:19 AM, Martin Braun (CEL)
> >> <address@hidden> wrote:
> >> > On Tue, Aug 27, 2013 at 12:11:48AM -0500, Miklos Maroti wrote:
> >> >> Hi Guys,
> >> >>
> >> >> I do not understand how set_history and fixed rate blocks are
> >> >> interacting. Supposedly, the scheduler can figure out a static
> >> >> schedule for sync blocks. However, the sync_interpolator is forcasting
> >> >> this
> >> >>
> >> >> int sync_interpolator::fixed_rate_noutput_to_ninput(int noutput_items) {
> >> >>     return noutput_items / interpolation() + history() - 1;
> >> >> }
> >> >>
> >> >> but consumes only noutput_items / interpolation(). This means, that
> >> >> the scheduler is making a schedule based on the wrong info, the block
> >> >> is actually consuming LESS than it has predicted, so how can the
> >> >> scheduler make optimal schedule?
> >> >
> >> > Hi Miklos,
> >> >
> >> > Think of the history as the number of *past* input samples it takes
> >> > to produce one output sample. The classic example is an FIR filter,
> >> > where you need as many samples as you have taps.
> >> > Minimum is of course 1 (which means you need only the current sample).
> >> > This is also the default value.
> >> >
> >> > In a sync_interpolator, noutput_items is always an integer multiple of
> >> > ninput_items. So if you have no history configured, it must consume
> >> > noutput_items / interpolation(). So what you're seeing is correct
> >> > (unless you changed your history).
> >> >
> >> >> On this point, it is not clear how history() is handled. I searched
> >> >> the archives, and the wisdom is, that set_history(2) means, that all
> >> >
> >> > I'm sure the topic of history() is covered in the tutorials. Also, what
> >> > you're saying is correct and fits what I just explained above.
> >> >
> >> > MB
> >> >
> >> >> the ninput_items and noutput_items and their relationship is
> >> >> completely unchanged, but we have an extra sample at the beginning of
> >> >> the input buffer. However, the sync_interpolator does not do this, it
> >> >> actually includes the history amount in the requested input. So does
> >> >> the scheduler takes history amounts into account, and the
> >> >> sync_interpolator has a bug, or every block has to add the history
> >> >> into their forecast?
> >> >>
> >> >> This is really confusing. I hope someone can shed some light on this.
> >> >>
> >> >> Best,
> >> >> Miklos
> >> >>
> >> >> _______________________________________________
> >> >> Discuss-gnuradio mailing list
> >> >> address@hidden
> >> >> https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
> >> >
> >> > --
> >> > Karlsruhe Institute of Technology (KIT)
> >> > Communications Engineering Lab (CEL)
> >> >
> >> > Dipl.-Ing. Martin Braun
> >> > Research Associate
> >> >
> >> > Kaiserstraße 12
> >> > Building 05.01
> >> > 76131 Karlsruhe
> >> >
> >> > Phone: +49 721 608-43790
> >> > Fax: +49 721 608-46071
> >> > www.cel.kit.edu
> >> >
> >> > KIT -- University of the State of Baden-Württemberg and
> >> > National Laboratory of the Helmholtz Association
> >> >
> >> > _______________________________________________
> >> > Discuss-gnuradio mailing list
> >> > address@hidden
> >> > https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
> >> >
> >>
> >> _______________________________________________
> >> Discuss-gnuradio mailing list
> >> address@hidden
> >> https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
> >
> > --
> > Karlsruhe Institute of Technology (KIT)
> > Communications Engineering Lab (CEL)
> >
> > Dipl.-Ing. Martin Braun
> > Research Associate
> >
> > Kaiserstraße 12
> > Building 05.01
> > 76131 Karlsruhe
> >
> > Phone: +49 721 608-43790
> > Fax: +49 721 608-46071
> > www.cel.kit.edu
> >
> > KIT -- University of the State of Baden-Württemberg and
> > National Laboratory of the Helmholtz Association
> >
> > _______________________________________________
> > Discuss-gnuradio mailing list
> > address@hidden
> > https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
> >
> 
> _______________________________________________
> Discuss-gnuradio mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

-- 
Karlsruhe Institute of Technology (KIT)
Communications Engineering Lab (CEL)

Dipl.-Ing. Martin Braun
Research Associate

Kaiserstraße 12
Building 05.01
76131 Karlsruhe

Phone: +49 721 608-43790
Fax: +49 721 608-46071
www.cel.kit.edu

KIT -- University of the State of Baden-Württemberg and
National Laboratory of the Helmholtz Association

pgpVi_nfWc2ZA.pgp
Description: PGP signature