finding the fundamental frequency in frequency domain

Question

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

Answer 1

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.

Answer 2

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.