Hi there, I have a question regarding the definitions surrounding FFTs. The help to numpy.fft.fft says:
help(N.fft.fft) Help on function fft in module numpy.fft.fftpack:
fft(a, n=None, axis=-1) fft(a, n=None, axis=-1) Will return the n point discrete Fourier transform of a. n defaults to the length of a. If n is larger than a, then a will be zero-padded to make up the difference. If n is smaller than a, the first n items in a will be used. The packing of the result is "standard": If A = fft(a, n), then A[0] contains the zero-frequency term, A[1:n/2+1] contains the positive-frequency terms, and A[n/2+1:] contains the negative-frequency terms, in order of decreasingly negative frequency. So for an 8-point transform, the frequencies of the result are [ 0, 1, 2, 3, 4, -3, -2, -1]. This is most efficient for n a power of two. This also stores a cache of working memory for different sizes of fft's, so you could theoretically run into memory problems if you call this too many times with too many different n's.
However, the help to numpy.fft.helper.fftfreq says:
help(N.fft.helper.fftfreq) Help on function fftfreq in module numpy.fft.helper:
fftfreq(n, d=1.0) fftfreq(n, d=1.0) -> f DFT sample frequencies The returned float array contains the frequency bins in cycles/unit (with zero at the start) given a window length n and a sample spacing d: f = [0,1,...,n/2-1,-n/2,...,-1]/(d*n) if n is even f = [0,1,...,(n-1)/2,-(n-1)/2,...,-1]/(d*n) if n is odd
So one claims, that the packing goes from [0,1,...,n/2,-n/2+1,..,-1] (fft) and the other one claims the frequencies go from [0,1,...,n/2-1,-n/2,...-1] Is this inconsistent or am I missing something here? Hanno -- Hanno Klemm klemm@phys.ethz.ch
The frequencies produced by the two recipies are not the same. But the DFT is periodic in both frequency and time. So whether you think that the number in bin in n/2 should correspond to frequency n/2 or -n/2, it's the same number. w On Mon, 5 Feb 2007, Hanno Klemm wrote:
Hi there,
I have a question regarding the definitions surrounding FFTs. The help to numpy.fft.fft says:
help(N.fft.fft) Help on function fft in module numpy.fft.fftpack:
fft(a, n=None, axis=-1) fft(a, n=None, axis=-1)
Will return the n point discrete Fourier transform of a. n defaults to the length of a. If n is larger than a, then a will be zero-padded to make up the difference. If n is smaller than a, the first n items in a will be used.
The packing of the result is "standard": If A = fft(a, n), then A[0] contains the zero-frequency term, A[1:n/2+1] contains the positive-frequency terms, and A[n/2+1:] contains the negative-frequency terms, in order of decreasingly negative frequency. So for an 8-point transform, the frequencies of the result are [ 0, 1, 2, 3, 4, -3, -2, -1].
This is most efficient for n a power of two. This also stores a cache of working memory for different sizes of fft's, so you could theoretically run into memory problems if you call this too many times with too many different n's.
However, the help to numpy.fft.helper.fftfreq says:
help(N.fft.helper.fftfreq) Help on function fftfreq in module numpy.fft.helper:
fftfreq(n, d=1.0) fftfreq(n, d=1.0) -> f
DFT sample frequencies
The returned float array contains the frequency bins in cycles/unit (with zero at the start) given a window length n and a sample spacing d:
f = [0,1,...,n/2-1,-n/2,...,-1]/(d*n) if n is even f = [0,1,...,(n-1)/2,-(n-1)/2,...,-1]/(d*n) if n is odd
So one claims, that the packing goes from [0,1,...,n/2,-n/2+1,..,-1] (fft) and the other one claims the frequencies go from [0,1,...,n/2-1,-n/2,...-1]
Is this inconsistent or am I missing something here?
Hanno
-- Hanno Klemm klemm@phys.ethz.ch
_______________________________________________ Numpy-discussion mailing list Numpy-discussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpy-discussion
On 2/5/07, Hanno Klemm <klemm@phys.ethz.ch> wrote: [numpy.fft[ The packing of the result is "standard": If A = fft(a, n), then A[0]
contains the zero-frequency term, A[1:n/2+1] contains the positive-frequency terms, and A[n/2+1:] contains the negative-frequency terms, in order of decreasingly negative frequency. So for an 8-point transform, the frequencies of the result are [ 0, 1, 2, 3, 4, -3, -2, -1].
[scipy.fft] f = [0,1,...,n/2-1,-n/2,...,-1]/(d*n) if n is even
f = [0,1,...,(n-1)/2,-(n-1)/2,...,-1]/(d*n) if n is odd
So one claims, that the packing goes from [0,1,...,n/2,-n/2+1,..,-1] (fft) and the other one claims the frequencies go from [0,1,...,n/2-1,-n/2,...-1]
Is this inconsistent or am I missing something here?
Both, I think. In the even case, the frequency at n/2 is shared by both the positive frequencies, so for that case things are consistent if not terribly clear. For the odd case, this is not true, and the scipy docs look correct in this case, while the numpy docs appear to assign an extra frequency to the positive branch. Of course that's not the one you were complaining about ;-). To be super pedantic, the discrete Fourier transform is periodic, so all of the frequencies can be regarded as positive or negative. That's not generally useful, since the assumptions that go into the DFT that make it periodic don't usually apply to the signal that you are sampling. Then again the results of DFTs are typicallly either small or silly in the vicinity of N//2. //=][=\\ tim.hochberg@ieee.org
On Mon, 5 Feb 2007, Timothy Hochberg wrote:
On 2/5/07, Hanno Klemm <klemm@phys.ethz.ch> wrote: [numpy.fft[
The packing of the result is "standard": If A = fft(a, n), then A[0]
contains the zero-frequency term, A[1:n/2+1] contains the positive-frequency terms, and A[n/2+1:] contains the negative-frequency terms, in order of decreasingly negative frequency. So for an 8-point transform, the frequencies of the result are [ 0, 1, 2, 3, 4, -3, -2, -1].
[scipy.fft]
f = [0,1,...,n/2-1,-n/2,...,-1]/(d*n) if n is even
f = [0,1,...,(n-1)/2,-(n-1)/2,...,-1]/(d*n) if n is odd
So one claims, that the packing goes from [0,1,...,n/2,-n/2+1,..,-1] (fft) and the other one claims the frequencies go from [0,1,...,n/2-1,-n/2,...-1]
Is this inconsistent or am I missing something here?
Both, I think.
In the even case, the frequency at n/2 is shared by both the positive frequencies, so for that case things are consistent if not terribly clear. For the odd case, this is not true, and the scipy docs look correct in this case, while the numpy docs appear to assign an extra frequency to the positive branch. Of course that's not the one you were complaining about ;-).
Extra frequency where? (numpy 1.0, debian sarge)
n=9 A=arange(n)
numpy docs:
A[1:n/2+1] array([1, 2, 3, 4]) A[n/2+1:] array([5, 6, 7, 8])
scipy docs:
(n-1)/2 4 -(n-1)/2 -4
Note that in the odd-n case, there is no Nyquist term. If F = fft(f), len(f) == 9 then F[-4] != F[4] (F[5] == F[-4] by periodicty in frequency) w
To be super pedantic, the discrete Fourier transform is periodic, so all of the frequencies can be regarded as positive or negative. That's not generally useful, since the assumptions that go into the DFT that make it periodic don't usually apply to the signal that you are sampling. Then again the results of DFTs are typicallly either small or silly in the vicinity of N//2.
//=][=\\
tim.hochberg@ieee.org
On 2/5/07, Warren Focke <focke@slac.stanford.edu> wrote:
On Mon, 5 Feb 2007, Timothy Hochberg wrote:
On 2/5/07, Hanno Klemm <klemm@phys.ethz.ch> wrote: [numpy.fft[
The packing of the result is "standard": If A = fft(a, n), then A[0]
contains the zero-frequency term, A[1:n/2+1] contains the positive-frequency terms, and A[n/2+1:] contains the negative-frequency terms, in order of decreasingly negative frequency. So for an
8-point
transform, the frequencies of the result are [ 0, 1, 2, 3, 4, -3, -2, -1].
[scipy.fft]
f = [0,1,...,n/2-1,-n/2,...,-1]/(d*n) if n is even
f = [0,1,...,(n-1)/2,-(n-1)/2,...,-1]/(d*n) if n is odd
So one claims, that the packing goes from [0,1,...,n/2,-n/2+1,..,-1] (fft) and the other one claims the frequencies go from [0,1,...,n/2-1,-n/2,...-1]
Is this inconsistent or am I missing something here?
Both, I think.
In the even case, the frequency at n/2 is shared by both the positive frequencies, so for that case things are consistent if not terribly clear. For the odd case, this is not true, and the scipy docs look correct in this case, while the numpy docs appear to assign an extra frequency to the positive branch. Of course that's not the one you were complaining about ;-).
Extra frequency where?
(numpy 1.0, debian sarge)
n=9 A=arange(n)
numpy docs:
A[1:n/2+1] array([1, 2, 3, 4]) A[n/2+1:] array([5, 6, 7, 8])
scipy docs:
(n-1)/2 4 -(n-1)/2 -4
Note that in the odd-n case, there is no Nyquist term. If F = fft(f), len(f) == 9 then F[-4] != F[4] (F[5] == F[-4] by periodicty in frequency)
Ooops, you're right I worked this through on paper and just blew it. I suppose I'd look less silly had I actually checked the results using the interpreter. -- //=][=\\ tim.hochberg@ieee.org
participants (3)
-
Hanno Klemm
-
Timothy Hochberg
-
Warren Focke