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
irrational factor decimation
Started by ●November 10, 2006
Reply by ●November 10, 20062006-11-10
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.
Reply by ●November 10, 20062006-11-10
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
Reply by ●November 10, 20062006-11-10
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 news:1163183569.925941.151430@f16g2000cwb.googlegroups.com...> 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 >
Reply by ●November 10, 20062006-11-10
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 > news:1163183569.925941.151430@f16g2000cwb.googlegroups.com... > > 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 > >
Reply by ●November 10, 20062006-11-10
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. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by ●November 10, 20062006-11-10
"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 > news:1163183569.925941.151430@f16g2000cwb.googlegroups.com... >> 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
Reply by ●November 12, 20062006-11-12
"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. > > Vladimir Vassilevsky >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
Reply by ●November 13, 20062006-11-13
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.
Reply by ●November 14, 20062006-11-14
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. >> >> Vladimir Vassilevsky >> > > 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. �����������������������������������������������������������������������
