6
$\begingroup$

I've just stepped into the FFT's world since the last weeks, therefore I still don't have an clear overall idea of how to setup the frequency array.

In case of even number N, I usually do (with respect to the Nyquist cut-off frequency)

$f=\left(-N/2\,:\, N/2-1\right)*f_{s}$

but how does it work in case of odd number N. Is it just

$f=\left(-(N+1)/2\,:\,(N+1)/2-1\right)*f_{s}$

I thank you all in advance.

$\endgroup$

2 Answers 2

6
$\begingroup$

Short answer: yes, I think so.

Long answer: The FFT is just a fast implementation of the DFT. The frequency spacing of an N-point DFT operation is $\frac{f_s}{N}$. Samples of the DFT where $\omega \ge \pi$ correspond to the negative frequencies. If N is odd, then $\frac{N-1}{2} \cdot \frac{2\pi}{N}$ is less than $\pi$ and the next DFT frequency, $\frac{N+1}{2} \cdot \frac{2\pi}{N}$, is above $\pi$.

I think your answer is correct, and another way to think about it is that you have a DC bin, with (N-1)/2 negative frequencies, and (N-1)/2 positive frequencies.

update: MATLAB/Octave syntax for odd-N DFT frequencies:

freqs = (fs/N)*( (N-1)/2 : (N-1)/2 )

Python/Numpy/Scipy syntax for odd-N DFT frequencies:

freqs = (fs/N) * arange(-(N-1)/2,(N+1)/2)

Python/Numpy/Scipy syntax for even and odd N DFT frequencies ( via @endolith ):

fftshift(fftfreq(N,1./fs))
$\endgroup$
6
  • 1
    $\begingroup$ In Python, it's freqs = fftfreq(N, 1/fs), for both even and odd size. ;) $\endgroup$
    – endolith
    Feb 8, 2013 at 18:40
  • 1
    $\begingroup$ @BruceZenone: Incorrect! There is absolutely no need for every FFT algorithm to operate on even-length signals. The reason you usually see even numbered FFT lengths is because most people look at power-of-2 FFTs. They are not the only ones. The more general form is the prime radix (factor) FFT. $\endgroup$
    – Peter K.
    Feb 8, 2013 at 20:19
  • 1
    $\begingroup$ @endolith Thanks! That's a great tip and I had no idea that existed! $\endgroup$
    – Dave C
    Feb 8, 2013 at 20:35
  • 1
    $\begingroup$ @PeterK. I didn't know that :-) Thanks for the clarification. $\endgroup$
    – user2718
    Feb 8, 2013 at 20:54
  • 1
    $\begingroup$ @BruceZenone: You're welcome! It's an interesting side-area of FFT algorithms. Some early hardware implementations used distinctly non-2 prime numbers. $\endgroup$
    – Peter K.
    Feb 9, 2013 at 1:40
12
$\begingroup$

Posted for anyone who may find this useful...

I created a picture that shows DFT frequency bin spacing for odd and even cases of N where N is the number of samples. FFTs usually operate on an even number of samples (the algorithm works by repeatedly breaking the problem into halves), so only the even case applies. The DC component (0*fs) is always part of the computation . The bin at the nyquist frequency (fs/2) only shows up for the even case. The frequencies above the nyquist frequency reflect back on the negative side of the frequency axis in reverse order. For real signals the reflected FFT values are complex conjugates of their positive counterparts. There are two specific cases depicted on the complex plane, N=5 for the odd case and N=8 for the even case.enter image description here

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.