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_multiplication_algorithm
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
_______________________________________________
[email protected] mailing list
UNSUBSCRIBE and account-management ->
http://lists.puredata.info/listinfo/pd-list
