# irrational factor decimation

Started by November 10, 2006
```Thanks for the guys who aswered my decimation question, howver I am really
looking for irrational decimation, so I am clearing up the confusion:

I am trying to decimate bandlimited data by an irrational factor like
Tin/Tout = 2*sqrt(2) where Tout and Tin are the output and input sampling
time. I am using a simple linear interpolator where coefficient
changes at the output rate: y(m) = x(n) + (x(n+1)-x(n))*alpha where alpha(m)
= alpha(m-1) + 0.1. (modulo 1)
This interpolator needs 2 consecutive input data in order to compute an
output.  At each Tout increment the interpolator compute an output from the
latest available 2 inputs, however when alpha overflow (> 1) then the latest
input should be skipped and use the next 2  that follow (is that true ?).

The next question how can this be implemented ? should I use a circular
buffer with a pointer pointing to the latest data input. It seems to me that
if I keep skipping input data every time alpha overflows I will be
incrementing my pointer faster that the input data rate !! Any suggestion
how this scheme can be implemented ?
Thanks,
Tom

```
```Tom wrote:

> Thanks for the guys who aswered my decimation question, howver I am really
> looking for irrational decimation, so I am clearing up the confusion:
>
> I am trying to decimate bandlimited data by an irrational factor like
> Tin/Tout = 2*sqrt(2) where Tout and Tin are the output and input sampling
> time. I am using a simple linear interpolator where coefficient
> changes at the output rate: y(m) = x(n) + (x(n+1)-x(n))*alpha where alpha(m)
> = alpha(m-1) + 0.1. (modulo 1)
> This interpolator needs 2 consecutive input data in order to compute an
> output.  At each Tout increment the interpolator compute an output from the
> latest available 2 inputs, however when alpha overflow (> 1) then the latest
> input should be skipped and use the next 2  that follow (is that true ?).
>
> The next question how can this be implemented ? should I use a circular
> buffer with a pointer pointing to the latest data input. It seems to me that
> if I keep skipping input data every time alpha overflows I will be
> incrementing my pointer faster that the input data rate !! Any suggestion
> how this scheme can be implemented ?
>  Thanks,
>  Tom
>
>

Close.  When alpha overflows it means you need to use the next sample
pair like you said.  While your computation of the interpolated samples
might progress very quickly so you could concievably get ahead of the
input, you only need to produce those samples at the rate determined by
alpha and your input sample rate.  That means if alpha overflows, you
have to stop and wait until the next input sample is available.
Assuming your processing can keep up with the input sample rate (if it
can't you are already in trouble), you only need a buffer deep enough to
hold the most recent two samples. Your interpolation routine should be
waiting for the next input sample by the time it arrives.  This is
assuming that you are interpolating, in which case there will always be
at least one point computed between input samples.  If not, then you
need to keep track of the integer portion of alpha as well so that you
can actually skip the correct number of input samples.  For
interpolation, you are not skipping input samples but the number of
interpolated samples between successive inputs will vary depending on
the phase of alpha.

SO the interpolation routine should, upon recieving a new input sample,
decrement alpha by 1, and if the residue is less than 1, compute an
interpolated value based on alpha, add the increment value to alpha, and
if alpha is still less than 1 repeat until alpha becomes larger than 1,
indicating it needs the next sample, then wait until the next sample
comes in.
```
```Tom wrote:
> Thanks for the guys who aswered my decimation question, howver I am really
> looking for irrational decimation, so I am clearing up the confusion:
>
> I am trying to decimate bandlimited data by an irrational factor like
> Tin/Tout = 2*sqrt(2) where Tout and Tin are the output and input sampling
> time. I am using a simple linear interpolator where coefficient
> changes at the output rate: y(m) = x(n) + (x(n+1)-x(n))*alpha where alpha(m)
> = alpha(m-1) + 0.1. (modulo 1)
> This interpolator needs 2 consecutive input data in order to compute an
> output.  At each Tout increment the interpolator compute an output from the
> latest available 2 inputs, however when alpha overflow (> 1) then the latest
> input should be skipped and use the next 2  that follow (is that true ?).
>
> The next question how can this be implemented ? should I use a circular
> buffer with a pointer pointing to the latest data input. It seems to me that
> if I keep skipping input data every time alpha overflows I will be
> incrementing my pointer faster that the input data rate !! Any suggestion
> how this scheme can be implemented ?

Any time you resample by a non-integer ratio, your algorithm will
need to be able to step at two different integer rates.  For instance
if your resample ratio in r, then the input stream could need to
advance by int(r) or int(r)+1 samples in order to produce an output
filtered by the same interpolation kernel.  So, after you fill the
pipeline, you need to be able to increment you integer input pointer
by two different values, but this value should always be less
than or equal to input data rate r, so you should never underflow.

IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

```
```I agree with what you said. Can I implement this using a circular buffer or
a FIFO. It seems to me underflow will happen no matter how the pipeline is
big since I am incrementing the input data pointer faster than the data
itself.

"Ron N." <rhnlogic@yahoo.com> wrote in message
> Tom wrote:
>> Thanks for the guys who aswered my decimation question, howver I am
>> really
>> looking for irrational decimation, so I am clearing up the confusion:
>>
>> I am trying to decimate bandlimited data by an irrational factor like
>> Tin/Tout = 2*sqrt(2) where Tout and Tin are the output and input sampling
>> time. I am using a simple linear interpolator where coefficient
>> changes at the output rate: y(m) = x(n) + (x(n+1)-x(n))*alpha where
>> alpha(m)
>> = alpha(m-1) + 0.1. (modulo 1)
>> This interpolator needs 2 consecutive input data in order to compute an
>> output.  At each Tout increment the interpolator compute an output from
>> the
>> latest available 2 inputs, however when alpha overflow (> 1) then the
>> latest
>> input should be skipped and use the next 2  that follow (is that true ?).
>>
>> The next question how can this be implemented ? should I use a circular
>> buffer with a pointer pointing to the latest data input. It seems to me
>> that
>> if I keep skipping input data every time alpha overflows I will be
>> incrementing my pointer faster that the input data rate !! Any suggestion
>> how this scheme can be implemented ?
>
> Any time you resample by a non-integer ratio, your algorithm will
> need to be able to step at two different integer rates.  For instance
> if your resample ratio in r, then the input stream could need to
> advance by int(r) or int(r)+1 samples in order to produce an output
> filtered by the same interpolation kernel.  So, after you fill the
> pipeline, you need to be able to increment you integer input pointer
> by two different values, but this value should always be less
> than or equal to input data rate r, so you should never underflow.
>
>
> IMHO. YMMV.
> --
> rhn A.T nicholson d.0.t C-o-M
>

```
```Tom wrote:
> I agree with what you said. Can I implement this using a circular buffer or
> a FIFO. It seems to me underflow will happen no matter how the pipeline is
> big since I am incrementing the input data pointer faster than the data
> itself.

No matter how you implement a resampler, you can't interpolate
data that hasn't been input to the system yet.

> "Ron N." <rhnlogic@yahoo.com> wrote in message
> > Tom wrote:
> >> Thanks for the guys who aswered my decimation question, howver I am
> >> really
> >> looking for irrational decimation, so I am clearing up the confusion:
> >>
> >> I am trying to decimate bandlimited data by an irrational factor like
> >> Tin/Tout = 2*sqrt(2) where Tout and Tin are the output and input sampling
> >> time. I am using a simple linear interpolator where coefficient
> >> changes at the output rate: y(m) = x(n) + (x(n+1)-x(n))*alpha where
> >> alpha(m)
> >> = alpha(m-1) + 0.1. (modulo 1)
> >> This interpolator needs 2 consecutive input data in order to compute an
> >> output.  At each Tout increment the interpolator compute an output from
> >> the
> >> latest available 2 inputs, however when alpha overflow (> 1) then the
> >> latest
> >> input should be skipped and use the next 2  that follow (is that true ?).
> >>
> >> The next question how can this be implemented ? should I use a circular
> >> buffer with a pointer pointing to the latest data input. It seems to me
> >> that
> >> if I keep skipping input data every time alpha overflows I will be
> >> incrementing my pointer faster that the input data rate !! Any suggestion
> >> how this scheme can be implemented ?
> >
> > Any time you resample by a non-integer ratio, your algorithm will
> > need to be able to step at two different integer rates.  For instance
> > if your resample ratio in r, then the input stream could need to
> > advance by int(r) or int(r)+1 samples in order to produce an output
> > filtered by the same interpolation kernel.  So, after you fill the
> > pipeline, you need to be able to increment you integer input pointer
> > by two different values, but this value should always be less
> > than or equal to input data rate r, so you should never underflow.
> >
> >
> > IMHO. YMMV.
> > --
> > rhn A.T nicholson d.0.t C-o-M
> >

```
```
Tom wrote:

> Thanks for the guys who aswered my decimation question, howver I am really
> looking for irrational decimation, so I am clearing up the confusion:
>
> I am trying to decimate bandlimited data by an irrational factor like
> Tin/Tout = 2*sqrt(2) where Tout and Tin are the output and input sampling
> time. I am using a simple linear interpolator where coefficient
> changes at the output rate: y(m) = x(n) + (x(n+1)-x(n))*alpha where alpha(m)
> = alpha(m-1) + 0.1. (modulo 1)
> This interpolator needs 2 consecutive input data in order to compute an
> output.  At each Tout increment the interpolator compute an output from the
> latest available 2 inputs, however when alpha overflow (> 1) then the latest
> input should be skipped and use the next 2  that follow (is that true ?).

Yes, this is correct. Dedending if the input or the output sample rate
is higher, you will have to slide one sample forward or one sample back
once in a while.

>
> The next question how can this be implemented ?

You should run your calculation at every sample at the input. Depending
on the current alpha and the resampling ratio, this will produce from
zero to two samples at the output.

should I use a circular
> buffer with a pointer pointing to the latest data input.

It is no point to use the circular buffers for just two samples.

It seems to me that
> if I keep skipping input data every time alpha overflows I will be
> incrementing my pointer faster that the input data rate !! Any suggestion
> how this scheme can be implemented ?

This interpolator works very well. You may consider using 3-rd order
interpolation. The basic algorithm is identical, however the accuracy is
lot better.

DSP and Mixed Signal Design Consultant

http://www.abvolt.com

```
```"Tom" <tomdarel@yahoo.com> wrote in message
news:4554ceb5\$0\$25451\$c3e8da3@news.astraweb.com...
>I agree with what you said. Can I implement this using a circular buffer or
>a FIFO. It seems to me underflow will happen no matter how the pipeline is
>big since I am incrementing the input data pointer faster than the data
>itself.
>
>
> "Ron N." <rhnlogic@yahoo.com> wrote in message
>> Tom wrote:
>>> Thanks for the guys who aswered my decimation question, howver I am
>>> really
>>> looking for irrational decimation, so I am clearing up the confusion:
>>>
>>> I am trying to decimate bandlimited data by an irrational factor like
>>> Tin/Tout = 2*sqrt(2) where Tout and Tin are the output and input
>>> sampling
>>> time. I am using a simple linear interpolator where coefficient
>>> changes at the output rate: y(m) = x(n) + (x(n+1)-x(n))*alpha where
>>> alpha(m)
>>> = alpha(m-1) + 0.1. (modulo 1)
>>> This interpolator needs 2 consecutive input data in order to compute an
>>> output.  At each Tout increment the interpolator compute an output from
>>> the
>>> latest available 2 inputs, however when alpha overflow (> 1) then the
>>> latest
>>> input should be skipped and use the next 2  that follow (is that true
>>> ?).
>>>
>>> The next question how can this be implemented ? should I use a circular
>>> buffer with a pointer pointing to the latest data input. It seems to me
>>> that
>>> if I keep skipping input data every time alpha overflows I will be
>>> incrementing my pointer faster that the input data rate !! Any
>>> suggestion
>>> how this scheme can be implemented ?

Tom,

By all appearances you have an implementation problem, not a problem with
the physics of the situation.

I think you're getting stuck on the code structure.  For example, why should
alpha overflow at all?  Isn't there a way to implement to meet your need
where that doesn't happen?

Hmmmm.. Now you're saying
Tin/Tout = 2*sqrt(2) where Tout and Tin are the output and input sampling
time.
If so then Tin/Tout > 1.0 which implies interpolation and yet you say
"decimation".
Which is it?

Also, the formula for alpha is wrong now because you don't want to increment
it by 0.1 any more.  It seems you would want to increment it by the
fractional part - of the location between input samples and the needed
output sample.

Pretty much the same approach applies as I'd outlined in my earlier post.
The only difference is that there's now a continuously-changing value for
the two coefficients to be used for each output.

Unless you're willing to declare that the two clocks have coincided after so
many cycles (which may be a practical thing to do) or if it's forced by
discrete numbers then the coefficient pairs will never repeat and I see no
reason for any circular buffers.  But, if you do then there may be a
circular buffer of coefficients possible.

At first glance it looks like you will have 3 samples of the input for each
sample of the output repeating 4 times and then 2 samples of the input for
one sample of the output.  What I've not bothered to figure out is whether
the sequence is more complicated than that.  I suspect that it is...

Fred

```
```"Vladimir Vassilevsky" <antispam_bogus@hotmail.com> wrote in message
news:w475h.24386\$TV3.24051@newssvr21.news.prodigy.com...
>
>
> You should run your calculation at every sample at the input. Depending on
> the current alpha and the resampling ratio, this will produce from zero to
> two samples at the output.
>
>

If indeed he is decimating and doing linear interpolation on two samples
then I don't see how one could use every input sample for a decimation
factor of 2*sqrt(2).  Only the 3rd sample and occasionally the 2nd sample
each with its predecessor is needed in any calculation.  I guess that's
equivalent to your "zero" samples at the output.  Perhaps that *is* cleaner
to implement.

The OP didn't say what the implementation was to be.  That may make a big
difference in implementation.  If there are two clocks then all one needs to
do is sample along.... and then at each output clock tick capture the
current two samples to be used for computing an output.

If there aren't two clocks or if the notion of a "clock" isn't part of the
implementation, such as in block processing, then some indexing math is
needed - which suggests something like pointers to me.

Fred

```
```Thanks to all of you guys for your valuable comments, I feel after your
comments that I am on solid ground to continue working on my project.

Tom

"Ray Andraka" <ray@andraka.com> wrote in message
news:G425h.30977\$Wb2.587@newsfe22.lga...
> Tom wrote:
>
>> Thanks for the guys who aswered my decimation question, howver I am
>> really looking for irrational decimation, so I am clearing up the
>> confusion:
>>
>> I am trying to decimate bandlimited data by an irrational factor like
>> Tin/Tout = 2*sqrt(2) where Tout and Tin are the output and input sampling
>> time. I am using a simple linear interpolator where coefficient
>> changes at the output rate: y(m) = x(n) + (x(n+1)-x(n))*alpha where
>> alpha(m)
>> = alpha(m-1) + 0.1. (modulo 1)
>> This interpolator needs 2 consecutive input data in order to compute an
>> output.  At each Tout increment the interpolator compute an output from
>> the
>> latest available 2 inputs, however when alpha overflow (> 1) then the
>> latest
>> input should be skipped and use the next 2  that follow (is that true ?).
>>
>> The next question how can this be implemented ? should I use a circular
>> buffer with a pointer pointing to the latest data input. It seems to me
>> that
>> if I keep skipping input data every time alpha overflows I will be
>> incrementing my pointer faster that the input data rate !! Any suggestion
>> how this scheme can be implemented ?
>>  Thanks,
>>  Tom
>
> Close.  When alpha overflows it means you need to use the next sample pair
> like you said.  While your computation of the interpolated samples might
> progress very quickly so you could concievably get ahead of the input, you
> only need to produce those samples at the rate determined by alpha and
> your input sample rate.  That means if alpha overflows, you have to stop
> and wait until the next input sample is available. Assuming your
> processing can keep up with the input sample rate (if it can't you are
> already in trouble), you only need a buffer deep enough to hold the most
> recent two samples. Your interpolation routine should be waiting for the
> next input sample by the time it arrives.  This is assuming that you are
> interpolating, in which case there will always be at least one point
> computed between input samples.  If not, then you need to keep track of
> the integer portion of alpha as well so that you can actually skip the
> correct number of input samples.  For interpolation, you are not skipping
> input samples but the number of interpolated samples between successive
> inputs will vary depending on the phase of alpha.
>
> SO the interpolation routine should, upon recieving a new input sample,
> decrement alpha by 1, and if the residue is less than 1, compute an
> interpolated value based on alpha, add the increment value to alpha, and
> if alpha is still less than 1 repeat until alpha becomes larger than 1,
> indicating it needs the next sample, then wait until the next sample comes
> in.

```
```Fred Marshall wrote:
> "Vladimir Vassilevsky" <antispam_bogus@hotmail.com> wrote in message
> news:w475h.24386\$TV3.24051@newssvr21.news.prodigy.com...
>>
>> You should run your calculation at every sample at the input. Depending on
>> the current alpha and the resampling ratio, this will produce from zero to
>> two samples at the output.
>>
>>
>
> If indeed he is decimating and doing linear interpolation on two samples
> then I don't see how one could use every input sample for a decimation
> factor of 2*sqrt(2).  Only the 3rd sample and occasionally the 2nd sample
> each with its predecessor is needed in any calculation.  I guess that's
> equivalent to your "zero" samples at the output.  Perhaps that *is* cleaner
> to implement.
>
> The OP didn't say what the implementation was to be.  That may make a big
> difference in implementation.  If there are two clocks then all one needs to
> do is sample along.... and then at each output clock tick capture the
> current two samples to be used for computing an output.
>
> If there aren't two clocks or if the notion of a "clock" isn't part of the
> implementation, such as in block processing, then some indexing math is
> needed - which suggests something like pointers to me.

I find it hard to believe that a practically robust system that can
handle 239/169 would choke on sqrt(2)

Jerry
--
Engineering is the art of making what you want from things you can get.
&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
```