# Logarithmic fourier transform(LFT) on audio signal

I am trying to analyze the musics as possible as precisely. Of course I tried FFT, but got some problems.

I found low frequencies have very low resolution than human's hearing. I tried very long time FFT to resolve this problem, but even analyzing with 8192 samples/s in 44100Hz sample rate(Means lack of time resolution), I got not enough resolution on low frequencies.

I found there are few solutions.

Firstly, a quadratic interpolation on FFT bins.
But it seems not a perfect way. Problems of this method are:

1. 'If i want to determine freqs between the freq bins, which three bins should I select to do an interpolation?'
2. 'Even I do this, there are no actual additional informations on result. I know interpolations are kind of tricky method.'

Secondly, extracting each freq bins with desired frequency, so I can extract the bins logarithmically.
But have a critical computational cost problem: (maybe over)N^2.

Thirdly, LFT(Logarithmic Fourier Transform).
This requiers logarithmically-spaced samples and gives me result exactly what I looking for with incredibly fast speed; https://stackoverflow.com/questions/1120422/is-there-an-fft-that-uses-a-logarithmic-division-of-frequency

But I have no idea with that algorithm. I tried to understand the paper and implement it, but it was impossible because of lack of my english and mathematical skills.

So, I need a help of implementation of LFT.

The simplest and most pragmatic solution is to use a normal FFT of a sufficiently large size that you get the required resolution at the lowest frequency of interest. E.g. if you want 1 Hz resolution at the lowest frequency of interest then you will need a 1 second FFT window, i.e. the FFT size would need to be equal the sample rate, e.g. 44100.

Note that even if you could implement a logarithmic FFT then it would still be bound by the laws of physics (information theory) and you would still need a similar length sample window - all you would gain would be convenience (not having to aggregate output bins) at the expense of performance.

• It's weird. I know that theorically there are no more data. If I use a large size FFT, it's true that it's not able to analyze very fast onsets of musical instrument. And it's also true that I am not able to get higher resolution on low frequency. But how about human hearing system? How that system is getting higher resolution both in time and frequencies?
– Jee-heon Oh
Jan 20, 2013 at 12:45
• Perhaps you should consider a hierachical approach, where you decimate each successive octave by a factor of 2, so that you can use short time windows at higher frequencies and longer time windows at lower frequencies? This would be somewhat analogous to an auditory filter bank, where bandwidth increases with frequency. Jan 20, 2013 at 17:25
• Great approach. Long time goertzel on low frequencies, short time goertzel on high frequencies? Makes sense. But will require a great computational costs.
– Jee-heon Oh
Jan 21, 2013 at 10:21
• It's probably more efficient than doing one large FFT, even though it's more complex. E.g. for a 4 octave hierarchy you might want 4 x 2048 point FFTs and 3 low pass filters for x2 down-sampling. The resolution of the lowest FFT will be as good as a single 16384 point FFT at the full sample rate, but since FFT is O(n log n) the total computational cost will be much lower. Jan 21, 2013 at 11:16
• aha, FFT 2048, down sample x2, FFT 2048, down sample x2.... than I have both time and frequency resolution, with much lesser costs than 16384 FFT. Great. And just now I have the another solution: on 16384 sample, goertzel each time by 32. So, with accumulating, I can extract both low and high frequencies with lesser costs. Thanks a lot. :)
– Jee-heon Oh
Jan 21, 2013 at 11:43

If the analysis you intend to perform requires the frequency of the signals in each bin, you can use the Short Time Fourier Transform to achieve this.

Each bin of the FFT yields a complex number representing the real and imaginary component- or after a bit of manipulation phase and magnitude.

As frequency = dPhi/dt, (Phi == phase), by taking corresponding bins from pairs of consecutive STFT spectra, you can calculate frequency.

DSP Dimension has a good article on the process.

• Looks like I am contemplating a further more complexed problem. I can use FFT, but on audio signal analysis, it's not suitable, though.
– Jee-heon Oh
Jan 21, 2013 at 10:24
• Look at the "constant Q" version of the Short Time Fourier Transform. This arrangement of the STFT provides frequency resolution that adjusts logarithmically to accommodate requirements for different frequency ranges. Jan 21, 2013 at 14:25
• I will take a look. I thought it was just a simple filter-bank transform operation applied to fft result.
– Laie
Jan 21, 2013 at 14:41