[PD] OT: faster than Fourier transform

[Charles Henry]

On Thu, Feb 2, 2012 at 3:07 PM, Mathieu Bouchard <matju at 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...