Here's my problem. I have a series of data points x1, x2... xn taken at time values t_1, t-2... t_n. Now t_1 through t_n-1 are all equally spaced (i.e. t_m = m * dt where dt is sampling period). The very last data point t_n is not at that spacing. It's close but not exact (in general t_n will fall short of the next equally space point, so t_n < n*dt) I need to perform an operation on the data, and I have an FIR filter representation of the operation I want to perform - but the FIR filter wants equally spaced time points. How would you solve this? What I'm thinking is that I would apply a spline (cubic) to extrapolate to the next equally spaced point, apply the filter, and then interpolate back to the data value at t_n. Anyone have anything better? /* Daniel */ in case you're wondering why I have this, I'm solving a differential equation numerically and the solver uses backwards differentiation with a variable time step. I need to apply an operation to calculate the residual function. It doesn't actually have to be a filter, but the operation is defined by an arbitrary frequency response, and an FIR filter is the easiest way I've come up with to represent that.
filtering a signal with variable time step
Started by ●April 1, 2009
Reply by ●April 1, 20092009-04-01
On Apr 1, 9:53�am, daniel.kirac...@gmail.com wrote:> � Here's my problem. �I have a series of data points x1, x2... xn > taken at time values t_1, t-2... t_n. �Now t_1 through t_n-1 are all > equally spaced (i.e. t_m = m * dt where dt is sampling period). �The > very last data point t_n is not at that spacing. �It's close but not > exact (in general t_n will fall short of the next equally space point, > so t_n < n*dt) �I need to perform an operation on the data, and I have > an FIR filter representation of the operation I want to perform - but > the FIR filter wants equally spaced time points. �How would you solve > this? �What I'm thinking is that I would apply a spline (cubic) to > extrapolate to the next equally spaced point, apply the filter, and > then interpolate back to the data value at t_n. �Anyone have anything > better? > > /* Daniel */ > > in case you're wondering why I have this, I'm solving a differential > equation numerically and the solver uses backwards differentiation > with a variable time step. �I need to apply an operation to calculate > the residual function. �It doesn't actually have to be a filter, but > the operation is defined by an arbitrary frequency response, and an > FIR filter is the easiest way I've come up with to represent that.If you think of the FIR filter coefficients as evenly spaced points of its impulse response, just resample (ie interpolate) the impulse response for the last tap at its new position. If you know the impulse response analytically this is trivial. This basically becomes polyphase interpolation (with the interpolation ratio of 1:1), and you will therefore have a slightly different set of coefficients for each result point you need (a set of n phases) reflecting the fact that as you sweep over n point the "shifted" sample lines up with points from the far left through the far right coefficient. If you don't have analytical coeffs, you ought to be able to interpolate using a series of overlapping sinc pulses, mimicing the ideal LPF reconstruction of the response. Just my 2 cents. - Kenn
Reply by ●April 1, 20092009-04-01
daniel.kiracofe@gmail.com wrote:> > Here's my problem. I have a series of data points x1, x2... xn > taken at time values t_1, t-2... t_n. Now t_1 through t_n-1 are all > equally spaced (i.e. t_m = m * dt where dt is sampling period). The > very last data point t_n is not at that spacing. It's close but not > exact (in general t_n will fall short of the next equally space point, > so t_n < n*dt) I need to perform an operation on the data, and I have > an FIR filter representation of the operation I want to perform - but > the FIR filter wants equally spaced time points. How would you solve > this?Are you talking about a block of 1 to n data points that gets run thru a filter to produce an output block of 1 to n points. Or is n just the index in a long stream of points (extending well past n) where you have one sample that is shifted a bit in time? If it is the second one then interpolating to correct for the shift in that one point would probably be the most sensible thing. If it is the former then it is kind of murky what you would do even if the point n was equally spaced like the rest. -jim>What I'm thinking is that I would apply a spline (cubic) to > extrapolate to the next equally spaced point, apply the filter, and > then interpolate back to the data value at t_n. Anyone have anything > better? > > /* Daniel */ > > in case you're wondering why I have this, I'm solving a differential > equation numerically and the solver uses backwards differentiation > with a variable time step. I need to apply an operation to calculate > the residual function. It doesn't actually have to be a filter, but > the operation is defined by an arbitrary frequency response, and an > FIR filter is the easiest way I've come up with to represent that.
Reply by ●April 1, 20092009-04-01
On Apr 1, 9:07�am, kennheinr...@sympatico.ca wrote:> If you think of the FIR filter coefficients as evenly spaced points of > its impulse response, just resample (ie interpolate) the impulse > response for the last tap at its new position. �If you know the > impulse response analytically this is trivial. This basically becomes > polyphase interpolation (with the interpolation ratio of 1:1), and you > will therefore have a slightly different set of coefficients for each > result point you need (a set of n phases) reflecting the fact that as > you sweep over n point the "shifted" sample lines up with points from > the far left through the far right coefficient. �If you don't have > analytical coeffs, you ought to be able to interpolate using a series > of overlapping sinc pulses, mimicing the ideal LPF reconstruction of > the response. > > Just my 2 cents. > > �- KennOk. I was wondering if this was possible. Sounds like it might work. I don't have the impulse response analytically so I'd have interpolate. thanks for the suggestion /* Daniel */
Reply by ●April 1, 20092009-04-01
On Apr 1, 9:45�am, jim <".sjedgingN0sp"@m...@mwt.net> wrote:> Are you talking about a block of 1 to n data points that gets run thru a filter > to produce an output block of 1 to n �points. Or is n just the index in a long > stream of points (extending well past n) where you have one sample that is > shifted a bit in time? > > � � � � If it is the second one then interpolating to correct for the shift in that one > point would probably be the most sensible thing. > > � � � � �If it is the former then it is kind of murky what you would do even if the > point n was equally spaced like the rest.I've got 1 through n input points, and I need to filter to produce 1 through n output points (I only really care about the last output point though). 1 through n-1 are equally spaced, but the last point is not necessarily at the same spacing.
Reply by ●April 1, 20092009-04-01
daniel.kiracofe@gmail.com wrote:> > On Apr 1, 9:45 am, jim <".sjedgingN0sp"@m...@mwt.net> wrote: > > Are you talking about a block of 1 to n data points that gets run thru a filter > > to produce an output block of 1 to n points. Or is n just the index in a long > > stream of points (extending well past n) where you have one sample that is > > shifted a bit in time? > > > > If it is the second one then interpolating to correct for the shift in that one > > point would probably be the most sensible thing. > > > > If it is the former then it is kind of murky what you would do even if the > > point n was equally spaced like the rest. > > I've got 1 through n input points, and I need to filter to produce 1 > through n output points (I only really care about the last output > point though). 1 through n-1 are equally spaced, but the last point > is not necessarily at the same spacing.So you have something like a series of daily stock market closing prices for a particular stock and you would like to predict what the closing price for that stock will be today based on the price that it is selling for a couple hours before closing. Is that sort of the nature of the problem? That may not be what you are doing and your problem may be easy to solve if you can make some valid assumptions. For instance If the data represents an inherently periodic function and you know the period you shouldn't have much trouble. -jim
Reply by ●April 2, 20092009-04-02
On Apr 1, 12:31�pm, jim <".sjedgingN0sp"@m...@mwt.net> wrote:> daniel.kirac...@gmail.com wrote: > > > On Apr 1, 9:45 am, jim <".sjedgingN0sp"@m...@mwt.net> wrote: > > > Are you talking about a block of 1 to n data points that gets run thru a filter > > > to produce an output block of 1 to n �points. Or is n just the index in a long > > > stream of points (extending well past n) where you have one sample that is > > > shifted a bit in time? > > > > � � � � If it is the second one then interpolating to correct for the shift in that one > > > point would probably be the most sensible thing. > > > > � � � � �If it is the former then it is kind of murky what you would do even if the > > > point n was equally spaced like the rest. > > > I've got 1 through n input points, and I need to filter to produce 1 > > through n output points (I only really care about the last output > > point though). �1 through n-1 are equally spaced, but the last point > > is not necessarily at the same spacing. > > So you have something like a series of daily stock market closing prices for a > particular stock and you would like to predict what the closing price for that > stock will be today based on the price that it is selling for a couple hours > before closing. Is that sort of the nature of the problem? > > � � � � That may not be what you are doing and your problem may be easy to solve if you > can make some valid assumptions. For instance If the data represents an > inherently periodic function and you know the period ...or, maybe, if the power spectrum (or, equivalently, the auto- correlation) of the data is known. using Linear Predictive Coding, you could, in an oversampled context, predict what the next equally spaced sample "should" be and adjust it based on what that oddly spaced sample is. r b-j
Reply by ●April 2, 20092009-04-02
Daniel wrote:> � Here's my problem. �I have a series of data points x1, x2... xn > taken at time values t_1, t-2... t_n. �Now t_1 through t_n-1 are all > equally spaced (i.e. t_m = m * dt where dt is sampling period). �The > very last data point t_n is not at that spacing. �It's close but not > exact (in general t_n will fall short of the next equally space point, > so t_n < n*dt) �I need to perform an operation on the data, and I have > an FIR filter representation of the operation I want to perform - but > the FIR filter wants equally spaced time points. �How would you solve > this? �What I'm thinking is that I would apply a spline (cubic) to > extrapolate to the next equally spaced point, apply the filter, and > then interpolate back to the data value at t_n. �Anyone have anything > better?Let's assume that you can write your data using the sinc-interpolation formula, ie. x(t) = sum_{k=0}^{n-1} x_k sinc(t-k) (with dt=1). Since you don't know x_{n-1} but you do know x(t_n), you can simply replace t with t_n, and write the unknown on the left, ie x_{n-1} = 1/sinc(t_n-(n-1)) (x(t_n) - sum_{k=0}^{n-2} x_k sinc(t_n- k)). Now you have uniformly resampled your vector and can apply the FIR filter. However, even under the assumption that the sampled function is bandlimited (a strong assumption for the solution of an arbitrary differential equation), the choice of the sinc-interpolation kernel is somewhat arbitrary. You could also use the periodic interpolation kernel (Dirichlet), or the even or the odd periodic interpolation kernels (nameless), or, as you suggest, the B-spline interpolation kernels for polynomial resampling. Another method to retrieve x_{n-1} would be to assume that the samples are not completely uncorrelated and try to take advantage of that, for example using linear prediction as r b j suggests. Regards, Andor
Reply by ●April 2, 20092009-04-02
Andor wrote:> Daniel wrote: > >> Here's my problem. I have a series of data points x1, x2... xn >>taken at time values t_1, t-2... t_n. Now t_1 through t_n-1 are all >>equally spaced (i.e. t_m = m * dt where dt is sampling period). The >>very last data point t_n is not at that spacing. It's close but not >>exact (in general t_n will fall short of the next equally space point, >>so t_n < n*dt) I need to perform an operation on the data, and I have >>an FIR filter representation of the operation I want to perform - but >>the FIR filter wants equally spaced time points. How would you solve >>this?> Let's assume that you can write your data using the sinc-interpolation > formula, ie.[...] One way is the interpolation of the data. The other way is representing the filter as the continuos time structure and solving it numerically as a part of the original differential equation. FIR is just the combination of exp(-st) and tap weights, so here we go. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by ●April 3, 20092009-04-03
On 3 Apr., 00:14, Vladimir Vassilevsky <antispam_bo...@hotmail.com> wrote:> Andor wrote: > > Daniel wrote: > > >> �Here's my problem. �I have a series of data points x1, x2... xn > >>taken at time values t_1, t-2... t_n. �Now t_1 through t_n-1 are all > >>equally spaced (i.e. t_m = m * dt where dt is sampling period). �The > >>very last data point t_n is not at that spacing. �It's close but not > >>exact (in general t_n will fall short of the next equally space point, > >>so t_n < n*dt) �I need to perform an operation on the data, and I have > >>an FIR filter representation of the operation I want to perform - but > >>the FIR filter wants equally spaced time points. �How would you solve > >>this? > > Let's assume that you can write your data using the sinc-interpolation > > formula, ie. > > [...] > > One way is the interpolation of the data. The other way is representing > the filter as the continuos time structure and solving it numerically as > a part of the original differential equation. FIR is just the > combination of exp(-st) and tap weights, so here we go.Good idea - just include the filtering in the numerical solving of the differential equation. This saves one from having to make assumptions for interpolation. Regards, Andor
