# Is there an algorithm for finding a frequency without DFT or FFT?

I was looking in the Android app store for a guitar tuner. I found a tuner app that claimed it was faster than other apps. It claimed it could find the frequency without using the DFT (I wish I still had the URL to this specification).

I have never heard of this. Can you acquire an audio signal and compute the frequency without using the DFT or FFT algorithm?

FFT is actually not a great way of making a tuner. FFT has inherently a finite frequency resolution and it's not easy to detect very small frequency changes without making the time window extremely long which makes it unwieldy and sluggish.

Better solutions can be based on phase-locked loops, delay-locked loops, auto correlation, zero crossing detection and tracking, max or min detection and tracking and certainly intelligent combination of these methods.

Pre-processing always helps.

• Whether an FFT can detect small frequency changes is not inherent in its length, but depends on the signal-to-noise ratio. Given sufficiently low noise and interference, interpolation of FFT results can easily produce sub-bin single frequency resolution. Commented Feb 2, 2012 at 19:35
• can anybody help me out with this : - stackoverflow.com/questions/42359344/… Commented Feb 22, 2017 at 4:29

An FFT reports spectrum frequency peak or peaks (quantized by FFT bin size), which is different from musical pitch. It's possible for the perceived pitch frequency to be completely missing from an FFT spectrum.

Some of the simplest guitar tuners just used low-pass or band-pass filtering and measured the time between zero-crossings. The reciprocal gives a frequency estimate.

Autocorrelation is another common pitch estimation method; and sliding correlation or other self-similarity measures have lots of variations, such as sliding ASDF (squared difference), AMDF (mean difference), non-linear pattern matchers, adaptive checking only for a limited range of lags, lag interpolation, windowing and adaptive window selection, various weightings or using decision theory to select among multiple potential lag history sequences, and etc. One problem with most self-similarity measures is choosing the appropriate octave, as a sub-octave may show nearly the same similarity.

Other possibilities include using PLLs, filtered quadrature demodulators, filtered Hilbert transforms, and etc.

But note that some DSP filtering and demodulation methods are computationally nearly equivalent to doing 1-bin of a windowed DFT, which may or may not fit as an answer to your question.

Pitch detection can be done in many versatile and curious ways. One way to do it is by using autocorrelation. This paper gives an example of how it can be used. Autocorrelation can be made ridiculously simple by using a 1-bit correlator (couldn't find any decent papers on that for some reason). So theoretically, pitch can be detected faster than with FFT, but I doubt that it will be much more precise without really clever pre-processing.

• I think the link is broken?... Commented Feb 2, 2012 at 18:31
• No, all works. I just checked it. Commented Feb 2, 2012 at 22:30

Also take a look at the relatively new algorithmically defined Hilbert-Huang Transform (HHT). It can handle non-stationary-non-linear signals which may be relevant for your application.

• This was quite a gem when I found it, although it does not give you the fourier decomposition, but rather, the instantaneous frequency decomposition. Commented Apr 13, 2012 at 22:26
• Most real-life signals are somewhat non-stationary, that is they vary slightly in amplitude and frequency. The HHT is less sensitive to these variations and thereby decompose such signals in a more natural way, where the parts are more closely related to the underlying physical phenomena. Commented Mar 11, 2013 at 21:29

If you know exactly which frequency bin you are looking for in a DFT/FFT then you can use the Goertzel algorithm to get the value of that bin only.

http://en.wikipedia.org/wiki/Goertzel_algorithm

• That's not for finding a frequency, though. Commented Feb 4, 2012 at 16:02

I have got a guitar a month ago and started writing a PLL-based tuner.

One of the resources I used to understand PLL was "Understanding Phase-Locked Loops" page by Paul Lutus.

You can actually compute the frequency of a signal using its pseudo-spectrum, which looks at the eigenvectors of its autocorrelation matrix. It basically decomposes your signal into noise and signal subspaces. From there, you can find its spectrum. (You can also limit it and give it a range of frequencies to check). It is also pretty noise immune. Of course, this is a parametric method, not an unparametric one like DFT.

• Apparently this uses the FFT though? mathworks.com/help/toolbox/signal/ref/peig.html Commented Apr 15, 2012 at 23:31
• @endolith You can compute it without any FFTs involved. From the correlation matrix, you get the eigenvectors, and then the noise subspace. Then you can construct your own frequency vector to project against, so no FFTs used. Commented Apr 16, 2012 at 2:30

It all depends with what platform you want to process it, if you need a simple circuit, i suggest blasting out the signal with gain and turn it into a square wave and measure the period with a microcontroller using the timer.

But if you want to go fancy with signal processing, check out MUSIC method:

http://en.wikipedia.org/wiki/Multiple_signal_classification

Hope it helps

There exist a lot of pitch estimation methods without using DFT/FFT, some of them including the MUSIC method are listed in this paper: https://ieeexplore.ieee.org/abstract/document/6521410/ The simulation results in this paper indicate that when the fundamental frequency is very low, the exact NLS method outperforms others among the listed.