On Thu, Feb 2, 2012 at 3:07 PM, Mathieu Bouchard matju@artengine.ca wrote:
Le 2012-02-02 à 02:36:00, Ed Kelly a écrit :
Still the problem with any window-based FFT is that we have to get enough points (e.g. 512, 1024) before we can do the analysis, so there is always a delay (44100/1024 = ~43ms) between live input and output (latency).
Heisenberg's Uncertainty Principle (in its acoustic version) is a hard theoretical limit, meaning it can't possibly be violated.
As I understand it, it's just a sheer mathematical fact expressing the trade-off between the std deviation of a distribution in the time domain and the std deviation of the fourier transform of that distribution.
But then you apply it to the Shrodinger equation (a differential equation involving position and velocity) and you get the most famous corollary in quantum.
I agree that it's a hard limit, but it's really just a math problem to begin with :)
All you can do is separate the analysis of frequencies so that you get frequent results for treble vs less frequent results for bass. This comes at the expense of having to customise, complicate and/or slow down FFT to make it do what you want.
Much more interesting is the sliding phase vocoder (Russell Bradford, Richard Dobson, and John ffitch, 2005) where the FFT is adjusted in each sample rather than each frame, and the latency is significantly reduced.
What's the speed of the sliding DFT ?
I can think of an O(n) algorithm for it (per sample). I'd be surprised if there's anything better. You'd still have to do an FFT to begin with, and after shifting by m samples, you'd be in O(m*n) territory.
Assume you've got a signal s on [0,N-1] and you have already computed its DFT plus this vector F1={e^(2*pi*i* k/N}, k=0,...,N-1
The next DFT to calculate is on [1,N]. First subtract out the contribution of s(0)--this is easy because the DFT of {s(0),0,0,..} is {s(0),s(0),s(0),...}
Next, the values in the resulting vector are multiplied by F1. This has the effect of shifting the time domain signal to the left by 1 sample.
Then, add in the effect of the new sample, F1*s(n).
I see some ways those steps could be made simpler. Lump the 1st and 3rd steps together and just add s(n)-s(0) to all the DFT values, then multiply once by F1 (performing a circular shift in the time domain). On the next iteration, use s(n+1)-s(1). So, the total cost is a buffer of N samples, a complex vector of N DFT values (F1)---N+1 additions/subtractions, and N complex multiply operations (each is 4 multiply and 2 additions/subtractions), per sample.
There might be some constants to shake out depending which DFT formula you decide to use. The sign convention on the DFT is arbitrary, so I often get mixed up (F1 could be e^(-2*pi*i*k/N){k=0,...,N-1} if I'm wrong).
Note that they call it «DFT», and not «FFT», and that's presumably because it doesn't have to do much with FFT... whereas DFT is a more generic term for whatever computes harmonics on blocks of discrete signals.
The access to the sliding DFT article is reserved to IEEE members...