The traditional Discrete Fourier Transform (DFT) and its cousin, the FFT, produce bins that are spaced equally. In other words, you get something like the first 10 hertz in the first bin, 10.1 through 20 in the second, etc. However, I need something a little different. I want the range of frequency covered by each bin to increase geometrically. Suppose I select a multiplier of 1.5. Then we have 0 through 10 in the first bin, I want 11 through 25 in the second bin, 26 through 48 in the third, etc. Is it possible to modify the DFT algorithm to behave in this fashion?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ You can always calculate DFT at the points of interest. Also, Discrete Wavelet Transform and Filter Banks come to my mind. Might be worth looking at them. $\endgroup$– AlexCommented Mar 24, 2012 at 6:46
-
3$\begingroup$ You are looking for the Constant Q Transform (CQT). $\endgroup$– Paul RCommented Mar 24, 2012 at 6:49
-
2$\begingroup$ Poorly worded. What you want is neither new, nor an improvement in many cases. $\endgroup$– hotpaw2Commented Mar 24, 2012 at 20:42
-
$\begingroup$ Related: stackoverflow.com/q/1120422/125507 dsp.stackexchange.com/q/651/29 $\endgroup$– endolithCommented Mar 26, 2012 at 17:40
-
2$\begingroup$ DFT and FFT are not cousins. They give identical results. $\endgroup$– PhononCommented Mar 26, 2012 at 20:38
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
To quote my dissertation:
A collection of transforms are given the name constant Q and are similar to the Fourier transform.
Computation of the discrete Fourier transform can be very efficient when employing the use of the fast Fourier transform. However we notice that energy of a signal is divided into uniformly sized frequency buckets across the spectrum. While in many cases this is useful, we notice situations where this uniform distribution is sub-optimal. An important example of such a case is observed with the analysis of musical frequencies. In Western music, the frequencies that make up the musical scales are geometrically spaced. We therefore see that the map between frequency bins of the discrete Fourier transform and the frequencies of musical scales is insufficient in the sense that the bins match poorly. The constant Q transform addresses this issue.
The aim of the constant Q is to produce a set of logarithmically spaced frequency bins in which the width of the frequency bin is a product of the previous. As a result we may produce an identical number of bins per musical note across the audible spectrum, thus maintaining a constant level of accuracy for each musical note. The frequency bins become wider towards the higher frequencies and narrower towards the lower frequencies. This spread in the accuracy of frequency detection closely imitates the manner in which the human-auditory system responds to frequencies.
Additionally, the close matching of notes in western scales renders the constant-Q particularly useful in note detection; identifying a musical note value rather than an explicit frequency value. Furthermore the constant Q simplifies the process of timbre analysis. The frequencies of a musical note played by an instrument are often comprised of harmonically related partials. The timbre of the instrument can be characterised by the ratios of the harmonics. With the constant Q transform, the harmonics are equally spaced across the bins regardless of the fundamental frequency. This greatly simplifies the process of identifying an instrument playing a note anywhere in the scale simply by shifting the characterisation across the bins. A potential downside to using the constant Q transform is that it demands more computation than the Fourier transform.
An efficient algorithm for transforming a discrete Fourier transform (which may be computed with the FFT) into a Constant Q transform is detailed in Brown and Puckette (1992).
$\begingroup$
$\endgroup$
There are significant mathematical assumptions in the DFT(FFT). The most significant in this case is that you are performing a truncated infinite-time sinusoid transformation. The second is that the truncated time and truncated frequncy signals are assumed to be modulo-wrapped (circular.) The bins as spaced in a normal FFT form an orthonormal set only because of these assumptions (and the even arithmetical-sense spacing.) The time <-> frequency pair are therefore perfectly reversible.
The constant-Q transform doesn't truncate so nicely, therefore any practical implementation doesn't yield perfect ortho-normal pairing. The kernel is an infinitely long exponentially decaying sinusoid and therefore cannot have the circular advantage indicated above. If you don't truncate, they do form an orthonormal set.
The wavelet transforms are typically power-of-2 spaced, which isn't very useful for fine-grained frequency estimation.
The suggestion to unevenly space a standard sinusoid DFT will miss information in the widely spaced region while it will duplicate information in the densely spaced region. Unless, a different apodization function is used for each frequency ... very costly.
One practical solution is to do a half-spectrum->decimate-by-2 repeated procedure to get octave based sub-sections to satisfy some minimax estimation error per octave. The portion-spectrum->decimate-by-ratio can be set to any ratio to achieve any granularity need. Still pretty compute intensive, though.
