3
$\begingroup$

I am always confused between FFT and DFT. In both algorithm, it has been assumed that the signal is periodic (so my understanding is that, if you have a 20 sample point signal, and you do DFT or FFT, the algorithm assumes 20 sample points repeat).

Now here is the question, someone told me that DFT can take odd number of samples, and spectral leakage could be avoid if use DFT.

I disagree with the person because spectral leakage occurs in both FFT and DFT. And I also disagree because DFT and FFT can both take odd number of samples point, except that it would be slower in FFT case. Is this correct?

$\endgroup$
  • $\begingroup$ there are even FFT algorithms for length $N$ that are prime numbers. at least i remember seeing some IEEE paper saying so. certainly there are ways of decimating for $N=3^p$ or $N=5^p$. and those are odd $N$. $\endgroup$ – robert bristow-johnson Mar 29 '15 at 4:01
  • $\begingroup$ @robertbristow-johnson Bluestein's algorithm, which turns the FFT into a convolution of more conveniently-sized FFTs, so it's not exactly a prime-size FFT, but a multi-step process that accomplishes the same thing $\endgroup$ – endolith Apr 28 '15 at 14:38
4
$\begingroup$

An FFT is an optimization for computing the DFT that works well for any number of samples that is the product of mostly small prime number factors. They produce the exact same results, except for numerical noise. The factor 2 is common, but 3 and 5 are also small primes that can be used in a very efficient odd number length FFT implementation. Many newer FFT libraries (Accelerate/vDSP, FFTW, etc.) thus support odd length FFTs, not just powers of 2. On newer processors, the speed of an FFT is more limited by data cache size and policy and CPU instruction pipeline depth and hazards, not by the input being only a power-or-2 or not.

The algorithm makes no assumption about the signal being periodic (although some people do), as it is just a finite matrix basis transform. If the signal input isn't exactly integer periodic in the FFT width, with that width being cut out of a longer signal, then there will be some windowing artifacts, often called spectral leakage (but they have the exact shape as the transform of the window used, so they are far more related to the window than to the spectrum.)

If you change the size of a DFT or FFT window so that it is an exact integer multiple of the period of a purely periodic input waveform, then the windowing artifacts (or leakage) just happens to be all zeros.

$\endgroup$
  • 1
    $\begingroup$ down arrowed due to mistaken second paragraph. $\endgroup$ – robert bristow-johnson Feb 26 '15 at 23:28
  • 1
    $\begingroup$ The Discrete Fourier Transform and the Discrete Fourier Series are exactly the same and have exactly the same mathematics. The DFT periodically extends the data passed to it. If the DFT results are $$ X[k] \quad \quad 0 \le k < N $$ the periodic function the DFT "assumes" is $$ x[n] = \frac{1}{N} \sum\limits_{k=0}^{N-1} X[k] \ e^{j 2 \pi \frac{nk}{N}} $$ and that $x[n]$ is surely periodic: $$x[n+N]=x[n] \quad \forall n$$. ALL theorems of the DFT are consistent with the periodic extension of the input and the only theorem that does not require this periodicity is the Linearity theorem. $\endgroup$ – robert bristow-johnson Feb 26 '15 at 23:34
  • $\begingroup$ just to be clear, the DFT and the DFS are exactly the same and have exactly the same mathematics. but the DFS might have little hats on the input or output sequences, like $\hat{x}[n]$ an $\hat{X}[k]$ to indicate explicitly to the reader that the sequences are periodic. as a result, in the theorems of the DFT/DFS that do require periodicity, the discrete functions with the little hats don't need the explicit language of periodic extension, using the $ \bmod $ulo operator such as $$\hat{x}[n] \triangleq x[n\,\bmod\,N]$$ or $$\hat{X}[k] \triangleq X[k\,\bmod\,N]$$. $\endgroup$ – robert bristow-johnson Feb 26 '15 at 23:46
  • 2
    $\begingroup$ and on that note, there is no issue with the 2nd paragraph of the answer. DFT takes $R^n$ to $R^n$. Whether you want to assume that the output vector is a set of coefficients for DFS (and subsequently use it to extend the data), is up to the interpretation of the user. $\endgroup$ – thang Feb 26 '15 at 23:55
  • 2
    $\begingroup$ @robertbristow-johnson, I am going to reiterate what I said. DFT is a transform. It's just a matrix multiplication by a specific matrix. What is done with the result is up to the user. $\endgroup$ – thang Feb 27 '15 at 0:04
1
$\begingroup$

DFT stands for Discrete Fourier Transform and FFT stands for Fast Fourier Transform. FFT is just a name to refer to a very fast implementation of the DFT. So, basically they are the same thing. When using the FFT it is better that the length of the signal be a multiple of 2, for implementation reasons, so the it's usual to pad the signal with 0s until the length is a multiple of 2.

So, answering your question both "work" with signals of even or odd length.

$\endgroup$
  • $\begingroup$ Zero-padding to make the length a multiple of $2$ is the wrong thing to do if one is interested in computing the DFT purely for the information that it conveys: the results obtained from the FFT algorithm as the DFT of the extended sequence are not the same as the DFT of the original unextended sequence. On the other hand, the zero-padding works very well when one is not interested in the DFT per se but only as an intermediate result while implementing a fast linear convolution via $\text{FFT}^{-1}(\text{FFT}(x)\otimes\text{FFT}(y))$ where $\otimes$ is term-by-term multiplication. $\endgroup$ – Dilip Sarwate Mar 29 '15 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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