Le 2012-02-03 à 10:10:00, Charles Henry a écrit :
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.
Well, there are not-so-obvious implications, and this is why there are several different reformulations of the principle (position vs momentum ; energy vs time ; sampling signals ; entropy ; etc).
Even when just looking at the version(s) about sampling, different ideas come out of it. You can't get information about a frequency if you don't take enough time to measure it or if you don't take enough measurements. Otherwise it may have been any other frequency. Whenever you do sampling, you have to either suppose or ensure that the analog signal does not contain frequencies that will confuse you. Otherwise, you'll get aliases.
This might be expressible more precisely in terms of standard-deviation, but I haven't really studied the topic of sampling to that level of depth.
I agree that it's a hard limit, but it's really just a math problem to begin with :)
Math is an excellent source of hard limits. There are not as many hard limits that require you to look at the universe to find them.
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.
Well, if you have to produce n slightly different values at the time of every sample, that implies O(n) steps. That's a hard limit unless lazy evaluation.
But if you have different rates for different harmonics, you might be able to skip more computations...
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.
Shifting what by m samples ?
A sliding DFT doesn't imply a FFT. It could mean doing the long form of the DFT but in a gradual fashion... a slow integrator just like what you could be doing using [rpole~ 1] on the result of [*~] [osc~].
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).
I was going to say that...
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.
BTW, if you multiply F1 by 1+i = sqrt(2i), then you can use a partially-precomputed version of Gauss' multiplication shortcut... but it doesn't make an improvement of order.
http://en.wikipedia.org/wiki/Multiplication_algorithm#Gauss.27s_complex_mult...
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).
The sign used in a forward DFT depends on whether you are using cos(t+offset) vs cos(t-offset). If your phases are mirrors of everybody else's, then your forward DFT's sign will have to be the opposite of everybody else's too.
| Mathieu BOUCHARD ----- téléphone : +1.514.383.3801 ----- Montréal, QC