Non-integer time shift for non-periodic data

A data analysis package I use (built on top of matlab) has a function for 
doing fractional time shifts of time series with constant sampling rates. 
It uses the fft and multiplication on the frequency side.

The only thing I'm wondering is what to do about the fact that the data are 
not periodic.  What the authors of the matlab function did is work with 
sequences of length equal to the power of two strictly greater than the 
length of the data.  And their padding scheme for the added timepoints was 
just to linearly interpolate from the last datum "forward" to the first 
datum, to make the data appear periodic.

While naively that seems pretty reasonable, is it?

TIA,

S

sinister skrev:
> A data analysis package I use (built on top of matlab) has a function for
> doing fractional time shifts of time series with constant sampling rates.
> It uses the fft and multiplication on the frequency side.
>
> The only thing I'm wondering is what to do about the fact that the data are
> not periodic.

No need to worry about the data not being periodic. The DFT doesn't see
the difference, what it is concerned the finite data sequence you
happen
to feed it corresponds to exactly one period of an infinitely long
periodic
sequence. That you in reality feeds it a finite sequence taken from
an infinitely long non-periodic sequence is irrelevant.

A different issue is stationary vs non-stationary data.

> What the authors of the matlab function did is work with
> sequences of length equal to the power of two strictly greater than the
> length of the data.  And their padding scheme for the added timepoints was
> just to linearly interpolate from the last datum "forward" to the first
> datum, to make the data appear periodic.
>
> While naively that seems pretty reasonable, is it?

I have no idea what this is. I don't see any reason why one would want
to 
"make the data appear periodic"?

Rune

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message 
news:1169128394.216000.8340@11g2000cwr.googlegroups.com...
>
> sinister skrev:
>> A data analysis package I use (built on top of matlab) has a function for
>> doing fractional time shifts of time series with constant sampling rates.
>> It uses the fft and multiplication on the frequency side.
>>
>> The only thing I'm wondering is what to do about the fact that the data 
>> are
>> not periodic.
>
> No need to worry about the data not being periodic. The DFT doesn't see
> the difference, what it is concerned the finite data sequence you
> happen
> to feed it corresponds to exactly one period of an infinitely long
> periodic
> sequence. That you in reality feeds it a finite sequence taken from
> an infinitely long non-periodic sequence is irrelevant.
>
> A different issue is stationary vs non-stationary data.
>
>> What the authors of the matlab function did is work with
>> sequences of length equal to the power of two strictly greater than the
>> length of the data.  And their padding scheme for the added timepoints 
>> was
>> just to linearly interpolate from the last datum "forward" to the first
>> datum, to make the data appear periodic.
>>
>> While naively that seems pretty reasonable, is it?
>
> I have no idea what this is. I don't see any reason why one would want
> to
> "make the data appear periodic"?

Thanks for replying to both of my posts.  (I did some USENET searching 
before posting, and you came up many times.)

So you're saying that one should just pad with zeros?

>
> Rune
> 

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message 
news:1169128394.216000.8340@11g2000cwr.googlegroups.com...
>
> sinister skrev:
>> A data analysis package I use (built on top of matlab) has a function for
>> doing fractional time shifts of time series with constant sampling rates.
>> It uses the fft and multiplication on the frequency side.
>>
>> The only thing I'm wondering is what to do about the fact that the data 
>> are
>> not periodic.
>
> No need to worry about the data not being periodic. The DFT doesn't see
> the difference, what it is concerned the finite data sequence you
> happen
> to feed it corresponds to exactly one period of an infinitely long
> periodic
> sequence. That you in reality feeds it a finite sequence taken from
> an infinitely long non-periodic sequence is irrelevant.
>
> A different issue is stationary vs non-stationary data.

These data definitely have slow drifts, which I assume would make them 
nonstationary.

>> What the authors of the matlab function did is work with
>> sequences of length equal to the power of two strictly greater than the
>> length of the data.  And their padding scheme for the added timepoints 
>> was
>> just to linearly interpolate from the last datum "forward" to the first
>> datum, to make the data appear periodic.
>>
>> While naively that seems pretty reasonable, is it?
>
> I have no idea what this is. I don't see any reason why one would want
> to
> "make the data appear periodic"?
>
> Rune
> 

sinister skrev:
> "Rune Allnor" <allnor@tele.ntnu.no> wrote in message
> news:1169128394.216000.8340@11g2000cwr.googlegroups.com...
> >
> > sinister skrev:
> >> A data analysis package I use (built on top of matlab) has a function for
> >> doing fractional time shifts of time series with constant sampling rates.
> >> It uses the fft and multiplication on the frequency side.
> >>
> >> The only thing I'm wondering is what to do about the fact that the data
> >> are
> >> not periodic.

> So you're saying that one should just pad with zeros?

Yes. If N is the length of your FIR filter, pad with N-1 zeros.

Rune

Rune Allnor wrote:
> sinister skrev:
> > "Rune Allnor" <allnor@tele.ntnu.no> wrote in message
> > news:1169128394.216000.8340@11g2000cwr.googlegroups.com...
> > >
> > > sinister skrev:
> > >> A data analysis package I use (built on top of matlab) has a function for
> > >> doing fractional time shifts of time series with constant sampling rates.
> > >> It uses the fft and multiplication on the frequency side.
> > >>
> > >> The only thing I'm wondering is what to do about the fact that the data
> > >> are
> > >> not periodic.
>
> > So you're saying that one should just pad with zeros?
>
> Yes. If N is the length of your FIR filter, pad with N-1 zeros.

Why would this be better than padding with an interpolated
polynomial (continuous with the data, or perhaps sevaral
derivatives)?  Would that not reduce potential high freqeuncy
artifacts at the ends of the times series?


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

Ron N. wrote:
> > Yes. If N is the length of your FIR filter, pad with N-1 zeros.
>
> Why would this be better than padding with an interpolated
> polynomial (continuous with the data, or perhaps sevaral
> derivatives)?  Would that not reduce potential high freqeuncy
> artifacts at the ends of the times series?

If you pad with made-up data, your resulting frequency domain will also
be full of made-up data.

The zero padding just gives extra space so that the result does not
suffer from circular convolution. Imagine the process as convolution
and you will understand why the presence of the zeros doesn't lead to
any problem.

Scott

sinister wrote:
> A data analysis package I use (built on top of matlab) has a function for
> doing fractional time shifts of time series with constant sampling rates.

are you applying this non-integer time shift to a single buffer of a
signal or to adjacent (perhaps overlapping) segments of a signal.  in
general, the means to do this is very similar to the polyphase
filtering that does sample rate conversion, but you just pick a single
phase (fractional delay) of the polyphase filter and use that.  in the
audio world, we worry about a different form of error (since it's just
a filter and there is no issue of images aliasing) when the fractional
delay does not move or moves very slowly that the kind of error we
worry about when doing SRC (and the fractional delay is changing kind
of wildly).

so whether it is a constant or slowly changing non-integer shift or
sample rate conversion, what you are essentially doing is bandlimited
interpolation which is evaluating something like:

                 +N/2
    x((m+a)*T) = SUM{ x[m+k] * sinc(a-k) * w((a-k)/(N/2)) }
              k=-N/2+1

where t = (m + a)*T  = the actual time of the interpolated point
      m = floor(t/T)
      a = fract(t/T) = t/T - floor(t/T)    0 <= a < 1
      N = number of FIR taps of a single phase of polyphase filter.
  and w(u) is a window function of non-zero width of N.

the  h(t) = sinc(t)*w(t/(N/2)) actually is an impulse response
approximating that of an ideal brick-wall LPF and can actually be
designed some other way (Parks-McClellan?) than windowing the ideal
sinc() function.

anyway, if you normalize out the sampling period by defining your unit
of time to be T (so that T=1), then the integer part of your normalized
time (i.e. "m") tells you which N samples you need to do your
interpolation and the fractional part, a, tells you how you will
combine those N samples.

> It uses the fft and multiplication on the frequency side.

because of issues of the inherent circularity or periodicity of the
FFT/DFT, i dunno if i could recommend that method.

r b-j

Scott L wrote:
> Ron N. wrote:
> > > Yes. If N is the length of your FIR filter, pad with N-1 zeros.
> >
> > Why would this be better than padding with an interpolated
> > polynomial (continuous with the data, or perhaps sevaral
> > derivatives)?  Would that not reduce potential high freqeuncy
> > artifacts at the ends of the times series?
>
> If you pad with made-up data, your resulting frequency domain will also
> be full of made-up data.

Aren't any added zero's made-up data as well?  Why is that made-up
data better than more continuous made-up data?

> The zero padding just gives extra space so that the result does not
> suffer from circular convolution. Imagine the process as convolution
> and you will understand why the presence of the zeros doesn't lead to
> any problem.

Convolving the impulse response with leading or trailing zeros
may or may not lead to greater or lesser transient problems
depending on the data.


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

Ron N. wrote:
> Scott L wrote:
> > If you pad with made-up data, your resulting frequency domain will also
> > be full of made-up data.
>
> Aren't any added zero's made-up data as well?  Why is that made-up
> data better than more continuous made-up data?

A sequence of zeros contains no energy at any frequency. It's not "made
up data," rather it is a lack of data. It is simply expanding the size
of the time domain, to give room for the tails of the convolution.

> > The zero padding just gives extra space so that the result does not
> > suffer from circular convolution. Imagine the process as convolution
> > and you will understand why the presence of the zeros doesn't lead to
> > any problem.
>
> Convolving the impulse response with leading or trailing zeros
> may or may not lead to greater or lesser transient problems
> depending on the data.

Probably the most ambiguous statement I've seen today :-) Care to
elaborate what it means?

Scott