Re: MATLABs FFT and fftshifting the input

On Jan 21, 8:42 am, Greg Heath <he...@xxxxxxxxxxxxxxxx> wrote:
....
I agree that MATLAB not using nonpositive indexing results
in wierd stuff...

Don't shoot the messenger!

not planning to (unless your name is Cleve Moler). this is an old and
tired problem with MathWorks spouting their old and tired excuses for
not fixing nor even recognizing the problem.

For example, regardless of how the time sample is circularly
shifted, when N is even, MATLAB's fftshift puts the Nyquist
point at the leftmost point of the negative frequency interval.

yes. and there is no Nyquist point for N odd.

However, that is really irrelevant to the main point. Regardless
of the indexing convention, when N is odd, MATLAB's fftshift is
not self inverting.

well, since i have never done an FFT in MATLAB with odd N, i never got
around to wondering what would happen.

i believe the main point from the OP on is "why would someone use
fftshift() on the *input* to the fft()?" and there is an answer to
that.


Therefore it's use should be confined to the
frequency domain for centering spectra that are created over a
nonnegative frequency interval by the fft.

ya know. these are numbers, arrays of numbers. the DFT does not know
nor care if the input to it is time or frequency domain. the iDFT is
just like the DFT except for a scaling factor.

That answers the question posed by the OP who
is trying to grasp how to use MATLAB's version
of fft.

So why is this thread dragging on?

but the main thing you're missing now, Greg, is that the DFT really
only transforms a periodic discrete sequence in the "time" domain to
another periodic discrete sequence in the "frequency" domain.

No.

The DFT really only transforms a finite discrete sequence in the
"time" domain to a periodic discrete sequence in the "frequency"
domain.

that's an old debate we had here at comp.dsp periodically, that you
are sure to lose.

there is not one mathematical difference between what we call the
"Discrete Fourier Transform" and what we call the "Discrete Fourier
Series".

i might recommend reading what Oppenheim and Schafer have to say about
it.

The IDFT transforms a finite discrete sequence in the "frequency"
domain to a periodic discrete sequence in the "time" domain.

you *better* put those quotes there because the iDFT doesn't know and
doesn't care if it's "time" or "frequency".

and there is *no* qualitative difference between the DFT and the
iDFT. most definitions put the 1/N factor completely in one or the
other (usually in the iDFT) but you can have a legit definition that
puts 1/sqrt(N) in both the DFT and iDFT. there is no qualitative
difference between -j and +j (they both have equal claim to squaring
to be -1 and no other numbers can make that claim).

so, if you're gonna build a case that ifftshift() should be used only
with one and that fftshift() should be used only with the other, it's
already a loser.

In other words, the representation obtained by the transform and
its inverse creates periodicity even when it is not present in the
original data.

perhaps a shorter way to say that is that the DFT periodically extends
the input presented to it.

it "assumes" (to anthropomorphize a bit) that the data passed to it is
exactly on period of a periodic sequence. and the DFT output is one
period of a periodic sequence of the same period, N.


those
points (using horrible MATLAB indexing convention), X(N/2+2:N) are
just as plausible being positive frequency above Nyquist as being
negative frequency.

I have a problem with that statement. It's akin to saying that
X(2:N/2) are just as plausible being negative frequency below
negative Nyquist as being positive frequency.

positive frequency above Nyquist. the data (going in or coming outa
the DFT) is periodic. always. it never is not periodic.

so (not using horrible MATLAB indexing) the data from X[N/2] to X[N]
can just as well be from X[-N/2] tp X[0]. it's interpretation. if
you look at x[0] to x[N-1] as being sampled from a real, continuous-
time function x(t), then we expect *before* sampling that there was no
energy at or above Nyquist (and at and below -Nyquist for negative
continuous frequency). that makes it a little confusing for X[N/2] if
there is any energy in it. if there is 0 in X[N/2], then we're okay
and we can safely say that X[N/2+1] to X[N-1] meaningfully map only to
the negative frequencies x[-(N/2-1)] to X[-1]. X[0] remains the DC
component and X[1] to X[N/2-1] remain the positive frequency
components.

but after sampling, the continuous spectrum itself is periodic, that
is another reason to understand X[k] as being periodic in k with
period N.

same for the time-domain sequence, the points x(N/2+2:N)
can be considered the "negative-time" portion or just the
latter half of the periodic waveform starting at x(1) (which is really
x[0] since MATLAB is so stupid).

now, Greg, i am not going through your code at all.

That was not the purpose of the inclusion. It was to
yield plots, for those with MATLAB, that visually
demonstrate the difference between using ifftshift,
fftshift or neither.

After all, this thread has dragged on because I
recommend using ifftshift, and not fftshift, in
the time domain.

what's "time domain" what's "frequency domain". what difference, in
MATLAB or anywhere else, is there between the DFT and iDFT?



take a *big*
chunk of signal (say you got it out of a wav file, a million samples):

    x_input(1:1000000)

from that extract, by use of windowing, a smaller chunk to send to the
FFT.

    n = 100000;  % or whatever big number of your choice.
    N = 4096;    % FFT size

    x = x_input(n+1:n+N);       % extract it
    x = x .* hanning(size(x));  % window it

i don't care what the data is, as long as it's not noise (there has to
be some sense of smoothness or predictability of the signal).  now
look at the results of these two operations:

    X = fft(x);

    Y = fft( fftshift(x) );

or maybe we would say...

    Y = fft( ifftshift(x) );

which should not make a difference for N even.  so Greg, can you tell
us what the difference is between X and Y?  why might it be useful to
swap the two halves of x going into the FFT?

If it is something that my examples didn't cover, just
come out and tell me because I don't have a clue to
what you are getting at.

i said it before. if you pass the above x as defined by

x = x_input(n+1:n+N); % extract it
x = x .* hanning(size(x)); % window it

directly to the FFT and look at the results, and compare that to
passing it to the FFT by way of fftshift(), the latter will have the
center of the window positioned around n=0 whereas the former will
have the center of the window positioned around n=N/2. that's a delay
of N/2. that will effectively multiply every odd sample of X[k] by
-1. that will add a phase of +pi or -pi (take your pick) to *only*
the X[k] with k odd. a nice smooth phase response won't look so
smooth because pulses centered at t=0 have less phasiness than pulses
centered at t=N/2.




now the MATLAB lit says that fftshift() does not undo itself for odd-
lengthed arrays and that's why you need ifftshift().  that's very well
the case and i don't know what fftshift (or ifftshift) does for odd-
length arrays anyway.

ifftshift(x(1:N)) = [ x(1+floor(N/2):N), x(1:floor(N/2))]
fftshift(X(1:N))  = [ X(1+ceil(N/2):N), X(1:ceil(N/2))]

that's useful to know.  so, if it's odd length, ifftshift will move
the point precisely in the middle to the "t=0" location whereas
fftshift does not.

Again, I recommend that MATLAB newbies use ifftshift in
the ifft (time) domain and fftshift in the fft (frequency)
domain. Then most of the worry about whether N is even or
odd is mitigated .

i just would not recommend using odd-length FFT for the most part.
then there is no "Nyquist point" to swap with the DC point.

In typical situations using a power of two or
zero-padding to a power of two is the norm.

The deal here is the atypical situation instigated by an
inexperienced MATLAB user. Most of the time it is someone
who is committed to N odd in order to make t = 0 exactly
in the middle of the time waveform and/or someone who
doesn't have much data and is reluctant to throw away
one measurement point.

so, Greg, i am still curious if you understand what use one might
derive from swapping the two halves of the windowed input going into
the FFT?  if you don't get it, that's fine, i'll leave it to your
future.

I have only recommended the swap to take advantage of
symmetry about the "middle" of the waveform.

sometimes you want that "middle of the waveform" positioned around
t=0.

If there is
another reason, you'd better tell me now. I'm too old
to count on the future.

i can relate.

r b-j
.

Relevant Pages

  • Re: FFT with matlab
    ... a fftshift when dealing with symetrical time domain around ... This article is dealing with DFT (the title is Fourier ... the signal you are taking the FFT of is assumed to ...
    (comp.soft-sys.matlab)
  • Re: Correcting the effect of spectral leakage on Phase
    ... Don't forget that many real world signals (those which are ... That requires an odd number of samples I ... FFT analysis aperature instead of at the start, ... and the th sample is in the middle of a DFT ...
    (comp.dsp)
  • Re: MATLABs FFT and fftshifting the input
    ... The source code is exactly the same except fftshift uses ... ceiland ifftshift uses floor. ... I agree that MATLAB not using nonpositive indexing results ... nonnegative frequency interval by the fft. ...
    (comp.dsp)
  • Re: FFT Radix
    ... method of breaking-up an N-length FFT into two shorter length ones, ... Tukey algorithm. ... single step of decomposing of a size N = LM DFT into DFTs of size L ... it's obvious that one has no problem combining radix-2 and radix-4 ...
    (comp.dsp)
  • Re: Spectra of Unequally Sampled Data
    ... time samples the FFT requires. ... FFT of unequal spaced data ... FFT algorithm (of the DFT) is only applicable to evenly spaced ...
    (comp.soft-sys.matlab)