# [Numpy-discussion] Here's what I've done to numpy.fft

Travis Oliphant oliphant@enthought....
Mon Jul 12 20:33:11 CDT 2010

On Jul 12, 2010, at 5:47 PM, David Goldsmith wrote:

> In light of my various questions and the responses thereto, here's what I've done (but not yet committed) to numpy.fft.
>
> There are many ways to define the DFT, varying in the sign of the
> exponent, normalization, etc.  In this implementation, the DFT is defined
> as
>
> .. math::
>    A_k =  \sum_{m=0}^{n-1} a_m \exp\left\{-2\pi i{mk \over n}\right\}
>
> where n is the number of input points.  In general, the DFT is defined
> for complex inputs and outputs, and a single-frequency component at linear
> frequency :math:f is represented by a complex exponential
> :math:a_m = \exp\{2\pi i\,f m\Delta t\}, where
> :math:\Delta t is the *sampling interval*.

This sounds very good, but I would not mix discussions of sampling interval with the DFT except as an example use case.

The FFT is an implementation of the DFT, and the DFT is self-contained for discrete signals without any discussion of continuous-time frequency or sampling interval.   Many applications of the FFT, however, use sampled continuous-time signals.

So, use a_m = \exp$$2\pi j m k$$ to describe the single-frequency case.   If you want to say that k = f\Delta t for a sampled-continuous time signal, then that would be fine, but there are plenty of discrete signals that don't have any relation to continuous time where an FFT still makes sense.

>
> Note that, due to the periodicity of the exponential function, formally
> :math:A_{n-1} = A_{-1}, A_{n-2} = A_{-2}, etc.  That said, the values in
> the result are in the so-called "standard" order: if A = fft(a,n),
> then A[0] contains the zero-frequency term (the sum of the data),
> which is always purely real for real inputs.  Then A[1:n/2] contains
> the positive-frequency terms, and A[n/2+1:] contains the
> negative-frequency (in the sense described above) terms, from least (most
> negative) to largest (closest to zero).  In particular, for n even,
> A[n/2] represents both the positive and the negative Nyquist
> frequencies, and is also purely real for real input.  For n odd,
> A[(n-1)/2] contains the largest positive frequency, while
> A[(n+1)/2] contains the largest (in absolute value) negative
> frequency.  In both cases, i.e., n even or odd, A[n-1] contains the
> negative frequency closest to zero.
>
> Feedback welcome.

I would remove "That said, " near the beginning of the paragraph.

Thanks for the great docs.

-Travis