0
$\begingroup$

I want to get the fundamental frequency of a signal. I used a time domain approach first. It just sums up the differences between the signal (lets say 2048 samples) and the delayed version of the same signal. I think it's not quite what autocorrelation does because I don't pad the signal with zeros or do circular convolution. Instead, I just accessed older samples. So when compairing the signals with 1 sample delay, I check samples 1 to 2048, for a 5 sample delay I check samples 5 to 2053 and so on. For the full 2048 sample delay, I check 2048 to 4096. This works our really well because I just need the delay where the difference is the lowest. That might not be the fundamental but haveing a closer match is more important for my actual usecase. (writing an oscilloscope)

I ran into performance issues, so I wanted to use FFT instead of the time domain approach. However, I've noticed that because of the zero padding of the signa, I get some kind of triangle window. I guess what would be the equivalent in the time domain approach is using zeros instead of older samples in the delayed signal. (I've attached a screen from Matlab)

My question is if there is some way to use FFT for processing but to get rid of this "triangle window" effect. Or in other words: Is there a way to implement my time domain approach using FFT?

Cheers

enter image description here

$\endgroup$
1
$\begingroup$

A triangle is the convolution of a rectangle against itself. Zero padding creates a rectangular window of data.

To remove the triangle (or other windowing) artifact, you can compensate the autocorrelation of your data by using the inverse of this window overlap versus lag function.

$\endgroup$
  • $\begingroup$ This salient point is made in this online paper. As far as I can tell, if you are going to use frequency-domain autocorrelation, you have to zero-pad and compensate for the effect of the windows sliding away from each other. If you do it all in the time domain, there are ways to avoid that roll-off. $\endgroup$ – robert bristow-johnson Dec 26 '15 at 23:31
  • $\begingroup$ Exactly. So there is no way to get rid of it in the frequency domain? Have to live with time domain then or compare the results / performance of both at a later point. $\endgroup$ – ruhig brauner Dec 27 '15 at 10:50
  • $\begingroup$ Get rid of it in the frequency domain by multiplying by a compensation window in the frequency domain (except where the triangle effect gets close to zero). $\endgroup$ – hotpaw2 Dec 27 '15 at 15:40
0
$\begingroup$

You are on the right track. To get the fundamental, you do have to zero-pad and then auto-correlate. The main peak in the above graph (looks like its at 1024) is the in-phase correlation. The second strongest peaks (looks like they are about 100 bins away from that main peak) will be at one wavelength away from the main peak, and that is the wavelength of the fundamental (I estimate about 100 bins). The reason you get the triangle effect is not so much from the zero padding (which is necessary, though), its from the fact that your window size is finite. That is, the further away from phase zero you get in an auto-correlation, the less energy matches from one data set because the more of it lies on top of the zero padding of the other data set. You can picture it by picturing the time-domain (with zero padding) auto-correlation.

$\endgroup$
  • $\begingroup$ That's exactly what I thought. And I hoped that there is a way to get rid of it. ;) Otherwise it's a bit cumbersom to analyse the data. You can't just search for the highest peak that's not the "0 delay peak". :/ $\endgroup$ – ruhig brauner Dec 27 '15 at 10:49
  • $\begingroup$ I have simply zeroed-out the bins around the in-phase peak (say, +/-10 bins, or so) and then searched the data from strongest peak. $\endgroup$ – Digiproc Dec 27 '15 at 12:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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