[SciPy-dev] fftpack2 for review

[Travis Oliphant]

> To be honest, I used the docs of scipy.fftpack.fft as a basic reference
> and followed that while implementing fftpack2. Until fftshift, everything
> was consistent. Then it turned out that fftshift uses a different
> convention than fft. Namely, according to scipy.fftpack.fft docs, the
> corresponding frequencies of the fft result are given as
>    [ 0, 1, 2, 3, 4, -3, -2, -1]
> for n=8 case, for example. But fftshift assumed
>    [ 0, 1, 2, 3, -4, -3, -2, -1]

O.K. so this is the issue:  How to treat the Nyquist value for even length
fft.

> Both cases are equivalent except when applying the definition of fftshift,

Yes, this is true, the fft value for bin 4 is the same as for bin -4 so
how you interpret it doesn't really matter.  Except for the fact that a
large group of people have been trained to calculate the FFT using MATLAB
and will be used to using fftshift where the convention is to interpret
the Nyquist value as the value for the negative bin number (-4).

This is a sutble difference but could cause headaches for many people
starting to use scipy who think they know how to shift the results of an
FFT to get a plot based on their MATLAB experience.

Because it really doesn't matter, I'm inclined to go with what MATLAB
chose rather than have a new convention.

> that is, how to order the frequencies of the fft result.
> Now, in fftpack2 I just kept being consistent (as everything were
> documented already) and as a result, the results of fftpack2.freqshift and
> fftshift (in scipy.fftpack and Matlab) had to differ by the location
> of the Nyquist mode

I don't understand how you were consistent.  What is documented already?
Why is interpreting the Nyquist mode as coming from a positive frequency
more consistent?

(that's also one of the hidden reasons why I
> introduced a new name freqshift for fftshift; about the other reason, see
> below).
>
> I guess it would not be a good idea to have both freqshift and fftshift at
> the same time (the latter behaving exactly as fftshift in MATLAB).

I suppose that is fine.

> Personally, I have no preference to either of them, it's just a
> matter of choosing a convention and sticking to it.  But since you insist
> MATLAB convention, I'll change the docs in fftpack2: basically, the
> Nyquist mode will be corresponding to the smallest negative frequency
> instead of the largest positive one.

That is what I would recommend.

> Ok. But I still think that "fftshift" is a misleading name, even
> if MATLAB uses it. Often people forget that FFT is just an efficient
> algorithm for performing the Fourier matrix multiplication with a vector,
> nothing more. And fftshift has nothing to do with this FFT algorithm.
>

True people do forget the difference between DTFT and FFT, and fftshift
doesn't have anything to do with the FFT algorithm.

But, the reason for fftshift is because of the way the FFT algorithm
computes the frequency leaving the positive frequencies in the first
half and the negative frequencies in the last half.  We usually don't
draw graphs this way (or create ranges this way).   So, I would submit
that fftshift is still a good name because it is a shift made necessary
by the use of the FFT.

But, it doesn't really matter and I'm not so opposed to freqshift either.
It's a fine name too.  We aren't copying all of MATLAB's names for every
other function.  I just lean towards the name fftshift because I've gotten
so used to using it the many, many, many times I've computed Fourier
transforms

> I see the following solutions:
> 1) continue with a bad manner learned from Matlab and use fftshift

I don't agree that fftshift is so bad.

> 2) use a more appropriate name, I proposed freqshift (other suggestions
> are welcome), and may be provide fftshift in MLab.py, for example.
>

> On the other hand, I don't want that some function name will make somebody
> unhappy. Right now I am just proposing this name change because it feels
> right to me and it is the right time to make a choice, later it would be
> too late. What do you think?

I'm not going to be sad either way.   But, I do think we should stick with
the convention of interpreting the Nyquist mode as a negative frequency.

I'm very happy with the great job you've done in cleaning up and testing
the fft package.

--Travis O.


P.S.  I also have a command called fftfreq that generates the frequency
values for each index (bin) assumed by the FFT algorithm.  I noticed you
did something similar with dftfreq.  This is another point we need to iron
out.