1
$\begingroup$

Apologies in advance if my question doesn't make sense. I'm not the most fluent person in signal processing.

I have an array of time domain values that I would like to apply a time delay to by computing the fft then apply the Fourier transform $f(t - \tau) = F(\omega)\exp(-i \omega\tau)$ and then compute the inverse fft to get my delayed signal.

My problem is that the delay is very large (three times further than the range of my original signal) so in order to get the delayed signal I have been zero padding my original signal by a significant amount which greatly increase the computation time.

Is there a better way to compute the delay using Fourier transform without the need to zero pad?

Improve this question
$\endgroup$
4
  • $\begingroup$ If you only need a constant delay, this corresponds to a linear phase shift. So you can directly change the shift in the frequency domain. As for the shift in real domain, you wrote it yourself: $t-\tau$... But I may have missed something because I don't get why you would need to perform an FFT to delay your signal: that's much faster in the time domain if you only apply one time delay. $\endgroup$
    – user13706
    Jul 15, 2015 at 18:57
  • $\begingroup$ The problem for me is that the time series are discrete and uniform in time (e.g. a bit per second) and the delay is not necessary in intervals of seconds. If the delay is 2 seconds for example I could just shift the array of values two elements but I don't quite know how to do that with a delay of 1.5 without resorting to using time shift in frequency domain. $\endgroup$
    – kkawabat
    Jul 15, 2015 at 20:37
  • $\begingroup$ Ah, I see... Then the Fourier transform would most likely not solve anything! If your signal is smooth enough, just interpolate data-points and change the $x$ values to get the correct shift. If your data is not smooth using the FFT is just wrong (I can explain more in a complete answer if you wish). In the end, for a limited number of delay calculation per sample, do it in time domain. $\endgroup$
    – user13706
    Jul 15, 2015 at 21:39
  • $\begingroup$ That said, if and only if your signal is smooth enough, you can perform the said shifting in frequency domain. In that case, do not pad: the signal in the time domain will "roll" as much as needed and the new points would correspond to the correct interpolated points. Then, all you have to do is to roll-back you signal array and to update $x$ accordingly. Said this way, real space interpolation seems soooo much simpler. $\endgroup$
    – user13706
    Jul 15, 2015 at 21:50

2 Answers 2

Reset to default
3
$\begingroup$

You must zero-pad, whether implementing the delay in the time domain or the frequency domain. (Consider this: by delaying, you are making the signal longer.)

Implementing the delay with the FFT implements a circular shift. If you don't pad and you use the FFT, the data will simply wrap around on itself. (Imagine that if you didn't zero pad and used the FFT with $\tau = NT$, the duration of the record length. Then you would simply get back what you started with, with no delay, because of circular wrapping.) If you want only an integer number of sample delays, do it in the time domain.

If you want a fractional sample delay, you can use the FFT as you describe. It makes no difference mathematically if you implement say a 20.7 sample delay first in time by 20 samples and then in frequency by 0.7 samples, or whether you do it all in frequency by 20.7 samples. Remember—you padded first. Computationally, as you say, this can increase computation time. But you are only increasing the length by a factor of four so computation time with an FFT should increase by a factor of only two. Is this too much? Alternatively, you can do the "bulk" delay in time and the fractional delay in frequency. In the frequency part, you have a couple of choices. First, before doing the bulk time delay, you can do the fractional delay on the original unpadded data and accept the fractional-sample delay wrap-around error at the beginning of the sequence. Second, you can pad your data by only one sample and do the fractional shift with an FFT. If your FFT software accepts only powers-of-two record lengths and your original record length is a power of two, this will likely slow your computation by more than a factor of two because a fast algorithm is not employed. However, most modern FFT packages provide fast algorithms for sequence lengths that can be factored into products of small prime numbers, so adding one data point might not significantly increase computation time.

Some have suggested alternatively using an interpolater for a fractional shift. The FFT is the ideal interpolater—it exactly interpolates bandlimited data when zero padding without adding a delay exponential or when your delay exponential is added. However, cubic splines are outstanding interpolators and should be in your toolbox.

Improve this answer
$\endgroup$
1
$\begingroup$

Delay in the frequency domain, as you are attempting, can only be circular, so you must zero pad unless you want your signal to wrap around in time.

I'm guessing there is a good reason why you cannot just prepend the appropriate number of zeros in the time domain?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your reply. The signals is about 5 seconds long while the delay is 20 seconds. And I'm repeating the operation for about 10000 signals so it increase the computation by a large amount. Would it be possible for me to manipulate the wrapped signal after the delay? $\endgroup$
    – kkawabat
    Jul 15, 2015 at 17:53
  • $\begingroup$ I don't really understand your requirements. I'm assuming this is offline processing: if you are going to delay a K sample signal by M samples, you will inevitably end up with a K+M sample result. The quickest way to achieve this is simply inserting the K sample signal at the end of the K+M sample all-zeros array. If you require fractional sample delay of, say, 20.5 samples, I would perform the fractional delay of 0.5 samples using the FFT method, then add the large integer delay by pre-padding zeros. You could also perform the fractional sample delay in the time domain by interpolation. $\endgroup$
    – kippertoffee
    Jul 17, 2015 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.